Can principal variation search be worth no Elo?

[algerbrex]

I checked this yesterday and for me, it is better if I do a re-search whenever the value is bigger than alpha, even if it is also bigger than beta. (Code)

Strange; checking if score > alpha does not prove that the move is a PV-move. Maybe I should run a test with this myself.

I'll try testing if the eval is within beta as well as being greater than alpha, but I believe like Jost mentioned it was a loss for me, although just score > alpha is still an Elo loss.

Annoyingly enough, I just realized with the test I showed last night I wasn't doing PVS in the root, so when I fixed that the Elo seemed to be dropping by -50, so I'm pretty stumped lol.

[Chan Rasjid]

I have to beg to differ. AFAIK, PVS has no accuracy issue at all. Whether we do a null window or a full window search for all LMR, the result of our search must be the same(except for some minor issues of having TT changes in a research); it is just we may need a research in cases of an alpha improvement.

I am not sure how it looks like in a pure alpha-beta search with PVS. It would make sense that every move that fails low with a null window will also fail low with a full window, and every move that is bigger than alpha with a null window will also be bigger than alpha with a full window.
But I am not so sure about how this looks in a realistic alpha-beta search with transposition table and lots of pruning that sometimes depend on how big alpha or beta are. Experimentally it sometimes happens, that a search with a null window raises alpha, but once researching it with a full window to the same depth, it turns out that it actually doesn't raise alpha. Same with null window searches that fail low, but once searched with a full windows they raise alpha.
Though that could be only the case for Nalwald, I don't know.

What you refer to is the well known "search instability" whenever your PVS implements a TT. The research may not be searching the exact same chess subbranch as in the earlier search due to TT changes; so a PVS FL may be followed by a fail high when re-searching with (score - 1, beta). In such cases, we need another research with the full window (alpha, beta). I think others must have tested that PVS is an overall winner against plain alpha-beta.

Another note. I do believe (if anyone care to check) that all top programs will use a null window whenever the search depth is reduced, whether it is LMR or nullmove.

I cannot comment if your program need a full window for some cases to decide on pruning, etc.

[Chan Rasjid]

My code checks if the eval score is higher than alpha, but below beta.
Your code only checks if the eval score is higher than alpha.

I checked this yesterday and for me, it is better if I do a re-search whenever the value is bigger than alpha, even if it is also bigger than beta. (Code)

I don't see why there is a need to do a research if the score >= beta; it is a plain and simple cutoff! You have to trust this alpha-beta algorithm that it is working fine

Of course, again if you test with a research, it is not certain that the score will not fall below beta.

[mvanthoor]

...

I don't see why there is a need to do a research if the score >= beta; it is a plain and simple cutoff! You have to trust this alpha-beta algorithm that it is working fine

This. If score > alpha, but also score >= beta, then it's a beta cutoff: you DON'T want to go down this line, because it's bad for you. If the PVS-test is only (score > alpha) instead of (score > alpha && score < beta), then you do a full research to AGAIN discover that this is not a good move and don't want to go down that line. The effort of the research is wasted. You'll end up (at best) making the PVS less effective, and, at worst, researching and wasting time so often that you actually do lose Elo.

[emadsen]

One optimization of alpha-beta that I've never quite been able to get working has been principal variation search. I understand the concept and how to implement it, but I've never quite been able to get an Elo gain from it.

PVS definitely helps my engine. I don't have hard numbers. Because I considered PVS essential to a basic engine, I've never measured the ELO difference between pure alpha / beta and alpha / beta + PVS.

PVS works very well when combined with LMR. The intent is to quickly prove late moves fail low. They're ordered late because the history heuristic has determined they're unlikely to cause a beta cutoff. So search them at a reduced depth. If a late move fails low, well, that's what you expected. However, if a late move fails high, perhaps the late move enables a tactical shot for the opponent. Perhaps. It's also possible the search doesn't have enough depth to see the tactic actually fails and the late move is weak and no serious threat. So, in a PVS framework...

