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.

7 comments:

CDP said...

Verrrrry interesting!

Matty Boy said...

A friend told me that last year, checkers was completely solved. Best play produces a draw.

Mathman6293 said...

My mom bought me go when I was a kid but I never learned to play because nobody ever wanted to play it with me.

Art said...

Monte Carlo algorithms are really odd creatures. They're easier to explain than than they initially appear, but they also yield confusing results.

Generally speaking, MC methods start by knowing three things: (1) the number of closely related elements in the system, (2) the starting position of each element and (3) the starting velocity of each element. Given that information, MC methods, track the movement of each element over some period of time.

During that period, each element either deflects in a different, creates a new element (that the MC method must then track), or disappears altogether. At the end of the period, the system may or may not be stable. In most cases, unstable cases stabilize if they are simply given more time.

In nuclear reactor engineering (my field of training), MC simulations help us tell where the power rods should (or should not!) be positioned. In "simpler" endeavors, such as chess and backgammon games, MC methods tell us which moves and counter-moves are most effective.

dguzman said...

Great post, Matty Boy. I had never heard of Go but it sounds like one of those mathy games I wouldn't be too good at. Like, um, almost all games. Gimme a crossword anytime.

Distributorcap said...

matty

question -- you said that for RPS the person should just play each R-P-S one third of the time and randomize -- you and i know both know a human cannot do this -- there is virtually no way over time a human can just randomly do one of the three and have all come to 1/3 -- some sort of pattern will develop.

am i correct?

also how many moves ahead does a computer 'think' in chess.

and how come the idiots who go on Deal or No Deal just dont play the odds. because humans cannot think in terms of logic - only the emotion of winning $1 million from one of the hot chicks

Matty Boy said...

Hey, DCap. Lemme answer some of your questions.

Nothing works better for randomization than a die. Computers or people trying to randomize always create patterns, though they may be very hard to see.

I don't know how far down a decision tree a computer looks in chess. I hear that they have worked out every endgame where both sides have four pieces or less on the board.

I can't even watch Deal or No Deal. If you tell me the contestants are idiots, I will take your word on it.