Sunday, April 21, 2013

Programming a Turn Based Strategy Game AI part 11

This time I want to take a look at the Tactical AI Module, which is responsible for making attacks. While quite an important module, this ended up being one of the most straight forward and simple modules to put together. It uses a simple brute force method that looks at every possible attack for every AI unit, and chooses the best move.

The general structure is simply:
  • Loop through all units able to move
    • Loop through every space this unit may move to
      • Loop through every valid target per space
        • Simulate the attack and score the results
      • Return the highest scoring attack action for this unit
    • Return the highest scoring attack action from all units
  • If the attack score is greater than a minimum threshold
    • Perform the action
  • Else
    • Signal that we have no more moves

If a valid attack move is generated, it will be performed, and then the whole process will start over again based on this updated state.

        public override AiAction GetNextMove(GameDetail gd)
        {
            AiAction ret = null;
            List possibleActions = GetUnitActions(gd.CurrentState, gd.Map);

            if (possibleActions.Count > 0)
            {
                float bestScore = MINIMAL_SCORE;
                foreach (AiAction aa in possibleActions)
                {
                    if (aa.ActionScore > bestScore)
                    {
                        bestScore = aa.ActionScore;
                        ret = aa;
                    }
                }
            }
            // if did not generate any moves, set done flag
            if(ret == null)
            {
                _noMoreMoves = true;
            }

            return ret;
        }

        private List GetUnitActions(GameState gs, GameMap gm)
        {
            List ret = new List();

            // get units to move
            List units = GetUnitsLeftToMove(gs.CurrentPlayer, gs);
            // loop through available units to find best move
            foreach (UnitStatus u in units)
            {
                // get best move for this unit
                AiAction act = GetBestMoveForUnit(u, gs, gm);
                // is this move better than our current best move?
                if (act != null)
                    ret.Add(act);
            }

            return ret;
        }

        private AiAction GetBestMoveForUnit(UnitStatus u, GameState gs, GameMap gm)
        {
            float currentBestScore = MINIMAL_SCORE; // 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, gm, gs);
            foreach (Point loc in moveLocs)
            {
                // get all possible actions at this location
                List acts = _combat.GetCombatActionsByUnitAtLocation(u, gm, gs, loc);
                // loop through all possible actions at this location
                foreach (CombatAction ca in acts)
                {
                    // score this action
                    float actionScore = ScoreActionForUnit(loc, u, ca, gs, gm);
                    // is this our best score so far?
                    if (actionScore > currentBestScore)
                    {
                        // set this as our best possible move
                        currentBestScore = actionScore;
                        currentBestMoveLocation = loc;
                        currentBestCombatAction = ca;
                    }
                }
            }

            return new AiAction(AiAction.AiActionType.UNIT_MOVE, u.UnitID, currentBestMoveLocation, currentBestCombatAction, currentBestScore);
        }


As usual, it all comes down to how we score each possible attack.  Shattered Throne is a perfect information game (all players have complete knowledge of the current game state) and also features no randomness in combat.

This allows me to pass each attack the combat engine, which returns a list of outcomes.  Each outcome is then given a score, and the total score is returned.

I chose to base my scoring algorithm on the value of a single health point.  This is computed for each unit as that units total cost divided by the unit's max health value.  Non damage related effects that resulted from combat I tried to estimate their value best I could.

        private float ScoreAttackForUnit(UnitStatus attacker, Point attackLocation, Point targetLocation, GameMap m, GameState gs)
        {
            float ret = MINIMAL_SCORE;
            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 -= attacker.Cost;
                    }
                    else
                    {
                        ret -= (float)ar.Damage * attacker.UnitGoldToHpRatio;
                    }
                }
                else
                {
                    // will this kill the target?
                    target = gs.GetUnitAtLocation(ar.TargetLocation);
                    if (target != null)
                    {
                        if (!target.CanSurviveDamage(ar.Damage))
                        {
                            // reward killing blow
                            ret += target.Cost;
                            // if attacking unit has raise dead, score extra points
                            if (attacker.HasTrait(UnitTrait.RAISE_DEAD))
                            {
                                ret += 10;
                            }
                            // score points if attacking unit has rampage and will refresh
                            if (attacker.HasTrait(UnitTrait.RAGE))
                            {
                                ret += attacker.Cost / 3;
                            }
                        }
                        else
                        {
                            // award score based on damage caused to target
                            ret += (float)ar.Damage * target.UnitGoldToHpRatio;
                            // does this attack add any conditions?
                            if (ar.AddedCondition != null && ar.AddedCondition.IsNegative)
                            {
                                ret += 3;
                            }
                        }
                    }
                }
            }

            return ret;
        }


