Friday, December 14, 2012

Looking for a few good Marksmen...and Archangels...

I am not a very social person by nature, so I do tend to fall into the shadows for weeks, sometimes months at a time. The Shattered Throne project has been proceeding quite nicely. And I am hopeful that very soon I will be able to show something of an update to show how things are coming along.

The AI series is not done, I have actually been thinking about it quite a bit again lately. I reached a bit of a cart before the horse problem, where in order to make further progress, I really needed to finish the full game design. To that end I have added in the Undead faction, and thanks to some small unexpected profits from Shattered Throne, I was also able to pay artists for the assets for a third faction, the Nature/Fey faction.

Most of the videos I have done to date I have had the pleasure of my 10 year old son's company and help in narration. I shied away from narration in the past because it would take me all night to record a couple minutes of dialoge that I could live with, a nasty process consisting of 20 some takes per sentence...I am certainly not very good at thinking on my feet. With his help however, one take is enough, I now understand why sports commentators typically come in pairs.

Anyways, (sidenote, 'anyways' is my #1 goto word to start of sentences with, I have to be vigilant to allow only one such instance per email/post) I was recently checking through a collection of my son's school work that came home and the following assignment had me laughing, and I wanted to share it. There is no doubt that he is my son. Myself who grew up playing DnD, Nintendo, and Warhammer, I give you my own son, much like myself:

Wednesday, September 12, 2012

Juicing with ease

It has been quite a while since my last post. I took a bit of a break from game programming in general (sometimes after spending all day coding at work, it can be the last thing I want to do when I get home). When I did come back to Shattered Throne, I found myself with a lot of enthusiasm to improve the visual style of the game.

One thing I have learned in developing games as a hobby, is that you have to follow where your current passion is. One of the main inspirations for this new obsession is the following most excellent video on adding juice to games.

The speakers in the video mention the use of easing functions to produce more natural animations as well as using particle effects among other great ideas.  So I wrote a list of simple animation ideas to enhance the game visuals and spent the next several weeks implementing each one.

  • Update the next turn swipe animation with easing
  • Changing the texture of the map selection highlights and add a fade in/out pulse animation
  • Increased the size of the damage numbers to make them easier to see and using an outlined font
  • Small screen shake and burst animation when a unit takes damage
  • Combo point stars flip up and sparkle when created
  • Stars and Gold resources fly up to the banner with a sparkles when these resources are gained
  • Coins flip up out of settlements when they generate gold
  • Star/combo icons on units have a periodic shimmer
  • Conditions applied to units use a fade in/out pulse, as well as cycle between multiple icons when a unit is suffering from multiple conditions at the same time
  • New Settlement capture animation and particle effects
  • Different sized stars on the player status banner show how many stars are needed to use both the leader's major and minor spells
  • The stars on the banner jump in a wave when the player has enough to cast a spell
  • A new simple animation when a unit heals
  • Arrows leave a trail behind as they fly towards their target
  • Stars explode from banner when used to cast a spell
  • New skull and bones image when a unit is killed
  • A simple light flash when a unit is built (I had trouble coming up with any good generic animation besides this one)
  • A rewind effect animation when the player chooses to Undo their last move

I am also considering adding some extra visual effects to the game dialog popups, but I do not yet have those in their final state yet, so this will have to wait.  The game is also missing a few art assets I am hoping to include such as Faction Emblems and Small Leader portraits by the status banner.

You can see the results in the following video:



As I mentioned above, a majority of the additional effects made use of both Easing functions and particle effects in addition to some simple sprite based animations.  There are a lot of different 3rd party particle effect engines that can be used, as well as good information on creating your own, so I will avoid discussing that in very much detail.  I did find it a bit more difficult to find actual good code samples for different easing functions, so I wanted to include those I used here.

Easing functions are all about providing more natural looking animations, by remapping a period of time to a curve.  As such, each of these functions take a float value between 0.0 and 1.0, representing the current time as a percentage of the whole.  The result is also a value between 0.0 and 1.0 that is used to scale some factor, such as distance, scale, or alpha values (the Bounce easing functions can generate values outside the normal 0.0 to 1.0 range to produce the actual bounce effect).

using System;

namespace ShatteredThrone
{
    class EasingFunctions
    {
        public enum EasingType
        {
            NONE = 0,
            LINEAR,
            PARABOLIC,
            PARABOLIC_QUAD,
            QUAD_IN,
            QUAD_OUT,
            QUAD_IN_OUT,
            QUAD_IN_WITH_START_BOUNCE,
            QUAD_OUT_WITH_END_BOUNCE
        }

        const float BOUNCE_TIME = .15f;
        const float NO_BOUNCE_TIME = 1f - BOUNCE_TIME;
        const float BOUNCE_SIZE = .05f;

        public static float LinearEase(float percent)
        {
            return percent;
        }

        public static float QuadEaseIn(float percent)
        {
            return (float)Math.Pow(percent, 2f);
        }

        public static float QuadEaseOut(float percent)
        {
            // p = 1 - (1-t)^2
            return 1f - (float)Math.Pow(1f - percent, 2f);
        }

        public static float QuadEaseInOut(float percent)
        {
            float ret = 0f;

            if (percent < .5)
            {
                ret = (float)(Math.Pow(percent * 2f, 2f)) / 2f;
            }
            else
            {
                ret = 1f - (float)(Math.Pow((1f - percent) * 2f, 2f)) / 2f;
            }

            return ret;
        }

        public static float ParabolicEase(float percent)
        {
            return (float)Math.Pow(percent - 0.5f, 2f) * (-4f) + 1f;
        }

        public static float QuadParabolicEase(float percent)
        {
            return (float)Math.Pow(Math.Pow(percent - 0.5f, 2f) * (-4f) + 1f, 2f);
        }

        public static float QuadOutWithEndBounce(float percent)
        {
            float ret = 0f;

            if (percent < NO_BOUNCE_TIME)
            {
                // ease out to dip
                ret = QuadEaseOut(percent / NO_BOUNCE_TIME) * (1f + BOUNCE_SIZE);
            }
            else
            {
                // dip down
                ret = (1f + BOUNCE_SIZE) - BOUNCE_SIZE * QuadEaseOut((percent - NO_BOUNCE_TIME) / BOUNCE_TIME);
            }

            return ret;
        }

        public static float QuadInWithStartBounce(float percent)
        {
            float ret = 0f;

            if (percent < BOUNCE_TIME)
            {
                // dip up
                ret = -BOUNCE_SIZE * QuadEaseIn(percent / BOUNCE_TIME);
            }
            else
            {
                // ease away from dip
                ret = QuadEaseIn((percent - BOUNCE_TIME) / NO_BOUNCE_TIME) * (1f + BOUNCE_SIZE) - BOUNCE_SIZE;
            }

            return ret;
        }

        public static float Compute(float percent, EasingType et)
        {
            float ret = 0f;

            switch (et)
            {
                case EasingType.LINEAR:
                    ret = LinearEase(percent);
                    break;
                case EasingType.PARABOLIC:
                    ret = ParabolicEase(percent);
                    break;
                case EasingType.PARABOLIC_QUAD:
                    ret = QuadParabolicEase(percent);
                    break;
                case EasingType.QUAD_IN:
                    ret = QuadEaseIn(percent);
                    break;
                case EasingType.QUAD_OUT:
                    ret = QuadEaseOut(percent);
                    break;
                case EasingType.QUAD_IN_OUT:
                    ret = QuadEaseInOut(percent);
                    break;
                case EasingType.QUAD_IN_WITH_START_BOUNCE:
                    ret = QuadInWithStartBounce(percent);
                    break;
                case EasingType.QUAD_OUT_WITH_END_BOUNCE:
                    ret = QuadOutWithEndBounce(percent);
                    break;
            }

            return ret;
        }

    }
}

Wednesday, June 6, 2012

Turn Based Strategy Game AI part 8

Continued from here...

Last time, we moved all constant values used for weighting different moves and goals into a single class called a DispositionProfile.  Going a step forward, a collection of these objects was created called a DispositionProfileSet, which used a different DispositionProfile based on the state of the game.  In essence giving it different behaviors based on whether it was winning, losing, or trying to expand.

There was one glaring problem however, I was picking the actual numbers.  Bringing all my own biases and expectations on how things should work.  Instead I wanted these numbers to be based on how things actually worked.  To do this I turned to using a Genetic Algorithm to compute the best numbers to use.

The general idea was pretty simple:
  • Create a population of  DispositionProfileSets initialized with random values
  • Play a game with each DispositionProfileSet in the population
  • Give each DispositionProfileSet a score based on how well it performed
  • Create a new population by:
    • Randomly choose 2 "parents" from the current generation with the chance of selection being based on their score
    • Each value in the new "child" DispositionProfileSet is computed as the average of its parents
    • Randomize 10% of each value further by +/- 50%  (aka Mutation)
  • Repeat the above sets for several population sets (Generations)

Given a large enough population, each generation will slowly become better at the given task (measured by the score each DispositionProfileSet generates).  I had built my game engine such that visuals were unnecessary, allowing me to run batches of games as I always had intended on trying to "evolve" the AI through the use of a Genetic Algorithm such as this.

I settled on a population size of 30, and would have each DispositionProfileSet play against last week's AI George.  I set the game to end in a loss after 40 turns.  Each AI player would gain 1 point for each turn it survived in a loss.  For a win, the AI would score 50 + 1 point for each turn prior to 40 it achieved victory.  The idea was to generate an AI that would win as quickly as possible.

I then started up the simulator and waited for the magic to happen.  Early AIs would lose in under 20 turns, but with each generation the number got larger.  Each game took 1-2 minutes to run in batch mode, such that each generation took about 90 minutes to complete.  I went to bed with the simulator running, hoping to see some wins the next day.

The next day showed that the average AI player was now losing at the maximum of 40 turns, but not a win in sight.  To try to address this, I made several small tweaks.
  • I set the parent selection to use the squared score, giving even greater chance for the high scoring AI players to propagate into the next generation
  • I added 5 new, completely random AI players into each population in the hopes of introducing some extra diversity into the population to keep it from stagnating
  • I had each AI player play 2 games, one as player 1, the other as player 2, attempting to eliminate any advantage or bias of playing one side over the other

Several long days later, there was no change.  Regardless of the various tweaks, the population would stagnate at hover at the best score for losing a game, 41.  After 100's of generations, not a single win.

After each generation, I would save out each DispositionProfileSet to disk, so I loaded up one of the most recently "evolved" players into the game viewer to take a look.  What I found was pretty surprising, the AI player would build 3-4 units, and then just sit there, passing each turn without action.  This seemed to work, as through some strange quirk in his logic, George would never identify the AI as a threat and was content to simply build units and hang out on his side of the board. 

Needless to say, I was pretty upset.  I had already left this simulator running day and night for the last week, completely neglecting Diablo 3.  I had nothing to show for it.  In trying to brainstorm where I went wrong, I concluded that the fitness test I used to score each AI player was the issue.  Afterall, the AI evolved to do exactly what I asked it to do, survive as long as possible, and it accomplished this by adopting a completely passive strategy.

I decided to change up the way I scored each game.  This time I would base it not on winning or losing, but on maximizing resources, figuring that an AI that managed its resources the best would also be good at winning.  So the updated scoring became:

+1 point awarded for each Gold gained
+3 points for each Mana gained (a ratio already partially established in the game)
+points equal to the cost of each enemy unit killed
-points equal to the cost of each friendly unit lost

I started each unit with 200 points to represent the amount of gold each side began with, and then divided each AI player's score by the number of turns the game lasted.  I ran George through the simulator against himself to get a baseline score (George scored a respectable 51 points).  Then the simulator was started up from the beginning once again.

Early scores were low (between 2 and 20) but ramped up quickly from there.  I ran it through 30 generations and starting seeing regular scores in the 80's and even a few into the 90's.  I ran the top 5 scoring AI players up against George in visual mode.  Each AI player won handily against George.

Comparing the evolved numbers against those I derived myself in George shows a few interesting bits (you can see the numbers yourself here).  The AI player has assigned negative values across the board for moving wounded units onto settlements to be healed for example, finding higher value in attacking with the units even when they are close to being eliminated.  Such values that go against my own common sense can have a few explanations, all of which are interesting:
  • At only 30 generations, I just did not run the simulation long enough for all numbers to converge
  • The Units and their abilities are just not balanced properly
  • Certain game systems (such as healing on settlements) does not have enough value to be worthwhile
  • A certain situation or value did not get exercised enough during the simulation to converge towards a maximum
  • My AI logic is flawed/bugged
  • My AI contains unnecessary logic

This makes this tool a lot more interesting than simply generating a good AI player.  It can be used to identify potentially unbalanced game systems and units and test the game itself.  The fact that the simulation ran without a hitch for 1000's of games without interruption gives me a good feeling about the stability of my code.  I do wish I had run it through a profiler, as 1-2 minutes per game seems excessive, and is likely something that could be easily remedied.

Initially I had a lot of expectations around the results of this phase of the project.  Initially they were crushed, but in the end I am really glad for building in the game batching and genetic algorithm, as it will give me many useful tools throughout the rest of this game project.  The AI I ended up with is unlikely to be the final version.  As game systems change and get added, I will certainly be running the simulation again.

I can also build out different AI behavior sets to address different factions, leaders, and even certain problematic maps.  Of all the steps I have taken during this project, none feels more right or correct than having all the weights and values used in the AI calculations separated out into a single central class like the DispositionProfileSet I have been using.  This is a concept I would very much recommend to others working on similar projects.  The ability to then use such a class in a Genetic Algorithm makes it all the more valuable.

Check out this week's evolved AI Henry take on George in this episode's video:

Tuesday, June 5, 2012

Nearly Ready

The next installment of Developing a Turn Based AI should be up tomorrow. I posted the video already and unlike prior chapters, I was unable to get the accompanying post ready on the same day. So if you are here after watching the Part 8 video, check back tomorrow for the full details.

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

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

Sunday, March 25, 2012

Turn Based Strategy AI part 2

Continued from Part 1

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







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

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

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

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

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

            return ret;
        }

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

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

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

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

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

            return ret;
        }

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

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

            return ret;
        }


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

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

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

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

            return ret;
        }

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

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

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

