LinuxOnly

Heuristics

A heuristic is a formula that connects a score to each board. Usually, the score is higher when the odds are better for the current player. A winning board should have the highest score and a losing board the lowest score.

Heuristics are important for the computer player to decide which move it has to make. If there are two possible moves, the one resulting in a board state with the highest score will be chosen. This score is the heuristic value, determined by the heuristic.

Heuristics are fallible. There is no heuristic that gives the best moves the best scores. A heuristic is just a informed guess about how things are doing for the computer player. The more "smart", or informed, the heuristic is, the more time it will take to calculate the heuristic value for a board.

Heuristics are usually described as:
h(n) = heuristic value for state n
State n is in our case a particular board state, e.g. where the black and white pieces are located.

These are just some examples of heuristics, there are many more possible.

Number of black pieces

One of the most simple heuristics is
h(n) = count(black_pieces)
or white pieces, for that matter.

This heuristic is fairly easy to compute. However, in the game of ataxx, the number of stones can change very quickly (max. 8 stones in one move). This means that this heuristic is somewhat crude and does not give a very informed guess. As we shall see, this can be solved a bit by searching a bigger part of the state space.

This heuristic can be a bit modified by giving losing boards a very low number and winning boards a very high heuristic value. A losing board is a state destined to be lost by the computer player, usually just before the game is over. This avoids committing suicide by choosing a losing combination.

Number of black pieces minus number of white pieces

This heuristic also considers how the opponent is doing:
h(n) = count(black_pieces) - count(white_pieces)

This seems like a better heuristic, for marginal higher costs, but most algorithms which use heuristics also consider the opponents move, so that this addition is not really needed.

Extra score for surrounded pieces

Black pieces surrounded on all sides by other black pieces are hard for the opponent to take over. If there is a border of two pieces around a particular piece, it is even harder.
h(n) = count(black_pieces) + a * pieces_with_border(1, black) + b * pieces_with_border(2, black)
a and b are constants with values that are either experimentally found or figured out by the program itself.
Rakesh came up with a nice idea: to randomly alter the constants a bit so that the playing style is different every time. This avoids predictable moves.

This heuristic may make the computer player smarter, or it may not. With more complex functions it is often hard to see if it works out OK.