How to recognize the optimal parent to a node?
Moderators: hgm, Rebel, chrisw
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
How to recognize the optimal parent to a node?
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?
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: How to recognize the optimal parent to a node?
Interesting! May be something like Retrograde Analysis?smrf wrote: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?
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...
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: How to recognize the optimal parent to a 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.Gerd Isenberg wrote:... 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. ...
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.
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: How to recognize the optimal parent to a node?
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 wrote: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?
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: How to recognize the optimal parent to a node?
Of course! But how to "create some estimate of optimality"? This is just my question. P.S.: how to identify the most natural ancestor?jwes wrote: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 wrote: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?
-
- Posts: 442
- Joined: Wed Mar 08, 2006 8:54 pm
Re: How to recognize the optimal parent to a node?
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
'Nearly Optimal Minimax Tree Search?' by Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin.
MvH Dan Andersson
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: How to recognize the optimal parent to a node?
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.
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.
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: How to recognize the optimal parent to a node?
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.smrf wrote: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.Gerd Isenberg wrote:... 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. ...
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.
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
-
- Posts: 484
- Joined: Mon Mar 13, 2006 11:08 am
- Location: Klein-Gerau, Germany
Re: How to recognize the optimal parent to a node?
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 wrote:... Back to your question, defining "quality" is only possible when you first assess, what you want to do with the additional information. ...
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: How to recognize the optimal parent to a node?
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?smrf wrote: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 wrote:... Back to your question, defining "quality" is only possible when you first assess, what you want to do with the additional information. ...