I finally got around to finish my min-max AI toy model, a Tic Tac Toe AI! I found out the hard way that creating an actual AI in a real situation, in a generic way, is harder than what the wikipedia page makes it look with its simple formula 🙂 Also, I spent a lot of time debugging small issues because even for Tic Tac Toe, the graph of possibilities can be quite daunting (9! = 362880 possibilities for the first move). So I had to imagine some ways to retrieve debug information about what is going on. I think I’ll have to push this further when I get to the real implementation with MTG. Otherwise, the AI just feels like a black box: “I chose to do this.” and then you go “Why the hell did it choose that move? It’s a losing move!”.
But now, it’s all fixed and my AI never loses in normal games 🙂 I also got surprised by some situations, where I would test a simpler case. Something like:
XX_ ___ ___
Now, where should the AI place its O? At first, I was expecting it to block the X line, of course. But it turns out it gives any move (the first move it evaluates in fact). It took me some time to figure out why that is. Basically, the AI is telling us that it’s going to lose whatever it does, so it doesn’t even bother trying a decent move. Indeed, if you block the line, the other player can place an X in the middle and the O player is screwed because X has two possible lines next turn.
XXO _X_ _..
It’s kind of creepy to be corrected by an AI 🙂
What’s left to do before attempting the MTG implementation:
- Alpha-beta pruning
- Simpler implementation + simpler integration with the game
- Support for multi-choice game (in Tic Tac Toe, every player is asked the same thing: what’s your next move? But in MTG, there’s a lot of choices to be made: “What card do you play? What player do you target? How will you pay this cost?”)
- More debug info 🙂
Next time, I’ll try to delve into the change in paradigm I had to make with regards to the game sequencing to make this work (solving the problem established in my last post).