LinuxOnly

Ataxx

Introduction

When I had a programming exercise at the university a few weeks ago, the task assignments where not as clear as they had to be and I had a lot of free time while I was in the computer room. It was then that I discovered gataxx, the ataxx game for gnome. After a few tries I was able to win of the computer, even with the highest level. A friend of me suggested that I looked into a better algorithm for ataxx, so I did and this document is the result of that.

First I will briefly describe what kind of game ataxx is, and what kind of variations there exist. Secondly I will explain some heuristics, which are important for the algorithms that I will discuss next. The state space of ataxx is big and I will talk about how big it is and about some optimizations after this. Then I refer to some implementations of the game and how they handled the computer player. Finally I will conclude with a recommendation that will improve the computer player in gataxx.

Gataxx, where white is me and black is the computer player.

Game rules and variations

The game is played on a seven by seven board, as shown below:

There are two players. The first player has white stones and the second player has black stones. These stones are also called pieces or blobs in various documents, and of course the colors differ in various implementations. For the rest of this document, white is the human player and black the computer player, unless otherwise stated.

To accurately describe locations on the board I will use a coordinate system. (0,0) is the top-left corner. (6,6) is the lower right corner. The lower left corner is (0,6).

Each player gets two stones which are in opposite corners. The white stones are in (0,6) and (6,0) and the black stones in (0,0) and (6,6). The white player starts and can make one of two kinds of moves:

1. a normal move of 1 step, horizontal, vertical or diagonal. The original stone stays where it is, and another stone is added.
2. a jump move of 2 steps, horizontal, vertical or diagonal. The original stone is removed and put on another place.

If white moves a stone next to a black stone, all black stones next to this stone are turned white. This is the way to get many stones. The game has ended when all spots are taken by either black or with stones. When a player can not make a move his move passes and the other player can move again. One has won when one has the most stones at the end of the game.

Variations on ataxx

Hexxagon

Hexxagon has the same rules as ataxx, only it is played on a hexagonal board. This also means that there are just six boxes around one location, making acquiring pieces somewhat more difficult. A normal board has 5 boxes on one side, for a total of 61 boxes.

Blocks

Some implementations add blocks to the board: boxes where no pieces can be put. Blocks do not move, but the places where the blocks are can not be used by any piece. Most implementations put the blocks symmetrical around the center of the board.

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.

Algorithms

An algorithm chooses the best move out of some or all possible moves. It usually works by thinking what would happen if a move is done. It does that by examining the heuristic value of each board which results after a move.

First some graph theory: a node is a board state. The children of this node are all boards that can be reached in one move.

Minimax

Minimax is an algorithm for games with more as one player. It searches the states beneath the current one to a current depth. This depth is called the ply depth, and the computer "looks ahead" for this many moves.

Minimax tries to maximize the advantage for the current player, while minimizing the advantage for the other player. It assumes that the other player does the same.

When it is black's turn, he can choose the best move out of all possible moves. The moves resulting in bad states are therefore not relevant. However, when white is moving, it will probably pick the move that is best for him and hence, very bad for black. Then the good moves (for black, that is) don't matter as much.

In minimax, all heuristic values of the nodes on a certain ply depth are evaluated. These values are then traversed to the top in a particular way: if in this ply it is black's turn, the heuristic values of a node is the maximum of the node's below. If white is moving in this ply, the heuristic values of the nodes are the minimum of the node's below.

For all leaves (nodes on the maximum search depth):
h(n) = h₁(n)
where h₁(n) is a certain heuristic function for state n.
For all nodes where it is black's turn:
h(n) = MAX(child₁, child₂, ..., child_n)
For all nodes where it is white's turn:
h(n) = MIN(child₁, child₂, ..., child_n)

With the functions above, all board states have a heuristic value and the best move can be chosen.

A disadvantage of the minimax algorithm is that each board state has to be visited twice: one time to find its children and a second time to evaluate the heuristic value.

Alpha-beta pruning

Alpha-beta pruning is a optimized form of minimax. It is almost the same, except that it searches the state space in a depth-first search. This enables it to cleverly skip parts of the search tree.

For example, it could be that the computer has to calculate the following in order to evaluate a heuristic value for a node:
MIN(3, MAX(5, a))
Here the variable a is unknown, but that is not really a problem. MAX(5, a) is at least 5, and MIN(3, b) where b is 5 or more is just 3. Alpha-beta pruning thus skips the tree under a.

Optimizations

A normal game will take at least 49 moves, as the board has 49 boxes. Depending on the rules, games can take shorter if a player is surrounded by a layer of two other pieces, or if a player has no more pieces. Off course games can also take longer, because with a jump move pieces are only replaced. Therefore an ataxx game can go on forever. A normal game will last something around 68 steps, thus 34 steps per player.