1. You definitely want to re-search late moves that fail high. Re-search with full alpha / beta window to the original horizon.
2. However, avoid an unnecessary re-search if beta and the horizon are their original values.

My PVS implementation is simple, and has worked well for me:

Code: Select all

var searchHorizon = GetSearchHorizon(board, depth, horizon, move, cachedPosition, quietMoveNumber, drawnEndgame); // LMR
var moveBeta = (legalMoveNumber == 1) || ((MultiPv > 1) && (depth == 0))
    ? beta // Search with full alpha / beta window.
    : bestScore + 1; // Search with zero alpha / beta window.
// Play and search move.
Move.SetPlayed(ref move, true);
board.CurrentPosition.Moves[moveIndex] = move;
board.PlayMove(move);
var score = -GetDynamicScore(board, depth + 1, searchHorizon, true, -moveBeta, -alpha);
if (FastMath.Abs(score) == StaticScore.Interrupted)
{
    // Stop searching.
    board.UndoMove();
    return score;
}
if (score > bestScore)
{
    // Move may be stronger than principal variation.
    if ((moveBeta < beta) || (searchHorizon < horizon))
    {
        // Search move at unreduced horizon with full alpha / beta window.
        score = -GetDynamicScore(board, depth + 1, horizon, true, -beta, -alpha);
    }
}
board.UndoMove();

To test the effect of removing PVS, I simply changed the first lines to:

Code: Select all

var searchHorizon = GetSearchHorizon(board, depth, horizon, move, cachedPosition, quietMoveNumber, drawnEndgame); // LMR
var moveBeta = true || (legalMoveNumber == 1) || ((MultiPv > 1) && (depth == 0))
    ? beta // Search with full alpha / beta window.
    : bestScore + 1; // Search with zero alpha / beta window.

I get these results for the test position mentioned in the first post.

Without PVS:

Code: Select all

❯ .\MadChess.Engine.exe
position fen rn1qkb1r/pp2pppp/5n2/3p1b2/3P4/2N1P3/PP3PPP/R1BQKBNR w KQkq - 0 1

go depth 18
info depth 1 seldepth 9 time 62 nodes 696 score cp 12 nps 11272 pv g1f3
info depth 2 seldepth 6 time 71 nodes 1186 score cp 10 nps 16764 pv f1d3 f5d3
info depth 3 seldepth 11 time 73 nodes 4399 score cp -16 nps 60295 pv c1d2 b8c6 g1f3
info depth 4 seldepth 10 time 77 nodes 6824 score cp -25 nps 88143 pv g1h3 b8c6 f1d3 f5d3
info depth 5 seldepth 13 time 97 nodes 21910 score cp -9 nps 224724 pv f1b5 b8c6 d1a4 e7e6 b5c6
info depth 6 seldepth 14 time 113 nodes 47757 score cp -16 nps 423516 pv f1d3 f5d3 d1d3 b8c6 g1f3 e7e6
info depth 7 seldepth 15 time 124 nodes 64934 score cp 6 nps 525653 pv f1d3 f5d3 d1d3 b8c6 g1f3 e7e6 f3g5
info depth 8 seldepth 18 time 173 nodes 179510 score cp 57 nps 1039529 pv g1f3 b8c6 f3e5 h7h5 f1b5 f5d7 e5d7 d8d7
info depth 9 seldepth 18 time 210 nodes 259342 score cp 56 nps 1234964 pv g1f3 b8c6 f3e5 h7h5 f1b5 a8c8 h2h3 a7a5 e1g1
info depth 10 seldepth 20 time 278 nodes 400217 score cp 37 nps 1437550 pv g1f3 b8c6 f3e5 h7h5 f1b5 a8c8 h2h3 h8h6 e1g1 e7e6
info depth 11 seldepth 22 time 380 nodes 661167 score cp 43 nps 1738831 pv g1f3 b8c6 f3e5 h7h5 f1b5 a8c8 h2h3 a7a5 d1a4 f5d7 e5d7
info depth 12 seldepth 26 time 979 nodes 2426040 score cp 15 nps 2476984 pv g1f3 a7a6 f3e5 b8c6 d1a4 b7b5 e5f7 c8c6 d4e5 f2h1 c3d5 h8h6
info depth 13 seldepth 25 time 1942 nodes 5166493 score cp 21 nps 2660370 pv g1f3 a7a6 f3e5 b8c6 f1e2 a8a7 e1g1 d8c8 g2g4 f5e6 d4e5 f5d3 d1d3
info depth 14 seldepth 25 time 3452 nodes 9462439 score cp 24 nps 2741432 pv g1f3 a7a6 f3e5 b8c6 g2g4 f5e6 h1g1 h7h6 f1d3 d8c8 h2h3 a8a7 g1g3 c6e5
info depth 15 seldepth 30 time 9036 nodes 25683279 score cp 8 nps 2842306 pv g1f3 a7a6 f3e5 b8d7 g2g4 f5e6 e5d7 e6d7 f1e2 d7e6 h2h4 h7h6 h1h3 a8c8 d1a4
info depth 16 seldepth 31 time 14603 nodes 42129063 score cp 17 nps 2884997 pv g1f3 a7a6 f3e5 b8d7 g2g4 f5e6 f1e2 g7g5 e1g1 f8g7 f2f4 d7e5 d4e5 f6e4 c3e4 d5e4
info depth 17 seldepth 30 time 25574 nodes 74214123 score cp 16 nps 2901955 pv g1f3 a7a6 f3e5 b8d7 g2g4 f5e6 f1e2 g7g5 h2h4 f8h6 f2f4 g5f4 e5d7 d8d7 g4g5 f4f3 e2f3
info depth 18 seldepth 33 time 70877 nodes 205493460 score cp 3 nps 2899282 pv g1f3 a7a6 f3e5 b8d7 g2g4 f5e6 f1e2 a8c8 e1g1 b7b5 a2a3 f6e4 d1b3 g7g6 e2f3 e4f6 b3d1 d7e5
bestmove g1f3

