Artificial Intelligence

Artificial Intelligence

First, I’m happy to announce that we’ll be releasing an interim beta later this week which will include the new AI for random single player matches.  This release will not have any of our lovely new single player stuff – it just gives the new, vastly improved AI to what is in there now.  (Including explosive units for you and the AI).

Ok, and now onto the main topic.

I’ve spent the last week working on our AI.  The existing AI had every response from “this is terrible” (Paul and almost everyone) to “it’s so good it must be cheating” (the guys on Three Moves Ahead).  I hadn’t touched the AI code in a year, and the first thing that I’d found was that the AI was actually broken – and always has been.  And the perpetrator was death animations, of all things.

A while ago we added death animations.  Beforehand, when a player died the player object was deleted.  But with death animations we stopped deleting the player and just set an “Alive” flag to false.  This was a pretty bad design decision actually, and everywhere in the code I had to go around checking whether a player was alive, when previously a player object existing meant that it was alive.

But I forgot to tell the AI code.  All of my advanced testing algorithms weren’t aware when players died in AI simulations.  The AI had no good metric for determining which of its plans were any good.  So it just went with the first one it made.

Anyway. I’m now going to explain what our AI does, and how it works.

Early on in my design process, I decided that I needed to split the AI up into two modules.  Module 1 (which I call the DoubleDummy module, in a nod to Bridge AI) needed to be able to beat any plan.  So I could feed in a plan of my units doing x,y, and z; and the DoubleDummy module would give me an emeny plan which would beat it

Module 2, the “Hand Generator” module, would generate a lot of different things the AI’s opponent might do.

I’ll be brief on how the DoubleDummy module works.  It splits the turn up into ten 0.5 second snapshots (ie one at time 0, one at 0.5, one at 1, etc), and for each snapshot it calculates all the areas within reach of your units which are either (a) dangerous (aimed at by an enemy who will beat you for example), (b) neutral (not in view of any enemies for example), or (b) “Green” – you will kill someone here (behind an enemy’s back for instance).  I rate all the green areas in terms of how good they are, and then try and find a path to that area without being in danger.

The DoubleDummy algorithm can produce 1 or 100 plans, all different.  That will be important later.  DoubleDummy can also react to multiple enemy plans – finding the one Green spot against five different enemy plans.

So once I had got DoubleDummy working, I set about on the Hand Generator – creating plans which the enemy might do.  And inspiration struck.  I could use DoubleDummy to make these plans without doing any extra work.  And here’s how:

Take a plan for Player 1 where his units do nothing – they stay where they are.  Camp basically. But they just don’t move.  This is easy to generate.

Use DoubleDummy to generate plans for Player 2 which will “beat” Player 1 doing nothing.  Generate say the best 5.

Use DoubleDummy to generate plans for Player 1 which will “beat” each plan generated for Player 2.

Use DoubleDummy to generate plans for Player 2 which will beat Player 1’s reactions to Player 2’s reactions to Player 1 doing nothing…

(and don’t throw away earlier plan iterations – keep them in the mix)

Continue until you run out of time.

Not only is this a brilliantly elegant solution, it actually mirrors what humans do when they play FS.  They generally imagine what the opponent is going to do, and try and beat it.

So we have say 30 plans for Player 1 and 30 for Player 2.  We simulate all of them against all of them, giving them points for kills and penalties for losing units, along with some other bonuses for “interesting” play.  The best Player 2 plan wins.

And it works.  You guys will be able to take a look later this week, and I’m looking forward to your feedback.  Right now it’s beating Bin regularly, which is a pretty good accolade…

8 Responses to “Artificial Intelligence”

  1. Ramsar:

    Interesting read, I admit I haven’t played any single player FS yet, but this article makes me curious. New AI, prepare for battle!

  2. Bleh:

    Please, please, don’t waste too much time and energy on AI stuff. Single player is _by far_ not what makes FS incredibly great.

    My biggest Christmas wish would be to get FS stabilized under both Windows and Wine, just eliminating the crashes and waypoint bugs. Then the matchmaking code could use some more polish/features/sense.

    pretty please?

  3. Ian:

    Hi Bleh, thanks for your comment.

    I promise that 100% stability and GUI usability is an absolute pre-release commitment from us.

    The reason I am working hard on a meaningful single player campaign is that there are a lot of people who will never play multiplayer unless they have a great time in single player. By having a good single player, we will end up having far greater MP numbers… in my opinion at least!

  4. Bleh:

    Okay, fair enough. I haven’t thought about that point since I jumped right into multiplayer after the tutorial.

  5. dete:

    First off: Thanks for putting the effort in to creating a decent AI. I understand Bleh’s point: A good human opponent will always be more satisfying to play against, and making sure the process of finding and fighting another person is really important. However! There are lots of times when I just want to play a game without having to worry about someone else’s schedule, and in those cases a good AI is invaluable. Also, I don’t know what your plans are for the campaign, but I can imagine that being good fun (and be pretty much pointless without an AI!).

    A question: How does your AI deal with incomplete knowledge in dark games? Do you just ignore the problem (the AI always sees the opponent’s position), or do you have a way of modelling possible movements between turns as well?

  6. Ian:

    Hi Dete, thanks for the comment.

    At the moment the AI sees perfectly in Dark. I am experimenting with basing the AI’s knowledge of “last known position” data but that tends to make the AI look significantly more stupid, and doesn’t tend to be as entertaining to play against.

  7. Jerawolfe:

    Keep working on that AI, good AI makes a game better, and I don’t like games that don’t keep their development keen on SP, since I actually enjoy that more most of the time, less hassle.

    SP is important.

  8. Jonathan Dickinson:

    Regarding Dark:

    1. Get the Hand Generator to generate `x` hands; knowing full well where the human is.
    2. Discard `x` *random* hands (*picking* random hands could work better; guess you would have to play test it).
    3. Your algorithm as usual.

    I would also give this one more time to fiddle about (as I would think a human would take more time as well).

    In my opinion is does make it completely fair; because while humans don’t have unfair knowledge they do have intuition. Discarding good knowledge is probably a good way to achieve something that seems like intuition (remember the machine might discard the best plan there is – because it’s random).