Triangular PV question

[hgm]

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

Yes, I understood that. My remark fully applies to that case. Natale already explained it in more detail.

The problem is not that TT entries are overwritte. IID takes care of that, and usually then hits upon the daughter (which is not overwritten) in the first iteration, so that you will resume following the old PV despite the missing entry. The problem is that when the entries from the previous search are there, they might be 'too good', and thus cause cutoffs.

[lucasart]

I do it recusively in Komodo because I am lazy:

int search( ... move_t *pv)



pv is an array of 64 moves. The first thing I do in the search routine is set the first move to null (a non-move) so that if there is a cutoff or something it does not retain the garbage:

int search( ... , move_t *pv)
{
pv[0] = NULL_MOVE;
....
}

When I recusively call any search routine I pass a local pv variable:


int search( ... , move_t *pv)
{
move_t sub_tree_pv[64];

pv[0] = NULL_MOVE;
....

sc = -search(-beta, -alpha, .... sub_tree_pv);

}

If the move proves to be the best move then I update pv with sub_tree_pv starting at the 2nd entry of sub_tree_pv - and the first move of pv is the local move that proved to be best.

Always make sure you do not update past the end of the array of course. I think my update code looks something like this:

if (sc > best_score) {
pv[0] = current move
memcpy(pv+1, sub_tree_pv, 63 * sizeof(mv_t));
pv[63] = NULL_MOVE; // to be sure we always end will a sential end-of-list
....
}

A NULL move is the move end-of-list sentinal. I used to do this in a loop to save time copying 63 moves when the PV was short, but I was unable to prove this was any benefit at all.

Don

To collect the PV, I use the eazy, lazy and notoriosly unreliable method of walking through the hash table. But I would like to implement the correct method, which involves a triangular pv array. Bruce Moreland's article explains it well in this page:

http://web.archive.org/web/200404270138 ... ing/pv.htm

A great article, but also "educational fraud": the context given is just too simplistic. Simple alpha-beta, no PVS, and no pruning anywhere (other than beta cutoffs), no IID...

Unfortunately, the article in the CPW doesn't give any further explanation, other than discuss endlessly how to represent a triandular array (which is trivial and uninteresting).

In a real program, it seems that there are more questions to answer:

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

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 ?

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 (?)

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?

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

Thanks!

I implemented it exactly like you and it works nicely. A couple of things I like in your implementation:
* the pv[0] = 0 at the entry of the search (at PV nodes) takes care of all early exit cases, and avoids having to terminate the PV in every such case.
* the PV copy code: nice and lazy mencpy, avoid having to think about indices and stop the loop only after having copied the null terminator. who cares about saving a few iterations, since it's not on the "hot path".

Another thing that is nice with the recursive method is that you don't need to have a big global array like pv[MAX_PLY][MAX_PLY], whose content is mostly useless outside context (only pv[0][...] makes sense outside the contect of the search, because we don't know where the other fragment PV lines start from). You just have a local array pv[MAX_PLY] that can stay in the context of the function that calls the search at the root.

This turns out to be simpler and more concise than the PV from TT stuff I had before. Something for Marco to reconsider in Stockfish.

[Don]

I do it recusively in Komodo because I am lazy:

int search( ... move_t *pv)



pv is an array of 64 moves. The first thing I do in the search routine is set the first move to null (a non-move) so that if there is a cutoff or something it does not retain the garbage:

int search( ... , move_t *pv)
{
pv[0] = NULL_MOVE;
....
}

When I recusively call any search routine I pass a local pv variable:


int search( ... , move_t *pv)
{
move_t sub_tree_pv[64];

pv[0] = NULL_MOVE;
....

sc = -search(-beta, -alpha, .... sub_tree_pv);

}

If the move proves to be the best move then I update pv with sub_tree_pv starting at the 2nd entry of sub_tree_pv - and the first move of pv is the local move that proved to be best.

Always make sure you do not update past the end of the array of course. I think my update code looks something like this:

