Verification of pruning techniques

[hgm]

You obviously don't know the difference between backward pruning (alpha/beta) and forward pruning (razoring, futility pruning, null move pruning, etc)

Backward pruning has complete enough knowledge to prune any kind of move without error. Forward pruning does not. Using the behavior of a backward pruning technique as proof of your "logic" concerning forward pruning only convinces me even more that I don't need to waste any more time on your mad ramblings.

Hello, anyone awake there???

d=1 futility pruning is backward pruning that cannot make any kind of error. And it is apparently not the only thing that is backward... Talking about mad ramblings!

[zd3nik]

d=1 futility pruning is backward pruning that cannot make any kind of error. And it is apparently not the only thing that is backward... Talking about mad ramblings!

Only if:

1) you do it on a per move basis so the following 2 requirements may be met:
2) your delta is larger than any difference a single move can make in your static positional eval function.
3) you don't do pruning on moves that give check

For #1: It seems likely that you've just assumed this whole time that the razoring routine (which you refer to as futility pruning) I posted at the beginning of this thread is, or should be, in the move search loop. But, as I stated in the beginning, it is placed after transposition table heuristics and before move generation - i.e. not inside the move searching loop. If you've assumed it's in the move loop, or that it should be so you've only been talking about it as if it is, that would be a big part of the reason we can't seem to agree on anything. Perhaps we've been talking about two completely different heuristics. That would certainly explain why you seem to think that I claim non-captures can overcome a large alpha deficit - even though I clearly stated (twice) that the routine is dropping into qsearch so it only looks at captures, promotions, and checks - as is the nature of qsearch (when not in check).

If the confusion about the razoring logic being assumed to be inside the move loop is true, the following 2 paragraphs are moot.

For #2: A delta of 150 obviously isn't large enough to fill this requirement. To even come close to fitting the bill for backward pruning it would have to be larger than the value of 2 queens - to account for a pawn capturing a queen while also promoting to a queen plus a little head room for positional considerations.

We already know you disregard #3. That is more than enough to make your statement that futility pruning is backward pruning totally false. Unless you're in the habit of allowing qsearch to stand-pat when in check - which apparently you are - in which case we're proceeding from a completely different foundation, so it's only natural that we see things differently.

Anyway, minor change of subject: I've finished some initial testing on the delta pruning routine inside qsearch (not to be confused with the d=1 routine which is discussed above) and I'll post the results in a separate message.

[zd3nik]

I've done some preliminary testing of some suggested changes in the delta pruning routine I posted at the beginning of this ridiculous thread.

The original routine:

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);
        if (_stop) {
          return beta;
        }
        continue;
      }

This is inside the qsearch move loop. And in the results below it is referred to as "Clunk DELTA".

The 3 new configurations that have been added since the last time I posted the round-robin results are:

Clunk DELTA 150 = _qsearchDelta[-depth] replaced with hard-coded value of 150
Clunk DELTA 150 NoWS = Removed (abs(alpha) >= WinningScore) test from DELTA 150
Clunk DELTA NoWS = Removed (abs(alpha) >= WinningScore) test from original routine

The bullet round-robin results with these 3 new engine configurations added in:

Code: Select all

    Engine               Score         Cl     Cl     Cl     Cl     Cl     Cl     Cl     Ki     Cl     Cl     Cl     Cl     Cl     Cl     Cl     Cl     Fa     TS    S-B
