Sunday, May 20, 2012

Turn Based Strategy Game AI part 7

Continued from part 6

For this installment, I watched the AI play several games and made note of a few behaviors it was performing that were less than ideal.  Some of these were solved by tweaking the behavior weights while others required some code changes.

On the test map I have been using for these tests, there is an isolated castle across a river that the AI has been ignoring.  By increasing the weight value used in scoring capture moves the AI responded to more isolated settlements such as the one located on this map.

The AI was also assigning units on attack goals which were ill suited to do so.  To correct this, I added a minimal suitability threshold when calculating if a goal had enough resources.  If it does not, the goal is not assigned.

        public bool HasSufficientResources
        {
            get
            {
                int numSuitableResources = 0;
                foreach (GoalResource gr in PotentialResources)
                {
                    // only count those that meet the minimum threshold
                    if (gr.Suitability > SUITABILITY_THRESHOLD) numSuitableResources++;
                }

                return (numSuitableResources >= NeededResources);
            }
        }

Another bad behavior I witnessed was the AI would abandon its settlements to let them be easily taken over by the enemy on the next turn.  Also somewhat related was that healer units were moving close to the enemy to heal their targets, as they had an attack goal rewarding them for being close to their target.

To address both of these issues, I added in two new AI Goals:
  • Support - Applicable to all friendly units, to support a unit means using friendly abilities (such as heal) or simply being close to them to prevent the enemy from attacking the unit from as many directions.
  • Protect - Applicable to all owned settlements, protecting a settlement is being close to the settlement, preferrably right atop it, to prevent the enemy from capturing the settlement.

The related code was so similar to the code for existing goals, that I am going to skip showing the code here in the interest of saving space.  This code will be presented fully when I do a complete overview of the code in a couple weeks.

Because the AI rewarded units with attack goals for being as close to their target as possible, Ranged units were attacking from a much closer range than necessary, leaving them open to counterattacks. To correct this, I updated the location scoring algorithm to take into account the attacker's range, and giving it high scores for maximizing its range.

        private float GetDistanceToGoalImproval(UnitStatus u, Point newLoc, int idealRange)
        {
            float oldDistance = Globals.GetDistance(u.X, u.Y, u.AiGoalTarget.X, u.AiGoalTarget.Y);
            float newDistance = Globals.GetDistance(newLoc, u.AiGoalTarget);

            // return factor representing improvement in position, protect vs divide by 0
            return (newDistance <= idealRange) ?
                1f + newDistance / 10f :            // give bonus for maximizing within range
                (oldDistance > 0) ? (1f - newDistance / oldDistance) : (1f - newDistance);
        }

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

            // score location based on goal
            switch (u.AiGoal)
            {
                case Goal.GoalType.ATTACK:
                    ret = GetDistanceToGoalImproval(u, loc, u.Range) * CurrentDisposition.AttackGoal.TargetDistanceFactor;
                    break;
                case Goal.GoalType.CAPTURE:
                    ret = GetDistanceToGoalImproval(u, loc, 0) * CurrentDisposition.CaptureGoal.TargetDistanceFactor;
                    break;
                case Goal.GoalType.SUPPORT:
                    ret = GetDistanceToGoalImproval(u, loc, u.FriendRange) * CurrentDisposition.SupportGoal.TargetDistanceFactor;
                    break;
                case Goal.GoalType.PROTECT:
                    ret = GetDistanceToGoalImproval(u, loc, 0) * CurrentDisposition.ProtectGoal.TargetDistanceFactor;
                    break;
                case Goal.GoalType.FORTIFY:
                default:
                    // get location score based on based on influence, (tend towards 0)
                    ret = CurrentDisposition.FortifyGoal.TargetDistanceFactor - _influenceMap.GetTotalInfluencePercentAt(loc.X, loc.Y) * CurrentDisposition.FortifyGoal.TargetDistanceFactor;
                    break;
            }

