MAY 2021

AI-Assisted Tic-Tac-Toe

The interactive app lets you play the game with AI assistance, illustrating which moves can guarantee a win: Red fields allow XX to win, blue fields allow OO to win. Note that the player who is given the theoretical guarantee to win still has to realize this guarantee by following one of the sequences of best moves, i.e. by adhering to the respective color. Then, you may notice, the other player will not have any other choice (all possible moves will be marked in the opponent's color).

The game tic-tac-toe is simple, but it is also sufficiently complex to illustrate a few core concepts of artificial intelligence. In tic-tac-toe, two players, XX and OO, mark the board with their respective symbol in turns. The first player to form a row, column, or diagonal of three identical symbols wins. Three-in-a-row board games can be traced back thousands of years.

The game is simple, but its game tree, i.e. the set of possible paths, is sufficiently complex: There are 9!9! possible sequences of moves. A play is one specific sequence of moves. However, not all sequences are valid: Once the game has ended, no more moves can be made. This reduces the number of possible plays to 255,168. The number of plays for different scenarios is discussed here.

Therefore, the game tree is too complex to be read manually. In practice, though, due to symmetry of moves, the number of distinct strategies is much lower. The minimax algorithm offers an approach to analyze the game tree recursively in order to identify the outcome of a specific move, given a certain board state and given the assumption that the other player plays perfectly. Minimax assigns each leaf of the game tree a value, e.g. +1+1 when player XX wins, 1-1 when OO wins, and 00 when the game is a draw.

In order to determine the best possible move for a player at a certain state of the game, results are recursively propagated upwards, given the assumption that both players will always choose one of their best moves. The following minimax implementation is part of the script that computes the complete game tree with all sequences of plays, including the expected outcomes for each board state. Here, bx and bo are sets of numbers from zero to eight, denoting the positions of symbols on the board for both players XX and OO.

def minimax(bx, bo):
    if is_over(bx, bo):
        return board_value(bx, bo)
    if turn(bx, bo) == "X":
        v = -math.inf
        for cx, co in next_boards(bx, bo):
            v = max(v, minimax(cx, co))
        return v
    if turn(bx, bo) == "O":
        v = math.inf
        for cx, co in next_boards(bx, bo):
            v = min(v, minimax(cx, co))
        return v

The minimax algorithm is an example of how a simple idea can solve a comparatively complex problem through recursion. However, minimax is not always feasible. The number of plays in a chess game is so large that traversing the tree is practically impossible. The optimization approaches that exist, such as alpha-beta pruning, reduce the number of nodes in the game tree that have to be evaluated, but the game tree still has to be traversed at least partially. Play the game here.