Each time black has to think out a move, it has the choice of all possible moves. The number of possible moves lies somewhere between 0 and 100 in a normal game, but can be as much as 200. I don't believe more than 200 moves are possible, but I can not proof that. The average number of possible moves lies around 43, depending on your and the computers play style. If a player is in the advantage and thus has more stones, the number of possible moves for that player increase. To the end of the game, the number of possible moves decreases rapidly, because there are no more empty boxes.

200 possible moves

Let's take 43 as the average number of possible moves and 68 for the duration of the game in steps. That is a very big number. But then I mean a very big number. In the bottom level only are 43⁶⁸, which is about 10¹¹².

So lets restrain ourselves to a limited depth. A depth of five moves would already result in 150,508,644 boards to be examined. To look three moves ahead, however, is doable, as this takes only 81,400 boards to be examined. One board can be examined in a couple of hundreds of microseconds with modern computers, so to choose the best move would take in the order of 10 seconds.

Looking three moves ahead seems fine, but 10 seconds is still a bit slow. To decrease this number, one can do one of two things: decrease the search depth or decrease the number of possible moves. Decreasing the search depth to two makes decisions take less than a second, but makes the computer rather dumb. So here are some tactics on decreasing the number of possible moves.

Removing duplicates

Probably there is a method/function/procedure in every ataxx game which finds all possible moves. This method generally find out for every black piece in which empty box it can go. So there are no real duplicate moves.

However, there are moves that result in the same board. Whether one moves a piece from (0,0) to (0,1) or from (1,0) to (0,1) makes no difference. In both cases all pieces stay put, except there is an extra piece on (0,1). If you join these moves into one, or remove all but one move which result in the same board, the number of possible moves can be drastically reduced. The number of normal moves can not exceed the number of empty boxes, which is 45 at the start of the game.

Removing jumps

Of course there are also jumps, where it does matter where the move originated from. Here is also some optimization possible. A player would never make a jump move if a normal move to the same position is possible. After all, this adds an extra stone and leaves less room for the opponent. If a normal move can be done to the same place where to a jump can be done, the jump can be removed.

Removing low scores

Normally, search algorithms search all board states. However, one can safely assume that no player will make a move that is not in advantage to him. Furthermore, if he does make such a move, for example a jump move with no surrounding opponent pieces, it is no concern to the other player.

It is important that this function is implemented within the search algorithm. When the low scores are removed before the possible moves are passed to the search algorithm, each board is examined at least twice: one time to remove the boards with low scores, and one time within the search algorithm. This probably do more bad than good.

The effect of optimization

With the first two of above optimizations enabled (removing duplicate moves and removing jumps if a normal move is possible), the average number of possible moves is only 19. Now we have "only" a search space of somewhere near 10⁸⁷. This is still not searchable off course, but a depth of 3 now takes 7,240 boards instead of 81,400. This is a 1:11 improvement, so choosing a best move is now a matter of seconds. With some tuning and the right algorithm, a depth of 4 is now also reachable: 137,561 boards.

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.

How to improve gataxx

Here is do some suggestions for improving gataxx, in no particular order:

Possible moves

Currently, all computer-player functions find out on their own what moves can be done. A function should be made which finds all possible moves, with duplicates removed and no jumps if a normal move to the same spot is possible.

This should probably work as follows:

function getPossibleMoves(board, player) {
	foreach(empty box) {
		move=find_one_normal_move(board, player);
		if (move) {
			moveList.add(move);
		} else {
			moves=find_all_jump_moves(board, player);
			moveList.add(moves);
		}
	}
	return moveList;
}

To effectively process moves, it would be easy to make a move struct. There are two possibilities for such a struct. The first is making a position struct and combining two position structs to get a move struct:

struct pos {
	int x;
	int y;
}

struct move {
	struct pos from;
	struct pos to;
}

Provide for more and better levels

Currently, the levels are named level one, level two and level three. Maybe it is logical for the developer which one is the hardest, but this may not be clear to everyone. The levels should get names like:

1. learning
2. novice
3. intermediate
4. advanced
5. professional

Very easy should be for people learning the rules of the game. The computer makes a random move, more normal moves than jumps. Easy should pick the move with the highest score, with a heuristic based on the number of pieces. Hard and very hard should do alpha-beta pruning or minimax search. Medium can do either one of these or use a better heuristic than easy.

Code cleanup

The code of ataxx is messy, has no comment and is badly organized. It is difficult for others to read and understand. If you expect someone else to contribute to the source code, you should keep it nice and clean.

Split the AI from the rest of the program

Each AI algorithm needs some common functions, like one to get all possible moves and methods to alter the board and to get information about the current state. These functions should be in one file. Furthermore, the algorithms themselves should be in another separate file. This makes it easy to try out new algorithms and heuristics, because one has only one file to replace.

Conclusion

There are a variety of possibilities to make an ataxx game faster and better. Gataxx' code, however, is a mess and it should be cleaned up before anything else is done.

I would like to thank Rakesh Sewgolam, who proposed to improve gataxx when I complained it was so easy, and Maarten Staedler, who proposed to let the computer cheat once in a while.

The end