Click here to Skip to main content
Click here to Skip to main content

Simple AI for the Game of Breakthrough

, 5 Jun 2009
Rate this:
Please Sign up or sign in to vote.
This article presents an implementation of a simple alpha-beta player for the board game of Breakthrough.

screen.jpg

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.

schema.jpg

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:

formula.jpg

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) // almost win
                board.Value += PieceAlmostWinValue;
            } else{
                // Same for black, with inverted signs for NegaMax
            }
        }
        if (WhitePiecesOnColumn == 0)Value -= PieceColumnHoleValue;
        if (BlackPiecesOnColumn == 0)Value += PieceColumnHoleValue;
    }
    // if no more material available
    if (RemainingWhitePieces == 0) board.BlackWins = true; 
    if (RemainingBlackPieces == 0) board.WhiteWins = true;

    // winning positions
    if (board.WhiteWins)Value += WinValue;
    if (board.BlackWins)Value -= WinValue;
}

int GetPieceValue(square, Column, Row)
{
    int Value = PieceValue;
    var Piece = square.CurrentPiece;
    
    // add connections value
    if (Piece.ConnectedH) Value += PieceConnectionHValue;
    if (Piece.ConnectedV) Value += PieceConnectionVValue;

    // add to the value the protected value
    Value += Piece.ProtectedValue;

    // evaluate attack
    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;
            }
        }
    }
    // danger value
    if (Piece.PieceColor ==White)
        Value += Row * PieceDangerValue;
    else
        Value += (8-Row) * PieceDangerValue;

    // mobility feature
    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)
{
    //Empty the Transposition Table
    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; // timeout
        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;

      // sort the boards in order to have better pruning
      Successors.SortByValue();

      //continue with normal Alpha-Beta ...
}

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) 
{
          //  (...) Transposition table ...

          if (Depth >= 2 && Beta < Infinity && 
                        AllowNullMove && Board.Pieces > 10) {
              // Try null move
              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;
              }
          }

          // (...) Move ordering & Alpha-Beta ...
}

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%

results.jpg

results2.jpg

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.

License

This article, along with any associated source code and files, is licensed under The GNU Lesser General Public License (LGPLv3)

About the Author

Kel_
Chief Technology Officer Misakai Ltd.
Ireland Ireland
Roman Atachiants is the guy behind www.spike-engine.com project, a real-time, client-server networking layer (SOA, RPC) for .NET developers. Also the founder of Misakai Ltd..
 
He is a software engineer and scientist with extensive experience in different computer science domains, programming languages/principles/patterns & frameworks.
 
His main expertise consists of C# and .NET platform, game technologies, cloud, human-computer interaction, big data and artificial intelligence. He has an extensive programming knowledge and R&D expertise.

 
Follow on   Twitter

Comments and Discussions

 
GeneralTechnique to improve AI PinmemberBill West10-Jun-09 15:13 
GeneralRe: Technique to improve AI PinmemberRoman Atachiants11-Jun-09 0:18 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140709.1 | Last Updated 5 Jun 2009
Article Copyright 2009 by Kel_
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid