MINIMAX Checkers

DEMOLISH your opponents (efficiently)!

Overview

Game section: tutorial on piece names and game rules
Math section: counts the number of valid game states and defines game trees
Algorithm section: explains how the MiniMax algorithm searches the checkers game tree
Optimization section: explains how to optimize using depth limits and alpha-beta pruning

Game

Rules

American checkers or English Draughts (pronounced "drafts") is fairly simple to learn. Elegantly implemented algorithms for it can be computationally inexpensive to run.

Checkers move diagonally, from a black square to another diagonally adjacent black square
At first, checkers can only move diagonally forward, but if a piece reaches the other side of the board it becomes a super* and can then move diagonally backward as well
Pieces diagonally adjacent to enemy pieces can be jump the enemy pieces provided the square behind the jumped piece is unoccupied; the jumped piece is then captured and collected
Multiple jumps can be made in a single turn by a single piece as long as they are consecutive

* While sometimes referred to as kings, we will refer to pieces that have reached the opposite end of the board and move diagonally forward and backward as supers in this project for gender neutrality

Possible Moves

A checker has two possible moves unless:

Tiles diagonally adjacent and in front of the it are blocked by other pieces ( -1 or -2 moves)
It is at the right or left edge of the board (-1 move)
It can make one or more jumps (+ j moves)

A super has four possible moves unless:

Tiles diagonally adjacent to it, in front or back, are blocked by other pieces (-1 to -4 moves)
At the top, bottom, right, left edge of the board (-1 to -3 moves)
It can make one or more jumps (+ j moves)

Math

Game Complexity

According to Jonathan Schaeffer and Robert Lake's "Solving the Game of Checkers" [1]:

Space complexity: the number of positions in the search space

Decision complexity: the difficulty required to make correct decisions

Checkers is bound on a maximum space complexity of 5^32 because it has 32 playable squares with 5 possible states: occupied by a blue checker, a blue super, a red checker, a red super, or empty.

B = number of blue supers

b = number of blue checkers

R = number of red supers

r = number of red checkers

f = number of blue checkers on the first row

With the conditions that:

Possible positions for supers: 32

Possible positions for checkers: 28

Function of game pieces

Take inputs r, R, b, B, and f and calculate the number of valid game states with those parameters:

Explanation of the terms

