Author: Robert Hyatt
Date: 05:29:12 11/24/98
Go up one level in this thread
On November 24, 1998 at 04:20:33, Amir Ban wrote: >On November 23, 1998 at 22:38:17, Robert Hyatt wrote: > >>On November 23, 1998 at 17:49:30, Amir Ban wrote: >> > >>I'll play that game. we are talking about a factor of 1,000. You implied >>this could easily be explained by their not doing null-move or other forward- >>pruning tricks? That is your explanation? >> >>I'd like to suggest you break out the calculator. Null move does *not* >>reduce the search by a factor of 1,000. Not by a factor of 100. Generally >>not by a factor of 10. So, I re-ask... if they are only searching to 10 >>plies, *why* does it take them so many nodes to get to ply=10. Want some >>math? perfect tree ought to be 2*38^5 moves. They search that many nodes in >>under 1 second (that is about 160M nodes). Most agree that current programs >>search within a factor of two of the optimal tree size (references available >>if needed). so lets say they can fully search this tree in 1 second, even >>assuming imperfect ordering... Now, again, I'd like to ask the >>*same* question again, and this time get a *reasonable* answer: >> >> >> >>If they take (say) 5 minutes to do a 10 ply search, at 250M+ nodes per second, >>that is over 300X the number of nodes a full-width search to depth=10 should >>search. If you factor in a q-search that is the same size as the full-width >>part, we have a missing factor of 150 to account for. I say that is *all* >>search extensions. And I say that is *far* more than any of the rest of us do >>in terms of extensions. How *else* would you characterize this? >> > >1. I'm not an expert on null-move, but I got the impression that it buys much >more than a factor of 10 at great depths. The factor should be an exponential >anyway, no ? yes, but so is the tree... the result is linear. It (R=2, recursive) is worth about 2 plies (maybe less) in the opening/middlegame, more in the endgame. But not a factor of 10. At least for my implementation... > >2. Programs are within a factor of 2 of optimal tree size ? I don't believe >this. I don't think I am there. Perhaps your references talk about 4-5 ply >searches ? Anyway, this factor also needs to be written as an exponential. > >3. You neglect the parallel overhead (factor of 3-4 according to a recent post). I corrected that post. There are two issues on this NPS stuff with DB. 1. they *should* search 1B nodes per second (512 processors times 2.4 million nodes per second per CPU). Hsu claims they average 250M nodes per second. That is where the 1/4 comes from. 2. In results obtained by me (crafty and Cray Blitz), Cilkchess, and others, the typical overhead is 30% per processor. IE Crafty is about 1.7X faster on two processors, about 2.4X faster on 3, about 3.1X faster on 4, and so forth, thru 8 from personal testing, and thru 16 taking someone else's data. There is nothing to make this get worse the way DB implemented the parallel search (You can find details in Hsu's thesis, for example, or in the DTS paper in JICCA on Cray Blitz). And even *if* they had a factor of 4 for overhead, which I *really* doubt unless we start at the 1B nps number, we aren't close to their speed yet. IE they are 1,000 times faster. we reduce that by 4, so we get 250. Where does that 250X go? You *have* to attribute this to either (a) doing useless work or (b) extending significantly. (a) isn't happening at a rate of more than 50% of total nodes searched, probably less. The only program I know of that might hit 50% overhead would be Cray Blitz because it was specifically designed around a "small" number of processors (64 max) and would need some serious work to go beyond that as interference becomes an issue. Crafty wasn't designed like that at all. DB wasn't either because they knew they would have a bunch of processors one day... > >4. You underestimate the Deeper Blue depth. In fact I see one move doing 11 ply >in 6:56 minutes, and another is 12 ply in 3:19. > >So I don't see a problem in the numbers. 11 plies is about 6x more work than 10 plies. 10 plies about 1/2 second at their current speed. 11 plies is therefore 3 seconds or so. So there is *still* a problem with the numbers... > >Amir
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.