With PVS:

Code: Select all

❯ .\MadChess.Engine.exe
position fen rn1qkb1r/pp2pppp/5n2/3p1b2/3P4/2N1P3/PP3PPP/R1BQKBNR w KQkq - 0 1

go depth 18
info depth 1 seldepth 6 time 64 nodes 184 score cp 12 nps 2883 pv g1f3
info depth 2 seldepth 6 time 72 nodes 641 score cp 10 nps 8849 pv f1d3 f5d3
info depth 3 seldepth 11 time 75 nodes 4103 score cp -16 nps 54817 pv c1d2 b8c6 g1f3
info depth 4 seldepth 11 time 77 nodes 6791 score cp -25 nps 87636 pv g1h3 b8c6 f1d3 f5d3
info depth 5 seldepth 12 time 91 nodes 12403 score cp -16 nps 136326 pv h2h4 b8c6 g1f3 a7a5 f1e2
info depth 6 seldepth 16 time 112 nodes 63715 score cp 24 nps 569905 pv g1f3 h7h5 f3e5 b8c6 f1b5 a8c8
info depth 7 seldepth 16 time 124 nodes 93171 score cp 34 nps 752963 pv g1f3 b8c6 f3e5 a7a6 g2g4 c6e5 g4f5
info depth 8 seldepth 16 time 134 nodes 121770 score cp 30 nps 906456 pv g1f3 b8c6 f3e5 a7a6 g2g4 c6e5 g4f5 e5c4
info depth 9 seldepth 18 time 149 nodes 159111 score cp 42 nps 1066378 pv g1f3 b8c6 f3e5 a7a6 g2g4 f5e6 d1a4 a8c8 f1a6
info depth 10 seldepth 19 time 191 nodes 252419 score cp 25 nps 1321572 pv g1f3 b8c6 f3e5 a7a6 f1d3 f5d3 d1d3 a8c8 e1g1 c6e5
info depth 11 seldepth 22 time 275 nodes 450625 score cp 21 nps 1639114 pv g1f3 b8c6 f3e5 e7e6 f1b5 a8c8 b5c6 b7c6 d1a4 f6d7 e5c6
info depth 12 seldepth 22 time 575 nodes 1283526 score cp 16 nps 2232596 pv g1f3 b8d7 f3e5 a7a6 h2h4 f5e6 e5d7 d8d7 f1d3 a8c8 e1g1 b7b5
info depth 13 seldepth 26 time 1406 nodes 3820846 score cp 21 nps 2717280 pv g1f3 b8c6 f3e5 a8c8 f1b5 f6d7 e5c6 b7c6 g2g4 f5e6 b5d3 d7f6 g4g5
info depth 14 seldepth 22 time 1939 nodes 5389403 score cp 14 nps 2779912 pv g1f3 b8c6 f3e5 a8c8 f1b5 f6d7 e5c6 b7c6 g2g4 f5e6 b5d3 g7g5 c1d2 f8g7
info depth 15 seldepth 26 time 4687 nodes 13707931 score cp 20 nps 2924689 pv g1f3 b8d7 f3e5 a7a6 d1b3 d8c8 f1e2 f5e6 e1g1 h7h5 c1d2 h8h6 e5d7 c8d7 e2d3
info depth 16 seldepth 28 time 9950 nodes 29757399 score cp 19 nps 2990576 pv g1f3 b8c6 f3e5 f6d7 g2g4 f5e6 e5d7 d8d7 h1g1 a8d8 g1g3 a7a6 g4g5 d7c7 f1d3 b7b5
info depth 17 seldepth 29 time 17781 nodes 53610483 score cp 17 nps 3015070 pv g1f3 b8c6 f3e5 f6d7 g2g4 f5e6 e5d7 d8d7 h1g1 a8d8 g1g3 g7g6 a2a3 d7c7 f1d3 f8g7 c1d2
info depth 18 seldepth 32 time 30117 nodes 91704585 score cp 15 nps 3044970 pv g1f3 b8c6 f3e5 a8c8 d1b3 e7e6 b3b7 c6e5 d4e5 c8c7 f1b5 f6d7 b7a6 f8b4 a6a4 b4c3 b2c3 c7c3
bestmove g1f3

