Turn Based Strategy Game AI part 5

Continued from part 4
This week I added two critical pieces that have been hanging over my head since week 1.  The reason being that I feared the logic would be both complex, and slow.  It turned out to be neither, and the result shows a much improved AI opponent.  Except for some remaining odd behaviors to work out by adjusting my weighting algorithms, I think that this iteration of the AI represents the first viable AI opponent.

Prior to this week, the AI players chose which unit to build and which order to move units purely at random.  This created a unit imblance because on unit (the light horse "Squire" unit) has the special Skirmishing ability.  This ability prevents all damage to the unit unless it has one or more combo points on it (stars).  While normally a weak unit, the random move ordering created a nigh-invulnerable unit as combo points fade unless a unit is attacked with successive attacks.

 The logic was relatively simple:

• Loop through every unit that can move
• Loop through every possible move/action combination for the unit
• Score this move/action
• Choose the highest scoring move/action
• If this move/action targets a unit with combo points, or the current best move does not
• If this is better than our currently saved best move
• Save this as the best possible move
• Perform the identified best move

The amount of computations required worried me that it could seriously slow down the game, but there was no such problem.  This also gives preference to grouping attacks against the same enemy (detected based on combo points) to take full advantage of the game's combo point mechanic.

One issue this does not take into account, is new combo opportunities that open up when a unit vacates a space that another unit could use.  The actual game code appears as:

        private UnitMove GetBestMoveForUnit(UnitStatus u, GameDetail gd)
        {
            AttackScore currentBestScore = new AttackScore();
            currentBestScore.Score = -10000f; // 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
                float 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
                    AttackScore actionScore = ScoreActionForUnit(loc, u, ca, gd);
                    // is this our best score so far?
                    if ((locScore + actionScore.Score) > currentBestScore.Score)
                    {
                        // set this as our best possible move
                        currentBestScore.Score = locScore + actionScore.Score;
                        currentBestScore.Combos = actionScore.Combos;
                        currentBestMoveLocation = loc;
                        currentBestCombatAction = ca;
                    }
                }
            }

            return new UnitMove(u, currentBestMoveLocation, currentBestCombatAction, currentBestScore.Score, currentBestScore.Combos);
        }

The second new piece of logic add intelligence to the building of new units.  Much like the unit move sequencing addressed above, my previous AI players chose both random build locations and random unit types to build.  The new logic prioritizes where to build, favoring locations closest to the action.  It also attempts to keep a balance of unit types, with ratios based on unit Roles.  I didn't want to hardcode specific unit types, as the Empire faction shown up to this point, is but one available faction in the game. 

When building the various factions however, I used the concept of unit Roles.  In total their are 7 roles which describe the optimal use of a particular unit.  Each faction has access to 6 of the 7 roles.  These roles break down as:

Line: Mostly defensive oriented troops which have the best cost to survivability ratio
Assault: Strong attacking units that form the backbone of an attacking force
Support: Units that are not strong on attack or defense, but grant a bonus or healing to other units, and serve as a force multiplier
Ranged: The more offensive version of Support units, while capable of ranged attacks, the attack itself is relatively weak on its own, and best used to debuff the enemy and setup attacks by other units
Flanker: Fast units that have a degree of self sufficiency.  These units are used to threaten and exploit openings in the opponent's defenses
Shock: The elite units of the army, good at pretty much everything, but coming at a high price
Artillery: Long ranged units capable of high damage, but not typically very mobile

As each faction is missing one of the Role types (the Empire faction shown lacks an Artillery selection), this plays a role in giving each faction a different feel.

My solution for choosing the best possible unit type to build is based on assigning optimal ratios for each unit type and every time the AI must build:

• Compute current ratios of each unit type role we own in the game
• Order each unit role based on which type is furthest from its optimal ratio
• Choose the top unit role type on this ordered preference list that we can afford

