Thursday, April 26, 2012

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...

Monday, April 16, 2012

Turn Based Strategy Game AI part 4

Continued from part 3



This installment has been difficult to put together.  The idea was to add in a Goal based planning element to the AI, and the resulting work quickly became a much larger undertaking than I desired.  My own objective is to only add small incremental changes each week, but this one really got away from me.  Often because I thought I knew what I was doing, when I really did not.

I ended up gutting a lot of the extra details I had been adding to get this back to a reasonable size.  I am glad I did, because the end result ended being less than steller.  Yet, it has a promising framework to work from in the weeks to come.

The basic idea was simple.  The AI would consist of two components, a tactical component will make the individual move decisions, while a new strategic component would parsel out individual goals to our units.  The tactical component will use each units goal in determining the best move.

The tactical component consists of the code I have written up to this point in the series, the only change here will be to give extra weight to the units assigned goal.

I ended up with 3 types of goals at this point.  A KILL goal of which all enemy units represent a single such goal.  A CAPTURE goal, which consists of all Settlements in the game that we do not own, and finally a FORTIFY goal, otherwise known as the default NULL goal where the unit works to maximize its best possible move without a specific target unit or settlement.

The strategic layer executes once at the start of the AI's turn and goes through the following logic:

  • Add each enemy unit as a KILL goal
  • Add each unowned settlement as a CAPTURE goal
  • Prioritize each goal
  • Loop through the goals in order of priority
    • Judge the Suitability of all our units not already assigned a goal for this goal
    • If the goal has enough units (3 for KILL, 1 for CAPTURE)
      • Assign the most suitable units to this goal (top 3 for KILL, just the top for CAPTURE goals)

Then the tactical portion of the AI will weight its potential moves towards its assigned goal target.

That is the simple idea, however a rather large amount of code resulted.  This was not helped by the fact that I also added a new component called a DispositionProfile.  This class holds all numeric constants used during the AI calculations (or at least just the new ones introduced this week so far).  The idea is that different weighting sets can be used based on different situations.  Also, I may try evolving the AI values through a genetic algorithm at some point, and these DispositionProfile objects can be used as the AI's "DNA" in the process.

One of the trickier aspects of the process is judging a Goal's Priority and a unit's Suitability for a goal.  At this point, I based this part of the algorithm on the Influence Map I added last week.  By adding both player's influence together, I generated a Tension map.  The areas of highest Tension values were located along the front where both players have units.  I would give higher priority to targets in these highly contested areas. 

The other major component of determining a goal's priority would be its Vulnerability, which was simply our own influence by itself.  The thinking being that we would give extra priority to the most vulnerable targets.

The idea was based on the following article on influence maps.  And the logic is that we want to target the most vulnerable enemies along the mutual front.  A unit's suitability to a goal is based mostly on its distance to the goal along with the unit's Attack value and current HP.

The results of this addition are a bit of a mixed bag.  The resulting video makes me realize that I still have 2 fundamental issues.  One is that the tactical engine does not maximize the order of its moves.  This has caused one unit type to become nearly unstoppable.  This unit is not particularly strong, but it has a strong defense which nullifies all damage against it when it has no combo points.  And combo points are generated by attacking the same unit with successive moves.

The other issue is that the map is not terribly balanced.  These two elements make it difficult to get an accurate feel for which AI is strongest.  I plan to make addressing these two items my focus for the next installment.

One positive takeaway is that this AI is not leaving units hanging around its staging area as badly as the prior.  Here is the video showing this weeks AI (called "Dave") in Blue against last weeks "Carl".  I have the game engine drawing a line between Dave's units and their assigned goal, along with overlaying the Influence map visually.

Video Here

Here is the new Goal class that keeps track of goals and assigns Priority and Suitability values. (The GoalResource and DispositionProfile classes referenced are simple data classes without any special logic)
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;

namespace ShatteredThrone.AI
{
    public class Goal
    {
        public enum GoalType
        {
            FORTIFY = 0,
            ATTACK = 1,
            CAPTURE = 2
        }

        public GoalType GoalId;
        public Point GoalTarget;
        public float Priority;
        public bool IsActive;
        List PotentialResources;
        public int NeededResources;

        public Goal()
        {
            PotentialResources = new List();
            IsActive = false;
            GoalTarget = new Point(0, 0);
        }

        public void CreateGoal(GoalType gt, int tx, int ty, GameState gs, DispositionProfile aiDisposition, InfluenceMap im)
        {
            // set basic goal properties
            GoalId = gt;
            GoalTarget.X = tx;
            GoalTarget.Y = ty;
            IsActive = false;
            PotentialResources.Clear();
            
            // Determine Goal Priority based on goal type
            switch (GoalId)
            {
                case GoalType.ATTACK:
                    SetAttackPriority(gs, aiDisposition, im);
                    NeededResources = 3;
                    break;
                case GoalType.CAPTURE:
                    SetCapturePriority(gs, aiDisposition, im);
                    NeededResources = 1;
                    break;
                case GoalType.FORTIFY:
                    Priority = 0f;
                    break;
            }
        }

        public bool HasSufficientResources
        {
            get
            {
                return (PotentialResources.Count >= NeededResources);
            }
        }

        public void AssignGoalResources(GameState gs)
        {
            // order our potential resources by suitability
            var resourcesBySuitability = from pr in PotentialResources
                                         orderby pr.Suitability descending
                                         select pr;

            // assign a number of resources equal to what we need
            int assignCount = 0;
            foreach(GoalResource gr in resourcesBySuitability)
            {
                // get unit representing this resource
                UnitStatus u = gs.GetUnitAtLocation(gr.SourceLocation);
                // double check that we got a valid unit
                if (u != null)
                {
                    // set goal for unit and bump count
                    u.SetAiGoal(GoalId, GoalTarget);
                    assignCount++;
                    // if we have assigned enough units, break out of loop
                    if (assignCount >= NeededResources) break;
                }
            }
        }

        public void AssignUnitResourceSuitability(UnitStatus u, GameState gs, DispositionProfile dp)
        {
            switch (GoalId)
            {
                case GoalType.ATTACK:
                    GetBaseUnitSuitabilityForAttackGoal(u, gs, dp);
                    break;
                case GoalType.CAPTURE:
                    GetBaseUnitSuitabilityForCaptureGoal(u, gs, dp);
                    break;
            }
        }

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

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

        private void AddPotentialUnitResource(UnitStatus u, float suitability)
        {
            GoalResource gr = new GoalResource();
            gr.SourceLocation.X = u.X;
            gr.SourceLocation.Y = u.Y;
            gr.Suitability = suitability;

            PotentialResources.Add(gr);
        }

        private float GetBaseDistanceFactor(int sx, int sy, int tx, int ty, float range)
        {
            float ret = (range > 0) ? (float)Globals.GetDistance(sx, sy, tx, ty) / range : 5f;
            return 4f - ret;
        }

        private void GetBaseUnitSuitabilityForAttackGoal(UnitStatus u, GameState gs, DispositionProfile dp)
        {
            float suitability;

            // get base distance rating
            suitability = GetBaseDistanceFactor(u.X, u.Y, GoalTarget.X, GoalTarget.Y, u.Move + u.Range) * dp.AttackGoal.SourceDistanceFactor;
            // add current hp rating
            suitability += (float)u.CurrentHP * dp.AttackGoal.SourceHpFactor;
            // add attack rating
            suitability += (float)u.Attack * dp.AttackGoal.SourceAttackFactor;

            AddPotentialUnitResource(u, suitability);
        }

        private void GetBaseUnitSuitabilityForCaptureGoal(UnitStatus u, GameState gs, DispositionProfile dp)
        {
            float suitability;

            // get base distance rating
            suitability = GetBaseDistanceFactor(u.X, u.Y, GoalTarget.X, GoalTarget.Y, u.Move) * dp.CaptureGoal.SourceDistanceFactor;

            AddPotentialUnitResource(u, suitability);
        }

    }
}

The goal assignment code run at the start of each AI turn is contained in the following new function:

