Hey everyone, it’s been a while since I wrote!
Since my last post, I’ve been working on solving the second problem I discovered a few months back: having the minmax algorithm ‘seeing’ exactly the same game state when trying different choices. This is essential to the algorithm working alright and was due to a skew between my sequencing module and my minmax module. They were not being on the same page. The sequencing module would start trying a choice from a given point while the minmax module would start from a slightly later point. I solved this by moving all the “replay” glue code in the sequencing module, so that the minmax module can concentrate on the minmax algorithm. This way, replaying parts of the game is always consistent.
After that, I kinda came to realize that the performance of the minmax algorithm is not so great, even with pretty intense multi-threading. It can really only check one or two ‘plies’ ahead (a ply can thought of as another step in the future the AI is trying). I’ve read more about minmax since then (thanks for mtgrares for this link) and I’d like to implement iterative deepening sometime in the future. Iterative deepening consists of applying the minmax algorithm to only 1 ply, then using the result of this pass for a 2-plies pass, and so on, until satisfied with the result. This technique can be used to give the AI a given amount of time to think instead of a given amount of plies. Also, it can actually make the algorithm go faster (which is a bit counter-intuitive) due to the pruning nature of the alpha-beta technique.
For that, I still need to be able to squeeze in a few more plies, so I’ll turn around to more down-to-earth optimisations. Especially, treating all cards of the same type the same would help me a lot. For example, when you have 4 shocks in your hand at a given time, it’s useless for the AI to try them all out, they are exactly the same and will have the same effect. Doing this optimisation in your hand is easy, but not so trivial in the battlefield, where effects can introduce variations in cards otherwise identical.
If anyone has experience in applying min-max algorithms to complex card games, please contact me, I’m interested in your advice or your code 🙂