Likelihood of Success

Ron Coleman’s pretty good blog

Computer perfectly simulates life

Posted by Ron Coleman on July 19, 2007


In the long run, you can’t win:

Developed by computer scientists at the University of Alberta in Canada, Chinook vanquished human competitors at tournaments more than a decade ago. Now, in an article published today on the Web site of the journal Science, the scientists report that they have rigorously proved that Chinook, in a slightly improved version, cannot ever lose. An opponent, no matter how skilled, practiced or determined, can at best achieve a draw.

In essence, that reduces checkers to the level of tic-tac-toe, where the ideal game-playing strategy has been codified into a series of immutable rules. But checkers — or draughts as it is known in Great Britain — is much more complex, with 500 billion billion theoretically possible board positions; it is the most complex game that has been solved to date.  …

Even with the advances in computers over the past two decades, it is still impossible, in practical terms, to compute moves for all 500 billion billion board positions. Instead, the researchers took the usual starting position and then looked only at the positions that would occur during the normal course of play.

“It’s a computational proof,” Dr. Schaeffer said. “It’s certainly not a formal mathematical proof.”

Hit your head against the wall here.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: