Beginning hashtable question.

[Fguy64]

Ignoring quiescence for now, (hashing inside quiescent search is a whole other discussion) there are three cases for hash writes:

1) The search failed high (ie, a move returned a value above the search window). The resulting score is a lower bound on the true, infinite window score of the node.
2) The search returned a value inside the search window. The result is exact.
3) The search failed low (ie, no move returned a value greater than alpha). The result is an upper bound on the true score of the node.

Unless you record this information in the hash table, you don't know what the number you record as the node's score actually means, and therefore you can't ensure that your transposition cutoffs are sound.

Thanks, that helps. So item 3) is the situation where we have an alpha write. I understand your post, where I have a problem is as follows....

In the situation where a hash probe turns up a match on the key, but the stored depth that the position has been searched to is less than the current depth to be searched, then instead of returning a value, we have a hashMove to play, right? Can we be sure that there will be a hash move to play. Is it possible that this could be an alpha entry? if the answer is yes, then how could there be a move stored if there was no move which caused an alpha update? make sense?

[Aaron Becker]

On fail low nodes, I don't store a move in the hash table. I fill in a hash entry with depth and score information (to help with cutoffs), but there's no move associated with the entry. I'm not positive, but I think this is standard practice. As you point out, there isn't a natural candidate for a hash move at nodes that fail low.

[Fguy64]

On fail low nodes, I don't store a move in the hash table. I fill in a hash entry with depth and score information (to help with cutoffs), but there's no move associated with the entry. I'm not positive, but I think this is standard practice. As you point out, there isn't a natural candidate for a hash move at nodes that fail low.

Your answer makes sense, but doesn't resolve whether it is possible that subsequent key match for a hash probe will pick up this elpha entry. Or, to phrase it differently, when you do a hash probe and find a key Match but the stored depth is too low, then do you check to see if a hash move exists, or do you assume there is one.

That's what I'm trying to nail down, whether it is even possible for a hash probe to turn up an alpha entry where the key matches but the depth is too low.

[Fguy64]

On fail low nodes, I don't store a move in the hash table. I fill in a hash entry with depth and score information (to help with cutoffs), but there's no move associated with the entry. I'm not positive, but I think this is standard practice. As you point out, there isn't a natural candidate for a hash move at nodes that fail low.

Your answer makes sense, but doesn't resolve whether it is possible that subsequent key match for a hash probe will pick up this elpha entry. Or, to phrase it differently, when you do a hash probe and find a key Match but the stored depth is too low, then do you check to see if a hash move exists, or do you assume there is one.

That's what I'm trying to nail down, whether it is even possible for a hash probe to turn up an alpha entry where the key matches but the depth is too low.

p.s, and I guess we can add that if such a scenario is possible, then it follows that a properly functioning system can give us a key match on a hash probe that provides us with no useful information.

[Aaron Becker]

Yes, that scenario is definitely possible and does happen in practice. You just need to take into account the fact that you may have a hash hit, with score, depth, etc, but no move.

[Fguy64]

OK, I'm runnng into as bit of a problem, I suspect i'm misunderstanding an essential aspect of iterative deepening and transposition. I'm in an intermediate phases of development and clarification is needed.

In the case where I have no ID, just a fixed depth search, My hash table is working very well just as a transposition table, and probes, and exact alpha and beta writes, are working well. Also, I am using the triangular approach to collect and display PV, and that is working well also.

Now, when I implement the iterative deepening, without trying to use the PV I am collecting, my evaluations and PV are thrown out of whack. Only when I clear the hash table before each iteration do I get proper eval and PV. I suppose I could get some benefit from ID by using the PV have collected in my trangular PV array, but one should not have to do use that approach at all, correct?

In light of the fact that in a proper implementation, PV moves are stored in exact hash entries, I can only conclude that some aspect of the hash probe, or hash write, needs to change when ID is implemented. In other words. Some but not all of my hash entries recorded at one iteration become invalid at a subsequent iteration. At least I would hope that not all become invald, else I am not gong to find PV moves in hash. It is my understanding that the proiginal alpha and beta is used for each iteration, in the external call to search.

make sense?

[Sven]

OK, I'm runnng into as bit of a problem, I suspect i'm misunderstanding an essential aspect of iterative deepening and transposition. I'm in an intermediate phases of development and clarification is needed.

In the case where I have no ID, just a fixed depth search, My hash table is working very well just as a transposition table, and probes, and exact alpha and beta writes, are working well. Also, I am using the triangular approach to collect and display PV, and that is working well also.

