Author: Vincent Diepeveen
Date: 05:13:48 04/06/03
Go up one level in this thread
On April 06, 2003 at 07:40:11, Ian Kennedy wrote:
The minimal tree is depending upon a lot of factors, but most important by far
is what kind of evaluation you use.
When a lot of different algorithms get mixed such as nullmove with multiprobe
hashtable with PVS, then the minimal tree is pretty difficult to determine.
In theory it is possible to measure minimal tree. In reality for a search with
millions of nodes, it's practical impossible to measure the minimal tree. All
you can do is determine a very small tree which will be somewhere in between the
minimal tree and the normal search tree.
Schaeffer has it easy to measure minimal tree compared to programs which use
nullmove. He never did AFAIK.
measuring branching factors for 3,4 ply is not exactly interesting. More
interesting is what branching factor can be at >= 10 ply.
>Has anyone done this in their program? I have been trying recently. One of the
>problems is that the standard formula for the size of a minimal tree assume a
>fixed branching factor. I've manually worked out what the figures are for a
>branching factor bf[depth] for the first few plies but gave up after that. I've
>just read a paper by Schaeffer in which he refers to a technique suggested by
>Carl Ebeling but the book 'All the right moves' in which it appears is now out
>of print and Schaeffer doesn't describe the method himself. He quotes some
>performances around 1.2x to 1.5x bigger than minimal (2.2 for Belle), does
>anyone have any figures for their programs they can share?
>
>Or does anyone have a useful general formula for the size of the minimal tree
>based on a varying bf[depth]?
>
>The figures I obtained during a game with my program playing both sides,
>averaged over the first 18 b/w moves were
>
>ply 3: 1.21x minimal
>ply 4: 2.48x minimal
>
>These actually look very similar to the graph in fig 1 - derived from Phoenix
>-in Schaeffer's paper ('New Advances in alpha-beta searching'). And yet my
>program looks like it doesn't order and prune as well as others and spends
>proportionally longer searching the moves 2-n at each iteration than others.
>
>Ian
This page took 0.01 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.