The largest change made to the AI however was to give it the ability to behave differrently based on the current game situation.  There are 4 different game states recognized by the AI:
  • Balanced - The default behavior the AI has been using up to this point.  This behavior strikes a balance between attack and defense.
  • Expansion - Representing the early game situation where neither player has many units and are attempting to expand their influence and capture resource points (settlements)
  • Winning - When the AI detects it is winning, it will play more aggressively, pushing the attack, even if it means taking more losses than normal
  • Losing - When The AI detects it is losing the game, it will play more defensively, pulling back to reinforce its positions, purchasing units more suited and cost effective for defending, and not making any risky attacks.

This is implemented rather easily.  Each of the 4 states has a separate set of goal and move weights it uses  when planing its moves.  As these weights are already packaged up into the DispositionProfile class, we now have 4 DispositionProfiles, one for each game state.  The AI detects which state the game is in at the start of each turn, and then uses the corresponding DispositionProfile.

The Game State is detected by summing the value of all units and resources for both players and comparing their totals.  If both players score below a certain threshold, the game state is set to "Expansion".  Otherwise the ratio of each player's score is computed, and this value used to determine who, if anyone, is currently winning, and then setting the game state appropriately.

This logic relys upon 3 new constant values that set the various thresholds.  It took several attempts to arrive at values that worked correctly.  I feel pretty good about the selected values for determining Winning vs Losing, but the value of the expansion threshold has me a bit concerned.  This value I can see being different based on the map being played, and I am expecting to have to update this to be a computed value based on the game map in the future.

