Wednesday, July 2, 2008
Wednesday Math, Vol. 30: Solved games
There are some games that have been solved, which is to say we know exactly the best way to play. For example, there is no particular reason to ever play a game of tic-tac-toe. Whether you like X or O, the correct play is to mark the middle square first. If you play second, mark one of the corners. After that, there is nothing the first player can do that the second player can't effectively counter. From this position, the best plays on both sides end up in a tie game, with no one able to get three in a row.
Rock Paper Scissors is also a solved game, though the definition works differently. If two people want to play until someone wins three times, for example, eventually someone will win. But in the long run, the best strategy is known. Play each choice exactly one third of the time, randomizing your play. If you have a die you could roll without your opponent seeing it, play rock when you roll a 1 or 2, paper when you roll a 3 or 4 and scissors when you roll a 5 or 6. There is no long term strategy that can beat this, and in the long run, this strategy breaks even, neither losing or winning.
Some much more complex games are close to being solved because there are computer programs that play the games very well. Chess probably can't be solved the way tic-tac-toe has been solved, where we can make a list of the correct move in every position, but in competitive chess there is always a time limit involved, and with the speed of computation getting better all the time, computers are getting close to unbeatable, especially at the faster games.
Random games like backgammon and poker are also being analyzed very nearly to the point of being solved. Again, like R-P-S the outcome is in doubt, but the best long run play in every position is becoming less of a mystery. By taking any particular position and either doing the math directly or having a computer simulation play the position countless thousands of times, which is called the Monte Carlo algorithm, we know the probabilities to close to a certainty and with the payoffs, we can define the expected value in every position and make the best play.
Of all the major games of skill, the one that is currently farthest from being solved is the ancient Asian game of go, which is its name in Japanese. Known as wéiqí in Chinese and baduk in Korean, it was invented before the time of Christ. The standard belief is that it was a Chinese game first, but there are some Koreans who claim their culture was the originator. Regardless of origin, Japan is now the center of the go playing world.
There are computer programs that play the game, but they are no match for even an intermediate strength player, even with a time limit. If in my lifetime go is ever "solved" the way chess has been solved, it will take a major mathematical miracle.