public override void Think(GameDetail gd, PlayerController pc)
        {
            // get units to move
            List units = GetUnitsLeftToMove(pc.PlayerIndex, gd.CurrentState);

            // do we have any units left to move
            if (units.Count > 0)
            {
                // pick a unit at random
                UnitStatus u = units[_random.Next(units.Count)];
                // do best move for this unit
                SubmitBestMoveForUnit(u, gd, pc);
            }
            else
            {
                // get available settlements to build
                List builders = GetAvailableBuildingSettlements(pc.PlayerIndex, gd.CurrentState);
                PlayerResources pr = gd.CurrentState.GetPlayerResources(pc.PlayerIndex);
                // get list of units we can afford
                List buildableTypes = GetBuildableUnitTypes(gd, pr.Gold, pc.PlayerIndex);

                // do we both have enough money and places to build?
                if (builders.Count > 0 && buildableTypes.Count > 0)
                {
                    // get random settlement to build at
                    Settlement s = builders[_random.Next(builders.Count)];
                    
                    // submit command to build random unit at random location
                    SubmitBuild(buildableTypes[_random.Next(buildableTypes.Count)], s.X, s.Y, pc);
                }
                else
                {
                    // nothing left to do except end our turn
                    SubmitEndTurn(pc);
                }

            }
        }

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

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

Continued in part 3