I did it, my AI can run on multiple threads (I think I’m going to call it Skynet from now on). The game flow part was much less stateless than I thought, and I needed that to be able to share it safely between multiple threads, so I had to do some work there. Otherwise, it went pretty well. Here are some perf measures I made using an especially expensive test. The test is composed of two AI players with each 7 Shocks and 7 Mountains in their hands. Remember that I did not implement the one land per turn rule yet so that makes quite a lot of “futures” to look into 🙂 This is on my quad core. Trying with more than 4 threads gives approximately the same result than 4 threads (even going up a little, which is normal).
The times are for the complete resolution of the state, which is the playing and resolving of all 14 Shocks and 14 Mountains in the game. For the 4-thread run, that means less than half a second per “card played” in average, which ain’t too bad I think (considering there is still room for optimization)! Obviously the first of the 28 cards is much more costly to play than the last.
As you can notice, the gain is not linear with the number of threads (i.e. 2 threads don’t run twice as fast as 1 thread). This is due to a design choice I made which is at the heart of my implementation. Basically, when faced with a choice, the AI will split the work to the different worker threads using the different possibilities it has for that choice. For example, when asked to mulligan, there are only two choices (yes/no), so we can only really use two threads, even if there are more available. On the other side, when given priority, the AI has initially 15 choices (7 shocks + 7 lands + pass) and this is where it pays off. The AI can distribute the 15 choices throughout the X threads allocated for the computation. So we get only a 2x speed up in average because a lot of the choices involved in that case don’t have that many possibilities (targeting a player = 2 choices, playing mana is also often very simple).
The good news is that we get the maximum gain when the situation is the most complex (AI faced with many choices). I do think that with more rules and more complex boards, there will be more choices involved and so I think I can expect to get more out of my cores! I’m satisfied with the result for now anyway… Now I have some cleaning to do in that code.. and next I think I’m gonna take a break from AI!