Monday, July 16, 2007

AI Testing Framework

My idea is to test different AI routines on a non-trivial, real problem – a game of Magic. Programming the AI should be made as simple as possible so it is easy to get things up and running.

What led me to this idea is that I keep thinking about the AI and how to make it smarter. Then I always come back to the question what is “smarter,” in this case I wish it played more like another human player. The problem with many AI routines and methods is that they are complicated. Even simple depth first or breadth first routines are difficult to integrate into a working program. More sophisticated algorithms like min-max are superior in many ways, but it is hard to test the success of one AI method over another.

It would be great to have a simple Magic game with about 100 cards that you could easily program and test your favorite AI algorithm. Even combat is difficult enough. When should you trade? When should you race? If I have two 2/2 creatures and my opponent has 7/7 creature, should I attack? Yes if he is at 2 life, or if I am holding a card like Lava Axe and I need to knock him down 2 more life.

Testing the algorithms with a non-trivial game like Magic would be great. You could play against the computer and see the mistakes of the AI in action. Maybe at first your combat routines would just check the creatures that are on the field and then later adjust its play according to what cards it is holding. AI versus AI would be cool also. Each AI player could use the same deck, and the better AI would win. I still believe the only way to thoroughly test the strength of an AI method is to play it yourself. A great AI routine should be able to beat you half of the time if you are both playing with the same deck. I know all this is just a dream, but a lovely one.

You could even host a Magic version of the “Turing Test” where people play an unknown player and have to guess if the opponent is another human player or a computer.

In reality unless many people are interested in this, and I do mean at least 30, I probably won’t program this. (Or at least not any time soon.) I have all of the components in MTG Forge, the GUI, the logic, the cards, but I would have to rework some parts of it. If I coded this, and that is a big if, it would be in Java. Also I don’t know that much about AI. Yes I’ve glanced at some AI books but I didn’t see any useful cut-and-paste code. AI books and websites seem to be mostly theory. I’m sure that there is some good AI information somewhere out there, but it is really hard to find. Even if I could just find some AI that worked great it combat, I would be eternally grateful. I’ve probably seen 100 different AI routines for playing Tic-Tac-Toe, but where are the routines that play Tetris?

No comments: