Author: Vincent Diepeveen
Date: 12:53:51 01/30/02
Go up one level in this thread
On January 30, 2002 at 14:06:04, Uri Blass 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 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. >> >>>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. >> >>Now in 2002 to explain some theoretical impossibilities a pruning >>technique for QUIESCENCESEARCH is getting quoted, don't confuse that >>with the alfabeta search. >> >>>I tested this. I crippled my program. No hashing in the last 6 plies, >>>no nullmove, no pruning except futility, all extensions on. >> >>>I didn't get an effective branching factor of 40. Far from it. >> >>>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? > >I also believe that deeper blue could not search 18 plies but your numbers are >wrong >18^(squareroot(40))<9^40 Yes sorry there is a small mistake here. I mean squareroot(40) ^ 18 is their total tree this is the same as 40^9 which is the number as i calculated upon. So it is 40^9 not 9^40 i was talking about. >Without hash tables even if we assume perfect move ordering it is easy to see >that the theoretic limit under some reasonable assumption is too high(even if >you assume 25 nodes per position(in the middle game there are usually more than >it) you get >25^(18/2)=25^9 and it is clear that deeper blue could not search 25^9 nodes >even at 10^9 nodes per second. >I see no mathematical proof that 18 plies of brute force search is impossible >when hash tables are used but I believe that it is practically impossible. without hashtables deep blue searched last 6 plies and before that it used all kind of extensions and it didn't forward prune a single node even, except perhaps in qsearch on alfa and beta (note that pruning on alpha there is very dubious, but that fits in the picture of a guy who is just creating a machine that overpowers everything in nodes a second but not in search depth). >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.