In addition to attack actions, several units have support actions which affect friendly units.  These are each dealt with in the same manner.

Empire priestess units can heal and remove negative conditions from friends:

        private float ScoreHealForUnit(UnitStatus actor, Point targetLoc, GameState gs)
        {
            float ret = MINIMAL_SCORE;

            // get target unit
            UnitStatus u = gs.GetUnitAtLocation(targetLoc);
            if (u != null)
            {
                // determine how much the unit is healed
                int amtHealed = (u.CurrentDamage < GameEngine.HEAL_AMOUNT_HEALED) ? u.CurrentDamage : GameEngine.HEAL_AMOUNT_HEALED;
                // multiply amount healed by unit hp to cost ratio to get amount this action scores
                ret = (float)amtHealed * u.UnitGoldToHpRatio;
                ret += u.NegativeConditionCount * 3;
            }

            return ret;
        }


Fey druids can grant a friendly unit regeneration over multiple turns:

        private float ScoreRegenForUnit(UnitStatus actor, Point targetLoc, GameState gs)
        {
            float ret = MINIMAL_SCORE;

            // get target unit
            UnitStatus u = gs.GetUnitAtLocation(targetLoc);
            if (u != null)
            {
                // no score if unit already has regeneration
                if (!u.HasCondition(Condition.ConditionType.REGEN))
                {
                    // score points based on how damage to unit, and it's value
                    ret = u.UnitGoldToHpRatio * u.CurrentDamage;
                }
            }

            return ret;
        }


Necromancer units can explode friendly zombies to cause damage to surrounding units, which can in turn then explode themselves if this defeats them, in a massive chain reaction.  As this is a much more complicated manuever, I have a special component to generate a list of resulting effects, which are then used to compute the total value of the action.

        private float ScoreZomboomForUnit(UnitStatus actor, Point targetLoc, GameMap gm, GameState gs)
        {
            float ret = MINIMAL_SCORE;
            UnitStatus boomUnit;

            // get target unit
            UnitStatus u = gs.GetUnitAtLocation(targetLoc);
            if (u != null)
            {
                // negative points for the unit being sacrificed
                ret = u.CurrentHP * u.UnitGoldToHpRatio * (-1);
                // get zomboom results
                List booms = _boomerManager.DoExplosion(targetLoc, gm, gs);
                // tally up score from result
                foreach (ZomboomActionItem zai in booms)
                {
                    if (zai.BoomEffect == ZomboomActionItem.BoomEffects.DAMAGE)
                    {
                        boomUnit = gs.GetUnitAtLocation(zai.Location);
                        if (boomUnit != null)
                        {
                            ret += zai.Value * boomUnit.UnitGoldToHpRatio;
                        }
                    }
                } // next boom
            }

            return ret;
        }


The usefulness of having each game engine component generate a list of effects, instead of updating the game state themselves cannot be understated.  It is extremely handy using the same routines the game engine itself uses.  It also means consistent results.

Most strategy games have random elements to combat results.  To score such, the combat should be run multiple times and the results collated into an average expected outcome.  Another method would be to compute the average outcome by multiplying the effect by the chance of that effect happening.  Such that a unit that had a 60% to hit for 1d8+1 damage would have the average effect of dealing 3.3 damage.

Average value of 1d8: (8 + 1) / 8 = 4.5
Average value of a successful hit:  <avg value of 1d8> + 1 = 5.5
Average value of an attack: <avg value of success> * <chance of success> = 5.5 * .60 = 3.3

The disadvantage of computing the average in this manner is that it can be inaccurate because of the effects of the extremes.  For example, imagine in the example above, that the target had armor that reduced all damage against it by 6.  Taking this into account, the above calculation would generate an average damage value of 0, which is incorrect, as we would actually still score damage if the d8 roll was 6+.

Looking through the code presented here, it is obvious it is still a bit rough.  For instance, there is no consideration given to the position a unit ends up in, just that the move has a net positive effect.  I have noticed this AI send a unit into a very dangerous situation just to finish off a low cost unit.

Another option I have not talked about, but which I have been thinking a lot about, is looking at multiple moves ahead.  Especially with the Combo star system in Shattered Throne, in which each attack makes any followup attack against the same unit more effective.

It would be ideal to have the AI not only compute the best move for each unit, but think one or more moves ahead.  For each potential move, I could then get the best follow up move, and then score both moves together.  This would improve the AI's intelligence quite a bit.

I may add in this capability in the end, but for now I find myself hesitating.  My goal is not to create an unbeatable AI, but rather a fun game.  In writing my first game, Dark Delve, I found that with each version I got lots of comments that the game was too hard.  I found myself consistently dialing back the difficulty to find the proper level of difficulty.

