Can principal variation search be worth no Elo?

[R. Tomasi]

So far testing isn't looking good for PVS, and its still showing up as no gain, even after the rewrite. At least it's not a loss anymore so that's progress

From some cursory observations, PVS seems to be reducing the node count and time-to-depth once again. For example using the original position from this thread, with no PVS:

Code: Select all

info depth 1 score cp 29 time 5 nodes 109
info depth 2 score cp 9 time 53 nodes 710
info depth 3 score cp 22 time 13 nodes 6488
info depth 4 score cp 13 time 17 nodes 31757
info depth 5 score cp 34 time 81 nodes 176965
info depth 6 score cp 31 time 286 nodes 857950
info depth 7 score cp 37 time 1743 nodes 5194817
Bestmove: g1f3
Time: 7500ms

With PVS:

Code: Select all

info depth 1 score cp 29 time 2 nodes 109
info depth 2 score cp 9 time 9 nodes 710
info depth 3 score cp 22 time 10 nodes 7026
info depth 4 score cp 13 time 24 nodes 31294
info depth 5 score cp 34 time 79 nodes 178970
info depth 6 score cp 31 time 285 nodes 835773
info depth 7 score cp 37 time 1662 nodes 5027167
Bestmove: g1f3
Time: 7500ms

I did notice in a couple of positions the node count would spike slightly higher at lower depths, so I'll try experimenting more with disabling PVS then and see how that goes.

Have you verified if the PV is the same in both versions if you disable the TT? I'm just guessing here, but if nodecount is reduced and you don't get any ELO gain, then the only explanation I would see is that the versions play different moves at some point. PVS should yield the same PV than normal alpha-beta if there is no TT. In Pygmalion I actually get exactly the same PV, even with TT enabled. It's just a guess, but it may help debugging.

[algerbrex]

So far testing isn't looking good for PVS, and its still showing up as no gain, even after the rewrite. At least it's not a loss anymore so that's progress

From some cursory observations, PVS seems to be reducing the node count and time-to-depth once again. For example using the original position from this thread, with no PVS:

Code: Select all

info depth 1 score cp 29 time 5 nodes 109
info depth 2 score cp 9 time 53 nodes 710
info depth 3 score cp 22 time 13 nodes 6488
info depth 4 score cp 13 time 17 nodes 31757
info depth 5 score cp 34 time 81 nodes 176965
info depth 6 score cp 31 time 286 nodes 857950
info depth 7 score cp 37 time 1743 nodes 5194817
Bestmove: g1f3
Time: 7500ms

With PVS:

Code: Select all

info depth 1 score cp 29 time 2 nodes 109
info depth 2 score cp 9 time 9 nodes 710
info depth 3 score cp 22 time 10 nodes 7026
info depth 4 score cp 13 time 24 nodes 31294
info depth 5 score cp 34 time 79 nodes 178970
info depth 6 score cp 31 time 285 nodes 835773
info depth 7 score cp 37 time 1662 nodes 5027167
Bestmove: g1f3
Time: 7500ms

I did notice in a couple of positions the node count would spike slightly higher at lower depths, so I'll try experimenting more with disabling PVS then and see how that goes.

Have you verified if the PV is the same in both versions if you disable the TT? I'm just guessing here, but if nodecount is reduced and you don't get any ELO gain, then the only explanation I would see is that the versions play different moves at some point. PVS should yield the same PV than normal alpha-beta if there is no TT. In Pygmalion I actually get exactly the same PV, even with TT enabled. It's just a guess, but it may help debugging.

Yup, I'm in the same boat as you. Even with the TT enabled, the PV is the exact same. Another example. Without PVS:

Code: Select all

info depth 1 score cp -116 time 0 nodes 175 pv h1g1
info depth 2 score cp -135 time 16 nodes 3104 pv e4g5 c7f4
info depth 3 score cp -129 time 31 nodes 12831 pv e4g5 h7h6 g5e4
info depth 4 score cp -136 time 104 nodes 89371 pv c1c7 d8c7 b4d6 c7b7
info depth 5 score cp -134 time 176 nodes 452460 pv d1h5 h7h6 c1e1 c7f4 h1g1
info depth 6 score cp -133 time 1039 nodes 2612105 pv d1h5 f7f5 c1c7 d8c7 b4d6 c7c6
info depth 7 score cp -112 time 3515 nodes 11522475 pv c1c7 d8c7 b4d6 c7b7 d6b8 b7b8 d1h5
Bestmove: c1c7
Time: 7500ms

