principal variation search

[adams161]

I dont have any special principal variation ordering in pulsar.

i order the previous root move first at root on each iteration, and i have hash tables so i assume if a principal variation is in hash it will get ordered.

Now i was thinking i only order a hash move if it caused a score change or fail high, not fail low, as there is no move, would any node of the PV every not cause a score change or pottentially not get ordered?

Mike

[bob]

I dont have any special principal variation ordering in pulsar.

i order the previous root move first at root on each iteration, and i have hash tables so i assume if a principal variation is in hash it will get ordered.

Now i was thinking i only order a hash move if it caused a score change or fail high, not fail low, as there is no move, would any node of the PV every not cause a score change or pottentially not get ordered?

Mike

Not possible except for very rare cases. A score has to be backed up from the tip, which means it passes back thru each ply with a best move at that ply.

[sje]

A predicted variation is built, as Bob noted, from a terminal node back to the root. And while it is true that each move in a PV is the best move at the corresponding node, it is not true that the best move at a node can always be part of any PV. If the best move at a node is outside the node's window, then there's no expectation that it can be played on the board and so it isn't a part of a PV.

Nodes where the best move is inside the window are relatively rare, so storing all of them in a transposition table has almost no overall cost. Most moves stored in the transposition table are fail high moves; I'd guess that few programs bother to store fail low moves.

[bob]

A predicted variation is built, as Bob noted, from a terminal node back to the root. And while it is true that each move in a PV is the best move at the corresponding node, it is not true that the best move at a node can always be part of any PV. If the best move at a node is outside the node's window, then there's no expectation that it can be played on the board and so it isn't a part of a PV.

Nodes where the best move is inside the window are relatively rare, so storing all of them in a transposition table has almost no overall cost. Most moves stored in the transposition table are fail high moves; I'd guess that few programs bother to store fail low moves.

This is an old discussion. Ed and I once argued about this as he had an algorithm he thought would find the best move even at a fail low node. He finally removed that code and it made his search go much faster. The hash move does need to be a good move, since you try it faithfully before trying any other move. And at fail low moves, by definition, each move was refuted and returned alpha or less, so there is no way to know which is best. I still store the fail low data, but the best move is zeroed out since I do not know what it should be...

In a normal implementation, as you mentioned, most entries are fail high or fail low nodes, there are very few actual EXACT-type entries assuming one is doing the classic null-window search implied by PVS/negascout/etc.