Sunday, March 25, 2012

Turn Based Strategy AI part 2

Continued from Part 1

While the first AI shown last time was not terribly exciting or competent, it was a necessary first step.  This time I am adding in some extra logic to help the AI select good moves.  The first thing needed to enable this is to provide some manner of scoring various moves.  Here is the routine I am using to score a potential move.







private int ScoreLocationForUnit(Point loc, UnitStatus u, GameDetail gd)
        {
            int ret = 0;

            // prefer to move instead of standing still
            if (loc == u.Location) ret = -1;

            // get score based on attack/defense mods for this location
            ret += gd.Map.GetMapSpaceTerrainAttackMod(loc);
            ret += gd.Map.GetMapSpaceTerrainDefenseMod(loc);

            // adjust score by settlements at this location
            Settlement s = gd.CurrentState.GetSettlementAtLocation(loc);
            if (s != null)
            {
                // update by settlement attack/defense mods
                ret += s.DefenseBonus;
                ret += s.AttackBonus;
                if (gd.CurrentState.AreFriendly(s.Owner, u.Owner))
                {
                    // settlement is owned by us, avoid being here if could build here
                    if (s.CanBuildUnits) ret -= 3;
                    // if current unit is hurt, and the players faction allows units to heal in settlements
                    if (gd.CurrentPlayer.HasPassive(Faction.FactionPassive.HEAL_IN_SETTLEMENTS))
                    {
                        if (u.CurrentDamage > 0) ret += 1;
                        if (u.CurrentDamage >= (u.MaxHP / 2)) ret += 2;
                    }
                    // if this unit generate extra income on settlements, give it more incentive to be here
                    if (s.GoldIncome > 0 && u.HasTrait(UnitTrait.CHARITY)) ret += 2;
                }
                else
                {
                    // always good to capture settlements
                    ret += 2;
                    // even better fully capture
                    if (s.Owner == Globals.PLAYER_NONE) ret += 2;
                }
            }

            // prefer to be next to our own units
            ret += GetAdjacentMovedFriendlyUnits(u.Owner, loc, gd.CurrentState);
            // if this unit has banding, give extra bonus for moving next to units of the same type
            if (u.HasTrait(UnitTrait.BANDING))
            {
                ret += gd.CurrentState.GetBandSize(loc, u.Owner, u.UnitType);
            }

            return ret;
        }

The various values the final score is made up from is mostly guesswork at this point. I am taking into account such factors as:

  • Terrain Attack and Defense modifiers
  • Capturing Settlements
  • Using Settlements to heal damaged units, a feature of the Empire faction shown so far
  • Not blocking its own Unit Creation by standing on Castle spaces
  • Factoring how the Priestess unit generates extra income when standing on settlements (the Charity trait)
  • A preference to move from its current location, a small cheat until I have a proper strategic vision for the AI
  • A preference for standing next to its own units that have already moved, as it is important to protect your flanks in this game
  • Units that have the Banding trait such as Guardians gain extra attack strength by being next to friendly units of the same type, something factored in

The move location is just one part of the score equation, the next part comes from what actions a unit takes once they move. Currently there are two possible actions, Attacking and Healing, both of which are computed as follows:

private int ScoreHealForUnit(Point targetLoc, GameDetail gd)
        {
            int ret = -1; // doing nothing is better than healing target that does not need it

            // get target unit
            UnitStatus u = gd.CurrentState.GetUnitAtLocation(targetLoc);
            if (u != null)
            {
                // score the heal based on how badly unit requires it
                if (u.CurrentDamage > 0) ret = 1;
                if (u.CurrentDamage >= 2) ret += 1;
                if (u.CurrentDamage > (u.MaxHP / 2)) ret += 1;
                if (u.CurrentDamage > (u.MaxHP / 3)) ret += 1;
            }

            return ret;
        }

        private int ScoreAttackForUnit(UnitStatus attacker, Point attackLocation, Point targetLocation, GameMap m, GameState gs)
        {
            int ret = 0;
            UnitStatus target;

            List results = _combat.GetAttackResults(attacker, attackLocation, targetLocation, m, gs);
            // loop through all returned results
            foreach (AttackResult ar in results)
            {
                // subtract damage caused to friends, add damage caused to enemies
                if (gs.AreFriendly(attacker.Owner, ar.TargetOwnerID))
                {
                    // will this kill ourselves?
                    if (!attacker.CanSurviveDamage(ar.Damage))
                    {
                        ret -= 3 + attacker.CurrentHP;
                    }
                    else
                    {
                        ret -= ar.Damage;
                    }
                }
                else
                {
                    // will this kill the target?
                    target = gs.GetUnitAtLocation(ar.TargetLocation);
                    if (target != null)
                    {
                        if (!target.CanSurviveDamage(ar.Damage))
                        {
                            // bonus is 4, + current HP (do not want to reward too much overkill)
                            ret += 4 + target.CurrentHP;
                        }
                        else
                        {
                            ret += ar.Damage;
                            ret += ar.TotalComboPoints;
                        }
                    }
                    else
                    {
                        // could not find target unit for some reason
                        ret += ar.Damage;
                        ret += ar.TotalComboPoints;
                    }
                }
            }

            return ret;
        }


