Lars Wächter

Posted on Dec 23, 2021

Improving Minimax performance

#programming #tutorial #algorithms #gamedev

This post was originally published on my blog.

The Minimax algorithm, also known as MinMax, is a popular algorithm for calculating the best possible move a player can player in a zero-sume game, like Tic-Tac-Toe or Chess. It makes use of an evaluation-function provided by the developer to analyze a given game board. During the execution Minimax builds a game tree that might become quite large. This causes a very long runtime for the algorithm.

In this article I'd like to introduce 10 methods to improve the performance of the Minimax algorithm and to optimize its runtime. Some of them have a bigger and some a smaller impact. In the future I'll try to add new methods. I won't go into more detail about how the algorithm works. It's just about optimizing it. Check out the link from above to learn how the algorithm actually works.

A quick overview of all techniques discussed in this article:

Alpha-Beta Pruning
Pre-sort moves
Bitboards
Transposition Tables
Board Symmetries
Reduce possible moves
Instant win
Improve .hasPlayerWon() function
Improve .evaluate() function
Decrease search depth

1. Alpha-Beta Pruning

One of the most widely-known improvements is Alpha-Beta-Pruning, also known as Alpha-Beta-Cut or Alpha-Beta-Search. This slightly modified version of Minimax can reduce the algorithm's runtime drastically. The key idea here is to reduce the number of nodes within the game tree by cutting them off. Therefore, two values α and β are passed along the tree. These values represent the worst-case-scenario for each player.

Have a look at the second row (3 6 3). Here, the α value is 6, which is the minimum score that MAX will reach after evaluating the first two nodes (3 6). When evaluating the third node MIN keeps in mind that MAX will at least achieve a score of 6. If MIN finds a value that is less than α, here 5, the other node 8 can be cut off. The reason: no matter what MIN chooses, MAX will choose the α value 6. And MIN will choose a value that is definitely <= 5.

Have a look at the link from above for a more detailed explanation.

2. Pre-sort moves

Try to pre-sort the list of possible moves starting with the best ones when using Alpha-Beta Pruning. In this case, there's a higher chance of cutting of nodes within the game tree since the algorithm starts with a high alpha or low beta value at the beginning of each level.

3. Bitboards

Bitboards are a way of representing the game board using bits. In this case, each single bit represents one position on the board. Moreover, both players have their own board.

An example bitboard for Tic-Tac-Toe:



const board = [
    0b000_000_000,  // Player 1 Board (X)
    0b000_000_000   // Player 2 Board (O)
]

One of the main advantages of bitboards is that they allow a lot of flexibility in evaluation. Using bitwise opertations like AND, OR, XOR and shifting you can check for winning conditions, play & validate moves or rotate the game board in a very short time. They are also useful for calculating the board hash, which is used for transposition tables.

Depending on the complexity of your game bitboards might make a remarkable difference in terms of performance. Check out this link to see a Connect Four implementation using bitboards.

4. Transposition Tables

Transposition tables are used to store the result of already analyzed boards. This prevents the algorithm from evaluating the same board multiple times and reading it from a memory, the transposition table, instead.

Usually, transposition tables are implemented as a HashMap where the key is the hashed board. You can either store the transposition table in-memory and build it during the Minimax execution or store it in a non-volatile memory, like a text file for example.

A transposition table might look as follows:



8063104835353205054 2 -8534.0 -1
3522504971336218492 1 1082.0 -1
9207316698546002515 5 2705.0 1

Each single row contains information about:

the board hash
the played move
the move's evaluated score
the move's player

In Minimax, you can search for the current board hash within the transposition table and return the according entry.



function minimax(storage, game) {
    // recursion anchor ...

    const storedMove = storage.get(game.calcBoardHash());
    if(storedMove) return storedMove;

    // evaluation ...
}

If not entry was found, the board must first be evaluated. At the end of Minimax you can push the evaluated move to the transposition table right before it's returned:



function minimax(storage, game) {
    const bestMove; // evaluation ...
    storage.set(game.calcBoardHash(), bestMove);
    return bestMove;
}

5. Board Symmetries

The key idea is that you apply a symmetrie to your current examined board and read its counterpart from the memory, if existing. This reduces the number of board evaluations immensely. Symmetries are very powerful especially in combination with bitboards.

Depending on your game there are different symmetries that you can make use of. For example:

Inverting the board
Rotating the board (and inverting) => Tic-Tac-Toe, Mill
Mirroring the board on the x/y axis (and inverting) => Connect Four, Chess

With Bitboards you can easily rotate and mirror the board using binary operations. Check out this GitHub Gist to see a Bitboard for Tic-Tac-Toe in Kotlin.

Inverting the board

Tic-Tac-Toe



1)          2)

X . .       O . .
X O O       O X X
. . .       . . .