The actual code:

        private bool SubmitBuildActions(GameDetail gd, PlayerController pc)
        {
            bool ret = false;
            List buildGoals = new List();

            // create build goal for our castles
            foreach (Settlement s in gd.CurrentState.Settlements)
            {
                // check that settlement is owned by us and can build
                if (s.CanBuildUnits && s.Owner == gd.CurrentPlayer.PlayerNum)
                {
                    // cannot build here if there is already a unit here
                    UnitStatus u = gd.CurrentState.GetUnitAtLocation(s.X, s.Y);
                    if (u == null)
                    {
                        // create build goal for this settlement
                        Goal g = new Goal();
                        g.CreateGoal(Goal.GoalType.BUILD, s.X, s.Y, gd.CurrentState, _disposition, _influenceMap);
                        buildGoals.Add(g);
                    }
                }
            } // next settlement

            // get list of all unit types for this player
            List unitSelection = gd.GetPlayerUnitsDetail(pc.PlayerIndex);

            // get top priority goal
            Goal tg = (from bg in buildGoals
                                  orderby bg.Priority descending
                                  select bg).FirstOrDefault();

            if (tg != null)
            {
                // order unit types for this goal by suitability
                tg.AssignBuildSuitabilities(unitSelection, gd.CurrentState, _disposition);
                // get id of unit to build
                int buildType = tg.GetBuildTargetUnitType(gd.CurrentState.GetPlayerResources(pc.PlayerIndex).Gold);
                // double check we got back something valid
                if (buildType >= 0 && buildType < unitSelection.Count)
                {
                    // send build command
                    SubmitBuild(buildType, tg.GoalTarget.X, tg.GoalTarget.Y, pc);
                    // set return that we built something
                    ret = true;
                }
            }

            return ret;
        }

This function makes use of some changes to the Goal class I introduced last week to support this new BUILD goal:

        private void SetBuildPriority(GameState gs, DispositionProfile dp, InfluenceMap im)
        {
            Priority = im.GetTensionPercentAt(GoalTarget.X, GoalTarget.Y) * dp.BuildGoal.TensionFactor;
            Priority += im.GetVulnerabilityPercentByPlayerAt(gs.CurrentPlayer, GoalTarget.X, GoalTarget.Y) * dp.BuildGoal.VulnerabiltiyFactor;
        }

        public void AssignBuildSuitabilities(List unitList, GameState gs, DispositionProfile dp)
        {
            float totalUnits = 0f;
            float[] existingUnits = new float[6];

            for(int i=0;i < 6;i++){
                existingUnits[i] = 0f;
            }
            // count up all units we own by type
            foreach (UnitStatus u in gs.Units)
            {
                // if we own this unit and it is alive, count it
                if (u.IsAlive && gs.AreFriendly(u.Owner, gs.CurrentPlayer))
                {
                    existingUnits[u.UnitType]++;
                    totalUnits++;
                }
            }

            // compute suitability of each unit type and add as a potential resource
            for (int n = 0; n < 6; n++)
            {
                GoalResource gr = new GoalResource();
                gr.SourceId = n;
                gr.SourceCost = unitList[n].Cost;
                // suitability is based on difference between desired ratio and actual ratio
                gr.Suitability = dp.BuildGoal.PreferredUnitRatio[(int)unitList[n].Role] - ((totalUnits > 0f) ? existingUnits[n] / totalUnits : 0f);
                PotentialResources.Add(gr);
            }
        }

        public int GetBuildTargetUnitType(int maxBudget)
        {
            // order our potential resources by suitability
            GoalResource gr = (from pr in PotentialResources
                                          where pr.SourceCost <= maxBudget
                                          orderby pr.Suitability descending
                                          select pr).FirstOrDefault();

            return (gr != null) ? gr.SourceId : -1;
        }

The result of these changes turned out to be significant.  While I originally intended to build out a new map because of the Advantage the RED player has in the map I have been using.  This new AI player was able to win on this map as the BLUE player which I thought showcased a higher degree of improvement.  The new map will have to wait until next time.

The following video shows this new AI player in BLUE facing off against last week's in RED.

Continued in part 6...