Author: Jan Pernicka
Date: 03:00:20 03/06/00
Go up one level in this thread
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...
With help from hashtables the situation sligtly changes. They can only
improve the speed (I neglect the
R/W overhead), but how much ? (...was your question...) I can say that in
the worst case the situation will be almost the same as it was before and in the
best case it could be much better, but the count of leaf nodes expanded will be
something like: d^(f(w)), where f(w) is close to w/2 - but especially in
end-games this gain could be much higher - because of "less possible states on
the board".
Thank you for your patience,
Jan Pernicka
PS: is mid-game you can take w=36 (sqare root looks fine (:-) ),
in end-game w is 10-25 or more (depends on the endgame (:-) ),
in both - choose d as you wish...
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.