2.1 Checkers

Checkers is a board game that is played on an 8x8 grid by two players. Each player starts the game with 12 "pawn" pieces. Pawns move towards the player's opponent diagonally one square at a time. A pawn may only occupy an unoccupied square. If a pawn makes it to the other side of the board then it is promoted to a "king". A king may move diagonally in any direction. If a king or a pawn wishes to make a move towards a square but the square is occupied by an opponent, and the square immediately beyond it in the same diagonal direction is unoccupied, then the moving piece may "capture" the opponent piece by removing it from the board. The player will then move their piece to the square immediately beyond the square of the capture piece. A game is over when a player captures all of their opponents pieces. For the purposes of this paper, a draw is defined as 20 moves from each player (40 total) without a promotion or a capture. More details about the rules of Checkers can be found on the International Draughts Federation website [11].

2.2 Checkers Engines

A Checkers engine is a computer program that is capable of playing the game of Checkers. The first Checkers engine to become World Champion by beating the best human player of Checkers was the Chinook Checkers engine. Chinook was developed by a team of researchers at the University of Alberta, and the team was led by Jonathan Schaeffer [1]. More recently, the best playing Checkers engines are the KingsRow engine by Ed Gilbert [4] and the Cake engine by Martin Fierz [2]. All three engines use some form of the Minimax search algorithm to help the engine find a winning move that can lead to a win against their opponent.

2.3 Minimax

The Minimax search algorithm relies on the fact that in an adversarial game like Checkers, a winning move for a player is an equally losing move for the opponent. At the heart of the algorithm is an evaluation function that determines how likely a given player is to win the game based on the layout of the pieces. The Chinook Checkers engine uses a hand-tuned evaluation function that was constructed over much trial and error. The KingsRow and Cake Checkers engine adopted Machine Learning constructed evaluation functions which outperformed their hand-tuned predecessors [3].

3.1 Language

The engine is implemented in the Rust programming language. Rust is a statically typed programming language with memory safety. The type system in Rust is very strong which allows for modeling complex data structures in compiler-checked abstractions. The strength of the type system and support for unit testing makes Rust a great language for complex software like a Checkers engine because the compiler will help notify you of errors before they happen at runtime. This lets you focus more on the bugs created from logical errors and not bugs created from typos.

3.2 Features and Optimizations

To explore the impact of changing features and optimizations to the Minimax algorithm, the Checkers engine I made is constructed to have the ability to run the Minimax algorithm in different states of configuration. Each feature or optimizations may be enabled or disabled. This allowed for greater flexibility when devising configurations to test for performance and ability to win.

3.3 Board Game

I created the Checkers board using a 46 element array [7]. Figure 1 is a visualization of the array indexes and their relationship to the playable diagonals of a Checkers board.

  37  38  39  40
32  33  34  35
  28  29  30  31
23  24  25  26
  19  20  21  22
14  15  16  17
  10  11  12  13
05  06  07  08

The padded array is used in this layout because diagonal moves can be calculated by using simple addition or subtraction without the need to check for array index bounds. For example, to check the surrounding squares for any given square position i, all that is required is to check i+4, i-4, i+5, and i-5.

3.4 Move Generation

Move generation is split into two phases. The first phase searches for capture moves. The rules of Checkers require the player to capture a piece if a capture is available. Therefore, these moves are generated first. If a capture exists, then the second phase of move generation is ignored. The second phase searches for single square movements (or, non-capturing moves).

3.5 Evaluation Function

An evaluation function takes as input the current state of the board and the current player searching for their next move. The function output is a signed integer which represents the ability to win given the player's pieces on the board. The engine I created can be configured to run one of three different evaluation functions. The first evaluation function (named v1) is the simplest. The pawns and kings for each player are summed separately. The result of the evaluation function is then: (MY_PAWNS - YOUR_PAWNS) + (3 * (MY_KINGS - YOUR_KINGS))

The second evaluation function (named v2) is a linear combination of 8 terms. Refer to the source code for a more thorough detail of the terms and their coefficients [9].

The third evaluation function (named v3) is a partial implementation of the evaluation function described by Arthur L. Samuel in his paper "Some Studies in Machine Learning Using the Game of Checkers" [14].

3.6 Negamax

Negamax is a simplification of Minimax and can be used as an easier to implement alternative to Minimax for a zero-sum game like Checkers. Because of this, the core algorithm used in my engine is Negamax, and the various features and optimization options of the engine are used to improve the base Negamax algorithm [5].

function negamax(board, player, depth) is
  moves <- board.movements(player)
  if moves.length() == 0 || depth == 0 then
    return evaluation(board, player)
  value <- -Infinity
  move <- None
  for m in moves do
    board.do_move(m)
    score <- negamax(board, player.other_player(), depth - 1)
    if score > value then
      value <- score
      move <- m
  return (value, move)

function getMove(board, player) is
  (score, move) <- negamax(board, player, depth)
  return move

3.7 Alpha-Beta Pruning

