Sunday, March 18, 2012

Building a Strategy Game AI

This is the first in what I hope to be a regular series on developing an AI player for a turn based Strategy game.  The game in question is my current project called Shattered Throne which is inspired by the Advance Wars series of games and has been an idea I have been playing around with for many years.

This is actually not the first time I have started this game, it has seen several iterations in various languages over the years.  One of the more difficult problems I ran into was developing an efficient and worthy AI opponent.  I found some information, but it was always at a conceptual level, never getting into the actual details enough.

I am not an expert on this subject.  I expect to make several misteps and run into deadends during this process.  I am not even sure how long this will take exactly.  Perhaps it will be easy and hence the reason there has not been much specific information available.

My intentions on documenting and sharing the process are two fold.  One, I expect there may be others like me who would benefit from it.  And second, I hope that those who come across this project that know a lot more on the topic may provide some additional advice, wisdom, or simply point out what I am doing wrong.

What I have currently is a playable game, though filled mostly with developer graphics (except for the Unit Sprites and Leader Portraits).  When the game engine is ready for the next move, it requests a GameCommand from the current player.  In the case of a Human player, this is determined by their interaction on screen.  For the AI, it goes through what I am simply calling a ComputerBrain object.

Here then is the most basic of such objects, I call him Abe, for no other reason than it was the first name that popped into my head that started with the letter 'A'.  Abe is the most basic of AI players, he simply picks moves at random.  Here is what the Abe AI class looks like:

using System;
  using System.Collections.Generic;
  using Microsoft.Xna.Framework;

  namespace ShatteredThrone.AI.Brains
    class Abe : ComputerBrain
      Random _random;
      Pathfinder _pather;
      CombatEngine _combat;

      public Abe()
        _random = new Random();
        _pather = new Pathfinder();
        _combat = new CombatEngine();

      public override void Think(GameDetail gd, PlayerController pc)
        // get units to move
        List<UnitStatus> units = GetUnitsLeftToMove(pc.PlayerIndex, gd.CurrentState);
        // do we have any units left to move
        if (units.Count > 0)
          // pick a unit at random
          UnitStatus u = units[_random.Next(units.Count)];
          // get all possible moves for this unit
          List<Point> moveLocs = _pather.GetValidMoveLocations(u, gd.Map, gd.CurrentState);
          // pick a random move loc
          Point loc = moveLocs[_random.Next(moveLocs.Count)];
          // build and submit command to move
          SubmitMove(u, loc, pc);
          // get list of all possible actions at new location
          List<CombatAction> acts = _combat.GetCombatActionsByUnitAtLocation(u, gd.Map, gd.CurrentState, loc);
          // choose random action
          CombatAction ca = acts[_random.Next(acts.Count)];
          // build and submit action command
          SubmitAction(ca, u, loc, pc);
          // get available settlements to build
          List<Settlement> builders = GetAvailableBuildingSettlements(pc.PlayerIndex, gd.CurrentState);
          PlayerResources pr = gd.CurrentState.GetPlayerResources(pc.PlayerIndex);
          // get list of units we can afford
          List<int> buildableTypes = GetBuildableUnitTypes(gd, pr.Gold, pc.PlayerIndex);
          // do we both have enough money and places to build?
          if (builders.Count > 0 && buildableTypes.Count > 0)
            // get random settlement to build at
            Settlement s = builders[_random.Next(builders.Count)];
            // submit command to build random unit at random location
            SubmitBuild(buildableTypes[_random.Next(buildableTypes.Count)], s.X, s.Y, pc);
            // nothing left to do except end our turn

And here is a short video showing me playing Abe (normally I will pit AI players against each other, but in this case it would be dreadfully boring).

Part 2


Don Jovar said...

You should have audio commentary on the video.

DodgingRain said...

I'm not a c# programmers so take that into account here.
Are you calling Think once for Abe's turn? It looks like that is the case based on the code but in the video it looks like he Thinks multiple times in a turn?

I would start with two things. One would be to assign a weight to each action, the second would be to give Abe some visibility to his own moves so he can coordinate his units in the same turn and possibly across multiple turns which you would use when calculating the weights of each action.

With weight I would, for example, assign a weight to different actions and then total up the weight for each combination of things Abe can do with each unit in a turn. A move to an empty map location might have a weight of 1 while a move to a map location with a high defensive value might have a weight of 5 and a move to a location near one of Abe's other units might have a weight of 2. So Abe would under normal circumstances keep his units near each other in higher defensive locations with an optimal move to be a location near one of his own units that has a high defense (a weight of 7). Attacking an unit might have a weight of 3 while attacking an emeny unit that has already been attacked in the same turn could have a weight of 6 and maybe a weight of 4 if it was attacked in the previous turn. This would let Abe focus his attacks on units he has a higher chance to defeat. I'd then change the code so that it loops through each possible move and finds the weight and then loops through each possible attack at the moved to locate and adds that to the move weight. Then have Abe do the action that gives him the highest weight value.

Then add in some rules that modify weights based on Abes unit's health. So if the units health is below 30% a move to a location that is not in range of an enemy unit might be 5 times as highs it's normal weight.

I'm not sure how difficult it will be to implement based on your design as I have not worked with that sort of design before. Typically I have a players unit's as a list(of PlayerUnits) as a class level variable inside the player itself and I would store a simple structure inside each unit that described it's previous move. Not sure, you're method might be superior to mine, and sorry for the syntax, I'm a vb programmer by trade.

The above are basic strategies I use in any game I play with some ability to differentiate which action is best by adding a weight factor. Add in a random modifier to each actions weight which ocassionally lets Abe violate his rules and he should be more difficult to beat.

Harvicus said...

Thanks for the great insight DodgingRain. I will be putting several of those ideas in place on the next version.

I am calling Think() multiple times each turn, each call performs a single move. As the current game state/situation changes with each move made, I am not sure what information is worth saving from call to call.

I am sure I will have to come up with something though as the complexity of the AI increases and more computations are being performed. As it is, even with this most simplistic of AIs there is already a small noticable hesitation introduced into the animation cycle of the units.

Fuhans Puji Saputra said...

Hai, i am interested with your project especially the AI, could you please tell us how to make AI on the turn-based strategy game? because i am doing similar like yours. I am able to move the AI character by itself, but it is not follow the right procedure (not following the pathfinding). Thank you very much! I will keep in touch in this game!