How to recognize the optimal parent to a node?

[smrf]

Because of transpositions there might be several nodes which could qualify as parent of a given node. There are several ideas to be tested, which could lead to search improvements when there would be an ability to always identify the right (optimal) ancestor. Are there any well founded methods to accomplish this?

[Gerd Isenberg]

Because of transpositions there might be several nodes which could qualify as parent of a given node. There are several ideas to be tested, which could lead to search improvements when there would be an ability to always identify the right (optimal) ancestor. Are there any well founded methods to accomplish this?

Interesting! May be something like Retrograde Analysis?

Otherwise, as a quick shot, one may also store not only the best move found into the TT, but also the current move from the parent node. If one gets an exact hit later from another move sequence, one may traverse the tree the other way around to look for the common ancestor and further analysis...

[smrf]

... Otherwise, as a quick shot, one may also store not only the best move found into the TT, but also the current move from the parent node. ...

No, it is not about retrograde analysis, yet. For this moment it has to do with an intended kind of node management. The problem is, that there isn't THE parent node. There could be SEVERAL parent nodes because of transpositions leading to identical child nodes.

But it seems to be necessary for some intended purpose to order those potential parent nodes taken from a game tree or selected inside a transposition table by quality. Therefor I ask for criteria, which parent node (or an optimal pair of those) should be elected. Would it make sense e.g. to prefer by the sequence of their last occurrences leading to their common child node?

P.S.: some programs seem to have evaluation procedures, which are depending on the preceding node. This will cause different evaluations or tree search results for the same node when approaching from different parents. Such will create instabilities during calculations what better should be avoided.

[jwes]

Because of transpositions there might be several nodes which could qualify as parent of a given node. There are several ideas to be tested, which could lead to search improvements when there would be an ability to always identify the right (optimal) ancestor. Are there any well founded methods to accomplish this?

You could create some estimate of optimality and every time you store a hash entry you could save it and the last move, then when you access the hash table, if the current path has a higher optimality, replace the optimality value and the last move.

[smrf]

Because of transpositions there might be several nodes which could qualify as parent of a given node. There are several ideas to be tested, which could lead to search improvements when there would be an ability to always identify the right (optimal) ancestor. Are there any well founded methods to accomplish this?

You could create some estimate of optimality and every time you store a hash entry you could save it and the last move, then when you access the hash table, if the current path has a higher optimality, replace the optimality value and the last move.

Of course! But how to "create some estimate of optimality"? This is just my question. P.S.: how to identify the most natural ancestor?

[Dan Andersson]

There are some papers concerning minimal graphs one of the first I read is:
'Nearly Optimal Minimax Tree Search?' by Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin.

MvH Dan Andersson

[smrf]

I understand your hint as to select parent nodes, which are members of a kind of a minimal tree. Taking an alpha beta evaluation tree (making extended use of transpositions) here seems not to help directly, as a parent selection decision (or a continuously improving update) has to be done just in time.

P.S.: moreover nevertheless there no guarantee seems to exist, that only one unique potential parent would exist inside such a kind of optimal tree.

[Edmund]

... Otherwise, as a quick shot, one may also store not only the best move found into the TT, but also the current move from the parent node. ...

No, it is not about retrograde analysis, yet. For this moment it has to do with an intended kind of node management. The problem is, that there isn't THE parent node. There could be SEVERAL parent nodes because of transpositions leading to identical child nodes.

But it seems to be necessary for some intended purpose to order those potential parent nodes taken from a game tree or selected inside a transposition table by quality. Therefor I ask for criteria, which parent node (or an optimal pair of those) should be elected. Would it make sense e.g. to prefer by the sequence of their last occurrences leading to their common child node?

P.S.: some programs seem to have evaluation procedures, which are depending on the preceding node. This will cause different evaluations or tree search results for the same node when approaching from different parents. Such will create instabilities during calculations what better should be avoided.

With not much success I have tried a special moveordering dealing with parent node threats. However I never thought about the problems concerning move transpositions in this context before.

Back to your question, defining "quality" is only possible when you first assess, what you want to do with the additional information. In my case this additional knowledge that one of the parent moves was a threatening move is worth a lot, because even though through a different transposition the last move wasn't the threat still it is on the board. So dealing with this would require maybe 6bit in the TT storing the target square of the threat.

regards,
Edmund

[smrf]

... Back to your question, defining "quality" is only possible when you first assess, what you want to do with the additional information. ...

One goal e.g. would be to more precisely estimate the local on-move advantage by comparing static evaluations between child and its "natural / optimal" parent.

[Edmund]

... Back to your question, defining "quality" is only possible when you first assess, what you want to do with the additional information. ...

One goal e.g. would be to more precisely estimate the local on-move advantage by comparing static evaluations between child and its "natural / optimal" parent.

How about storing the parent static eval in the TT entry of the child-node and only replace the exising value if it is < than the new one?