La Vieja

John Von Neumann 🇭🇺 was a mathematician, computer scientist, and philosopher who made significant contributions to a wide range of fields, including game theory, computer science, and quantum mechanics.

Game theory: a branch of mathematics that deals with the study of strategic decision-making, and it is used to analyze situations in which multiple actors make decisions that affect each other’s outcomes.

In the 1950s, John used game-theoretic principles to develop algorithms such as the minimax algorithm, which is a decision-making strategy used in game theory to minimize the maximum loss that a player can incur in a two-player, zero-sum game in which one player’s gain is the other player’s loss.

One of the key features of the minimax algorithm is that it assumes that the other player is rational and will always choose the strategy that is most beneficial to them. The algorithm works by considering all possible moves that a player could make, and then calculating the maximum loss that could result from each move. The player then chooses the move that minimizes the maximum loss, hence the name “minimax.”

\[ v_i=\max _{a_i} \min _{a-i} v_i\left(a_i, a-i\right) \]

Where

• i = index of the player of interest
• -i = denotes all other players except player i
• a_i = action taken by player i
• a-i = actions taken by all other players
• v_i = value function of player i

So…what does this have to do with playing an optimal game of tic-tac-toe? It turns out that we can represent tic-tac-toe as a two-player zero-sum game which means that we can use the algorithm above to calculate an optimal move, thus, our game “AI” (if we can even call it that) is born.

Here, I’ll present the relevant bits for the game, the full code can be found here. First, we represent each possible state of our board with an enum:

enum class SquareState {
        Empty,
        Circle,
        Cross
};

Once we can represent our state, we can represent groups of states with an array (i.e. a 2D 3x3 array of SquareState). Each winning rule for the game can then be encoded as a bit-sequence that corresponds to the locations in the grid that a player needs to have filled to have won the game, e.g a horizontal line, vertical line or diagonal line in any of the valid combinations:

WinningStates WinStates[8] = {  //there are  8 different conditions that the board can be in where somebody has won
    {std::bitset<BOARD_SIZE>(std::string("100010001")), std::string("diagonal (left-to-right) #1")},
    {std::bitset<BOARD_SIZE>(std::string("100100100")), std::string("vertical col #1")},
    {std::bitset<BOARD_SIZE>(std::string("010010010")), std::string("vertical col #2")},
    {std::bitset<BOARD_SIZE>(std::string("001001001")), std::string("vertical col #3")},
    {std::bitset<BOARD_SIZE>(std::string("111000000")), std::string("horizontal row #1")},
    {std::bitset<BOARD_SIZE>(std::string("000111000")), std::string("horizontal row #2")},
    {std::bitset<BOARD_SIZE>(std::string("000000111")), std::string("horizontal row #3")},
    {std::bitset<BOARD_SIZE>(std::string("001010100")), std::string("diagonal (right-to-left) #2")}
};

Also, we make something that can hold our board state including things like whose turn it is, for brevity, I won’t show that here. Once we have these three pieces, we can put them together in a function like this:

    score minimax(BoardState board, unsigned int depth, bool playing_as_maximizer){
        score val = heuristic(board);
        if(val == 10){
            return 10-depth;
        }
        if(val == -10){
            return -10+depth;
        }

        if(board.is_full()){
            return 0;
        }

        if(playing_as_maximizer){
           score value = -1000;
           for(auto move: board.empty_slots()){
               auto [x,y] = move;
               BoardState child = board;
               child.grid[x][y] = maximizing_player;
               value = std::max(value, minimax(child, depth+1, !playing_as_maximizer));
           }
           return value;
        } else {
           score value = 1000;
           for(auto move: board.empty_slots()){
               auto [x,y] = move;
               BoardState child = board;
               child.grid[x][y] = inverse_player(maximizing_player);
               value = std::min(value, minimax(child, depth+1, !playing_as_maximizer));
           }
           return value;
        }
    }

The minimax function above is where all the magic happens, it basically implements a version of the equation we saw at the beginning except that we have a “base case” heuristic used to assign a value to the final configuration of the evaluation of a board state. In this case, there is a natural heuristic which is to simply assign a large negative gain when the other player ends up with a winning combination and a large positive gain when we ended up with a winning combination.

Now that we understand how it all works, you can try out my code implementation as a live game that you can play on your browser thanks to WebAssembly.