TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Rein Halbersma

Joined: 22 May 2007
Posts: 241

Post subject: Re: Luke skywalker has done it again.    Posted: 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...

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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Daniel Shawul Mon Apr 02, 2012 12:15 pm
Terry McCracken Mon Apr 02, 2012 12:27 pm
Julien MARCEL Mon Apr 02, 2012 12:34 pm
Daniel Shawul Mon Apr 02, 2012 12:34 pm
Jimmy Huggins Mon Apr 02, 2012 12:42 pm
Daniel Shawul Mon Apr 02, 2012 12:46 pm
Don Dailey Mon Apr 02, 2012 2:59 pm
Terry McCracken Mon Apr 02, 2012 3:30 pm
Daniel Shawul Mon Apr 02, 2012 7:07 pm
Terry McCracken Mon Apr 02, 2012 7:39 pm
Dan Honeycutt Mon Apr 02, 2012 8:04 pm
Andranik Khachatryan Mon Apr 02, 2012 8:31 pm
Jouni Uski Mon Apr 02, 2012 8:38 pm
Daniel Shawul Mon Apr 02, 2012 8:51 pm
Don Dailey Mon Apr 02, 2012 9:04 pm
Graham Banks Mon Apr 02, 2012 10:35 pm
Daniel Shawul Mon Apr 02, 2012 8:49 pm
Terry McCracken Mon Apr 02, 2012 8:59 pm
Daniel Shawul Mon Apr 02, 2012 9:06 pm
Dan Honeycutt Mon Apr 02, 2012 10:29 pm
Daniel Shawul Mon Apr 02, 2012 10:56 pm
Dan Honeycutt Mon Apr 02, 2012 11:26 pm
Daniel Shawul Mon Apr 02, 2012 11:34 pm
Jef Kaan Tue Apr 03, 2012 12:17 am
Daniel Shawul Tue Apr 03, 2012 12:22 am
Jef Kaan Tue Apr 03, 2012 12:47 am
Daniel Shawul Tue Apr 03, 2012 12:53 am
Sam Hamilton Tue Apr 03, 2012 1:21 am
Daniel Shawul Tue Apr 03, 2012 8:02 am
Terry McCracken Tue Apr 03, 2012 4:06 am
Terry McCracken Tue Apr 03, 2012 12:32 am
Daniel Shawul Tue Apr 03, 2012 12:40 am
Dan Honeycutt Mon Apr 02, 2012 10:26 pm
Ricardo Barreira Mon Apr 02, 2012 2:30 pm
Daniel Shawul Mon Apr 02, 2012 3:00 pm
Ricardo Barreira Mon Apr 02, 2012 3:08 pm
Don Dailey Mon Apr 02, 2012 3:30 pm
Re: Luke skywalker has done it again. Rein Halbersma Mon Apr 02, 2012 7:23 pm
Rein Halbersma Wed Apr 04, 2012 2:46 pm
Daniel Shawul Wed Apr 04, 2012 3:02 pm
Daniel Shawul Wed Apr 04, 2012 4:10 pm
Terry McCracken Wed Apr 04, 2012 4:29 pm
Daniel Shawul Wed Apr 04, 2012 4:34 pm
Terry McCracken Wed Apr 04, 2012 4:50 pm
Daniel Shawul Wed Apr 04, 2012 4:59 pm
Julien MARCEL Wed Apr 04, 2012 5:15 pm
Terry McCracken Wed Apr 04, 2012 5:22 pm
Julien MARCEL Wed Apr 04, 2012 5:40 pm
Terry McCracken Wed Apr 04, 2012 5:51 pm
Dan Honeycutt Fri Apr 06, 2012 4:38 am
Daniel Shawul Fri Apr 06, 2012 9:17 am
Dan Honeycutt Fri Apr 06, 2012 12:21 pm
Daniel Shawul Fri Apr 06, 2012 12:42 pm
Dan Honeycutt Fri Apr 06, 2012 2:00 pm
Daniel Shawul Fri Apr 06, 2012 2:10 pm
Terry McCracken Fri Apr 06, 2012 6:51 pm
Daniel Shawul Fri Apr 06, 2012 7:10 pm
Miguel A. Ballicora Fri Apr 06, 2012 7:15 pm
Daniel Shawul Wed Apr 04, 2012 9:54 pm
Daniel Shawul Wed Apr 04, 2012 10:30 pm
Marco Costalba Thu Apr 05, 2012 4:40 am
Mark Mason Thu Apr 05, 2012 7:46 am
Daniel Shawul Thu Apr 05, 2012 9:08 am
Mark Mason Fri Apr 06, 2012 7:37 am
Daniel Shawul Fri Apr 06, 2012 9:22 am
Mark Mason Fri Apr 06, 2012 11:28 am
Daniel Shawul Fri Apr 06, 2012 12:19 pm
Daniel Shawul Thu Apr 05, 2012 9:03 am
Don Dailey Mon Apr 02, 2012 3:09 pm
Carl Bicknell Mon Apr 02, 2012 3:16 pm
Terry McCracken Mon Apr 02, 2012 3:37 pm
Albert Silver Mon Apr 02, 2012 1:39 pm
Terry McCracken Mon Apr 02, 2012 3:31 pm
Graham Banks Mon Apr 02, 2012 6:41 pm
Don Dailey Mon Apr 02, 2012 1:37 pm
Terry McCracken Mon Apr 02, 2012 3:32 pm
gerold daniels Mon Apr 02, 2012 1:56 pm
Don Dailey Mon Apr 02, 2012 2:33 pm
Miguel A. Ballicora Mon Apr 02, 2012 2:45 pm
Julien MARCEL Mon Apr 02, 2012 2:59 pm
Terry McCracken Mon Apr 02, 2012 3:50 pm
Don Dailey Mon Apr 02, 2012 4:34 pm
Terry McCracken Mon Apr 02, 2012 6:58 pm
Miguel A. Ballicora Mon Apr 02, 2012 6:47 pm
Don Dailey Mon Apr 02, 2012 6:52 pm
Graham Banks Mon Apr 02, 2012 6:55 pm
Terry McCracken Mon Apr 02, 2012 7:02 pm
Adam Hair Tue Apr 03, 2012 2:05 am
Uri Blass Tue Apr 03, 2012 6:00 am
Don Dailey Tue Apr 03, 2012 11:40 am
Rodolfo Leoni Tue Apr 03, 2012 12:11 pm
Uri Blass Tue Apr 03, 2012 2:51 pm
Vincent Diepeveen Tue Apr 03, 2012 9:42 am
Thorsten Czub Tue Apr 03, 2012 9:44 am
Marco Costalba Tue Apr 03, 2012 5:59 pm
Alex Newman Mon Apr 02, 2012 5:22 pm
Ricardo Barreira Mon Apr 02, 2012 5:51 pm
Gunnar Harms Mon Apr 02, 2012 5:59 pm
Ricardo Barreira Mon Apr 02, 2012 6:01 pm
Gunnar Harms Mon Apr 02, 2012 6:13 pm
Miguel A. Ballicora Mon Apr 02, 2012 6:50 pm
Jorge Pichard Tue Apr 03, 2012 1:37 am
Graham Banks Mon Apr 02, 2012 6:44 pm
Terry McCracken Mon Apr 02, 2012 7:04 pm
Ian Osgood Mon Apr 02, 2012 7:53 pm
Daniel Shawul Mon Apr 02, 2012 8:53 pm
George Speight Tue Apr 03, 2012 5:11 pm
Terry McCracken Tue Apr 03, 2012 5:15 pm
Don Dailey Tue Apr 03, 2012 5:38 pm
Sam Hamilton Tue Apr 03, 2012 5:45 pm
Vincent Diepeveen Tue Apr 03, 2012 5:46 pm
Terry McCracken Tue Apr 03, 2012 6:12 pm
Julien MARCEL Wed Apr 04, 2012 7:09 am
Mark Mason Wed Apr 04, 2012 10:52 am
Albert Silver Wed Apr 04, 2012 1:28 pm
gerold daniels Wed Apr 04, 2012 2:00 pm
Daniel Shawul Wed Apr 04, 2012 2:29 pm
Albert Silver Wed Apr 04, 2012 3:08 pm
Daniel Shawul Wed Apr 04, 2012 3:30 pm
Terry McCracken Wed Apr 04, 2012 4:16 pm
Daniel Shawul Wed Apr 04, 2012 4:31 pm
Terry McCracken Wed Apr 04, 2012 4:53 pm
Daniel Shawul Wed Apr 04, 2012 5:15 pm
Terry McCracken Wed Apr 04, 2012 5:21 pm
Daniel Shawul Wed Apr 04, 2012 5:29 pm
Brent M Wed Apr 04, 2012 5:47 pm
Daniel Shawul Wed Apr 04, 2012 6:09 pm
Terry McCracken Wed Apr 04, 2012 5:48 pm
Daniel Shawul Wed Apr 04, 2012 6:06 pm
Terry McCracken Wed Apr 04, 2012 6:36 pm
Daniel Shawul Wed Apr 04, 2012 6:54 pm
Terry McCracken Wed Apr 04, 2012 7:03 pm
Uri Blass Wed Apr 04, 2012 9:36 pm
Daniel Shawul Wed Apr 04, 2012 9:57 pm
Uri Blass Thu Apr 05, 2012 7:54 am
Daniel Shawul Thu Apr 05, 2012 9:17 am
Vincent Diepeveen Wed Apr 04, 2012 11:56 am
Julien MARCEL Wed Apr 04, 2012 12:00 pm
George Speight Fri Apr 06, 2012 4:24 am

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum