Can principal variation search be worth no Elo?

[R. Tomasi]

Not only did the time to depth and node count improve with the PVS version, but from SPRT testing, the version with PVS is clearly stronger. So it seems that somehow the way I'm ordering killers and/or the TT best move is screwing the move-ordering up. I'll spend some more time this afternoon taking a closer look at the move ordering to see if I can find any bugs.

A quick sanity check is to ensure you don't search the TT best move or killers more than once. Meaning, ensure move generation doesn't include the best move or marks it as played so the search will skip it. Same for killers, though this depends whether you play killers prior to move generation or not.

Maybe not your issue... just a suggestion. This is one of the reasons I advocate the perft call stack should exactly mimic the search call stack- so it catches bugs related to skipped or doubled moves in search. I'll get off my soapbox now.

Thanks for the suggestion. From my testing, I don't think I'm researching previous best moves or previous killers. But move ordering being the issue was further confirmed because when I tried adding back in just killer moves, the strength gained from PVS dropped, and the version with PVS started playing worse again, so move ordering seems to be the culprit.

Sure that you're not storing captures as killers? (Just an idea)

[algerbrex]

Not only did the time to depth and node count improve with the PVS version, but from SPRT testing, the version with PVS is clearly stronger. So it seems that somehow the way I'm ordering killers and/or the TT best move is screwing the move-ordering up. I'll spend some more time this afternoon taking a closer look at the move ordering to see if I can find any bugs.

A quick sanity check is to ensure you don't search the TT best move or killers more than once. Meaning, ensure move generation doesn't include the best move or marks it as played so the search will skip it. Same for killers, though this depends whether you play killers prior to move generation or not.

Maybe not your issue... just a suggestion. This is one of the reasons I advocate the perft call stack should exactly mimic the search call stack- so it catches bugs related to skipped or doubled moves in search. I'll get off my soapbox now.

Thanks for the suggestion. From my testing, I don't think I'm researching previous best moves or previous killers. But move ordering being the issue was further confirmed because when I tried adding back in just killer moves, the strength gained from PVS dropped, and the version with PVS started playing worse again, so move ordering seems to be the culprit.

Sure that you're not storing captures as killers? (Just an idea)

Hmmm, I don't think so. I'd be pretty surprised if I am somehow. I have a function which stores killers when a beta cutoff occurs:

Code: Select all

// Given a "killer move" (a quiet move that caused a beta cut-off), store the
// Move in the slot for the given depth.
func (search *Search) storeKiller(ply uint8, move Move) {
	if search.Pos.Squares[move.ToSq()].Type == NoType {
		if !move.Equal(search.killers[ply][0]) {
			search.killers[ply][1] = search.killers[ply][0]
			search.killers[ply][0] = move
		}
	}
}

