Patrick Buckland is the lead programmer responsible for the development of the Live arcade game Duels of the planeswalkers. He recently started a series of articles on the development of the game. His last paper exposes the challenges he and his team had to overcome to produce a convincing/challenging AI that could run on an Xbox 360. It’s very interesting for me to compare their results with what I came up with for Mox, especially since I’m actually in this very process of high-level AI optimizations. I say high-level because I’m not chasing after micro-optimizations. This ain’t about shaving a few milliseconds of the clock. It’s about what assumptions you can make about the game of Magic and what shortcuts you can take to drastically improve AI performance.
First, their approach to AI is exactly the same as mine: let an algorithm explore all the possible futures of the game starting from the current state. This is the very definition of minimax AI. Of course, it’s impossible to examine all the futures so you have to stop looking when far enough in the future. This look-ahead distance is kind of arbitrary and must be tweaked to balance speed and challenge. An AI that can look further ahead in the game will likely be more challenging, but will also take more time to decide on a move. Patrick Buckland suggests that about 3 moves ahead is enough to create a convincing AI. I have yet to experiment on this number in Mox.
Even when cutting off the tree at some depth, I quickly realized that other assumptions have to be made to help the AI cut down on the number of possible paths in the tree of futures.
Here is some points that Patrick Buckland is discussing:
- Optimizations of the engine: When trying out different possibilities, the AI is actually running the game engine. So optimizing the game engine should help improve the AI speed. While I did not put any effort in this, I expect that I can shave off pretty easily about 50% of the computing time, strictly in the engine, mostly by targeting problematic sections.
- Parallelism: This is something I thought about without actually trying it. Although it would require minimal changes in my codebase, I think it would actually be quite easy to do. A 4x improvement on quad cores would definitely be welcome. I’ll keep that one as a dessert 🙂
- Dismissal of pointless actions: I thought about that one, and I didn’t implement it yet, as I want to try to shave off time elsewhere before trying to push the AI too much on a guided rail. I would like to be surprised by the AI. If damaging yourself is actually the way to win, why not? Realistically though, these cases are so rare that it can be worth eliminating those possibilities, so I think I might have to do that someday.
- Dismissal of unecessary actions: This one is actually the one where you can have some of the most important savings, especially when it comes to the stack. The article explains that very well. This is something that I began to implement and I really saw huge improvements.
- Suppression of pointless depth: This one is also very important and I implemented it very early. Basically, after a couple of “moves”, you let the spells resolve and then you observe the result. It’s not valuable to try to play other spells on top of an already complex 10 spells stack.
- Pre-sorting of actions: This is important if you plan on cutting off the AI after a fixed period of time, which I don’t do for now. I would like to not have to resort to this.. don’t know if that will hold in complex situations.
The author then goes on to discuss a feature of their engine that allow multiple instances of the AI to run at the same time. He basically describes a transactional model where only the modifications are synchronized between the different instances. Mox features exactly the same kind of transactional model. This same synchronisation mechanism is used to bind the server instance to the different UI client instances. Right now, the Mox AI runs on the main ‘instance’ but I could easily add more ‘client AI’ instances that would synchronize with the main instance on different threads (through various cunning multi-threaded semaphores and witchcraft, as Patrick Buckland says).
It’s not clear from the article whether or not the AI runs ‘while’ playing, thus trying to use the human player thinking time as time for AI computations. Maybe someone who has played the game can answer.
So it looks as I’m not totally off the track with my implementation. This article gave me confidence about the direction I took and some very good ideas about future optimizations 🙂
Edit: by the way, I added a measure of raw AI performance for comparison. I currently compute ~650 “futures” per seconds. In the article, Patrick claims being able to compute “thousands” of them per seconds so I guess I have some work to do on this side too!