Question on standard implementation of PVS+NWS

[rob]

Any chance of iterative deepening in the ZWS?

Rob

[kbhearn]

Iterative deepening at the root will mostly automatically give you iterative deepening at the entire interior tree, including the scout searches. If you enter a node that is missing a HT entry because it got overwritten you can of course do internal-iterative-deepening to generate one. I'm not sure how much of a gain that is inside a scout search vs in a PV search.

[rob]

Add a transposition table, aka a hash table. Otherwise the re-searches of internal deepening, pvs, null move, lmr and other enhancements over plain alpha-beta will indeed kill performance.

Perhaps I can explain the source of my question. Basically, I have many different search algorithms implemented and I can benchmark them against each other over a complete game. Indeed, I benchmark them over many dozens (sometimes hundreds) of games.

I put all this data into a spreadsheet and look at the overall performance of each algorithm. I basically have two "winning" algorithms:

1. Alpha/Beta + iterative deepening + reuse PV of previous iteration as first move to try of this iteration + killer moves + move sorting

2. Bruce Moreland's PVS + iterative deepening + reuse PV of previous iteration as first move to try of this iteration + killer moves + move sorting.

I can just pick a game at random, e.g., here's the data for game 400:

best_move_nabcpv_id_ms_killer: 138.1 seconds
best_move_npvscpv_id_ms_killer: 124.4 seconds (Bruce Moreland's PVS)
best_move_npvs_nws_ms_killer: 1026.1 seconds (Canonical PVS+NWS + move sorting + killer moves)
best_move_npvs_nws_cpv_id_ms_killer: 971.2 seconds (Canonical PVS + NWS + iterative deepening + move sorting + killer moves)
… various others …

What I notice is that Bruce Moreland's PVS (BM-PVS) is consistent in being approximately 10% faster than AB when both are using only iterative deepening, re-use PV of previous iteration, move sorting, and killer moves.

In other words, consistently (over many hundreds of games), BM-PVS does NOT need transposition tables to outperform alpha beta (assuming AB is also not using TT, and both are using the above move ordering methods).

So move ordering is probably rather important.

Now I look at the canonical PVS+NWS, and it's not immediately clear to me how to add the move ordering techniques described above (especially iterative deepening with re-use of the previous iteration's PV) into the NWS. It's crucial to add these to the NWS because that's where the majority of board evaluations come from.

Finally, on average, over many hundreds of games, the canonical PVS+NWS is roughly (1026.1 / 124.4 =) 8.24 times slower than Bruce Moreland's PVS. That further suggests that proper move ordering is critical for PVS+NWS, since BM-PVS is in fact more careful about researching possible instability errors (if I'm understanding correctly) than canonical PVS+NWS. Said another way, canonical PVS+NWS should occasionally be faster than BM-PVS. The fact that it's consistently over 8 times slower is a rather stunning observation.

Rob

[Henk]

I don't understand the research step.

Code: Select all

v = -PVS(ni, d-1, -beta, -v) 

I always thought they said it had to be

Code: Select all

v = -PVS(ni, d-1, -beta, -alpha) 

Because of search instability.

[Henk]

But perhaps it works with fail hard only ?

[Or better not use PVS at all if one is afraid of search instability. Also forget about aspiration search and MTDF. Only alpha beta can be trusted]

[hgm]

Now I look at the canonical PVS+NWS, and it's not immediately clear to me how to add the move ordering techniques described above (especially iterative deepening with re-use of the previous iteration's PV) into the NWS. It's crucial to add these to the NWS because that's where the majority of board evaluations come from.

It seems to me that splitting the search into a PVS and an NWS is totally artificial, and that the NWS(beta) is just a PVS(alpha=beta-epsilon, beta). So I don't understand why the move ordering techniqes should be any different.

But I must admit that it is not entirely clear to me what your move ordering entails. Normally one would use something like (1) hash-move/IID move (2) MVV/LVA captures (3) killers (4) history non-captures. The PV of the previous root iteration could be viewed as a very small hash table in this context, and in nodes where you don't have one, you can do a reduced-depth pilot search (IID) to obtain a cut move.

This should not be any different in the NWS. You won't have a hash move there, (with your root-PV-only TT), so you can start IID to see if it gives you a cut move, and then use that one as a first attempt for the full-depth search.

So the moral lesson is that even a search that failed high will return a variation, but that this variation is only a single move long, as the fail-low daughter node will not have found any move. But you only need one move; by the time you are 2 ply deeper into the tree the latter will have fanned out over all moves of the following all-node, and you will now need to find cut-moves for each particular case, again through IID.

If you don't do that, your move ordering in the NWS will suck, because you will frequently embark on searching moves in a cut node that stand no chance at all of becoming a cut move, (just because they happen to come early in your static move ordering), and would have been cheaply rejected by a reduced-depth IID iteration. And if your move ordering sucks, you will get a bloated tree. That is just as true in NWS as in alpha-beta.

I always thought they said it had to be

Code: Select all

v = -PVS(ni, d-1, -beta, -alpha) 

Because of search instability.

The memory-less search algorithm discussed here will not suffer from any search instability. Without any window-dependent reductions there just is nothing that could jeopardize the reproducibility of the search

[rob]

You can use the standard set of tricks:
* Hash move
* Non-losing captures (according to SEE), in MVV/LVA order.
* Killer moves
* Quiet moves in history-heuristic order.
* Losing captures.

What criteria are you using inside the ZWS to collect killer moves? In a traditional alpha-beta search, I collected killers if they produced a score larger than alpha.

I don't use Schaeffer's history heuristic although I did implement it. I recall reading that Robert Hyatt (apologies in advance if I am not using the preferred first name) also doesn't use the history heuristic in Crafty; There was no apparent performance benefit for Crafty from using history heuristic moves. Are you seeing a benefit in your engine?

Rob

[bob]

You can use the standard set of tricks:
* Hash move
* Non-losing captures (according to SEE), in MVV/LVA order.
* Killer moves
* Quiet moves in history-heuristic order.
* Losing captures.

What criteria are you using inside the ZWS to collect killer moves? In a traditional alpha-beta search, I collected killers if they produced a score larger than alpha.

I don't use Schaeffer's history heuristic although I did implement it. I recall reading that Robert Hyatt (apologies in advance if I am not using the preferred first name) also doesn't use the history heuristic in Crafty; There was no apparent performance benefit for Crafty from using history heuristic moves. Are you seeing a benefit in your engine?

Rob

I started using it again after I went to LMR. The "L" (Late) means that move ordering is a bit more important than without LMR. This tends to push decent moves up in the move list so they are reduced less. But other than for that sole purpose, I don't use the history info for anything else or any search decisions at all.

[AlvaroBegue]

You can use the standard set of tricks:
* Hash move
* Non-losing captures (according to SEE), in MVV/LVA order.
* Killer moves
* Quiet moves in history-heuristic order.
* Losing captures.

What criteria are you using inside the ZWS to collect killer moves? In a traditional alpha-beta search, I collected killers if they produced a score larger than alpha.

The same criterion works here: If you have a response that produced a score larger than alpha (in the case of ZWS this is the same thing as producing a beta cut), you store that as the killer. I don't have statistical evidence that this will work well, but I don't see why it wouldn't. We use ZWS in an attempt at showing that none of the other moves are better than our current champion, and it will often be the case that most of those moves are refuted by the same threat, so that can become the killer move.

I don't use Schaeffer's history heuristic although I did implement it. I recall reading that Robert Hyatt (apologies in advance if I am not using the preferred first name) also doesn't use the history heuristic in Crafty; There was no apparent performance benefit for Crafty from using history heuristic moves. Are you seeing a benefit in your engine?

No, I kept it in because I've always had it, but the last time I checked, it didn't seem to help (or hurt).