Author: Robert Hyatt
Date: 19:50:30 12/21/99
Go up one level in this thread
On December 21, 1999 at 21:55:35, Vincent Diepeveen wrote: >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. Hsu has reported 30%. IE with 100 processors it runs 30 times faster than with one. I have seen nothing where he claims anything other than that... > >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. Does that really matter? they are doing _way_ more in the first N plies than you do... I have seen their results on several of the Nolot positions with old hardware. I'd suspect DB2 probably solves them all (assuming all have legit solutions, which is not a given) in tournament time limits, although I have no direct knowledge that suggests that. It doesn't really matter whether you extend 40 plies and then have a simple final 4 plies, or extend way less and then extend more in the last 4 plies. It is the overall depth that is the issue. They aren't lacking there... > >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. They are not talking about 40 plies max in bizarre paths. They are talking about 40 plies along the _important_ lines. There is a difference. I hit beyond 50 plies all the time. But that doesn't mean a thing. I have _seen_ (with my own eyes) how well they search tactically. Against my old program, and against others like *Socrates. They were _dynamite_. lots of handwaving and blustering won't change that at all, any more than it changes the fact that they are the _only_ program to ever beat Kasparov in a match, they will likely be the only program for _many_ years to accomplish that. Until micro programs can win game 6 from the white side, I won't be impressed at all. Once they can, then at least they will begin to have some chess skill/understanding... > >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. > > without null-move I'll bet it is over 3. Or else _very_ selective, which they definitely aren't. >>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. singular extensions aren't in the hardware, but others are... > >>>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. > They didn't leave out check extensions. That was the first problem they fixed with the first version of DB processors. Later versions also included repetition detection which the first didn't. It _always_ had the check extensions, as belle did that and the original DB was "belle on a chip". >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. Baloney. I saw them extend beyond 30 plies with a forced variation against my program. They saw something about 10 full moves before we saw it. I saw this against other programs... And every time you extend a ply, you _still_ have 6 plies left. Just look at how far you extend in _your_ program. I find mates in 10 at depth=6 all the time, and I don't do _any_ checks in the q-search at all. It is not hard to extend that far... > >>>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. Their margin was about 1/3 of a pawn. I will retrieve the actual value tomorrow, but I think it was 38, with a pawn=128. > >This obviously means it's giving tactical a little bit, but >do youplay better chess by being tactical a bit stronger? _yes_ > >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.