Triangular PV question

[lucasart]

The original Glaurung has this method, in case you are interested you may look there for a reference implementation.

Just out of curiosity, do you remember why you removed it in Stockfish and replaced it with the TT method ?
It seems like a regression to me

[xmas79]

1/ In a PVS algorithm, you only do that at PV nodes, right ?

I do it or every node type, as at the splitting node search will take care of updating or not parent PV.

2/ the "if (depth == 0) pline->cmoves = 0", which says that the PV of the current ply is empty when we stand pat (in a real program would be when we call the qsearch() instead of evaluate()). Should I do that at every possible exit point of the search (other than beta cutoff). For example: razoring, eval pruning, null move pruning (I don't do them at PV nodes, but let's imagine I did), SEE pruning, move count pruning ?

I do EVERY time im going to have an EXACT score:
1) before calling qsearch
2) after a draw by repetition or TT hash hit with EXACT score
3) when alpha is improved (code is executed AFTER beta cutoff check)

3/ what about TT pruning at a PV node ? If I clear the PV of the current ply, it means that a TT pruning in the PV results in a truncated PV. That could mean there's no ponder move (pv[1]=null). A bit annoying. Seems inevitable though, unless one has a different hash table for PV nodes that stores PV or something (?)

I think this is an open question...

4/ IID ? I don't want to pollute the PV extraction mechanism when within an IID search (ie. if any ancestor of the current node, even grand grand grand father etc. was an IID search, we shouldn't back up the PV). Is there a ruse to get around this problem?

I don't see any problem with that, as you never leave that node during IID, so you actually cannot update its parent. Simply calling (IID) search with the local PV as you usually do in normal search and then using the PV[0] as best move should do the trick...

5/ qsearch? Is it common wisdom to terminate the PV at the end of the search(), or do some programs also include the qsearch()? It seems interesting to continue the PV in the qsearch, as there can be some interesting sequences of captures/checks that are worth displaying (at least, you can follow the PV till the end, and know on which position you stood pat, and you can see where the score is coming from).

I tried to get it working, and maybe it is, but for the "problems" I had I actually disabled it.

[xmas79]

...
I do EVERY time im going to have an EXACT score:
1) before calling qsearch
2) after a draw by repetition or TT hash hit with EXACT score
3) when alpha is improved (code is executed AFTER beta cutoff check

Sorry I was in hurry. I mean in 3) I update parent only when alpha is improved.

I set length=0 in 1) 2) and in checkmate/stalemate condition.

[hgm]

The triangular-array method is not intrinsically superior to the TT method. The former gives you shortened PVs because of hash cuts (and fixing that by disabling hash cuts in PV nodes prevents grafting overdeep hash hits), while the latter gives you PVs that are different from the one used by the search to provide the root score.

The only method that works perfectly is hashing the PV of PV nodes in a separate table, so that in case of a hash hit you will also retrieve the entire PV on which the hashed score was based. (And use that in combination with the triangular array.)

[Rein Halbersma]

The triangular-array method is not intrinsically superior to the TT method. The former gives you shortened PVs because of hash cuts (and fixing that by disabling hash cuts in PV nodes prevents grafting overdeep hash hits), while the latter gives you PVs that are different from the one used by the search to provide the root score.

The only method that works perfectly is hashing the PV of PV nodes in a separate table, so that in case of a hash hit you will also retrieve the entire PV on which the hashed score was based. (And use that in combination with the triangular array.)

What also works is to collect the PV through an array parameter of the search() function (in the way described by Bruce Moreland's tutorial), and to insert this PV at the root in the hash table at the start of the next iteration. This also means I don't need special code to avoid TT cutoffs in PV nodes (because the old PV is searched with a full window first). I have many elaborate asserts() to verify correctness of the PV down to the position generating the propagated score, and it never fires.

[hgm]

But that amounts to the same thing, not? You have no PV cutoffs because you destroyed the PV entries that could give such cutoffs by less deep entries, that don't. This is the same thing as forbidding hash cutoffs in PV nodes..

[Rein Halbersma]

But that amounts to the same thing, not? You have no PV cutoffs because you destroyed the PV entries that could give such cutoffs by less deep entries, that don't. This is the same thing as forbidding hash cutoffs in PV nodes..

No I mean, in the main ID loop at the root, after every iteration, I first insert the propagated PV of the previous iteration into the main hash table (not a separate dedicated one). Searching that PV as the left-most path in the new iteration and doing a full window search on that PV, make sure I don't need special code to avoid cutoff along the PV.

Because I only rely on the propagated PV array, I don't care whether those PV entries in the hash table get overwritten during the search of later moves.

[mcostalba]

The original Glaurung has this method, in case you are interested you may look there for a reference implementation.

Just out of curiosity, do you remember why you removed it in Stockfish and replaced it with the TT method ?
It seems like a regression to me

Because it was simpler, I removed a good bunch of code and at the time it didn't seem a regression to me, although my testing resources were peanuts compared to what we have now.

[xmas79]

No I mean, in the main ID loop at the root, after every iteration, I first insert the propagated PV of the previous iteration into the main hash table (not a separate dedicated one). Searching that PV as the left-most path in the new iteration and doing a full window search on that PV, make sure I don't need special code to avoid cutoff along the PV.

So you are avoiding TT cutoffs in PV nodes as described by HG. Since you insert that PV into main hashtable, you expect search to follow PV untill the end and not have a cutoff, which will never happen because when you *just* insert this PV from previous iteration, you *are* overwriting something that (eventually) is the same PV node with different draft and scores, which originally*could* cause a cutoff (e.g. if you don't change the draft).

And this lead me to a question: what to do when you do an hash probe, see that you have a hash signature match but a draft is less than current depth? This obviously cannot lead to a cutoff, but the question is: do you use the best move retrieved or let search start with its own stuff?

[lucasart]

The original Glaurung has this method, in case you are interested you may look there for a reference implementation.

Just out of curiosity, do you remember why you removed it in Stockfish and replaced it with the TT method ?
It seems like a regression to me

Because it was simpler, I removed a good bunch of code and at the time it didn't seem a regression to me, although my testing resources were peanuts compared to what we have now.

It's not a regression in terms of ELO: there should be no ELO difference. Whatever you do there should be a non functional patch, so no testing is needed.

What I meant is that it's a regression in terms of functionality. The search method is more accurate than the TT method, because the TT entries get overwritten, and even if you do show a long PV with the TT method, how much of this PV is actually correct ? And how does the answer to the previous question depend on your TT replacement method ? (which is ugly because TT replacement should be optimized with ELO in mind not caring about the risk of breaking PV display).

An old forum post, where Stuart Cracraft (original author of GNU Chess versions <= 5.07) was experimenting with both methods and decided to abandon the TT method:
http://www.stmintz.com/ccc/index.php?id=387179

Bob Hyatt is also of the same opinion
http://open-chess.org/viewtopic.php?f=5&t=2309

When I'm back from holiday, I'll implement the search method andkeep the TT method in order to do some comparison.

For DiscoCheck, it's probably not so important, because nobody uses it for serious analysis. But for a top engine like Stockfish, it's really important, because people really do use it for analysis, and look at the PV line, comparing it with Houdini, Komodo, Critter, etc.

Anyway, it's up to you. But something to consider.