01: Clunk ALL            258.5/340 ······  9-5-6 10-7-3 11-3-6 10-3-7 11-4-5 13-2-5 12-6-2 14-4-2 15-2-3 14-2-4 16-0-4 17-1-2 13-2-5 11-2-7 14-1-5 13-0-7 19-1-0  41146.
02: Clunk NO ALPHA       250.5/340  5-9-6 ······  9-3-8 10-4-6 12-6-2  9-5-6 8-1-11 13-4-3 11-3-6 15-3-2 10-2-8 15-2-3 13-4-3 14-2-4 14-0-6 17-0-3 17-0-3 17-0-3  39343.
03: Clunk NO LMR         226.5/340 7-10-3  3-9-8 ······ 11-4-5 12-4-4  9-8-3  9-5-6  7-7-6 14-2-4  7-5-8 11-4-5 10-3-7 16-1-3 12-1-7 12-3-5 13-1-6 15-3-2 16-1-3  35600.
04: Clunk BETA           208.0/340 3-11-6 4-10-6 4-11-5 ······  8-7-5  9-6-5  8-9-3  9-7-4 11-7-2 12-6-2 12-4-4 13-3-4 13-4-3 12-3-5 13-3-4 13-4-3 15-3-2 16-1-3  31996.
05: Clunk LMR            207.0/340 3-10-7 6-12-2 4-12-4  7-8-5 ······  8-5-7  9-6-5  6-8-6 11-5-4  8-6-6 12-3-5 11-6-3  9-3-8 11-2-7 12-1-7 10-1-9 18-0-2 17-0-3  31581.
06: Clunk NMP            206.0/340 4-11-5  5-9-6  8-9-3  6-9-5  5-8-7 ······  7-6-7  9-7-4 10-6-4 10-4-6 10-4-6  8-7-5  9-2-9 14-3-3 12-1-7 11-4-5 17-1-2 18-0-2  31637.
07: Clunk NO BETA        205.0/340 2-13-5 1-8-11  5-9-6  9-8-3  6-9-5  6-7-7 ······ 10-4-6  8-6-6 14-3-3 10-2-8 12-4-4 13-2-5 11-5-4 12-4-4 11-1-8 11-3-6 18-1-1  31428.
08: KingSlayer           189.5/340 6-12-2 4-13-3  7-7-6  7-9-4  8-6-6  7-9-4 4-10-6 ······ 10-9-1 7-10-3  9-8-3  9-4-7  8-4-8 13-5-2 12-4-4 11-4-5 17-1-2 16-1-3  29160.
09: Clunk FUTILITY       174.0/340 4-14-2 3-11-6 2-14-4 7-11-2 5-11-4 6-10-4  6-8-6 9-10-1 ······  7-5-8  8-7-5 10-3-7 13-4-3  9-6-5  9-5-6  9-5-6 12-5-3 18-0-2  26314.
10: Clunk DELTA 150 NoWS 161.0/340 2-15-3 3-15-2  5-7-8 6-12-2  6-8-6 4-10-6 3-14-3 10-7-3  5-7-8 ······  9-5-6  9-2-9  2-9-9 7-10-3  7-8-5  9-3-8 16-2-2 15-2-3  24455.
11: Clunk                149.0/340 2-14-4 2-10-8 4-11-5 4-12-4 3-12-5 4-10-6 2-10-8  8-9-3  7-8-5  5-9-6 ······  4-8-8 12-6-2  8-8-4 10-5-5  6-9-5 11-4-5 13-2-5  22917.
12: Clunk DELTA 150      143.5/340 0-16-4 2-15-3 3-10-7 3-13-4 6-11-3  7-8-5 4-12-4  4-9-7 3-10-7  2-9-9  8-4-8 ······  9-7-4  7-7-6  9-6-5 11-5-4 11-4-5 10-6-4  21981.
13: Clunk ALPHA          143.5/340 1-17-2 4-13-3 1-16-3 4-13-3  3-9-8  2-9-9 2-13-5  4-8-8 4-13-3  9-2-9 6-12-2  7-9-4 ······  9-6-5  8-4-8 10-7-3 10-4-6 19-1-0  21040.
14: Clunk DELTA          141.0/340 2-13-5 2-14-4 1-12-7 3-12-5 2-11-7 3-14-3 5-11-4 5-13-2  6-9-5 10-7-3  8-8-4  7-7-6  6-9-5 ······  9-7-4  8-7-5 11-5-4 16-3-1  21185.
15: Clunk RZR            132.0/340 2-11-7 0-14-6 3-12-5 3-13-4 1-12-7 1-12-7 4-12-4 4-12-4  5-9-6  8-7-5 5-10-5  6-9-5  4-8-8  7-9-4 ······  7-4-9  8-5-7 16-1-3  19853.
16: Clunk DELTA NoWS     127.5/340 1-14-5 0-17-3 1-13-6 4-13-3 1-10-9 4-11-5 1-11-8 4-11-5  5-9-6  3-9-8  9-6-5 5-11-4 7-10-3  7-8-5  4-7-9 ······ 12-3-5 13-3-4  19000.
17: FairyMax             90.0/340  0-13-7 0-17-3 3-15-2 3-15-2 0-18-2 1-17-2 3-11-6 1-17-2 5-12-3 2-16-2 4-11-5 4-11-5 4-10-6 5-11-4  5-8-7 3-12-5 ······ 15-4-1  13312.
18: TSCP64               47.5/340  1-19-0 0-17-3 1-16-3 1-16-3 0-17-3 0-18-2 1-18-1 1-16-3 0-18-2 2-15-3 2-13-5 6-10-4 1-19-0 3-16-1 1-16-3 3-13-4 4-15-1 ······  7583.7

Note the margin of error is very high in this round robin because it is a bullet tournament and the number of games (3060) is "relatively" low. But given that it takes days to complete even this small/fast tournament it's as much as I have patience for in my "preliminary" testing. The best looking options coming out of the preliminary tests will be put through more tournaments with longer time controls, etc.

Mostly what I look at here is the number of losses to weaker engines like TSCP and FairyMax. A higher than average number of losses to those engines is probably indicative of some major tactical weakness introduced by the routine(s) the engine is configured to use.

And a high win/loss ratio (like 10-3) is probably significant enough to be meaningful even under these conditions.

I also ran all the engine configs through some test positions. Results sorted by SCORE, then KNODES/SEC, then AVG_DEPTH

https://chessprogramming.wikispaces.com/Win+at+Chess 1 second per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk.no_alpha,      96.00,    1411.97,        22
clunk.all,           95.33,    1351.19,        22
clunk.beta,          95.00,    1447.83,        20
clunk.nmp,           95.00,    1431.39,        20
clunk.no_lmr,        95.00,    1369.70,        20
clunk.lmr,           94.33,    1369.80,        20
clunk.no_beta,       94.33,    1273.81,        20
clunk.futility,      92.33,    1444.39,        19
clunk,               92.00,    1416.61,        18
clunk.rzr,           92.00,    1372.86,        18
clunk.delta,         92.00,    1338.24,        18
clunk.delta_nows,    92.00,    1326.05,        18
clunk.delta150,      92.00,    1297.84,        18
clunk.alpha,         92.00,    1290.92,        18
clunk.delta150_nows, 92.00,    1284.00,        18

https://chessprogramming.wikispaces.com ... but+deadly 5 seconds per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk.futility,      80.60,    1153.86,         8
clunk.beta,          79.85,    1131.96,        10
clunk.no_alpha,      79.85,    1112.68,        13
clunk.no_beta,       79.85,    1019.30,        10
clunk.lmr,           79.10,    1101.99,        10
clunk.nmp,           78.36,    1115.88,        10
clunk.alpha,         78.36,    1047.43,         8
clunk.delta150_nows, 78.36,    1026.56,         8
clunk.delta150,      78.36,    1021.06,         8
clunk.rzr,           77.61,    1108.07,         8
clunk.delta_nows,    77.61,    1093.99,         8
clunk.delta,         77.61,    1085.98,         8
clunk.no_lmr,        77.61,    1037.67,        10
clunk,               76.87,    1148.65,         8
clunk.all,           76.87,    1026.93,        13