That's the only place the killers array is ever updated, and unless I have a movegen bug, I think I'm guarding against any captures (even captures that occur with promotions with the method I'm using).

Even odder is that when I removed the killers, and tried only MVV-LVA and the best TT move instead, PVS still performs worse than the none PVS version, searching more nodes and taking longer. This is incredibly strange to me since the TT should seriously enhancing PVS, not breaking it. But when I remove killers and TT move ordering, magically PVS gains 30-40 Elo!

And from a test I just finished running, TT cuts work fine with PVS though. So the only part of the engine that's not playing nice with PVS right now are the killers and the best hash move...which should be the two parts that make PVS even better

[R. Tomasi]

Not only did the time to depth and node count improve with the PVS version, but from SPRT testing, the version with PVS is clearly stronger. So it seems that somehow the way I'm ordering killers and/or the TT best move is screwing the move-ordering up. I'll spend some more time this afternoon taking a closer look at the move ordering to see if I can find any bugs.

A quick sanity check is to ensure you don't search the TT best move or killers more than once. Meaning, ensure move generation doesn't include the best move or marks it as played so the search will skip it. Same for killers, though this depends whether you play killers prior to move generation or not.

Maybe not your issue... just a suggestion. This is one of the reasons I advocate the perft call stack should exactly mimic the search call stack- so it catches bugs related to skipped or doubled moves in search. I'll get off my soapbox now.

Thanks for the suggestion. From my testing, I don't think I'm researching previous best moves or previous killers. But move ordering being the issue was further confirmed because when I tried adding back in just killer moves, the strength gained from PVS dropped, and the version with PVS started playing worse again, so move ordering seems to be the culprit.

Sure that you're not storing captures as killers? (Just an idea)

Hmmm, I don't think so. I'd be pretty surprised if I am somehow. I have a function which stores killers when a beta cutoff occurs:

Code: Select all

// Given a "killer move" (a quiet move that caused a beta cut-off), store the
// Move in the slot for the given depth.
func (search *Search) storeKiller(ply uint8, move Move) {
	if search.Pos.Squares[move.ToSq()].Type == NoType {
		if !move.Equal(search.killers[ply][0]) {
			search.killers[ply][1] = search.killers[ply][0]
			search.killers[ply][0] = move
		}
	}
}

That's the only place the killers array is ever updated, and unless I have a movegen bug, I think I'm guarding against any captures (even captures that occur with promotions with the method I'm using).

Even odder is that when I removed the killers, and tried only MVV-LVA and the best TT move instead, PVS still performs worse than the none PVS version, searching more nodes and taking longer. This is incredibly strange to me since the TT should seriously enhancing PVS, not breaking it. But when I remove killers and TT move ordering, magically PVS gains 30-40 Elo!

And from a test I just finished running, TT cuts work fine with PVS though. So the only part of the engine that's not playing nice with PVS right now are the killers and the best hash move...which should be the two parts that make PVS even better

I'm just guessing wildly - hope you don't mind. Another idea might be, that when retrieving killers/hashmoves they're not legal for the current position. I had that kind of bug at some point in Pygmalion, because I was using the same legality test for both killers/hashmove and pseudo-legal moves from the movegen. But the movegen does not generate certain illegal moves in the first place (like for example it would not generate moves from a square that has no piece, etc.). Again, it's just wild guessing/speculation. I wish I could be of better help...

[mvanthoor]

Not only did the time to depth and node count improve with the PVS version, but from SPRT testing, the version with PVS is clearly stronger.

So what was the Elo gain?! Darn... clifhangers...

[algerbrex]

Not only did the time to depth and node count improve with the PVS version, but from SPRT testing, the version with PVS is clearly stronger.

So what was the Elo gain?! Darn... clifhangers...

Sorry to leave you wondering with just MVV-LVA and PVS vs MVV-LVA, the Elo gain after 2000+ games was 26 Elo (+/- 13 Elo), and after adding back in just TT cuts into both versions, the Elo gain was 39 Elo (+/- 17 Elo). Which is a big improvement over -13 Elo

[mvanthoor]

Thanks for the suggestion. From my testing, I don't think I'm researching previous best moves or previous killers.

Do you have staged move generation, where you try the TT-move if any, and killers if any, before generating moves? If not, then you can't have the bug Eric mentions. If you try the TT-move or killers first and don't get a beta cutoff, you must exclude them from the move list (or skip them).

But move ordering being the issue was further confirmed because when I tried adding back in just killer moves, the strength gained from PVS dropped, and the version with PVS started playing worse again, so move ordering seems to be the culprit.

Good to know So you can now first use MVV-LVA, and then add PVS for a strength gain, and then add killers which should give you another gain. (In my case, PVS and killers roughly added 55 Elo per feature, and 89 Elo when together, in self-play. In practice, the combination of the two features added 50 Elo in a real CCRL gauntlet.)

Sorry to leave you wondering with just MVV-LVA and PVS vs MVV-LVA, the Elo gain after 2000+ games was 26 Elo (+/- 13 Elo), and after adding back in just TT cuts into both versions, the Elo gain was 39 Elo (+/- 17 Elo). Which is a big improvement over -13 Elo

Hm... feels a bit on the low end... and I already thought something like 55 Elo for PVS and then another 55 for killers was 'just ok'; and I certainly expected more than 89 Elo in self-play when using both features at the same time. Still, the "60% of self-play Elo transfers to a gauntlet" rule held, because 0.6*89 = 53 Elo; and that was what Rustic Alpha 3 gained over 2 in the CCRL-list.

This 60% seems to come up time and time again for Rustic. I've also noticed that there are some engines that are completely impervious to speed gains of Rustic; I optimize something and gain somewhere around 50 Elo (see latest entry: https://rustic-chess.org/progress/sprt_results.html) in self-play, and against some engines Rustic actually does perform 50 Elo better, while others don't seem to budge. I've always found that strange.

[mvanthoor]

Even odder is that when I removed the killers, and tried only MVV-LVA and the best TT move instead, PVS still performs worse than the none PVS version, searching more nodes and taking longer. This is incredibly strange to me since the TT should seriously enhancing PVS, not breaking it. But when I remove killers and TT move ordering, magically PVS gains 30-40 Elo!

And from a test I just finished running, TT cuts work fine with PVS though. So the only part of the engine that's not playing nice with PVS right now are the killers and the best hash move...which should be the two parts that make PVS even better

So as you surmised earlier, you are messing up your move MVV_LVA move ordering when you sort TT moves and killers. (I had a similar problem where a bug in my history function destroyed move ordering. I scrapped history for now, and add it back in later again.)

Do you actually sort the entire move list, or do you set move scores, and then do a pick move by swapping the best move into the array index where alpha-beta wil be at the next move? I use the scoring method, and an MVV_LVA_OFFSET. The tt_move is MVV_LVA_OFFSET + tt_move_value (which is higher than the highest mvv_lva value), then MVV_LVA_OFFSET + mvv_lva_value for the MVV_LVA ordering, and lastly, MVV_LVA_OFFSET - (killer_value * killer_number) to order the killers below the MVV_LVA values.

(And while looking at the code, I possibly see a bug... have to look at it better tomorrow evening.)

[algerbrex]

Thanks for the suggestion. From my testing, I don't think I'm researching previous best moves or previous killers.

Do you have staged move generation, where you try the TT-move if any, and killers if any, before generating moves? If not, then you can't have the bug Eric mentions. If you try the TT-move or killers first and don't get a beta cutoff, you must exclude them from the move list (or skip them).

But move ordering being the issue was further confirmed because when I tried adding back in just killer moves, the strength gained from PVS dropped, and the version with PVS started playing worse again, so move ordering seems to be the culprit.

Good to know So you can now first use MVV-LVA, and then add PVS for a strength gain, and then add killers which should give you another gain. (In my case, PVS and killers roughly added 55 Elo per feature, and 89 Elo when together, in self-play. In practice, the combination of the two features added 50 Elo in a real CCRL gauntlet.)

Sorry to leave you wondering with just MVV-LVA and PVS vs MVV-LVA, the Elo gain after 2000+ games was 26 Elo (+/- 13 Elo), and after adding back in just TT cuts into both versions, the Elo gain was 39 Elo (+/- 17 Elo). Which is a big improvement over -13 Elo

Hm... feels a bit on the low end... and I already thought something like 55 Elo for PVS and then another 55 for killers was 'just ok'; and I certainly expected more than 89 Elo in self-play when using both features at the same time. Still, the "60% of self-play Elo transfers to a gauntlet" rule held, because 0.6*89 = 53 Elo; and that was what Rustic Alpha 3 gained over 2 in the CCRL-list.

This 60% seems to come up time and time again for Rustic. I've also noticed that there are some engines that are completely impervious to speed gains of Rustic; I optimize something and gain somewhere around 50 Elo (see latest entry: https://rustic-chess.org/progress/sprt_results.html) in self-play, and against some engines Rustic actually does perform 50 Elo better, while others don't seem to budge. I've always found that strange.

Thanks

But keep in mind that if I remember correctly, you added PVS after you had TT move ordering, TT Cuts, and MVV-LVA, and gained ~56 Elo. The 39 Elo I gained was just with using MVV-LVA and TT-Cuts. If my TT move ordering was playing nice with PVS, I think 15-20 Elo more would be realistic. Not to mention killers.

While I'm glad I found the culprit of this bug, it's such an odd bug. Both the killers and the TT add significant speed, node reduction, and Elo gains to the engine, but when PVS is added to the mix, it just makes things worse. But take them away, and then all of sudden PVS is a strength gaining feature again? Huh? I honestly have no clue what might be at play here, but I have a couple of theories, so I suppose I'll just go from there.

And I've noticed what you mention with regards to Rustic being stronger against certain engines versus others, although Blunder's improvements are usually optimizations and whatnot. This is now why I always try to pair self-pay with gauntlet testing, which I know you do as well. Seems to be the best way to good an accurate estimate of what the engines Elo will end up being on the CCRL.

[algerbrex]

Not only did the time to depth and node count improve with the PVS version, but from SPRT testing, the version with PVS is clearly stronger. So it seems that somehow the way I'm ordering killers and/or the TT best move is screwing the move-ordering up. I'll spend some more time this afternoon taking a closer look at the move ordering to see if I can find any bugs.

A quick sanity check is to ensure you don't search the TT best move or killers more than once. Meaning, ensure move generation doesn't include the best move or marks it as played so the search will skip it. Same for killers, though this depends whether you play killers prior to move generation or not.

Maybe not your issue... just a suggestion. This is one of the reasons I advocate the perft call stack should exactly mimic the search call stack- so it catches bugs related to skipped or doubled moves in search. I'll get off my soapbox now.

Thanks for the suggestion. From my testing, I don't think I'm researching previous best moves or previous killers. But move ordering being the issue was further confirmed because when I tried adding back in just killer moves, the strength gained from PVS dropped, and the version with PVS started playing worse again, so move ordering seems to be the culprit.

Sure that you're not storing captures as killers? (Just an idea)

Hmmm, I don't think so. I'd be pretty surprised if I am somehow. I have a function which stores killers when a beta cutoff occurs:

Code: Select all

// Given a "killer move" (a quiet move that caused a beta cut-off), store the
// Move in the slot for the given depth.
func (search *Search) storeKiller(ply uint8, move Move) {
	if search.Pos.Squares[move.ToSq()].Type == NoType {
		if !move.Equal(search.killers[ply][0]) {
			search.killers[ply][1] = search.killers[ply][0]
			search.killers[ply][0] = move
		}
	}
}

That's the only place the killers array is ever updated, and unless I have a movegen bug, I think I'm guarding against any captures (even captures that occur with promotions with the method I'm using).

Even odder is that when I removed the killers, and tried only MVV-LVA and the best TT move instead, PVS still performs worse than the none PVS version, searching more nodes and taking longer. This is incredibly strange to me since the TT should seriously enhancing PVS, not breaking it. But when I remove killers and TT move ordering, magically PVS gains 30-40 Elo!

And from a test I just finished running, TT cuts work fine with PVS though. So the only part of the engine that's not playing nice with PVS right now are the killers and the best hash move...which should be the two parts that make PVS even better

I'm just guessing wildly - hope you don't mind. Another idea might be, that when retrieving killers/hashmoves they're not legal for the current position. I had that kind of bug at some point in Pygmalion, because I was using the same legality test for both killers/hashmove and pseudo-legal moves from the movegen. But the movegen does not generate certain illegal moves in the first place (like for example it would not generate moves from a square that has no piece, etc.). Again, it's just wild guessing/speculation. I wish I could be of better help...

No, I appreciate the help. Your guess is as good as mine is right now that could be the issue, but I don't have staged move generation in my engine yet, so what I do is score all of the moves (in the order of TT move, MVV-LVA, killers), and then sort the moves list so that the highest scored moves are iterated over first. But the moves are always all generated first and checked for legagility:

Code: Select all

        // Generate and score the moves for the side to move
	// in the current position.
	moves := genMoves(&search.Pos)
	search.scoreMoves(&moves, ply, ttBestMove)

	legalMoves := 0
	ttFlag := AlphaFlag

	for index := 0; index < int(moves.Count); index++ {
		// Order the moves to get the best moves first.
		orderMoves(index, &moves)
		move := moves.Moves[index]

		// Make the move, and if it was illegal, undo it and skip to the next move.
		if !search.Pos.MakeMove(move) {
			search.Pos.UnmakeMove(move)
			continue
		}

[algerbrex]

Even odder is that when I removed the killers, and tried only MVV-LVA and the best TT move instead, PVS still performs worse than the none PVS version, searching more nodes and taking longer. This is incredibly strange to me since the TT should seriously enhancing PVS, not breaking it. But when I remove killers and TT move ordering, magically PVS gains 30-40 Elo!

And from a test I just finished running, TT cuts work fine with PVS though. So the only part of the engine that's not playing nice with PVS right now are the killers and the best hash move...which should be the two parts that make PVS even better

So as you surmised earlier, you are messing up your move MVV_LVA move ordering when you sort TT moves and killers. (I had a similar problem where a bug in my history function destroyed move ordering. I scrapped history for now, and add it back in later again.)

Do you actually sort the entire move list, or do you set move scores, and then do a pick move by swapping the best move into the array index where alpha-beta wil be at the next move? I use the scoring method, and an MVV_LVA_OFFSET. The tt_move is MVV_LVA_OFFSET + tt_move_value (which is higher than the highest mvv_lva value), then MVV_LVA_OFFSET + mvv_lva_value for the MVV_LVA ordering, and lastly, MVV_LVA_OFFSET - (killer_value * killer_number) to order the killers below the MVV_LVA values.

(And while looking at the code, I possibly see a bug... have to look at it better tomorrow evening.)

The latter method since it's more efficient. And currently, I score my moves by making sure the TT move always has the highest score, then the MVV-LVA values, and then finally the killer scores are always below the MVV-LVA values. I think the exact values are something like 60, 56-11, and 10.