Author: blass uri
Date: 15:54:58 11/24/98
Go up one level in this thread
On November 24, 1998 at 17:43:11, Robert Hyatt wrote: >On November 24, 1998 at 09:59:02, Amir Ban wrote: > >>On November 24, 1998 at 08:40:01, Robert Hyatt wrote: >> >>>On November 24, 1998 at 03:14:02, Christophe Theron wrote: >>> >>>>On November 23, 1998 at 22:38:17, Robert Hyatt wrote: >>>> >>>>>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? >>>> >>>>I don't want to go into a heated discussion, but I notice: >>>> >>>>A program that does no forward pruning has a branching factor of (roughly) 5. >>>> >>>>A program that uses null move has a branching factor of (roughly) 3. >>>> >>>> (5^10) / (3^10) = 165.38 >>>> >>>>Weren't you looking for a factor of 150 or so ? >>>> >>>>If the IBM team is interested I can provide some help for their null move >>>>implementation. This way we could have the power of Deeper Blue with only one of >>>>their chip stuffed into a simple PC. :) >>>> >>>> >>>> Christophe >>> >>> >>>One minor flaw in this discussion. :) Neither Junior *nor* Deep Blue use >>>null-move. *now* how would you explain that factor of 1,000? >>> >>>Bob >> >> >>It seems you agree with Christophe's math. Strange because 10 minutes earlier in >>another post you said the opposite: >> >>Quote: >> >>>>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 ? >>> > > >Sorry... didn't mean to imply that... I was responding to his null-move >point only. *no* null move is *not* exponential... and it is quite easy >to figure this out. If your branching factor is 3.0, null move makes you >about 10X faster... because you lop off 2 plies here and there with R=2. >Which is why I said "about 10X". I can certainly provide some real data if >you'd like to see this... but otherwise wouldn't we keep getting *faster* as >we go deeper? Doesn't work like that. And that factor of 168 would be *very* >useful because that translates into log base 3 of 160 which would *five* more >plies? Sounds good to me. *too* good. :) > > >IE I can run crafty with null off and null on to depth=5, then 6, then 7, >and so forth... and show that rough factor of 10x or so carries from >iteration to iteration. > >here's a sample, position about 15 moves into a normal game: >with null on: 8 plies 8 seconds, 9 plies 40 seconds. null off: >8 plies 110 seconds 410 seconds.. may not be a good case as odd things >happen with null on and off... but that is a "trend"... > > >>>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. >> >>End quote. >> >>But this doesn't concern me. In fact I no longer understand what the problem is >>here. What factor of 1000 about Junior needs to be explained, and why ? > >Here, again: If we take Rebel, or any program without null-move, they are >currently searching to about 10 plies in 3-5 minutes. At least that is >what I see running rebel on my P6/200. And seems to be what Crafty might >do with a decent hash table (above numbers were with default which is small, >I didn't think about that, so the non-null search got zapped a bit due to >overrunning the hash table.) So.. 10 plies at 80-100K nodes per second. >DB is doing 10-11 at 250M nodes per second. *that* is the factor of 1,000 >(actually 2,500) that I am looking at. How come they don't get any deeper >than rebel (nominal depth) (which I assume is somehow equivalent to the >depth you reach although you count things differently) yet they are searching >2500 times faster? > >*that* is the question. I propose that they *must* be doing far more extensions >than we are doing, to consume that many nodes to reach that nominal search >depth... > > >> >>To recap: The argument was if the search trees of PC programs and Junior in >>particular are deeper and thinner in comparison to the Deep Blue search tree. >> >>Bob said that the fact that DB reaches 10-11 ply is proof that this is not so. I >>believe he said that because he knows that null-movers can match this nominal >>depth in about equal time (but about 1000 lower NPS). Christophe's math shows >>why, and incidentally confirms the point for null-movers. > > >Nope... his math doesn't work, and a trivial inspection shows why. You >lose two plies here and there. But I certainly don't get a factor of 100x >faster. Above numbers support that. And rebel/deep blue/junior don't use >null-move, so I don't see the connection anyway... > >Note that I changed to "rebel" because ed reports "traditional plies" which >can be directly compared. Your programs seem similar in strength, so I assume >your "different" numbers are somehow similar. > >> >>Junior doesn't match this nominal depth (would be depth 19-21 for Junior), so >>there is no factor to explain. Junior is more aggressively extended than most PC >>programs, and therefore more than DB. >> >>Amir > > >how deep would you go if you were 1000 times faster? And compare *that* to >deep blue's numbers that you have there. I say their number will be much >*less* than yours, even after your correct for half-plies. And if that is >true, then *they* must be extending more than you. My complete point... Their number is similiar and not much less. It depends on the position but on my hardware(pentium200MMX) it needs sometime some hours to finish depth 18(9 plies) they serch 2000 times faster than Junior5 on pentium200MMX so I need to search 100 hours. I did not try to see what happen after 100 hours but if I assume that I need one hour to get 9 plies and I assume a factor of 5 then I get 12 plies after 125 hours and they got 11-12 plies Uri
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.