Triangular PV question

[lucasart]

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

[hgm]

In Shokidoki I just put the PV moves on a stack pvMoves[] (pvPtr pointing at the first free element), and each PV terminated by a zero (which would be an invalid move encoding). In Search(), after the return of the recursive call, whenever the score is between alpha and beta, I then do:

Code: Select all

#ifdef PV_UPDATE
		    {   int i = pvPtr; // start of PV 'returned' by daughter node
			pvMoves[pvPtr=pvStart] = moveStack[curMove].m & 0xFFFF; // our own move
			while(pvMoves[++pvPtr] = pvMoves[i++]); // and copy sequel after it
			pvPtr++;
		    }
#endif

When entering Search() I do

Code: Select all

int pvStart = pvPtr; // start of this node's PV
pvMoves[pvPtr++} = 0; // initialize empty PV

and when leaving I restore pvPtr (deallocating the space on the stack used by the returning move's PV, but leaving the data there, so the parent can copy it):

Code: Select all

pvPtr = pvStart;

That is all. There are so few PV nodes that any worry about making it more efficient is a pure waste of time. Even if you do plain alpha-beta rather than PVS. So I don't worry about IID at all.

I use the same Search() for QS and full-width; if you would use separate search routines (for whatever purpose) you would have to include the code in each of them.

[mcostalba]

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

[hgm]

Or you could look at Fairy-Max, from which I actually took the above code (which uses it in the context of plain alpha-beta, but which uses more cryptic variable names).

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

[lucasart]

So I don't worry about IID at all.

The reason I worry about IID is not efficiency. Granted: few PV nodes -> don't care about speed.

The problem is that the IID search will pollute the subsequent PVs. On the other hand, it should be overwritten by the actual PV, unless we fail low (in which case we're in a partial PV that will get refuted later, or it will propagate all the way to the root and fail low/high in the aspiration window, so we don't need a PV). So I *guess* the IID side effect is not a problem, but I'm not sure...

[Don]

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

In my simple recursive implementation Komodo goes all the way through the PV. There is no reason to stop at quies and you generally want to see what is going on the PV.

[hgm]

I don't see how IID can be a problem. You will never leave a node before IID reaches its ultimate depth. When it does, the PV obtained at a lower depth in that node (if any) will be overwritten by that of the full depth for that ply. If it is not overwritten (because you fail high or low at full depth) the parent node will ignore what you might have gotten at the lower depth anyway (because you only back up the PV for moves that don't fail either way).

Fairy-Max does IID in every node, in steps of 1. This never gives any problem, with the code I posted.

[Don]

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

In my simple recursive implementation Komodo goes all the way through the PV. There is no reason to stop at quies and you generally want to see what is going on the PV.

I meant all the way through quies.

[Rein Halbersma]

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 ?

Yes, and only if alpha is being raised.

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 ?

No, only along the PV, and only when alpha is raised. For each depth, I pass a stack-based array to each recursive call to search(). Cutoffs are simply returns without any modification to that array. Null move is just another move, and with the double null move trick you never propagate that to the root.

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

TT pruning is just another return, without any modifications. One-level higher that return could cause an alpha-raise, and only then do you update the PV with the TT-move.

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?

Not necessary: IID or LMR or any kind of reduced search simply gets the same array passed as a parameter. IID will neatly fill that array with the correct PV.

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

Simply pass the array to qsearch as well, and you get a PV all the way to the position being evaluated. In fact, I have an assert() in debug mode that verifies that the position at the end of the PV has a score that is exactly equal to the eval().

There isn't much else to it, really. The only subtlety that I have come across is to clear the current PV array after you detect a repetition draw or mate. See http://talkchess.com/forum/viewtopic.ph ... highlight=