So PVS reduces the node count to 45% of pure alpha / beta. It reduces time-to-depth to 42% of pure alpha / beta. For this particular position.

Note 1: I don't use aspiration windows.

Note 2: I distinguish between alpha and bestScore because of how I implement MultiPV (alpha is not raised at the root, yet I track the score of the best move, which could be > alpha, though < beta). For the purposes of this discussion, assume bestScore == alpha.

[mvanthoor]

Yesterday night I ran a test between three Rustic versions.

- No PVS is a clear Elo loss.
- PVS with only the score > alpha check (without "&& score < beta") seems to be a gain... of +3 to +29 Elo. To be honest, I don't understand this because researching on a fail high (when not using LMR) shouldn't be useful. I expected this to be about equal, or a bit worse because of the unnecessary re-searches.

On the other hand, I also save the "best of the worst move" (the best-move that fails low the highest) in the TT, which shouldn't for all intents and purposes bring any Elo gain, but it gives the engine some 40-50 Elo.

Code: Select all

Rank Name                          Elo     +/-   Games   Score    Draw 
   0 Rustic Alpha 3.6.100            8       9    4000   51.2%   26.4% 
   1 Rustic APVS1 3.7.100           16      13    2000   52.3%   26.9% 
   2 Rustic ANoPVS 3.7.101         -33      13    2000   45.3%   25.9% 

4000 of 4000 games finished.

[R. Tomasi]

I compiled two versions of Pygmalion to test the raw influence of PVS:

• Plain alpha-beta search, with no TT, no pruning of any sort. Just heuristics an killers for move-ordering:

  Code: Select all

  0:  +0.00585938 -
    3.00 N   in    114 mcs =>   26.2 kN/s
  
  1:   +0.0214844 - h4
    64.0 N   in    137 mcs =>    466 kN/s
  
  2:            0 - Bd3 e6 Bxf5 xf5
    3.92 kN  in   2.57 ms  =>   1.52 MN/s
  
  3:  +0.00976562 - h4 e6 a3
    10.0 kN  in   5.70 ms  =>   1.76 MN/s
  
  4:  -0.00390625 - f3 h5 Bd3 e6 Bxf5 xf5
     168 kN  in    112 ms  =>   1.49 MN/s
  
  5:   +0.0117188 - Bd3 Bxd3 Qxd3 e6 Nf3
     623 kN  in    359 ms  =>   1.73 MN/s
  
  6:  +0.00195312 - Qb3 Qd7 Nf3 Nc6 h3 e6
    13.4 MN  in   7.93 s   =>   1.69 MN/s
  
  7:    +0.015625 - Qb3 Qd7 Nf3 Nc6 h3 Be4 Rg1
    64.9 MN  in   38.5 s   =>   1.69 MN/s
  

• Same as above, only difference is PVS is enabled:

  Code: Select all

  0:  +0.00585938 -
    3.00 N   in   81.7 mcs =>   36.7 kN/s
  
  1:   +0.0214844 - h4
    70.0 N   in    146 mcs =>    480 kN/s
  
  2:            0 - Bd3 e6 Bxf5 xf5
    1.91 kN  in   1.09 ms  =>   1.75 MN/s
  
  3:  +0.00976562 - h4 e6 a3
    5.12 kN  in   2.82 ms  =>   1.82 MN/s
  
  4:  -0.00390625 - f3 h5 Bd3 e6 Bxf5 xf5
     117 kN  in   63.9 ms  =>   1.84 MN/s
  
  5:   +0.0117188 - Bd3 Bxd3 Qxd3 e6 Nf3
     401 kN  in    209 ms  =>   1.92 MN/s
  
  6:  +0.00195312 - Qb3 Qd7 Nf3 Nc6 h3 e6
    3.87 MN  in   2.05 s   =>   1.88 MN/s
  
  7:    +0.015625 - Qb3 Qd7 Nf3 Nc6 h3 Be4 Rg1
    42.1 MN  in   22.2 s   =>   1.90 MN/s
  

This very clearly shows that PVS is helping a lot in Pygmalion: fewer nodes searched and higher NPS. Still the results are somewhat misleading, since PVS helps even more in Pygmalion if I turn TT and all the other search optimizations on (there are a lot of synergetic effects, especially concerning the TT, since the ZWS will improve move-ordering via TT). But even without that, the speed improvement is overall roughly a factor 2.

[algerbrex]

One optimization of alpha-beta that I've never quite been able to get working has been principal variation search. I understand the concept and how to implement it, but I've never quite been able to get an Elo gain from it.

PVS definitely helps my engine. I don't have hard numbers. Because I considered PVS essential to a basic engine, I've never measured the ELO difference between pure alpha / beta and alpha / beta + PVS.

PVS works very well when combined with LMR. The intent is to quickly prove late moves fail low. They're ordered late because the history heuristic has determined they're unlikely to cause a beta cutoff. So search them at a reduced depth. If a late move fails low, well, that's what you expected. However, if a late move fails high, perhaps the late move enables a tactical shot for the opponent. Perhaps. It's also possible the search doesn't have enough depth to see the tactic actually fails and the late move is weak and no serious threat. So, in a PVS framework...

1. You definitely want to re-search late moves that fail high. Re-search with full alpha / beta window to the original horizon.
2. However, avoid an unnecessary re-search if beta and the horizon are their original values.

My PVS implementation is simple, and has worked well for me:

Code: Select all

var searchHorizon = GetSearchHorizon(board, depth, horizon, move, cachedPosition, quietMoveNumber, drawnEndgame); // LMR
var moveBeta = (legalMoveNumber == 1) || ((MultiPv > 1) && (depth == 0))
    ? beta // Search with full alpha / beta window.
    : bestScore + 1; // Search with zero alpha / beta window.
