Games that have been solved
klausbh
United States
Bowie
Maryland
flag msg tools
badge
Avatar
Recommend
47 
 Thumb up
5.00
 tip
 Hide
Abstract strategy games with perfect information are all theoretically solvable. With perfect play the outcome is predetermined by the game itself, not the players. I am curious which noteworthy games have been solved. Here are the ones I know about:
Your Tags: Add tags
Popular Tags: abstract [+] solved [+] [View All]
  • [+] Dice rolls
1. Board Game: Tic-Tac-Toe [Average Rating:2.60 Overall Rank:15341]
klausbh
United States
Bowie
Maryland
flag msg tools
badge
Avatar
DRAW - This serves to illustrate the idea of a solved game. Most children give up on Tic-Tac-Toe when they realize the game should always end in a draw. More importantly, it can be mathematically demonstrated that Tic-Tac-Toe cannot be won against a "perfect" opponent.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
2. Board Game: Connect Four [Average Rating:4.84 Overall Rank:15312]
klausbh
United States
Bowie
Maryland
flag msg tools
badge
Avatar
WIN - When played correctly, the first player always wins.
(http://www.tomski.com/archive/connect4.pdf)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
3. Board Game: Kalah [Average Rating:5.86 Overall Rank:3457]
klausbh
United States
Bowie
Maryland
flag msg tools
badge
Avatar
DRAW - One particular version of this family of games, "Awari", has been solved.
(http://www.cs.ualberta.ca/~awari/)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
4. Board Game: Nine Men's Morris [Average Rating:5.37 Overall Rank:14955]
klausbh
United States
Bowie
Maryland
flag msg tools
badge
Avatar
DRAW - Now if only I could memorize all those moves ...
(http://www.geocities.com/twixtplayer/NMM1.html)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
5. Board Game: Qubic [Average Rating:5.25 Overall Rank:14122]
klausbh
United States
Bowie
Maryland
flag msg tools
badge
Avatar
WIN - First player should take this one every time.
(http://www.wylliedraughts.com/Qubic.htm)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
6. Board Game: Go-Moku [Average Rating:5.95 Overall Rank:5239]
klausbh
United States
Bowie
Maryland
flag msg tools
badge
Avatar
WIN - Player one strikes again
(http://www.ics.uci.edu/~eppstein/cgt/gomoku.html)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
7. Board Game: Mastermind [Average Rating:5.49 Overall Rank:14317]
eugene meidinger
United States
Unspecified
Pennsylvania
flag msg tools
mbmb
Win on turn four: I hope someone has the link but you can break the code in four turns if you know how.
I hope this fits the list.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
8. Board Game: Focus [Average Rating:6.46 Overall Rank:2695]
Pat Wilz
United States
Bay St. Louis
MS
flag msg tools
It's a funny name
badge
I found this backstage, an over-sized hat, it's funny!
Avatar
mbmbmbmbmb
Draw. The second player can force a draw by mirroring the moves of the first player. However, this can be prevented using rules described in Sackson's A Gamut of Games
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
9. Board Game: Checkers [Average Rating:4.86 Overall Rank:15311]
Valdir Jorge
Canada
Montreal
Quebec
flag msg tools
badge
Avatar
mbmbmbmbmb
Not finished yet but very close. And done by Canadians! Yeah!! Read it all here: http://www.cs.ualberta.ca/~chinook/
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
10. Board Game: Nim [Average Rating:3.88 Overall Rank:14849]
Jody Morgan
United States
Fancy Gap
Virginia
flag msg tools
badge
Avatar
mbmbmbmbmb
WIN: For most starting positions, regardless of whether the object of the game is to take the last stick/counter or to avoid doing so, the first player is able to guarantee victory by playing perfectly; however, there are some starting positions allowing the second player to win with perfect play.

For the starting setup in the picture, for example, the first player should remove three sticks from the top row of four (regardless of whether the object is to take, or avoid taking, the last stick). If the second row had six sticks instead of three, however, the second player could always win with perfect gameplay.

One of many websites where you can try your hand at Nim: http://www.transience.com.au/pearl3.html
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
11. Board Game: Babylon [Average Rating:5.56 Overall Rank:11733]
Stefan Alexander
Canada
Waterloo
ON
flag msg tools
designer
badge
Avatar
mbmb
In this case, the player who goes second is guaranteed a win, with perfect play. Bruno Faidutti (the designer) has links to the solution on his website somewhere:

http://faidutti.free.fr/

(but it's in French).

A good English explanation, though, at the Games Journal:

http://www.thegamesjournal.com/letters/Nov2004.shtml

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
12. Board Game: Solitaire [Average Rating:4.28 Overall Rank:15301]
Olivier Clementin
France
Paris
Paris
flag msg tools
badge
Avatar
mbmbmbmbmb
Player wins

http://en.wikipedia.org/wiki/Solution_to_peg_solitaire
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
13. Board Game: Quarto [Average Rating:6.83 Overall Rank:819]
Mark Goadrich
United States
Conway
Arkansas
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
DRAW: Has 61,152 possible game states. Good references here:

http://ssel.vub.ac.be/Members/LucGoossens/quarto/quartotext....

and here:

http://zoo.cs.yale.edu/classes/cs490/00-01b/kerner.matthew.m...
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
14. Board Game: Simpei [Average Rating:6.02 Overall Rank:10145]
mrbass
United States
Las Vegas
Nevada
flag msg tools
Avatar
mbmbmbmbmb
http://boardgamegeek.com/thread/116277
Solved....2nd player can always win.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
15. Board Game: Hex [Average Rating:6.78 Overall Rank:2550]
Philippe Beaudoin
Canada
Montréal
Québec
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
WIN - first player can always win

This one is interesting though, as we don't have a constructive proof. That is, we know the first player always win, but, apart for small board sizes, we don't know how he should play to win.

The proof uses the strategy stealing argument.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
16. Board Game: Teeko [Average Rating:6.12 Unranked]
Herb
United States
Georgia
flag msg tools
mbmbmbmbmb
From Wikipedia on article on Teeko

"The rules, as summarized above, are very simple, but the strategy is complicated enough to fill a book, Scarne on Teeko, by Scarne (1955). Nonetheless, Guy Steele solved the game (i.e., showed what must occur if both players play wisely) via computer in 1998: he found that neither player can force a win."


Scarne, John (1955). Scarne on Teeko. New York: Crown Publishers.

Steele, Guy (November 23, 1998). Re: Teeko, HAKMEM. E-mail on the math-fun mailing list.

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
17. Board Game: BRIDG-IT [Average Rating:4.95 Overall Rank:13643]
Brian Dysart
United States
San Jose
California
flag msg tools
Win for first player, following intructions linked from the game's page.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
18. Board Game: Fanorona [Average Rating:6.40 Overall Rank:5379]
Ethan Larson
Canada
flag msg tools
designer
Avatar
mbmbmbmbmb
This has been solved.

http://www.unimaas.nl/games/games_fanorona.htm

"This means that we solved all positions with 7 or less pieces on the board and stored that information in a file. It turned out that there exist a total of 6.261.651.660 different positions with 7 or less pieces on the board and the database used 3.6 GB of hard-disk space. The construction of the 4vs3 database alone took more then three weeks. In total more then 2 months were used to compute all endgame databases."
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
19. Board Game: Game of SIM [Average Rating:4.00 Unranked]
Eddy
Germany
flag msg tools
Go Lizards, Go Hogs, Go Illini; and the Army keeps rolling along!
badge
Hillbilly Schwäbisch
Avatar
mbmbmbmbmb
Sim is a pretty intriguing pencil-and-paper game -- simple in concept but profound in its depth. The game has been solved as a win for Player 2.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
Loading... | Locked Hide Show Unlock Lock Comment     View Previous {{limitCount(numprevitems_calculated,commentParams.showcount)}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
{{error.message}}
{{comment.error.message}}
    View More Comments {{limitCount(numnextitems_calculated,commentParams.showcount)}} / {{numnextitems_calculated}} 1 « Pg. {{commentParams.pageid}} » {{data.config.endpage}}
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.