Alpha-Beta pruning has the same result as Negamax, but it ignores branches of the search that do not influence the result of the search [12]. This reduces the search space which has the effect of the search running much faster than the base Negamax algorithm.

function negamax(board, player, depth, alpha, beta) is
  moves <- board.movements(player)
  if moves.length() == 0 || depth == 0 then
    return evaluation(board, player)
  value <- -Infinity
  move <- None
  for m in moves do
    board.do_move(m)
    score <- negamax(board, player.other_player(), depth - 1, -beta, -alpha)
    if score > value then
      value <- score
      move <- m
      if value >= beta then
        break
    if alpha < value then
      alpha <- value
  return (value, move)

function getMove(board, player) is
  (score, move) <- negamax(board, player, depth, MIN, MAX)
  return move

3.8 Transposition Table

A transposition table allows previous board evaluations to be stored and reused, and thus eliminates the need to evaluate the same board position multiple times, further improving the time efficiency. A previous evaluation is only reused if it was evaluated at a depth that is equal to or deeper than the current depth of the search. If the evaluation was conducted at a shallower depth, the algorithm will try to reuse the evaluation calculation to narrow the search window [8].

Transposition table usage is a feature that can be toggled on or off in the engine. When the transposition table feature is enabled, then the Alpha-Beta pruning feature is also enabled by default.

function negamax(board, player, depth, alpha, beta) is
  alpha_orig <- alpha
  moves <- board.movements(player)
  if moves.length() == 0 || depth == 0 then
    return evaluation(board, player)
  entry <- ttable.get(board)
  if entry then
    if entry.depth >= depth then
      case entry.flag
      when Exact then
        return (entry.score, entry.movement)
      when Lowerbound then
        alpha <- max(alpha, entry.score)
      when Upperbound then
        beta <- min(beta, entry.score)
    if alpha >= beta then
      return (entry.score, entry.movement)
  ### (rest of normal negamax function body here) ###
  entry <- ttable.new_entry()
  entry.score <- value
  if value <= alpha_orig then
    entry.flag <- Upperbound
  elseif value >= beta then
    entry.flag <- Lowerbound
  else
    entry.flag <- Exact
  ttable.insert(board, entry)
  return (value, move)

A hash table is used to store the previous board evaluations. The hash algorithm used in the engine is the Zobrist hash algorithm [17]. This algorithm has great properties for board games as the hash can be updated during every state change (or player move). Given this property, when a transposition table lookup is required, the board's hash is already computed.

3.9 Quiescence Search

The horizon effect is when the search algorithm hits the end of its search, either by reaching a depth limit or some terminal state, but there exists a move just beyond the search limit that would greatly influence the state of the game. By stopping the search before this game-changing move, the resulting evaluation may give wildly inaccurate results. Quiescence search is used to mitigate the horizon effect [8]. In the engine there is a very basic quiescence search feature that can be toggled on or off. When enabled, if the search algorithm would otherwise stop, instead it looks at the next set of moves. If the moves are capture moves, then the search continues for at least one more iteration.

function negamax(board, player, depth, alpha, beta) is
  moves <- board.movements(player)
  if depth == 0 && moves.first().is_jump() then
    depth <- 1
  ### (rest of normal negamax function body here) ###

4.1 Description of Technique

I created a "Random Opponent" to select random moves from a list of valid moves. This opponent is used to run tests in order to have a simple baseline to compare the various engine features and optimizations against. The engine is capable of reporting a few metrics by outputting data to the terminal. For each player after each game is played:

• Moves - how many moves each player played.
• Explored - the total amount of moves explored in the search.
• Beta Cuts - the total times that Alpha-Beta pruning ended a search early.
• TT Exact - the total times that the Transposition Table used an exact match and ended a search early.
• TT Cuts - the total times that the Transposition Table was used to do Alpha-Beta pruning and ended a search early.
• Max Depth - the deepest level of search that happened at any point.

The engine can play multiple games and report the above metrics for each game to the terminal. I wrote a script that can accept the output of the Checkers engine and compute the averages of the game metrics [9]. Additionally, I used the macOS tool Instrument to profile debug builds of the engine in order to see how much time was spent in various parts of the code. I also used the Hyperfine command-line tool to profile the run-time of release builds of the engine in order to compare the impact of the various engine optimizations. In following analysis subsections, I use a shorthand to represent the various engine configurations that were tested:

• D - This represents the configured max depth to search. For example, D=6 means the search will stop at depth 6.
• E - This represents the configured evaluation function to use in the search. For example, E=2 means that the v2 evaluation function will be used.
• AB - This means the Alpha-Beta Pruning feature is enabled.
• Q - This means the Quiescence Search feature is enabled.
• TT - This means the Transposition Table feature is enabled.

For a full example, consider the configuration "AB, TT, Q, D=6, E=2". This configuration has Alpha-Beta Pruning, Transposition Table, and Quiescence Search enabled. The max depth is set to 6, and the v2 evaluation function is used.