// Play and search move.
Move.SetPlayed(ref move, true);
board.CurrentPosition.Moves[moveIndex] = move;
board.PlayMove(move);
var score = -GetDynamicScore(board, depth + 1, searchHorizon, true, -moveBeta, -alpha);
if (FastMath.Abs(score) == StaticScore.Interrupted)
{
    // Stop searching.
    board.UndoMove();
    return score;
}
if (score > bestScore)
{
    // Move may be stronger than principal variation.
    if ((moveBeta < beta) || (searchHorizon < horizon))
    {
        // Search move at unreduced horizon with full alpha / beta window.
        score = -GetDynamicScore(board, depth + 1, horizon, true, -beta, -alpha);
    }
}
board.UndoMove();

To test the effect of removing PVS, I simply changed the first lines to:

Code: Select all

var searchHorizon = GetSearchHorizon(board, depth, horizon, move, cachedPosition, quietMoveNumber, drawnEndgame); // LMR
var moveBeta = true || (legalMoveNumber == 1) || ((MultiPv > 1) && (depth == 0))
    ? beta // Search with full alpha / beta window.
    : bestScore + 1; // Search with zero alpha / beta window.

I get these results for the test position mentioned in the first post.

Without PVS:

Code: Select all

❯ .\MadChess.Engine.exe
position fen rn1qkb1r/pp2pppp/5n2/3p1b2/3P4/2N1P3/PP3PPP/R1BQKBNR w KQkq - 0 1

go depth 18
info depth 1 seldepth 9 time 62 nodes 696 score cp 12 nps 11272 pv g1f3
info depth 2 seldepth 6 time 71 nodes 1186 score cp 10 nps 16764 pv f1d3 f5d3
info depth 3 seldepth 11 time 73 nodes 4399 score cp -16 nps 60295 pv c1d2 b8c6 g1f3
info depth 4 seldepth 10 time 77 nodes 6824 score cp -25 nps 88143 pv g1h3 b8c6 f1d3 f5d3
info depth 5 seldepth 13 time 97 nodes 21910 score cp -9 nps 224724 pv f1b5 b8c6 d1a4 e7e6 b5c6
info depth 6 seldepth 14 time 113 nodes 47757 score cp -16 nps 423516 pv f1d3 f5d3 d1d3 b8c6 g1f3 e7e6
info depth 7 seldepth 15 time 124 nodes 64934 score cp 6 nps 525653 pv f1d3 f5d3 d1d3 b8c6 g1f3 e7e6 f3g5
info depth 8 seldepth 18 time 173 nodes 179510 score cp 57 nps 1039529 pv g1f3 b8c6 f3e5 h7h5 f1b5 f5d7 e5d7 d8d7
info depth 9 seldepth 18 time 210 nodes 259342 score cp 56 nps 1234964 pv g1f3 b8c6 f3e5 h7h5 f1b5 a8c8 h2h3 a7a5 e1g1
info depth 10 seldepth 20 time 278 nodes 400217 score cp 37 nps 1437550 pv g1f3 b8c6 f3e5 h7h5 f1b5 a8c8 h2h3 h8h6 e1g1 e7e6
info depth 11 seldepth 22 time 380 nodes 661167 score cp 43 nps 1738831 pv g1f3 b8c6 f3e5 h7h5 f1b5 a8c8 h2h3 a7a5 d1a4 f5d7 e5d7
info depth 12 seldepth 26 time 979 nodes 2426040 score cp 15 nps 2476984 pv g1f3 a7a6 f3e5 b8c6 d1a4 b7b5 e5f7 c8c6 d4e5 f2h1 c3d5 h8h6
info depth 13 seldepth 25 time 1942 nodes 5166493 score cp 21 nps 2660370 pv g1f3 a7a6 f3e5 b8c6 f1e2 a8a7 e1g1 d8c8 g2g4 f5e6 d4e5 f5d3 d1d3
info depth 14 seldepth 25 time 3452 nodes 9462439 score cp 24 nps 2741432 pv g1f3 a7a6 f3e5 b8c6 g2g4 f5e6 h1g1 h7h6 f1d3 d8c8 h2h3 a8a7 g1g3 c6e5
info depth 15 seldepth 30 time 9036 nodes 25683279 score cp 8 nps 2842306 pv g1f3 a7a6 f3e5 b8d7 g2g4 f5e6 e5d7 e6d7 f1e2 d7e6 h2h4 h7h6 h1h3 a8c8 d1a4
info depth 16 seldepth 31 time 14603 nodes 42129063 score cp 17 nps 2884997 pv g1f3 a7a6 f3e5 b8d7 g2g4 f5e6 f1e2 g7g5 e1g1 f8g7 f2f4 d7e5 d4e5 f6e4 c3e4 d5e4
info depth 17 seldepth 30 time 25574 nodes 74214123 score cp 16 nps 2901955 pv g1f3 a7a6 f3e5 b8d7 g2g4 f5e6 f1e2 g7g5 h2h4 f8h6 f2f4 g5f4 e5d7 d8d7 g4g5 f4f3 e2f3
info depth 18 seldepth 33 time 70877 nodes 205493460 score cp 3 nps 2899282 pv g1f3 a7a6 f3e5 b8d7 g2g4 f5e6 f1e2 a8c8 e1g1 b7b5 a2a3 f6e4 d1b3 g7g6 e2f3 e4f6 b3d1 d7e5
bestmove g1f3

