Can principal variation search be worth no Elo?

[j.t.]

...

If I understand correctly, when you find that a search returns a value bigger than alpha, you then first do a full-depth-but-null-window search, right?

Code: Select all

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)
	}
}

I found that first doing a search with reduced depth, but full window works better. Just something to try out. I think you would need to change the structure of your PVS and LMR stuff a bit to do that.

[algerbrex]

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.

Sure. I’m in no hurry.

[algerbrex]

If I understand correctly, when you find that a search returns a value bigger than alpha, you then first do a full-depth-but-null-window search, right?

Right yeah, that's correct.

From my research, the approach I've always taken when combing LMR & PVS is to search the first move with a full window and full depth, then for every other move search with a null-window and reduced depth (the LMR part), and then if alpha is raised research again with a null-window and a full-depth (the PVS part), and then finally if I discover that the current move is part of the PV (score > alpha && score < beta), then I search with a full-window and full depth.

I found that first doing a search with reduced depth, but full window works better. Just something to try out. I think you would need to change the structure of your PVS and LMR stuff a bit to do that.

Hmm, interesting, thanks. I'll try that out too and see how that works out. Intuitively that might work better for Blunder since null-window searches have been pretty suboptimal (per this thread). So it might make more sense to prove a move fails-low cheaply by using reduced-depth first.

[algerbrex]

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.

Another update.

While your test has been running, I went ahead and rewrote Blunder's search and copied the structure of Rustic's code (in alpha_beta.rs, qsearch.rs, and sorting.rs), and I started running a test of 2000 games with an 8+0.8s time control between a version with PVS and without PVS. And although its only been 500 games, the results are looking pretty positive:

Code: Select all

Score of Blunder_pvs vs Blunder_no_pvs: 244 - 147 - 109  [0.597] 500
...      Blunder_pvs playing White: 128 - 60 - 62  [0.636] 250
...      Blunder_pvs  playing Black: 116 - 87 - 47  [0.558] 250
...      White vs Black: 215 - 176 - 109  [0.539] 500
Elo difference: 68.3 +/- 27.3, LOS: 100.0 %, DrawRatio: 21.8 %

In addition to the above results, from testing individual positions, PVS quite significantly reduces the time-to-depth and node count, searching a full-ply deeper in some positions.

The version with PVS is clearly better. Which seems to indicate that I was making a silly mistake somewhere in Blunder's original code. The plan right now is to let the test finish to confirm the above results and then slowly change the code piece by piece back to Blunder's original code, testing after each change until PVS starts failing again, at which point I'll know where I introduced the bug.

[algerbrex]

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.

Another update.

While your test has been running, I went ahead and rewrote Blunder's search and copied the structure of Rustic's code (in alpha_beta.rs, qsearch.rs, and sorting.rs), and I started running a test of 2000 games with an 8+0.8s time control between a version with PVS and without PVS. And although its only been 500 games, the results are looking pretty positive:

Code: Select all

Score of Blunder_pvs vs Blunder_no_pvs: 244 - 147 - 109  [0.597] 500
...      Blunder_pvs playing White: 128 - 60 - 62  [0.636] 250
...      Blunder_pvs  playing Black: 116 - 87 - 47  [0.558] 250
...      White vs Black: 215 - 176 - 109  [0.539] 500
Elo difference: 68.3 +/- 27.3, LOS: 100.0 %, DrawRatio: 21.8 %

In addition to the above results, from testing individual positions, PVS quite significantly reduces the time-to-depth and node count, searching a full-ply deeper in some positions.

The version with PVS is clearly better. Which seems to indicate that I was making a silly mistake somewhere in Blunder's original code. The plan right now is to let the test finish to confirm the above results and then slowly change the code piece by piece back to Blunder's original code, testing after each change until PVS starts failing again, at which point I'll know where I introduced the bug.

After 1000 games:

Code: Select all

Score of Blunder 1.1.0 vs Blunder 1.0.0: 505 - 290 - 205  [0.608] 1000
...      Blunder 1.1.0 playing White: 264 - 128 - 108  [0.636] 500
...      Blunder 1.1.0 playing Black: 241 - 162 - 97  [0.579] 500
...      White vs Black: 426 - 369 - 205  [0.528] 1000
Elo difference: 75.9 +/- 19.5, LOS: 100.0 %, DrawRatio: 20.5 %

[algerbrex]

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.

Another update.

While your test has been running, I went ahead and rewrote Blunder's search and copied the structure of Rustic's code (in alpha_beta.rs, qsearch.rs, and sorting.rs), and I started running a test of 2000 games with an 8+0.8s time control between a version with PVS and without PVS. And although its only been 500 games, the results are looking pretty positive:

Code: Select all

Score of Blunder_pvs vs Blunder_no_pvs: 244 - 147 - 109  [0.597] 500
...      Blunder_pvs playing White: 128 - 60 - 62  [0.636] 250
...      Blunder_pvs  playing Black: 116 - 87 - 47  [0.558] 250
...      White vs Black: 215 - 176 - 109  [0.539] 500
Elo difference: 68.3 +/- 27.3, LOS: 100.0 %, DrawRatio: 21.8 %

In addition to the above results, from testing individual positions, PVS quite significantly reduces the time-to-depth and node count, searching a full-ply deeper in some positions.

The version with PVS is clearly better. Which seems to indicate that I was making a silly mistake somewhere in Blunder's original code. The plan right now is to let the test finish to confirm the above results and then slowly change the code piece by piece back to Blunder's original code, testing after each change until PVS starts failing again, at which point I'll know where I introduced the bug.

After 1000 games:

Code: Select all

Score of Blunder 1.1.0 vs Blunder 1.0.0: 505 - 290 - 205  [0.608] 1000
...      Blunder 1.1.0 playing White: 264 - 128 - 108  [0.636] 500
...      Blunder 1.1.0 playing Black: 241 - 162 - 97  [0.579] 500
...      White vs Black: 426 - 369 - 205  [0.528] 1000
Elo difference: 75.9 +/- 19.5, LOS: 100.0 %, DrawRatio: 20.5 %

After the test finished:

Code: Select all

Score of Blunder 1.1.0 vs Blunder 1.0.0: 962 - 641 - 397  [0.580] 2000
...      Blunder 1.1.0 playing White: 500 - 293 - 207  [0.604] 1000
...      Blunder 1.1.0 playing Black: 462 - 348 - 190  [0.557] 1000
...      White vs Black: 848 - 755 - 397  [0.523] 2000
Elo difference: 56.2 +/- 13.8, LOS: 100.0 %, DrawRatio: 19.9 %
Finished match

(blunder 1.1.0 = one with PVS, changed the names in the first post to make it clearer)

[mvanthoor]

After 1000 games:

Code: Select all

Score of Blunder 1.1.0 vs Blunder 1.0.0: 505 - 290 - 205  [0.608] 1000
...      Blunder 1.1.0 playing White: 264 - 128 - 108  [0.636] 500
...      Blunder 1.1.0 playing Black: 241 - 162 - 97  [0.579] 500
...      White vs Black: 426 - 369 - 205  [0.528] 1000
Elo difference: 75.9 +/- 19.5, LOS: 100.0 %, DrawRatio: 20.5 %

Blunder 1.1.0 vs 1.1.0? Did you start re-versioning or something?

I assume you copied Rustic's search code, and then testing a version of this with and without PVS, which gave a difference of +75 for the version with PVS? That's impressive... even more than Rustic itself gained. You must have had a subtle bug somewhere which we both have been missing (but I must say that I didn't read through your move ordering and qsearch parts, so the bug might have been there).

The thing I was testing was the draw condition. Yours is at the beginning of the search. Mine skips the search in the move loop, just scoring the move as a draw. You go one ply deeper and then return at the beginning. I think the only difference is if and when a drawing move will be stored in the TT; in my case, the move is taken into account as a normal move, in your case, the function exits, so I think my drawn move may end up in the TT as a beta cutoff more often, which might give a few speedups and thus Elo.

So I created a version of Rustic which copied your draw condition, and tested it against mine:

Code: Select all

Score of Rustic Alpha 3.25.100 vs Rustic Alpha 3.24.100: 806 - 817 - 377 [0.497]
...      Rustic Alpha 3.25.100 playing White: 457 - 363 - 180  [0.547] 1000
...      Rustic Alpha 3.25.100 playing Black: 349 - 454 - 197  [0.448] 1000
...      White vs Black: 911 - 712 - 377  [0.550] 2000
Elo difference: -1.9 +/- 13.7, LOS: 39.2 %, DrawRatio: 18.9 %
2000 of 2000 games finished.

So no such thing. It doesn't matter if you skip the search in the move loop as I do, or exit the function in the beginning as you do.

I'd still be interested to know where the bug in your search function was. If you managed to fix it and PVS gains 75 Elo, you should see blunder gain 40-50 Elo in an average gauntlet.

[mvanthoor]

After the test finished:

Code: Select all

Score of Blunder 1.1.0 vs Blunder 1.0.0: 962 - 641 - 397  [0.580] 2000
...      Blunder 1.1.0 playing White: 500 - 293 - 207  [0.604] 1000
...      Blunder 1.1.0 playing Black: 462 - 348 - 190  [0.557] 1000
...      White vs Black: 848 - 755 - 397  [0.523] 2000
Elo difference: 56.2 +/- 13.8, LOS: 100.0 %, DrawRatio: 19.9 %
Finished match

(blunder 1.1.0 = one with PVS, changed the names in the first post to make it clearer)

Blunder: 56.2 Elo gain. 13.8 margin.
Rustic: 54.2 Elo gain, 16.6 margin.

I think we can call that similar enough to state that PVS earns about 55 Elo in self-play... at least in an engine with a TT and PST's. (I assume you left the TT enabled, but removed null move, LMR, etc...)

[algerbrex]

After 1000 games:

Code: Select all

Score of Blunder 1.1.0 vs Blunder 1.0.0: 505 - 290 - 205  [0.608] 1000
...      Blunder 1.1.0 playing White: 264 - 128 - 108  [0.636] 500
...      Blunder 1.1.0 playing Black: 241 - 162 - 97  [0.579] 500
...      White vs Black: 426 - 369 - 205  [0.528] 1000
Elo difference: 75.9 +/- 19.5, LOS: 100.0 %, DrawRatio: 20.5 %

Blunder 1.1.0 vs 1.1.0? Did you start re-versioning or something?

I assume you copied Rustic's search code, and then testing a version of this with and without PVS, which gave a difference of +75 for the version with PVS? That's impressive... even more than Rustic itself gained. You must have had a subtle bug somewhere which we both have been missing (but I must say that I didn't read through your move ordering and qsearch parts, so the bug might have been there).

The thing I was testing was the draw condition. Yours is at the beginning of the search. Mine skips the search in the move loop, just scoring the move as a draw. You go one ply deeper and then return at the beginning. I think the only difference is if and when a drawing move will be stored in the TT; in my case, the move is taken into account as a normal move, in your case, the function exits, so I think my drawn move may end up in the TT as a beta cutoff more often, which might give a few speedups and thus Elo.

So I created a version of Rustic which copied your draw condition, and tested it against mine:

Code: Select all

Score of Rustic Alpha 3.25.100 vs Rustic Alpha 3.24.100: 806 - 817 - 377 [0.497]
...      Rustic Alpha 3.25.100 playing White: 457 - 363 - 180  [0.547] 1000
...      Rustic Alpha 3.25.100 playing Black: 349 - 454 - 197  [0.448] 1000
...      White vs Black: 911 - 712 - 377  [0.550] 2000
Elo difference: -1.9 +/- 13.7, LOS: 39.2 %, DrawRatio: 18.9 %
2000 of 2000 games finished.

So no such thing. It doesn't matter if you skip the search in the move loop as I do, or exit the function in the beginning as you do.

I'd still be interested to know where the bug in your search function was. If you managed to fix it and PVS gains 75 Elo, you should see blunder gain 40-50 Elo in an average gauntlet.

Nope, no new versioning. I usually keep a lot of binaries of Blunder in the same directory for testing. And while I’m testing I’ll usually change around the version number. And since this Bludner’s search was a copy of yours, I wanted to make sure I remembered that. Although in this case it didn’t really matter since these two binaries were kept separate. Force of habit I guess.

But anyway, that sounded like a good hypothesis, I wonder the same myself, although a little differently. Unfortunate it wasn’t the cause though.

On the plus side, I know I’m not crazy and PVS works and gives around 50-60 Elo, so at this point all I (theoretically) have to do is slowly change your code back to mine and see at what point I introduce a bug. I’ll probably start tonight and finish sometime this weekend since I’ll be testing every change.

[algerbrex]

After the test finished:

Code: Select all

Score of Blunder 1.1.0 vs Blunder 1.0.0: 962 - 641 - 397  [0.580] 2000
...      Blunder 1.1.0 playing White: 500 - 293 - 207  [0.604] 1000
...      Blunder 1.1.0 playing Black: 462 - 348 - 190  [0.557] 1000
...      White vs Black: 848 - 755 - 397  [0.523] 2000
Elo difference: 56.2 +/- 13.8, LOS: 100.0 %, DrawRatio: 19.9 %
Finished match

(blunder 1.1.0 = one with PVS, changed the names in the first post to make it clearer)

Blunder: 56.2 Elo gain. 13.8 margin.
Rustic: 54.2 Elo gain, 16.6 margin.

I think we can call that similar enough to state that PVS earns about 55 Elo in self-play... at least in an engine with a TT and PST's. (I assume you left the TT enabled, but removed null move, LMR, etc...)

I agree

And yep that’s right. I basically copied your code, and since it had no pruning I removed that too…which may have contributed to the problem, time will tell after I start the debugging. I’m mostly just glad I have something I can work with now