EPTI thought it was going to be some clever algorithm, too bad.
Scientists 'solve' checkers - Page 2
| Forum Index > General Forum |
|
HeadBangaa
United States6512 Posts
I thought it was going to be some clever algorithm, too bad. | ||
|
Maenander
Germany4926 Posts
On July 21 2007 14:24 IIICodeIIIIIII wrote: have one computer play white. have the other play black in another window. you know what i'm getting at... They draw, afaik there is always a possibility for draw and the computer will find it. So only a human, who makes mistakes, can lose ... and there is no human player who makes no mistakes. | ||
|
mahnini
United States6862 Posts
On July 21 2007 18:07 HeadBangaa wrote: Wow they really brute-forced this. I thought it was going to be some clever algorithm, too bad. What? | ||
|
gravity
Australia1734 Posts
On July 21 2007 18:36 Maenander wrote: They draw, afaik there is always a possibility for draw and the computer will find it. So only a human, who makes mistakes, can lose ... and there is no human player who makes no mistakes. It should be easy to draw with the computer since you just have to memorize a drawing game and then play it since the computer will always play the same (best) moves in response to yours. | ||
|
{CC}StealthBlue
United States41117 Posts
| ||
|
haduken
Australia8267 Posts
brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. | ||
|
HaXxorIzed
Australia8434 Posts
| ||
|
SoMuchBetter
Australia10606 Posts
On July 21 2007 14:54 CharlieMurphy wrote: Most of us have been playing Starcraft for 9-10 years. Its not that much a difference. Wow, also on that site it lists other games that have been solved. My Gf thinks shes the shit at connect 4, I'll rape her every time now. http://homepages.cwi.nl/~tromp/c4/c4.html http://img264.imageshack.us/my.php?image=necksnappedeznf6.jpg ohh yeahhhhh | ||
|
ToT)OjKa(
Korea (South)2437 Posts
program noob dodger | ||
|
BlackJack
United States10209 Posts
On July 21 2007 16:02 JeeJee wrote: captures are forced in checkers=/ you only have 1 option, capture the white piece, at which point he will counter-capture 3 of yours and it spirals down from there Triple jump to the face. King me. | ||
|
CoralReefer
Canada2069 Posts
On July 22 2007 01:13 haduken wrote: brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. Brute force means trying every possible combination. This means that every move in every possible game has been stored in a database, the trick is just to follow the path leading to the best outcome. Similarly, there is an algorithm for Tic Tac Toe which will always lead to a draw (or a win if your opponent makes a mistake). | ||
|
mdb
Bulgaria4059 Posts
| ||
MasterOfChaos
Germany2896 Posts
| ||
|
Jathin
United States3505 Posts
| ||
|
sc0rchedst0rm
Ireland176 Posts
On July 22 2007 01:24 HaXxorIzed wrote: IIRC Go would eat any computer that was competent at Chess/Checkers alive, or is my memory poor? A computer that's competent at Go is a pretty rare thing, there's so many possibilities they have trouble comprehending it. And yes, Chess is "solvable" the same way Checkers is, there's just a hell of a lot more permutations (in the order of 10^40 or even more, as said). Go on the other hand, while still "solvable", you're looking at 10^600 or even more iirc. | ||
Bill307
Canada9103 Posts
On July 22 2007 13:24 Jathin wrote: Devising algorithms that leave portions of the tree out aren't actively used I don't think. I think I read somewhere that it's easier/more fool-proof/just as efficient to do brute-force (or a modification of the such, like brute force after a certain point) http://en.wikipedia.org/wiki/Chess_computers You heard wrong. Heuristics are crucially important to chess-playing programs. Edit: I read parts of the article and I think what they're saying is, it's a bad idea to try to prune branches from the tree without at least searching part-way down those branches first. But after searching part-way they may see that one branch is (almost) definitely going to lead to a worse position than another, and so they don't need to analyse the rest of that branch. That's basically the effect of doing alpha-beta pruning. Chess programs employ other heuristics, too, but I am not familiar with them. On July 21 2007 18:07 HeadBangaa wrote: Wow they really brute-forced this. I thought it was going to be some clever algorithm, too bad. It wasn't completely brute-force. Chinook first figured out that of the 5 * 10^20 possible positions in checkers, only 10^14 needed to be analysed. Then it brute-forced those 10^14 positions. (It didn't need to analyse every move because many moves lead to losing positions, and so there's no point in analysing them when Chinook will never play those moves.) | ||
|
Maenander
Germany4926 Posts
On July 21 2007 23:14 gravity wrote: It should be easy to draw with the computer since you just have to memorize a drawing game and then play it since the computer will always play the same (best) moves in response to yours. Yeah and it is just as easy to let the program vary its moves by some kind of random number generator. I think it is likely there are different ways to reach a non-losable position for the program in most situations ^^ | ||
|
Bill307
Canada9103 Posts
On July 21 2007 23:14 gravity wrote: It should be easy to draw with the computer since you just have to memorize a drawing game and then play it since the computer will always play the same (best) moves in response to yours. True but, apparently in professional tournaments the first 3 moves are selected at random, so you would have to memorize a draw for each possible starting position. Furthermore, what if the computer can take more than one move that leads to a draw? Then it might pick one at random. | ||
|
Bill307
Canada9103 Posts
Referring to a match between Tinsley and Chinook in 1994 (at which time Chinook had opening and ending databases but had not solved the mid-game of checkers), I found the following quote: Also present in the room is a mild-looking retired professor of mathematics. He wears a light blue suit and tie-pin with "Jesus" written on it in colored rhinestones. He doesn't look like the sort of man to acquire a nickname like "The Terrible Tinsley." But Marion Tinsley's benign exterior cloaks a formidable intellect. At age 27, he was the best checkers player in the world, and by all accounts his game has only improved during the forty intervening years. His record is unparalleled in checkers, chess, or any other game of skill. To get an idea of the embarrassingly wide margin by which Tinsley surpasses his nearest competition, consider his defense of the world title in 1989 against the challenger Paul Davis. Tinsley drew 23 games, won 9, and lost 0. During his forty-year reign, and over the course of over a thousand games of tournament play, Tinsley has lost exactly nine games. It's hard to come up with anyone who has so thoroughly dominated a field of human endeavor for such a long stretch of time. http://www.math.wisc.edu/~propp/chinook.html Just to reiterate that, his last human challenger lost 9 games out of 32 against Tinsley, whereas Tinsley has lost 9 games out of one thousand throughout his entire career. I also liked this post on Slashdot: No. 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. Except that they are wrong- it's not.  | ||
|
mahnini
United States6862 Posts
On July 22 2007 01:13 haduken wrote: brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. I understand the difference, I just don't understand how you would solve checkers without brute-forcing, as if some algorithm could be thought up without first brute-forcing it. | ||
| ||
![[image loading]](http://i8.tinypic.com/66lh1t3.jpg)
