Author: Ian Kennedy
Date: 05:38:31 04/06/03
Go up one level in this thread
On April 06, 2003 at 08:13:48, Vincent Diepeveen wrote:
>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.
>
Yes, I should have pointed out for simplification that I don't use null-move and
for measuring purposes I am only counting full width searching, no extensions
nodes.
>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.
>
Sure, the only reason I quoted the figures I did is that I had actually worked
out the precise formula at those shallow depths, beyond that I am relying on a
bf averaged over all depths and that's not accurate enough unless I find some
positions where the branching is truly constant.
>>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.