Luke skywalker has done it again.

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Harvey Williamson, bob

Locked
Rein Halbersma
Posts: 672
Joined: Tue May 22, 2007 9:13 am

Re: Luke skywalker has done it again.

Post by Rein Halbersma » Mon Apr 02, 2012 7:23 pm

Don wrote: In the book One Jump Ahead, Jonathan Schaeffer at some point thought that it might be good enough to say that if you were N checkers ahead you could write the position off as a win - and much to his surprise this was not a valid assumption even for a fairly large number of checkers, and in checkers a single pawn (or checker) ahead is a huge advantage. It's been my experience that no simplistic rule can be reliably used to stop a search without introducing scalability issues - because you will ALWAYS be able to find a position where it is badly wrong! In this study Vas it treating 5.12 as a forward pruning rule to represent a complete search to the end of the game.
Apart from the lame April fools date obfuscation in the piece, the actual numbers already made the story incredible without reading further!

First, the solution space of checkers was 10^22 (the search space was 10^40), which was reduced to 10^14 by a bidirectional search. The back-end search built 10^14 database positions, and the front-end search built 10^14 opening positions. Schaeffer (http://ilk.uvt.nl/icga/journal/pdf/toc30-4.pdf) estimates it would take 200 core years to re-create this solution. Second, Schaeffer also estimates that the solution space for chess is about the square of that of checkers.

How does Vas's claim stack up against this? Hm, about 10 times the computing power but about the square of the search space (10^80 vs 10^40). Being liberal, let's suppose the actual solution space is the square root of that (10^40). However, the efficient bidirectional search (giving almost another square root reduction), was dependent on 10-piece databases which were already reachable from shallow root searches. Without the equivalent chess databases, the 10^40 solution space will not be reduced by another square root. And covering 26 orders of magnitude with 10 times more computing power... :roll:

BTW, the way checkers was solved by Schaeffer et al. was by iterating over the threshold value. So a real proof would take the 5.12 as the first step in such an iteration, and stepwise increase it all the way to a mate score.

Terry McCracken
Posts: 15798
Joined: Wed Aug 01, 2007 2:16 am
Location: Canada

Re: Luke skywalker has done it again.

Post by Terry McCracken » Mon Apr 02, 2012 7:39 pm

Daniel Shawul wrote:Terry postmortem doesn't get you credits.
You were almost 4 hours late to reply :)
I didn't see it till you posted it. I was the first in the thread to reply. I rarely look at Chessbase anymore. Probably that article to attack the ICGA was the final straw.

I believe you could solve an opening in chess only a little more probable than FTL neutrinos.

I'll win the lottery first by finding the winning numbers in a dumpster and I don't look through dumpsters.
Terry McCracken

IanO
Posts: 444
Joined: Wed Mar 08, 2006 8:45 pm
Location: Portland, OR
Contact:

Re: Luke skywalker has done it again.

Post by IanO » Mon Apr 02, 2012 7:53 pm

Whether this is a joke or not, I have long expected computer science research like this to have come out of computer chess. Are any other academic groups working on automatic discovery of opening theory?

User avatar
Dan Honeycutt
Posts: 4995
Joined: Mon Feb 27, 2006 3:31 pm
Location: Atlanta, Georgia

Re: Luke skywalker has done it again.

Post by Dan Honeycutt » Mon Apr 02, 2012 8:04 pm

Daniel Shawul wrote:Terry postmortem doesn't get you credits.
You were almost 4 hours late to reply :)
Where do you get 4 hours? My post headers say 12 minutes.

Good call, Terry.

Best
Dan H.

playjunior
Posts: 338
Joined: Thu Jun 21, 2007 10:53 pm

Re: Luke skywalker has done it again.

Post by playjunior » Mon Apr 02, 2012 8:31 pm

There are 2 things about this article that make it lame. First, it was posted on April 2nd. Second, Chessbase uses Fischer's name in almost every April fools article.

Still, will be fun to read the readers' feedback ;)

Jouni
Posts: 1782
Joined: Wed Mar 08, 2006 7:15 pm

Re: Luke skywalker has done it again.

Post by Jouni » Mon Apr 02, 2012 8:38 pm

This was good joke, when some "experts" here fell for it!
Jouni

Daniel Shawul
Posts: 3429
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Luke skywalker has done it again.

Post by Daniel Shawul » Mon Apr 02, 2012 8:49 pm

Where do you get 4 hours? My post headers say 12 minutes.
Look the headers since our replies to him that it is real NOT his first post. 12:34 - 3:30
Time starts from there and ends on the first evidence Referee. The PGN tag was his input ofcourse. Even he said he didnt see the chessbase article your post is nonsense. Many things have been talked about by that time.

Daniel Shawul
Posts: 3429
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Luke skywalker has done it again.

Post by Daniel Shawul » Mon Apr 02, 2012 8:51 pm

This was good joke, when some "experts" here fell for it!
Could you be more specific as to who fall for it ? :) For me the failures are those who got scared to even post their thought but have much time to do postmortem :)

Daniel Shawul
Posts: 3429
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Luke skywalker has done it again.

Post by Daniel Shawul » Mon Apr 02, 2012 8:53 pm

Someone said in rybka forum that he tried similar stuff but I haven't read his work.
http://rybkaforum.net/cgi-bin/rybkaforu ... ?tid=24668

Terry McCracken
Posts: 15798
Joined: Wed Aug 01, 2007 2:16 am
Location: Canada

Re: Luke skywalker has done it again.

Post by Terry McCracken » Mon Apr 02, 2012 8:59 pm

Daniel Shawul wrote:
Where do you get 4 hours? My post headers say 12 minutes.
Look the headers since our replies to him that it is real NOT his first post. 12:34 - 3:30
Time starts from there and ends on the first evidence Referee. The PGN tag was his input ofcourse. Even he said he didnt see the chessbase article your post is nonsense. Many things have been talked about by that time.
My first post was only minutes after your post...No post mortem!

I'm cynical not naive!
Terry McCracken

Locked