https://chessprogramming.wikispaces.com ... Kopec+Test 10 seconds per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk,               70.83,    1204.80,        12
clunk.rzr,           70.83,    1162.70,        12
clunk.delta_nows,    70.83,    1135.24,        12
clunk.delta,         70.83,    1125.40,        12
clunk.all,           70.83,    1099.33,        18
clunk.alpha,         70.83,    1090.00,        12
clunk.delta150_nows, 70.83,    1054.57,        12
clunk.delta150,      70.83,    1052.38,        12
clunk.beta,          66.67,    1201.89,        15
clunk.nmp,           66.67,    1187.36,        15
clunk.no_alpha,      66.67,    1175.56,        18
clunk.lmr,           66.67,    1168.08,        15
clunk.no_lmr,        66.67,    1107.50,        15
clunk.no_beta,       66.67,    1062.40,        15
clunk.futility,      62.50,    1213.10,        13

https://chessprogramming.wikispaces.com/Kaufman+Test 10 seconds per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk.beta,          92.00,    1378.55,        14
clunk.nmp,           92.00,    1350.68,        14
clunk.lmr,           92.00,    1321.05,        14
clunk.no_lmr,        92.00,    1319.46,        14
clunk.futility,      88.00,    1380.35,        11
clunk,               88.00,    1358.04,        11
clunk.no_alpha,      88.00,    1339.62,        17
clunk.rzr,           88.00,    1309.54,        11
clunk.all,           88.00,    1303.97,        18
clunk.delta,         88.00,    1302.58,        11
clunk.delta_nows,    88.00,    1295.84,        11
clunk.alpha,         88.00,    1258.98,        11
clunk.delta150,      88.00,    1243.16,        11
clunk.no_beta,       88.00,    1238.51,        14
clunk.delta150_nows, 88.00,    1236.75,        11

https://chessprogramming.wikispaces.com/LCT+II 15 seconds per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk.all,           60.00,    1214.06,        16
clunk.beta,          57.14,    1317.98,        13
clunk.nmp,           57.14,    1297.85,        12
clunk.no_alpha,      57.14,    1285.37,        16
clunk.lmr,           54.29,    1260.34,        13
clunk.no_lmr,        54.29,    1226.73,        13
clunk.no_beta,       48.57,    1153.65,        13
clunk.futility,      45.71,    1322.05,        10
clunk,               37.14,    1293.11,        10
clunk.rzr,           37.14,    1259.19,        10
clunk.delta,         37.14,    1222.25,        10
clunk.delta_nows,    37.14,    1209.28,        10
clunk.alpha,         37.14,    1190.69,        10
clunk.delta150,      37.14,    1176.58,        10
clunk.delta150_nows, 37.14,    1161.56,        10

I will also do tests with the following routine and the same variations (but I haven't gotten to it yet):

Code: Select all

      if (!(checks | (move->Promo() == (color|Queen)) | (abs(alpha) >= WinningScore)) &
          ((standPat + ValueOf(move->Cap()) + _qsearchDelta[-depth]) < alpha))
      {
        _stats.deltaCount++;
        if (_stop) {
          return beta;
        }
        break; // don't examine any more moves
      }
      Exec<color>(*move, *child);

The above routine is what HGM suggests, if I'm not misinterpreting something. The main differences from the original are:

1) don't care whether a move gives check or not, so no need to make the move first (in order to figure out whether it gives check)
2) since moves are ordered in MVV/LVA fashion don't search any more moves once the first move that falls bellow the threshold is found.

[hgm]

Only if:

1) you do it on a per move basis so the following 2 requirements may be met:
2) your delta is larger than any difference a single move can make in your static positional eval function.
3) you don't do pruning on moves that give check

Well, (2) and (3) are the usual definition of 'futile'. The check evasions we are discussing satisfy all these criteria. And your code does apply the criteria per move, in QS, so that takes care of (1).

For #1: It seems likely that you've just assumed this whole time that the razoring routine (which you refer to as futility pruning) I posted at the beginning of this thread is, or should be, in the move search loop. But, as I stated in the beginning, it is placed after transposition table heuristics and before move generation - i.e. not inside the move searching loop. If you've assumed it's in the move loop, or that it should be so you've only been talking about it as if it is, that would be a big part of the reason we can't seem to agree on anything.

It doesn't really matter whether you implement the pruning as bulk or per-move pruning (other than in efficiency). What matters is which moves you search, and which not. You can always achieve the same tree in both cases. Your code searches non-futile captures (based on approaching alpha or checking, excluding the futile captures by a per-move test) and non-capture checks(through a dedicated generator for those), and all evasions (even those that are non-captures and non-checksand fall very far below alpha). I only pointed out that searching the latter is a waste of time, as they are moves that with certainty can be predicted to fail low. The 'checks' condition just does not belong in that test.

Perhaps we've been talking about two completely different heuristics. That would certainly explain why you seem to think that I claim non-captures can overcome a large alpha deficit - even though I clearly stated (twice) that the routine is dropping into qsearch so it only looks at captures, promotions, and checks - as is the nature of qsearch (when not in check).

You use a margin of 800 in that test, right? So if eval = alpha - 700 the test fails, and you will NOT drop into QS, right? So you stay in the d=1 node, which generates and searches all non-captures (amongst others). It does not even test them on a per-move basis for futility, not ever after making them, as you only do that in QS.

So the question was: why does your code search non-captures in positions where eval = alpha - 700? Do you expect there to be any non-captures that would raise eval so much that they don't fail low. And if not, why would you search them? That 800 margin is just so big that it effectively disables any pruning completely.

For #2: A delta of 150 obviously isn't large enough to fill this requirement. To even come close to fitting the bill for backward pruning it would have to be larger than the value of 2 queens - to account for a pawn capturing a queen while also promoting to a queen plus a little head room for positional considerations.

That would be the condition if you wanted to outright prune the current node, i.e. return alpha rather than QS. But you return QS, and QS will search that PxQ=Q move, as your QS does take the material gain of the specific moves into account. The difference jumping into QS makes compared to just staying at d=1 is that it bulk-prunes non-captures that are not checks. And for non-captures 150 seems a reasonable margin. (Assuming that promotions are considered captures, and searched in QS.)

We already know you disregard #3. ....

No!? Where do you get that idea from??? I repeatedly stated that checks are NEVER futile. (Provided your QS declines to stand pat when in check, of course. If it would stand pat in the face of check, checks would be just as futile as any other move, when they do not approach alpha.)

