Can principal variation search be worth no Elo?

[algerbrex]

Well, from some quick preliminary testing, PVS + Killers still seems to be stronger, not sure by how much yet. But PVS + Killers + TT move is still a loss, so there's something still buggy about how I'm dealing with TT moves.

I just pass the TT-move to the scoring function and when I find find the TT move in the move list, I score it with a score higher than the highest MVV_LVA score. That's basically all.

As far as I can tell, I'm doing the same thing. So, I'm going to look back at how I'm storing the TT move because obviously, something's wrong.

[algerbrex]

Another update, and the last one for now.

I spent the weekend, among other things, experimenting around with PVS, and the results still baffle me: PVS is a decent win with ONLY MVV-LVA move ordering, but if any other move ordering is added, PVS immediately becomes a loss. I'm still none the wiser as to why this is.

At this point, I've been trying to get PVS to play nice with Blunder for about two months now, and I have to admit at this point I'm getting pretty tired of trying to get it for work. Obviously, it's pretty frustrating for me to see that PVS seems to be a win in every other engine I've experimented or interacted with, but I'm starting to ask myself at what point am I just going to cut my losses if PVS refuses to cooperate, and move forward?

But even more importantly, I'm just simply out of ideas. I've read pretty much every linked thread and/or paper on PVS in the CPW, I've scoured the internet myself, I've tried every suggestion from here (thanks for those!), and at this point, I just don't have anything else to try. And I've tried everything I can think of myself to pinpoint this phantom "bug" (rewriting the search routine from scratch, removing qsearch, simplifying the evaluation, debugging the TT, messing with the move ordering, double-checking the move generator to make sure it's really bug-free, etc.).

So while I'll be happy to continue trying new ideas as I come to implementing them (for example, PVS + LMR might be an overall win?), or new ideas for debugging PVS , I think I'm done fooling with PVS directly right now. I'm tired of it, and I feel like my time could be better spent continuing to improve the engine in other ways.

While I'm disappointed for now since it feels like I'm missing out on Elo, and I don't have a feature that seems like it should be a basic part of every engine, I feel like I've done my due diligence finding this PVS bug, and there's no point in banging my head against a wall if I've exhausted all my resources. Hopefully sometime in the (near) future I'll get PVS working

[emadsen]

Another update, and the last one for now.

I spent the weekend, among other things, experimenting around with PVS, and the results still baffle me: PVS is a decent win with ONLY MVV-LVA move ordering, but if any other move ordering is added, PVS immediately becomes a loss. I'm still none the wiser as to why this is.

At this point, I've been trying to get PVS to play nice with Blunder for about two months now, and I have to admit at this point I'm getting pretty tired of trying to get it for work.

I can empathize with your frustration. Chess engine programming can be that way at times... Have you adjusted your code so it searches the first legal move with a full window and all subsequent moves with a zero window? If I remember correctly, at one point you were waiting for a move to score > alpha before you searched with a zero window.

[algerbrex]

Another update, and the last one for now.

I spent the weekend, among other things, experimenting around with PVS, and the results still baffle me: PVS is a decent win with ONLY MVV-LVA move ordering, but if any other move ordering is added, PVS immediately becomes a loss. I'm still none the wiser as to why this is.

At this point, I've been trying to get PVS to play nice with Blunder for about two months now, and I have to admit at this point I'm getting pretty tired of trying to get it for work.

I can empathize with your frustration. Chess engine programming can be that way at times... Have you adjusted your code so it searches the first legal move with a full window and all subsequent moves with a zero window? If I remember correctly, at one point you were waiting for a move to score > alpha before you searched with a zero window.

Thanks Erik. And yes, after that initial discussion with you, I switched to only doing a full-window search on the first move, and a null-window search on every subsequent move. And I haven't changed that while I've been debugging and testing PVS recently. So I don't think that should be causing issues.

It really just seems that from observing games Blunder plays, the benefits from using PVS are offset by the times where PVS fails due to expensive researches. Why this offset is happening though is unfortunately still a mystery

[Chan Rasjid]

Another update, and the last one for now.

I spent the weekend, among other things, experimenting around with PVS, and the results still baffle me: PVS is a decent win with ONLY MVV-LVA move ordering, but if any other move ordering is added, PVS immediately becomes a loss. I'm still none the wiser as to why this is.

At this point, I've been trying to get PVS to play nice with Blunder for about two months now, and I have to admit at this point I'm getting pretty tired of trying to get it for work. Obviously, it's pretty frustrating for me to see that PVS seems to be a win in every other engine I've experimented or interacted with, but I'm starting to ask myself at what point am I just going to cut my losses if PVS refuses to cooperate, and move forward?

But even more importantly, I'm just simply out of ideas. I've read pretty much every linked thread and/or paper on PVS in the CPW, I've scoured the internet myself, I've tried every suggestion from here (thanks for those!), and at this point, I just don't have anything else to try. And I've tried everything I can think of myself to pinpoint this phantom "bug" (rewriting the search routine from scratch, removing qsearch, simplifying the evaluation, debugging the TT, messing with the move ordering, double-checking the move generator to make sure it's really bug-free, etc.).

So while I'll be happy to continue trying new ideas as I come to implementing them (for example, PVS + LMR might be an overall win?), or new ideas for debugging PVS , I think I'm done fooling with PVS directly right now. I'm tired of it, and I feel like my time could be better spent continuing to improve the engine in other ways.

While I'm disappointed for now since it feels like I'm missing out on Elo, and I don't have a feature that seems like it should be a basic part of every engine, I feel like I've done my due diligence finding this PVS bug, and there's no point in banging my head against a wall if I've exhausted all my resources. Hopefully sometime in the (near) future I'll get PVS working

To implement PVS search should be as easy as ABC; that's if you don't try to meddle with it by trying to add tricks to get a "better" PVS - there is only PVS, never a better PVS. It is for the same reason that you don't try to get a better alphabeta algorithm - there's none!

1) The first thing you have to be very clear is what is a pv-node. After the first iteration in iterative deepening, you usually have a PV from the previous iterastion and you play the full pv-line from root. You should keep track of this "follow-pv", i.e. the first move is a pv-move(in previous iteration) and the node's (with all its generated moves) other moves are all moves from a pv-node, but not pv-moves.
2) The pv-move - the first move when still followPV - is done with a full window; this window is the exact full width from root (depends on what width you set your aspiration window). All subsequent moves of this pv-node are searched with a null/zero window (alpha, alpha + 1) :

Code: Select all

x = -searchpvs(...depth - 1, -alpha - 1, -alpha, ply + 1, ....)   

3) If (2) returns with an improvement in alpha, x > alpha and x < beta, do a pvs research with a window
(x - 1, infi).

A further note. I believe every top chess engine use PVS and they also have 2 search functions, searchpv and search_normal. Within searchpv() it will call searchpv() if followPV = true, else it will call seach_normal() with a null window. DONT add any other "tricks".

Some here claims PVS is useful only when we implement LMR, etc. It's not correct. The only reason for PVS is that it has been tested to be better than plain alphabeta(), with or w/o LMR. It may (very unlikely) be bad if you completely mess up your move ordering (bad bugs). The so called MVV/LVA for capturesi is good enough plus some ordering for ep/castle/checks, killers, promote, etc.

A further note. Always search with null/zero window when doing LMR and nullmove with the necessary research when needed.

I don't know and never have run any test to determine elo improvements when changes are made with my codes. How can you be certain that the elo gain/loss of your test may be statistically reliable?

[mvanthoor]

I don't know and never have run any test to determine elo improvements when changes are made with my codes. How can you be certain that the elo gain/loss of your test may be statistically reliable?

By running the test as an SPRT-test. SPRT is specifically created (a very long time ago) to be able to run tests on an unknown sample size, and stop as soon as a statistically significant result has been achieved.

