I see various programs handle mate and stalemate scores differently. Specifically, I am talk about when a program at a node finds no available move. If it is in check, it is scored as a mate. Otherwise, it is scored as a stalemate. Many programs I have looked at just return at this point, and do not store the mate/stalemate results. It would seem to me that storing them would save time, since it would allow the search to not evaluate or try to generate moves when the same position is encountered. And the position could be stored as an infinite depth one, sinc ethis is an exact score not requiring more search.
Has anyone experimented with this (storing mate/stalemate and assigning it a big depth value)?
I also have noted many programs do not store null move search values. For these, we can assign a depth of at least R+1.
Mark
Immediate mate and stalemate trans table storage
Moderators: hgm, Rebel, chrisw
-
mjlef
- Posts: 1494
- Joined: Thu Mar 30, 2006 2:08 pm
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Immediate mate and stalemate trans table storage
I always store mate scores. But I don't store them with artificial depth, because I am not sure that is the shortest possible mate from that position... I also always store stalemate scores and any other score I encounter during a normal search.mjlef wrote:I see various programs handle mate and stalemate scores differently. Specifically, I am talk about when a program at a node finds no available move. If it is in check, it is scored as a mate. Otherwise, it is scored as a stalemate. Many programs I have looked at just return at this point, and do not store the mate/stalemate results. It would seem to me that storing them would save time, since it would allow the search to not evaluate or try to generate moves when the same position is encountered. And the position could be stored as an infinite depth one, sinc ethis is an exact score not requiring more search.
Has anyone experimented with this (storing mate/stalemate and assigning it a big depth value)?
I also have noted many programs do not store null move search values. For these, we can assign a depth of at least R+1.
Mark
-
MattieShoes
- Posts: 718
- Joined: Fri Mar 20, 2009 8:59 pm
Re: Immediate mate and stalemate trans table storage
Mine doesn't store the actual mate position though there's no reason it couldn't. I think it's not a timesaver that you think though, and in fact may lose time.
A hash entry saves time needed to calculate a node's value, but in the case of a mate position, the time needed to calculate the exact value is tiny (just prove all pseudo-legal moves are illegal in the case of non-legal-move-generators). Now if you're storing these in your hash table, you might be saving a tiny bit of time when it encounters the mate position. But since the mate-in-1 position is in hash, it probably won't need to revisit the mate position too often. But that mate position occupies the same hash slot as about a trillion other positions, perhaps one or two of those others might even be encountered in your search. And those other, non-mate ones would require far more time to calculate a score.
So probably nothing wrong with storing mate positions IF you give precedence to any node that's not a mate-in-zero.
Hmm, I wonder if storing mate in small-number scores is all that valuable relative to non-mate scores in general...
A hash entry saves time needed to calculate a node's value, but in the case of a mate position, the time needed to calculate the exact value is tiny (just prove all pseudo-legal moves are illegal in the case of non-legal-move-generators). Now if you're storing these in your hash table, you might be saving a tiny bit of time when it encounters the mate position. But since the mate-in-1 position is in hash, it probably won't need to revisit the mate position too often. But that mate position occupies the same hash slot as about a trillion other positions, perhaps one or two of those others might even be encountered in your search. And those other, non-mate ones would require far more time to calculate a score.
So probably nothing wrong with storing mate positions IF you give precedence to any node that's not a mate-in-zero.
Hmm, I wonder if storing mate in small-number scores is all that valuable relative to non-mate scores in general...
-
mjlef
- Posts: 1494
- Joined: Thu Mar 30, 2006 2:08 pm
Re: Immediate mate and stalemate trans table storage
I am only suggesting storing the immediate mate (I guess you would call it mate in zero) which would always be accurate. The time saved would be the time it takes to generate and test pseudo legal moves, only to find all of them are illegal.bob wrote:I always store mate scores. But I don't store them with artificial depth, because I am not sure that is the shortest possible mate from that position... I also always store stalemate scores and any other score I encounter during a normal search.mjlef wrote:I see various programs handle mate and stalemate scores differently. Specifically, I am talk about when a program at a node finds no available move. If it is in check, it is scored as a mate. Otherwise, it is scored as a stalemate. Many programs I have looked at just return at this point, and do not store the mate/stalemate results. It would seem to me that storing them would save time, since it would allow the search to not evaluate or try to generate moves when the same position is encountered. And the position could be stored as an infinite depth one, sinc ethis is an exact score not requiring more search.
Has anyone experimented with this (storing mate/stalemate and assigning it a big depth value)?
I also have noted many programs do not store null move search values. For these, we can assign a depth of at least R+1.
Mark
-
hgm
- Posts: 27794
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Immediate mate and stalemate trans table storage
I always store all mates. I don't think the probability to re-encounter the mate is any bigger or less than re-encounter any other position (through transposition or in a following ID or IID iteration). The time to judge the mate is not less than the time it takes to judge many other leaves (e.g. where all captures are futile or bad), and I also store those.
You have to be careful with a depth-preferred table, though. Mate and stalemate scores are valid to infinite depth, when making hash cutoffs. But storing them in the table as infinite depth will lead to the depth-preferred part of the table becoming entirely filled with mates. So the decision to replace should be done based on the actual distance to the mate (which represents the work to find it by searching from scratch). If you don't have the possibility to make that distinction it is better to store the mate positions as if they have the depth (draft) at which they were actually uncovered, even if that means that you might miss a few hash cutoffs on them later.
This also holds for deeper mates; as soon as the search depth is such that it guarantees no faster mate exists, you can bump the 'validity depth' of the mate score to infinity, but you should not let your replacement algorithm be confused by that. The most efficient way to implement this is checking it when you get the hash hit on an entry with a mate-score range. From the mate score you can then see how distant the mate was, compare that to the entries draft, and if the mate was well within the horizon, treat the draft as if it were infinite for the decision of making the hash cutoff. This would then be rarely executed code, reduced to an if statement and a correctly predicted branch in insufficient-depth hash hits without mate score, and none at all in sufficient depth hash hits or hash misses.
You have to be careful with a depth-preferred table, though. Mate and stalemate scores are valid to infinite depth, when making hash cutoffs. But storing them in the table as infinite depth will lead to the depth-preferred part of the table becoming entirely filled with mates. So the decision to replace should be done based on the actual distance to the mate (which represents the work to find it by searching from scratch). If you don't have the possibility to make that distinction it is better to store the mate positions as if they have the depth (draft) at which they were actually uncovered, even if that means that you might miss a few hash cutoffs on them later.
This also holds for deeper mates; as soon as the search depth is such that it guarantees no faster mate exists, you can bump the 'validity depth' of the mate score to infinity, but you should not let your replacement algorithm be confused by that. The most efficient way to implement this is checking it when you get the hash hit on an entry with a mate-score range. From the mate score you can then see how distant the mate was, compare that to the entries draft, and if the mate was well within the horizon, treat the draft as if it were infinite for the decision of making the hash cutoff. This would then be rarely executed code, reduced to an if statement and a correctly predicted branch in insufficient-depth hash hits without mate score, and none at all in sufficient depth hash hits or hash misses.