Find the number of possible ways for f to occur, meaning the number of blue checkers that are placed in row 1 (which has 4 tiles that could possibly be occupied).
Find the valid positions for b-f blue checkers, given that 4 positions are "reserved" for f blue checkers in row 1. There are a total of 24 positions the remaining blue checkers can occupy.
Find the number of positions that r red checkers can occupy, given that red checkers can occupy tiles besides those in the first row (as they'd be turned into supers) and those already occupied by the b-f blue checkers not positioned in the first row.
Find the positions B blue supers can occupy, given that b positions are already occupied by blue checkers and r positions are already occupied by red checkers.
Find the positions R red supers can occupy, given that there are 32 total legal positions - B - r - b positions that are already occupied by blue supers, blue checkers, and red checkers.

Since all of these positions can happen at once (as we subtracted from the total any impossible cases as we considered each possibility) we multiply the ways that each piece could occupy valid tiles to get the total number of ways exactly r, R, b, B, and f pieces could legally occupy tiles on the board.

Full Equation

Since r, R, b, B, and f could be a range of values, the cases where each variable equals a value within each range need to be considered and added to the total number of valid game states. The total number of valid game states for a game of checkers with n or fewer pieces on the board is given by:

* The -1 at the end accounts for the case when b, B, r, R, and f are all equal to zero (meaning there are no pieces on the board at all).Note: though these are valid game states, they are not necessarily playable ones (ex: although there is no rule making it invalid for 12 blue supers to exist on the board, there is no way to play a game so that ends up happening), so this calculation of possibilities still overestimates.

For the case of n = up to 24 checkers on the board, that adds up to a total of 5.01×10^20 valid game states.

So what does this mean?

It means an algorithm that works extremely efficiently will be needed to consider the most useful moves without exploring too many possibilities, as checkers has a high space complexity according to the estimate described above.

Game Tree

A game tree is a directed graph whose nodes are game states and whose edges are moves. Its nodes can be traversed to show possible game states and their associated metrics. As the tree is traversed, its levels alternate between players; that is, if the first level represents the moves that can be made by blue, the second represents the moves that can be made by red.

The figure above shows a game tree of mini-checkers with a depth of 2 moves. Red has four possible first moves, then blue has three possible follow-up moves to each red move, a total of 12 possible game states at two moves into the future.

In the following sections, we will explain how to the MiniMax algorithm works on the checkers game tree to find the best move, then explain some optimizations allowing us to reduce how much of the game tree we need to search.

Algorithm

Metrics

Depth - the number of turns ahead at which the score is computed

Score - maximize on red pieces and minimize on blue pieces using:

MiniMax

The main goal of the MiniMax (minimizer-maximizer) algorithm is to play through all possible iterations (to all possible outcomes). This approach accounts for each players' best interest in the moves via a decision tree.
A decision tree represents the scores (relative to the computer's side) of each player after every turn. On the computer's turn we are trying to maximize points and on the opponent's turn, we are trying to minimize points. Whatever move we make is only as strong as the opponent's next move is weak.
A good evaluation metric is the maximizing player's pieces minus the minimizing player's pieces. This quantitatively indicates how effective a decision would be for the player whose score is being maximized.
Supers are weighted more heavily than checkers, which prioritizes them as pieces. Supers are more beneficial than checkers because of their greater movement ability, so weighting them higher ensures that the the algorithm will try to gain them and avoid losing them.
Since the algorithm is recursive, the runtime increases exponentially the deeper we go.

LaZY™ gameplay simulationThe algorithm (playing as red) checks all possible moves and returns the move with the maximum evaluated score, which will benefit red the most. It assumes blue will choose the move with the minimum evaluated score to benefit red the least, maximizing blue's score.

Assumptions

The other player is going to make the best move for themselves every turn. The MiniMax algorithm assumes that the opponent will automatically make a move that is most beneficial for them, and therefore discards the less optimal moves from the decision tree. Playing a different move than expected adds an element of unpredictability.

Optimization

Alpha-Beta Pruning

Alpha-beta pruning is the process of eliminating possible moves from consideration in a decision tree that are not optimal because they are not to the benefit of the player whose current turn it is.
With alpha-beta pruning, we can remove moves with the least benefit to each player on their turn, as it is unlikely for them to take that route. Understanding which move is not beneficial to the opponent depends on the algorithm's search depth (how far ahead we can search) and how far ahead the opponent is thinking.
Alpha-beta pruning allows the algorithm to run faster by reducing run-time complexity.
In the visual on the right (computer is playing O), all non-optimal moves where a player has the option of winning but takes the route of not winning are discarded (greyed out). Since this game tree is searching from left to right (the orange arrows), the first move it sees (4th level of this tree, all the way to the left) is not discarded since the tree is being traversed from left to right, and the algorithm has no reference yet at that point.

Graphic from Moin H. Moti's "Ultimate Tic-Tac-Toe" project [2]

Depth Limit

The algorithm's depth limit specifies the number of turns to look ahead in the game tree. The number of moves possible become exponentially greater after each turn, as presented by the visual. This poses a limit to how deep we can search a game tree while playing in real time, so we have to set a depth limit.
For example, if there are 10 possible moves each player can make each turn, all 10 of those moves would need to be explored if we're not using alpha-beta pruning. At a depth level of 3 that adds up to 10^3 total moves, regardless of whether or not they actually improve the player's score. This idea is visually represented in the nested tree where each branch from the root creates its own tree. A smaller example with 3 possible moves and 3 turns is represented on the right. Notice how the third turn had 3^3=9 possible moves.
The benefit of increasing the depth limit is that we can better see all the possible ways the opponent can make winning moves. We are always assuming that plays are made (during the opponents turn) in the opponent's best interest. But if we have a search depth of 1, then we can only see moves that directly help the opponent in the next turn. However, say if our depth limit is 5 (we can see 5 moves ahead), we can view setups that the opponent could potentially make that help them maximize their score later on. We always want to increase the depth limit as much as we can to see the opponent's possible counter-strategy.

Graphic from Towards Data Science article on Minimax [3]

Google Sites

Report abuse