Determining Winning Moves in Board Games

Determining whether a board game has a “forced winning move” (or forced draw move) falls under the research domain of Combinatorial Game Theory in mathematics and computer science. To determine and find forced winning moves, one typically needs to examine the game's properties and apply corresponding mathematical theorems and algorithms.

The following are common theories and methods for determining and proving whether a board game has a forced winning move:

1. Confirm if the game meets the prerequisites of Zermelo's Theorem

Before exploring winning strategies, first confirm if this board game qualifies as a ‌“finite two-player zero-sum perfect information game”‌‌.

• Two-player:‌ 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 hidden cards in poker), both sides can see the entire board state.
• Deterministic:‌ No random elements like dice rolls.
• Finite:‌ The game must end in a finite number of moves, no infinite loops.

Zermelo's Theorem states:‌ For any game meeting the above conditions, under optimal play by both sides, there is always a definite outcome‌:

1. First player wins;
2. Second player wins;
3. Draw (if rules allow draws, like in chess, Tic-Tac-Toe).

In other words, as long as these conditions are met (e.g., Chinese Chess, Go, Gomoku, Othello), theoretically, there definitely exists some winning or non-losing (forcing a draw) strategy‌. The current focus is on “determining exactly which one it is” and “how to find it”.

2. Brute-Force Search and Backward Induction (Game Tree Expansion)

For games with small state spaces, exhaustively enumerate all possible positions to generate a “game tree”.

• Method (Backward Induction):‌ Start from terminal positions (loss, win, draw) and work backward to the opening.
• Algorithm (Minimax Algorithm):‌ Assume both sides make no mistakes; first player always chooses the move most favorable to themselves (Max), second player chooses the move least favorable to the first (Min).
• Applications:‌
  • Tic-Tac-Toe:‌ Extremely small state space, easily deduces that under optimal play, it's a draw‌.
  • Connect Four:‌ Fully solved by computers, proving first player wins‌.

3. Strategy-Stealing Argument

This is a very clever existence proof method (proof by contradiction). It proves first player wins but doesn't tell you the specific moves‌.

• Logic:‌ Assume second player has a winning strategy. Then, first player makes a random first move, then “steals” the second player's winning strategy, pretending to be the second player. If in this game, having an extra move is always beneficial or harmless, then first player following the second player's winning strategy will definitely win. This contradicts the “second player wins” assumption!
• Conclusion:‌ In such games, since second player cannot win and there are no draws, it must be first player wins‌.
• Applications:‌
  • Hex:‌ Rules disallow draws, and placing an extra piece is never harmful, so mathematician Nash used this to prove Hex is first player win‌.
  • Gomoku (free-style five in a row):‌ Similarly proved first player wins (later computers found specific winning moves, leading to the introduction of “forbidden moves” in Gomoku to balance it).

4. Exploiting Symmetry (Symmetry / Pairing Strategy)

If the board has certain symmetry and rules allow, 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 one who can't place loses. First player places the first coin in the exact center, then mirrors the second player's placement symmetrically across the center. This strategy guarantees first player wins‌.

5. Sprague-Grundy Theorem (For Impartial Combinatorial Games)

If the game is “impartial” (Impartial Game)—meaning from the same position, whoever's turn it is has the exact same legal moves and rules (e.g., Nim stone-taking games), then use the SG theorem.

• Method:‌ Convert any complex position to an equivalent Nim game (compute SG function values / XOR sum).
• Conclusion:‌ If the initial position's Nim-Sum (or SG value) is non-zero, first player wins; if zero, second player wins.

Summary

• Theoretically:‌ Any two-player perfect-information finite game without luck definitely has a perfect strategy (win or draw).
• How to find it:‌
  1. Tiny board: Manual backward induction.
  2. Mathematical model (like stone-taking): Compute SG value or exploit symmetry.
  3. Special properties: Use “strategy stealing” to prove first player wins.
  4. Huge boards (like Go, Chinese Chess): Currently, humans and AI can only compute near-optimal solutions approaching perfection, but in rigorous mathematical terms, for these complex games, whether it's “first player win” or “draw” remains unknown due to insufficient computational power for full enumeration.

When discussing Gomoku's winning strategy, first clarify an absolute premise: This refers to traditional Gomoku without forbidden moves (free-style Gomoku)‌‌.

