Yes, the complexity of Magic is overwhelming! Where do we start?
Let's start by laying down some well tried heuristics (rules of thumb) for the development process.
Walk Before You Run - this means we might have to try to solve a simpler version of the problem first, learn some lessons, and then attack the bigger problem we really want to solve. Sure we want to play any kind of Magic game out there, but starting off by staring at 10,000+ card descriptions just leads to drooling. Think about ways to cut the problem down to size. Work with only the cards of a recent core set, for example, instead of every card ever made. How about limiting the number of colors? Eliminate enchantments or some other aspect of the game, until later. Even programming some BabyMagic game is going to be a challenge, so start easy. You won't get discouraged (so fast).
Separation of Concerns - this means not trying to solve everything at once in one ball of wax. Magic naturally falls into separate areas, such as deck construction and play. There are even areas such as the metagame and trading values that I won't try to talk to right now. You can attack deck construction separately from play, even if you want to integrate them eventually.
Self Play - the interface of your system should allow the system to play against a copy of itself, not just a human being. The computer can play thousands of games while you sleep, improving it's algorithms, databases, etc. Self play assumes that your AI is written so that learning/improvement can be scored independently of a human. A genetic algorithm is an example of that.
I'm sure we can come up with other high level heuristics like these, but for now this will do nicely.