I worry about the same thing here, especially as I have been finding it difficult to explain the Combo Stars game mechanic that is central to the whole game.  It might just be right to let the player who spends the time to figure out that game system to be rewarded with an advantage the AI does not fully take advantage of, rather than being pounded into the dirt right from the start by this rather confusing game element.

In the end I want the AI to put up a good fight, and just not make any obviously stupid or nonsensical moves.

Next time I will introduce the module that may not make the final cut, the Consolidation Module.

And as usual, here is the complete code listing of the TacticalModule.

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

namespace ShatteredThrone.AI.Modules
{
    class TacticalModule : CommandModule
    {
        Pathfinder _pather;
        CombatEngine _combat;
        Zomboom _boomerManager;

        // state information
        bool _noMoreMoves;

        const float MINIMAL_SCORE = 0f;

        public TacticalModule()
        {
            _pather = new Pathfinder();
            _combat = new CombatEngine();
            _boomerManager = new Zomboom();

            _noMoreMoves = true;
        }

        public override bool IsFinished
        {
            get { return _noMoreMoves; }
        }

        public override void Initialize()
        {
            _noMoreMoves = false;
        }

        public override AiAction GetNextMove(GameDetail gd)
        {
            AiAction ret = null;
            List possibleActions = GetUnitActions(gd.CurrentState, gd.Map);

            if (possibleActions.Count > 0)
            {
                float bestScore = MINIMAL_SCORE;
                foreach (AiAction aa in possibleActions)
                {
                    if (aa.ActionScore > bestScore)
                    {
                        bestScore = aa.ActionScore;
                        ret = aa;
                    }
                }
            }
            // if did not generate any moves, set done flag
            if(ret == null)
            {
                _noMoreMoves = true;
            }

            return ret;
        }

        private List GetUnitActions(GameState gs, GameMap gm)
        {
            List ret = new List();

            // get units to move
            List units = GetUnitsLeftToMove(gs.CurrentPlayer, gs);
            // loop through available units to find best move
            foreach (UnitStatus u in units)
            {
                // get best move for this unit
                AiAction act = GetBestMoveForUnit(u, gs, gm);
                // is this move better than our current best move?
                if (act != null)
                    ret.Add(act);
            }

            return ret;
        }

        private AiAction GetBestMoveForUnit(UnitStatus u, GameState gs, GameMap gm)
        {
            float currentBestScore = MINIMAL_SCORE; // 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, gm, gs);
            foreach (Point loc in moveLocs)
            {
                // get all possible actions at this location
                List acts = _combat.GetCombatActionsByUnitAtLocation(u, gm, gs, loc);
                // loop through all possible actions at this location
                foreach (CombatAction ca in acts)
                {
                    // score this action
                    float actionScore = ScoreActionForUnit(loc, u, ca, gs, gm);
                    // is this our best score so far?
                    if (actionScore > currentBestScore)
                    {
                        // set this as our best possible move
                        currentBestScore = actionScore;
                        currentBestMoveLocation = loc;
                        currentBestCombatAction = ca;
                    }
                }
            }

            return new AiAction(AiAction.AiActionType.UNIT_MOVE, u.UnitID, currentBestMoveLocation, currentBestCombatAction, currentBestScore);
        }

        private float ScoreActionForUnit(Point loc, UnitStatus u, CombatAction ca, GameState gs, GameMap gm)
        {
            float ret = MINIMAL_SCORE;
            
            switch (ca.ActionType)
            {
                case CombatActionType.ATTACK:
                    ret = ScoreAttackForUnit(u, loc, ca.Location, gm, gs);
                    break;
                case CombatActionType.HELP:
                    // is this a zomboom?
                    switch (u.FriendSpell)
                    {
                        case FriendlyTargetEffect.ZOMBOOM:
                            ret = ScoreZomboomForUnit(u, ca.Location, gm, gs);
                            break;
                        case FriendlyTargetEffect.REJUVINATE:
                            ret = ScoreRegenForUnit(u, ca.Location, gs);
                            break;
                        case FriendlyTargetEffect.HEAL:
                            ret = ScoreHealForUnit(u, ca.Location, gs);
                            break;
                    } // end help inner switch
                    break;
            } // end switch

            return ret;
        }