I only said that evasions are just as futile as any other move. 'Evasion' is not the same as 'check', right? In fact evasions very rarely are checks (although it can occasionally happen).

[zd3nik]

New engine config: Clunk DELTA HGM

Delta pruning in qsearch HGM style (lives inside the move loop):

Code: Select all

      if ( ! (checks | (move->Promo() == (color|Queen))) &
          ((standPat + ValueOf(move->Cap()) + 150) < alpha))
      {
        _stats.deltaCount++;
        break; // don't search any more moves
      }
      Exec<color>(*move, *child);
      move->Score() = -child->QSearch<!color>(-beta, -alpha, (depth - 1));
      Undo<color>(*move);
      ...

Where it stands in the bullet round robin:

Code: Select all

    Engine               Score         Cl     Cl     Cl     Cl     Cl     Cl     Cl     Ki     Cl     Cl     Cl     Cl     Cl     Cl     Cl     Cl     Cl     Fa     TS    S-B
01: Clunk ALL            276.0/360 ······  9-5-6 10-7-3 11-3-6 10-3-7 11-4-5 13-2-5 12-6-2 14-4-2 15-2-3 14-2-4 15-0-5 16-0-4 17-1-2 13-2-5 11-2-7 14-1-5 13-0-7 19-1-0  46624.
02: Clunk NO ALPHA       268.5/360  5-9-6 ······  9-3-8 10-4-6 12-6-2  9-5-6 8-1-11 13-4-3 11-3-6 15-3-2 10-2-8 17-1-2 15-2-3 13-4-3 14-2-4 14-0-6 17-0-3 17-0-3 17-0-3  44779.
03: Clunk NO LMR         243.0/360 7-10-3  3-9-8 ······ 11-4-5 12-4-4  9-8-3  9-5-6  7-7-6 14-2-4  7-5-8 11-4-5 15-2-3 10-3-7 16-1-3 12-1-7 12-3-5 13-1-6 15-3-2 16-1-3  40541.
04: Clunk BETA           222.0/360 3-11-6 4-10-6 4-11-5 ······  8-7-5  9-6-5  8-9-3  9-7-4 11-7-2 12-6-2 12-4-4 13-5-2 13-3-4 13-4-3 12-3-5 13-3-4 13-4-3 15-3-2 16-1-3  36325.
05: Clunk LMR            221.0/360 3-10-7 6-12-2 4-12-4  7-8-5 ······  8-5-7  9-6-5  6-8-6 11-5-4  8-6-6 12-3-5 11-3-6 11-6-3  9-3-8 11-2-7 12-1-7 10-1-9 18-0-2 17-0-3  35871.
06: Clunk NMP            216.5/360 4-11-5  5-9-6  8-9-3  6-9-5  5-8-7 ······  7-6-7  9-7-4 10-6-4 10-4-6 10-4-6  7-6-7  8-7-5  9-2-9 14-3-3 12-1-7 11-4-5 17-1-2 18-0-2  35431.
07: Clunk NO BETA        215.0/360 2-13-5 1-8-11  5-9-6  9-8-3  6-9-5  6-7-7 ······ 10-4-6  8-6-6 14-3-3 10-2-8  6-6-8 12-4-4 13-2-5 11-5-4 12-4-4 11-1-8 11-3-6 18-1-1  35131.
08: KingSlayer           203.0/360 6-12-2 4-13-3  7-7-6  7-9-4  8-6-6  7-9-4 4-10-6 ······ 10-9-1 7-10-3  9-8-3 12-5-3  9-4-7  8-4-8 13-5-2 12-4-4 11-4-5 17-1-2 16-1-3  33241.
09: Clunk FUTILITY       183.0/360 4-14-2 3-11-6 2-14-4 7-11-2 5-11-4 6-10-4  6-8-6 9-10-1 ······  7-5-8  8-7-5 4-6-10 10-3-7 13-4-3  9-6-5  9-5-6  9-5-6 12-5-3 18-0-2  29516.
10: Clunk DELTA 150 NoWS 171.5/360 2-15-3 3-15-2  5-7-8 6-12-2  6-8-6 4-10-6 3-14-3 10-7-3  5-7-8 ······  9-5-6  9-8-3  9-2-9  2-9-9 7-10-3  7-8-5  9-3-8 16-2-2 15-2-3  27765.
11: Clunk                158.0/360 2-14-4 2-10-8 4-11-5 4-12-4 3-12-5 4-10-6 2-10-8  8-9-3  7-8-5  5-9-6 ······  7-9-4  4-8-8 12-6-2  8-8-4 10-5-5  6-9-5 11-4-5 13-2-5  25885.
12: Clunk DELTA HGM      157.5/360 0-15-5 1-17-2 2-15-3 5-13-2 3-11-6  6-7-7  6-6-8 5-12-3 6-4-10  8-9-3  9-7-4 ······  6-9-5  5-7-8  6-6-8  8-5-7 13-6-1 11-8-1 15-3-2  25241.
13: Clunk DELTA 150      155.0/360 0-16-4 2-15-3 3-10-7 3-13-4 6-11-3  7-8-5 4-12-4  4-9-7 3-10-7  2-9-9  8-4-8  9-6-5 ······  9-7-4  7-7-6  9-6-5 11-5-4 11-4-5 10-6-4  25234.
14: Clunk ALPHA          154.5/360 1-17-2 4-13-3 1-16-3 4-13-3  3-9-8  2-9-9 2-13-5  4-8-8 4-13-3  9-2-9 6-12-2  7-5-8  7-9-4 ······  9-6-5  8-4-8 10-7-3 10-4-6 19-1-0  24180.
15: Clunk DELTA          151.0/360 2-13-5 2-14-4 1-12-7 3-12-5 2-11-7 3-14-3 5-11-4 5-13-2  6-9-5 10-7-3  8-8-4  6-6-8  7-7-6  6-9-5 ······  9-7-4  8-7-5 11-5-4 16-3-1  24172.
16: Clunk RZR            140.5/360 2-11-7 0-14-6 3-12-5 3-13-4 1-12-7 1-12-7 4-12-4 4-12-4  5-9-6  8-7-5 5-10-5  5-8-7  6-9-5  4-8-8  7-9-4 ······  7-4-9  8-5-7 16-1-3  22522.
17: Clunk DELTA NoWS     134.0/360 1-14-5 0-17-3 1-13-6 4-13-3 1-10-9 4-11-5 1-11-8 4-11-5  5-9-6  3-9-8  9-6-5 6-13-1 5-11-4 7-10-3  7-8-5  4-7-9 ······ 12-3-5 13-3-4  21312.
18: FairyMax             98.5/360  0-13-7 0-17-3 3-15-2 3-15-2 0-18-2 1-17-2 3-11-6 1-17-2 5-12-3 2-16-2 4-11-5 8-11-1 4-11-5 4-10-6 5-11-4  5-8-7 3-12-5 ······ 15-4-1  15524.
19: TSCP64               51.5/360  1-19-0 0-17-3 1-16-3 1-16-3 0-17-3 0-18-2 1-18-1 1-16-3 0-18-2 2-15-3 2-13-5 3-15-2 6-10-4 1-19-0 3-16-1 1-16-3 3-13-4 4-15-1 ······  8731.0

