Can principal variation search be worth no Elo?

[algerbrex]

Maybe it's a combination of factors? In the above position, Rustic's current development version searches 60 million nodes at depth 9. (Including PVS and transposition table.) Your engine searches only 7.4 mln (without PVS) and 5.5 mln (with PVS) nodes. What other enhancements do you have at this point?

Well currently, I'm doing null-move pruning, reverse-futility pruning, and I'm also using history heuristics to improve my move ordering, as of version 6.0.0. So I am doing some pruning. This is in addition to having a TT, killer moves, and MVV-LVA moves to order already.

It is expensive for PVS, having to re-search; the transposition table mitigates this expense.

Right, that's what's confusing to me. By all other metrics I should be getting an improvement in strength, but from a recent test I ran last night, I'm losing 12 Elo (6.1.0 is the dev version):

Code: Select all

Score of Blunder 6.1.0 vs Blunder 6.0.0: 1552 - 1709 - 1050  [0.482] 4311
...      Blunder 6.1.0 playing White: 778 - 846 - 531  [0.484] 2155
...      Blunder 6.1.0 playing Black: 774 - 863 - 519  [0.479] 2156
...      White vs Black: 1641 - 1620 - 1050  [0.502] 4311
Elo difference: -12.7 +/- 9.0, LOS: 0.3 %, DrawRatio: 24.4 %
SPRT: llr -2.96 (-100.4%), lbound -2.94, ubound 2.94 - H0 was accepted
Finished match

Could it be that the TT is not working correctly, making your PVS re-search more expensive than it needs to be? Seeing that your time to depth drops from just over 3 seconds down to 2.2 for depth 9, it's unlikely; but with a time to depth speedup of almost 30%, the engine -should- have been measurably stronger.

Maybe so Marcel, that's something I'll definitely look into because I'm a little stumped about where to start debugging this. I'm fairly confident my TT isn't buggy, because if I remember correctly, I got about ~160-180 Elo from it in self-play. But I'll look back over it and how it's being used. My other working theory at the moment is that my PVS is running out of time on certain searches, and returns a bad move every now and then, as mentioned here: http://www.talkchess.com/forum3/viewtop ... =7&t=69252

[Chan Rasjid]

I doubt there is any way to do PVS with greater or lesser aggressiveness. I think what have been suggested here covered all aspects of PVS search.

[edit] Someone mentioned doing a null window for reduced depth LMR; this may be considered "common sense" as we expect the move to fail low; this is what I do in my engine.

My point was not that you should do null window searches for LMR. My point was that you can vary the conditions for when you use null window searches. Using null windows can cause issues, as the result may not be as accurate as if you are using a full window. So in some cases it might make sense to search a move with a full window, even if we think that it is more likely that it will fail low.

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.

[algerbrex]

If your analysis shows PVS getting the same bestmove in a shorter time of search, it cannot be that there is no elo gain; the logic means your engine can only be stronger - other bugs aside.

Well, I agree, it seems that it should by all other accounts. But it's just not, for whatever reason the chess gods have decided. See my response to Marcel about the most recent test of PVS that I ran.

I've run a couple of tests with tc=inf/3+0.08, and both of them have shown losses of 12-15 Elo. So I'm pretty stumped. For whatever reason, it's just not showing up a as win for me.

[algerbrex]

Could it be that the TT is not working correctly, making your PVS re-search more expensive than it needs to be?

I included my TT implementation in the code linked in my original post as well as the search file, so if anything looks weird it would be there. AFAIK, the only difference I see between my TT and the ones in other engines is that theirs' use buckets, whereas mine doesn't. But I doubt buckets alone would explain PVS being a loss.

[mvanthoor]

Maybe so Marcel, that's something I'll definitely look into because I'm a little stumped about where to start debugging this. I'm fairly confident my TT isn't buggy, because if I remember correctly, I got about ~160-180 Elo from it in self-play. But I'll look back over it and how it's being used. My other working theory at the moment is that my PVS is running out of time on certain searches, and returns a bad move every now and then, as mentioned here: http://www.talkchess.com/forum3/viewtop ... =7&t=69252

If you have used the TT in perft and the numbers match up AND you get 160-180 Elo improvement in self-play, the result is as expected. The TT is (probably) correct.

Have you also tried adding PVS to a version of the search that _only_ has a TT, or only has a TT and killers?

In my engine:
- Killer moves gave 56 Elo in self-play
- PVS gave 54 Elo in self-play
- The combination gave 89 Elo in self-play

( https://rustic-chess.org/progress/sprt_results.html )

A combination of functions does not always give the Elo difference of function1+function2.

For example:
(QSearch + PST) measurement > QSearch measurement + PST measurement (proven by MinimalChess)
(PVS + Killers) measurement < PVS measurement + Killers measurement (my engine)

So to be sure that no other function is in the way, I'd remove everything from the search and use only the TT + PVS. If you have no bugs in the TT and PVS, the engine should be stronger. (I can't remember if you tried this already.)

[mvanthoor]

...

I see a difference in the re-search code, between yours and mine:

Yours:

Code: Select all

		if alphaRaised {
			score = -search.negamax(depth-1, 0, -alpha-1, -alpha, true)
			if score > alpha {
				score = -search.negamax(depth-1, 0, -beta, -alpha, true)
			}
		} else {
			score = -search.negamax(depth-1, 0, -beta, -alpha, true)
		}

Mine:

Code: Select all

                if do_pvs {
                    eval_score =
                        -Search::alpha_beta(depth - 1, -alpha - 1, -alpha, &mut node_pv, refs);

                    // Check if we failed the PVS.
                    if (eval_score > alpha) && (eval_score < beta) {
                        eval_score =
                            -Search::alpha_beta(depth - 1, -beta, -alpha, &mut node_pv, refs);
                    }
                } else {
                    eval_score = -Search::alpha_beta(depth - 1, -beta, -alpha, &mut node_pv, refs);
                }

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.

The point of the PVS search is to very quickly prove that no other move in the move list is a Principal Variation move compared to the last one you found. If that search call returns a move with eval > alpha, eval < beta, then there IS a move that is a PV move (and thus better). The proof failed, and you have to research with the normal -beta, -alpha window. Testing just for alpha isn't enough. If eval > alpha, it could very well also be eval > beta. That would make that move NOT a PV move. Because you test only for score > alpha, you research anyway. So, I think you are researching much more often than you should, basically negating the PVS and probably even slowing your engine down. That would explain the elo loss.

Try:

Code: Select all

if score > alpha  && score < beta {
	...
}

And then retest again.

[j.t.]

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.

[j.t.]

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)

[mvanthoor]

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.

[algerbrex]

Maybe so Marcel, that's something I'll definitely look into because I'm a little stumped about where to start debugging this. I'm fairly confident my TT isn't buggy, because if I remember correctly, I got about ~160-180 Elo from it in self-play. But I'll look back over it and how it's being used. My other working theory at the moment is that my PVS is running out of time on certain searches, and returns a bad move every now and then, as mentioned here: http://www.talkchess.com/forum3/viewtop ... =7&t=69252

If you have used the TT in perft and the numbers match up AND you get 160-180 Elo improvement in self-play, the result is as expected. The TT is (probably) correct.

Have you also tried adding PVS to a version of the search that _only_ has a TT, or only has a TT and killers?

In my engine:
- Killer moves gave 56 Elo in self-play
- PVS gave 54 Elo in self-play
- The combination gave 89 Elo in self-play

( https://rustic-chess.org/progress/sprt_results.html )

A combination of functions does not always give the Elo difference of function1+function2.

For example:
(QSearch + PST) measurement > QSearch measurement + PST measurement (proven by MinimalChess)
(PVS + Killers) measurement < PVS measurement + Killers measurement (my engine)

So to be sure that no other function is in the way, I'd remove everything from the search and use only the TT + PVS. If you have no bugs in the TT and PVS, the engine should be stronger. (I can't remember if you tried this already.)

I haven't tried just TT and killers so I'll do that. I remember I tried without TT and killers and MVV-LVA before and it was still a loss, so I'll try that combination instead.