Introduction
Breakthrough presents an interesting challenge for an AI Player since the game consists only of a single type of figure; therefore, the game is based on deep tactics and deep search for an AI Player. In order to build a deep search with an Alpha-Beta call tree, several techniques can be used. This article presents a combination of those techniques: Iterative Deepening Alpha-Beta Pruning (for Negamax); Transposition Table; Move Ordering; and Null-Move Heuristic. It presents several techniques for building an efficient .NET board game engine, an evaluation function for the game of Breakthrough.
This article presents only a prototype of such a program, so it's far from perfect. Parts of the graphical user interface and the engine were built on top of the ChessBin starter kit: http://www.chessbin.com.
Background
Breakthrough is an abstract strategy board game invented by Dan Troyka. It won the 2001 8x8 Game Design Competition, even though the game is trivially extendable to larger board sizes. This paper presents an implementation of this game for an 8x8 board with an AI Player.
The game is played on a square board, initially similar to checkers; the first two rows are filled with pawns. A player to play first is chosen, and then the players alternate their moves.
A piece may move one space straight or diagonally forward if the target square is empty. A piece may move into a square containing an opponent's piece if and only if that square is one step diagonally forward. The opponent's piece is removed and the player's piece replaces it.
The first player to reach the opponent's home row, the one farthest from the player, is the winner. A draw is impossible since pieces can only move ahead (or be captured), and some pieces always have at least one forward diagonal move available.
For more information on the Breakthrough game: http://en.wikipedia.org/wiki/Breakthrough_(board_game).
AI Player
Breakthrough presents an interesting challenge for an AI Player since the game consists only of a single type of figure; therefore, the game is based on deep tactics and deep search for an AI Player. In order to build deep search with an Alpha-Beta call tree, several techniques can be used. This paper presents a combination of those techniques:
- Iterative Deepening Alpha-Beta Pruning (for Negamax);
- Transposition Table;
- Move Ordering;
- Null-Move Heuristic.
Alpha-beta pruning is a search algorithm with reduction of the number of nodes to evaluate in the search tree. The algorithm is very common, and used in a lot of different board game machine playing engines. Iterative Deepening Enhancement allows the search algorithm to handle time constraints. Re-search and search speed improvements are done with transposition tables, move ordering (in order to provide better Alpha-Beta pruning), and Null Move Heuristic (speeds the Negamax algorithm by identifying cutoffs, points in the game tree where the current position is so good for the side to move that the best play by the other side would have avoided it).
Engine Architecture
The Breakthrough engine was built in two clearly separated layers:
- the engine itself, containing all game algorithms, board representation, and evaluation function;
- the graphical user interface, used for user input and visualization.
The board representation is implemented in a very straightforward way: a board class to represent current positions; a board square for the square state representation; and a game piece for storing the values of the game. Moves are pre-generated, and valid moves are computed in order to facilitate and make the move selection process more efficient.
The Breakthrough game engine was built on the .NET platform (running on Windows with Microsoft .NET and on Linux/Mac with Mono .NET). In order to build an engine as efficient as possible, several software optimizations have been considered:
- a board representation in a simple one dimensional array (therefore, 64 board squares for an 8x8 board) with a fast copy of a board in order to generate faster moves (simple chunk copy);
- the object-oriented architecture as simple as possible; even avoiding it is recommended for the real-time constraints, therefore almost everything was done with static methods;
- the visibility modifiers changed to
internal
and private
wherever possible, allowing the CLR compiler to inline as much as possible; - analyzing the complexity of intensive (real-time) sections in order to simplify the implementation (e.g., the possible boards/moves generation, board copying, values assignments).
With those optimizations, some significant improvements have been achieved and 40% search improvement has been measured.
Evaluation Function
The evaluation function is used to evaluate the state of the board in order to compare different possible movements. The function built into the system is linear, and can be described with the following formula:
Where:
- s is the board square state;
- f is the feature;
- n is number of squares (64 for the 8x8 board);
- m is the number of features in the evaluation function;
- v(b) is the value of the board;
- v(f)|s is the value of a feature, given the board square state.
The features used in order to implement the current evaluation function:
Feature Name
| Feature Role/Description
|
Winning Position
| Feature that valorizes a winning position. In Breakthrough, the winning position is simply detected by a position of a pawn on the opponent's farthest row (e.g., black pawn on a row 1).
|
Piece Almost Win Value
| Feature that predicts a winning position in P - 1 moves (by looking on the three next possible moves).
|
Piece Value
| Feature that valorizes a piece/pawn on board
|
Piece Danger Value
| Positional value of a piece, following the formula: row * danger_value, symmetrically for black and white players.
|
Piece High Danger Value
| Feature for highest danger value of a piece, for a piece on a last row - 1.
|
Piece Attack Value
| This value weights an attack on a pawn, cumulative.
|
Piece Protection Value
| This value weights a protection of a pawn, cumulative.
|
Connection Horizontal
| Feature that characterizes a two pawns horizontal connection.
|
Connection Vertical
| Feature that characterizes a two pawns vertical connection.
|
Piece Mobility Value
| Feature that valorizes the number of valid moves for a piece.
|
Column Hole Value
| Feature that penalizes the columns where no player's pawns are present (empty columns).
|
Home Ground Value
| Feature that valorizes the pawns on the initial home ground row.
|
Following is a pseudo-code (simplified C# code) for the implementation of the evaluation function. The implementation within the system was split into two functions for easier readability:
int GetValue(board, ColorMoving){
for (byte x= 0; x < 8; x++){
for (byte y = 0; y< 8; y++){
BoardSquare square = board. GetPosition(x,y);
if (NoPieceOnSquare) continue;
if (square.CurrentPiece.PieceColor ==White)
{
Value += GetPieceValue(square, x, y);
if(y ==7)board.WhiteWins = true;
if(y == 0)Value += HomeGroundValue;
if (column > 0) ThreatA = (board[GetPosition(y - 1, 7).NoPieceOnSquare);
if (column < 7) ThreatB = (board.GetPosition(y + 1, 7).NoPieceOnSquare);
if (ThreatA && ThreatB)
board.Value += PieceAlmostWinValue;
} else{
}
}
if (WhitePiecesOnColumn == 0)Value -= PieceColumnHoleValue;
if (BlackPiecesOnColumn == 0)Value += PieceColumnHoleValue;
}
if (RemainingWhitePieces == 0) board.BlackWins = true;
if (RemainingBlackPieces == 0) board.WhiteWins = true;
if (board.WhiteWins)Value += WinValue;
if (board.BlackWins)Value -= WinValue;
}
int GetPieceValue(square, Column, Row)
{
int Value = PieceValue;
var Piece = square.CurrentPiece;
if (Piece.ConnectedH) Value += PieceConnectionHValue;
if (Piece.ConnectedV) Value += PieceConnectionVValue;
Value += Piece.ProtectedValue;
if (Piece.AttackedValue > 0)
{
Value -= Piece.AttackedValue;
if (Piece.ProtectedValue == 0)
Value -= Piece.AttackedValue;
}else{
if (Piece.ProtectedValue != 0){
if (Piece.PieceColor == White){
if (Row == 5) Value += PieceDangerValue;
else if (Row == 6) Value += PieceHighDangerValue;
}else{
if (Row == 2) Value += PieceDangerValue;
else if (Row == 1) Value += PieceHighDangerValue;
}
}
}
if (Piece.PieceColor ==White)
Value += Row * PieceDangerValue;
else
Value += (8-Row) * PieceDangerValue;
Value += Piece.ValidMoves.Count;
return Value;
}
Search Algorithm / Heuristics
Overview
Search algorithm for the system was built on the basis of Negamax Alpha-Beta search, enhanced with:
- Iterative-Deepening in order to have control of the execution duration;
- Transposition table (required for faster re-search of ID Alpha Beta);
- Complete move ordering;
- Null-move forward pruning heuristic.
Iterative-Deepening Alpha-Beta
Since the the depth first methodology is not suitable for time-constraints, the Negamax Alpha-Beta search was enhanced with iterative-deepening. Therefore, to facilitate re-search on each level, the transposition table would be necessary.
The following pseudo-code illustrates the approach. We can see that the transposition table is cleared in the beginning of every move, and extensively used for re-search on each level:
Board IterativeDeepeningAlphaBeta(Board, MaxDepth, WhosMove)
{
TT.Table = new TranspositionTable();
Depth = 1;
Watch.Reset();
Watch.Start();
for (Depth = 1; Depth < MaxDepth; Depth++)
{
LastBoard = AlphaBetaTTRoot(Board, Depth, WhosMove, EnableNullMoves);
if (Watch.ElapsedMilliseconds >= TimeToMoveMs || LastBoard == null)
break;
BestBoard = LastBoard;
}
Watch.Stop();
return BestBoard;
}
Transposition Table
In Breakthrough, the transposition table proved to be very effective for detecting duplicate positions as well as for Iterative Deepening (re-search is almost done instantaneously).
Zobrist hashing was used in the algorithm in order to create the transposition table. According to original research, the better the random generated numbers are, the better would be the actual distribution and collisions could be avoided. The engine was built in C#, which offers a way to generate pseudo-random numbers. Pseudo-random numbers are chosen with equal probability from a finite set of numbers. The chosen numbers are not completely random because a definite mathematical algorithm is used to select them, but they are sufficiently random for practical purposes.
However, to ensure better quality of random number distribution, the Zobrist hashing was enhanced with the Mersenne Twister pseudo-random number generator, developed in 1997 by Makoto Matsumoto and Takuji Nishimura, that is based on a matrix linear recurrence over a finite binary field. It provides for fast generation of very high-quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms. It is designed with consideration on the flaws of various existing generators.
Complete Move Ordering
In order to increase the pruning for alpha-beta algorithm, a move ordering technique was used. Since the evaluation function itself was designed in the simplest and most efficient way, the move ordering was done completely by retrieving all possible boards and sorting them by the value. The following pseudo-code shows the ordering:
int AlphaBetaTT(...)
{
Successors = GetPossibleBoards(WhosMove, Board);
if (Total Successors == 0)
return Board.Value;
Successors.SortByValue();
}
Null-move Heuristic
The algorithm was enhanced with Null-move forward pruning heuristic, greatly improving the depth of search. In order to avoid Zugzwang positions, several restrictions were implemented to the algorithm:
- the side to move has a small number of pieces remaining;
- the previous move in the search was also a null move.
The following pseudo-code illustrates the Null-Move approach for Breakthrough:
int AlphaBetaTT(Board, Depth, Alpha, Beta, WhosMove, AllowNullMove)
{
if (Depth >= 2 && Beta < Infinity &&
AllowNullMove && Board.Pieces > 10) {
int r = 1;
if (Depth >= 4) r = 2;
else if (Depth >= 7) r = 3;
Board.MakeNullMove();
int value = -AlphaBetaTT(Board, Depth - r - 1, -Beta,
-Beta + 1, WhosMove, false);
Board.UnmakeNullMove();
if (value >= Beta) {
TT.StoreEntry(HashValue, value,Upperbound, Depth);
return value;
}
}
}
Results
In order to evaluate the search improvement made with the algorithm presented in the paper, a simple Alpha-Beta with Negamax was compared to the presented approach. The AI Player was set to play black, the same move (White A2-A3) from the initial position was done, and the AI Player performed a search with a different depth. Times and number of nodes searched were measured.
Below is the table with the results measured for a different depth of search. A1 is a simple search algorithm, and A2 is an enhanced one:
Ply-Depth
| A1 - Nodes
| A1 - Time
| A2 - Nodes
| A2 - Time
| Nodes Impr.
| Time Impr.
| Cutoffs Impr.
|
2
| 192
| 12
| 25
| 29
| 167
| -17
| 86,98%
|
3
| 1152
| 59
| 115
| 58
| 1037
| 1
| 90,02%
|
4
| 12389
| 358
| 526
| 225
| 11863
| 133
| 95,75%
|
5
| 77288
| 3502
| 2564
| 837
| 74724
| 2665
| 96,68%
|
6
| 804367
| 23152
| 3568
| 1090
| 800799
| 22062
| 99,56%
|
7
| 5751094
| 245487
| 62536
| 22491
| 5688558
| 222996
| 98,91%
|
Conclusions
Transposition table, null moves heuristic, and move ordering significantly improve the search depth in a game of Breakthrough, where tactics and strategies are most important. The experiments have shown that complete move ordering with a simple Alpha-Beta pruning is possible, and the system achieved 99+% cutoffs within a reasonable time.
In order to achieve even better results, the parallelization of the algorithm can be done, especially since the algorithm conforms to a standard Alpha-Beta and there is a lot of research that has already been done.
History
- 5 June 2009 - First version of the article.