Without forbidden moves, first player (black) has a winning strategy‌. This is why modern formal Gomoku tournaments (Renju) must introduce “black forbidden moves” (like three-three ban, four-four ban, overline ban) and complex opening rules (like Yamaguchi rules) to break this first-player win advantage and make the game fairer.

Here is the specific content of the winning strategy for Gomoku without forbidden moves and its discovery process:

I. What is Gomoku's winning strategy?

Gomoku's winning strategy is not about memorizing a fixed sequence of opening-to-endgame “moves”, as opponents have thousands of defensive options. The winning strategy is essentially a tactical system that uses “absolute first-move advantage” to continuously pressure the opponent, ultimately forming multiple threats (impossible to defend simultaneously)‌‌.

Specifically, black's winning strategy is based on the following cores:

1. Opening choice:‌
   On a 15×15 board, black's first move is at the center (tengen). After white's second move defense, black's third move chooses specific formations (like ‌“Flower Moon” or “Bay Moon”‌ openings), guaranteeing a win for black.
2. Core tactics: VCT and VCF
   • VCF (Victory by Continuous Four - continuous four win):‌ Black makes a “four threat” every move (white must defend tightly); during continuous four threats, black's pieces unknowingly connect into a group, ultimately forming a killing blow (like four-three).
   • VCT (Victory by Continuous Threats - continuous threat win):‌ Black makes a “live three” or “four threat” every move, forcing white into passive defense without counterattack opportunities.
3. Creating intersections (making a kill):‌
   Black's ultimate goal through constant attacks is to create ‌“double three”, “double four”, or “four-three”‌ situations on the board. Since white can only defend one point at a time, multiple threats overwhelm white's defense, leading to black's victory.

II. How was this winning strategy discovered and proven?

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

Over hundreds of years, Gomoku experts discovered in practice that first player has a huge advantage. By the late 19th century, Japanese players realized that without restrictions, high-level black players were nearly unbeatable. Thus, they evolved “Renju” rules with forbidden moves. At this point, first-player win was just an “empirical consensus”, not rigorously proven by computation.

2. Mathematical Existence Proof: Strategy-Stealing

Mathematicians can prove first-player win in free-style Gomoku using “strategy-stealing” logic.
The logic is simple: Assume second player (white) has a winning method. Then black makes a random first move somewhere, then pretends to be white (ignoring or treating the extra black stone as beneficial), and follows white's winning method. In Gomoku, having an extra stone of your own on the board is always beneficial, never harmful‌. Thus, black wins, contradicting the “second player wins” assumption.
Therefore, free-style Gomoku is either a draw or first-player win. Since filling the board for a draw is extremely rare, the conclusion is first-player win. But this is theoretical, without specific moves.

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

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

In 1992, while writing his PhD thesis, he developed a program called Victoria‌.

• His method:‌ Gomoku's game tree is enormous; traditional brute-force (like enumerating Tic-Tac-Toe) was impossible then. Allis cleverly integrated human Gomoku knowledge (VCF, VCT, and double-threat search algorithms) with a “proof-number search” algorithm.
• His achievement:‌ The program exhaustively computed every key branch on the 15×15 board for free-style Gomoku, for the first time in history proving not only black wins but also computing specific winning paths‌. He also proved that even with certain opening restrictions, black still wins in some openings.

Summary:‌
Gomoku's first-player win is an empirical consensus from centuries of human play, ultimately exhaustively solved in 1992 by a computer scientist using a custom algorithm. Free-style Gomoku is thus known in computer science as a ‌“weakly solved game”‌‌—as long as black doesn't blunder, white cannot prevent loss no matter the defense; black has coded paths to victory.

Before introducing other solved games, let's first explain the three levels of “solving” in computer science, to better understand:

1. Ultra-weakly solved:‌ Proven mathematically who wins (or draw), but no specific moves known (like the “strategy-stealing” mentioned previously).
2. Weakly solved:‌ Computer found a specific winning (or drawing) line from the initial position‌. Follow it to not lose, but for weird endgame positions, it might not know the optimum.
3. Strongly solved:‌ For any legal position‌, computer knows the absolute optimal solution (e.g., Tic-Tac-Toe).

Here are some famous weakly solved (even strongly solved) games, and those still unsolved.

---

I. Famous Games That Have Been “Solved”

Besides free-style Gomoku, several famous board games have been fully cracked by computers:

1. Connect Four

• Solve result: First player wins (weakly solved).‌
• Solve process:‌ Also by L. Victor Allis who solved Gomoku, in 1988 (almost simultaneously independently discovered by mathematician James Dow Allen). First player places first move in the exact center column and plays perfectly to win. Center-adjacent columns lead to draw; edges to second-player win.

2. Checkers / Draughts

• Solve result: Perfect play leads to draw (weakly solved).‌
• Solve process:‌ A landmark milestone. Professor Jonathan Schaeffer from University of Alberta, Canada, led a team developing Chinook‌. They computed for 18 full years (1989-2007), enumerating $5 \times 10^{20}$ (500 quintillion) positions, announcing in 2007 in Science magazine: Checkers is solved. Perfect play by both = draw.

3. Nine Men's Morris

• Solve result: Perfect play leads to draw (strongly solved).‌
• Solve process:‌ This ancient game (appears in many Western classical films) was strongly solved in 1993 by Ralph Gasser. Proven: any position, perfect play = draw.

4. Othello / Reversi — Latest Breakthrough!

• Solve result: Perfect play leads to draw (weakly solved).‌
• Solve process:‌ A very recent breakthrough! In October 2023‌, Japanese researcher Hiroki Takizawa used modern supercomputer power, with optimized algorithms over days of computation, officially announced 8×8 standard Othello weakly solved. Conclusion: Perfect play = exact tie score.

---

II. Games Still “Unsolved” to Date

You might ask: With AI so strong (like AlphaGo), are all board games solved?
Answer: No.‌

‌“AI beating humans” and “mathematically solving a game” are completely different.‌ AI beats humans via probabilistic computation finding 99% win-rate moves; “solving” requires 100% exhaustive proof.

These games have “state-space complexity” (number of possible board states) and “game-tree complexity” (branching of all moves) far too large, exceeding all current and foreseeable supercomputer power for centuries.

1. Chess

• Why unsolved:‌ ~$10^{43}$ legal states, ~$10^{120}$ possible games (Shannon number). Observable universe atoms ~$10^{80}$. Even computers made from all universe atoms couldn't compute all Chess variations.
• Status:‌ Deep Blue and modern Stockfish crush human grandmasters, but Chess is mathematically unsolved‌. Unknown if perfect play is white (first) win or draw (most experts lean draw).

2. Chinese Chess (Xiangqi)

• Why unsolved:‌ Larger board, more pieces; state-space ~$10^{48}$, orders higher than Chess.
• Status:‌ Top engines (Elephant, Cyclone) dominate humans, but unsolved rigorously.

3. Go

• Why unsolved:‌ Go is the “complexity king” of board games. 19×19 board: state-space ~$10^{170}$, game-tree ~$10^{360}$. Chess is trivial by comparison.
• Status:‌ Even revolutionary AlphaGo/AlphaZero didn't “solve” Go. They use neural nets for strong “intuition evaluation” maximizing win chance, but cannot prove “first win or draw”.

Summary

• Games under $10^{20}$ (quintillion) complexity like Checkers, Gomoku, Othello can be brute-forced solved.
• Over $10^{40}$ (‌Chess, Xiangqi, Go‌), exhaustive solving is physically impossible. AI can only infinitely approach “perfect truth” without fully touching it.

This question is very sharp! Your logic is completely correct: Expanding the board to infinite size does make the number of positions infinite, so computers absolutely cannot “enumerate” all moves.‌

However, infinite-board free-style Gomoku has still been “solved” mathematically and logically: first player (black) wins.‌

Without enumeration, how? Using a very simple yet cheeky ‌“dimensional reduction” logic‌:

1. “Territorial Claim” Strategy (Nested Proof)

In 1992, computers proved: On 15×15‌, black has a winning line.

On infinite board, how does black win?
Simple: Black imagines drawing a 15×15 invisible box in the infinite board's center and exactly copies the 15×15 winning moves.‌

If white plays inside the box, black responds per the known winning program; if white plays a million kilometers away in infinite space, black ignores and connects five in its 15×15 area. Gomoku winning relies on “relentless pressure (continuous fours, live threes)”; white has no spare turns to disrupt elsewhere and must defend the main battlefield.

2. Larger Board Favors First Player More

In Gomoku, board edges actually help the trailing player (white) defend.‌
Black fears chains hitting walls mid-formation, short of 5.
Since black wins 100% on wall-prone 15×15; on infinite board, no wall worries—winning even easier.

Summary:‌
Infinite Gomoku isn't solved by infinite computation, but by human mathematical nested logic‌. If 15×15 wins, any larger (even infinite) board guarantees first-player win.