Multithreaded AI performance

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.

Skynet is alive!

Skynet is alive!

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!


About fparadis2

Lead Game programmer
This entry was posted in Mox. Bookmark the permalink.

3 Responses to Multithreaded AI performance

  1. LokiX says:

    Cool stuff. Looks pretty cool at this stage.

    Although I don’t think it’ll be too soon, I wonder when we’ll get to test this. =D

  2. Snacko says:

    Do you allocate the worker threads for a whole path in the tree or just one node?
    Because if you do the first thing then when you try to limit the AI execution time to some arbitrary amount, the tree of possible futures that were evaluated will be heavily limited to one branch. This makes the AI heavily predictable and biased on the first choices.

    If you haven’t considered it yet, this may be the right time to see how your implementation performs under a time constrain as AI should have one (can’t have the player waiting for a couple of minutes for each AI move).

  3. fparadis2 says:

    Each worker thread gets to evaluate one complete subpath of the tree. So I could start by dispatching the “best subpaths” (using another heuristic…) and then stop them when the time is up.

    Honestly, it’s hard to evaluate how good my AI really is until I get more cards done and I see more gameplay situations. Before doing such blunt optimizations such as artifically cutting a whole subpath of the tree, I want to be able to measure the impact in more realistic cases. That’s why I did not implement a time constraint (yet).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s