Find possible moves for Tic Tac Toe's minimax algorithm

Question

I decided to create a Tic Tac Toe game with 11x11 board, the winning condition is 5 cell X or O in a row (vertical, horizontal or diagonal) or when the board is full, i.e. no possible move left.

I create an AI opponent, which use the minimax algorithm to find the best move on the board. The pseudocode of minimax (with alpha-beta pruning) is as follow:

function alphabeta(node, depth, α, β, maximizingPlayer)
    if the game ends:
        return the heuristic value of the current state
    if maximizingPlayer
        v := -∞
        for each possible move in board // notice this
            v := max(v, alphabeta(child, depth – 1, α, β, FALSE))
            α := max(α, v)
            if β ≤ α
              break (* β cut-off *)
        return v
    else
    ....

Originally, the size of the Tic-tac-toe board is only 3x3, which mean there's no much empty cell to loop minimax. But with 11x11 board, there are 121 cells!

For example, if the first turn is X, then O have 120 possible moves. O will try each move to find the best value to play, and therefore the running time of the function is factorial of 120.

My question is, can we somehow reduce the possible moves? For example, if the first player moves somewhere in the center then we don't need to check minimax for some corner or edge cells.

Codor Codor · Accepted Answer · 2017-02-17T08:32:49

If I understood the question correctly, the Alpha-Beta-Pruning itself is intended to reduce the numer of investigated moves by stopping if the respective maximum or minimum is found. If this isn's sufficient, some heuristic needs to be employed. This means that the game tree is not investigated up to the leaves (which the pseudocode description above does not do) but some artificial bound on the recursiuon depth is introduced. If the recursion depth is reached, the board has to be heuristically evaluated if it is not in a terminal state.

Find possible moves for Tic Tac Toe's minimax algorithm

1 Answers