if (sc > best_score) {
pv[0] = current move
memcpy(pv+1, sub_tree_pv, 63 * sizeof(mv_t));
pv[63] = NULL_MOVE; // to be sure we always end will a sential end-of-list
....
}

A NULL move is the move end-of-list sentinal. I used to do this in a loop to save time copying 63 moves when the PV was short, but I was unable to prove this was any benefit at all.

Don

To collect the PV, I use the eazy, lazy and notoriosly unreliable method of walking through the hash table. But I would like to implement the correct method, which involves a triangular pv array. Bruce Moreland's article explains it well in this page:

http://web.archive.org/web/200404270138 ... ing/pv.htm

A great article, but also "educational fraud": the context given is just too simplistic. Simple alpha-beta, no PVS, and no pruning anywhere (other than beta cutoffs), no IID...

Unfortunately, the article in the CPW doesn't give any further explanation, other than discuss endlessly how to represent a triandular array (which is trivial and uninteresting).

In a real program, it seems that there are more questions to answer:

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

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 ?

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 (?)

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?

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

Thanks!

I implemented it exactly like you and it works nicely. A couple of things I like in your implementation:
* the pv[0] = 0 at the entry of the search (at PV nodes) takes care of all early exit cases, and avoids having to terminate the PV in every such case.
* the PV copy code: nice and lazy mencpy, avoid having to think about indices and stop the loop only after having copied the null terminator. who cares about saving a few iterations, since it's not on the "hot path".

Another thing that is nice with the recursive method is that you don't need to have a big global array like pv[MAX_PLY][MAX_PLY], whose content is mostly useless outside context (only pv[0][...] makes sense outside the contect of the search, because we don't know where the other fragment PV lines start from). You just have a local array pv[MAX_PLY] that can stay in the context of the function that calls the search at the root.

This turns out to be simpler and more concise than the PV from TT stuff I had before. Something for Marco to reconsider in Stockfish.

There is no rule that says your PV has to be 64 moves long either, it could be 30 or 40 if you want to save a little copying although I doubt you will be able to measure a difference. Or it could be much longer.

Also, you do not have to do this in non-pv nodes if your program makes that distinction so you could have a 1000 move PV and not notice a difference as PV nodes are a fraction of a percent of all the nodes. In quies you could probably limit the copy (and sentinel) to 8-12 moves if you really want to engineer it to death! I did stuff like that when I was younger, now I don't care

[lucasart]

There is no rule that says your PV has to be 64 moves long either, it could be 30 or 40 if you want to save a little copying although I doubt you will be able to measure a difference. Or it could be much longer.

Yes, I figured that your 64 is an arbitrary limit. I'm not *that* dumb

My max PV length is 127 plies. This is because I use 8 bits signed for the depth in TT entries, so from -128 to + 127. So I use arrays of 128 elements (to allow for the null terminator). 127 is more than enough.

My iterative deepening loop stop after depth=127 (for the same reason).

Using variable length arrays, I could half the stack space useage

Code: Select all

move_t subtree_pv[128-ply];

of course I need an assert around that, and test it well, because when you start to have stack overwriting in a recursive search, you're deeply screwed...

[hgm]

Using variable length arrays, I could half the stack space useage

Code: Select all

move_t subtree_pv[128-ply];

of course I need an assert around that, and test it well, because when you start to have stack overwriting in a recursive search, you're deeply screwed...

Indeed, that is why I used a 1d array as a stack rather than a 2d array. Then all the PVs are optimally packed.

Note that pv[128-ply] is in most cases still way to large. But it is also risky trying to predict the exact lengths of each PV, as there could be extensions, and reductions.

[lucasart]

My only remaining problem is this one:

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 (?)

In practice, it can happen that there is no ponder move pv[1] as a result, which is annoying. I don't know if it's UCI compliant to have Ponder=true (UCI option) and to send either:

Code: Select all

bestmove pv[1] ponder pv[1]

when pv[1] != 0, or

Code: Select all

