Author: Vincent Diepeveen
Date: 08:23:41 01/30/02
Go up one level in this thread
On January 30, 2002 at 11:15:03, Gian-Carlo Pascutto wrote: >On January 30, 2002 at 11:04:18, Vincent Diepeveen wrote: > >>On January 30, 2002 at 10:12:25, Gian-Carlo Pascutto wrote: >> >>>Why are you blindly assuming that their effective branching factor >>>is 40, just because that is the average number of legal chess >>>moves? You should know better. And I know you do. >> >>branching factor is not the issue here GCP and you know it. >>the total number of nodes needed when assuming a theoretical >>minimum here is more important. >> >>Please get your college book again and see that this is about >>the squareroot of the number of legal moves. > >The formula is: > >nodes = (branching factor)^floor(depth/2) + (branching factor)^ceil(depth/2) -1 where branching factor is defined as the number of legal moves. So obviously this is about 2 times more than 40^9. I always said 'about'. It is here about magnitude of nodes, that there is another factor of 2 is not so hard to believe, as you can also add another factor of 10 for qsearch and just check extensions. i'm using (legal moves)^(depth/2) = 40^(18/2) = 40^9 In the Knuth formula there is in fact the statement 2.40^9 - 1 So for the number of nodes i quoted you can add another factor of 2 to that. But a million times more nodes is already more. Now bob uses 4^18 which is bloody nonsense as that would mean that there are on average 16 moves in a position which is not extended. Best regards, Vincent >Your formula is an approximation. > >>The average number of legal moves, not counting checking positions as >>those get extended, it is 40. >> >>so squareroot(40) is what you need for nodes. > >For an alphabeta with perfect move ordering and NO enhancements >whatsoever, yes. But that is not what Deep Blue is. I tested >a comparable version of Sjeng. >I got the number 10-20 out of experimentation, rather than out of my a**. > >>>They used PVS. Aspiration windows. Hashtables for the first TWELVE >>>plies. Even futility pruning. >> >>In 1998 and 1999 it was mentionned by direct postings from Hsu >>and others that they only did a fullwidth search not a single form >>of pruning as they disbelieved this, Bob has quoted that zillions of >>times in these years. > >Bob'll have to be the reference on this, but I always understood they >didn't use any form of pruning except for quiescent futility pruning, >which is what I tested with. > >>>The _worst_ I saw was around 20, on _average_ it was only about 10 or >>>even less. >> >>that would make it 18^20 then in your case = 9^400, >>where i used 18^squareroot(40) = 9^40, get the point? > >Your maths is wrong. So wrong, I suspect you and Bob >attended the same school :) > >-- >GCP
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.