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 AlphaBeta call tree, several techniques can be used. This article presents a combination of those techniques: Iterative Deepening AlphaBeta Pruning (for Negamax); Transposition Table; Move Ordering; and NullMove 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 AlphaBeta call tree, several techniques can be used. This paper presents a combination of those techniques:
 Iterative Deepening AlphaBeta Pruning (for Negamax);
 Transposition Table;
 Move Ordering;
 NullMove Heuristic.
Alphabeta 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. Research and search speed improvements are done with transposition tables, move ordering (in order to provide better AlphaBeta 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 pregenerated, 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 objectoriented architecture as simple as possible; even avoiding it is recommended for the realtime 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 (realtime) 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 pseudocode (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 += (8Row) * PieceDangerValue;
Value += Piece.ValidMoves.Count;
return Value;
}
Search Algorithm / Heuristics
Overview
Search algorithm for the system was built on the basis of Negamax AlphaBeta search, enhanced with:
 IterativeDeepening in order to have control of the execution duration;
 Transposition table (required for faster research of ID Alpha Beta);
 Complete move ordering;
 Nullmove forward pruning heuristic.
IterativeDeepening AlphaBeta
Since the the depth first methodology is not suitable for timeconstraints, the Negamax AlphaBeta search was enhanced with iterativedeepening. Therefore, to facilitate research on each level, the transposition table would be necessary.
The following pseudocode illustrates the approach. We can see that the transposition table is cleared in the beginning of every move, and extensively used for research 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 (research 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 pseudorandom numbers. Pseudorandom 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 pseudorandom 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 highquality 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 alphabeta 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 pseudocode shows the ordering:
int AlphaBetaTT(...)
{
Successors = GetPossibleBoards(WhosMove, Board);
if (Total Successors == 0)
return Board.Value;
Successors.SortByValue();
}
Nullmove Heuristic
The algorithm was enhanced with Nullmove 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 pseudocode illustrates the NullMove 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 AlphaBeta with Negamax was compared to the presented approach. The AI Player was set to play black, the same move (White A2A3) 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:
PlyDepth

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 AlphaBeta 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 AlphaBeta and there is a lot of research that has already been done.
History
 5 June 2009  First version of the article.