We score nothing for unecessary healing, and give higher weight to units that are more heavily damaged. Attacks are scored as a comparrison of damage caused vs damage taken. Extra points are scored for killing a unit, including an adjustment to bias against overkilling them.

This yields the following code for determining what move a unit should make:

private int ScoreActionForUnit(Point src, UnitStatus u, CombatAction ca, GameDetail gd)
        {
            int ret = 0;

            switch (ca.ActionType)
            {
                case CombatActionType.ATTACK:
                    ret = ScoreAttackForUnit(u, src, ca.Location, gd.Map, gd.CurrentState);
                    break;
                case CombatActionType.HELP:
                    ret = ScoreHealForUnit(ca.Location, gd);
                    break;
            }

            return ret;
        }

        private void SubmitBestMoveForUnit(UnitStatus u, GameDetail gd, PlayerController pc)
        {
            int currentBestScore = -10000; // always want to do something
            Point currentBestMoveLocation = new Point(u.X, u.Y); // by default go nowhere
            CombatAction currentBestCombatAction = new CombatAction(u.X, u.Y, CombatActionType.IDLE); // and do nothing

            // get all possible move locations for this unit
            List moveLocs = _pather.GetValidMoveLocations(u, gd.Map, gd.CurrentState);
            foreach (Point loc in moveLocs)
            {
                // score this move location
                int locScore = ScoreLocationForUnit(loc, u, gd);
                // get all possible actions at this location
                List acts = _combat.GetCombatActionsByUnitAtLocation(u, gd.Map, gd.CurrentState, loc);
                // loop through all possible actions at this location
                foreach (CombatAction ca in acts)
                {
                    // score this action
                    int actionScore = ScoreActionForUnit(loc, u, ca, gd);
                    // is this our best score so far?
                    if ((locScore + actionScore) > currentBestScore)
                    {
                        // set this as our best possible move
                        currentBestScore = locScore + actionScore;
                        currentBestMoveLocation = loc;
                        currentBestCombatAction = ca;
                    }
                }
            }
            // perform the determined best move/action
            // build and submit command to move
            SubmitMove(u, currentBestMoveLocation, pc);
            if (currentBestCombatAction.ActionType != CombatActionType.IDLE)
            {
                // build and submit action command
                SubmitAction(currentBestCombatAction, u, currentBestMoveLocation, pc);
            }
        }

And finally the modified Think() function from last time with these new additions:

public override void Think(GameDetail gd, PlayerController pc)
        {
            // get units to move
            List 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)];
                // do best move for this unit
                SubmitBestMoveForUnit(u, gd, pc);
            }
            else
            {
                // get available settlements to build
                List builders = GetAvailableBuildingSettlements(pc.PlayerIndex, gd.CurrentState);
                PlayerResources pr = gd.CurrentState.GetPlayerResources(pc.PlayerIndex);
                // get list of units we can afford
                List 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);
                }
                else
                {
                    // nothing left to do except end our turn
                    SubmitEndTurn(pc);
                }

            }
        }

Once again, a short video showing this new AI in action.

Though this version of the AI puts up a decent fight, it has the strong tendancy to just wait around until something gets in range. It is missing the aggression of moving towards the other player and mounting a true attack. This is something I plan to address next time.

Continued in part 3

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);
        }
        else
        {
          // 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);
          }
          else
          {
            // nothing left to do except end our turn
            SubmitEndTurn(pc);
          }
        }
      }
    }
  }

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