Ippolit, Robbolito, Fire, etc. do something like this (generate only captures > some threshold at low depth). I think it is a bit dubious because you will overlook things like moves that check.
--Jon
Verification of pruning techniques
Moderators: hgm, Rebel, chrisw
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Verification of pruning techniques
Checks can only be generated effeciently by a dedicated move generator. Otherwise you would have to generate all moves, and test each of them for delivering check. That is at least 10x slower.
So if you want checks, just replace the
by
So if you want checks, just replace the
Code: Select all
gen_captures(threshold);
Code: Select all
gen_captures(threshold),
gen_checks(trheshold);
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Verification of pruning techniques
This is still in the main search, and could trigger extensions for example.hgm wrote:Code: Select all
gen_captures(alpha - seval - 150); // generate captures of sufficiently valuable victims
But this one goes straigth to qsearch and guarantees early exit.
Code: Select all
if (seval + 150 <= alpha){
return qsearch(alpha, beta, 0);
}
Code: Select all
# PLAYER : RATING ERROR POINTS PLAYED (%)
1 CDrill No Razor : 25.8 26.1 57.0 100 57.0%
2 CDrill HGM Fut : -25.8 26.1 43.0 100 43.0%
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Verification of pruning techniques
What extensions do you have in this CDrill engine, then? For one, extensions are supposed to make the engine stronger, so missing them by going directly to QS should be bad. Normally one only extends checks, and I suppose you do that in QS too. So it is hard to believe that this can be the reason.Ferdy wrote: This is still in the main search, and could trigger extensions for example.
...
Sample result on silver test suite.Code: Select all
# PLAYER : RATING ERROR POINTS PLAYED (%) 1 CDrill No Razor : 25.8 26.1 57.0 100 57.0% 2 CDrill HGM Fut : -25.8 26.1 43.0 100 43.0%
The only difference between my first proposal and using QS might be checks, if you would do these in QS, as John Dart remarked. This should of course be fixed to in the way I indicated to have a meaningful comparison. The idea is to have a less inefficient implementation to search the same tree, not to search another tree...
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Verification of pruning techniques
CDrill has only check extension in main search and there is no extension in qsearch.
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Verification of pruning techniques
I think you've overlooked the negation. It's not evading checks, it's making sure it only does pruning when *not* (in check or giving check with the current move or promoting to a queen with the current move or in a mate search).hgm wrote:I suppose 'checks' here means that you are in check in the current node, so that this move really is an evasion, and that child->checks means the move delivers check?zd3nik wrote:Code: Select all
Exec<color>(*move, *child); if (!(checks | child->checks | (move->Promo() == (color|Queen)) | (abs(alpha) >= WinningScore)) & ((standPat + ValueOf(move->Cap()) + _qsearchDelta[-depth]) < alpha)) { _stats.deltaCount++; Undo<color>(*move); continue; } move->Score() = -child->QSearch<!color>(-beta, -alpha, (depth - 1)); Undo<color>(*move);
The condition looks correct. The test for if alpha exceeds WinningScore seems redundant; I presume you could never exceed WinningScore with a score derived frm the static eval, so the part after & would already take care of that. As you use & instead of && the latter test would be done anyway, and even if not, the abs(alpha) test doesn't seem any cheaper.
I am also not sure why you would exempt check evasions. The idea of futility pruning is that the move is guaranteed to fail low to a stand-pat reply. That is just as true for check evasions.
I think you've also overlooked the winning score comparison is against alpha, not standPat. standPat will indeed never be within the realm of winningScore, but alpha could be if we're in a mate search.
I have tried static deltas with similarly bad results. This version of delta pruning is the most conservative version I have ever written. The thinking is that the farther away from the frontier node you get the less risky pruning gets. Perhaps that reasoning is false. but it's not worse that using a static delta of say 150 (the recommended value from what I've seen).I also don't see the justification for making the qsearchDelta depth dependent. No matter what depth you are already on, you only try to estimate the score after this single move. How much that score can change due to non-material terms not taken into account should not depend on how deep in QS you are.
The moves are sorted MVV/LVA.The point could be that it is not clear what this delta pruning actually saves you. You still make the pruned moves, and you still have to unmake them. Not doing the pruning at all would save you the effort of the test (which is also done for all non-pruned moves!), and the moves eligible to pruning would run into an immediate stand pat, possibly based on a lazy evaluation because of the margin.
This pruning would start to make sense if it saved you the work of the make/unmake. Or better yet, when you search the captures in MVV order, as soon as you reach the first futile victim, immediately return from the node with a fail-low score rather than keep running through the remaining captures to see if they are also futile (which they certainly will be), and then making and unmaking them nevertheless, just for fun.
I make/unmake the move because I have no other way of knowing if the move gives check or not. And moves that give check throw all assumptions about material value out the window because they could be mate, or lead to mate.
In any case, I have done the more traditional version where you stop searching on the first move that fits the pruning bill. And the results were much worse, for obvious reasons: you skip searching all the checks.
True.Note that this really helps in d=1 nodes, where also the non-captures would be futile. And there usually are a lot of non-captures.
Good point. I do have a check move generator, but it only generates non-capture, non-promo checks. This is because it's very easy in this engine to generate captures so I do that first then look for the non-capture checks. I could try reversing that, generate all checking moves then find the non-checking captures/promos. That way I can mark the moves that give check and I won't have to make the moves to know.If you want to exempt moves that deliver check from futility pruning, it would be best to have a selective generator of checks, rather than tokeep looping through all moves to test whether they deliver check. Then, at the point where you reach futile victims, you could continue with any HxL captures that were postponed (and thus not futile) based on their SEE, although one could argue that currEval + SEE + margin < alpha is also not worth trying, and then continue with a checks-only generator to finish the node.
But this is getting into nodes/sec optimization. The way I've implemented it doesn't have any noticeable detrimental effect on nodes/sec. Trying to squeeze more Nodes/sec isn't going to correct the weaknesses this routine introduces in the search path. That's what this topic is all about: why does this implementation cause so much ELO drop? I think I can safely say it's not because it's effecting nodes/sec; it's because it's pruning a higher number of important lines.than it should be for some reason - even though I've made it exceedingly conservative about it.
Looks like you've posted many more comments. I'll get to them one at time. I just hope this thread doesn't explode into too many branches of conversation.
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Verification of pruning techniques
I use underscores to indicate global variables. Sorry if that upsets you.abulmo wrote:Why do people use a leading underscore to name variables in their programs?According to both C and C++ standards, such name are reserved to the implementation. For example the C++ (last draft) standard says:zd3nik wrote:Code: Select all
_qsearchDelta[-depth] _stats.deltaCount _razorDelta[depth]
§2.10 (3.2) Each identifier that begins with an underscore is reserved to the implementation for use as a name in the global namespace.
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Verification of pruning techniques
I've posted the same argument on this forum before: razoring is just the inverse of futility pruning, e.g. one does the pruning after the move, the other does it before. But this topic isn't about the semantics of the terms futility pruning and razoring.hgm wrote:Btw, this code makes very little sense to me. I know razoring in the definition of Heinz, where it is just futility pruning at d=3 with a larger margin. I.e. it would be applied to the individual moves, and not to the node as a whole, unless you could prove there were no moves that could possibly beat the margin.zd3nik wrote:Code: Select all
// forward pruning prerequisites if (pvNode || !(pruneOK & !checks & (depthChange <= 0))) { goto search_main; // yeah that's a goto, horrible I know } // razoring (fail low pruning) if ((depth < 4) & (abs(alpha) < WinningScore) & !parent->checks & ((eval + _razorDelta[depth]) <= alpha)) { _stats.rzrCount++; if ((depth <= 1) && ((eval + _razorDelta[3 * depth]) <= alpha)) { _stats.rzrEarlyOut++; return QSearch<color>(alpha, beta, 0); } const int ralpha = (alpha - _razorDelta[depth]); const int val = QSearch<color>(ralpha, (ralpha + 1), 0); if (_stop) { return beta; } if (val <= ralpha) { _stats.rzrCutoffs++; return val; } }
_razorDelta[0] is not used because this routine is in the primary search function where depth is always > 0. And for that matter _razorDelta[4] is also not used in this particular implementation.I don't understand how with depth <= 1 razorDelta[0] would be NOT_USED.
I could have had-coded _razorDelta[3*depth] to 800 or _razorDelta[3]. it doesn't matter. the net result is the same. the extra couple cycles isn't the problem. I'll optimize away the extra cycles later.How much is 3*depth if depth=0? And if depth can only be 1, why not use depth[3] or a hard-coded 800 here?
It drops into qsearch not in hopes of getting a standPat. It drops into qsearch to see if there are any checks/captures/promos that can save the day.The depth <= 1 part seems regular futility pruning, not razoring, but implemented in an inefficient way, by delegating it to QS. In the first place this would re-calculate eval, while this was established to be already so much below alpha that there is no hope for a stand-pat at all.
Even a pawn capture can beat the margin of 800, the game doesn't stop after 1 move. One capture can expose other threats that lead to larger gains.(But perhaps it relies on an eval cache to ameliorate this waste of time.) In the second place it would still test all the individual captures (after making them) to see if they get close to alpha, despite the fact that they start from a position hugely below alpha. Basically only capture of a Queen or promotion could beat the margin of 800. And there might not even been a Queen on the board, so that the entire exercise is a pure waste of time.
Anyway you're arguing against the logic of a routine used in one of the most successful chess engines on the planet. All I'm looking for is flaws in my implementation of that well proven logic. Perhaps I'm using an AND somewhere that I should be using an OR, or I've inverted some logic somewhere.
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Verification of pruning techniques
Excellent feedback. That gives pretty substantial proof that razoring can work. Do you see any fundamental differences in CDrill's razoring implementation vs the code that I've posted?Ferdy wrote: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.
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Verification of pruning techniques
For context, here are the current standings in the bullet round-robin I'm running.
Clunk ALL = all pruning techniques enabled
Clunk LMR = only late move reductions enabled
Clunk NMP = only null move pruning enabled
Clunk FUTILITY = only futility pruning enabled
Clunk RZR = only razoring enabled
Clunk DELTA = only delta pruning enabled
Clunk ALPHA = only razoring and delta pruning (alpha pruning techniques) enabled
Clunk BETA = only futility and nmp (beta pruning techniques) enabled
Clunk NO ALPHA = all pruning except razoring and delta pruning enabled
Clunk NO BETA = all pruning except futility and nmp enabled
Clunk = no forward pruning techniques enabled
All Clunk engines configured with transposition table, pawn eval hash table, and killer heuristic
The latest versions of fairymax, kingslayer, and tscp are being used - as far as I know.
Code: Select all
Engine Score Cl Cl Cl Cl Cl Cl Cl Ki Cl Cl Cl Cl Cl Fa TS S-B
01: Clunk NO ALPHA 84.0/116 ····· 2-5-1 5-1-3 5-1-2 4-3-1 1-1-6 6-0-2 5-1-2 6-1-1 4-0-5 5-3-1 5-1-2 6-0-2 8-0-0 7-0-2 4473.2
02: Clunk ALL 83.5/117 5-2-1 ····· 3-4-1 2-3-4 5-2-1 6-1-2 5-1-2 6-3-0 6-2-1 5-1-2 6-1-1 4-1-3 5-1-2 6-0-3 8-0-0 4487.7
03: Clunk NO LMR 80.5/116 1-5-3 4-3-1 ····· 4-2-2 5-2-1 2-2-4 7-1-0 3-3-2 6-1-1 5-1-3 7-1-1 6-0-3 5-2-1 6-1-1 8-0-0 4250.7
04: Clunk NMP 72.5/117 1-5-2 3-2-4 2-4-2 ····· 2-3-4 3-3-2 1-5-2 6-1-1 5-2-1 6-2-1 3-2-3 8-0-0 6-1-2 6-1-1 7-0-2 3744.0
05: Clunk LMR 72.0/116 3-4-1 2-5-1 2-5-1 3-2-4 ····· 3-2-3 4-1-3 1-4-3 6-2-1 4-0-4 5-0-4 3-2-4 5-0-3 8-0-0 6-0-2 3722.2
06: Clunk NO BETA 66.5/116 1-1-6 1-6-2 2-2-4 3-3-2 2-3-3 ····· 5-1-3 4-2-3 3-3-2 3-2-3 5-0-3 4-3-1 4-2-2 5-2-2 6-1-1 3588.5
07: Clunk BETA 65.5/116 0-6-2 1-5-2 1-7-0 5-1-2 1-4-3 1-5-3 ····· 3-4-2 6-2-1 5-2-1 7-1-0 6-1-1 5-0-3 7-2-0 7-0-1 3224.0
08: KingSlayer 63.5/116 1-5-2 3-6-0 3-3-2 1-6-1 4-1-3 2-4-3 4-3-2 ····· 4-4-0 4-3-1 3-2-3 5-2-1 5-3-1 7-0-1 7-0-1 3289.7
09: Clunk FUTILITY 55.5/116 1-6-1 2-6-1 1-6-1 2-5-1 2-6-1 3-3-2 2-6-1 4-4-0 ····· 4-4-0 6-2-0 4-2-2 6-1-2 5-2-1 6-0-2 2773.5
10: Clunk 50.5/117 0-4-5 1-5-2 1-5-3 2-6-1 0-4-4 2-3-3 2-5-1 3-4-1 4-4-0 ····· 5-3-1 5-3-1 2-2-4 5-2-1 4-2-2 2659.5
11: Clunk ALPHA 45.5/117 3-5-1 1-6-1 1-7-1 2-3-3 0-5-4 0-5-3 1-7-0 2-3-3 2-6-0 3-5-1 ····· 4-2-2 3-2-3 2-3-3 9-0-0 2281.7
12: Clunk DELTA 45.0/117 1-5-2 1-4-3 0-6-3 0-8-0 2-3-4 3-4-1 1-6-1 2-5-1 2-4-2 3-5-1 2-4-2 ····· 4-2-3 5-1-2 6-2-1 2274.2
13: Clunk RZR 40.5/117 0-6-2 1-5-2 2-5-1 1-6-2 0-5-3 2-4-2 0-5-3 3-5-1 1-6-2 2-2-4 2-3-3 2-4-3 ····· 3-3-3 5-1-2 2096.5
14: FairyMax 31.0/116 0-8-0 0-6-3 1-6-1 1-6-1 0-8-0 2-5-2 2-7-0 0-7-1 2-5-1 2-5-1 3-2-3 1-5-2 3-3-3 ····· 5-3-0 1544.0
15: TSCP64 17.0/116 0-7-2 0-8-0 0-8-0 0-7-2 0-6-2 1-6-1 0-7-1 0-7-1 0-6-2 2-4-2 0-9-0 2-6-1 1-5-2 3-5-0 ····· 886.25
Clunk LMR = only late move reductions enabled
Clunk NMP = only null move pruning enabled
Clunk FUTILITY = only futility pruning enabled
Clunk RZR = only razoring enabled
Clunk DELTA = only delta pruning enabled
Clunk ALPHA = only razoring and delta pruning (alpha pruning techniques) enabled
Clunk BETA = only futility and nmp (beta pruning techniques) enabled
Clunk NO ALPHA = all pruning except razoring and delta pruning enabled
Clunk NO BETA = all pruning except futility and nmp enabled
Clunk = no forward pruning techniques enabled
All Clunk engines configured with transposition table, pawn eval hash table, and killer heuristic
The latest versions of fairymax, kingslayer, and tscp are being used - as far as I know.