private void StartOfTurn(GameDetail gd)
        {
            // reset all goals
            _CurrentGoals.Clear();

            // reset our own unit goals from last turn, and create attack goal for enemy units
            foreach (UnitStatus u in gd.CurrentState.Units)
            {
                if (gd.CurrentState.AreFriendly(u.Owner, gd.CurrentState.CurrentPlayer))
                {
                    // friendly unit, reset goal
                    u.ResetAiGoal();
                }
                else
                {
                    // enemy unit, add as goal assuming is alive
                    if (u.IsAlive)
                    {
                        Goal g = new Goal();
                        g.CreateGoal(Goal.GoalType.ATTACK, u.X, u.Y, gd.CurrentState, _disposition, _influenceMap);
                        _CurrentGoals.Add(g);
                    }
                }
            }

            // create capture goal for all unowned settlements
            foreach (Settlement s in gd.CurrentState.Settlements)
            {
                if (s.Owner != gd.CurrentState.CurrentPlayer)
                {
                    Goal g = new Goal();
                    g.CreateGoal(Goal.GoalType.CAPTURE, s.X, s.Y, gd.CurrentState, _disposition, _influenceMap);
                    _CurrentGoals.Add(g);
                }
            }

            // Sort goals in descending order by priority
            var goalsByPriority =   from ug in _CurrentGoals
                                    orderby ug.Priority descending
                                    select ug;
            // add all our units as potential resources for every goal
            foreach (Goal g in goalsByPriority)
            {
                foreach (UnitStatus u in gd.CurrentState.Units)
                {
                    // if unit is living, friendly, and not yet assigned a goal, add it as a potential resource
                    if (u.IsAlive && !u.HasAiGoal && gd.CurrentState.AreFriendly(u.Owner, gd.CurrentState.CurrentPlayer))
                    {
                        g.AssignUnitResourceSuitability(u, gd.CurrentState, _disposition);
                    }
                }
                // Does goal have enough potential resources
                if (g.HasSufficientResources)
                {
                    // Assign resources to goal
                    g.AssignGoalResources(gd.CurrentState);
                }
            }

            // set this as current turn so we only run this routine once per game turn
            _lastTurn = gd.CurrentState.CurrentTurn;
        }

        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);
            }


Moves scoring now has additional scoring logic based on a units goal. The scoring for the default FORTIFY goal is the same logic used last time.

        private float GetDistanceToGoalImproval(UnitStatus u, Point newLoc)
        {
            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 (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) * _disposition.AttackGoal.TargetDistanceFactor;
                    break;
                case Goal.GoalType.CAPTURE:
                    ret = GetDistanceToGoalImproval(u, loc) * _disposition.CaptureGoal.TargetDistanceFactor;
                    break;
                case Goal.GoalType.FORTIFY:
                default:
                    // get location score based on based on influence, (tend towards 0)
                    ret = 8f - _influenceMap.GetTotalInfluencePercentAt(loc.X, loc.Y) * 8f;
                    break;
            }

And finally, when scoring attack actions, a bonus is applied to the score if the attack action contains the units assigned Attack target (if any).

// if we had an attack goal, boost value of attack if is against our assigned target
            if (attacker.AiGoal == Goal.GoalType.ATTACK && attacker.AiGoalTarget == targetLocation)
            {
                ret += _disposition.AttackGoal.AttackedTargetBonus;
            }

Monday, April 2, 2012

Turn Based Strategy Game AI part 3








Continued from part 2

This week I would like to introduce you to Carl.  This AI player shares almost the same code as Brutus from last week, but with one very important difference.  Carl generates an Influence Map to determine the relative strengths of each player at each space on the map. 

The influence map is generated by seeding a representation of the game map with each unit's strength, and then using an algorithm known as Chamfering or Grassfire to propagate these influence values across the map.  The advantage of this algorithm is that it is relatively quick, requiring only 2 passes over the map (3 if one includes the initial seeding of values).

I am currently computing the influence value of a unit equal to its Attack value multiplied by the sum of its movement rate and attack range.  This value then falls off at a rate of 1 per space distant from the source.  I then record the highest influence at each space.

