Hash Collision?

[hgm]

Well, if mate scores are not being stored, storing wrong mate scores can obviously not be the cause of the error. It is just another design flaw.

I guess there is nothing left then but finally trying to do something about it, rather than beating around the bush. Print the moves+scores after 1.Bd6+ Bxd6.

[Fguy64]

Well, if mate scores are not being stored, storing wrong mate scores can obviously not be the cause of the error. It is just another design flaw.

I guess there is nothing left then but finally trying to do something about it, rather than beating around the bush. Print the moves+scores after 1.Bd6+ Bxd6.

huh?!?

listen, I appreciate your effort, but frankly It's not worth it to me. I think I can live with what I have. An incorrect mate score in maybe 1/10 of one percent of forced mate positions is something I can live with, especially when most of those searches still return the correct move. Cause that's all that I have noticed.

I'll be watching my test results closely, any increase in problems will not go unnoticed.

Thanks again I'm gonna move on to more productive areas.

[jwes]

Well, the most likely explanation then is that you do not properly correct the hash mate scores during storing and probing. I don't suppose you use a delayed-loss bonus, so to get any measurement of the mate distance, you would have to use this silly method of fudging the mate scores with the current depth, which again requires you tocorrect them if probing takes place at a different depth than storing. This is notoriously error prone, and probably also the problem here.

hmm, I make no special consideration for mate scores.

The hash type is initialized to typeAlpha at the beginning of the search function, then change to typeExact when there is an alpha update. At the end of the search function hval=alpha is written along with the type. Beta writes store hval = beta.

My hash probe is the first thing that happens at each node, before the termination condition (depth==0).

I'll have a look around for information on hashing and mate scores. Usually I use Moreland's pages, I'll try there first.

p.s. oooh, mate scores aren't being stored...

The difference with mate scores in the TT is that they need to be adjusted as they move up the tree, e.g. if the TT has a cutoff with mate in 3 ply, the search needs to return -mate in 4 ply.

[tvrzsky]

Hi Fred,
do not give up!
I believe that your bug (as has been pointed out by HGM) lies in handling mat scores in your hash table (TT). You have to realize that mat score is something very different from ordinary (material + position evaluation) score. It reflects distance from the root to the given checkmate position and in this form it works perfect with plain AlfaBeta without TT. But it does not work with TT. Why? Because when storing mat score then what you in fact need to store is not distance from the root but from your ACTUALL POSITION WHICH ARE YOU STORING to the position of checkmate. Consequently you have to adjust every mat score before storing to TT like this:
a) if the score is positive than add your current ply to it
b) if the score is negative than subtract your current ply from it
After retrieving mat score from the TT adjust it like this:
a) if the score is positive than subtract your current ply from it
b) if the score is negative than add your current ply to it.
Please note that the fact that you do not store checkmate position to the TT does not mean that you do not store mat scores. Of course you store them in parents of this checkmate node.
I think that storing mat scores without adjusting explains perfectly behaviour of your engine. The fact that it finds mat in 5 plies within the 4 plies search in itself is not a bug but a feature , yes, it is well known feature of TT which manifests e. g. in pawn hash tables as well (Fine 70) and which consists in enhancement of your search depth beyond nominal depth. As explained by HGM your engine probably searched at first line 1. a7a8Q Bb8 2. Qxb8++. Position after 1. a7a8Q Bb8 got stored (but with incorrect unadjusted score 9997). Now after 1. Bd6+ Bxd6 2. a7a8Q+ Bb8 this position ocurred again and you retrieved the incorrect score 9997.
So only wrong thing here are incorrect mat scores. And this phenomenon of course can not manifest if you retrieves scores from TT only with condition stored depth == current depth because then distance to checkmate from the root and from the actuall position is the same both when storing and when retrieving from TT.

[Fguy64]

Thanks Filip, I don't think I can absorb your post tonight, but tomorrow when I am fresher I will look at it closely.

I will respond to JW point though. If I am just doing transpositions, and there is a cutoff from a previous write, but I need the extra ply to know it is the mating position because I needed another ply to determine there is no legal responses, then the question becomes how am I supposed to know it is a mate if the cutoff prevents me from determining that there are no legal responses?

I am tired and none too certain, but my gut is telling me not to waste too much time with mate scores and hashing in my current fixed depth version of the algorithm, that once I add in iterative deepening along with a qSearch with a check extension might make the problem disappear? Just a guess.

[tvrzsky]

Thanks Filip, I don't think I can absorb your post tonight, but tomorrow when I am fresher I will look at it closely.

Good idea indeed, I slept only about 3 hours the last night myself and now it is here almost half past two AM ...

I will respond to JW point though. If I am just doing transpositions, and there is a cutoff from a previous write, but I need the extra ply to know it is the mating position because I needed another ply to determine there is no legal responses, then the question becomes how am I supposed to know it is a mate if the cutoff prevents me from determining that there are no legal responses?

I think that you are both talking different things. I guess that JW just tried to suggest you to use another functional scheme of handling mat scores.
It works like this:
a) when in checkmate then return constant score (for instance -10000) WITHOUT adding of current ply
b) then whenever you get mat score from child node subtract 1 from it
c) you do not need to adjust scores when storing to and retrieving from TT.
Regarding your question, it seems to me that you are seeking for problems where there are not any. Was the position checkmate before storing to TT? Is it the same position now? Then it is checkmate again, period.
Or did I misunderstand you?

I am tired and none too certain, but my gut is telling me not to waste too much time with mate scores and hashing in my current fixed depth version of the algorithm, that once I add in iterative deepening along with a qSearch with a check extension might make the problem disappear? Just a guess.

I can assure you that it is better to fix those bugs now. Surely they are not going to disappear by any magic.

[Fguy64]

I am tired and none too certain, but my gut is telling me not to waste too much time with mate scores and hashing in my current fixed depth version of the algorithm, that once I add in iterative deepening along with a qSearch with a check extension might make the problem disappear? Just a guess.

I can assure you that it is better to fix those bugs now. Surely they are not going to disappear by any magic.[/quote]

Oh, I understand that philosophy all to well. If my idea doesn't work, it wouldn't be the first time. well it's no loss, I'll just go back and try something different. Anyways, g'night.

[tvrzsky]

Please, correct all "mat" to "mate". My poor english ...

Hi Fred,
do not give up!
I believe that your bug (as has been pointed out by HGM) lies in handling mat scores in your hash table (TT). You have to realize that mat score is something very different from ordinary (material + position evaluation) score. It reflects distance from the root to the given checkmate position and in this form it works perfect with plain AlfaBeta without TT. But it does not work with TT. Why? Because when storing mat score then what you in fact need to store is not distance from the root but from your ACTUALL POSITION WHICH ARE YOU STORING to the position of checkmate. Consequently you have to adjust every mat score before storing to TT like this:
a) if the score is positive than add your current ply to it
b) if the score is negative than subtract your current ply from it
After retrieving mat score from the TT adjust it like this:
a) if the score is positive than subtract your current ply from it
b) if the score is negative than add your current ply to it.
Please note that the fact that you do not store checkmate position to the TT does not mean that you do not store mat scores. Of course you store them in parents of this checkmate node.
I think that storing mat scores without adjusting explains perfectly behaviour of your engine. The fact that it finds mat in 5 plies within the 4 plies search in itself is not a bug but a feature , yes, it is well known feature of TT which manifests e. g. in pawn hash tables

I meant pawn endings.

as well (Fine 70) and which consists in enhancement of your search depth beyond nominal depth. As explained by HGM your engine probably searched at first line 1. a7a8Q Bb8 2. Qxb8++. Position after 1. a7a8Q Bb8 got stored (but with incorrect unadjusted score 9997). Now after 1. Bd6+ Bxd6 2. a7a8Q+ Bb8 this position ocurred again and you retrieved the incorrect score 9997.
So only wrong thing here are incorrect mat scores. And this phenomenon of course can not manifest if you retrieves scores from TT only with condition stored depth == current depth because then distance to checkmate from the root and from the actuall position is the same both when storing and when retrieving from TT.

[Sven]

You have written that you do not store mate scores in the TT. Others have written that they think your bug may be related to handling of mate scores in the TT. You did not reply to them that this were impossible because you don't store mate scores.

So what do you really do: Do you store mate scores, or don't you?

If you do then a second question is how to do it. There were some comments and suggestions about it. I'll come back to it further down.

If you say you don't then this would mean that you explicitly prevent mate scores from being stored in the TT, by something like this:

Code: Select all

if (score > -(10000-MAX_PLY) && score < 10000-MAX_PLY) store_in_TT(score, valueType, ...);

My guess is that you don't do it like this, i.e. your TT does also contain entries for positions where you have detected mate, either a mate in the current position or a forced mate coming back from a subtree search.


Now how to store mate scores? A couple of choices exist.


1) Bruce Moreland's pages give a simple advice. You can store a positive mate score (moving side can mate his opponent in N plies) as a lower bound, like "at least +9000" (if 10000 is your MaxValue), and a negative mate score (moving side is being mated in N plies) as an upper bound, like "at most -9000".

This is a possible way to go. You get enough cutoffs, and you still get the correct "minimax value" returned by your root search even in case of a mate if there are no other bugs around in the search code. It is just not very accurate, and it can slow down finding deep mates. But it is o.k. to start this way, and should not suffer from the problems you are describing here.


2) HGM suggests to use his own proposal which he calls delayed-loss bonus. I cannot say much about it, and don't want to discuss it here (has been discussed several times in CCC), I just say that it is one way to do it. I would classify it as an "advanced" technique, and I really do not know how many authors have detailled knowledge about it and/or use it in their engines. It may indeed be a good choice, I can't tell at the moment.


3) There is one very "popular" technique, however, which has also been mentioned by some posters in this thread. This technique has two major components:
a) adjust mate scores before storing them in TT to reflect the distance to mate relative to the current node, not to the root node;
b) readjust mate scores to "relative to root" viewpoint after retrieving them from TT.

To understand this technique consider the following, "very silly" example.
[d]7k/4Q3/8/5K2/8/8/8/8 w - - 0 1
White mates in 3 plies with 1.Kg6 Kg8 and then for instance 2.Qg7#. But your search *may* also include the sub-optimal path 1.Kg4 (??!) Kg8 2.Kg5 Kh8 3.Kg6 leading to a transposition. So what happens during search?

Let's assume the sub-optimal path gets searched first, since we are not talking about move ordering or strong search in general here but *only* about handling of mate scores for the TT. After 1.Kg4 Kg8 2.Kg5 Kh8 3.Kg6 Kg8 4.Qg7# there is a mate at a distance of 7 plies from root, so you return -(10000-7) from black viewpoint who is now mated. Let's ignore the possibility that you might also store this "mated" value somehow in the TT, and let's proceed upwards in the tree.

At the parent node (after 3...Kg8), let's call this situation X, White has a forced mate in 1 ply with Qg7# which is clearly >= beta. The search returns +(10000-7). But before returning, you want to store that score in the TT. Let's say you do it wrong and store +(10000-7), and let's see what happens later on.

More search happens, and at some point you return to the root from the subtree of 1.Kg4 with the value +(10000-7) for White, telling that 1.Kg4 mates in 7 plies. Alpha gets set to this value, narrowing the window for all subsequent searches. (The real problem is indeed independent from alpha/beta, it would also occur with Minimax + TT. I mention alpha just for completeness.)

As next move you happen to search 1.Kg6 with the forced black reply Kg8. Let's call this situation Y. You look up the TT and find an exact value of +(10000-7) which you retrieve unmodified. You return this value to the parent node but there you get a beta cutoff (window had been narrowed), and therefore at root 1.Kg6 does not improve over 1.Kg4.

Why? But 1.Kg6 is much better??

By storing +(10000-7) in situation X and retrieving the same value at situation Y you miss the fact that at X it was a mate in 1 ply at a root distance of 6 while the same position in situation Y was a mate in 1 ply at a root distance of only 2, leading to a shorter mate.

So the "popular" way is to store an adjusted value +(10000-(7-6)) = "mate in 1 ply" at X and retrieve it at Y as "mate in 1 ply", too, but readjust to the current root distance as +(10000-(7-6)-2) so that it becomes a mate in 3 plies from the root. You can figure out yourself how to implement this properly. Both the adjustment and readjustment must be restricted to mate scores only.

That's nearly all about it, the final details come when implementing it.


Now I hope that there are enough choices for you

Sven

[Fguy64]

You have written that you do not store mate scores in the TT. Others have written that they think your bug may be related to handling of mate scores in the TT. You did not reply to them that this were impossible because you don't store mate scores.

So what do you really do: Do you store mate scores, or don't you?
...

I didn't reply that it was "impossible that the handling of mate scores in hash was the problem because I wasn't storing them" because my initial reaction was that the fact that I wasn't storing them was the problem. This morning I am not so sure what the problem is. Maybe it is not mate scores at all.

My code that shows the relationship between mate scores and the hash write was posted yesterday on the previous page. It shows clearly that the code that returns a mate/stalemate score from search comes before, and is independant of, the hash write at the end of alphaBeta. My initial attempts to store mate scores were unsuccessful.

Anyways, I appreciate the effort people make, but this thread has gone in a direction I never really intended. It started off with a question to Bob about what he meant by, and I paraphrase "I can't tell you how many times I'be tried to debug the problem, only to realise that it isn't a problem" I think, but I am not certain that he was referring to grafting, and at that time I was trying to ascertain whether his remark was relevant to the problem I was having, I thought it might be because my remarks clearly showed that while an incorrect score was being reported (a mate in 2 score instead of a mate in three score), the correct move was being played.

Anyways, with these remarks I am not trying to make a case, nor am I looking for validation, just trying to explain where I was coming from when this all started up again yesterday.

Finally, thanks Sven for the simple example, and everyone else for the help, I'll be reviewing that info today, I'll report back with the results.