找出井字游戏所有获胜组合

1. Introduction

In this tutorial, we’ll show how to find all the ways to win a game of tic-tac-toe.

2. Problem Statement

Even though we’re dealing with a game that we can play using an adversarial search algorithm such as minimax or Monte Carlo Tree Search, we should note that the problem we’re solving now isn’t that of game playing. Instead of winning a single game against an actual opponent, we want to find all the states of the tic-tac-toe grid that represent a victory for player or player .

Another thing we should note is that this also isn’t a problem we can classify as a traditional search for the best solution because we’re not interested in the shortest sequence of winning moves. Instead, we consider all the victories equal, no matter the number of moves, and want to discover them all.

3. The Brute-Force Solution

The simplest way is to iterate over all the states of tic-tac-toe and return only those in which a player wins.

3.1. States

To do so, we first have to define a tic-tac-toe state. Since we play it on a grid, and each cell can be either blank or marked with or , we can define the states of the game as matrices. For example:

   

There are states the grid can be in, but not all of them are legal. Since players and alternate, the difference of the number of s and s on the grid at any point in the game can be at most 1. For instance, the following state isn’t legal because made three moves while made only one.

   

3.2. States and Matches

Each state corresponds to several matches. If the player occupies cells, and fills cells, then there are sequences of moves that lead to that state. For example, these two sequences finish in the same state:

   

There are move sequences that end the same way.

3.3. Win States

Let’s define a test to check if a legal grid state represents a victory for player .

The first thing that we should check is if contains a row, a column, or a diagonal comprised of all s. However, although this test would capture all the grid states in which wins, it would produce a significant number of false victories. For instance, the following grid state passes this test for player :

   

even though it’s not possible to encounter it in an actual game! As soon as filled the middle row, the game stopped, and couldn’t mark its third cell, so one is illegal.

Therefore, if player wins, it will have one cell more than player . But, if player wins, it will always have the same number of cells as player . That’s because has the first move, and the game stops after the winner makes its last move.

For the same reason, can win only in the odd turn, while can win only in the even turn. If the number of filled cells is even, and both and qualify for a win, then we know that the state is illegal. Since wins in the odd turn, the game would have ended before would get to connect its three cells.

So, this is the pseudocode to check if player has won:

algorithm TicTacToeWinTest(A):
    // INPUT
    //    A = a state of the tic-tac-toe 3x3 grid where each cell can be blank or filled with X or O
    // OUTPUT
    //    true if A represents a win for either player; false if A is not a win or even a legal state

    w <- an empty hash map
    w[X] <- false
    w[O] <- false

    // Find the player(s) that connected three cells
    // Check the rows and columns
    for i <- 1, 2, 3:
        if a[i, 1] = a[i, 2] = a[i, 3] and a[i, 1] != blank:
            w[a[i, 1]] <- true
        else if a[1, i] = a[2, i] = a[3, i] and a[1, i] != blank:
            w[a[1, i]] <- true

    // Check the diagonals
    if (a[1, 1] = a[2, 2] = a[3, 3] and a[1, 1] != blank) 
      or (a[3, 1] = a[2, 2] = a[1, 3] and a[3, 1] != blank):
        w[a[2, 2]] <- true

    // If there is a winner, verify the state is legal
    n_X <- count the Xs in A
    n_O <- count the Os in A

    if (n_X + n_O) is odd:
        if (w[X] = true) and (w[O] = false):
            return true
    else if (w[X] = false) and (w[O] = true):
            return true

    return false

3.4. Pseudocode

Finally, we formulate our brute-force approach as follows:

algorithm FindWinStatesTicTacToe():
    // OUTPUT
    //    The win states in tic-tac-toe

    W <- an empty set

    for each matrix A in {X, O, blank}^{3x3}:
        win <- perform the win test on A
        if win = true:
            W <- W + {A}

    return W

3.5. Complexity

Both the space and time complexities of our algorithm depend on the size of the search space. We calculated that there were states in total. Modern computers can easily store all of them in the main memory. So it’s reasonable to expect that it won’t take much time to run this algorithm, depending on the actual hardware used and other jobs our CPUs are executing concurrently.

That’s why a brute-force approach is justified in this case. Since the problem is tractable, a simple algorithm without complex logic can handle it.

4. Generalizations of Tic-Tac-Toe

However, generalizations of tic-tac-toe require a more sophisticated approach.

In them,n,k-game, we play tic-tac-toe on a grid. The winner is the player that first connects cells horizontally, vertically, or diagonally. An grid can have states. For example, the board has states. So, even for small values of and , there are too many states for a brute-force solution to be efficient.

Similar holds for the three-dimensional tic-tac-toe usually played in a cube of cells.

To find all the win states in these forms of tic-tac-toe, we’d have to use a more efficient constraint-satisfaction technique. We’d define constraints on the grid cells that win states fulfill and then construct the state cell by cell. If we realize that a state is illegal or infer that no player can win, then we backtrack and change the assignment of one of the cells we previously left blank or filled with or . Once we find a win state, we record it, backtrack, and continue the search.

5. Conclusion

In this article, we showed how to find all the tic-tac-toe grids that represent a win. Even though a simple brute-force algorithm proved sufficient to handle the standard game, the generalizations of tic-tac-toe to three dimensions and larger grids require a more efficient approach.