Author: Uri Blass
Date: 11:06:04 01/30/02
Go up one level in this thread
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 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. 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.