Now, when I implement the iterative deepening, without trying to use the PV I am collecting, my evaluations and PV are thrown out of whack. Only when I clear the hash table before each iteration do I get proper eval and PV. I suppose I could get some benefit from ID by using the PV have collected in my trangular PV array, but one should not have to do use that approach at all, correct?

In light of the fact that in a proper implementation, PV moves are stored in exact hash entries, I can only conclude that some aspect of the hash probe, or hash write, needs to change when ID is implemented. In other words. Some but not all of my hash entries recorded at one iteration become invalid at a subsequent iteration. At least I would hope that not all become invald, else I am not gong to find PV moves in hash. It is my understanding that the proiginal alpha and beta is used for each iteration, in the external call to search.

make sense?

What do you store now: still the "ply" (distance to root in your case), or "draft" (remaining full search depth)?

Do you store best moves in the hash table, and try these first whenever there is a hash table hit but the value can't be used to avoid the current search?

Regarding your PV problems, you might want to implement a function that locally reconstructs the PV from the hash table, and use its result for comparison with the "triangular" PV, for printing, etc.

In general, what changes with ID against fixed-depth is that you frequently revisit nodes that have been searched to draft D in an earlier iteration, but now with a bigger draft D+X. That means you can't replace the new search that you're about to perform by returning the stored hash table value, but you can use the hash table move and try it as first move with draft D+X before searching all other moves.

If all these hints are not sufficient then you can post, or send to me, the relevant current code parts if you like.

Sven

[Fguy64]

OK, I'm runnng into as bit of a problem, I suspect i'm misunderstanding an essential aspect of iterative deepening and transposition. I'm in an intermediate phases of development and clarification is needed.

In the case where I have no ID, just a fixed depth search, My hash table is working very well just as a transposition table, and probes, and exact alpha and beta writes, are working well. Also, I am using the triangular approach to collect and display PV, and that is working well also.

Now, when I implement the iterative deepening, without trying to use the PV I am collecting, my evaluations and PV are thrown out of whack. Only when I clear the hash table before each iteration do I get proper eval and PV. I suppose I could get some benefit from ID by using the PV have collected in my trangular PV array, but one should not have to do use that approach at all, correct?

In light of the fact that in a proper implementation, PV moves are stored in exact hash entries, I can only conclude that some aspect of the hash probe, or hash write, needs to change when ID is implemented. In other words. Some but not all of my hash entries recorded at one iteration become invalid at a subsequent iteration. At least I would hope that not all become invald, else I am not gong to find PV moves in hash. It is my understanding that the proiginal alpha and beta is used for each iteration, in the external call to search.

make sense?

What do you store now: still the "ply" (distance to root in your case), or "draft" (remaining full search depth)?

Do you store best moves in the hash table, and try these first whenever there is a hash table hit but the value can't be used to avoid the current search?

Regarding your PV problems, you might want to implement a function that locally reconstructs the PV from the hash table, and use its result for comparison with the "triangular" PV, for printing, etc.

In general, what changes with ID against fixed-depth is that you frequently revisit nodes that have been searched to draft D in an earlier iteration, but now with a bigger draft D+X. That means you can't replace the new search that you're about to perform by returning the stored hash table value, but you can use the hash table move and try it as first move with draft D+X before searching all other moves.

If all these hints are not sufficient then you can post, or send to me, the relevant current code parts if you like.

Sven

I am now storing the draft (remaining search depth). I am also clearing my PV triangular array at each iteration. I'm not storing any moves in hash yet. Q search and positional eval is turned off at the moment, although I don't see that that should make a difference.

Not only my PV for each iteration is wrong, but the eval that is returned from search is wrong also. It does appear that the first move of each PV is correct, although that is a pretty casual observation. Anyways, I'll take another close look at my code in the context of your remarks, and let you know how it goes. Thanks.

[jwes]

I would try it without the transposition table to make sure ID is working correctly.

[Fguy64]

I would try it without the transposition table to make sure ID is working correctly.

Thanks, but I think I have found my problem. It ws a logic error in one of my hash writes.

My convention for numbering the plies is slightly non-standard I guess, although it is intuitive for me. I have a class variable iPly, and in my ID loop iPly goes from 1 to maxPly. At each iteration, 1 is passed to alphsBeta, then in my recursive alphaBeta method, ply goes from 1 to iPly inclusive, and evaluate() is called for ply > iPly.

The problem was, along with my call to evaluate, I was storing a draft (remaining depth) of 0, which is wrong since my stop condition is ply > iPly. By storing a depth of -1 for this exact hash write at the stop condition, all my problems appear to have been resolved. It's not clear to me why my straght up fixed depth searching appeared to work fine with this particular hash write error.

regards.