I am also keeping track of each player's influence separately as I hope to generate additional types of influence maps in the weeks to come.  Here is the code I am currently using to generate the influence map.

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

namespace ShatteredThrone
{
    class InfluenceMap
    {
        class InfluenceKey
        {
            // player
            float[] _influences;

            public InfluenceKey() : this(0f, 0f) { }

            public InfluenceKey(float p1, float p2)
            {
                _influences = new float[2];
                _influences[0] = p1;
                _influences[1] = p2;
            }

            public float GetInfluenceByPlayer(int who)
            {
                return _influences[who];
            }

            public float GetTotalInfluence()
            {
                return GetInfluenceByPlayer(0) - GetInfluenceByPlayer(1);
            }

            public void SetInfluenceForPlayer(int who, float v)
            {
                _influences[who] = Math.Max( v, _influences[who]);
            }
        }

        float _minInfluence;
        float _maxInfluence;
        int _width;
        int _height;
        List _influenceMapping;

        public InfluenceMap(float maxInfluenceValue)
        {
            _minInfluence = -maxInfluenceValue;
            _maxInfluence = maxInfluenceValue;
            _influenceMapping = new List();
        }

        public float GetTotalInfluenceAt(int x, int y)
        {
            float ret = 0f;

            if (x >= 0 && x < _width &&
                y >= 0 && y < _height)
                ret = _influenceMapping[y * _width + x].GetTotalInfluence();

            return MathHelper.Clamp(ret, _minInfluence, _maxInfluence);
        }

        public float GetTotalInfluencePercentAt(int x, int y)
        {
            // returns value between -1 and 1
            return GetTotalInfluenceAt(x, y) / _maxInfluence;
        }

        private float GetInfluenceByPlayerAt(int who, int x, int y)
        {
            float ret = 0f;

            if (x >= 0 && x < _width &&
                y >= 0 && y < _height)
                ret = _influenceMapping[y * _width + x].GetInfluenceByPlayer(who);

            return ret;
        }

        private void SetInfluenceForPlayerAt(int who, int x, int y, float v)
        {
            if (x >= 0 && x < _width &&
                y >= 0 && y < _height)
                _influenceMapping[y * _width + x].SetInfluenceForPlayer(who, v);
        }

        float _upDownValue;
        float _leftRightValue;
        float _bestValue;

        private float CalculateInfluenceForPlayerAt(int who, int x, int y, int dir)
        {
            _upDownValue = GetInfluenceByPlayerAt(who, x, y + dir); // north/south
            _leftRightValue = GetInfluenceByPlayerAt(who, x + dir, y); // west/east

            // subtract 1 from the value of our highest neighbor
            _bestValue = Math.Max(_upDownValue, _leftRightValue) - 1;

            // all values should be positive
            return (_bestValue > 0f) ? _bestValue : 0f;
        }

        private float GetInfluenceForUnitType(UnitStatus u)
        {
            return (u.Move + u.Range) * u.Attack;
        }

        // based on Chamfering/grassfire algorithm
        public void CreateMap(GameMap m, GameState gs)
        {
            int x, y;

            // rebuild map and working arrays
            _width = m.Width;
            _height = m.Height;

            // rebuild our array only if necessary
            if (_influenceMapping.Count != (_width * _height))
            {
                _influenceMapping.Clear();
                // zero out arrays
                for (x = 0; x < _width; x++)
                {
                    for (y = 0; y < _height; y++)
                    {
                        _influenceMapping.Add(new InfluenceKey());
                    }
                }
            }
            else
            {   // reset all existing influence values to 0
                for (x = 0; x < _width; x++)
                {
                    for (y = 0; y < _height; y++)
                    {
                        SetInfluenceForPlayerAt(0, x, y, 0f);
                        SetInfluenceForPlayerAt(1, x, y, 0f);
                    }
                }
            }
            // seed initial values based on units
            foreach (UnitStatus u in gs.Units)
            {
                if (u.IsAlive)
                {
                    SetInfluenceForPlayerAt((u.Owner == Globals.PLAYER_ONE) ? 0 : 1, u.X, u.Y, GetInfluenceForUnitType(u));
                }
            }
            
            // perform pass 1 (calculates based on North/West neighbors)
            for (y = 0; y < _height; y++)
            {
                for (x = 0; x < _width; x++)
                {
                    SetInfluenceForPlayerAt(0, x, y, CalculateInfluenceForPlayerAt(0, x, y, -1));
                    SetInfluenceForPlayerAt(1, x, y, CalculateInfluenceForPlayerAt(1, x, y, -1));
                }
            }

            // perform pass 2 (calculates based on South/East neighbors)
            for (y = (_height - 1); y >= 0; y--)
            {
                for (x = (_width - 1); x >= 0; x--)
                {
                    SetInfluenceForPlayerAt(0, x, y, CalculateInfluenceForPlayerAt(0, x, y, 1));
                    SetInfluenceForPlayerAt(1, x, y, CalculateInfluenceForPlayerAt(1, x, y, 1));
                }
            }
        }
    }
}

