Author: Vincent Diepeveen
Date: 18:55:35 12/21/99
Go up one level in this thread
On December 21, 1999 at 20:37:35, Jeremiah Penery wrote: >On December 21, 1999 at 15:34:26, Vincent Diepeveen wrote: > >>How efficient was the search of Deep Blue? >>Let's compare Diep searching FULLWIDTH (so no pruning at all!) >>with Deep Blue fullwidth. > >I hope you're including turning off Null-Move also? of course. >>Hsu writes in a paper that Deep Blue searched near 1 billion nodes a second >>but never came over that number. > >1 billion nodes was the maximum possible speed from the processors. When >parallel loss is factored in, along with other speed losses in this case, DB was >really only getting around 200M NPS in the games. Sorry, but that doesn't count. Apart from that, i heart a claim they got effective speedup of 40% out of 480 processors, but i don't remember it very well. 40% from 1 billion would be 400 million, which is not 200 million either. >>At a machine never getting 1 billion but getting over it, let's say >>800 million nodes a second, which just starts with 12 ply after more >>than 3 minutes, we talk about next estimation: >> 3 minutes * 800 M/s = 180 * 800,000,000 = 144 billion nodes >With the real speed DB was getting, it's more like 45 billion nodes in 3 >minutes. (@250M NPS, which is still probably higher than it was truly getting.) > >> Diep needs 49957263 nodes. Let's see how many more nodes Deep Blue >> needed: >> 144 B / 50M = 144000 / 50 = 2880 times more nodes needed by Deep Blue. > >Should read: 45B/50M=900 900 is still a HUGE margin for a few forced move extensions. >>In the same article Hsu writes that in the hardware deep blue isn't doing >>forced moves extensions, so that means that this search of DIEP picks up >>a lot of more tactics there, where i'm doing ESPECIALLY near my leafs >>extensions. > >They were doing the singular extensions in software, but many of the other >extensions in hardware. They didn't just use the "extend 1 ply" stuff, either. >In many cases, DB was extending multiple plies along singular lines. In the >average position, it was around 11-12 ply full-width, with well over 40 ply >extended. That's quite a lot of extensions. I'm doing way more in the last 4 ply than that. That 40 ply extended is a peanut. I get that at 9 ply depth already or something. I'm storing in DIEP the deepest lines it sees... ...the 40 ply is a big BS story of course. this is not the depth that's effective. Of course the average line is not 40 ply. It's positional seeing 12 ply. of course the just extend totally 1 ply is not true. That is not true in DIEP either. We're all not counting checks anyway of course. >>So branching factor is about 3 of DIEP in this position (obviously >>because most lines lead to an endgame). > >Again, I hope null-move is turned off? Yes of course. >>Let's now see how deep DIEP would search with bf=3 with 144 billion nodes. >> extra depth = log( 144000/520 ) / log ( 3 ) = 5.12 ply >> >>So 13 ply + 5 ply = 18 ply. > >>Diep would finish 18 ply here fullwidth, starting with 19. > >Assuming a relatively constant branching factor of 3... Transpositions take care it won't get worse. >>Compare that with Deep Blue getting 11 ply here fullwidth, this considering >>that in the leafs DIEP sees a lot more than Deep Blue. > >How do you know Diep sees "a lot more" than DB does in the leaves? Diep is doing doing threat extensions in the leafs (passed pawns only though as mating and such is not included as nullmove can't detect them because it's turned off). Hsu writes forced move extensions are turned off. >>Now you might cry about DIEP not having singular extensions? >>Well that's no problem. In the 11 ply search deep blue got, it could >>only extend 11 - 5 = 6 ply (not extending in root i suppose and for sure >>not extending last 4 ply in hardware). Secondly i remember some work >>done on extensions that prevents it from keeping extending the same move. >>So Deep Blue would see (not counting checks of course as those get >>extended anyway in both programs): 11 + 6 = 17 ply at maximum. > >This is grossly wrong. See above my comment on DB's extensions. Not when you leaf out check extensions. I know this is hard to imagine for you, but it's a simple deduction. Also in 6 ply of course it's actually near to impossible when fiddling with alfa and beta to get 6 singular moves in a row. If you get 3 singular extensions at 6 ply then it's already an incredible forced line. >>Now DIEP searches without singular extensions with the same number of nodes >>another ply deeper, not to mention that interesting lines don't have too >>much singular extensions! >The interesting lines should have the most singular extensions, or else they're >not the most interesting...? The whole deep blue story is getting weird. Singular extensions with the 2*S margin they're using is only gonna detect big tactics and attacks on king. This obviously means it's giving tactical a little bit, but do youplay better chess by being tactical a bit stronger? If i get 18 ply fullwidth against deep blue 11 fullwidth, does this mean that singular extensions see tactical also more on average? We're not even talking about positoinal depth here. It's OBVIOUS that positionally 18 ply is a lot more than 11 ply with a few extensions inside 6 ply of the search, knowing that this 6 ply is the most uninteresting part to extend. You want to extend inside that last 4 ply especially so that something not falling within your horizon still falls inside horizon. Let's investigate some tricks in later emails assuming an 10 or 11 ply search. If you already don't get deep in that position... Vincent
This page took 0 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.