<p>The best known example is probably <em>checkers</em> (also known as <em>draughts</em>), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on <a href="https://en.wikipedia.org/wiki/Solved_games">solved games</a>; notable among them are <em>connect four</em> and <em>nine men's morris</em>. Additionally, several chess endgames have been solved.</p>

<p>This perhaps doesn't seem like an answer to your question, but if an expert (such as <a href="https://en.wikipedia.org/wiki/Marion_Tinsley">Marion Tinsley</a>) loses to a computer program, then the computer must have found a "more optimal" move. </p>

CC BY-SA 3.0
2013-06-13T00:19:06.400Z
2013-06-13T00:19:06.400Z
Yuval Filmus
<p>See Wolfe and Berlekamp -- <a href="http://books.google.com/books?id=Gb0bELsFQn8C&amp;dq=isbn:1568810326&amp;hl=en&amp;sa=X&amp;ei=fEa5UZWUK6OjiAKQ6oDoDw&amp;ved=0CC8Q6AEwAA">Mathematical Go</a>.  Using Conway's theory of games, they show how to analyze certain kinds of Go endgames.  Their solutions turn out to be measurably better than the solutions given by top Go players.  (Not quite an answer to your problem, as those latter solutions were probably never claimed to be optimal.)</p>

CC BY-SA 3.0
2013-07-23T23:55:08.093Z
I'm no Go expert, but my impression of the Mathematical Go work is that it's much more interesting mathematics than it is interesting Go, and that the structures they find - for the most part - don't really correlate with the structures that occur in actual games.  Perhaps someone with more Go experience can speak to this?
Steven Stadnicki
CC BY-SA 3.0
2013-07-25T20:40:44.933Z
Yes, that's more or less my understanding also.
Neal Young
CC BY-SA 3.0
2013-06-13T04:13:37.677Z
2013-06-13T04:13:37.677Z
Neal Young
<p>Chess endgame techniques have been greatly enhanced by the advent of endgame tablebases.  Endgame tablebases are lookup tables that solve chess when there are no more than (currently) seven pieces on the board.  <a href="http://www.k4it.de/index.php?lang=en&amp;topic=egtb" rel="nofollow">Here</a> is an online tablebase I've used in the past that works for up to six pieces.</p>

<p>Algorithmically, these tablebases are not very interesting; they are generated mostly by brute force.  However, they have contributed to several aspects of endgame theory.     Wikipedia has a nice summary of some interesting points <a href="http://en.wikipedia.org/wiki/Chess_endgame#Effect_of_tablebases_on_endgame_theory" rel="nofollow">here.</a></p>

<p>These discoveries also had implications for the "fifty move rule," which states that after fifty moves without a capture or pawn advance, either player can claim a draw.  Even before computer analysis, several endgames were thought to take more than fifty moves, and the rule was slightly extended in those circumstances (probably the most famous is the <a href="http://en.wikipedia.org/wiki/Rook_and_bishop_versus_rook_endgame" rel="nofollow">rook and bishop vs rook endgame</a>).  As the number of positions requiring these moves became larger, these extensions were dropped and the normal 50-move rule was reinstated in all cases.  Modern analysis has shown that some endgames take <a href="http://en.wikipedia.org/wiki/Chess_endgame#Longest_forced_win" rel="nofollow">several hundred moves</a> .</p>

<p><a href="http://chessok.com/?page_id=27966" rel="nofollow">This</a> is another interesting article, summarizing some effects of seven-piece tablebases on endgame theory.  I particularly like the mutual zugzwang shown in the last position.</p>

CC BY-SA 3.0
2014-03-06T18:42:19.097Z
2014-03-06T18:42:19.097Z
SamM
<p>It is not properly a "game strategy", however in 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge found that all 
Rubik's cube positions can be solved with a maximum of 20 face turns using a
computer-assisted proof [1] ... a nice result.</p>

<p>The annotated source code is available at <a href="http://cube20.org/src/" rel="nofollow">http://cube20.org/src/</a>.</p>

<p>The average number of moves taken by standard solving methods is ~50-60, but there is also 
an official <a href="http://www.worldcubeassociation.org/results/e.php?i=333fm" rel="nofollow">"fewest moves" hall of fame</a>:</p>

<pre><code>  #player          #moves
1 Tomoaki Okayama  20  Japan    Czech Open 2012     
2 Moritz Karl      21  Germany  BW Open 2013     
3 István Kocza     22  Hungary  Czech Open 2010     
  Jimmy Coll       22  Belgium  Barcelona Open 2009     
5 Adrian Lehmann   23  Germany  German Open 2013
</code></pre>

