This is the fourth and final part in this series that explains how the min-max algorithm could improve MTG Forge's AI. I'm going to summarize the previous three articles.AI programming is hard. Actually any computer programming is hard, but AI programming is even harder. I feel that this is important, so I keep emphasizing this point. It is like saying if you know English then you should be able to write a novel or be able to read a medical dictionary. Writing a novel or reading a medical dictionary is a very specialized form of English.
The min-max algorithm works for two player games like chess and should also work for Magic: The Gathering. Actually using min-max in MTG Forge is very hard because of the programming. You have to copy everything and iterate through the each player's actions. Basically the min-max generates future game states and picks the best one. (Instead of copying the game state it would be better to implement an undo system using Command objects. That way you wouldn't have to copy everything.)
The min-max algorithm has to figure out who is winning. The min-max algorithm might generate 1 or 2 moves ahead and then try to determine which player is winning. Determining which player is winning is very complicated and will require much tweaking. Most of the time the min-max algorithm will not be able to generate all future game states because the number of possibilities is astronomical.
Well this ends this series of four articles that examines the question, "Why programming AI is hard?" The min-max algorithm is very important and I'll bore you with more details later. (joke)
I'll try to get back to talking about MTG Forge. Monday I'll post a new version and Wednesday I'll talk about some of the harder cards to program like planeswalkers,
ReplyDeleteKiki-Jiki, Mirror Breaker and Adarkar Valkyrie.
Wednesday is a very technical post about alpha-beta, so put on your thinking hat.
ReplyDeleteI was thinking about the problem of hiddne information, and came up with something akin to Monte Carlo method. Simply said, at each step randomly generate the hidden information (hands, libraries, etc.), then assume all information is known. Find the optimum strategy.
ReplyDeleteGo back to start, generate the hidden information again, randomly - repeat.
After, say, 100 attempts, you might have good idea of which strategies are generally successful, and which only have low probability of success. The thing is that the random generation must take into account known information. I.e., if computer returns your creature to hand, it knows one card in your hand is that creature, and will only randomly generate the others. Or it might decline to cycle a card if it thinks that average value of top card of its library is lower, but would cycle it if it happens to know that the top card of its library is very good.
The only information AI needs for this approach is your decklist. In real life, you often don't know opponent's decklist, but you know some constraints (for example tournament format etc.) In computer Magic that is, by definition, unrestricted, I think that knowing the opponent's decklist is reasonable condition.
I think we should wait a bit with releasing a new version... there are still a few manapool bugs in our current Beta. Hopefully they'll be fixed soon though :)
ReplyDelete