Last week, when the AI was grading the value of a space to move into, it had the following section to encourage it to move around:

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;

For Carl, this is replaced by the following (based on an influence map generated at the start of the Think() call).

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

            // get location score based on based on influence, (tend towards 0)
            ret = 8f - _influenceMap.GetTotalInfluencePercentAt(loc.X, loc.Y) * 8f;

With this change, Carl now has a preference towards moving areas where the influence is 0, which coincides with the battle front.  Here is a link to a video showing Carl playing Brutus from last week.

I added code to my draw to show the current influence map as well, so we can see the extra information that Carl is using.

I actually expected Carl to play a better game than he does, but it is certainly still a step up from last week, but I still do not have a solid beginner level AI player.  I have gotten some great suggestions that I hope to explore in the weeks to come, but did not yet include them as I want to progress in small bite sized chunks where I can see the level of proficiency of the AI player grow with each change.

Here is the full code listing for Carl:

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

namespace ShatteredThrone.AI.Brains
{
    class Carl : ComputerBrain
    {
        Random _random;
        Pathfinder _pather;
        CombatEngine _combat;
        InfluenceMap _influenceMap;

        public Carl()
        {
            _random = new Random();
            _pather = new Pathfinder();
            _combat = new CombatEngine();
            _influenceMap = new InfluenceMap(10f);
        }


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

            // get location score based on based on influence, (tend towards 0)
            ret = 8f - _influenceMap.GetTotalInfluencePercentAt(loc.X, loc.Y) * 8f;

            // 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 -= 3f;
                    // 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 += 1f;
                        if (u.CurrentDamage >= (u.MaxHP / 2f)) ret += 2f;
                    }
                    // if this unit generate extra income on settlements, give it more incentive to be here
                    if (s.GoldIncome > 0 && u.HasTrait(UnitTrait.CHARITY)) ret += 2f;
                }
                else
                {
                    // always good to capture settlements
                    ret += 2f;
                    // even better fully capture
                    if (s.Owner == Globals.PLAYER_NONE) ret += 2f;
                }
            }

            // 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;
        }

        private float ScoreHealForUnit(Point targetLoc, GameDetail gd)
        {
            float ret = -1f; // 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 = 1f;
                if (u.CurrentDamage >= 2) ret += 1f;
                if (u.CurrentDamage > (u.MaxHP / 2)) ret += 1f;
                if (u.CurrentDamage > (u.MaxHP / 3)) ret += 1f;
            }

            return ret;
        }

        private float ScoreAttackForUnit(UnitStatus attacker, Point attackLocation, Point targetLocation, GameMap m, GameState gs)
        {
            float ret = 0f;
            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 -= 3f + 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 += 4f + 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;
        }


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

            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)
        {
            float currentBestScore = -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
                    float 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);
            SubmitAction(currentBestCombatAction, u, currentBestMoveLocation, pc);
        }

        public override void Think(GameDetail gd, PlayerController pc)
        {
            // build influence map
            _influenceMap.CreateMap(gd.Map, gd.CurrentState);
            // 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);
                }
            }
        }
    }
}

Continued in part 4...