<p>(note that the upper bound of 20 was reached only one time in 2012 ... so in Rubik's cube championships humans are far from playing the "optimal strategy" :) </p>

<p>[1] <a href="http://epubs.siam.org/doi/abs/10.1137/120867366" rel="nofollow">Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge: The Diameter of the Rubik's Cube Group Is Twenty. SIAM J. Discrete Math. 27(2): 1082-1105 (2013)</a></p>

CC BY-SA 3.0
2014-03-06T18:53:45.260Z
2014-03-06T19:17:57.327Z
2014-03-06T19:17:57.327Z
Marzio De Biasi
<p>I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.</p>

CC BY-SA 3.0
2013-07-22T21:08:40.190Z
You can't say they're "optimal" strategies, but computers have apparently made a huge difference in chess openings.
Peter Shor 
CC BY-SA 3.0
2013-06-12T21:01:33.143Z
There is no such thing as "more optimal".
Jeffε
<gt.game-theory><board-games><combinatorial-game-theory>
Examples of Computer-Found Optimal Strategies in Games
fkenter
# Examples of Computer-Found Optimal Strategies in Games

(Asked by: username_0 on 2013-06-12)

I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.

**Tags:** gt.game-theory, board-games, combinatorial-game-theory
> **Comments:**
> **username_2**: There is no such thing as "more optimal".  
> **username_1**: You can't say they're "optimal" strategies, but computers have apparently made a huge difference in chess openings.  

---

## 4 answers

### Answer by username_3 on 2013-06-13. Score: 12

The best known example is probably *checkers* (also known as *draughts*), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on [solved games](https://en.wikipedia.org/wiki/Solved_games); notable among them are *connect four* and *nine men's morris*. Additionally, several chess endgames have been solved.

This perhaps doesn't seem like an answer to your question, but if an expert (such as [Marion Tinsley](https://en.wikipedia.org/wiki/Marion_Tinsley)) loses to a computer program, then the computer must have found a "more optimal" move.


---

### Answer by username_4 on 2013-06-13. Score: 8

See Wolfe and Berlekamp -- [Mathematical Go](http://books.google.com/books?id=Gb0bELsFQn8C&dq=isbn:1568810326&hl=en&sa=X&ei=fEa5UZWUK6OjiAKQ6oDoDw&ved=0CC8Q6AEwAA). Using Conway's theory of games, they show how to analyze certain kinds of Go endgames. Their solutions turn out to be measurably better than the solutions given by top Go players. (Not quite an answer to your problem, as those latter solutions were probably never claimed to be optimal.)

> **Comments:**
> **username_5**: I'm no Go expert, but my impression of the Mathematical Go work is that it's much more interesting mathematics than it is interesting Go, and that the structures they find - for the most part - don't really correlate with the structures that occur in actual games.  Perhaps someone with more Go experience can speak to this?  
> **username_4**: Yes, that's more or less my understanding also.  

---

### Answer by username_6 on 2014-03-06. Score: 1

Chess endgame techniques have been greatly enhanced by the advent of endgame tablebases. Endgame tablebases are lookup tables that solve chess when there are no more than (currently) seven pieces on the board. [Here](http://www.k4it.de/index.php?lang=en&topic=egtb) is an online tablebase I've used in the past that works for up to six pieces.

Algorithmically, these tablebases are not very interesting; they are generated mostly by brute force. However, they have contributed to several aspects of endgame theory. Wikipedia has a nice summary of some interesting points [here.](http://en.wikipedia.org/wiki/Chess_endgame#Effect_of_tablebases_on_endgame_theory)

These discoveries also had implications for the "fifty move rule," which states that after fifty moves without a capture or pawn advance, either player can claim a draw. Even before computer analysis, several endgames were thought to take more than fifty moves, and the rule was slightly extended in those circumstances (probably the most famous is the [rook and bishop vs rook endgame](http://en.wikipedia.org/wiki/Rook_and_bishop_versus_rook_endgame)). As the number of positions requiring these moves became larger, these extensions were dropped and the normal 50-move rule was reinstated in all cases. Modern analysis has shown that some endgames take [several hundred moves](http://en.wikipedia.org/wiki/Chess_endgame#Longest_forced_win) .

[This](http://chessok.com/?page_id=27966) is another interesting article, summarizing some effects of seven-piece tablebases on endgame theory. I particularly like the mutual zugzwang shown in the last position.


---

### Answer by username_7 on 2014-03-06. Score: 1

It is not properly a "game strategy", however in 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge found that all 
Rubik's cube positions can be solved with a maximum of 20 face turns using a
computer-assisted proof [1] ... a nice result.
The annotated source code is available at http://cube20.org/src/.
The average number of moves taken by standard solving methods is ~50-60, but there is also 
an official "fewest moves" hall of fame:
  #player          #moves
1 Tomoaki Okayama  20  Japan    Czech Open 2012     
2 Moritz Karl      21  Germany  BW Open 2013     
3 István Kocza     22  Hungary  Czech Open 2010     
  Jimmy Coll       22  Belgium  Barcelona Open 2009     
5 Adrian Lehmann   23  Germany  German Open 2013

(note that the upper bound of 20 was reached only one time in 2012 ... so in Rubik's cube championships humans are far from playing the "optimal strategy" :) 
[1] Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge: The Diameter of the Rubik's Cube Group Is Twenty. SIAM J. Discrete Math. 27(2): 1082-1105 (2013)


---

