Verification of pruning techniques

[jdart]

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

[hgm]

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

Code: Select all

gen_captures(threshold);

by

Code: Select all

gen_captures(threshold),
gen_checks(trheshold);

[Ferdy]

Code: Select all

gen_captures(alpha - seval - 150); // generate captures of sufficiently valuable victims

This is still in the main search, and could trigger extensions for example.


But this one goes straigth to qsearch and guarantees early exit.

Code: Select all

if &#40;seval + 150 <= alpha&#41;&#123;
    return qsearch&#40;alpha, beta, 0&#41;;
&#125;

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%

[hgm]

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%

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.

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...

[Ferdy]

CDrill has only check extension in main search and there is no extension in qsearch.

[zd3nik]

Code: Select all

      Exec<color>(*move, *child&#41;;
      if (!&#40;checks | child->checks | &#40;move->Promo&#40;) == &#40;color|Queen&#41;) | &#40;abs&#40;alpha&#41; >= WinningScore&#41;) &
          (&#40;standPat + ValueOf&#40;move->Cap&#40;)) + _qsearchDelta&#91;-depth&#93;) < alpha&#41;)
      &#123;
        _stats.deltaCount++;
        Undo<color>(*move&#41;;
        continue;
      &#125;
      move->Score&#40;) = -child->QSearch<!color>(-beta, -alpha, &#40;depth - 1&#41;);
      Undo<color>(*move&#41;;

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?

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 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).

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 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.

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).

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.

The moves are sorted MVV/LVA.

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.

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.

True.

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.

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.

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.

[zd3nik]

Why do people use a leading underscore to name variables in their programs?

Code: Select all

        _qsearchDelta[-depth]
        _stats.deltaCount
        _razorDelta[depth]

According to both C and C++ standards, such name are reserved to the implementation. For example the C++ (last draft) standard says:

§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.

I use underscores to indicate global variables. Sorry if that upsets you.

[zd3nik]

Code: Select all

    // forward pruning prerequisites
    if &#40;pvNode || !&#40;pruneOK & !checks & &#40;depthChange <= 0&#41;)) &#123;
      goto search_main;  // yeah that's a goto, horrible I know
    &#125;

    // razoring &#40;fail low pruning&#41;
    if (&#40;depth < 4&#41; & &#40;abs&#40;alpha&#41; < WinningScore&#41; &
        !parent->checks & (&#40;eval + _razorDelta&#91;depth&#93;) <= alpha&#41;)
    &#123;
      _stats.rzrCount++;
      if (&#40;depth <= 1&#41; && (&#40;eval + _razorDelta&#91;3 * depth&#93;) <= alpha&#41;) &#123;
        _stats.rzrEarlyOut++;
        return QSearch<color>&#40;alpha, beta, 0&#41;;
      &#125;
      const int ralpha = &#40;alpha - _razorDelta&#91;depth&#93;);
      const int val = QSearch<color>&#40;ralpha, &#40;ralpha + 1&#41;, 0&#41;;
      if (_stop&#41; &#123;
        return beta;
      &#125;
      if &#40;val <= ralpha&#41; &#123;
        _stats.rzrCutoffs++;
        return val;
      &#125;
    &#125;

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.

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.

I don't understand how with depth <= 1 razorDelta[0] would be NOT_USED.

_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.

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?

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.

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.

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.

(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.

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.

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.

[zd3nik]

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.

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?

[zd3nik]

For context, here are the current standings in the bullet round-robin I'm running.

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 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.