|
Checkers solved; Rubik's cube algorithm improved
|
News
|
By overconvergent
from the solving hard problems with lots of computer power department
Posted Fri Sep 14, 2007 at 12:51:36 PM PDT
|
|
A research programme that has been running since 1989 has proved that, with perfect play on both sides, the game of checkers is a draw. Also, it has now been proved that Rubik's cube can be solved in at most 26 moves.
Post a Comment
|
| Certain other games had been proved to be drawn with best play before; tic-tac-toe can be analyzed easily by hand, Connect Four is rather harder, but checkers is the most complicated game to be completely analyzed so far. The proof that checkers is drawn is actually an explicit strategy; it is not a mere existence proof.
The next game for which this is likely to be done is the game Othello; it is felt likely that this is also drawn with best play. Chess will be much harder; a different order of magnitude of work.
The previous best maximum number of moves to solve the Rubik's cube (from any position) was 27; intensive number-crunching with a supercomputer reduced this to 26, by first showing that most positions could be easily solved in 26 moves or less, and then concentrating on the small remainder. It is thought that the actual minimum number is in the ``low twenties''. |
|
|
