A dominant strategy for checkers, in news@nature:
Long-time world checkers champion Marion Tinsley consistently bested all comers, losing only nine games in the 40 years following his 1954 crowning. He lost his world championship title to a computer program in 1994 and now that same program has become unbeatable; its creators have proved that even a perfectly played game against it will end in a draw.
Jonathan Schaeffer and his team at the University of Alberta, Canada, have been working on their program, called Chinook, since 1989, running calculations on as many as 200 computers simultaneously. Schaeffer has now announced that they have solved the game of American checkers, which is played on an 8 by 8 board and is also known as English draughts.
The team directed Chinook so it didn’t have to go through every one of the 500 billion billion (5 * 10^20) possible moves. Not all losing plays needed to be analysed; instead, for each game position, Chinook needed to work out only a move that would allow it to win. In the end, only 1/5,000,000 of the moves were computed.