In the first scenario, the best possible move for player X is to play position 7 (bottom left). The same applies to player O in the second case. If Minimax have already calculated the best possible move for board #1 and it's stored in a transposition table, you can invert the board in the case of board #2, which gives you board #1, and read the best possible move of board #1 from memory and apply it. Keep in mind that this only applies to player O for the second board.

Rotating the board

Tic-Tac-Toe



1)          2)

X . .       . X X
X O O       . O .
. . .       . O .

Again, the best move for player X is to play position 7 in the first scenario. The second board is the same as the first one, but rotated by 90° clockwise. This time if Minimax have already evaluated board #1, you can rotate board #2 by 90°, which gives you board #1, and again read the best possible move of board #1 from memory. In this case you have to slightly modify the move: since the board was rotated by 90° clockwise you have to rotate the move 90° counter clockwise. Repeat this procedure for 180° and 270°.

Moreover, you can combine this method with the inverted board from above.

Mirroring the board

Connect Four



1)                  2)

. . . . . . .       . . . . . . .
. . . . . . .       . . . . . . .
. . . . . . .       . . . . . . .
. X . . . . .       . . . . . X .
. X . O O . .       . . O O . X .
. X O X O . .       . . O X O X .

Here, the best move for player X is to play column 2 in the first scenario. The second board is the same as the first one, but mirrored on the center y-axis. This time, after the evaluation of board #1, you can mirror board #2, which gives you board #1, and apply its best move. Don't forget to to mirror the move as well.

Once more, you can combine this technique with the inverted board.

6. Reduce possible moves

Keep in mind that each single move causes a new child node that has to be evaluated recursively. Therefore, it's simple: a smaller number of possible moves for each board leads to less nodes and evaluations in your game tree. That means: remove unnecessary and irrelevant moves. For example, in Connect-Four, don't play any moves that will definitely not result in a row of 4 in future. Be careful not to remove any moves that could prevent your opponent from winning.

7. Instant win

Before evaluating all possible moves you can check whether any of them will result in an instant win for the current player. If that's the case you can directly return this move and you don't have to evaluate the other ones.



function minimax(game) {
    // recursion anchor ...

    for(const move of game.getPossibleMoves())
        if(game.doMove(move).hasPlayerWon(game.currentPlayer))
            return [1_000_000, move];

    // evaluation ...
}

Furthermore, make sure to return a high score since it's a win-move.

8. Improve .hasPlayerWon() function

The .hasPlayerWon() function checks whether a player has won. It's commonly used in the recursion anchor, when evaluating the game board. Here, we can optimize two things:

Don't check before a win is possible
Don't check both players



game.hasPlayerWon = function(player) {
    if(this.playedMoves < 5) return false;
    // check if the given player has won ...
}

For example, in Tic-Tac-Toe, at least 5 moves must have been played before a player can win. That's why we immediately return false when less than 5 moves were played.

Moreover, we only have to check whether one player has won, not both. The player who played the last move is the only one who could have won so we don't have to check the other one.



function minimax(nodeHeight, game) {
    // recursion anchor
    if (nodeHeight == 0 || game.isDraw() || game.hasPlayerWon(-game.currentPlayer))
        return [game.evaluate(), null];
    // ...
}

Here, when calling game.hasPlayerWon() we check whether the previous player (the one who played the last move) has won. If player A is stored as 1 and player B as -1 you can easily switch between them using a negate: -game.currentPlayer.

9. Improve .evaluate() function

The evaluation function is called dozen of times during the execution of Minimax. That means: improve this function and make it as fast as possible. Combine it with Bitboards and check for a player's win blazing fast.

Moreover, there's no need to dig into the depths of the game tree if your evaluation function returns a score that reflects the board quite well. Just a single descent within the game tree can lead to a much longer runtime.

Another tip: include the current node height in the evaluation score. Moves that are higher up in the game tree will have a better score this way and the algorithm will pick the one that leads the fastest to a win.



game.evaluate = function(nodeHeight) {

    const score; // calc score ...

    return score + nodeHeight;

}

function minimax(nodeHeight, game) {

    // recursion anchor

    if (nodeHeight == 0 || game.isDraw() || game.hasPlayerWon(-game.currentPlayer))

        return [game.evaluate(nodeHeight), null];

    // evaluation ...

}

Decrease search depth

The last option might be the most obvious one: decrease the maximum search depth of the algorithm.
Does your game tree really have to be that deep? Do you have to look 9 or 10 moves ahead? Isn't a lookahead of 5 enough? Depending on the game, I guess most human players cannot anticipate more than maybe 3 to 4 moves. As I already said above, each single tree level results in a much longer runtime. Think about it.

Further resources

Last but not least a list with some useful resources.

We blog: Minimax Improvements
Chessprogramming: Bitboards
Wikipedia: Transposition Tables

Check out my example projects as well:

Connect Four in Kotlin
TTT Bitboard in Kotlin
Minimax in Kotlin
Zobrist Hashing in Kotlin

DEV Community