Examples of Computer-Found Optimal Strategies in Games

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.

• There is no such thing as "more optimal". Jun 12 '13 at 21:01
• You can't say they're "optimal" strategies, but computers have apparently made a huge difference in chess openings. Jul 22 '13 at 21:08

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; 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) loses to a computer program, then the computer must have found a "more optimal" move.

See Wolfe and Berlekamp -- Mathematical Go. 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.)

• 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? Jul 23 '13 at 23:55
• Yes, that's more or less my understanding also. Jul 25 '13 at 20:40

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 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.

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). 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 .

This 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.

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" :)