It did better than I was expecting. But still no better than not having delta pruning enabled at all.

https://chessprogramming.wikispaces.com/Win+at+Chess 1 second per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk.no_alpha,      96.00,    1411.97,        22
clunk.all,           95.33,    1351.19,        22
clunk.beta,          95.00,    1447.83,        20
clunk.nmp,           95.00,    1431.39,        20
clunk.no_lmr,        95.00,    1369.70,        20
clunk.lmr,           94.33,    1369.80,        20
clunk.no_beta,       94.33,    1273.81,        20
clunk.futility,      92.33,    1444.39,        19
clunk,               92.00,    1416.61,        18
clunk.rzr,           92.00,    1372.86,        18
clunk.delta,         92.00,    1338.24,        18
clunk.delta_nows,    92.00,    1326.05,        18
clunk.delta150,      92.00,    1297.84,        18
clunk.alpha,         92.00,    1290.92,        18
clunk.delta150_nows, 92.00,    1284.00,        18
clunk.delta_hgm,     91.33,    1371.21,        18

https://chessprogramming.wikispaces.com ... but+deadly 5 seconds per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk.futility,      80.60,    1153.86,         8
clunk.beta,          79.85,    1131.96,        10
clunk.no_alpha,      79.85,    1112.68,        13
clunk.no_beta,       79.85,    1019.30,        10
clunk.lmr,           79.10,    1101.99,        10
clunk.nmp,           78.36,    1115.88,        10
clunk.alpha,         78.36,    1047.43,         8
clunk.delta150_nows, 78.36,    1026.56,         8
clunk.delta150,      78.36,    1021.06,         8
clunk.rzr,           77.61,    1108.07,         8
clunk.delta_nows,    77.61,    1093.99,         8
clunk.delta,         77.61,    1085.98,         8
clunk.no_lmr,        77.61,    1037.67,        10
clunk,               76.87,    1148.65,         8
clunk.all,           76.87,    1026.93,        13
clunk.delta_hgm,     76.12,    1089.84,         8

https://chessprogramming.wikispaces.com ... Kopec+Test 10 seconds per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk,               70.83,    1204.80,        12
clunk.rzr,           70.83,    1162.70,        12
clunk.delta_nows,    70.83,    1135.24,        12
clunk.delta_hgm,     70.83,    1134.86,        12
clunk.delta,         70.83,    1125.40,        12
clunk.all,           70.83,    1099.33,        18
clunk.alpha,         70.83,    1090.00,        12
clunk.delta150_nows, 70.83,    1054.57,        12
clunk.delta150,      70.83,    1052.38,        12
clunk.beta,          66.67,    1201.89,        15
clunk.nmp,           66.67,    1187.36,        15
clunk.no_alpha,      66.67,    1175.56,        18
clunk.lmr,           66.67,    1168.08,        15
clunk.no_lmr,        66.67,    1107.50,        15
clunk.no_beta,       66.67,    1062.40,        15
clunk.futility,      62.50,    1213.10,        13

https://chessprogramming.wikispaces.com/Kaufman+Test 10 seconds per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk.beta,          92.00,    1378.55,        14
clunk.nmp,           92.00,    1350.68,        14
clunk.lmr,           92.00,    1321.05,        14
clunk.no_lmr,        92.00,    1319.46,        14
clunk.futility,      88.00,    1380.35,        11
clunk,               88.00,    1358.04,        11
clunk.no_alpha,      88.00,    1339.62,        17
clunk.rzr,           88.00,    1309.54,        11
clunk.delta_hgm,     88.00,    1306.19,        11
clunk.all,           88.00,    1303.97,        18
clunk.delta,         88.00,    1302.58,        11
clunk.delta_nows,    88.00,    1295.84,        11
clunk.alpha,         88.00,    1258.98,        11
clunk.delta150,      88.00,    1243.16,        11
clunk.no_beta,       88.00,    1238.51,        14
clunk.delta150_nows, 88.00,    1236.75,        11

https://chessprogramming.wikispaces.com/LCT+II 15 seconds per position

Code: Select all

ENGINE,              SCORE, KNODES/SEC, AVG_DEPTH
clunk.all,           60.00,    1214.06,        16
clunk.beta,          57.14,    1317.98,        13
clunk.nmp,           57.14,    1297.85,        12
clunk.no_alpha,      57.14,    1285.37,        16
clunk.lmr,           54.29,    1260.34,        13
clunk.no_lmr,        54.29,    1226.73,        13
clunk.no_beta,       48.57,    1153.65,        13
clunk.futility,      45.71,    1322.05,        10
clunk.delta_hgm,     40.00,    1241.10,        10
clunk,               37.14,    1293.11,        10
clunk.rzr,           37.14,    1259.19,        10
clunk.delta,         37.14,    1222.25,        10
clunk.delta_nows,    37.14,    1209.28,        10
clunk.alpha,         37.14,    1190.69,        10
clunk.delta150,      37.14,    1176.58,        10
clunk.delta150_nows, 37.14,    1161.56,        10

Short time controls in relatively shallow tactical positions it does poorly (not surprisingly). In longer time controls on positions that are more positional or involving deep tactics it comes in middle of the pack.

Next up: variations on the razoring routine..

[zd3nik]

d=1 futility pruning is backward pruning that cannot make any kind of error.

Only if:

1) you do it on a per move basis so the following 2 requirements may be met:
2) your delta is larger than any difference a single move can make in your static positional eval function.
3) you don't do pruning on moves that give check

Well, (2) and (3) are the usual definition of 'futile'. The check evasions we are discussing satisfy all these criteria. And your code does apply the criteria per move, in QS, so that takes care of (1).

We are not talking about evasions. I feel like I'm talking to Zoolander or I'm taking crazy pills. This goes back to the original "I think you missed the negation" thing. No where, in any of this, is pruning happening when the side to move is in check. That's what the !(checks... stuff in the code is all about.

You're responses clearly show that we are communicating very badly (or you're just trolling me).

It doesn't really matter whether you implement the pruning as bulk or per-move pruning (other than in efficiency). What matters is which moves you search, and which not. You can always achieve the same tree in both cases.

Nonsense. How do you expect to fulfill #3 without doing pruning on a per move basis? And you're contradicting yourself. You just said dropping into qsearch satisfies #1 because delta pruning in qsearch does pruning on a per move basis.

And here's another contradiction coming from you: you've clearly said that you don't care whether a move gives check or not, you would prune any move that's below alpha + delta (and all moves after it - including those that give check). So you deny #3 in previous posts and yet in this post you happily agree that #3 is part of the very definition of futility pruning.

Your code searches [...] and all evasions (even those that are non-captures and non-checksand fall very far below alpha). I only pointed out that searching the latter is a waste of time, as they are moves that with certainty can be predicted to fail low. The 'checks' condition just does not belong in that test.

Yes, I search all moves when in check. Now let's just take a moment here to note that you are very clearly recommending doing pruning when in check.

You use a margin of 800 in that test, right? So if eval = alpha - 700 the test fails, and you will NOT drop into QS, right? So you stay in the d=1 node, which generates and searches all non-captures (amongst others). It does not even test them on a per-move basis for futility, not ever after making them, as you only do that in QS.

So the question was: why does your code search non-captures in positions where eval = alpha - 700? Do you expect there to be any non-captures that would raise eval so much that they don't fail low. And if not, why would you search them? That 800 margin is just so big that it effectively disables any pruning completely.

You're talking about what happens outside of the pruning heuristic. I don't expect any moves outside the heuristic to be able to overcome the deficit. The deltas are not a declaration of what I expect. They are "damage control". The deltas are just a margin of error. I've tried small, medium, and large deltas. Small deltas give more cutoffs but have a higher error rate. Large deltas produce fewer cutoffs (and yes, that means potentially wasting time looking at futile moves) but large deltas are less error prone.

Anyway, as I've said before, the deltas are not the issue. I have experimented with many deltas, all with similarly bad results. How many times have I said that now? 6? 7? When is it going to get through to you?

Stop latching on to the excessively high deltas in some "futile" effort to add weight to your arguments. The deltas are adjustable. And I'll say it again: I've used smaller deltas with similarly bad results. Starting to sink in yet?

That would be the condition if you wanted to outright prune the current node, i.e. return alpha rather than QS.

Yes, you are correct. I realized that mistake shortly after I posted it but I didn't have the energy to correct it. Qsearch will account for the "material" differences made by the move. You only need the delta to account for the lost ply (e.g. any non-capture/promotion moves that might have been searched via the ply this heuristic is taking out of the search). So in most engines 150 centipawns is probably enough. In mine it is not because many drawn positions are recognized and scored accordingly, and runaway passed pawn evaluation can also result in a positional evaluation difference of well over 150.

The point I was trying to make is: you need a "sufficiently large" delta before you can consider this form of pruning to be "backward" pruning. I don't have an excuse for why I neglected the effects of qsearch in my explanation. I am and always have been well aware of the process - just had a brain fart there.

We already know you disregard #3. ....

No!? Where do you get that idea from??? I repeatedly stated that checks are NEVER futile.

Correction, you've repeatedly stated that checks ARE candidates for futility pruning. See the cases above in which I call this out. See many of your previous posts.

Like this one for example:

When in check, futile moves deserve to be pruned just as much as when not in check.

If you want to claim otherwise now, I'm not going to disagree because I've been repeatedly stating that you should never do any kind of pruning when in check - and that obviously includes futility pruning. But maybe you should see a doctor. You've obviously got a brain tumor, or you're just going senile or something.

I only said that evasions are just as futile as any other move. 'Evasion' is not the same as 'check', right? In fact evasions very rarely are checks (although it can occasionally happen).

As far as I've ever seen in the context of chess, particularly chess engine development, that term has been exclusively used to mean "evasion from check".

So you'll just have to forgive me for misinterpreting your intent any time you used the term "evasion".

[Ferdy]

I've had a lot of trouble getting much value out of razoring and delta pruning, both techniques I classify as "alpha pruning" or "fail low pruning". The general idea behind both techniques is that if you're in a situation that looks likely to "fail low" in an alpha/beta search framework just return alpha. I'm over-simplifying of course, but that's the gist of it.

There is delta pruning here, not sure if you tried this.
https://chessprogramming.wikispaces.com/delta+pruning

I tried this in CDrill with slight modification on calculation of delta. Something like this.

Code: Select all

