Spring news

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 🙂

Advertisements

About fparadis2

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

7 Responses to Spring news

  1. Ben says:

    This seems like a good reason to use a profiler or other performance tools. Have you timed how long it takes to reset for the AI’s next choice? I wonder how many of those can be run per second.

    I also wonder about the overhead of running in a transaction. I didn’t double check the code, I thought that was in Mox.

    • fparadis2 says:

      Hello Ben,

      I do use a profiler, but there’s no immediate bottleneck. The shear number of min max steps is astounding (> 1 million for complex scenarios – that runs in maybe 10-20s), so I think I will gain most by trying to get the same results out of less evaluations, thus the importance of considering the same cards only once.

      About transactions, I do see a small cost associated with that, but it’s pretty small (<5%). Also, since the whole system is based on that, I don't really see how to do without them! The overall big time consuming methods are the small, often-called getters (Card.Zone, Card.Controller). These can be called 10s of millions of time in a single AI choice. Again, in my opinion, less evaluations to try = less code to run = faster.

      • Ben says:

        Speaking of the getters, why do you have them all go through your AttachedProperty system? I understand the reasoning if you need to apply an unknown number of properties to an object, but I can’t figure out the benefit here. Is it so you can more easily apply modifiers and limit when they can be applied?

        I was hoping that was something you could greatly simplify. Although it would be fair to say that most of the code in the class ValueEntryStore confuses me.

      • fparadis2 says:

        The first reason to this abstraction is to enable transactions when setting properties (being able to rollback them). This is used when the AI ‘tries’ things.

        The second reason is to enable replication, which is taking a value on a given game instance and replicating it on a client instance. This is used obviously in the server/client architecture, but AI also uses a separate replicated game for choosing a move.

        The third reason is that I can apply modifiers/effects on any property registered to the system (Think +1/+1 on P/T) without having to add any special code in the object containing the property (here, the Card class). Nice!

        I could do all these things ‘manually’ for each property, but it would get tedious and the maintenance cost would go up (what happens when I need to change how replication or transactions work, which already happened in the past). This abstraction enables me to do the change for all properties at once.

        Because those reasons are mainly related to setting a property value, I guess I could optimize the most called getters by using a direct variable (only the properties where I know there won’t be any effects though). Currently, I use the ValueEntryStore as the storage behind all properties. It’s basically just a sorted array for decent binary search capabilities.

      • Ben says:

        Thank you for the detailed explanation. I hope you don’t mind these questions. This is a pretty complex system and I like to learn why such systems choose certain implementations.

        Is there a significant performance improvement by using your binary search and insert compared with the SortedList or SortedDictionary generic classes? If so, I may have to study them more.

        Some reference for SortedList is here.
        http://msdn.microsoft.com/en-us/library/ms132319.aspx

      • fparadis2 says:

        I don’t mind 🙂

        This is a very good question.. if you look at the code for SortedList, you’ll see that it is in fact implemented as two sorted arrays! Because my need is so specific and I need every bit of performance, I need my own implementation though. SortedList does too much (it handles key/value pairs while I just need sorted values) and lacks some of the features I need (modifiers!). SortedDictionary is an heavyweight collection, implemented as a binary tree. The downside of trees is that each node is allocated possibly anywhere in memory and thus much less cache-friendly than a linear array. Its advantage is its insertion speed. In my case, I’m doing way more reading than writing in this collection, so I’m better off with better memory usage & locality.

  2. Pingback: Struggling with combat | Mox

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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