games.slashdot.org/article.pl?sid=07/07/19/1952211
From the game's 500 billion billion positions (5 * 10^20), 'Chinook' has determined which 100,000 billion (10^14) are needed for their proof, and run through all relevant decision trees.
ever since the swelling of Chess's "opening book" began. They randomise starting back-rank positions now in some tournaments, to stave off the eventual "book death" that has already conquered checkers.
you have any idea how badly their server is going to be slashdotted now? It's bad enough when its a php driven webpage but now you've just encouraged slashdotters to try a game or two against it. if the server crashes in the middle of a game is it considered a win for the human player?
They claim the best you can do is draw against chinook in deterministic checkers. The Times points out that: The new research proves that Chinook is invincible in the traditional game of checkers. But in most tournament play, a match starts with three moves chosen at random. In solving the traditional game, the researchers have also solved 21 of the 156 three-move openings, leaving a crack of hope for humans, at least for now.
When I click on the proof, all I get is a Java error saying "Unable to connect to server". While the inability to connect to the Checkers server may make it "Unbeatable" in a Wargames-esque "the only way to win is not to play" kind of way, it's kind of a cop-out.
entry: The most popular forms are international draughts, played on a 1010 board, followed by English draughts, also called American checkers that is played on an 88 board, but there are many other variants.
net/) Hasn't it always been fairly easy for a computer to beat a human at checkers? I don't recall it making the news the first time deep blue beat the world grand master at checkers.
Schaeffer has a book out ("One Jump Ahead") about writing Chinook. He thought the same when he started, but the project got rapidly far harder than he thought. It helped that the existing human champion (Marion Tinsley) was literally as close to perfection as any human has ever been at any game- they exhaustively studied every professional game he ever played and found something like a grand total of 10 actual mistakes in a 40 year career. It's a very sad book in many ways- there was a lot of tension between certain members of the team and you realized that professional checkers was dying rapidly. Tinsley and Schaffer set up a world championship rematch between them (Tinsely won the first one) and Tinsely pulled out after six games saying he felt ill. He checked himself into the hospital, was diagnosed with some aggressive form of cancer and died a few months later. Schaeffer basically retired Chinook from human tournaments since nobody else was even remotely close to Tinsley. It didn't make many headlines because everyone knows checkers is easy.
org/drDugan/) So, I've struggled with the issue of the really large numbers in game AI problems. In go, for example, there are about 10^170 possible legal board layouts for the 19x19 board. There are (esitmiated) only about 10^81 atoms in the universe. Do all of the 10^170 positions exist in any meaningful way? It is impossible to count, enumerate, or articulate them all? Getting the point back to chess, these folks have done a similar thing - it seems they articulated 1/10000th or so of the legal boards and used it to "prove" something about the whole space. After about 3-5 moves in their java applet, I found moves that could make sense that there not in their "legal" moves database.
I've been trying to convince my chess-playing friends that someday computers will be (literally) unbeatable at the game, but they've always been skeptical. Like TFA says, there are a finite number of positions and if the computer can store and map all non-losing paths through all of them, the game is solved. Now interestingly, it sounds like they short cut that strategy by excluding positions reached by moves that this machine will never make and significantly reduced the number of "possible" positions that way. So I wonder if this means their program can't win from an otherwise winnable position, because that position isn't in it's database.
Friday July 16, @09:05PM) The day an automaton is "unbeatable" is the day it's 500ft tall and shoots nuclear rockets from its fingertips. I think I know a relatively easy way to beat this checkers program.
Back in 1972 when HAKMEM was written, the AI Lab folks estimated a year or so of computer time then, I'm guessing, given how long has passed, that this was a bit optimistic.
That was never a rule in any game of checkers I've played before. I just know that if there were a chess version of this with a forced capture rule, people would be screaming blood muder.
|
http://csua.com/feed/