PVS/NegaScout: Actual benefits.

[konsolas]

Currently, my engine uses a pretty generic alpha-beta search algorithm.

Looking at open-source engines, all seem to use Principal Variation search.

What absolute benefits would I get by using PVS over normal alpha-beta? More importantly, is PVS a "safe" improvement that will not change the inherent behaviour of the engine?

[kbhearn]

PVS vs normal alpha-beta is a matter of speed via reducing the number of nodes searched. If you have reasonably good move ordering PVS will save you time by getting you additional cuts in the lines it's scouting and proving aren't an improvement. If you have abhorrent move ordering PVS will take longer as you'll wind up having to research frequently wasting the effort of the scout search.

It is safe in a plain alpha-beta framework. If you add in pruning based on alpha/beta values of some variety it may change the tree you're searching. And you may be more or less lucky with TT grafts in PVS than plain alpha-beta. But essentially, apart from these effects you should get the same score value at the same depth using PVS as alpha-beta.

[Dann Corbit]

Usually, pvs is done with zero window searches for the non-pv nodes.
As long as you have very good move ordering, this will make your program run faster.
On the other hand, if you have bad move ordering, it will actually make it run slower due to re-searching with wider windows.
So make sure that your move ordering is good first or you won't see much benefit.

[konsolas]

My current move ordering produces beta cutoffs on the first move 87% of the time. After crudely implementing PVS, my engine took slightly longer to search deeper, but (after ~20 test games), I'm seeing quite a significant strength increase. Is the reduction in search depth normal?

[Dann Corbit]

My current move ordering produces beta cutoffs on the first move 87% of the time.

Try adding IID. It is a simple way to increase your quality of move ordering. It can be tricky to know when to call IID and when to skip it, so look at how some other engines have implemented it. (e.g. which sort of nodes need it, which ones don't).
87% is a little sub-par.

After crudely implementing PVS, my engine took slightly longer to search deeper, but (after ~20 test games), I'm seeing quite a significant strength increase.

You can't tell anything from 20 games. I guess that your new search fixed a bug in your search if you see a large strength improvement.

Taking longer and searching less deeply is probably a function of only 87% cutoffs.

Is the reduction in search depth normal?

It is not at all unusual if your move ordering is somewhat sub-par. In fact, it is expected in that case.

[ZirconiumX]

My current move ordering produces beta cutoffs on the first move 87% of the time.

I would be careful of using beta cutoff percentage as your only metric of ordering performance.

As an example, here is a search with my move ordering based on the relative history heuristic:

Code: Select all

1 89 0 49 1 0 0  d2d4
2 10 0 458 3 0 0         c2c4 c7c5
3 64 0 1126 5 0 0        g1f3 c7c5 c2c4
4 10 1 4312 6 0 0        g1f3 g8f6 d2d4 d7d5
5 30 1 11964 9 0 0       b1c3 g8f6 d2d4 d7d5 g1f3
6 38 6 45151 12 0 0      e2e4 d7d5 e4d5 d8d5 c2c4 d5e4
7 41 25 173103 16 0 0    e2e4 d7d6 g1f3 g8f6 b1c3 c7c5 b2b3
8 14 84 565103 17 0 0    c2c4 d7d5 c4d5 g8f6 d2d4 f6d5 g1f3 b7b5
9 26 125 827943 19 827943 0      g1f3 d7d5 d2d4 g8f6 c1f4 b8c6 b1d2 c8f5 g2g4
10 21 517 3612998 22 722599 0    e2e4 d7d5 e4d5 d8d5 g1e2 g8f6 b1c3 d5e6 d2d4 b7b5
# 1st move cuts: 262701 total cuts: 307513
move e2e4

262,701 / 307,513 = 85.4% cutoffs on the first move.

Here is a search with my move ordering based on PSTs:

Code: Select all

1 89 0 47 1 0 0  d2d4
2 10 0 362 3 0 0         c2c4 c7c5
3 64 0 746 4 0 0         g1f3 c7c5 c2c4
4 10 1 3782 6 0 0        g1f3 d7d5 d2d4 g8f6
5 37 1 9381 9 0 0        g1f3 d7d5 d2d4 g8f6 g2g4
6 38 9 55150 12 0 0      e2e4 d7d5 e4d5 d8d5 c2c4 d5e4
7 41 26 168846 16 0 0    e2e4 c7c5 g1f3 e7e6 c2c4 g8f6 b1c3
8 17 85 566720 19 0 0    c2c4 g8f6 b1c3 e7e5 g1f3 e5e4 f3g5 f6g4
9 25 123 835761 19 835761 0      g1f3 d7d5 d2d4 g8f6 b1c3 b8c6 c1g5 c6b4 g5f6
10 22 390 2654430 21 884810 0    e2e4 d7d5 e4d5 d8d5 g1e2 d5e6 b2b4 g8f6 d2d4 b7b5
# 1st move cuts: 191598 total cuts: 223874
move e2e4

191,598 / 223874 = 85.6% cutoffs on the first move.

Based only on cutoff counts, RHH ordering is only 0.2% less efficient than PST ordering. But look at the node counts - the RHH searches 36% more nodes than ordering by PST values, and the PST ordering has an effective branching factor of ~3.2, compared to the RHH EBF of ~4.4.

[konsolas]

I suppose move ordering would be a good thing to work on.

Can I ask what would be a "on-par" beta cutoff rate? It's difficult to use time-to-depth as a measure because of interference from pruning methods, etc.

I'm going to try out PST move ordering.

[Dann Corbit]

This is a really good thread on move ordering and cut-offs:
http://www.open-chess.org/viewtopic.php?f=5&t=2173

[Henk]

No still too mysterious. Everybody knows how alpha beta or PVS works but when they talk about move ordering they start talking abra cadabra.

[Dann Corbit]

No still too mysterious. Everybody knows how alpha beta or PVS works but when they talk about move ordering they start talking abra cadabra.

I don't think it is mysterious.
You need a good evaluation. Otherwise, search will not be accurate.
You need a correct hash table implementation. Any bug in hash will mess up the search.
You need some simple ordering heuristics like IID, which is easy to understand.