This logic all fit nicely into a new class called a DispositionProfileSet which is shown below:

    public class DispositionProfileSet
    {

        public List Profiles;

        private const int PROFILE_BALANCED = 0;
        private const int PROFILE_WINNING = 1;
        private const int PROFILE_LOSING = 2;
        private const int PROFILE_EXPANSION = 3;

        private const float EXPANSION_THRESHOLD = 160f;
        private const float LOSING_THRESHOLD = 1.25f;
        private const float WINNING_THRESHOLD = 0.8f;

        private int _currentProfile;

        public DispositionProfileSet()
        {
            Profiles = new List();
            _currentProfile = PROFILE_BALANCED;
        }

        public DispositionProfile ActiveProfile
        {
            get
            {
                return Profiles[_currentProfile];
            }
        }

        public void ComputeActiveProfile(GameState gs)
        {
            float friendlyUnitsScore = 0f;
            float enemyUnitsScore = 0f;

            // loop through all units
            foreach (UnitStatus u in gs.Units)
            {
                // ensure unit is living
                if (u.IsAlive)
                {
                    // add unit score to running total based on which side it is on
                    if (gs.AreFriendly(u.Owner, gs.CurrentPlayer))
                    {
                        // friendly
                        friendlyUnitsScore += u.Cost; 
                    }
                    else
                    {
                        // enemy
                        enemyUnitsScore += u.Cost; 
                    }
                }
            }

            // loop through settlements and add gold income from each
            foreach (Settlement s in gs.Settlements)
            {
                // is settlement owned?
                if (s.Owner != Globals.PLAYER_NONE)
                {
                    if (gs.AreFriendly(s.Owner, gs.CurrentPlayer))
                    {
                        // friendly
                        friendlyUnitsScore += s.GoldIncome;
                    }
                    else
                    {
                        // enemy
                        enemyUnitsScore += s.GoldIncome;
                    }
                }
            }

            // now compare our scores to see which profile to set as active
            
            // if both unit scores are less than base threshold, consider this to be expansion phase
            if (friendlyUnitsScore < EXPANSION_THRESHOLD && enemyUnitsScore < EXPANSION_THRESHOLD)
            {
                _currentProfile = PROFILE_EXPANSION;
            }
            else
            {
                // compare scores
                float scoreRatio = enemyUnitsScore / friendlyUnitsScore;
                // assume balanced
                _currentProfile = PROFILE_BALANCED;
                if (scoreRatio < WINNING_THRESHOLD) _currentProfile = PROFILE_WINNING;
                if (scoreRatio > LOSING_THRESHOLD) _currentProfile = PROFILE_LOSING;
            }
        }

And as usual, here is this week's modified AI (codenamed "George") against Frank from last week.  It should be noted that Frank gained the benefit of several of this week's changes such as the updated weight values and the Suitability minimum thresholds due to the fact that these changes were made to the AI framework itself.

Next time I am planning on running the collected weights through a genetic algorithm to arrive at hopefully better values.  Until then, happy coding!


Continued in part 8

Monday, May 7, 2012

Turn Based Strategy Game AI part 6

Continued from part 5
This weeks changes were pretty minimal, but ended up having a large impact.  First up was some cleanup.  I created a new map that was symetrical to give a more balanced way of measuring AI skill differences.  I then also moved all constant weights used to determine AI behavior scoring into the DispositionProfile class, and made the DispositionProfile accessed through a property.

This change, enables different behaviors to be swapped in with minimal work.  While this week's AI "Frank" does not make use of this feature, it is in the works for the next week.  After doing this, I tweaked a few of the values to give less value to the Banding ability of the Spearmen units which has been causing them to stack up together instead of moving across the map.

The final change of note was to enable the AI to make use of Leader skills.  In Shattered Throne, when a unit is defeated, the number of stars (combo points) on the unit is added to the killing player as mana points that can be used to fuel special abilities unique to the player's chosen leader.  In this game, the blue player is using the High Priestess.  Each leader has both a minor, and major ability.  The High Priestess's minor ability is called "Mercy" and converts all active stars on enemy units into gold.  Her major ability is currently called "Blessing" and heals all friendly units by 2 points.

The abilities are so specific to each leader that I could not think of a generic way to handle the logic for using the abilities.  As such, I would have to code special logic for every leader skill in the game.  I did take note of a few things that would help out.  All the Major skills I have currently planned, are of use only at the beginning or end of a turn.  As such, I make a check at those two points on whether the Leader's Major skill should be used or not.

As there is a maximum amount of mana/stars that can be stored at once, which is not much higher than the cost of major skills.  If we can afford to cast a major skill, it is in the AI's best interest to use it as soon as possible, assuming it is not completely wasted.

I created a new class to encapsulate all the specific leader skill use checks called LeaderPowerCalculator.  When checking whether the Priestess should use her "Blessing" skill, I count the number of HP that could be healed by using the skill, and based on how many points would be healed, a chance to cast is generated, which quickly climbs to 100%.

        private int GetChanceToUseHealPower(GameState gs)
        {
            int dmgAmt = 0;

            // get amount of damage on our units
            foreach (UnitStatus u in gs.Units)
            {
                if (u.IsAlive && gs.AreFriendly(u.Owner, gs.CurrentPlayer))
                    dmgAmt += (u.CurrentDamage > 2) ? 2 : u.CurrentDamage; // do not count more than 2 points per unit
            }

            return (dmgAmt * 15) - 30;
        }

        public bool UsePowerAtTurnEnd(Faction.LeaderSpecialEffect power, GameState gs)
        {
            int useChance = 0;

            // determine chance to use power 
            switch (power)
            {
                case Faction.LeaderSpecialEffect.BLESSING:
                    useChance = GetChanceToUseHealPower(gs);
                    break;
            }

            return (useChance > _roller.Next(100));
        }

        public bool UsePowerAtTurnStart(Faction.LeaderSpecialEffect power, GameState gs)
        {
            int useChance = 0;

            // determine chance to use power 
            switch (power)
            {
                case Faction.LeaderSpecialEffect.BLESSING:
                    useChance = GetChanceToUseHealPower(gs);
                    break;
            }

            return (useChance > _roller.Next(100));
        }

The minor skills are a lot more tricky, and unlike the major skills, are best use throughout the turn, intermixed with the player's normal actions.  Because of this, I make a call to see if the AI should use their minor power after the AI has chosen a move, but before it is executed.  If the calculation specifies that the minor ability of the leader should be used, the chosen move is discarded in favor of using the minor ability.

For "Mercy", the key in determining if it should be used is whenever the next move would not continue any combo chains.  Making a move that does not include attacking a unit with combo points (stars) causes those combo points to disappear.  This is the perfect time to use Mercy, to cash in the otherwise wasted combo points into Gold.   The decision to use the ability is based on how many combo points would be converted into Gold.  We also tend towards not using this ability, as saving up mana to use for Blessing is also a good move.

        private int GetChanceToUseMercyPower(UnitMove um, GameState gs)
        {
            int numCombos = 0;

            // no chance if this does not extend combo
            if (!um.ExtendsCombo)
            {
                // get number of combo points that would be converted
                foreach (UnitStatus u in gs.Units)
                {
                    if (u.IsAlive)
                        numCombos += u.ComboPoints;
                }
            }
            
            // return chance based on num combos that would be converted
            return (numCombos * 25) - 40;
        }

        public bool UsePowerBeforeMove(Faction.LeaderSpecialEffect power, UnitMove proposedMove, GameState gs)
        {
            int useChance = 0;

            // determine chance to use power 
            switch (power)
            {
                case Faction.LeaderSpecialEffect.MERCY:
                    useChance = GetChanceToUseMercyPower(proposedMove, gs);
                    break;
            }

            return (useChance > _roller.Next(100));
        }

This updates the main Think() logic of our new AI player to the following:

        public override void Think(GameDetail gd, PlayerController pc)
        {
            // build influence map
            _influenceMap.CreateMap(gd.Map, gd.CurrentState);

            // is this the start of the turn?
            if (_lastTurn != gd.CurrentState.CurrentTurn)
            {
                StartOfTurn(gd);
                // check for use of Major leader power at turn start
                if (gd.CanAffordMajorSpell())
                {
                    if (_leaderPowerCalc.UsePowerAtTurnStart(gd.CurrentPlayer.LeaderMajorId, gd.CurrentState))
                    {
                        SubmitLeaderMajor(pc);
                        return;
                    }
                }
            }

            // get units to move
            List units = GetUnitsLeftToMove(pc.PlayerIndex, gd.CurrentState);

            // loop through available units to find best move
            UnitMove bestMove = null;
            foreach (UnitStatus u in units)
            {
                // get best move for this unit
                UnitMove thisMove = GetBestMoveForUnit(u, gd);
                // is this move better than our current best move?
                if (thisMove.IsBetter(bestMove))
                {
                    // set this as the new best move
                    bestMove = thisMove;
                }
            }

            // did we generate a move action?
            if (bestMove != null)
            {
                if (gd.CanAffordMinorSpell())
                {
                    // check for pre move minor power use
                    if (_leaderPowerCalc.UsePowerBeforeMove(gd.CurrentPlayer.LeaderMinorId, bestMove, gd.CurrentState))
                    {
                        SubmitLeaderMinor(pc);
                        return;
                    }
                }
                SubmitUnitMove(bestMove, gd, pc);
            }
            else
            {
                // check for end of turn power use
                if (gd.CanAffordMajorSpell())
                {
                    if (_leaderPowerCalc.UsePowerAtTurnEnd(gd.CurrentPlayer.LeaderMajorId, gd.CurrentState))
                    {
                        SubmitLeaderMajor(pc);
                        return;
                    }
                }

                // submit builds
                if (!SubmitBuildActions(gd, pc)) // returns false if did not build anything
                {
                    // nothing left to do except end our turn
                    SubmitEndTurn(pc);
                }
            }
        }

The results are telling, as Frank makes short work of Eva from last week, despite only changing the weight constant for Banding and allowing the use of Leader special abilities.


Continued in Part 7