Can principal variation search be worth no Elo?

[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.

By all other signs, it seems to be working well. I'm getting a pretty nice reduction in nodes searched and time to depth. For example for the following position:

[fen]rn1qkb1r/pp2pppp/5n2/3p1b2/3P4/2N1P3/PP3PPP/R1BQKBNR w KQkq - 0 1[/fen]

Blunder gives the following output without PVS:

Code: Select all

go wtime 300000 btime 300000

info depth 1 seldepth 4 score cp 29 time 5 nodes 108
info depth 2 seldepth 5 score cp 9 time 7 nodes 665
info depth 3 seldepth 7 score cp 22 time 8 nodes 4646
info depth 4 seldepth 9 score cp 13 time 17 nodes 17120
info depth 5 seldepth 10 score cp 34 time 33 nodes 52474
info depth 6 seldepth 12 score cp 31 time 142 nodes 236423
info depth 7 seldepth 12 score cp 35 time 354 nodes 769418
info depth 8 seldepth 14 score cp 36 time 1371 nodes 3158661
info depth 9 seldepth 16 score cp 37 time 3398 nodes 7419403
Bestmove: g1e2
Time: 7501ms

And the following output with PVS:

Code: Select all

go wtime 300000 btime 300000

info depth 1 seldepth 4 score cp 29 time 1 nodes 110
info depth 2 seldepth 4 score cp 9 time 8 nodes 730
info depth 3 seldepth 7 score cp 22 time 8 nodes 4579
info depth 4 seldepth 9 score cp 13 time 15 nodes 16896
info depth 5 seldepth 9 score cp 34 time 30 nodes 44778
info depth 6 seldepth 11 score cp 31 time 113 nodes 195962
info depth 7 seldepth 13 score cp 35 time 208 nodes 469929
info depth 8 seldepth 14 score cp 36 time 675 nodes 1718405
info depth 9 seldepth 17 score cp 37 time 2205 nodes 5507529
Bestmove: g1e2
Time: 7501ms

So I seem to be getting an improvement, but it's not showing up as an Elo gain. Currently, from testing (tc=inf/3+0.08) both versions are testing equal to each other.

I would post a snippet of my PVS search, but I'm pretty confident that's correct and another part of my program is causing a bug, so my full current search file can be found here:

So far, I've tried stripping the search of everything but basic move ordering (MVV-LVA), but I still didn't see much of an Elo gain. I've also heard that the transposition table can cause issues and so I've disabled it but also didn't get an improvement in play.

It seems I either have a nasty bug hiding somewhere in my program, or I'm unaware of certain cases where PVS isn't a win.

[R. Tomasi]

I just quickly skimmed over your code, so maybe I have just overlooked it. But to me it seems you do the ZW search even if you do not have found a move yet. In PVS you should only do it once you already have a PV move. Apologies if you actually do what I said and I just mis-read your code.

[algerbrex]

I just quickly skimmed over your code, so maybe I have just overlooked it. But to me it seems you do the ZW search even if you do not have found a move yet. In PVS you should only do it once you already have a PV move. Apologies if you actually do what I said and I just mis-read your code.

Hi Roland, thanks for the feedback. In the code I posted, I'm only setting my PVS flag raiseAlpha to true when alpha is raised, which means I've found a move. Or am I off? No problem if you mis-read, I hope you didn't and I've just been making a very silly mistake

[j.t.]

Why not use a null window whenever alpha is bigger than -inf? At least that's what I found works best. Especially all-nodes you want to search as quickly as possible. The way you're doing it, all nodes are completely searched with a full window, if I see that correctly.

[algerbrex]

Why not use a null window whenever alpha is bigger than -inf? At least that's what I found works best. Especially all-nodes you want to search as quickly as possible. The way you're doing it, all nodes are completely searched with a full window, if I see that correctly.

Hmm, I believe I’m doing that, no? At the root alpha is infinity, and after the first time alpha is raised and I have a PV move, then I always try to search with a null window.

If you’re asking why past the root I don’t always search with a null-window, I don’t think I’ve tried that but I can test it. I assumed that it wouldn’t work great since you would have to do a lot of researching as the first few moves in any position become PV moves.

[j.t.]

If you’re asking why past the root I don’t always search with a null-window, I don’t think I’ve tried that, but I can test it. I assumed that it wouldn’t work great since you would have to do a lot of researching as the first few moves in any position become PV moves.

I think that's what I mean. The assumption is that by using iterative deepening, you will have close-to-the-best pv already searched first. So the likelyhood of researches is not that high.

[R. Tomasi]

I just quickly skimmed over your code, so maybe I have just overlooked it. But to me it seems you do the ZW search even if you do not have found a move yet. In PVS you should only do it once you already have a PV move. Apologies if you actually do what I said and I just mis-read your code.

Hi Roland, thanks for the feedback. In the code I posted, I'm only setting my PVS flag raiseAlpha to true when alpha is raised, which means I've found a move. Or am I off? No problem if you mis-read, I hope you didn't and I've just been making a very silly mistake

My Bad! I have overlooked that. What worked best for me, is to actually have two search methods. One for the PVS and one for ZWS.That way I don't have to check (and branch on) any flags, and I do not propagate any moves upwards in the search tree from ZWS.

[algerbrex]

I just quickly skimmed over your code, so maybe I have just overlooked it. But to me it seems you do the ZW search even if you do not have found a move yet. In PVS you should only do it once you already have a PV move. Apologies if you actually do what I said and I just mis-read your code.

Hi Roland, thanks for the feedback. In the code I posted, I'm only setting my PVS flag raiseAlpha to true when alpha is raised, which means I've found a move. Or am I off? No problem if you mis-read, I hope you didn't and I've just been making a very silly mistake

My Bad! I have overlooked that. What worked best for me, is to actually have two search methods. One for the PVS and one for ZWS.That way I don't have to check (and branch on) any flags, and I do not propagate any moves upwards in the search tree from ZWS.

Hmm, thanks. I'll try that maybe and see how it goes.

[algerbrex]

If you’re asking why past the root I don’t always search with a null-window, I don’t think I’ve tried that, but I can test it. I assumed that it wouldn’t work great since you would have to do a lot of researching as the first few moves in any position become PV moves.

I think that's what I mean. The assumption is that by using iterative deepening, you will have close-to-the-best pv already searched first. So the likelyhood of researches is not that high.

That makes sense, the more I'm thinking about what you said. Unfortunately, right now, reality seems to be trumping theory and I'm getting horrendous time to depth results and the node count explodes. So I need to think a little bit about what I'm doing differently in Blunder, since as you said, most of the time I should be getting close to the PV the first couple of tries.

[j.t.]

That makes sense, the more I'm thinking about what you said. Unfortunately, right now, reality seems to be trumping theory and I'm getting horrendous time to depth results and the node count explodes. So I need to think a little bit about what I'm doing differently in Blunder, since as you said, most of the time I should be getting close to the PV the first couple of tries.

That's just how it is with chess programming. Lots of ideas that sound really good, don't work, and stuff that works, makes you scratch your head over why it actually does.

I think when I first added PVS it didn't make a huge difference. But then I wasn't really testing each change properly (maybe sometimes I played fifty or a hundred games, but nothing serious). So it could be that initially PVS was not a measurable improvement, but then I slowly developed my engine to be better while depending on the PVS, so now I cannot remove PVS without losing Elo. I don't know why that is so, but unfortunately I neither have a plan nor the time to thoroughly test if PVS is truly necessary.

Search explosions when the PV changes is actually an issue for Nalwald (my engine). As long as the PV doesn't change, the search is really fast, but as soon as the current PV is refuted, the search can take 10 times or more. This doesn't necessarily prevent an engine to be quite good, but it is something worth thinking about before adding (aggressive or less aggressive) PVS.