Author: Vincent Diepeveen
Date: 06:39:22 04/06/03
Go up one level in this thread
On April 06, 2003 at 09:31:14, Ian Kennedy wrote:
i understand you just want to be busy with math, but it is of overwhelming
importance whether you use a quiescencesearch and which evaluation you use.
Best regards,
Vincent
>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.