Creating an algorithm like the Difference AI (see below) is
not very difficult, but it only looks a few moves ahead. That means
it is only able to make tactical decisions, especially on big boards, although
it is quite good at that. Adding strategical strength is a real challenge.
With Color Expansion, moving strategically would mean to move across the board as fast
as possible while keeping the opponent from doing so. Fast movement
will let you cut off groups of regions from the
opponent and it will increase the number of neutral regions within reach of your territory.
All the AIs that come with Java Color Expansion
calculate a number (equivalent to their level) of moves ahead,
evaluate every game state they can reach and pick the move that
should lead to the game state with the highest
value. Here's a description of the two AIs currently included in the program :
This AI tries to increase its territory as fast as possible while keeping the opponent from doing so.
The value of a game state is equal to
(size of the AI's territory) - (size of the opponent's territory)
Many neutral regions on the board are far
closer to one player's territory than to the other's. Going for a
region the opponent can conquer with a single move while you need
five moves to get there is a waste of effort. To account for this,
the Maze AI uses only the neutral regions for which the distance to
the player territories differs by less than two (other values are
possible and do not have a big impact on the algorithm's strength,
although when looking solely at regions with equal distance to both
player territories there will - very rarely - be game situations
where there is no region that meets the criterium). It marks these
regions before starting the look ahead algorithm. The value of a game state is equal to
(sum of the distances between the AI's territory and the marked regions)- (sum of the distances between the
opponent's territory and the marked regions)
The Maze AI algorithm is not very good at
tactical decisions, because it ignores the size of the regions.
That's why it uses the Difference AI algorithm for the last few
moves of a game, where tactical strength is all that matters.