With PVS:

Code: Select all

❯ .\MadChess.Engine.exe
position fen rn1qkb1r/pp2pppp/5n2/3p1b2/3P4/2N1P3/PP3PPP/R1BQKBNR w KQkq - 0 1

go depth 18
info depth 1 seldepth 6 time 64 nodes 184 score cp 12 nps 2883 pv g1f3
info depth 2 seldepth 6 time 72 nodes 641 score cp 10 nps 8849 pv f1d3 f5d3
info depth 3 seldepth 11 time 75 nodes 4103 score cp -16 nps 54817 pv c1d2 b8c6 g1f3
info depth 4 seldepth 11 time 77 nodes 6791 score cp -25 nps 87636 pv g1h3 b8c6 f1d3 f5d3
info depth 5 seldepth 12 time 91 nodes 12403 score cp -16 nps 136326 pv h2h4 b8c6 g1f3 a7a5 f1e2
info depth 6 seldepth 16 time 112 nodes 63715 score cp 24 nps 569905 pv g1f3 h7h5 f3e5 b8c6 f1b5 a8c8
info depth 7 seldepth 16 time 124 nodes 93171 score cp 34 nps 752963 pv g1f3 b8c6 f3e5 a7a6 g2g4 c6e5 g4f5
info depth 8 seldepth 16 time 134 nodes 121770 score cp 30 nps 906456 pv g1f3 b8c6 f3e5 a7a6 g2g4 c6e5 g4f5 e5c4
info depth 9 seldepth 18 time 149 nodes 159111 score cp 42 nps 1066378 pv g1f3 b8c6 f3e5 a7a6 g2g4 f5e6 d1a4 a8c8 f1a6
info depth 10 seldepth 19 time 191 nodes 252419 score cp 25 nps 1321572 pv g1f3 b8c6 f3e5 a7a6 f1d3 f5d3 d1d3 a8c8 e1g1 c6e5
info depth 11 seldepth 22 time 275 nodes 450625 score cp 21 nps 1639114 pv g1f3 b8c6 f3e5 e7e6 f1b5 a8c8 b5c6 b7c6 d1a4 f6d7 e5c6
info depth 12 seldepth 22 time 575 nodes 1283526 score cp 16 nps 2232596 pv g1f3 b8d7 f3e5 a7a6 h2h4 f5e6 e5d7 d8d7 f1d3 a8c8 e1g1 b7b5
info depth 13 seldepth 26 time 1406 nodes 3820846 score cp 21 nps 2717280 pv g1f3 b8c6 f3e5 a8c8 f1b5 f6d7 e5c6 b7c6 g2g4 f5e6 b5d3 d7f6 g4g5
info depth 14 seldepth 22 time 1939 nodes 5389403 score cp 14 nps 2779912 pv g1f3 b8c6 f3e5 a8c8 f1b5 f6d7 e5c6 b7c6 g2g4 f5e6 b5d3 g7g5 c1d2 f8g7
info depth 15 seldepth 26 time 4687 nodes 13707931 score cp 20 nps 2924689 pv g1f3 b8d7 f3e5 a7a6 d1b3 d8c8 f1e2 f5e6 e1g1 h7h5 c1d2 h8h6 e5d7 c8d7 e2d3
info depth 16 seldepth 28 time 9950 nodes 29757399 score cp 19 nps 2990576 pv g1f3 b8c6 f3e5 f6d7 g2g4 f5e6 e5d7 d8d7 h1g1 a8d8 g1g3 a7a6 g4g5 d7c7 f1d3 b7b5
info depth 17 seldepth 29 time 17781 nodes 53610483 score cp 17 nps 3015070 pv g1f3 b8c6 f3e5 f6d7 g2g4 f5e6 e5d7 d8d7 h1g1 a8d8 g1g3 g7g6 a2a3 d7c7 f1d3 f8g7 c1d2
info depth 18 seldepth 32 time 30117 nodes 91704585 score cp 15 nps 3044970 pv g1f3 b8c6 f3e5 a8c8 d1b3 e7e6 b3b7 c6e5 d4e5 c8c7 f1b5 f6d7 b7a6 f8b4 a6a4 b4c3 b2c3 c7c3
bestmove g1f3

