Can principal variation search be worth no Elo?

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
algerbrex
Posts: 608
Joined: Sun May 30, 2021 5:03 am
Location: United States
Full name: Christian Dean

Re: Can principal variation search be worth no Elo?

Post by algerbrex »

mvanthoor wrote: Sat Sep 25, 2021 8:25 pm Nah. Don't bother. It's a very common way to implement MVV-LVA. I've read tutorials that do it in a similar way, MaksimKorzh mentioned it in his video's, BlueFever uses a similar version in VICE; I just adapted it to make the MVV-LVA values smaller, and took care that capturing the king or landing on an empty square would be 0 adjustment; that way, you don't have to check for the king or the empty square, which makes the MVV-LVA routine a tiny bit faster.
Cool, thanks. And right, that's what I noticed in how you implemented it, which also worked quite well for me.
mvanthoor wrote: Sat Sep 25, 2021 8:25 pm Your transposition table looks a lot like mine, minus the generics (so I can use it for perft, and pawn hash data as well). It's inevitable that some code looks like existing code, especially if authors communicate with one another; and there are only so many ways to implement something in a correct and readable way.

"Don't port Rustic to Go" was more of a tongue-in-cheek comment than anything else. I wouldn't mind if someone actually did that.
Yeah I know :lol:

And I agree. I remember I finished writing the transposition table, and then checked around to make sure I wasn't doing something dumb, and there are only so many ways sometimes to write good code. Particularly I made sure the way I adjusted mate scores made sense, and when I saw the missing minus sign in your code, I decided your implementation was probably just a little different from mine, and so I didn't chalk it up to a bug. Although I'm glad it's been fixed now.
mvanthoor wrote: Sat Sep 25, 2021 8:25 pm PS: I actually installed Go for the first time in my life. Maybe it'll come in handy somewhere in the future. I actually like Blunder and MinimalChess, and some of the other newer engines as well, in which I had a bit of influence in the development such as Loki and Zahak. The newer engines are often easier to compile and use than older engines of the same rating; many of the weaker engines in the CCRL list are old and no longer in development.
Thanks. I noticed that myself when developing Blunder 1.0.0. Your engine and MinimalChess were the two I found the most reliable, especially at the lower Elo ratings. Many of the other engines I couldn't even get running, or they'd crash halfway thru testing and cause many headaches. So I'm also quite excited to see a new generation of engines.
User avatar
mvanthoor
Posts: 1784
Joined: Wed Jul 03, 2019 4:42 pm
Location: Netherlands
Full name: Marcel Vanthoor

Re: Can principal variation search be worth no Elo?

Post by mvanthoor »

algerbrex wrote: Sun Sep 26, 2021 3:06 pm Thanks. I noticed that myself when developing Blunder 1.0.0. Your engine and MinimalChess were the two I found the most reliable, especially at the lower Elo ratings. Many of the other engines I couldn't even get running, or they'd crash halfway thru testing and cause many headaches. So I'm also quite excited to see a new generation of engines.
Good to hear that Rustic has been useful :) The problem is that many of the older engines have low ratings due to bugs, not due to a lack of features. (And indeed, many of the sub-2000 engines are just unstable.) I have thought about disabling MVV-LVA for an Alpha 0.5 version, and maybe even removing PST's and QSearch and such for Alpha 0.4, 0.3, etc... to create engines in the range below 1600. In the end I decided against it, because I deem MVV-LVA, QSearch and PST's to be essential elements to a chess engine. And, to be honest, I didn't want to bother the CCRL testers with it.

I'm on the verge of building an 8-core ITX computer specifically for Rustic, and CCRL testing. If I can get permission from the other testers, I might just create those Alpha 0.x versions and test them myself, to put at least one more reliable engine in the lower part of the list.
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL
User avatar
algerbrex
Posts: 608
Joined: Sun May 30, 2021 5:03 am
Location: United States
Full name: Christian Dean

Re: Can principal variation search be worth no Elo?

Post by algerbrex »

mvanthoor wrote: Sun Sep 26, 2021 3:41 pm
algerbrex wrote: Sun Sep 26, 2021 3:06 pm Thanks. I noticed that myself when developing Blunder 1.0.0. Your engine and MinimalChess were the two I found the most reliable, especially at the lower Elo ratings. Many of the other engines I couldn't even get running, or they'd crash halfway thru testing and cause many headaches. So I'm also quite excited to see a new generation of engines.
Good to hear that Rustic has been useful :) The problem is that many of the older engines have low ratings due to bugs, not due to a lack of features. (And indeed, many of the sub-2000 engines are just unstable.)
That makes sense, and as you've pointed out before, I noticed many engines had impressive lists of features, only to find from testing they play quite weak.

