LinuxOnly

Implementations

Ataxxlet

This game has two types of computer players: AtaxxMoron and AtaxxPaul. I will only cover AtaxxPaul here, because AtaxxMoron doesn't seem smart at all.

AtaxxPaul has a fancy heuristic. I will first give the whole heuristic and then explain all variables and how it works:

Obviously, Buchheit finds it important to let the pieces stick together. The variable enemyGoNear is the number of enemy pieces surrounding the destination of the move. These pieces will be turned black if the move is done. The variable selfGoNear is the number of own pieces surrounding the destination of the move. As this is less important, it is multiplied by goNearCoef (coefficient), which is set to 0.2. selfGoAway is the number of own pieces surrounding the original location of the piece which is moved. It is multiplied by goAwayCoef, which is normally also 0.2. This line only kicks in when there is a jump, because then other pieces are left behind. The next line adds 1 for a normal move and the last line adds 0.05 if the destination of the move is near the edge of the board.

This heuristic has some new features. It results in higher scores

• if a move is made with many enemy stones surrounding it;
• if a move is made with many own stones surrounding it;
• if a normal move is made instead of a jump;
• if the original location of a jump move surrounds few own stones;
• if the destination location of a move is adjacent to the edge of the board.

Choosing the best move is here implemented in the heuristic. There is no real algorithm. The computer player just chooses the move resulting in the highest score.

What is exceptional about this heuristic is that it evaluates moves instead of boards. The heuristics named a few chapters earlier were all about board states. This heuristic however, gives scores to individual moves and does not actually do the move to get a new board.

KVirus is a C++ KDE port of Ataxxlet, and essentially the same.

SwingAtaxx

The algorithm this program uses is really simple. The heuristic is the number of pieces won by the move. It then chooses the best move out of all possible moves.

It is not very smart to look at the pieces won, because then a jump move and a normal move to the same spot have the same score. A better heuristic is the total number of own pieces.

Furthermore, if multiple moves with the same score are found, this is the code to pick one randomly, executed for each move with the highest score:
if ((int)(Math.random()*2) == 1) bestMove = allMoves[i];
This gives a 50% chance that of all valid moves, the last one is chosen. This gives predictable results and should be avoided.

Hexxagon

This is ataxx with a hexagonal board. It uses the following heuristic:

Hexxagon lets you choose the search depth and a maximum search time. Search time varies as follows:

Gataxx

Gataxx has three difficulty options, of which level three is the hardest. I will try to explain level three.

First something else. The AI code of gataxx is a mess. There is very little comment in the source files. Furthermore, variable names as tmp, tmp1 and tmp2 are not exactly descriptive. 6 layers of nested if and for statements are not really neat.

Gataxx works with a heuristic, adds the moves with the highest score to an array and then randomly select one. It really picks a random move, unlike some other programs, which randomly add best moves to the array. Randomly adding moves gives problems, because you do not know how many moves there will be and there has to be at least one in the array. Randomly selecting one from a array with all the moves is a better strategy, but requires more coding and memory.

The heuristic that gataxx uses is really special. It does not bases the score only on the board which results after this move, but also uses the boards which result after one extra step.
Here is some pseudo-code which resembles the heuristic:

function heuristic(board) {
	foreach(hisMoves) {
		t2Board=doMove(tBoard);
		if (count(hisPieces) >= maxPieces) {
			maxPieces=count(hisPieces);
			if (count(myPieces) < maxWhite) {
				maxWhite=count(myPieces);
			}
		}
	}
	score=maxWhite-maxPieces;
	return score;
}

The variable maxPieces becomes the maximum of enemy pieces, after one move. maxWhite becomes the minimum of own pieces, reachable with one such move. The score kind of resembles count(myPieces) - count(hisPieces) in the worst-case scenario.

This algorithm resembles minimax, but it isn't quite the same. First, the heuristic explained above does not search for the lowest count(myPieces) - count(hisPieces), but searches for the highest count(hisPieces) and only then picks the one with the lowest count(myPieces). Furthermore, it is far harder to implement.