algerbrex wrote: ↑Wed Sep 15, 2021 6:52 pm
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...
- You definitely want to re-search late moves that fail high. Re-search with full alpha / beta window to the original horizon.
- 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.