With PVS:

Code: Select all

info depth 1 score cp -116 time 12 nodes 194 pv h1g1
info depth 2 score cp -135 time 6 nodes 2898 pv e4g5 c7f4
info depth 3 score cp -129 time 11 nodes 12092 pv e4g5 h7h6 g5e4
info depth 4 score cp -136 time 55 nodes 70728 pv c1c7 d8c7 b4d6 c7b7
info depth 5 score cp -134 time 146 nodes 409814 pv d1h5 h7h6 c1e1 c7f4 h1g1
info depth 6 score cp -133 time 672 nodes 1903127 pv d1h5 f7f5 c1c7 d8c7 b4d6 c7c6
info depth 7 score cp -112 time 2148 nodes 9140775 pv c1c7 d8c7 b4d6 c7b7 d6b8 b7b8 d1h5
Bestmove: c1c7
Time: 7500ms

I have to admit, I'm pretty stumped as to what could be the issue, especially since I've rewritten the engine's search routine and I've been pretty diligent in weeding out bugs. The only constant would be the TT, but I fixed the bugs that've been pointed out.

[mvanthoor]

So far testing isn't looking good for PVS, and its still showing up as no gain, even after the rewrite. At least it's not a loss anymore so that's progress

Is this in a branch on GitHub somewhere? Yesterday I only saw up to and including the 6.0.0 release.

[R. Tomasi]

For example using the original position from this thread, with no PVS:

Code: Select all

info depth 1 score cp 29 time 5 nodes 109
info depth 2 score cp 9 time 53 nodes 710
info depth 3 score cp 22 time 13 nodes 6488
info depth 4 score cp 13 time 17 nodes 31757
info depth 5 score cp 34 time 81 nodes 176965
info depth 6 score cp 31 time 286 nodes 857950
info depth 7 score cp 37 time 1743 nodes 5194817
Bestmove: g1f3
Time: 7500ms

With PVS:

Code: Select all

info depth 1 score cp 29 time 2 nodes 109
info depth 2 score cp 9 time 9 nodes 710
info depth 3 score cp 22 time 10 nodes 7026
info depth 4 score cp 13 time 24 nodes 31294
info depth 5 score cp 34 time 79 nodes 178970
info depth 6 score cp 31 time 285 nodes 835773
info depth 7 score cp 37 time 1662 nodes 5027167
Bestmove: g1f3
Time: 7500ms

To me the nodecounts that you get when using PVS seem to high, I would expect the effect to be more pronounced:

• 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
  

My results above are without TT and without any kind of pruning/reductions, though. That might explain why the effect is so strong.

[algerbrex]

So far testing isn't looking good for PVS, and its still showing up as no gain, even after the rewrite. At least it's not a loss anymore so that's progress

Is this in a branch on GitHub somewhere? Yesterday I only saw up to and including the 6.0.0 release.

Ah no, this is just the dev version on my laptop. I have yet to start a dev branch.

Edit: Just uploaded the dev version of Blunder in a new branch: https://github.com/algerbrex/blunder/tree/develop

[emadsen]

Edit: Just uploaded the dev version of Blunder in a new branch: https://github.com/algerbrex/blunder/tree/develop

I read your search code. Here are my suggestions:

