How to determine the winner

The state of the board at each point can be represented by a \(3 \times 3\) two-dimensional array \(C\), where each element takes one of \(\{\) white, red, blue \(\}\). In other words, \(C_{i,j}\) corresponds to the color of square \((i,j)\). Let \(f(C)\) be the final winner when we start the game from a board state \(C\).

Let \(I\) be the \(3 \times 3\) two-dimensional array whose elements are all white (corresponding to the initial state). The sought answer is \(f(I)\), so if we can find \(f(C)\) for an arbitrarily given \(C\) fast, the problem can be solved.

Let us consider how to evaluate \(f(C)\). Let \(x\) be the current player, and \(y\) be the other player.

If \(C\) is already in the terminal state (where there are three consecutive red or blue squares, or there is no white square), then the winner can be easily determined.

If \(C\) is not in the terminal state, then the board transitions to another when \(x\) chooses a white square and paint it with his color. Then the following holds:

• If there exists a board \(C'\) that can be transitioned from \(C\) with one operation such that \(f(C')=x\), then \(x\) can win by transitioning from \(C\) to \(C'\).
• Conversely, if \(f(C')=y\) for all boards \(C'\) that can be transitioned from \(C\) with one operation, then \(x\) can never win no matter how he make moves.

By this property, if \(f(C')\) is known for all boards \(C'\) that can be transitioned from \(C\), then \(f(C)\) can be found from these values. Such process can be easily implemented with a recursive function.

Implementation using recursive function

In the implementation using a recursive function, when the function \(f\) is called against a board \(C\), the following are executed:

1. If \(C\) is a terminal state, determine the winner and return the answer.
2. If \(C\) is not a terminal state, then enumerate all the boards \(C'\) that can be transitioned from \(C\) with one operation.
3. Calculate \(f(C')\) for each \(C'\).
4. From the results of the obtained \(f(C')\), determine the value \(f(C)\) according to the discussion above.

Since \(f\) it self is called during the process of \(f\) (at step 3), this process is called a recursion. Here, \(C'\) in \(f(C')\) that is called from \(f(C)\) is nearer to the terminal state, so such recursive function call does not repeat indefinitely (formally, the transitions of boards form a Directed Acyclic Graph (DAG).)

Let us roughly estimate how many times \(f\) is called. There are nine possible moves for the first turn, eight moves for the second turn, …, so there are about \(9! \approx 3.6 \times 10^5\) combinations of operations to reach from the initial to terminal state; this is fast enough. (Actually, the game terminates when three consecutive squares with the same color emerge, where recursive calls end, so the number of calls is even fewer than that.)

Sample code (Python)

Bonus: implementation using memorized recursion

While this problem can be solved fast enough with a naive recursive function, one can adopt the trick called memorization to reduce the number of times the recursive function is called.

In the implementation with a recursive function, if there are multiple paths to reach from the initial state \(I\) to a board \(C\), \(f(C)\) is called as many times as the number of such paths. However, \(f(C)\) evaluates to the same value for the same \(C\), so it is useless to evaluate \(f(C)\) for every recursive call. Instead, we memorize the result for the first evaluation of \(f(C)\), and return the memorized value for the second and subsequent calls of \(f(C)\).

Let us estimate how many times \(f(C)\) is called when memorization is enabled. There are at most about \(3^{3 \times 3} = 19683\) boards for \(C\), so \(f\) is called at most \(19683 \times 9 \approx 1.7 \times 10^5\) times, which turn out to be fewer than the estimation without memorization, \(3.6 \times 10^5\).

Although this problem does not require memorization, if there are more boards or possible transitions, the complexity may greatly improve by applying memorization.

Sample code (Python)