Perfect game (idea)

Is there always a perfect game?

Some games of course cannot be played perfectly. An example of this is Freecell. Despite the claims in the Windows help file that it is believed (but not proven) that it is possible to win every game, some deals are impossible. The first such deal to be found is number 11982 and was discovered in 1995.

Complete information games that are dynamic and finite have perfect games. This means that the players have a complete knowledge of the situation, that players take turns and that the game has a well defined end. In chess for example both of the players have all the information available to them: the positions of the pieces on the board. Chess without the draw by repetition rule or connect four without a limit on the number of rows, would be non finite. In poker information is not shared, players do not show each other their cards. Games like backgammon are not complete information games because players cannot know what the next dice roll will be. Lastly stone paper scissors is not dynamic, because both players make their move at the same time and their decision is revealed simultaneously.

There's a perfect game of chess? I'm off to play the world champion!

Finding how to play a perfect game is difficult. Although many games such as chess, checkers or go can in theory be played perfectly, the complexity and sheer number of possible moves of the games often puts a brute force approach far beyond the possibilities of current computers. Awari, a variant of mancala was recently solved, and an unbeatable opponent known as the Awari Oracle is now available. To gauge the scale of things, this program plays with the aid of a 778 gigabyte database of positions and moves. For some other games (notable checkers and othello) there have been some very good attempts.

Chinook for example is a checkers playing program developed by Dr. Jonathan Schaeffer, and is currently the world champion. It plays with a database of all possible positions with 8 or less pieces of the board (that's around 444 billion positions). You can play a cut down version of Chinook (the database has only positions with 6 pieces) at http://www.cs.ualberta.ca/~chinook/play.php. Ultimately the team hopes to completely solve the game.

Choose carefully...

For some games if both players play a perfect game then the result will be a draw. Noughts and crosses is such a game, with a simple strategy: go for the centre first, followed by the corners (unless of course you are forced to make a certain move to avoid losing). If both players do this, then the outcome will always be a draw, and you cannot beat someone playing this strategy. In other games a perfect game is playable by only one of the players. For example it has been shown that in connect four, if there is not the option of passing a turn, the player who moves first can always win. No matter what the second player does, they cannot win.

Finally a little puzzler: This little 2 player game starts with the numbers 2,3,4,5,6,7,8,9,10. Each player picks a number in turn, and once a number is picked it may not be picked again by either player. The aim of the game is to pick exactly three numbers whose sum is 18. It is possible for there to be a draw. Can you play a perfect game?