Author: Robert Hyatt
Date: 20:21:35 01/30/02
Go up one level in this thread
On January 30, 2002 at 12:52:14, Ed Schröder wrote: >On January 30, 2002 at 09:43:49, Vincent Diepeveen wrote: > >>Hello, >> >>I would like to adress some major nonsense about search depth >>deep blue. >> >>First of all, we know that deep blue was doing only fullwidth >>with loads of extensions. >> >>a) 12(6) doesn't mean they searched 18 ply. It means they searched >> 12 plies fullwidth from which 6 ply in hardware > >Agreed Vincent. 18 plies brute force is impossible. 12 plies brute force fits. > >Ed > based on what? Cray Blitz, using null-move R=1, non-recursive (one null move along any path, period, which made the search go about 25% faster overall was quite capable of searching 12 plies. It searched 10 plies at 200K nodes per second. DB was only 1000 times faster. Could it _really_ only search 2 plies deeper? I don't think so... > > >>Nevertheless Bob again claims it is 18 ply fullwidth. Note that he >>bases his claim on an EMAILED and not PUBLISHED statement from a >>non-programmer who said it was Deep Thought printing stuff out >>like that. Note that the only published depth is 12 ply in IEEE99, >>an OFFICIAL document. >> >>Let's assume Bob as only defender from IBM is right, >>let's do some math on the MINIMUM number of nodes >>they would need for a 18 ply search. >> >>Also we know they didn't use a hashtable in hardware. >> >>It is not amazing to see that in the complex middlegame Deep Blue searched >>just as deep as in the far endgame, about 11(6) to 12(6). >> >>That means Knuth's lemma is of course working for them, otherwise >>they would have searched many plies deeper in endgames. >> >>Knuths lemma says that you need about the square root of the average >>number of moves for even depths. >> >>Now everyone can easily figure out what the average number of legal moves >>is (considering they extend checks so these positions do not count) >> >>This was measured by me at 40. There i am the only person here >>who recently >>measured this, the previous measurement of 35 was INCLUDING checks >>and is like 50 years old, and was just saying something about >>positions in GM games, >>it is obviously logical that 40 is pretty true in the middlegame. >> >>Note that >>in this math we assume a PERFECT move ordering, we do not count >>the huge number of nodes singular extensions need and we do forget >>the fact that deep blue proved in the games tactical weaker than >>crafty would be at 15 ply even, whereas the truth is that they DID >>do some extensions of course, it's even mentionned that in the software >>part they did do 'dangerous extensions'. >> >>For a 18 ply fullwidth search: squareroot (40^18) = 40^9 >> = 262,144,000,000,000 >> >>Now we know Deep Blue ran at 200M nodes a second, which from >>hardware viewpoint is an incredible achievement and the only >>thing IBM cared for. IBM *never* said something about searching >>deeper. >> >>So for a 18 ply search the theoretical minimum would have been >>(assuming 100% speedup from deep blue, whereas in reality they >>wrote down they got 20% out of it this was published in IEEE99 >>by Hsu): >> >>262144000000000 / 200,000,000 nodes a second = 1310720 seconds >>needed to get 18 ply >> >>We definitely need to note that in 1995 not a single program with mobility >>did get *near* 11 or 12 ply at 3 minutes a move, not even WITH nullmove. >> >>Even in 1997 it was a pain to reach 11 to 12 ply with just nullmove for >>programs with mobility. >> >>Only years after that things happened soon and fast, but a single email >>from a person who didn't make the chip is quoted by Bob and believed >>by some idiots here who are bad in math. >> >>18 ply fullwidth without hashtable is unreachable CCC audience, with >>nullmove things change rapid however. This is why nullmove earns the >>nobel prize and the defense of deep blue must admit that in 2002 >>it is hard to say that a program that just searched fullwidth and >>which was promoted only by nodes a second, that it got 11 to 12 ply >>and not 17 to 18. 12 ply is in fact already a real good search >>depth fullwidth, if i let diep search fullwidth WITH hashtables and >>singular extensions, then i don't even get over 10 ply in fact. >> >>The reason is real easy. I do my singular extensions also 4 ply from the >>leafs, whereas DB 'only' did it 7 ply from the leafs. If never forward >>pruning is used (like nullmove R=3 as i use in DIEP) it is simply >>impossible to explain the huge problems singular extensions cause. >> >>Best regards, >>Vincent Diepeveen
This page took 0.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.