[algerbrex]

Update.

Since I've gotten LMR working recently in Blunder, I decided to revisit PVS, since several people here mentioned that LMR + PVS was where PVS actually helped their engines.

So I'm currently running a test of 4000 games, and 3/4 of the way through, it seems that LMR + PVS is better than just LMR, giving about 13 Elo, though the error margins are still pretty high:

Code: Select all

Score of Blunder 7.3.0 vs Blunder 7.2.0: 1230 - 1108 - 712  [0.520] 3050
...      Blunder 7.3.0 playing White: 654 - 524 - 347  [0.543] 1525
...      Blunder 7.3.0 playing Black: 576 - 584 - 365  [0.497] 1525
...      White vs Black: 1238 - 1100 - 712  [0.523] 3050
Elo difference: 13.9 +/- 10.8, LOS: 99.4 %, DrawRatio: 23.3 %

(7.3.0 is the one with LMR + PVS, and 7.2.0 with just LMR, if it wasn't clear)

And here is the code combining LMR + PVS:

Code: Select all

score := int16(0)
if legalMoves == 1 {
    score = -search.negamax(depth-1, ply+1, -beta, -alpha, &childPVLine, true)
} else {

    historyScore := search.history[search.Pos.SideToMove][move.FromSq()][move.ToSq()]
    research := false

    if legalMoves > 4 && depth > 3 && historyScore < 50 && !inCheck {
        newDepth := depth - 2
        if legalMoves > 6 {
            newDepth--
        }
        score = -search.negamax(newDepth, ply+1, -alpha-1, -alpha, &childPVLine, true)
        research = score > alpha
    } else {
        research = true
    }

    if research {
        score = -search.negamax(depth-1, ply+1, -alpha-1, -alpha, &childPVLine, true)
        if score > alpha && score < beta {
            score = -search.negamax(depth-1, ply+1, -beta, -alpha, &childPVLine, true)
        }
    }
}

So for whatever reason, with my engine and others, it seems that PVS is only a win when combined LMR. Not sure why that is exactly, I'll have to think about it more.

Regardless, I am glad that I was at least able to get PVS working in this way, since it annoyed me not having it

[mvanthoor]

Update.
....
Regardless, I am glad that I was at least able to get PVS working in this way, since it annoyed me not having it

I still think it's strange you're only getting +13 from PVS _IF_ you have LMR also, where my engine gets 50-60 Elo from PVS alone. I still wonder what the cause of that difference can be.

[algerbrex]

Update.
....
Regardless, I am glad that I was at least able to get PVS working in this way, since it annoyed me not having it

I still think it's strange you're only getting +13 from PVS _IF_ you have LMR also, where my engine gets 50-60 Elo from PVS alone. I still wonder what the cause of that difference can be.

I do to Marcel, but I can't imagine what might be the issue.

I know my move generator is working correctly, it's probably the most well-tested part of my engine. So the bug that's causing PVS to be suboptimal is part of the search and/or evaluation, so a few select files.

I've rewritten search.go, and evaluation.go as far as I could tell when going through it is working fine. transposition.go also seems to be working well right now, and I got almost 200 Elo from it in testing, so I highly doubt the transposition table is the issue. So my problem is that I'm not sure where to look right now. But since I've been away from the problem for a while though, I do have some ideas I'm going to try, so I'll see how that goes and post another update if anything fruitful comes up.

All else failing, I'll try one more time to rewrite the search from scratch. And I think this time, to ensure I don't keep unknowingly adding the same bug into my engine, I'm going to temporarily copy someone else's code line for line as a sanity check, which should make PVS work in Blunder. Then I'll go back through each part of my code rewriting it and see what part introduces the bug again.

[mvanthoor]

I do to Marcel, but I can't imagine what might be the issue.
...
All else failing, I'll try one more time to rewrite the search from scratch.

If you can wait another few hours, I may have something, but to be sure, the current test run must be finished. I won't say anything more at this point as not to raise false expectations.