Author: Volker Böhm
Date: 22:00:02 08/14/04
Go up one level in this thread
On August 14, 2004 at 12:11:58, Stuart Cracraft wrote:
>On August 12, 2004 at 17:26:15, Volker Böhm wrote:
>
>>Hi Stuart,
>>
>>I recommend you test all your prunings you are doing in the following way. Then
>>you´ll get some informations about pruning error.
>>I currently have the following results:
>>
>>SEE < 0 gets about 0,3% of error rate (bad_prunings/good_prunings)
>>a eval + eval_captured_piece() + margin gets a error rate about 0,001% - I
>>tested many different "eval_captured_piece()" and margin to get to a low error
>>rate.
>>
>>I never found any good solution to reduce the error rate for SEE < 0. The
>>problem cases are much to complex to be easily calculated.
>>
>>The way to measure:
>>
>>pruning = Calc_If_Ill_prune(...);
>>
>>if (pruning) then pruneval = current_value;
>>
>>Do_the_stuff_that_would_be_pruned(); // changes current_value
>>
>>if (pruning)
>>{
>> if (current_value > alpha)
>> {
>> // pruning was a bad decision
>> bad_pruning++;
>> max_error = max(max_error, current_value - alpha);
>> }
>> else
>> {
>> good_pruning++;
>> }
>> write_statistics();
>>}
>
>This is over-my-head. I didn't understand it.
>
>Can you give a general description? (I like to code too but
>like to understand first. Thanks Volker.)
>
>Stuart
Hi Stuart,
I describe it for the SEE Pruning in Q-Search as example. The same priciple
could be used for every pruning.
The Idea is, whenever you add a pruning rule you should test it the rule does
only a small amount of mistakes.
The test starts with the calucaltion if you should prune. For SEE is would be:
boolean pruning;
pruning = SEE(position, move) < 0;
Now in test case don´t prune. Just call the quiescence without SEE pruning.
Now, it the call to quiescense returns it returns a value. If this returned
value is > alpha it changes the current search result.
Thus if ((pruning == true) && (returned_value > alpha))
you know that the pruning would have been a mistake. On the other hand if
returned_value <= alpha it would have been correct to prune.
With this knowledge you can calculate a statistic of "correct_pruned" and
"false_pruned". On top you can calculate the size of the error: returned_value -
alpha. If this value is big, the error the pruning gives is big too. I calculate
the maximum of this value.
For SEE Pruning caluclating the 100 prositions of wm-test until depth 7 I had a
maximum error of about 4 pawns and an error rate of 0,3%.
Now you can change the pruning rule, for example add a pinned-piece detection
and test if this results in a less big error rate or if it reduces the maximal
error.
It is a good idea to check the positions with high error rate. Print those
positions (as fen) in a log file and don´t forget the move that would have been
pruned. Now you can check the positions and decide if your code is buggy or if
the pruning has a systematic error.
For SEE pruning it shows mostly allways the following systematic error cases:
1. A piece is pinned (to king, to queen, to undefended piece)
2. A piece defends two attacked pieces
3. The capturing piece is hanging and there are other hanging pieces. Example
white to move, white and black queen are hanging. White queen hits defendet
rook, SEE says < 0. But if black captures white queen white will capture black
queen, winning a rook.
Now try to add a rule for the third case and test if it reduces the error rate
without reducing the pruning factor too much :
If (!Capturing_Piece_Is_Hanging() && SEE() < 0) prune
Greetings Volker
This page took 0 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.