I have an issue that I am not sure about how to solve relating to transposition tables and mates. My engine now correctly find mates, without the TT tables enabled, but there is anomaly that I am seeing when I enable them.
I am using iterative deepening, and after each iteration I clean the table, things seem to work well, and I can find the mate in the position I am testing. If I don't clean the table after each depth, I run into the situation where my engine doesn't pick the best mate score.
A mate score in my engine is 10000 - the currentdepth + 1. Inside of my deepening loop, I check to see if I found a mate at that depth as the best score, and if so I cutoff early. With the TT enabled, I run into an issue where I don't cutoff because the score being returned is no longer correct after a move is made. I don't believe there is any issue with my TT logic, for storing and retrieving values. I'm using the negamax implementation from wikipedia.
I think I should be able to fix it so I don't have to clear the TT after each iteration, but I am not sure what fix I need to apply to my mate check.[/code]
Issue with Mating And Transposition Tables
Moderators: hgm, Rebel, chrisw
-
Stan Arts
- Posts: 179
- Joined: Fri Feb 14, 2014 10:53 pm
- Location: the Netherlands
Re: Issue with Mating And Transposition Tables
Hi there,
Store the mate as distance from the current node rather than distance from the root.
Then when you retrieve add the (possibly different) distance from the root to the current node again.
Store the mate as distance from the current node rather than distance from the root.
Then when you retrieve add the (possibly different) distance from the root to the current node again.
-
Sven
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Issue with Mating And Transposition Tables
Hi Aaron,
at a node X where you detect the mate it is always the moving side that has just been mated. So the score would be -(MATE_SCORE - distanceOfNodeXToRoot) in your case, where you seem to be using MATE_SCORE = 10001 (but the actual value of MATE_SCORE does not matter much as long as you always use the same value for it and it is bigger than the biggest possible score that may result from your static evaluation function). Backing up this mate score towards the root always keeps the score fully intact whenever the mate is actually forced, apart from the sign which changes with the active color. This is the easy part with no TT involved.
Now as soon as the TT comes into play you want to deal correctly with transpositions. There is one very common way to do so, although there are people who do it differently (and still do it right of course). Let's say in the example above distanceOfNodeXToRoot was 7, and you back up the mate score -(MATE_SCORE - 7) to the parent node Y1 where the score becomes +(MATE_SCORE - 7). It means: at node Y1 the moving side can mate the opponent in 1 ply. Y1 is 6 plies from the root ("height = 6"), so you store the score +(MATE_SCORE - 7 + 6) in the TT for node Y1. In general a positive (winning) mate score is stored as score+height and a negative (losing) mate score as score-height, so in both cases the height is "removed" from the score and makes the score relative to the current node.
Retrieving this score at a node Y2 which is identical to Y1 but appears on a different path (say, at ply 4 instead of ply 6) goes the other way round: you retrieve a positive mate score as score-height and a negative mate score as score+height. In both cases you "insert" the height and make the score relative to the root again, but now you are using the current height, so an "I can mate in 1 ply" score now reads "I can enforce a mate that is 4+1 plies from root". Backing this up to the root would finally lead to preferring the second path through Y2 which enforces the mate faster than through Y1.
This is essentially the same as Stan's reply, only with N^2 words
Sven
at a node X where you detect the mate it is always the moving side that has just been mated. So the score would be -(MATE_SCORE - distanceOfNodeXToRoot) in your case, where you seem to be using MATE_SCORE = 10001 (but the actual value of MATE_SCORE does not matter much as long as you always use the same value for it and it is bigger than the biggest possible score that may result from your static evaluation function). Backing up this mate score towards the root always keeps the score fully intact whenever the mate is actually forced, apart from the sign which changes with the active color. This is the easy part with no TT involved.
Now as soon as the TT comes into play you want to deal correctly with transpositions. There is one very common way to do so, although there are people who do it differently (and still do it right of course). Let's say in the example above distanceOfNodeXToRoot was 7, and you back up the mate score -(MATE_SCORE - 7) to the parent node Y1 where the score becomes +(MATE_SCORE - 7). It means: at node Y1 the moving side can mate the opponent in 1 ply. Y1 is 6 plies from the root ("height = 6"), so you store the score +(MATE_SCORE - 7 + 6) in the TT for node Y1. In general a positive (winning) mate score is stored as score+height and a negative (losing) mate score as score-height, so in both cases the height is "removed" from the score and makes the score relative to the current node.
Retrieving this score at a node Y2 which is identical to Y1 but appears on a different path (say, at ply 4 instead of ply 6) goes the other way round: you retrieve a positive mate score as score-height and a negative mate score as score+height. In both cases you "insert" the height and make the score relative to the root again, but now you are using the current height, so an "I can mate in 1 ply" score now reads "I can enforce a mate that is 4+1 plies from root". Backing this up to the root would finally lead to preferring the second path through Y2 which enforces the mate faster than through Y1.
This is essentially the same as Stan's reply, only with N^2 words
Sven
-
aaronmell
- Posts: 14
- Joined: Sat Aug 30, 2014 2:32 am
Re: Issue with Mating And Transposition Tables
Thanks for the responses, I'll give it a try and see if that doesn't fix my issue.
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Issue with Mating And Transposition Tables
Are you adjusting the mate scores as you store them in the TT? A mate is really a "mate in N plies from THIS position". SO when you store the position, you need to adjust the score so that it is mate in N plies from this position, not mate in N plies from the root. Then when you get a tt hit, you need to adjust it again so that rather than mate in N from this position, it becomes (again) mate in N from the root.aaronmell wrote:I have an issue that I am not sure about how to solve relating to transposition tables and mates. My engine now correctly find mates, without the TT tables enabled, but there is anomaly that I am seeing when I enable them.
I am using iterative deepening, and after each iteration I clean the table, things seem to work well, and I can find the mate in the position I am testing. If I don't clean the table after each depth, I run into the situation where my engine doesn't pick the best mate score.
A mate score in my engine is 10000 - the currentdepth + 1. Inside of my deepening loop, I check to see if I found a mate at that depth as the best score, and if so I cutoff early. With the TT enabled, I run into an issue where I don't cutoff because the score being returned is no longer correct after a move is made. I don't believe there is any issue with my TT logic, for storing and retrieving values. I'm using the negamax implementation from wikipedia.
I think I should be able to fix it so I don't have to clear the TT after each iteration, but I am not sure what fix I need to apply to my mate check.[/code]