ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Luke skywalker has done it again.
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: General Topics Flat
View previous topic :: View next topic  
Author Message
Rein Halbersma



Joined: 22 May 2007
Posts: 241
PostPost subject: Re: Luke skywalker has done it again.    Posted: Mon Apr 02, 2012 7:23 pm Reply to topic Reply with quote
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... Rolling Eyes

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

 
Jump to:  
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




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads