Draft AI design/spec for Chaos-like turn-based tactical game

Earlier this year we were briefly involved in the design and early production of a Chaos-like game, inspired directly by Julian Gollop's popular original Chaos: The Battle of Wizards.

If you're not familiar with the original check out the many resources linked from the above wikipedia article and the original game rules.

Before the project was cancelled, we produced a version 1 AI design - which, unfortunately, never got used (or reviewed for that matter). So, in all it's unedited, incomplete glory, here is a design document for a Chaos AI. Apologies for the variable formatting - it's come via Google Docs > HTML > embedded CSS to this post.

Use it for what you like - and if you do fancy reviewing, editing or improving on it, do so and let us know in the comments and we'll keep it up to date.

This work is licensed under a Creative Commons Attribution 3.0 Unported License

AI Design for a Chaos-like game

Notes

This assumes game rules are enshrined in the interface functions provided to the AI player/code, but is written in such a way that it should behave in legally.

This is (should be) modular such that individual methods and calculations can be adjusted independently.

It assumes a set of constants that can be adjusted (and managed separately) for each AI player to produce a set of differently-behaving AIs. See AI Type and the Constants section for more information.

The design is set up to take positive actions based on the queries it makes to game state. As such, it can be incomplete (insofar as it may not recognise creature, spell or player characteristics or behaviors) but still functional (i.e. will still play turns).

In order to remain performant relatively easily manipulated through data (constant) changes, it performs single turn analysis in two broad stages (tactical and local/per creature). Long running actions (such as multi-turn moves to a target) are managed by creating predictable (within the given set of constants) behaviours that are also affected by previous actions (in the form of last-turn decision memory) that is affected by a weighting constant (see RankTargets and RankTargetsLocally). This allows for one AI player to be very responsive to new circumstances (a nearby threat mid long-running move) whilst another AI player may show determinism to follow through on long-running actions.

Discussion points / things to complete:

1. Should all creatures know ranged attack range of all other creatures? i.e. for inbound proximity (Ranged Defense Proximity, Melee Defense Proximity). A good human player might - but it's not realistic to expect that they always would.