int qsearch(int alpha, int beta, int depth, bool incheck){
	bool pv_node = beta - alpha > 1;
	// ...

	// Prune based on static eval
	if (!incheck){
		best_value = eval();
		if (best_value >= beta)
			return best_value;
		if (best_value > alpha){
			alpha = best_value;
		}
		else{
			// Delta pruning: Assume we can capture the highest piece (not king) of opp
			if (!pv_node && get_opp_piecevalue() > QUEEN_VALUE + KNIGHT_VALUE && alpha < 5 * QUEEN_VALUE){
				if (best_value + get_opp_highest_piecevalue() <= alpha)
					return best_value;
			}
		}
	}

	// Gen and search moves
	generate_move();

	// ...
}

It gets a good result vs the version without delta pruning.

[hgm]

We are not talking about evasions. I feel like I'm talking to Zoolander or I'm taking crazy pills. This goes back to the original "I think you missed the negation" thing. No where, in any of this, is pruning happening when the side to move is in check. That's what the !(checks... stuff in the code is all about.

Well, I am talking (and have always been talking) about evasions. No way telling into what that morphs as after it enters your brain (because of the pills and such...).

As others have also tried to point out to you, nowhere pruning is happening when the side to move is in check, and all that I am saying (for the umptieth time) is that this is a mistake, and that you should prune moves when in check.

Nonsense. How do you expect to fulfill #3 without doing pruning on a per move basis?

By having a separate generator for checks, of course. I even described how such a generator would typically work in a mailbox design.

And you're contradicting yourself. You just said dropping into qsearch satisfies #1 because delta pruning in qsearch does pruning on a per move basis.

There seems to be a problem of logic here. That pruning on a per-move basis satisfies condition #1 does not imply that anything else will violate it, and thus in particular in does not imply that pruning on a per-move bases is the only way to satisfy #1.

And here's another contradiction coming from you: you've clearly said that you don't care whether a move gives check or not, you would prune any move that's below alpha + delta (and all moves after it - including those that give check). So you deny #3 in previous posts and yet in this post you happily agree that #3 is part of the very definition of futility pruning.

Sigh... A check is not an evasion.

Yes, I search all moves when in check. Now let's just take a moment here to note that you are very clearly recommending doing pruning when in check.

Exactly. Please let that sink in. There is no reason to refrain from backward pruning when you are in check.

Anyway, as I've said before, the deltas are not the issue. I have experimented with many deltas, all with similarly bad results. How many times have I said that now? 6? 7? When is it going to get through to you?

The first time you said it? There is little I can do to prevent you from saying it an 8th or 9th time... But as long as you keep bringing it up, the reply will of course remain the same. I just pointed out that a margin of 800 is nonsensically large, and should have the effect of practically disabling this kind of pruning alltogether. If disabling the pruning disway makes any effect of it go away, things are fine. But if you nevertheless see an effect on playing strength of something you disabled, (as you seem to have implied 6 or 7 times now) you should look for reasons other than the implementation of the disabled feature. That remains true, no matter how often you bring it up.

Yes, you are correct. I realized that mistake shortly after I posted it but I didn't have the energy to correct it. Qsearch will account for the "material" differences made by the move. You only need the delta to account for the lost ply (e.g. any non-capture/promotion moves that might have been searched via the ply this heuristic is taking out of the search). So in most engines 150 centipawns is probably enough. In mine it is not because many drawn positions are recognized and scored accordingly, and runaway passed pawn evaluation can also result in a positional evaluation difference of well over 150.

Well, scoring of draws is well known to cause problems in futility pruning. It depends on how you determine the value of the captured material. If you do it by a table of piece values, or by PST, you would overlook that KNK is draw, and prune the recapture KxP after PxB in KNPKB as futile, whileit in fact drew. This can be prevented by always using the difference of the material-table entries for the new and old material composition, but this makes the test more expensive, which especially hurts in a per-move implementation. The problem is almost always that the last Pawn is worth the game rather than just a pawn. So another sensible implenetation is to flag in the material table when you get in a situation where the remaining Pawn means everything, and then correct the base value of the Pawns accordingly. (E.g. with KNP you would have N=3, P=4.) This would not only cure the futility problem, but also cause better move sorting (prioritizing KxP over BxN), better SEE, etc. If Pawns are considered more valuable victims than minors in the MVV/LVA sort, it would also not interfere with bulk pruning. In othe rbulk-pruning implementations it is not significantly costly to check whether the opponent's mating potential depended on his last Pawn, and skip directly to the Pawn captures when other material falls below the futility threshold.

In general it will not be optimal to tune your margin to very exceptional cases that cause huge score swings. Trying to exempt these moves from pruning by increasing the margin will hurt more through wasting time on other moves than occasionally pruning the exceptional move unjustly will hurt you. If you want to improve, you should specifically test for the move type (similar to testing for promotions, and treating those as captures). Creating an unstoppable passer is logically equivalent to a promotion.

Correction, you've repeatedly stated that checks ARE candidates for futility pruning. See the cases above in which I call this out. See many of your previous posts.

Like this one for example:

When in check, futile moves deserve to be pruned just as much as when not in check.

Well, this entire discussion will remain completely pointless as long as you fail to understand the difference between checks and evasions. A check is a move that leaves the enemy King exposed to capture after it is done. An evasion is a move that has your own King exposed to capture before it is done. The statement you quote obviously deals with evasions, not with checks.

If you want to claim otherwise now, I'm not going to disagree because I've been repeatedly stating that you should never do any kind of pruning when in check - and that obviously includes futility pruning. But maybe you should see a doctor. You've obviously got a brain tumor, or you're just going senile or something.

Well, now that you mention it, this could very well be the root cause of the communication problem we seem to have. But I am afraid it is extremely obvious to any other reader who of the two of us actually has this problem...

As far as I've ever seen in the context of chess, particularly chess engine development, that term has been exclusively used to mean "evasion from check".

Right! So the check comes first, and the evasion only later, right? They are not the same move. First you have a move that is a check, and then it is followed by a move that is an evasion (from check), right?

[zd3nik]