So PVS reduces the node count to 45% of pure alpha / beta. It reduces time-to-depth to 42% of pure alpha / beta. For this particular position.

Note 1: I don't use aspiration windows.

Note 2: I distinguish between alpha and bestScore because of how I implement MultiPV (alpha is not raised at the root, yet I track the score of the best move, which could be > alpha, though < beta). For the purposes of this discussion, assume bestScore == alpha.

Thanks for taking the time to test this Erik.

I think right now what I'm going to do is rewrite the search from scratch, and this time add PVS early and test it since right now the move generator is the only bug-free place I'm certain of. If PVS still doesn't work even after rewriting things, I'll know a bug somewhere else is affecting things.

[R. Tomasi]

On the other hand, I also save the "best of the worst move" (the best-move that fails low the highest) in the TT, which shouldn't for all intents and purposes bring any Elo gain, but it gives the engine some 40-50 Elo.

Assuming you're using iterative deepening and order TT moves first, then that should actually help with move ordering, I would think.

[algerbrex]

I think while I continue to debug this issue, I'll post updates here, and hopefully, they'll be useful to future newcomers like me.

So far what I've done is rewrite the search from scratch, and only include MVV-LVA move ordering and killer moves. I've also gotten rid of an entire function just for searching from the root, as using only one function was cleaner IMO. So far my attempts at adding PVS even to this new search routine are still failing.

Again, strangely enough, my time to depth and nodes searched are both decreasing, but I'm losing 10-12 Elo every time I enable PVS.

Although I'm tempted to chuck PVS to the side and move forward with other features (since it isn't strictly necessary), it (1) should be giving me an Elo gain, and there's no point in missing out on Elo, and (2) I suspect that PVS is bringing to light some obscure bug in Blunder, and it'd bother me if I never figured out what it was.

Right now my plan of debugging is to look around the engine and scrutinize everything. I know my move generator is working correctly and is bug-free, from extensive testing, so that's where I'm starting from. Since the move generator is bug-free, I know the issue lies somewhere within the search file or evaluation file. The only problem is figuring out where exactly...

Currently, I've been brainstorming and writing down a list of possible issues that might be causing PVS to fail. My two current working theories are that:

• PVS isn't actually helping my engine, and I'm not manually testing enough positions to see that. This would mean of course that the number of researches that need to be performed because the null-window search failed high would be offering any gains from PVS. This shouldn't be happening with good move ordering, which would indicate there's a bug somewhere with that.
• PVS is implemented fine, move ordering is fine, but there's a bug somewhere else. If this is the case, the bug should be easier to locate since I rewrote and cleaned up the search.

In the next couple of days, I'll be doing some ruthless bug hunting, and I hope to report back with some positive news that'll be useful to those in the future dealing with this same issue.