This is actually what motivated me to completely scrap my original version of Blunder. I had many features that should've made Blunder quite strong, but because I wasn't privy to the idea of testing changes to actually measure their benefit, the original Blunder never broke 1700. And I had no desire to be yet another engine on the CCRL that looked impressive, but consistently crashed and was riddled with bugs.
mvanthoor wrote: Sun Sep 26, 2021 3:41 pm I have thought about disabling MVV-LVA for an Alpha 0.5 version, and maybe even removing PST's and QSearch and such for Alpha 0.4, 0.3, etc... to create engines in the range below 1600. In the end I decided against it, because I deem MVV-LVA, QSearch and PST's to be essential elements to a chess engine. And, to be honest, I didn't want to bother the CCRL testers with it.

I'm on the verge of building an 8-core ITX computer specifically for Rustic, and CCRL testing. If I can get permission from the other testers, I might just create those Alpha 0.x versions and test them myself, to put at least one more reliable engine in the lower part of the list.
I think such a project would be very helpful to new engine developers :) I know I would've loved to have a solid group of sub-2000 engines for testing when I started out. So I definitely think exploring something like that is worthwhile.
User avatar
mvanthoor
Posts: 1784
Joined: Wed Jul 03, 2019 4:42 pm
Location: Netherlands
Full name: Marcel Vanthoor

Re: Can principal variation search be worth no Elo?

Post by mvanthoor »

algerbrex wrote: Sun Sep 26, 2021 7:27 pm I think such a project would be very helpful to new engine developers :) I know I would've loved to have a solid group of sub-2000 engines for testing when I started out. So I definitely think exploring something like that is worthwhile.
Blunder could join in with versions 0.9, 0.8, 0.7... MinimalChess already goes down to something like 1100 or so, because the very first version had no features apart from alpha/beta IIRC.
Author of Rustic, an engine written in Rust.
Releases | Code | Docs | Progress | CCRL
User avatar
algerbrex
Posts: 608
Joined: Sun May 30, 2021 5:03 am
Location: United States
Full name: Christian Dean

Re: Can principal variation search be worth no Elo?

Post by algerbrex »

mvanthoor wrote: Sun Sep 26, 2021 8:07 pm
algerbrex wrote: Sun Sep 26, 2021 7:27 pm I think such a project would be very helpful to new engine developers :) I know I would've loved to have a solid group of sub-2000 engines for testing when I started out. So I definitely think exploring something like that is worthwhile.
Blunder could join in with versions 0.9, 0.8, 0.7... MinimalChess already goes down to something like 1100 or so, because the very first version had no features apart from alpha/beta IIRC.
I wouldn't mind do something like that at all. If I remember correctly, Blunder 1.0.0 was already around ~1400 Elo, so it shouldn't be to hard to hit some values in the 1500-1000 Elo range.
User avatar
algerbrex
Posts: 608
Joined: Sun May 30, 2021 5:03 am
Location: United States
Full name: Christian Dean

Re: Can principal variation search be worth no Elo?

Post by algerbrex »

As another update to document by debugging progress, since PVS is still causing issues, I've stopped doing SPRT testing and instead have just been watching the engine play games with and without PVS.

While watching a game yesterday evening, I found the following position was searched differently if PVS was enabled:

[fen]r3r1k1/ppp2ppp/2nb2b1/3q4/3P4/1P3N2/PB1Q1PPP/2KR1B1R w - - 1 13[/fen]

With PVS (tc=inf/60s+0.00):

Code: Select all

info depth 1 score cp 17 time 2 nodes 328 pv f1c4
info depth 2 score cp 6 time 12 nodes 1082 pv f1c4 d5h5 b3c4
info depth 3 score cp 14 time 11 nodes 3693 pv f1c4 d5a5 d2a5
info depth 4 score cp -17 time 12 nodes 18258 pv f1c4 d5e4 c4d3 e4d3
info depth 5 score cp -15 time 91 nodes 131269 pv h2h3 d5f5 f1d3 f5d3 d2d3
info depth 6 score cp -32 time 142 nodes 290557 pv f1d3 c6b4 d3g6 h7g6 a2a3 d5c6 c1b1
info depth 7 score cp -21 time 567 nodes 1359034 pv h2h3 c6b4 b2c3 b4c2 f3e5 d6a3 c3b2 a3b2 c1b2
Bestmove: h2h3
Time: 1500ms
Without PVS (tc=inf/60s+0.00):

Code: Select all

info depth 1 score cp 17 time 2 nodes 328 pv f1c4
info depth 2 score cp 6 time 19 nodes 1082 pv f1c4 d5h5 b3c4
info depth 3 score cp 14 time 36 nodes 3697 pv f1c4 d5a5 d2a5
info depth 4 score cp -17 time 31 nodes 18348 pv f1c4 d5e4 c4d3 e4d3
info depth 5 score cp -15 time 109 nodes 135742 pv h2h3 d5f5 f1d3 f5d3 d2d3
info depth 6 score cp -32 time 133 nodes 307257 pv f1d3 c6b4 d3g6 h7g6 a2a3 d5c6 c1b1
info depth 7 score cp -30 time 742 nodes 1534345 pv f1c4 d5e4 c4d3 e4g4 d3g6 h7g6 d2g5
Bestmove: f1c4
Time: 1500ms
So not only does the version with PVS search MORE nodes, but it also finds a different PV line. As far as I understand, this shouldn't be happening with PVS, the PVs should be staying the same, just with fewer nodes searched. So this was somewhere to start debugging more.

From what I know, this is likely caused by search instabilities and when I disabled TT-cutoffs, the PVs now matched, but the efficiency was still worse:

Code: Select all

info depth 1 score cp 17 time 2 nodes 328 pv f1c4
info depth 2 score cp 6 time 19 nodes 1082 pv f1c4 d5h5 b3c4
info depth 3 score cp 14 time 36 nodes 3697 pv f1c4 d5a5 d2a5
info depth 4 score cp -17 time 31 nodes 18348 pv f1c4 d5e4 c4d3 e4d3
info depth 5 score cp -15 time 109 nodes 135742 pv h2h3 d5f5 f1d3 f5d3 d2d3
info depth 6 score cp -32 time 133 nodes 307257 pv f1d3 c6b4 d3g6 h7g6 a2a3 d5c6 c1b1
info depth 7 score cp -30 time 742 nodes 1534345 pv f1c4 d5e4 c4d3 e4g4 d3g6 h7g6 d2g5
Bestmove: f1c4
Time: 1500ms
I'm not entirely sure why this is, but from brainstorming, it seems that somewhere down the line a search instability occurred which changes the root PV move and causes PVS to start doing expensive re-searches. I'll have to think more about how to debug this...
User avatar
algerbrex
Posts: 608
Joined: Sun May 30, 2021 5:03 am
Location: United States
Full name: Christian Dean

Re: Can principal variation search be worth no Elo?

Post by algerbrex »

algerbrex wrote: Mon Sep 27, 2021 7:25 pm As another update to document by debugging progress, since PVS is still causing issues, I've stopped doing SPRT testing and instead have just been watching the engine play games with and without PVS.

While watching a game yesterday evening, I found the following position was searched differently if PVS was enabled:

[fen]r3r1k1/ppp2ppp/2nb2b1/3q4/3P4/1P3N2/PB1Q1PPP/2KR1B1R w - - 1 13[/fen]

With PVS (tc=inf/60s+0.00):

Code: Select all

info depth 1 score cp 17 time 2 nodes 328 pv f1c4
info depth 2 score cp 6 time 12 nodes 1082 pv f1c4 d5h5 b3c4
info depth 3 score cp 14 time 11 nodes 3693 pv f1c4 d5a5 d2a5
info depth 4 score cp -17 time 12 nodes 18258 pv f1c4 d5e4 c4d3 e4d3
info depth 5 score cp -15 time 91 nodes 131269 pv h2h3 d5f5 f1d3 f5d3 d2d3
info depth 6 score cp -32 time 142 nodes 290557 pv f1d3 c6b4 d3g6 h7g6 a2a3 d5c6 c1b1
info depth 7 score cp -21 time 567 nodes 1359034 pv h2h3 c6b4 b2c3 b4c2 f3e5 d6a3 c3b2 a3b2 c1b2
Bestmove: h2h3
Time: 1500ms
Without PVS (tc=inf/60s+0.00):

Code: Select all

