Author: Ian Kennedy
Date: 06:31:14 04/06/03
Go up one level in this thread
On April 06, 2003 at 08:55:57, Vincent Diepeveen wrote:
>On April 06, 2003 at 08:38:31, Ian Kennedy wrote:
>
>>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.
>
>are you using a quiescencesearch?
>
>>>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
>
>The formula is dependant upon the evaluation function you use. Each evaluation
>function will have a different minimal tree (because of increased transpositions
>and qsearch).
>
>
>
>>bf averaged over all depths and that's not accurate enough unless I find some
>>positions where the branching is truly constant.
>
>'some positions where the bf is truly constant' ????
>
>you mean some positions X where X is all the same positions. In short all 100%
>the same positions?
>
>Even changing a position from white to move to black to move will of course
>already change branching factor. bf is also dependant upon the number of average
>moves possible and with todays deep searches especially upon how many
>transpositions are possible at bigger depths.
>
I haven't been clear enough, sorry. Let's say that, for my program, I can apply
a formula at three levels of accuracy. In improving order of usefulness they are
1. 2 x BF^(d/2) -1 (even) ; BF^(d-1/2) + BF^(d+1/2) -1 (odd)
This is pretty useless in the real world of a chess game tree!
2. Now I average the BF at each depth and re-calculate the formula at each depth
using AverageBF[depth]. This is better but still not that good.
3. Closer still; for example at ply 2 it's BF[1] + AverageBF[2] -1. ply 3 its
AverageBF[2] + (bf[1] * AverageBF[3]) - 1. I deduced these by looking at a dump
of my search tree, not churning algorithms in my head!
4. ??? The *real* formula which will use specific branching widths on specific
branches at each depth. I haven't calculated these formulae yet and if I do they
are more costly to measure at runtime.
Currently I'm doing (3) above to depth 4 as I slogged out the formula, beyond
that I use (2):
perfect actual a-p a/p AverageBF[depth]
36 36 0 1.000000 36
62 84 22 1.354839 27
1286 1512 226 1.175739 35
2173 3586 1413 1.650253 30
52021 74223 22202 1.426789 37
59581 183075 123494 3.072708 31
1726271 2326127 599856 1.347487 36
etc, where beyond depth 4 the formula is less accurate.
>>>>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.