Solved Game - Solved Games

Solved Games

Awari (a game of the Mancala family)

The variant of Oware allowing game ending "grand slams" was strongly solved by Henri Bal and John Romein at the Vrije Universiteit in Amsterdam, Netherlands (2002). Either player can force the game into a draw.

Chopsticks

The second player can always force a win.

Connect Four

Solved first by James D. Allen (Oct 1, 1988), and independently by Victor Allis (Oct 16, 1988). First player can force a win. Strongly solved by John Tromp's 8-ply database (Feb 4, 1995). Weakly solved for all boardsizes where width+height is at most 15 (Feb 18, 2006).

Draughts, English (i.e. checkers)

This 8x8 variant of draughts was weakly solved on April 29, 2007 by the team of Jonathan Schaeffer, known for Chinook, the "World Man-Machine Checkers Champion". From the standard starting position, both players can guarantee a draw with perfect play. Checkers is the largest game that has been solved to date, with a search space of 5x1020. The number of calculations involved was 1014, and those were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50.

Fanorona

Weakly solved by Maarten Schadd. The game is a draw.

Free Gomoku

Solved by Victor Allis (1993). First player can force a win without opening rules.

Ghost

Solved by Alan Frank using the Official Scrabble Dictionary in 1987.

Hex

• A strategy-stealing argument (as used by John Nash) will show that all square board sizes cannot be lost by the first player. Combined with a proof of the impossibility of a draw this shows that the game is ultra-weak solved as a first player win.
• Strongly solved by several computers for board sizes up to 6×6.
• Jing Yang has demonstrated a winning strategy (weak solution) for board sizes 7×7, 8×8 and 9×9.
• A winning strategy for Hex with swapping is known for the 7×7 board.
• Strongly solving hex on an N×N board is unlikely as the problem has been shown to be PSPACE-complete.
• If Hex is played on an N × N+1 board then the player who has the shorter distance to connect can always win by a simple pairing strategy, even with the disadvantage of playing second.
• A weak solution is known for all opening moves on the 8x8 board.

Hexapawn

Kalah

Most variants solved by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk (2000) except Kalah (6/6). The (6/6) variant was solved by Anders Carstensen (2011). Strong first-player advantage was proven in most cases.

L game

Easily solvable. Either player can force the game into a draw.

Maharajah and the Sepoys

This asymmetrical game is a win for the sepoys player with correct play.

Nim

Strongly solved.

Nine Men's Morris

Solved by Ralph Gasser (1993). Either player can force the game into a draw

Ohvalhu

Weakly solved by humans, but proven by computers. (Dakon is, however, not identical to Ohvalhu, the game which actually had been observed by de Voogt)

Pentominoes

Weakly solved by H. K. Orman. It is a win for the first player.

Quarto

Solved by Luc Goossens (1998). Two perfect players will always draw.

Qubic

Weakly solved by Oren Patashnik (1980) and Victor Allis. The first player wins.

Renju-like game without opening rules involved

Claimed to be solved by János Wagner and István Virág (2001). A first-player win.

Sim

Weakly solved: win for the second player.

Teeko

Solved by Guy Steele (1998). Depending on the variant either a first-player win or a draw.

Three Musketeers

Strongly solved by Johannes Laire in 2009. It is a win for the blue pieces (Cardinal Richelieu's men, or, the enemy).

Three Men's Morris

Trivially solvable. Either player can force the game into a draw.

Tic-tac-toe

Trivially solvable. Either player can force the game into a draw.

Tigers and Goats

Weakly solved by Yew Jin Lim (2007). The game is a draw.