Thursday, September 13, 2007

Checkers is solved!

Imagine my surprise when I read this headline in this week's Science magazine.

Turns out computers have been working on it for years. The question:

What would happen in a game of checkers if both players play perfectly (no mistakes, anticipating the other's moves)?

In tic-tac-toe, the result is known - a draw, unless the first player (X) wins by choosing a corner for the first move.

How did they do it? They calculated the number of possible positions with up to 24 checkers (which is the mind-boggling number 500,995,484,682,338,672,639). Then they disregarded the positions that don't make sense (like jumping across the board, which you can't do) and found a "best path" of positions. They did this by playing forward (just playing) and by playing backward (imagining the end and extrapolating the moves in reverse).

And the result: A perfect play by both sides (no mistakes!) results in (tada!) a draw.

Hmm. Kind of a disappointment, yet an amazing mathematical discovery, and the most complex game solved so far.

In the past they have also done Connect Four - first player can force a win. They've also solved a whole bunch of games I haven't heard of :)

Makes me wonder if perfect play by more complex games results in either a first player win or draw. No wonder there was such a fight over eenie-meenie-miney-moe!

Water Week Eco-tip: How do you brush your teeth - with the water running? Instead, fill a cup with water and use it to wet your brush. You can rinse out your mouth, the sink, and brush with the cup of water at the end. Compared to leaving the water running, you save at least 10 gallons over a 2 minute brush, or 2 gallons even if you only let the water run at the beginning and end. Even if you only brush once a day, that saves you 730-3650 gallons a year!

No comments: