Beginning hashtable question.

[Fguy64]

Thanks Sven I appreciate your help. I gather from your remarks that the real benefit of hashing comes in a system that uses iterative deepening. And I will get to that, and give serious thought to your remarks, later. But I still want to squeeze what I can, in terms of saving of nodes from transpositions, from my current fixed depth searching, and in this context I do not see that you are arguing against my saving of ply as "distance from root". Agreed?

Anyways, my current focus is with my fixed depth search, and dealing with the issue of upper and lower bounds that HG raised, and why "fixing the ply" at which hashing is done, as I showed earlier, seems to avoid the problem. The other thing I still need to figure out is just how to determine if a score obtained by search is exact, or upper or lower bound. Once that is done I'll return to your last couple of posts for another look.

[Fguy64]

Anyways, just to close off this particular chapter, I managed to figure out the upper/lower bound thing using Bruce Moreland's pages as a guide, and ran the first dozen or so WAC positions through the wringer. So with a fixed depth search and qSearch turned off, I managed about a 50% reduction in leaf nodes, which was encouraging. I'll probably take a look at iterative deepening in a week or two.

Thanks to all for the help.

[hgm]

If you fix the ply at 3, you will not have any transspositions. They require at least 4 ply. So you won't have any hash hits, and then it does not matter much how erroneous it is what you do on a hash hit.

[Fguy64]

If you fix the ply at 3, you will not have any transspositions. They require at least 4 ply. So you won't have any hash hits, and then it does not matter much how erroneous it is what you do on a hash hit.

Well, my observations do not bear that out. I think maybe there is an issue about semantics and numbering conventions here. As I see it, 1.e4 whatever 2.d4 and 1.d4 whatever 2.e4 happens in 3-ply, and is a transposition.

This issue about ply count a problem I've run into before when discussing with others. I eventually decided to go with what is intuitive with me. Even though I have long suspected my conventions were non-standard.

regards.

[Fguy64]

Ok, another question...

in Bruce Moreland's pseudo code found here http://web.archive.org/web/200404200216 ... ashing.htm

we see the following code block for the alphaBeta stop condition.

Code: Select all

if (depth == 0) {
	val = Evaluate();
	RecordHash(depth, val, hashfEXACT);
	return val;
}

what is not clear to me is what should happen to the hash type when qSearch is called instead of evaluate(). Should it still be an "exact" hash entry?

[hgm]

In general, it should not. Scores from searching a move are only exact if they ly between alpha and beta. So the standard way of handling this is to err on the safe side, and consider all other scores bounds.

Of course there is something illogical there: suppose you have a QS node where you have a few captures, and an eval that is not above beta. So you don't have a stand-pat cutoff, and you are going to search the captures. Suppose the bounds returned by these searches proves they are all below Eval. Together that would prove that the score of the current node must be Eval, and thus exact.

So scores based on Eval start out exact, and stay exact as long as you search moves that can be proven to have upper-bound score below it. But it becomes a lower bound as soon as you decide to return the score without having searched all moves (captures). If you have searched all captures, and some of them have a score higher than Eval, the core would still be exact if the highet scoring move had an exact score.

E.g., you could have eval < alpha, so you cannot stand pat and are going to search move, and now it turns out you can capture a hanging Pawn, and that raises your score above alpha, while the opponent cannot capture anything back. So the score of your capture is based on Eval() after the capture, and thus exact. (Although it might have been above beta.) If you had more captures, this exact score would only be a lower bound for the current node, because one of these other captures could be better. (And you are not going to search them, as you already acheived a cutoff.) But if it was your only possible capture, the score would be exact.

But you can only know that if you let the search not only return the sscore, but also explicit information on the bound type (that usually is only stored in the hash table). Because otherwise, you would see a score above beta, and have no clue that in this case it was an exact score. You would think it was a lower bound.

No one I know bother to do this.

[Fguy64]

Thanks HG, I'll take some time to let this sink in. In the mean time it has occurred to me, can we not answer the question this way...

Even though the score returned from qSearch might not be exact in the strictest sense of the word, it seems to me that it must be at least "as good" (as accurate) as the score that would have been returned from evaluate(). Agreed? So that while automatically treating the score as exact when it isn't might not be optimal, it is certainly better than treating it as exact when it is, i.e. when a qSearch has not been done.

[hgm]

It can be about a Queen off. If that is accurate enough for you to label it as exact...

[Fguy64]

ok on to a slightly different question. When is a hash write an alpha write?

As I see it there are three places where there is a hash write,

1. After the call to q (evaluate() ) there is an exact write.
2. after a beta cutoff there is a beta write
3. At the end of alphaBeta, when alpha is returned. If there has been an alpha update then this write must be an exact write. In Moreland's pseudo code an alphaUpdate is accompanied by hashf = hashfEXACT;

So there is only an alpha write when there is no alpha update? And no alpha update means no best move? My brain starts to hurt when I contemplate that possibility.

[Aaron Becker]

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.