4.2 Playing Against a Random Opponent

Marked in red, "D=6, E=1" performs the worst against the Random Opponent in terms of its ability to win games. This configuration also requires the most moves to finish a game.

Marked in red, "D=6, E=3" takes the most time to select a move. Other baseline engine configurations ("D=6, E=1" and "D=6, E=2") are very slow at move selection. The evaluation functions have a big impact on the time it takes to pick a move.

Marked in green, "AB, TT, D=6, E=1" is the fastest at selecting a move. However, the configuration lost a game against a Random Opponent, so it is not a very good configuration with regards to winning games.

Marked in green, "AB, TT, Q, D=6, E=3" requires the least amount of moves to win a game. This configuration also searches the deepest and utilizes the best evaluation function.

Marked in purple, "AB, D=6, E=3" compared to "AB, TT, D=6, E=3" is the first time we see a Transposition Table configuration outperform its Alpha-Beta Pruning counterpart. The v3 evaluation function is the best at determining a good board position, but it also seems to be the slowest. The caching of results in the Transposition Table helps to avoid the costly evaluation function.

All configurations in Table 2 have Alpha-Beta Pruning and Transposition Tables enabled. Given that they all have those features enabled, the configuration shorthand for those features is omitted.

"memmove" is a function call to "memcpy" which is part of the C standard library. This function copies memory from one location to another.

Function calls that start with "core" are either primitives of the Rust programming language, or they are function calls to standard library functions in the Rust programming language.

The first noticeable piece of information in this data is that move generation takes up a large portion of time in most configurations. On average, move generation accounts for about 15% of the runtime.

In configurations that use evaluation function v3, the evaluation function call dominates the runtime. In these configurations, we also see a significant increase in the runtime usage of "checkers::Board::get" and "core..slice..iter". The function call to "checkers::Board::get" retrieves an element from the board's padded array. The function call to "core..slice..iter" is related to iterators in Rust, which is a mechanism to iterate over various data structures in the Rust programming language. The evaluation function v3 accesses the elements of the board a lot more than the other evaluation functions.

4.3 Engine vs Engine

Marked in purple, "AB, TT, Q, D=8, E=1" hit a max depth of 15, yet it still lost to and explored less nodes than "AB, TT, D=7, E=3".

Marked in green, "AB, TT, D=6, E=1" vs "AB, TT, D=3, E=3" is where we see the v1 evaluation function beat the v3 evaluation function. At a depth of 3, "AB, TT, D=3, E=3" did not explore many nodes. It's not surprising that this configuration lost to "AB, TT, D=6, E=1".

Marked in yellow, "AB, TT, D=12, E=1" vs "AB, TT, D=6, E=3" ends in a draw. This configuration was picked to see if exploring a lot more nodes was the reason for v1 evaluation functions win in the previously discussed configuration. It seems that the answer is no. "AB, TT, D=12, E=1" explores over 40 times more nodes than "AB, TT, D=6, E=3", but it's not enough to find a win.

4.4 Playing Against a Human

The most noticeable difference in play against the Checkers engine is when using different evaluation functions. All evaluation functions have an ability to find great moves in the opening states of the game. As the game progresses, the v1 and v2 evaluation functions begin to make undesirable moves. The v3 evaluation function continues to make good moves, especially when it comes to forcing the opponent to make a capture which puts the engine in a position to make a multi-capture move. All evaluation functions fail to find good moves near the end of the game. It was common for the engine to move one piece back and forth at the end of the game until the opponent forces a different move via threat of capture or force of capture. If the v2 and v3 evaluation functions remove enough pieces from their opponent at the start of the game, they are good enough to force the opponent into a draw, but not good enough to force a win.

5.1 Bitboards

The slowest aspects of the engine (move generation and evaluation function) have a lot to do with the underlying data structure that is used (a padded array). Bitboards are an extremely common solution to this performance bottleneck. The idea of a bitboard is to codify positions of pieces into the bits of unsigned 32-bit integers. Then, using bitwise operators, you can generate moves or evaluate board positions in an evaluation function. The performance gain comes from using bitwise operators to find whole-board information instead of iterating through each item of an array [7].

5.2 ML Evaluation Function

Fine tuning an evaluation function by hand is difficult and time consuming. There are many more metrics even beyond the ones I employed that could have been used to improve the linear combination of the most advanced evaluation function currently in the engine. However, the best Checkers engines today use Machine Learning to generate superior evaluation functions [3]. So for a future iteration of this project, I would replace the current evaluation functions with Machine Learning generated evaluation functions because it would perform much better than any hand-tuned evaluation function I could create.

5.3 MTD(f) and BNS

As seen with Alpha-Beta Pruning and Transposition Tables, smaller search windows allow you to search deeper and faster. Two modern optimizations to Minimax searching are MTD(f) [10] and BNS [13]. They can enable the engine to search much deeper without too much change to the Minimax algorithm. Both algorithms utilize previous search results to inform the current search with regards to shrinking the search window.