        private float ScoreHealForUnit(UnitStatus actor, Point targetLoc, GameState gs)
        {
            float ret = MINIMAL_SCORE;

            // get target unit
            UnitStatus u = gs.GetUnitAtLocation(targetLoc);
            if (u != null)
            {
                // determine how much the unit is healed
                int amtHealed = (u.CurrentDamage < GameEngine.HEAL_AMOUNT_HEALED) ? u.CurrentDamage : GameEngine.HEAL_AMOUNT_HEALED;
                // multiply amount healed by unit hp to cost ratio to get amount this action scores
                ret = (float)amtHealed * u.UnitGoldToHpRatio;
                ret += u.NegativeConditionCount * 3;
            }

            return ret;
        }

        private float ScoreRegenForUnit(UnitStatus actor, Point targetLoc, GameState gs)
        {
            float ret = MINIMAL_SCORE;

            // get target unit
            UnitStatus u = gs.GetUnitAtLocation(targetLoc);
            if (u != null)
            {
                // no score if unit already has regeneration
                if (!u.HasCondition(Condition.ConditionType.REGEN))
                {
                    // score points based on how damage to unit, and it's value
                    ret = u.UnitGoldToHpRatio * u.CurrentDamage;
                }
            }

            return ret;
        }

        private float ScoreZomboomForUnit(UnitStatus actor, Point targetLoc, GameMap gm, GameState gs)
        {
            float ret = MINIMAL_SCORE;
            UnitStatus boomUnit;

            // get target unit
            UnitStatus u = gs.GetUnitAtLocation(targetLoc);
            if (u != null)
            {
                // negative points for the unit being sacrificed
                ret = u.CurrentHP * u.UnitGoldToHpRatio * (-1);
                // get zomboom results
                List booms = _boomerManager.DoExplosion(targetLoc, gm, gs);
                // tally up score from result
                foreach (ZomboomActionItem zai in booms)
                {
                    if (zai.BoomEffect == ZomboomActionItem.BoomEffects.DAMAGE)
                    {
                        boomUnit = gs.GetUnitAtLocation(zai.Location);
                        if (boomUnit != null)
                        {
                            ret += zai.Value * boomUnit.UnitGoldToHpRatio;
                        }
                    }
                } // next boom
            }

            return ret;
        }

        // TODO: Give bonus points for mana gained via kill
        private float ScoreAttackForUnit(UnitStatus attacker, Point attackLocation, Point targetLocation, GameMap m, GameState gs)
        {
            float ret = MINIMAL_SCORE;
            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 -= attacker.Cost;
                    }
                    else
                    {
                        ret -= (float)ar.Damage * attacker.UnitGoldToHpRatio;
                    }
                }
                else
                {
                    // will this kill the target?
                    target = gs.GetUnitAtLocation(ar.TargetLocation);
                    if (target != null)
                    {
                        if (!target.CanSurviveDamage(ar.Damage))
                        {
                            // reward killing blow
                            ret += target.Cost;
                            // if attacking unit has raise dead, score extra points
                            if (attacker.HasTrait(UnitTrait.RAISE_DEAD))
                            {
                                ret += 10;
                            }
                            // score points if attacking unit has rampage and will refresh
                            if (attacker.HasTrait(UnitTrait.RAGE))
                            {
                                ret += attacker.Cost / 3;
                            }
                        }
                        else
                        {
                            // award score based on damage caused to target
                            ret += (float)ar.Damage * target.UnitGoldToHpRatio;
                            // does this attack add any conditions?
                            if (ar.AddedCondition != null && ar.AddedCondition.IsNegative)
                            {
                                ret += 3;
                            }
                        }
                    }
                }
            }

            return ret;
        }

    }
}

3 comments:

Josh Jung said...

How about making different difficulties, where the normal AI will only look at the current turn, and as the player sets higher difficulty, or if there is any progress system within say a campaign mode, they can start looking at future turns, and taking the combo system into account. This will ensure that players will be able to win without much struggle for first few games, and as they get more comfortable with the game mechanics and combo system and whatnot, the AI keeps the game challenging by making less errors and playing smarter.

Harvicus said...

That is a great idea Josh. I will certainly keep it in mind. Because I am learning as I go, I am not sure if I will end up with more than one reasonable AI to do this with. Right now, I will be happy with an AI that just avoids making obviously stupid moves.

What I currently have puts up a good fight, and can punish a player that makes a bad move, but it is also still prone to making the occasional odd move itself that does not make any sense.

Because it has proven to be so efficient (usually) I do not think I will need to add in any multi-move look ahead. Which truthfully is a bit daunting to think of. I am still surprised that the current AI makes its moves without any slowdown based on how many moves it is calculating, and I worry a bit about increasing the complexity to a whole new order of magnitude.

It may just be that I am underestimating the power of computers these days though. I may play around with the idea at some point, just as a challenge to myself if nothing else.

Thanks for dropping by and commenting.

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!