Summaries - Primitive measures

How does an AI evaluate the strength of a position?

This document sumarises some primitive measures that could be combined to produce the basics of a position evaluation function. Most of this converstation happened during September 2003 under the thread "Position evaluation".

Per-position Measures

Overall Game Progress

The "Calhamer Index" is the standard measure of overall game progress. However, a small modification makes it more suitable for a an AI that can play on variant maps. This problem with the Calhamer Index is that it takes a different range across different maps because it does not take into account the number of SCs required to win the game. Andrew suggested the following overall progress index.

sum(i = 1 -> powers, SCs(i) ^ 2)
-------------------------------- x 100%
2 * ((SCs / 2) ^ 2)

This index cannot be less than 0 and if it reaches 100 or greater than a power has won the game. Note that it is not strictly a percentage because it can exceed 100. Also note that at the start of the game, it will not have a value of 0. The standard game starts at 22%.

This measure could easily be enhanced so that the game started at 0%.

Per-power Measures

Personal Progress

It is useful to have an personal progress measure in terms of the number of SCs owned because a game is won when the required number of SCs are owned and tracking progress towards that target is useful. Andrew suggested the very simple measure below.

SCs owned / SCs required

SCs required is the total number of SCs divided by two and rounded up to the nearest integer.

Fear Factor

See Paul Windsor's excellent article on fear factor. Whilst Paul discusses it in a static sense, looking at the start of the game, this could easily be computed on a per-turn basis and the results compared with the results of previous turns. This may help to reveal the alliance structure of the game.

Tempi

See another of Paul's excellent articles. This time it's on tempi. Tempi is a measure of how advanced units are. The idea here is that time is a valuable commodity. It takes time to get a unit to an advanced position. Therefore, when disbanding (for example), it may be wise to disband a unit nearer home. The change in tempi from one turn to the next is a good measure of how much progress a player is making. If they aren't getting anywhere, perhaps now is the time to pounce.

n-cohesion

Andrew invented this measure of whether or not a power's units formed a cohesive front or whether they were scattered to the four corners.

Firstly, this measure is formally n-incohesion - you'll see why in a minute. However, it is usually more convenient to talk of the opposite measure, n-cohesion.

n-incohesion covers a range of measures (1-incohesion, 2-incohesion, 3-incohesion, etc. for any positive integer n).

For each unit belonging to the power in question, compute the sum of the distance to the nearest n units and divide by n. Add together the values for all the units and divide by the total number of units that the power has. This is the n-incohesion for the power.

Under this scheme a low 1-cohesion (high 1-incohesion) would indicate a power that had units all over the place. A high 1-cohesion would indicate that the units formed some sort of cohesive structure. Assuming the 2-cohesion was high (which it probably would be for a high 1-cohesion), a high 3-cohesion would indicate a "blob" of units and a low 3-cohesion would indicate a linear structure. There may be times when each of linear and blob like structures would be good. This doesn't attempt to determine that but seeks to determine if a particular structure has been achieved.

Stab Potential

This measure, suggested by Tarzan, and fleshed out by Andrew, seeks to determine how susceptible a player is to a stab.

The likelihood of player A being stabbed by player B is the number of supply centres that player A owns that player B has a unit closer to than player A.

This measure is always a whole number of varies between 0 and the number of supply centres that the player has at the time.

Battle-Tied

There are times in the game when a player is relatively free to expand and times when they are heavily involved in a battle. This measure, suggested by Andrew, seeks to measure how battle-tied a player is.

A player's level of 'battle-tiedness' is the number of units owned by the player that border an enemy unit, divided by the total number of units that the player owns.

This measure is a strict percentage.

Neighbour Effect

Whilst not strictly a primitive measure, this effect, noted by Tarzan, observes that a player's position is stregthened if he is surrounded by players in a weak position and weakened if he is surrounded by players in a strong position.