bestmove pv[0]

when pv[1] = 0.

If there's no ponder move sent, the engine would patiently wait his turn and not be asked to ponder, simply. This means we are not using the time at hand to ponder, which is a waste, but it should be rare enough that it doesn't affect ELO (in pondering conditions).

I can see a couple of solutions:

1/ use the TT. if pv[1]=0, then:

Code: Select all

play pv[0]
probe the TT and set pv[1] = TT move (if any)
undo pv[0]

It doesn't guarantee that there is a ponder move (because of TT overwriting), but most often there will.

2/ no TT pruning at PV nodes. Avoids the problem completely. But there may be a small loss of ELO involved. I'm running a test to see (if there's no ELO loss I'll choose that solution as it's the cleanest).

[hgm]

Yes, it is UCI compliant. It has to be. When the engine plays a move that checkmates or stalemates there can also be no ponder move.

Not pruning o TT hits in the PV hurts a bit in end-games (where grafting can be very important), but I doubt it will be measurable in terms of Elo. You can limit the no-pruning to ply 2, and then it will certainly not affect Elo.

In an engine that makes an instant reply when it has only a single legal move, there is a similar problem.

[lucasart]

Yes, it is UCI compliant. It has to be. When the engine plays a move that checkmates or stalemates there can also be no ponder move.

Thanks for confirming. I figured it would compliant or one would have to send "ponder 0000" or something silly like that in such cases.

Not pruning o TT hits in the PV hurts a bit in end-games (where grafting can be very important), but I doubt it will be measurable in terms of Elo. You can limit the no-pruning to ply 2, and then it will certainly not affect Elo.

I did a quick test of disabling TT pruning at PV nodes: 10000 games in 5"+0.05" with Hash=1, and got the following result

Code: Select all

W: 2839 L: 2875 D: 4286 [49.8%]

So it's not statistically significant, but still it shows that there could be a small regression in not doing TT pruning at PV nodes.

I'm a bit worried to validate a regression, even a tiny one, so I opted for the ply >= 2 condition that you propose, to be on the safe side
https://github.com/lucasart/chess/commi ... d841627956

In an engine that makes an instant reply when it has only a single legal move, there is a similar problem.

DiscoCheck does that. I need to handle that case too. Thanks for reminding me!

[hgm]

I just implemented speculative pondering in Shokidoki (it used to have 'think-for-the-opponent pondering', and I did it the following way:

It starts thinking for the opponent (like it used to), but after it completes the 7-ply iteration it freezes the best move so far by jumping to iteration 1000. So it now starts speculatively pondering that move. Whenever it returns from that 1000-ply search at ply 2 it makes sure it aborts the node at ply 1 (because it returns by setting the abort flag, which it also does when it is severely out of time).

This way I never have to worry about the availability of a ponder move. Normally the first 7 iterations from the opponent would be instantly recovered from the hash (all nodes at ply 2 are sufficient-draft hits). But if for some reason there would be nothing there, it first generates a ponder move by itself with a 7-ply search. Basically it is like pondering for the opponent, but suppressing the search of all alternative moves after you reach depth 7.

[lucasart]

Using variable length arrays, I could half the stack space useage

Code: Select all

move_t subtree_pv[128-ply];

of course I need an assert around that, and test it well, because when you start to have stack overwriting in a recursive search, you're deeply screwed...

Indeed, that is why I used a 1d array as a stack rather than a 2d array. Then all the PVs are optimally packed.

I think the recursive method is the most elegant (with or without optimal compactness using VLA, stacks are so big these days...)
- indexing is simpler than the flat array solution.
- SMP: every thread has its own stack, so there's no problem of concurrent access to the global PV array.
- elegance: no global variable (whether triangular or quadratic array) whose content is mostly irrelevant at global scope (PV fragments from positions who have been lost). everything is nicely in the scope where it belongs.

Don said he does it because he's "lazy". I've always been convinced that lazyness is the beginning of intelligence

To iterate is human. To recurse is divine.