1. You should immediately update the TT and return beta at line 155. I realize it may not matter based on lines 173 onwards. However, it's confusing to me. You've found a beta cutoff. So cutoff immediately.
2. Your TT should store the score precision so you can distinguish between lower bound (beta cutoff), upper bound (fail low), and exact. You need to know the bound for correct score cutoffs at line 113.
3. Your doPVS boolean logic is incorrect. You set it to false initially, then true when score exceeds alpha. That's backwards. DoPvs should be true initially (when legalMoveNumber == 1), false otherwise.
4. To get the most out of PVS, you need to add LMR. For first legal move, search full alpha beta window at unreduced depth. For subsequent moves, search with zero-width window at reduced depth based on LMR. If it fails high, re-search with full alpha beta window at unreduced depth. The code I provided earlier illustrates this.
5. Notice this logic (in #4) enables PVS even if, say, a new PV is discovered on the third legal move. The fourth and subsequent moves will be searched with zero-width window at reduced depth in an attempt to prove they fail low compared to the new best move.
6. Considering this, your re-search condition in line 142 is incorrect. It should be if score > alpha {// re-search}. It doesn't matter now, but it will matter once you add LMR. For expected all-nodes (beta = alpha + 1), expected to fail low, you'll want to re-search at unreduced depth. Your condition will not allow that.

I see now you're handling #2 correctly. Nevermind.

[algerbrex]

Edit: Just uploaded the dev version of Blunder in a new branch: https://github.com/algerbrex/blunder/tree/develop

I read your search code. Here are my suggestions:

Hi Erik, thanks for taking the time to look through things.

You should immediately update the TT and return beta at line 155. I realize it may not matter based on lines 173 onwards. However, it's confusing to me. You've found a beta cutoff. So cutoff immediately.

I originally wrote the code this way because I thought I looked cleaner with regards to storing things in the TT only in one place, but if it seems confusing, I'll change that and return immediately.

Your TT should store the score precision so you can distinguish between lower bound (beta cutoff), upper bound (fail low), and exact. You need to know the bound for correct score cutoffs at line
113.

I agree, but I actually put that logic inside of transposition.go:

Code: Select all

if entry.Flag == ExactFlag {
    // If we have an exact entry, we can use the saved score.
    adjustedScore = score
}

if entry.Flag == AlphaFlag && score <= alpha {
    // If we have an alpha entry, and the entry's score is less than our
    // current alpha, then we know that our current alpha is the best score
    // we can get in this node, so we can stop searching and use alpha.
    adjustedScore = alpha
}

if entry.Flag == BetaFlag && score >= beta {
    // If we have a beta entry, and the entry's score is greater than our
    // current beta, then we have a beta-cutoff, since while
    // searching this node previously, we found a value greater than the current
    // beta. so we can stop searching and use beta.
    adjustedScore = beta
}

Your doPVS boolean logic is incorrect. You set it to false initially, then true when score exceeds alpha. That's backwards. DoPvs should be true initially (when legalMoveNumber == 1), false otherwise.

I'm a little confused by what you mean here? From my understanding, after alpha is raised and we've found a PV move, we try to cheaply refute every other move my searching with a null-window. That's the doPVS part. After alpha is raised, doPVS is set to true, so that every move after the one that raised alpha is searched with a null window. Are you suggesting I need to search the first move with a null-window and every move after with a full window?

To get the most out of PVS, you need to add LMR. For first legal move, search full alpha beta window at unreduced depth. For subsequent moves, search with zero-width window at reduced depth based on LMR. If it fails high, re-search with full alpha beta window at unreduced depth. The code I provided earlier illustrates this.

Right, that's what I've heard, but shouldn't PVS be a decent Elo gain even without LMR?

Notice this logic (in #4) enables PVS even if, say, a new PV is discovered on the third legal move. The fourth and subsequent moves will be searched with zero-width window at reduced depth in an attempt to prove they fail low compared to the new best move.

Considering this, your re-search condition in line 142 is incorrect. It should be if score > alpha {// re-search}. It doesn't matter now, but it will matter once you add LMR. For expected all-nodes (beta = alpha + 1), expected to fail low, you'll want to re-search at unreduced depth. Your condition will not allow that.

I need to conceptualize what you're saying, but I think I understand it. I'll look into that when I implement LMR.

[emadsen]

Damn. Nevermind #3. I misread it. Your code is fine as-is.

[emadsen]

Right, that's what I've heard, but shouldn't PVS be a decent Elo gain even without LMR?

Perhaps some, but I wouldn't expect much.

In my opinion, PVS doesn't make any sense without LMR. The objective is to quickly prove no other move beats the best known move, either from TT.bestMove or from move ordering. We do that through the combination of searching 1) a zero-width window at 2) reduced depth. You can experiment how much to reduce based on quiet move number. Perhaps reduce 1 at quiet move 3, reduce 2 at quiet move 7, reduce 3 at quiet move 13? Experiment with it. Of course, quiet moves must be ordered according to the history heuristic.

[emadsen]

The logic in lines 163 to 167 is confusing. Whether to do PVS shouldn't be based on whether you've found a move that beats alpha. It simply should be based on legalMoves == 1 or > 1.

I think it's much simpler to eliminate the doPVS variable and write an if statement based on legalMoves.

Code: Select all

if (legalMoves == 1)
{
    // Search full alpha beta window at unreduced depth.
}
else
{
    // Search zero-window at reduced depth based on LMR.
}