Background :
Knoughty was written as a simple demonstration of the alpha-beta search algorithm. Because noughts and crosses is a simple game, a perfect alpha-beta search is possible and can also be done very quickly (on my Palm Zire 72, it only takes a fraction of a second to make each move.) I have written the program much like a chess program (with functions for move generation, evaluation and searching as well as a simple bitboard board representation) and I think it is a good place to start when planning to write your first chess (or any other board game) program.
And how does it work?
First a note: the snippets of code shown will be in C/C++, but it shouldn’t be too difficult to follow if you’re used to a different language. I will also use a bit of Boolean algebra, click here for an introduction of the subject.
Move generation:
Knoughty uses a simple bitboard approach to represent moves. The board is defined as follows:
struct position
{
int side; //side to move
int board[2]; //occupied places
}
You will notice that the board is comprised of two integers. The one is to represent the positions of the noughts and the other one is for the crosses. At start of play, both boards equals zero. When a player makes a move, a specific bit of the board (say board[0] for noughts and board[1] for crosses) is set. The setting of the bits work as follows: The board is numbered as follows: 678 345 012 If a player makes a cross on position 0, we set bit number 0 (the Least Significant Bit) of the board to one (e.g. board[0]=000000001b). If the opponent now makes a knot on position 4, we set bit number 4 to one (board[1]=000010000b). If the first player now makes a cross on position 2, we also set bit 2 of the cross board (board[0]=0000000101b). This will go on until the game is finished.
Evaluation:
Knoughty knows all possible 3-in-a-row winning combinations, they are declared as follows:
Int threeInRow[8] =
{
0x007,0x038,0x1c0, //3 in a row – horizontal
0x049,0x092,0x124, //3 in a row – vertical
0x111,0x054 //2 diagonal
}
To know if a side is winning, it simply AND the board of that side with all the possible winning combinations. If the resulting board equals the winning combination, it knows that there are 3 in a row and returns a winning score, e.g. If there is a cross on positions: 0,4,5 and 8 (board[0]=100110001b) First it tries threeInRow[0]: threeInRow[0] AND board[0] = 000000111b AND 100110001b = 000000001b 000000001b does not equal threeInRow[0], thus it tries the next winning combination. This will keep on until it gets to the second last combination (threeInRow[6]): threeInRow[6] AND board[0] = 100010001b AND 100110001b = 100010001b 100010001b equals threeInRow[6], thus it returns a winning score.
The “brain”:
Knoughty uses the alpha-beta algorithm to decide what move to play. Because there is no winning or losing move to start with, the first is decided on by random (just to make things a bit more interesting). It can be very rewarding to play around with the alpha-beta algorithm and see the effect of small changes. Some ideas to try: · First make a function to show the number of nodes searched (tip: add a counter to the “makeNextMove” function) · Change the search to Minimax and see the nodes searched increasing! (Tip: remove the line: “if (value>=beta) return value;”) · To see more drastic results, remove the code that make a random move and let it also search the first move.
And that’s about it! Feel free to play with the source code and maybe even turn it into a chess program!