adams161 wrote:Pulsar uses root ordering prior to every iteration of search. If on ply 1 the best move is move 20 then move 20 moves to spot 1. On ply 2 if the best move is now move 13 then move 13 moves to spot 1 and move 20 moves to spot 2. This means on interation 3, a 3 ply search it will search move 13 then move 20 then go in order. The benefit is better moves are played at the root. And if I reach ply 8 and have to abort before finishing, I will have played my best moves first and have scores on them.
Here is my question, as you fill your hash table moving through the moves at the root, alpha beta are the best moves so far. If you have fully searched root moves 1 2 and 3 they can only be as good as those moves. Move 4 may be better. But if the root order changes does this effect hashing. True I don’t hash exact scores, only fail highs and lows, but it seems that using the same hash values from a previous iteration may effect things if you don’t search in the same order so you are not really at the same alpha beta points in the new search.
Mike
Doesn't affect a thing except the size of the tree. That's all move ordering changes can _ever_ do. Ordering can't affect which move is best, nor the score, nor anything else...
Order is immaterial to best move when you think about it... You only need to find the path from the root to the best possible terminal position. Doesn't matter how big or small the tree, except for time.
As pointed out by Warnock, T. and Wendroff, B. (1988). Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 1, pp. 10-13., Alpha-Beta with hashing is order dependent. Also in PVS a value returned from TT can cause a cutoff that is violated in a subsequent re-search.
That is correct. But in reality, how does this affect the best move or its score? yes, hashing lets us solve fine 70 in less than the required 26 plies, by tree-grafting. But how often does that occur. In general, order has no effect on alpha/beta, proven quite simply by knuth/moore, when "no effect" applies to score and best move, but not to tree size. Alpha/beta is certainly dependent on ordering to search the smallest possible tree. But you can search the tree in worst-first order and get the same move/score except for the hashing inconsistencies (caused by an implementation problem where we do not include path information, of course)
Changing the order of the moves searched at the root is not going to have _any_ effect on the best move or score, except for the tree-grafting problem already mentioned. Bad ordering is the only way you can solve fine 70 faster than 26 plies, in fact. But I'd rather have perfect ordering even though it would mean a little slower solution for fine 70, because it would help overall significantly.
adams161 wrote:Pulsar uses root ordering prior to every iteration of search. If on ply 1 the best move is move 20 then move 20 moves to spot 1. On ply 2 if the best move is now move 13 then move 13 moves to spot 1 and move 20 moves to spot 2. This means on interation 3, a 3 ply search it will search move 13 then move 20 then go in order. The benefit is better moves are played at the root. And if I reach ply 8 and have to abort before finishing, I will have played my best moves first and have scores on them.
Here is my question, as you fill your hash table moving through the moves at the root, alpha beta are the best moves so far. If you have fully searched root moves 1 2 and 3 they can only be as good as those moves. Move 4 may be better. But if the root order changes does this effect hashing. True I don’t hash exact scores, only fail highs and lows, but it seems that using the same hash values from a previous iteration may effect things if you don’t search in the same order so you are not really at the same alpha beta points in the new search.
Mike
Doesn't affect a thing except the size of the tree. That's all move ordering changes can _ever_ do. Ordering can't affect which move is best, nor the score, nor anything else...
Order is immaterial to best move when you think about it... You only need to find the path from the root to the best possible terminal position. Doesn't matter how big or small the tree, except for time.
As pointed out by Warnock, T. and Wendroff, B. (1988). Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 1, pp. 10-13., Alpha-Beta with hashing is order dependent. Also in PVS a value returned from TT can cause a cutoff that is violated in a subsequent re-search.
That is correct. But in reality, how does this affect the best move or its score? yes, hashing lets us solve fine 70 in less than the required 26 plies, by tree-grafting. But how often does that occur. In general, order has no effect on alpha/beta, proven quite simply by knuth/moore, when "no effect" applies to score and best move, but not to tree size. Alpha/beta is certainly dependent on ordering to search the smallest possible tree. But you can search the tree in worst-first order and get the same move/score except for the hashing inconsistencies (caused by an implementation problem where we do not include path information, of course)
Changing the order of the moves searched at the root is not going to have _any_ effect on the best move or score, except for the tree-grafting problem already mentioned. Bad ordering is the only way you can solve fine 70 faster than 26 plies, in fact. But I'd rather have perfect ordering even though it would mean a little slower solution for fine 70, because it would help overall significantly.
Except for the minor case of two moves with the same evaluation. Different move ordering can cause different best moves but with the same score.