Determining Winning Moves in Board Games

Determining whether a board game has a "winning strategy" (or a drawing strategy) falls within the realm of Combinatorial Game Theory in mathematics and computer science. To determine and find a winning strategy, one typically needs to examine the properties of the game and apply corresponding mathematical theorems and algorithms.

Below are the common theories and methods used to determine and prove whether a board game has a winning strategy:

1. Confirm whether the game satisfies the prerequisites of Zermelo's Theorem

Before discussing winning strategies, it is necessary to confirm whether the board game belongs to the category of "finite, two-player, zero-sum, perfect-information games".

• Two-player: There are only two players.
• Zero-sum (or win/loss/draw): One player's win means the other's loss; no mutual wins.
• Perfect information: No hidden information (like concealed cards in poker); both players can see the entire board state.
• Deterministic: No random elements such as dice rolls.
• Finite: The game must end within a finite number of moves, with no infinite loops.

Zermelo's Theorem states: For any game satisfying the above conditions, if both players play optimally, there is a definite outcome:

1. The first player has a forced win;
2. The second player has a forced win;
3. Both players can force a draw (if the rules allow draws, e.g., chess, tic-tac-toe).

That is, as long as these conditions are met (e.g., chess, Go, Gomoku, Othello), there must theoretically exist some winning or undefeatable (draw-securing) strategy. The key question now is "how to determine which specific outcome applies" and "how to find it."

2. Brute-force search and backward induction (game tree expansion)

For games with a small state space, it is possible to enumerate all possible positions and generate a "game tree."

• Method (backward induction): Start from the terminal states of the game (loss, win, draw) and work backward to the initial position.
• Algorithm (Minimax algorithm): Assume both players never make mistakes; the first player always chooses the move most favorable to them (Max), and the second player always chooses the move least favorable to the first player (Min).
• Applications:
  • Tic-Tac-Toe: The state space is extremely small, making it easy to deduce that optimal play leads to a draw.
  • Connect Four: Has been completely solved by computers, proving that the first player has a forced win.

3. Strategy-stealing argument

This is a very clever existence proof method (proof by contradiction). It can prove that the first player has a forced win, but does not tell you the specific moves.

• Logic: Assume the second player has a winning strategy. Then, on the first move, the first player makes an arbitrary move and then "steals" the second player's winning strategy, playing as if they were the second player. If, in this game, making an extra move is always beneficial (or at least never harmful), then the first player, following the second player's winning strategy, is guaranteed to win. This contradicts the assumption that "the second player has a forced win"!
• Conclusion: In such games, since the second player cannot have a forced win and there is no draw, the outcome must be that the first player has a forced win.
• Applications:
  • Hex: The rules do not allow draws, and placing an extra piece is never harmful. Therefore, mathematician John Nash used this argument to prove that Hex is a first-player win.
  • Gomoku (without forbidden moves): It was similarly proven that the first player has a forced win (later, computers found specific winning strategies, leading to the introduction of "forbidden move" rules in Gomoku to balance the game).

4. Finding symmetry (Symmetry / Pairing Strategy)

If the board has a certain symmetry and the game rules allow it, a player can obtain a winning strategy by "mirroring" the opponent's moves.

• Example (Coin game): Players take turns placing coins flat on a round table. The player who cannot place a coin loses. The first player only needs to place the first coin in the exact center of the table. Then, wherever the second player places a coin, the first player places one symmetrically opposite relative to the center. This strategy guarantees a win for the first player.

5. Sprague-Grundy Theorem (for impartial combinatorial games)

If the game is "impartial" — meaning that for any given position, the set of legal moves and rules is the same for both players (e.g., the game of Nim) — then the SG theorem can be applied.

• Method: Transform any complex position into an equivalent Nim game (by calculating the SG function value / XOR sum).
• Conclusion: If the Nim-sum (or SG value) of the initial position is non-zero, the first player has a forced win; if it is zero, the second player has a forced win.

Summary

• Theoretically: As long as it is a finite, two-player, perfect-information game without luck, a perfect strategy (win or draw) must exist.
• How to find it:
  1. Very small board: Manual backward induction.
  2. Mathematical model (e.g., Nim): Calculate SG values or find symmetry.
  3. Special properties: Use "strategy-stealing" to prove a first-player win.
  4. Vast board (e.g., Go, chess): Currently, humans and AI can only compute "optimal solutions" that are infinitely close to a forced win. However, in the strict mathematical sense, for these complex games, whether it is a "first-player win" or a "forced draw" remains unknown, as current computer power is insufficient for complete enumeration.

When discussing the winning strategy in Gomoku, we must first clarify an absolute premise: this discussion is about traditional Gomoku without forbidden moves (free-style Gomoku).

In the absence of forbidden moves, the first player (Black) has a winning strategy. This is why modern standard Gomoku competitions (Renju) must introduce "forbidden moves for Black" (such as double-three, double-four, and overline) and complex opening rules (like the Yamaguchi rule), precisely to break this first-player advantage and make the game fair.

Below are the specifics of the winning strategy in free-style Gomoku and how it was discovered.

I. What is the winning strategy in Gomoku?

