Posted on 07/20/2007 6:37:43 PM PDT by rawhide
Canadian researchers report they have "solved" checkers, developing a program that cannot lose in a game popular with young and old alike for more than a thousand years.
"The program can achieve at least a draw against any opponent, playing either the black or white pieces," the researchers say in this week's online edition of the journal Science.
In the past, game-playing programs have used rules of thumb — which are right most of the time, he said — to make decisions.
"What we've done is show that you can take nontrivial problems, very large problems, and you can do the same kind of reasoning with perfection. There is no error in the Chinook result. ... Every decision point is 100 percent."
Schaeffer's team started with the end of a game with just one checker on the board. Then the team looked at every possible position with two checkers, on up to 10 checkers on the board.
Every combination of 10 checkers offers 39 trillion positions for the endgame, he said. Chinook can calculate them all.
It does not matter how the players make it to 10 checkers left because from that point on, the computer cannot lose, Schaeffer said.
For two players who never make a mistake, every game would be a draw, he said.
(Excerpt) Read more at foxnews.com ...
I bet it loses when I get frustrated and uninstall its ass from Add/Remove programs! :O)
I thought some time ago it was solvable in a reasonable time — of course I was not ambitious enough to actually program it. There are less than 5^32 possible boards (red king, red pawn, black pawn, black king, blank square), red men <= 12, black men <= 12.
A really good checkers player disagreed with me though.
Chess will require heuristics for some time, I think...
By my understanding of the article, they’re saying that they’ve classified every position of ten checkers as being a win for white, a win for black, and a draw; they’re assuming that if both sides play reasonably the game will not end up in any of the ten-piece positions which is a win for white or black. That’s probably true, but I’m curious what sort of formal argument one would use to show that one side couldn’t force the game to either end up in one of the ten-piece positions where he would be victorious, or for that matter to end up in an eleven- or twelve-piece position where he’d already won (the latter, of course, would seem pretty unlikely).
Maybe an easy way is to compare it to tic-tac-toe. Here there are less than 9*3 = 27 possible boards instead of something less than (5)^32.
You can easily list them out.
Intelligent play by both players will always lead to a draw.
I was thinking you could hold each board in a 16-byte structure. Use 4 bits to encode each square — red king, red pawn, black king, black pawn, empty square. Of course that takes only 3 bits, so you’d have 32 bits left over. Use one to say whose turn it is.
Then start building the game tree.
Spock will be able to prove that the ships computer was tampered with after successfully beating the computer at a game of checkers.
No wait that was tri-dimensional chess.
Hmmm...I never quite followed that one. In fact I was unable to do the Cracker Barrel peg game. I sat down and wrote a program to solve it. My program spit out solutions left and right.
I guess the Vulcan mind operates differently from the human mind.
So why not replace the ship’s computer with a team of Vulcans?
Probably because the vulcans were far to logical to ever agree to it ;-)
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.