The value was never tuned. But 800 is about the value of a bishop. So it is not really "ridiculously large".It is well-known that d=1 or even d=2 nodes and QS nodes are often the same. It seems very strange, though, to subject that notion to a ridiculously large margin of 800. How much do you have to be below alpha to be sure that non-captures are not going to cut it?
Verification of pruning techniques
Moderators: hgm, Rebel, chrisw
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Verification of pruning techniques
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Verification of pruning techniques
Oh, that is pretty unusual. Normally one would expect scores to be posted without warning to be in centi-Pawns.
A Bishop still seems a pretty large margin to me. Which fraction of the non-captures would increase the eval by more than a Bishop? Would it really pay to search those thousands of non-captures that don't to spot the occasional one that does?
A Bishop still seems a pretty large margin to me. Which fraction of the non-captures would increase the eval by more than a Bishop? Would it really pay to search those thousands of non-captures that don't to spot the occasional one that does?
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Verification of pruning techniques
Well futility pruning is not done solely on the basis of evaluation. Some types of moves are excluded from futility pruning because they are interesting otherwise. You'd expect there to be a price to pay for skipping these additional safeguards. But as said, the value 800 was never tuned.A Bishop still seems a pretty large margin to me. Which fraction of the non-captures would increase the eval by more than a Bishop? Would it really pay to search those thousands of non-captures that don't to spot the occasional one that does?
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Verification of pruning techniques
Normally these would be only checks.Michel wrote:Well futility pruning is not done solely on the basis of evaluation. Some types of moves are excluded from futility pruning because they are interesting otherwise.
It doesn't help to qualify moves as too 'interesting' to prune when the opponent would happily stand pat against them. Futility pruning is not about good or bad moves, it is about not wasting time on moves that will face the harsh reality of stand pat. So if you don't have something like
if(eval >= beta && !interesting) return eval;
in your QS there is really no point in taking anything else into account for deciding about futility.
If there is an easily identifiable class of non-captures that can cause such extreme eval swings, (e.g. King or Pawn moves in connection to King Safety, or Pawn pushes to 7th rank), it would be wise to have a separate generator for them, and also search them in QS. Otherwise you should expect severe horizon effects.
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Verification of pruning techniques
I have this uci engine called CDrill without search reduction and pruning not even NMP, it only has hash table. In the evaluation only piece values and pst for P, N, B and K. No mobility, no passers, no king shelter, no weak pawns eval nothing.
It scored 100 (+61,=12,-27), 67.0 % vs Robin 0.983 (CCRL40/4 1755).
Created a branch from this engine and added razoring at depth 1. Run some self-test of 100 games each (TC 40moves/60s) from different test suites. Here is the result.
It scored 100 (+61,=12,-27), 67.0 % vs Robin 0.983 (CCRL40/4 1755).
Created a branch from this engine and added razoring at depth 1. Run some self-test of 100 games each (TC 40moves/60s) from different test suites. Here is the result.
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Verification of pruning techniques
Razoring at d=1? That is normal futility pruning, isn't it?
How did you implement it then, to save you any time compared to just latting stand-pat in the daughter take care of it? With only incremental PST for eval, stand-pat must be nearly as cheap as pruning. But your results suggest it is a least 35% faster.
Is this a hash-probe problem?
How did you implement it then, to save you any time compared to just latting stand-pat in the daughter take care of it? With only incremental PST for eval, stand-pat must be nearly as cheap as pruning. But your results suggest it is a least 35% faster.
Is this a hash-probe problem?
Last edited by hgm on Mon Oct 05, 2015 4:21 pm, edited 1 time in total.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Verification of pruning techniques
By interesting moves I mean moves which can cause large eval swings without being captures.
As I said the value 800 was never tuned. Perhaps it can be lower but I would expect that in any case it needs to be higher than the futility margin for depth 1 since the latter takes into account that interesting moves will not be pruned.
Of course there are different implementations possible of the same idea (one could subcase futility pruning for depth=1). But IMHO the current implementation expresses the idea in the most concise way.
As I said the value 800 was never tuned. Perhaps it can be lower but I would expect that in any case it needs to be higher than the futility margin for depth 1 since the latter takes into account that interesting moves will not be pruned.
Of course there are different implementations possible of the same idea (one could subcase futility pruning for depth=1). But IMHO the current implementation expresses the idea in the most concise way.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Verification of pruning techniques
But if non-captures exist where you can gain on the order of a Bishop, not considering them in QS would have the same effect as not considering Bishop captures in QS. And when you consider them in QS, there wouldn't be any need to not do QS instead of d=1 already at a much lower margin. I would say the margin should always be smaller as a Pawn, to avoid severe horizon effect. When I gave castling a bonus of more than a Pawn, my engine would make non-sensical Pawn sacs in the opening all the time, to push the opponent's castling over the horizon.Michel wrote:By interesting moves I mean moves which can cause large eval swings without being captures.
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Verification of pruning techniques
It is just similar to this.
Code: Select all
// Razoring
if (depth < 2 && !pv_node && !incheck){
int seval = eval();
if (seval + 150 <= alpha){
return qsearch(alpha, beta, 0);
}
}
Code: Select all
int search(int alpha, int beta, int depth, bool incheck){
pv_node = beta-alpha > 1;
if depth < 1 return qsearch()
check_rep()
probe_hash()
// Razoring here
gen_moves()
...
}
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Verification of pruning techniques
Well, that is just futility pruning, implemented by letting QS do it.Ferdy wrote:It is just similar to this.Code: Select all
// Razoring if (depth < 2 && !pv_node && !incheck){ int seval = eval(); if (seval + 150 <= alpha){ return qsearch(alpha, beta, 0); } }
You mean that you otherwise would search all non-captures in this node? Then I can imagine why it saves you so much time. The more efficient implementation of this would be
Code: Select all
int search(int alpha, int beta, int depth, bool incheck){
pv_node = beta-alpha > 1;
if depth < 1 return qsearch()
check_rep()
probe_hash()
int seval = eval();
if(depth < 2 && !pv_node && !incheck && seval + 150 < alpha)
gen_captures(alpha - seval - 150); // generate captures of sufficiently valuable victims
else
gen_moves()
...
}
And I wonder why you would not do it while in check. The non-capture check evasions will be just as futile as any other non-capture. They will not approach alpha, and the opponent is sort of guaranteed to make them fail low by standing pat.