2. How to handle infinite values (i.e. a creature that's not reachable - i.e. in water), significant for the purposes of calculation and multiplication. Options are:

2.1. Use 0 - will nullify any multiplying factor in relevant calculations
2.2. Use fixed representation of infinity (e.g. 9999) - will balloon factors in multiplying calculations

The real impact of the above is if a value that could be infinity (any of the proximities potentially) is used in a multiplication (which they are in RankTargetsLocally()), states that return the infinite value will result in either a 0 value or a higher value than anything else (other than other infinities).

One or the other will likely be desirable but a consistent use of potentially infinite values is preferable. If necessary, the logic could always be switched with (e.g. value==0 in the case of using infinity==0).

EDIT - this is largely irrelevant now - 2.1 isn't a valid option as it's possible to be adjacent to a target and have a proximity query return 0.

3. Handling of non-creature spells not factored into tactical or local decision making (i.e. avoidance of sticky blobs, movement toward citadels etc etc). Casting of these spells also isn't considered (but its not being considered is covered in the current non-specification of SelectAndCastSpell()).

4. How would/should a creature move away from a threat? This is potentially covered in MoveToTarget, option 2 in circumstances that include the creature ranking a very threatening creature as the current target and then acting "scared". This does not cover movement away from a creature/threat that is not the targeted creature, however (i.e. a creature may melee attack creature 1, ranged attack creature 2 but still want to move away from creature 3 or another threat (blob, fire etc).

5. Ranged proximity calculations are not accurate (and could be unpredictably very inaccurate) as they rely on a movement pathfind - obvious alternatives would be computationally expensive.

6. MoveToTarget() needs expansion - both in a tactical sense (making smarter movement decisions) and a practical one (how to accomplish path finding and boundary decisions). See description for more information.

7. How do wizards (and to some extent creatures) stay put / run away (different rank local for wizards?). Affected also by special spells and feature (towers, citadel etc). Separate decision for keeping wizards safe, then weighted against immediate threats (i.e. if it can't move out of range then eval RankTargetsLocally)?

8. How/should creatures make decisions about the threat of a wizard's potential spell casts (i.e. because they can't be evalutated as a simple threat calculation).

Legend

Stub methods / procedures
    - written in style MethodName(Argument 1, Argument 2)
    - only information relevant at point of mention is included in arguments list

Concepts

DATA

CONSTANTS

META - stuff not done, reminders and suchlike.

AI Player's move - outline steps

1. RankPOPs(): Rank Points of Presence (POPs) - Player's Wizard and Creatures
   
   
2. IdentifyTargets(): Identify Targets (up to MAX_TARGETS)
   
   
3. RankTargets(): Rank Targets
   
   
4. SelectAndCastSpell(): Select & cast spell appropriate spell, insert created creature (if any) into RankedPOPs (no position mechanic as yet - suspect first or last will work best, re-rank is feasible)
   
   
5. (optional) IdentifyTargets() as a new creature may affect proximity-based calculations (see IdentifyTargets for options)
   
   
6. (if spell cast sucessful) PurgeTargets(): Remove destroyed creatures / wizards
   
   
7. (if spell cast sucessful) RankTargets(): Update rankings based on presence of new creature
   
   
8. Step creatures (in order of RankedPOPs, but with Wizard moved to last place), and:
1. TestEngagement(): check if creature is being engaged
   
2. RankTargetsLocally(): sort RankedTargets for applicability to this creature
   
3. Set CurrentTarget to position 1 on RankedLocalTargets
4. MoveToTarget()
5. MeleeAttack()
6. If CurrentTarget no longer exists, select a new CurrentTarget (position #2 on RankedLocalTargets)
7. RangedAttack()
8. If CurrentTarget has not been destroyed, set this creature's LastTarget to CurrentTarget
9. (if any attack was successful) PurgeTargets()
10. (if any attack was successful) RankTargets()

Method descriptions

RankPOPs

Create sorted list of wizard and creatures (RankedPOPs) for the AI player, with Wizard always first and each creature listed in descending order of Relative Value.

Also needs to factor likelihood of engagement, so rank value should be:

Relative Value - (Number of Adjacent Creatures * ENGAGEMENT_PARANOIA)

IdentifyTargets

Scan entire visible map, then for each found wizard or creature calculate:

Perceived Value * SUM(Simple Distance to POPx from creature * Relative Value of POPx)

Note: the SUM part is evaluated for each of the AI Player's POPs.

Sort this list descending and store top MAX_TARGETS in Targets
 
Note - actual ranking is done in the RankTargets stage - the approximate calculation of importance shown above exists solely to create a sorted list (such that the top x creatures can be properly considered in RankTargets).

Potential simplification: if it is possible to consider all targets in RankTargets (i.e. for a performance perspective), this step can likely be removed (a simple map scan would suffice).

ALTERNATIVE - work out from POPs (in descending order of importance), going 1 extra hex in radius for each iteration of the POPs list until reaching MAX_TARGETS. Note:
 - would need to ignore duplicates
 - doesn't necessarily hit all wizards
 - no assessment of value / threat / risk imposed by creatures discovered, only considers proximity to important targets

RankTargets

Prepares a ranked list of targets (in order of tactical importance), which can then be sorted locally for each controlled creature, and used for spell casting and wizard movement decisions.

See RankTargetsLocally for usage on a creature level.

Obtain rank for each creature(x) by:
RANK =

  (1 / Position in targets list) * TARGET_NEARBY_CREATURES
+ Threat(x, wizard) * WIZARD_PROTECTION
+ SUM(Threat(x, each creature)) * COMPANION_PROTECTION
+ Previous rank (rank score, not position) on RankedTargets list * PARTY_DETERMINATION
+ (1 / Turn Age of x) * ATTENTION_TO_NEW_CREATURES
+ Attention from Opponent * FOCUS_ON_AGRESSORS

Rank should also incorporate target affinity (i.e. targeting creatures belonging to the same wizard), this could be done as a simple distribution, e.g.:

+ (# Affiliated Targets / # Targets) * FOCUS_ON_SINGLE_OPPONENTS (not yet defined)

However, it would be more useful to balance it as attention on powerful opponents (based on the actual ranking value of all of each opponents creatures), so alternatively the entire RANK sum for an individual creature could then be:

* (# Affiliated Targets / # Targets) * FOCUS_ON_SINGLE_OPPONENTS (not yet defined)

Incorporate "rescue" like behavior for companions who are potentially engaged - with a factoring on ATTENTION_TO_ENGAGED_COMPANIONS. This was lost somewhere along the way - behavior may be emergent from other characteristics.

Note: see "Constants" section for description (and effect) of each constant.

RankTargetsLocally()

This will be a re-sort (by adding a local rank score to the existing rank and re-sorting - i.e. if the creature in position 1's rank score is orders of magnitude in score above position 2+, little will prevent all creatures from attacking (locally ranking at #1) that target.

Targets are re-ranked locally to obtain a target to attack (or to move to attack if out of range).

As per step 8. in the AI Player's move, this is done for every creature (AI Creature) for each target creature (Target Creature) in the RankedTargets list.

Local Rank for creature x =

(Rank
 + IsEngaged * (Move Proximity == 0) * FOCUS_ON_ENGAGING_TARGETS
 + Threat(Target Creature, AI Creature) * CREATURE_SELFISHNESS
 + Threat(AI Creature, Target Creature) * DESIRE_TO_KILL
 + (Target == Last Target) * CREATURE_DETERMINATION
 + (1 / Team Compatibility) * ATTENTION_TO_DIFFICULT_TARGETS
) * Compatibility

The Compatibility multiplier essentially forces unattackable targets to the bottom of the list when Compatibility is 0 and as a consequence of wizards being prone to attacks from all creatures (and therefore higher in the list) mean a creature should never attack an incompatible target.

Must include significant weighting for any immediately threatening creatures (i.e. ignoring tactics in favor of self defense) - NOTE: this replaces the old AssessThreatsToCreature() method and associated break-out loop from inner list of step creatures.

SelectAndCastSpell

Expand, considering:
- value ranking (against ranked targets)
- relative value of subsequent creature
- tactical (group wise) value
- likelihood of success (factored against constant)
- forward value (i.e. spell tactics)
- likelihood of illusion present (to cast disbelieve) (simple decision tree?)
- decision on casting an illusion (simple decision tree?)
- casting creatures that will be incompatible (undead etc)
- decision on non-creature spells and buffs, inc blobs, fires, citadels, turmoil, subversion, vortex, shadow form, teleport (embedded within decision tree that includes creature spells?)

TestEngagement()

Test for engagement and store in IsEngaged

MeleeAttack()

Attack the CurrentTarget with this creature's melee attack.

If out of range, this method could still be called (but obviously no attack will take place).

RangedAttack()

Attack the CurrentTarget with this creature's ranged attack.

If out of range, this method could still be called (but obviously no attack will take place).

MoveToTarget()

Make a movement decision for the current creature, based on it targeting the specified target.

If engaged, MoveToTarget() will return without movement having happened.

Movement assumes doing a pathfind to desired position and moving through that route as many place as is permitted by creature's movement ability.

Does not consider terrain types (other than in the sense that they're passable by some creatures and not others) - i.e. a defensive move for a weak creature vs one that can't pass terrain x, would be to move into terrain x and attack ranged only.

Also does not consider avoiding engagement and tactical choices on which side to engage an enemy, blocking opponent paths etc.

OPTION 1
    If the creature has a melee attack, move to within Melee Range (which may mean staying put).
    If the creature only has a ranged attack, either:
        Stay put if in range
        Move to within range (but no further)

OPTION 2
    Make assessment of relative threat and either act:
    AGGRESSIVELY
        If creature has melee move to within melee
        If no melee, move toward target (expand - how far toward target?)
    DEFENSIVELY
        Regardless of melee ability, move to just within ranged range
    SCARED
        Move away from target (which may still be in ranged range)

PurgeTargets

Check each creature / wizard in RankedTargets list still exists (if not, remove it from list)

Threat (attacker, defender)

The relative threat imposed by creature a on creature b.

EXPAND CALCULATION

Must sum (or multiply as appropriate):
- Actual Attack (a, d)
- Actual Defense (a, d)
- Proximity for Melee (in terms of number of turns to reach range - 0 should be special case)
- Proximity for Ranged (in terms of number of turns to reach range - 0 should be special case)
- Chance of hit (is this applicable)
- Chance of resist
- Chance of engagement and/or being engaged

Actual Attack (attacker, defender)

The actual attack value of creature a when attacking creature b.

EXPAND

Includes:
- base attack value
- buffs
- terrain bonus for attacker (inc special terrain types - citadel etc - if applicable)

Actual Defense (attacker, defender)

The actual attack value of creature a when attacking creature b.

EXPAND

Includes:
- base defence value
- buffs
- terrain bonus for attacker (inc special terrain types - citadel etc - if applicable)

Concept descriptions

Note: most are methods that return a scalar.

Relative Value

Typically used for AI player's creatures. The value of a creature compared to other creatures.

Calculated as a sum of relevant creature attributes with an individual multiplier constant on each. Attribute sum may look like:

RELATIVE_VALUE=

  movePoints * IMPORTANCE_OF_AGILITY
+ attack * IMPORTANCE_OF_ATTACK
+ defence * IMPORTANCE_OF_DEFENCE
+ magicdefence * IMPORTANCE_OF_DEFENCE
+ initiative * IMPORTANCE_OF_AGILITY
+ canFly * IMPORTANCE_OF_AGILITY
+ isUndead * IMPORTANCE_OF_UNDEAD
+ isMount * IMPORTANCE_OF_AGILITY

Note: the IMPORTANCE_OF_UNDEAD is no more complicated than the AI Player favoring undead creatures in spell selection and tactics - however, see alternative note 2 below where it could be more significant.

ALTERNATIVE 1: a finer grained weighting could apply constants to each part of the calculation (i.e. split out agility and the like).

ALTERNATIVE 2: a more complicated calculation could be based upon game state, e.g. other creatures on the map (e.g. an undead creature is worth more if there are no other undead creatures, for example).

Note: Could be calculated differently per AI Type, but shouldn't need to be directly - changes in constants should be sufficient.

Perceived Value

The apparent value of an opponent creature or wizard. Similar to Relative Value, but:

- Ignorant of illusions
- Doesn't know stats on wizard
- Wizards' value will be multiplied by a fixed (per AI Type) constant PERCEIVED_WIZARD_IMPORTANCE such that they are more directly targeted.

Note: A separate set of IMPORTANCE_OF_ constants could be used for perceived value (for each AI Type) but is unlikely to be needed.

Compatibility

The ability for the given creature to attack (in any form) the given target. 0 if incompatible (i.e. attacking undead with a non-magic-casting mortal), 1 otherwise.

If water creatures are invunerable to attack (other than magic, other water creatures and dive bombs) this would include return 0 in such a circumstance.

The logic for any such compatibility test (or incompatibility between creature types / situations) can be embedded here without modifications elsewhere.

Wizards are always 1 against any target.

Team Combatibility

The team's mean compatibility with the target (3 of 4, including wizard would be 0.75).

Attention from Opponent

Relatively, how attention is the AI Player getting from the give opponent.

Could be calculated (remembered) as:

Total Number of Opponent Attacks / Total Number of Opponent Attacks Against Me

Note: A human player will likely make a judgement decision on this, not an actual one - but remembering the attack distribution for the purposes of satisfying the above sum for AI Players shouldn't have a significant unfair impact.

AI Type

A set of fixed weightings and constants that characterise a particular AI. See "Weighting Constants" in the Constants section.

Simple Distance

Straight-line distance between creatures.

ALTERNATIVE: use Move Proximity (far more potential computation due to aggregate use of Simple Distance in IdentifyTargets).

Melee Range

Generally 1, but greater in some cases (creatures with Dive Bomb ability, for example).

Move Proximity

Number of moves (spaces) required to be adjacent to target. If the target's already adjacent, should return 0.

If it's not possible to reach the target (i.e. blocked or incompatible terrain), return PROXIMITY_INFINITE.

Number of moves based on path find to target, not straight line.

Proximity should include adverse terrain affects (i.e. a single hex width 50% movement speed will result in a distance of 2, not 1, for that hex). Note - irrelevant if moves are costed.

Melee Attack Proximity

=Move Proximity - Melee Range (floored to zero - negative results only indicate creature is already in range).

Note: not accurate/optimal under certain conditions (i.e. dive bombing could bomb over impassable terrain, meaning a move pathfind takes a longer route).

Ranged Attack Proximity

Based on getting to a point from which a ranged attack can be initiated.

For simple calculation, it could be:

= Move Proximity - Ranged Range

However, this doesn't provide an optimal path as blocking in the later section is different for ranged weapons and creature movement.

Melee Defense Proximity

=Move Proximity - Melee Range of targeted creature (floored to zero - negative results only indicate already in range of that creature).

Note: not accurate/optimal under certain conditions (i.e. dive bombing could bomb over impassable terrain, meaning a move pathfind takes a longer route).

See note 1. regarding AI Player's knowledge of other creatures' abilities.

Ranged Defense Proximity

Based on the targeted creature getting with ranged distance.

For simple calculation, it could be:

= Move Proximity - Ranged Range of targeted creature

However, this doesn't provide an optimal path as blocking in the later section is different for ranged weapons and creature movement.

See note 1. regarding AI Player's knowledge of other creatures' abilities.

Turn Age

The number of turn for which a creature has been present in the game.

Data descriptions

Boolean values stored as int(0|1) for the purposes of calculation.

RankedPOPs - see RankPOPs - top of list is greatest value (Relative Value - with Wizard at top regardless)

Targets - list of targets (see IdentifyTargets)

RankedTargets - ranked list of targets (see RankTargets)

CurrentTarget - (per creature) the target a creature is currently operating on

RankedLocalTargets - re-ranked version of RankedTargets based on applicability to current creature

IsEngaged (bool) - is current creature currently engaged

Constants

See AI Type for details on usage

Note: each constant may require a companion constant (multiplier) (not specific to AI Type) in order to balance disparate figures and obtain approximate balance amongst design-adjusted constants (those below) such that they can all be represented in similar orders of magnitude and/or are otherwise clear in usage. A range of viable/sensible parameters should come out in testing (and analysis of ranking functions outputs).

General constants

MAX_TARGETS - The max number of targets considered in AI players decision

PROXIMITY_INFINITE - Likely 999 or similar.

Weighting constants (all are relative - i.e. increasing every constant by the same factor will have no affect).

PERCEIVED_WIZARD_IMPORTANCE - Higher values will cause AI Players to target player wizards more directly

ENGAGEMENT_PARANOIA - Higher value will cause creatures that can't be engaged (no adjacent enemies) to act first.

FOCUS_ON_ENGAGING_TARGETS - Higher values will cause creatures to directly target any adjacent creatures when engaged, lower values won't necessarily mean the oppposite but will allow for a chance of attacking other creature with ranged attacks if other circumstances promote/permit it.

ATTENTION_TO_ENGAGED_COMPANIONS - Higher value will cause more attacks on creatures that are potentially engaging companions.

IMPORTANCE_OF_AGILITY - Used in relative value. Will cause AI Player to favor agile creatures in spell selection and tactical importance.

IMPORTANCE_OF_ATTACK - Used in relative value. Will cause AI Player to favor high attack value creatures in spell selection and tactical importance.

IMPORTANCE_OF_DEFENCE - Used in relative value. Will cause AI Player to favor high defence value creatures in spell selection and tactical importance.

IMPORTANCE_OF_UNDEAD - Used in relative value. Will cause AI Player to favor undead creatures in spell selection and tactical importance.

TARGET_NEARBY_CREATURES - Higher value mean creatures that are closer to more of the AI Player's creatures will be targeted more readily.

WIZARD_PROTECTION - Higher values will cause all creatures to target creatures that threaten the wizard most.

COMPANION_PROTECTION - Higher values will distort targets such that the most threatening creatures (to the entire party) are ranked at the top.

PARTY_DETERMINATION - The extent to which targeting choices should be carried between turns. High values will cause creatures that are ranked high to continue to rank high until they are killed and new creatures to be ignored.

ATTENTION_TO_NEW_CREATURES - Higher values will cause newly casted creatures to be ranked higher. Can be used to balance PARTY_DETERMINATION

FOCUS_ON_AGGRESORS - Higher values will cause higher ranking of creatures belonging to opponents who have attacked this AI Player more than other players, and subsequently should cause opponents who have not attacked this AI Player to be left alone (all else being equal).

CREATURE_SELFISHNESS - The attention paid to creatures who impose a local (personal) threat to the creature in question. Essentially the extent to which tactics are followed.

DESIRE_TO_KILL - Higher values will cause higher targeting of creatures that this AI Creature has a better chance of killing. THIS IS IMPORTANT as it effectively dicatates the sensible matchmaking of creatures in the AI Player's roster with the tactical list of targets). Obviously needs to be balanced against everything else though ;)

CREATURE_DETERMINATION - Higher values will cause the creature to prefer creatures that it's previously targeted.

ATTENTION_TO_DIFFICULT_TARGETS - Higher values will cause creatures that are compatible with creatures that are difficult (in the sense than not many companions can target then - i.e. undead) to target them more directly. I.e. undeads will always go for undeads all else being equal.

Gareth Jenkins | Post a Comment | Share Article | Permalink | tagged ai, chaos, creativecommons, design, resource in resources