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

3 comments:

jaapk85 said...

Very interesting stuff, i don't think i can actually help you, since you know quite a bit more about me, but it might be a good next step to determine certain goals for the AI to achieve (for example capture a certain settlement). If your maps are fixed, you could preprogram an AI to focus on certain choke points, like capturing key settlements.

It might also be an improvement to determine which is the best order to move units, for example it might be useful to attack a certain target first with a unit with high defensive strength (which takes low damage in return) and afterwards attack it with a unit with a higher attacking power but possibly lower defense.

No matter what unit attacks first, you still kill the enemy, but if you first use the unit with the most defensive strength, you will take least damage on your own.

I really dont know if this is a useful approach, but maybe this will help you a bit!

Harvicus said...

Excellent points! I have put off brute forcing the order of the moves for now, as I have a few ideas which might change the way I approach that. It certainly is true with this game that order of moves makes a big difference.

I am currently implementing goals for the AI, and you should see that in the 4th installment.

Fuhans Puji Saputra said...

Hai, i am interested with your project especially the AI, could you please tell us how to make AI on the turn-based strategy game? because i am doing similar like yours. I am able to move the AI character by itself, but it is not follow the right procedure (not following the pathfinding). Thank you very much! I will keep in touch in this game!