There is delta pruning here, not sure if you tried this.
https://chessprogramming.wikispaces.com/delta+pruning

I tried this in CDrill with slight modification on calculation of delta. Something like this.

Code: Select all

int qsearch(int alpha, int beta, int depth, bool incheck){
	bool pv_node = beta - alpha > 1;
	// ...

	// Prune based on static eval
	if (!incheck){
		best_value = eval();
		if (best_value >= beta)
			return best_value;
		if (best_value > alpha){
			alpha = best_value;
		}
		else{
			// Delta pruning: Assume we can capture the highest piece (not king) of opp
			if (!pv_node && get_opp_piecevalue() > QUEEN_VALUE + KNIGHT_VALUE && alpha < 5 * QUEEN_VALUE){
				if (best_value + get_opp_highest_piecevalue() <= alpha)
					return best_value;
			}
		}
	}

	// Gen and search moves
	generate_move();

	// ...
}

It gets a good result vs the version without delta pruning.

I believe I did try the chessprogrammingwiki version a long time ago (in whatever engine I was working on back then). But I probably did it almost exactly like it's shown on the wiki. I don't remember how I tested it or how it effected results. But the fact that I didn't adopt it probably means I didn't like the results.

I will definitely be giving your variation a try. Just one question to make sure I adapt it to my engine properly:

Is get_opp_piecevalue() the sum of all opponent pieces (minus king)? And if so does it exclude or include pawns?

Thanks

[zd3nik]

Sigh... This is easily the most unproductive conversation in the history of mankind.

But as long as you keep bringing [delta margins] up

Nice try. Aside from the original post I have only said what I've said about deltas in "response" to you bringing it up.

And yes I understand that higher deltas reduce the effectiveness of the pruning heuristic. I've also said that like 2 times now. I've also explained my reasoning for using the larger deltas: as a test, not a permanent solution. Would it make you feel better if I lied and said I didn't know that large deltas effectively disable the routine until you pointed it out?

But if you nevertheless see an effect on playing strength of something you disabled, (as you seem to have implied 6 or 7 times now) you should look for reasons other than the implementation of the disabled feature.

Agreed.

That's actually part of the reason I started this thread. First to see if anyone could spot problems in the pruning heuristics as I had implemented them. Secondly to see if anyone knew of some interaction(s) these heuristics could have with other heuristics that might explain bad results.

Now let me take a step back here and acknowledge that all you started out trying to do is provide the feedback I was asking for. And believe it or not I appreciate that. It just seems that poor communication and/or poor reading comprehension has taken the thread into a darker place.

I don't agree with a lot of what you say (like futility pruning is just a nodes/sec optimization, futility pruning is a form of backward pruning, it's okay to prune when in check, etc) but I have tried to acknowledge the things you've said that have seemed useful/logical to me - like your comment about futility pruning interactions with fail-soft frameworks.

Well, scoring of draws is well known to cause problems in futility pruning. It depends on how you determine the value of the captured material. If you do it by a table of piece values, or by PST, you would overlook that KNK is draw, and prune the recapture KxP after PxB in KNPKB as futile, whileit in fact drew. This can be prevented by always using the difference of the material-table entries for the new and old material composition, but this makes the test more expensive, which especially hurts in a per-move implementation. The problem is almost always that the last Pawn is worth the game rather than just a pawn. So another sensible implenetation is to flag in the material table when you get in a situation where the remaining Pawn means everything, and then correct the base value of the Pawns accordingly. (E.g. with KNP you would have N=3, P=4.) This would not only cure the futility problem, but also cause better move sorting (prioritizing KxP over BxN), better SEE, etc. If Pawns are considered more valuable victims than minors in the MVV/LVA sort, it would also not interfere with bulk pruning. In othe rbulk-pruning implementations it is not significantly costly to check whether the opponent's mating potential depended on his last Pawn, and skip directly to the Pawn captures when other material falls below the futility threshold.

In general it will not be optimal to tune your margin to very exceptional cases that cause huge score swings. Trying to exempt these moves from pruning by increasing the margin will hurt more through wasting time on other moves than occasionally pruning the exceptional move unjustly will hurt you. If you want to improve, you should specifically test for the move type (similar to testing for promotions, and treating those as captures). Creating an unstoppable passer is logically equivalent to a promotion.

Also good advice. I knew draw scoring and runaway passers are a problem for futility pruning. I didn't know it was common knowledge nor did I know there are common solutions. Your suggestion here may very well be the solution to my alpha pruning problems. I have noticed that a lot of the games in the bullet tournaments I run go into relatively equal endgames, but rarely end in draws. Which seems to imply that the errors introduced by pruning take effect most often in the endgame - where the drawscore and runaway passer stuff kicks in.

Well, this entire discussion will remain completely pointless as long as you fail to understand the difference between checks and evasions.

Now back to our regularly scheduled program... You're obviously deliberately misinterpreting me. Nowhere do I say or imply that "evasion" == "check". But if you want to play the deliberate misinterpretation game, it's not very difficult to turn that around on you. Take this sentence typed by your very own fingers for example:

In fact evasions very rarely are checks (although it can occasionally happen).

That pretty clearly shows that you think checks ARE evasions on occasion. See how easy it is is to deliberately twist someone's words around to seem like they means something other than what was intended?

Checks are checks. Evasions are moves that get you out of check. And sometimes a move that gets you out of check also happens to "give" check.

Still seem to you like I don't know the difference between checks and evasions? Now if you actually misinterpreted what I said. Perhaps you should read it again with the knowledge that I know the difference between check and evasion.

Anyway, I think the only real disagreement we're having on this point is that you say it's okay to prune when "in" check. I've been saying it's just as bad to do pruning when "in" check as it is to prune away moves that "give" check. It seems pretty clear to me that you've also said it's okay to prune moves that "give" check. But now you seem to be implying you agree with me that pruning moves that "give" check is bad.

From now on, if we're going to continue this conversation, perhaps it would be best to do it with code. If you have a suggestion post some [pseudo] code that exemplifies your suggestion. I will do the same.