alpha beta hashing and move ordering

[adams161]

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

[adams161]

for clarity i do hash exact scores when there is an exact score known it didnt fail high or low, and i forget the other requirement, i think i cant hash a score if its over beta or under alpha or something. of course i need = or greater depth to return a hash score or fail high or low.

[bob]

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.

[adams161]

what brought this up is for the longest time ( this is a policy put in effect years ago with puslar before the hash tables got better debuged) pulsar has been throwing out its hash as it moves to a different turn. like move 5 .. then opponent moves and pulsar i think calls a clean hash function were it does a for loop and i think just sets all hash values in the hash table to 0, which should turn them off, unless by some freak chance a postion is actually hashing to 0. Well i'm thinking i want to do some testing with saving the last searches hash, but i want to be clear that i have good values in there even though its a different search, a different order etc. Obviously the depth of the last search would be lower for the typical postion. early iterations of the next search would get the most benefit since their depth value is low, and the previous search might have reached positons in the next search and gotten sufficient depth that i can actually hash a fail high or low or score ( if depth is insufficient all the hash move is used for is move ordering). Also what is the benefit of saving the hash from search to search, if you got good hash code, in terms of speed up or greater depth? i would tend to think if the search was predictive last time, i.e. they made a move in line with what pulsar expected ply 2 of the last search to be, there be a lot of good values. If they made a move that is unexpected most of that search tree could be pruned.

Mike

[adams161]

also when time is up i set an abort variable and every call just starts returning without searching. i know which move was the abort move, say i searched at the root 6 good moves and aborted on 7, well i expect 7's value is trash so i set an aborttop to tell me to stop looking at scores by move 6. I assume with hash all i have to do is stop hashing moves once that abort variable is set, since scores cant be trusted from that point on, but no reason they cant be trusted before that abort variable is set even though the search didnt complete? correct?

[bob]

what brought this up is for the longest time ( this is a policy put in effect years ago with puslar before the hash tables got better debuged) pulsar has been throwing out its hash as it moves to a different turn. like move 5 .. then opponent moves and pulsar i think calls a clean hash function were it does a for loop and i think just sets all hash values in the hash table to 0, which should turn them off, unless by some freak chance a postion is actually hashing to 0. Well i'm thinking i want to do some testing with saving the last searches hash, but i want to be clear that i have good values in there even though its a different search, a different order etc. Obviously the depth of the last search would be lower for the typical postion. early iterations of the next search would get the most benefit since their depth value is low, and the previous search might have reached positons in the next search and gotten sufficient depth that i can actually hash a fail high or low or score ( if depth is insufficient all the hash move is used for is move ordering). Also what is the benefit of saving the hash from search to search, if you got good hash code, in terms of speed up or greater depth? i would tend to think if the search was predictive last time, i.e. they made a move in line with what pulsar expected ply 2 of the last search to be, there be a lot of good values. If they made a move that is unexpected most of that search tree could be pruned.

Mike

The entire idea is about "transpositoins". That is, reaching the same position through two different move pathways. Suppose your PV for the current move is Nf3 Nf6 Nc3 Nc6. But your opponent plays Nc6 instead. Notice that after you play Nc3 and he plays Nf6, you have reached the same position through a different order of moves. Why search all of this again? The transposition table avoids this and that is its primary function. Bue also, even if you reach a position in the table where the "draft" (remaining depth) is too low to use because your current depth is larger, you still may get a good move to try first. This is what makes iterative deepening work in the first place. If you remove the hash table, then iterative deepening wastes time for no gain... The transposition table is, therefore, critical, in that it carries information from iteration to iteration (and even from move to move in the real game) that can make your search more efficient. You have to hang on to the data in the hash table as long as possible to extract as much utility from it as is possible.

[bob]

also when time is up i set an abort variable and every call just starts returning without searching. i know which move was the abort move, say i searched at the root 6 good moves and aborted on 7, well i expect 7's value is trash so i set an aborttop to tell me to stop looking at scores by move 6. I assume with hash all i have to do is stop hashing moves once that abort variable is set, since scores cant be trusted from that point on, but no reason they cant be trusted before that abort variable is set even though the search didnt complete? correct?

All you need to do is set a flag. After each call to Search()/Quiesce() check to see if this flag is true. If so, do an instant return(0). Do not back up a PV, do not remember the value being passed back to you. Just get out a.s.a.p. This is what I do in crafty. Since I can't possibly back up anything once the abort flag is set, I can never use a bogus score that might be backed up if I were less careful.

[rvida]

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.

I dont agree here. If you use reductions that are dependant on move order (eg LMR), ordering CAN affect your score, even the bestmove for given depth.

[Gerd Isenberg]

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.

[bob]

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.

I dont agree here. If you use reductions that are dependant on move order (eg LMR), ordering CAN affect your score, even the bestmove for given depth.

Simple to solve. Don't do reductions that are dependent on move order. Use some sort of static criteria instead. Nobody reduces checks, or captures, etc. So this is already done to an extent. I don't do any internal ordering in crafty, which makes it foolish to use position within the move list as a reduction criterion when the position is essentially random.