Author: José de Jesús García Ruvalcaba
Date: 07:01:39 03/07/00
Go up one level in this thread
On March 07, 2000 at 07:48:21, Jan Pernicka wrote: >On March 06, 2000 at 06:25:00, blass uri wrote: > >>On March 06, 2000 at 06:00:20, Jan Pernicka wrote: >> >>>On March 03, 2000 at 15:53:31, blass uri wrote: >>> >>>>Suppose you have a program with evaluation of 0.00 for every position so the >>>>order of moves is always perfect. >>>>Suppose this program does no prunning and no extensions. >>>> >>>>What is the branching factor of this program and how many nodes does it need to >>>>search to get 17 plies in the positions that deeper blue is supposed to get 17 >>>>plies with no prunning and a lot of extensions? >>>> >>>>It seems to me that it is impossible with no hash tables to get 17 plies in 3 >>>>minutes even if you can search 200,000,000 nodes/second,have a perfect order of >>>>moves and do no extensions. >>>> >>>>Hash tables can help to reduce the branching factor but how much do they help? >>>> >>> >>> Hi, >>>let's suppose that at every position you have w moves to choose and you >>>don't use any hashtables. Then (it's well known) - when using alpha-beta >>>prunning - your branching factor is something like sqrt(w) - i.e square >>>root, when searching to the depth d (still the same, no extensions...), >>>you have to examine about d^(w/2) (leaf) positions (x^y means "x powered to >>>y"), so you can estimate how long does it take (for your program) to search >>>17 plies ahead... Simply said - you can search two times deeper... >> >>I think that the formula is sqrt(w)^d=w^(d/2) >> >>If w=36 in the middle game then the formula is 6^d without hastables and f(w)^d >>with the hashtables when the question is if f(w) is really close to 6. >> >>If f(w) is really close to 6 then the claim that deeper blue could search 17 >>plies in the middle game with no pruning is wrong. >> >>Uri > > I don't know whether 17 plies is the depth of exhaustive search or selective >one (in the case of deeper blue). >I also apologise for changing(swapping) the variables in my formula. Your >correction is correct, Uri (:-). My expression means that you would be able to >search VERY deep... > So one question arises: What's the average gain (with respect to time) when >you start to use hash tables - when f(d) is the (average) count of nodes >explored with simply alfa-beta (even with perfect ordering of moves) into >depth d - >what's relation between g(d), which is the same as f(d) except the fact >that you use hash tables now. Well, if it's true, that g(d)=c.f(d), where >c is constant which DONT depend on d (e.g: c=0.1), then my calculations >are correct (after correcting my formula (:-)). More interesting it >would be if g(d)/f(d) is not constant and is smaller and smaller when >d is bigger and bigger (I don't know that term in English for such a >function). "Decreasing function". José. >But I don't know it could be answered because: > 1) to find it out from artificial trees is out of reality (chess > is our reality) > 2) how to correctly define "average" count > 3) measurements could be made only to restricted depth (how is it > for lim (g(d)/f(d)) (where d->infinity) > > Jan Pernicka
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.