The winning strategy in Gomoku is not about memorizing a fixed sequence of moves, because the opponent's defensive positions are countless. The winning strategy is essentially a tactical system that uses "absolute initiative" to continuously pressure the opponent, ultimately forming multiple threats that cannot be defended simultaneously.

Specifically, Black's winning strategy is based on the following core elements:

1. Opening Choice:
   On a 15×15 board, Black's first move is at the center (tengen). After White's second move, if Black's third move chooses certain specific formations (such as the "Hua Yue" or "Pu Yue" opening), Black can guarantee victory.
2. Core Tactics: VCT and VCF
   • VCF (Victory by Continuous Four): Black makes a "straight four" (four in a row) with every move, forcing White to block immediately. Through continuous straight-four attacks, Black's stones gradually connect, eventually forming a decisive blow (such as a four-three).
   • VCT (Victory by Continuous Threats): Black makes a "live three" or "straight four" with every move, forcing White to passively defend without being able to counterattack.
3. Creating a Cross Point (Setting Up a Kill):
   Through the above continuous attacks, Black's ultimate goal is to create a "double-three," "double-four," or "four-three" situation on the board. Since White can only defend one point at a time, encountering multiple threats inevitably leads to a failure to defend, and Black wins.

II. How was this winning strategy discovered and proven?

1. Accumulation of Experience and Intuition (Early Human Stage)

For centuries, Gomoku masters had already realized in practice that the first player has a huge advantage. By the end of the 19th century, the Japanese had clearly recognized that without restrictions, a high-level Black player was almost invincible. Therefore, they gradually evolved the "Renju" rules with forbidden moves. However, at that time, the first-player win was only an "empirical consensus" and had not been rigorously proven by calculation.

2. Mathematical Existence Proof: Strategy-Stealing Argument

Mathematicians can use a logical proof called the "strategy-stealing argument" to show that in free-style Gomoku, the first player has a winning strategy.
The logic is simple: Assume the second player (White) has a winning strategy. Then Black makes a random first move, and then pretends to be White (ignoring the extra black stone or treating it as an extra move) and adopts White's winning strategy. In Gomoku, having an extra stone on the board is always beneficial and never harmful. Therefore, Black can win. This contradicts the assumption that "White has a winning strategy."
Thus, free-style Gomoku is either a draw or a first-player win. Since it is extremely difficult to fill the board for a draw, the conclusion points to a first-player win. However, this is only a theoretical proof and does not provide specific moves.

3. Complete Computer Solving (1992, L. Victor Allis)

The true "terminator" of Gomoku's winning strategy was Dutch computer scientist L. Victor Allis.

In 1992, while writing his doctoral dissertation, he created a computer program called Victoria.

• His method: The game tree of Gomoku is enormous, making traditional brute-force search (like exhaustive enumeration for Tic-Tac-Toe) impossible at the time. Allis cleverly incorporated human Gomoku knowledge (the VCF, VCT, and algorithms for finding double threats mentioned above) into the system, inventing an algorithm based on "proof-number search."
• His achievement: The program successfully exhaustively searched and computed every critical branch of free-style Gomoku on a 15×15 board, for the first time in human history proving not only that Black has a winning strategy but also computing the specific winning paths. He also proved that even under certain opening restrictions, some openings still guarantee a Black win.

Summary:
The first-player win in Gomoku was an empirical consensus among human players for centuries, and was finally exhaustively solved in 1992 by a computer scientist using a specially designed algorithm. Free-style Gomoku is therefore known in computer science as a "weakly solved game" — meaning that as long as Black does not make a mistake, no matter how White defends, Black has a guaranteed winning path.

Before introducing which other games have been solved, let's first clarify the three levels of "solved" in computer science, which will help in understanding:

1. Ultra-weakly solved: Only mathematically proven who will win (or draw), but the specific moves are unknown. (e.g., the "strategy-stealing" argument mentioned earlier).
2. Weakly solved: A computer has found a specific winning (or drawing) line starting from the initial game state. Following this line guarantees not losing, but if the pieces are arranged in a strange endgame position, the computer may not know the optimal move.
3. Strongly solved: Regardless of any legal endgame position on the board, the computer knows the absolute optimal move. (e.g., Tic-Tac-Toe).

Below are some famous games that have been weakly solved (or even strongly solved), and games that remain unsolved to this day.

---

I. Famous Games That Have Been "Solved"

Besides free-style Gomoku, several other famous board games have been completely figured out by computers:

1. Connect Four

• Result: First-player win (weakly solved).
• Process: The same computer scientist who solved Gomoku, L. Victor Allis, solved Connect Four in 1988 (almost simultaneously and independently discovered by mathematician James Dow Allen). As long as the first player places the first piece in the center column and plays perfectly, the first player wins. Playing in the columns immediately adjacent to the center leads to a draw; playing in the edge columns leads to a second-player win.

2. Checkers (Draughts)

• Result: Draw under perfect play (weakly solved).
• Process: This was a major milestone that made headlines. Professor Jonathan Schaeffer from the University of Alberta led a team that developed a program called Chinook. They computed for 18 years (from 1989 to 2007), enumerating $5 \times 10^{20}$ (500 quintillion) endgame positions, and finally announced in 2007 in the journal Science that Checkers had been completely solved. If both players play without error, the outcome is always a draw.

