Author: Vincent Diepeveen
Date: 05:55:57 04/06/03
Go up one level in this thread
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.
>>>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.