PVS weaker than plain alpha-beta

[rtarga]

Hi! I am a new chess programmer and I'm trying to implement PVS in my engine. I implemented something similar to the following pseudo-code:

Code: Select all

if moves_searched == 0 {
    score = -search(-beta, -alpha)
else {
    score = -search(-(alpha+1), -alpha)
	
    if score > alpha && score < beta {
        score = -search(-beta, -alpha)
    }
}
...
moves_searched += 1

However, I get approximately -30 elo when testing versions of my engine with plain AB vs PVS:

Code: Select all

Results of PVS vs AB (10, NULL, 16MB, hyatt2500.epd):
Elo: -28.12 +/- 3.94, nElo: -34.52 +/- 4.82
LOS: 0.00 %, DrawRatio: 40.68 %, PairsRatio: 0.70
Games: 20000, Wins: 6895, Losses: 8510, Draws: 4595, Points: 9192.5 (45.96 %)
Ptnml(0-2): [1547, 1936, 4068, 1483, 966], WL/DD Ratio: 5.92

My move ordering scheme is as follows:

Root:

• PV move

• Other moves sorted by nodes count from last iteration

Non-root:

• PV/TT move

• Good captures (sorted by MVV/LVA then tested with SEE >= 0)

• 2 killer moves

• Non-capture moves sorted by history heuristic

• Bad captures (SEE < 0)

I tested the first 20 positions in https://www.chessprogramming.org/Silent_but_Deadly with fixed 12-depth search to compare statistics between AB and PVS versions of my engine and found the following:

• Total average nodes and time reduced by PVS was approximately 33%

• Cut-off on 1st move rate: 96.5% (Nodes that failed-high on first move divided by total nodes that failed high)

• PVS re-search rate: 0.0045%

The numbers seem good to me, but in self-play, the plain AB version is significantly stronger than the PVS version. Any ideas?

Thanks!

[Steve Maughan]

Do you update alpha after the initial search?

— Steve

[rtarga]

Do you update alpha after the initial search?

— Steve

Yes. I update alpha when score > alpha, which, in the first move of the root position, is always true since alpha is initially -INF.

[pb00067]

It looks to me that your condition for research is wrong:

Code: Select all

if score > alpha && score < beta {  research

According to chessprogramming it must be:

Code: Select all

if ( score > alpha && beta - alpha > 1 )

Source: https://www.chessprogramming.org/Princi ... seudo_Code

[pb00067]

..and your research rate is way to low, it would imply almost perfect move ordering.
In stockfish we have a research rate about 2-3%

[Joerg Oster]

..and your research rate is way to low, it would imply almost perfect move ordering.
In stockfish we have a research rate about 2-3%

Still too low, imho.
I measure well above 10% research rate.

[rtarga]

Thanks for the responses. I was away from my computer for a couple of days. I will look into it.

[expositor]

@rtarga I wrote a bit about the theory of principal variation search here: https://expositor.dev/pvs
It may not be particularly helpful, but on the off chance it is, I thought I’d share.

[rtarga]

Thank you for all the help. Unfortunately, I could not get PVS to work and I'm getting burned out with it so I decided to shelve the idea for now and come back to it later. My engine is probably currently around ~2200 elo (CCRL) as I'm testing against engines at this rating, so there are a lot of other things I can work on.

What's funny is I inserted a sloppily written LMR code (without PVS) just for fun that goes something like:

Code: Select all

if moves_searched > 4 and depth >= 3 {
    score = -search(-beta, -alpha, depth - 2);
} else {
    score = -search(-beta, -alpha, depth - 1);
}

And it gained me around +30 elo. Of course I'll enhance it, but I just find it funny that a piece of code I wrote for less than a minute and was sure was not going to work, actually worked. While the code I'm trying to make work doesn't.