info depth 1 score cp 17 time 2 nodes 328 pv f1c4
info depth 2 score cp 6 time 19 nodes 1082 pv f1c4 d5h5 b3c4
info depth 3 score cp 14 time 36 nodes 3697 pv f1c4 d5a5 d2a5
info depth 4 score cp -17 time 31 nodes 18348 pv f1c4 d5e4 c4d3 e4d3
info depth 5 score cp -15 time 109 nodes 135742 pv h2h3 d5f5 f1d3 f5d3 d2d3
info depth 6 score cp -32 time 133 nodes 307257 pv f1d3 c6b4 d3g6 h7g6 a2a3 d5c6 c1b1
info depth 7 score cp -30 time 742 nodes 1534345 pv f1c4 d5e4 c4d3 e4g4 d3g6 h7g6 d2g5
Bestmove: f1c4
Time: 1500ms
So not only does the version with PVS search MORE nodes, but it also finds a different PV line. As far as I understand, this shouldn't be happening with PVS, the PVs should be staying the same, just with fewer nodes searched. So this was somewhere to start debugging more.

From what I know, this is likely caused by search instabilities and when I disabled TT-cutoffs, the PVs now matched, but the efficiency was still worse:

Code: Select all

info depth 1 score cp 17 time 2 nodes 328 pv f1c4
info depth 2 score cp 6 time 19 nodes 1082 pv f1c4 d5h5 b3c4
info depth 3 score cp 14 time 36 nodes 3697 pv f1c4 d5a5 d2a5
info depth 4 score cp -17 time 31 nodes 18348 pv f1c4 d5e4 c4d3 e4d3
info depth 5 score cp -15 time 109 nodes 135742 pv h2h3 d5f5 f1d3 f5d3 d2d3
info depth 6 score cp -32 time 133 nodes 307257 pv f1d3 c6b4 d3g6 h7g6 a2a3 d5c6 c1b1
info depth 7 score cp -30 time 742 nodes 1534345 pv f1c4 d5e4 c4d3 e4g4 d3g6 h7g6 d2g5
Bestmove: f1c4
Time: 1500ms
I'm not entirely sure why this is, but from brainstorming, it seems that somewhere down the line a search instability occurred which changes the root PV move and causes PVS to start doing expensive re-searches. I'll have to think more about how to debug this...
The without PVS example should've been:

Code: Select all

info depth 1 score cp 17 time 14 nodes 227 pv f1c4
info depth 2 score cp 6 time 74 nodes 1726 pv f1c4 d5h5 b3c4
info depth 3 score cp 14 time 70 nodes 4071 pv f1c4 d5a5 d2a5
info depth 4 score cp -17 time 19 nodes 23658 pv f1c4 d5e4 c4d3 e4d3
info depth 5 score cp -15 time 49 nodes 62797 pv h2h3 d5f5 f1d3 f5d3 d2d3
info depth 6 score cp -32 time 162 nodes 281386 pv f1d3 c6b4 d3g6 h7g6 a2a3 d5c6 c1b1
info depth 7 score cp -30 time 303 nodes 655650 pv f1c4 d5e4 c4d3 e4g4 d3g6 h7g6 d2g5
Bestmove: f1c4
Time: 1507ms
User avatar
algerbrex
Posts: 608
Joined: Sun May 30, 2021 5:03 am
Location: United States
Full name: Christian Dean

Re: Can principal variation search be worth no Elo?

Post by algerbrex »

Another update.

After doing some thinking, I've decided to spend some time debugging my move ordering, since my TT seems bug-free, and my PVS implementation seems bug-free, I suspect that the move-ordering is causing issues in Blunder. So I removed all move ordering except MVV-LVA and started testing a version of Blunder with and without PVS.

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.
User avatar
emadsen
Posts: 441
Joined: Thu Apr 26, 2012 1:51 am
Location: Oak Park, IL, USA
Full name: Erik Madsen

Re: Can principal variation search be worth no Elo?

Post by emadsen »

algerbrex wrote: Wed Sep 29, 2021 7:04 pm 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.
Erik Madsen | My C# chess engine: https://www.madchess.net
User avatar
algerbrex
Posts: 608
Joined: Sun May 30, 2021 5:03 am
Location: United States
Full name: Christian Dean

Re: Can principal variation search be worth no Elo?

Post by algerbrex »

emadsen wrote: Wed Sep 29, 2021 8:03 pm
algerbrex wrote: Wed Sep 29, 2021 7:04 pm 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.