 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
| HomeDiscussion GroupsGeneral TopicsAnalysisComputerChess Politics ChessKB.com Contact UsLink To UsSearch & Site Map |
Chess Forum / General Topics / July 2007Checkers is solved
Computer Program Can't Lose at Checkers By RANDOLPH E. SCHMID WASHINGTON (AP) - Perhaps Chinook, the checker-playing computer program, should be renamed ``King Me.'' 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 athousand 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. http://netscape.compuserve.com/news/story.jsp?floc=ne-main-9-l7&idq=/ff/story/00 01%2F20070720%2F0119365665.htm&sc=1333 > Computer Program Can't Lose at Checkers > By RANDOLPH E. SCHMID [quoted text clipped - 8 lines] > > http://netscape.compuserve.com/news/story.jsp?floc=ne-main-9-l7&idq=/... That link asks for a password. To my mind, "solving" checkers would not simply mean being able to handle any human or present computer opponent without losing; instead, I want to have every legal checkers position scored as a win/loss/draw, by calculating every simpler position that can arise from it and so forth; like the endgame tablebases in chess. I suppose you would begin with the simplest positions, and work backwards, adding more and more for many years until one day, your efforts suddenly hit a wall -- having tackled every legal position and tallied the results. Although checkers uses a similar board to chess, only half the squares are actually used; critically, since every man moves and captures the same way (until a promotion at least), this should be much easier than solving chess. Also, many of the possible moves of a random checker will be blocked, reducing further the possible legal moves. I am wondering whether they really "solved" the game or, as the chosen language suggests, they merely succeeded in never losing in practice. -- help bot Since checkers can be shown to end in a draw (both white and black are guaranteed a draw with perfect play), it is considered weakly solved. Checkers is so far the "largest" of the board games to show this, I believe. > To my mind, "solving" checkers would not simply mean being able to > handle any human or present computer opponent without losing; They've done much more than that! They've demonstrated that the game can be held to a draw against any possible opponent. > instead, I want to have every legal checkers position scored as a > win/loss/draw, by calculating every simpler position that can arise > from it and so forth; like the endgame tablebases in chess. That is a slightly stronger condition and I'm not sure exactly what the UAlberta guys have done. At the very least, they can tell you whether any position that can be reached from the initial position according to the replies they would make is a win, loss or draw. (In chess terms, if their computer would play 1.d4 all the time, it might not be able to tell you about unreachable positions such as that after 1.e4.) > Although checkers uses a similar board to chess, only half the > squares are actually used; critically, since every man moves and > captures the same way (until a promotion at least), this should be > much easier than solving chess. Also, many of the possible moves of > a random checker will be blocked, reducing further the possible > legal moves. Yes, checkers is very, very much simpler than chess. But it's still a pretty complex game and far more complex than anything that's been solved before. > I am wondering whether they really "solved" the game or, as the > chosen language suggests, they merely succeeded in never losing in > practice. They're claiming in scientific journals that they've solved it. Nobody publish that claim if all they'd done was produce a very very strong engine. Dave.  SignatureDavid Richerby Hilarious Solar-Powered Clock (TM): www.chiark.greenend.org.uk/~davidr/ it's like a clock but it doesn't work in the dark and it's a bundle of laughs! > That is a slightly stronger condition and I'm not sure exactly what > the UAlberta guys have done. At the very least, they can tell you [quoted text clipped - 3 lines] > not be able to tell you about unreachable positions such as that after > 1.e4.) I didn't read the link because I would have to sign up and go through all that junk, just to read about checkers. :>D > Yes, checkers is very, very much simpler than chess. But it's still a > pretty complex game and far more complex than anything that's been > solved before. Except... the human genome, for instance. And developing "the bomb". The thing is, checkers is a finite problem, so, unlike exploring space, you know exactly how far you have to go to the end. > > I am wondering whether they really "solved" the game or, as the > > chosen language suggests, they merely succeeded in never losing in [quoted text clipped - 3 lines] > Nobody publish that claim if all they'd done was produce a very very > strong engine. Sanny would. And Sam Sloan. And Weaver Adams. -- help bot > I am wondering whether they really "solved" the > game or, as the chosen language suggests, they > merely succeeded in never losing in practice. The last report I read said that checkers has been "weakly solved". Positions with 10 checkers or fewer are completely solved. I don't know how to reconcile this with the quote "the initial position is a draw". I suspect it's a slight mis-quote. I can imagine a claim that "the program can achieve at least a draw" - but that's not quite the same thing. SignatureKenneth Sloan KennethRSloan@gmail.com Computer and Information Sciences +1-205-932-2213 University of Alabama at Birmingham FAX +1-205-934-5473 Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/ >> I am wondering whether they really "solved" the >> game or, as the chosen language suggests, they [quoted text clipped - 7 lines] > that "the program can achieve at least a draw" - but that's not quite > the same thing. Now that's just silly. What was I thinking... SignatureKenneth Sloan KennethRSloan@gmail.com Computer and Information Sciences +1-205-932-2213 University of Alabama at Birmingham FAX +1-205-934-5473 Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/ > To my mind, "solving" checkers would not simply > mean being able to handle any human or present [quoted text clipped - 7 lines] > your efforts suddenly hit a wall -- having tackled > every legal position and tallied the results. They've done this. Checkers is solved. > In article <1184919926.968955.198...@d55g2000hsg.googlegroups.com>, > [quoted text clipped - 13 lines] > > Checkers is solved. So why are there people here saying just the opposite? Adding on qualifiers? "Solved", to me, means that every legal position has a known result, and that every legal move leads to another position which has a known result, and every capture yields a simpler position, with a known result. NOT just having a computer which can't be beaten (like say, Rybka). In chess, which has been worked on for many decades, they max out at about only seven men on the board! Add one lousy isolated, blockaded, worthless Rook-pawn, and the program draws a complete blank, requiring human intelligence to intervene (as with the Whitaker game, which I knew was a win, though not an easy one). At the beginning of a game of checkers, there are 24 men on the board, but most of them are blocked and can't yet move. If, when a man reached the last row it merely scored a point and then was removed, this would be fairly simple, but instead the darned things promote to Kings, which can move backwards. So, you get repetitions of position (yeck). -- help bot >> Computer Program Can't Lose at Checkers >> By RANDOLPH E. SCHMID [quoted text clipped - 3 lines] > That link asks for a password. >Computer Program Can't Lose at Checkers Here is a yahoo link: http://news.yahoo.com/s/ap/20070719/ap_on_hi_te/solving_checkers Doesn't need a password. Interesting news. Fred >>> Computer Program Can't Lose at Checkers >>> By RANDOLPH E. SCHMID [quoted text clipped - 13 lines] > > Fred "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." I hope there's more than this - or that this is a bad paraphrase. Of course it "matter(s) how the players make it to 10 checkers". Surely SOME positions with 10 checkers are lost, no? We now need a proof that a player CAN, in fact, always manage to reach a 10-checker position that happens to be drawn with best play. I'm certain that this proof must be in the full paper. Can someone who has actually read the paper please supply the missing steps? Actually, what I'd love to see is an example of a "well-balanced" 10-checker position that is NOT drawn with best play. SignatureKenneth Sloan KennethRSloan@gmail.com Computer and Information Sciences +1-205-932-2213 University of Alabama at Birmingham FAX +1-205-934-5473 Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/ > > Here is a yahoo link: > > >http://news.yahoo.com/s/ap/20070719/ap_on_hi_te/solving_checkers > > > Doesn't need a password. > "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 [quoted text clipped - 21 lines] > Actually, what I'd love to see is an example of a "well-balanced" > 10-checker position that is NOT drawn with best play. It looks to me like yet another case of empty hype. The article on Yahoo! says that they have only solved checkers with ten or fewer men on the board. More than ten, and they are in the same boat as Rybka and Ace Ventura -- they are the best there is, but hardly perfect. The article blames a lack of computer power for their failure to "solve" checkers; in short, they must be doing a brute force approach, like Conan the Barbarian or the world hot-dog-eating champion. Still, when it comes to this sort of thing, there is no besting IM Innes or Sanny or Sam Sloan -- they are the real Aces of hype. -- help bot > It looks to me like yet another case of empty hype. I disagree. It looks to me like bad reporting. this research team is rock solid and I trust their papers. the trouble is - all I've seen so far are the news reports - NOT the paper. I'm objecting to the gloss - not questioning the result. SignatureKenneth Sloan KennethRSloan@gmail.com Computer and Information Sciences +1-205-932-2213 University of Alabama at Birmingham FAX +1-205-934-5473 Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/ > > It looks to me like yet another case of empty hype. > > I disagree. It looks to me like bad reporting. That is precisely what I mean by empty hype. > this research team is rock solid and I trust their papers. My take is that possibly the use of a technical term, to mean "only partly solved" was the reason so many reporters keep mucking things up. > the trouble is - all I've seen so > far are the news reports - NOT the paper. Indeed, all you really need to see is the link which admitted that they have only solved for ten men or fewer. Logic tells us that since there are 24 men at the beginning of each game, they cannot have truly solved checkers. An interesting thing is that they have decided to move on... blaming a lack of computer power for this partial failure. > I'm objecting to the gloss - not questioning the result. I'm noting the hype, and how easily many people are confused by the misuse of the term "solved". -- help bot >> this research team is rock solid and I trust their papers. > > My take is that possibly the use of a technical term, > to mean "only partly solved" was the reason so many > reporters keep mucking things up. They wouldn't be publishing partial results in _Science_ under the title ``Checkers is Solved.'' What you are doing is taking a journalist's garbled description of Schaeffer et al.'s work, and saying ``That doesn't work. Therefore the claim is false.'' This is unreasonable and unfair. What Schaeffer actually seems to have done is developed 10-man tablebases and then searched from the initial 24-man position to give a drawing strategy for white for every position that is consistent with the strategy. See http://chinook.cs.ualberta.ca/users/chinook/index.html for a demonstration. Dave. SignatureDavid Richerby Accelerated Tongs (TM): it's like a www.chiark.greenend.org.uk/~davidr/ pair of tongs but it's twice as fast! >>> this research team is rock solid and I trust their papers. >> My take is that possibly the use of a technical term, [quoted text clipped - 18 lines] > > Dave. a) don't believe everything you read in "Science" b) we don't want a demonstration - we want a proof. SignatureKenneth Sloan KennethRSloan@gmail.com Computer and Information Sciences +1-205-932-2213 University of Alabama at Birmingham FAX +1-205-934-5473 Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/ >> They wouldn't be publishing partial results in _Science_ under the >> title ``Checkers is Solved.'' [...] See >> http://chinook.cs.ualberta.ca/users/chinook/index.html >> for a demonstration. > > a) don't believe everything you read in "Science" Of course. > b) we don't want a demonstration - we want a proof. Of course. But the paper hasn't been published yet and isn't available on the project website. So that's all there is for the time being. But I suspect the proof will consist of ``We ran the initial position through this big alpha-beta search using ten-man tablebases to evaluate the leaves and it said `draw'.'' It's hard to imagine any other sort of proof for something so big. It is, after all, essentially just the case-split of the century. Dave. SignatureDavid Richerby Love Tool (TM): it's like a hammer www.chiark.greenend.org.uk/~davidr/ that you can share with someone special! >>> They wouldn't be publishing partial results in _Science_ under the >>> title ``Checkers is Solved.'' [...] See [quoted text clipped - 8 lines] > Of course. But the paper hasn't been published yet and isn't > available on the project website. In which case, it's perhaps wise to wait before making announcemens, making claims, and certainly before trying to evaluate the claims. Perhaps we should just wait for the paper and then read it. Unless, of course, one has seen a review copy - but it would be unethical to base any comments on such a source, right? > So that's all there is for the time > being. But I suspect the proof will consist of ``We ran the initial > position through this big alpha-beta search using ten-man tablebases > to evaluate the leaves and it said `draw'.'' It's hard to imagine any > other sort of proof for something so big. It is, after all, > essentially just the case-split of the century. I wonder if that part of the tree that they expanded will fit in one issue of "Science". SignatureKenneth Sloan KennethRSloan@gmail.com Computer and Information Sciences +1-205-932-2213 University of Alabama at Birmingham FAX +1-205-934-5473 Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/ >> Of course. But the paper hasn't been published yet and isn't >> available on the project website. > > In which case, it's perhaps wise to wait before making announcemens, The point at which the paper is accepted sounds like a reasonable time to announce the result, to me. Ordinarily, one would put a copy on one's website but perhaps _Science_ are stricter about that than most other journals? > Perhaps we should just wait for the paper and then read it. Of course. > Unless, of course, one has seen a review copy - but it would be > unethical to base any comments on such a source, right? For the record, I have not seen the paper, in any form. > I wonder if that part of the tree that they expanded will fit in one > issue of "Science". Not sure. But it's perfectly normal not to print the raw data... Dave. SignatureDavid Richerby Portable Erotic Atlas (TM): it's like www.chiark.greenend.org.uk/~davidr/ a map of the world but it's genuinely erotic and you can take it anywhere! >>> Of course. But the paper hasn't been published yet and isn't >>> available on the project website. [quoted text clipped - 18 lines] > > Not sure. But it's perfectly normal not to print the raw data... Have you actually READ articles in "Science"? > Dave. SignatureKenneth Sloan KennethRSloan@gmail.com Computer and Information Sciences +1-205-932-2213 University of Alabama at Birmingham FAX +1-205-934-5473 Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/ On Jul 21, 7:05 pm, David Richerby <dav...@chiark.greenend.org.uk> wrote: > > My take is that possibly the use of a technical term, > > to mean "only partly solved" was the reason so many > > reporters keep mucking things up. > They wouldn't be publishing partial results in _Science_ under the > title ``Checkers is Solved.'' As I have not seen that magazine, I have no idea whether or not "they" (whoever they are) would likely place such an article under such a name. > What you are doing is taking a journalist's garbled description of > Schaeffer et al.'s work, and saying ``That doesn't work. Therefore > the claim is false.'' This is unreasonable and unfair. What is unreasonable (and silly, actually), is taking anything I wrote as pertaining to Science magazine, rather than the articles at the links posted here in this thread. > What Schaeffer actually seems to have done is developed 10-man > tablebases and then searched from the initial 24-man position to give [quoted text clipped - 4 lines] > > for a demonstration. Interesting. This "strategy" was never mentioned in the article I read; that article stated flatly that the "scientists" were moving on, having settled on a partial solving of checkers, and placing the blame for their partial failure on a lack of computer power. Note that I complained about the first link in this thread requiring a password, so I of course am talking about the other link, which did not. BTW, if someone wrote here that "scientists" had "solved" chess, I would rush right out and buy the magazine; but as for checkers... . -- help bot > > Computer Program Can't Lose at Checkers > > By RANDOLPH E. SCHMID [quoted text clipped - 34 lines] > game or, as the chosen language suggests, they > merely succeeded in never losing in practice. I would also wonder what rules were in effect when the game of Checkers was reportedly solved. Specifically, did they use the mandatory capture or optional capture rules? Mandatory capture apparently allows for "huffing", that is, one player can remove an opponent palyer's checker that did not make a capture when had an open opportunity to capture. >Specifically, did they use the mandatory capture or optional capture rules? English draughts / American checkers rules. http://en.wikipedia.org/wiki/Draughts >Mandatory capture apparently allows for "huffing", that is, one player can >remove an opponent palyer's checker that did not make a capture when had an >open opportunity to capture. I believe that tournament rules only allow the opponent to point out that an illegal move was made, with the usual touch rules. |
Reply to this Message |
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2010 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.