3. Nine Men's Morris

• Result: Draw under perfect play (strongly solved).
• Process: This ancient game (often seen in classic Western films) was strongly solved in 1993 by Ralph Gasser. He proved that regardless of the opening or any mid-game state, if both players play perfectly, the game is a draw.

4. Othello / Reversi — Latest Breakthrough!

• Result: Draw under perfect play (weakly solved).
• Process: This is a very recent breakthrough! In October 2023, Japanese researcher Hiroki Takizawa, using the computational power of modern supercomputers and optimized algorithms over several days of computation, officially announced that 8×8 standard Othello had been weakly solved. The conclusion is that when both players adopt perfect strategies, the final score is a direct draw.

---

II. Games That Remain "Unsolved"

You might ask: Since AI is so powerful (like AlphaGo), haven't all board games been solved?
The answer is: No.

"AI beating humans" and "mathematically solving a game" are completely different concepts. AI beats humans because it can find moves with a 99% winning probability through probabilistic calculation; "solving" requires 100% exhaustive enumeration and an irrefutable proof of the outcome.

Because the "state-space complexity" (number of possible board positions) and "game-tree complexity" (number of branches of all possible move sequences) of the following games are so enormous, they far exceed the total computational power of all existing supercomputers, and likely even those for centuries to come.

1. Chess

• Why unsolved: Chess has approximately $10^{43}$ legal positions, and the number of possible games is as high as $10^{120}$ (this number is known as the "Shannon number"). The total number of atoms in the observable universe is only about $10^{80}$. Even if every atom in the universe were turned into a computer, it would be impossible to compute all variations of chess.
• Current status: Although Deep Blue and modern engines like Stockfish crush all human masters, chess remains mathematically unknown. We do not know whether perfect chess is a win for White (first player) or a draw (most experts lean towards a draw).

2. Chinese Chess (Xiangqi)

• Why unsolved: Chinese Chess has a larger board and more room for movement. Its state-space complexity is approximately $10^{48}$, several orders of magnitude higher than chess.
• Current status: Similar to chess, top Xiangqi software (like Wang Zhong Wang, Pi Ka Yu, etc.) leaves humans helpless, but in the strict mathematical sense, it remains unsolved.

3. Go

• Why unsolved: Go is the "king of complexity" among board games. On the standard 19×19 board, the state-space complexity is a staggering $10^{170}$, and the game-tree complexity reaches $10^{360}$. Compared to Go, the complexity of chess is negligible.
• Current status: Even the groundbreaking AlphaGo and its successor AlphaZero have not "solved" Go. They merely use neural networks to build extremely strong "intuitive evaluations," knowing in most positions which move has the highest winning probability. However, if asked to prove "whether Go is a first-player win or a draw," even AlphaGo cannot do it.

Summary

• If a game's complexity is within $10^{20}$ (100 quintillion), like Checkers, Gomoku, Othello, humans can use supercomputers to brute-force "solve" it completely.
• Once the complexity exceeds $10^{40}$ (i.e., Chess, Chinese Chess, Go), exhaustive solving becomes physically impossible. For these games, we can only use AI to infinitely approach that "perfect truth," but we may never be able to touch it completely.

That's a very sharp question! Your logic is completely correct: expanding the board to infinity does make the number of positions infinite, making it absolutely impossible for a computer to "exhaustively enumerate" all possible moves.

However, free-style Gomoku on an infinite board is still "solved" mathematically and logically, and the conclusion remains: the first player (Black) has a forced win.

Since exhaustive enumeration is impossible, how was it solved? This uses a very simple but also very clever "dimensionality reduction" logic:

1. The "Cordon Off an Area" Strategy (Nested Proof)

In 1992, computers had already exhaustively proven that on a 15×15 limited board, Black has a winning line.

So, how does Black win on an infinite board?
It's simple: Black only needs to imagine drawing an invisible 15×15 square in the center of the infinite board and then completely copy the proven winning strategy for the 15×15 board.

As long as White plays inside this square, Black responds according to the known winning program; if White plays ten thousand kilometers away in the infinite space, Black simply ignores it and directly forms a line of five within their own 15×15 area. Because the winning strategy in Gomoku involves "tightly pressing" (continuous straight fours, live threes), White has no spare turns to go far away and cause trouble; they must stay in the main battlefield to defend.

2. The Larger the Board, the More Advantageous for the First Player

In Gomoku, the "board edge" actually helps the losing side (White) defend.
When Black attacks, the biggest fear is that the pieces will "hit the wall" before forming a line of five.
Since Black can achieve a 100% guaranteed win even in a cramped 15×15 space where hitting the wall is easy, then on an infinite board, Black no longer has the worry of hitting the wall and will win even more easily.

Summary:
Gomoku on an infinite board was not solved by infinite computational power, but by human mathematical logic using a nested proof. As long as the game is winnable on a 15×15 board, the first player is guaranteed to win on any board larger than that size (even an infinite one).