Author: Jan Pernicka
Date: 04:48:21 03/07/00
Go up one level in this thread
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). 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.