Win scores in the TT causing problems

[wgarvin]

The "when to terminate" is easy. If you find a mate in N, and you keep searching until you complete iteration 2N-1, there can't possibly be a shorter mate. I prefer my other solution as it is pointless to keep searching after you find a mate, just in the hope that you can find a shorter one.

I see there has been some interesting discussion around this point. I think in a tournament there is an argument for not wasting clock time at the expense of risking the game, but for a recreational program I think it makes sense to find the shortest win and the longest loss.

Another approach is to simply stop when you find the first mate, and make the move. But on the next move, you must search until you find a mate in N-1 so that you "make progress" rather than checking yourself into a repetition.

This makes alot of sense to me and is the direction I will likely pursue.

Note that I am assuming that you are correcting the mate scores before you store them so that they represent "mate in N moves from this ply" rather than "mate in X from the root ply". You also have to "uncorrect" them when you do a probe and get a hit.

Yes, I am doing all that, storing the win in the TT relative to the position, not the ply, and adjusting accordingly when removing from the TT.

On a slightly different note, I noticed that my implementation eval's all terminal nodes (probably because I based my implementation off of some pseudo-code which did the same). Is there any reason not to check the TT for an exact value of the position and use that instead for terminal nodes.

Hashing in the q-search has two sides.

1. If you do this, you have to both store and probe at every q-search node. This will overwrite cache significantly since something on the order of 90% of the total nodes searched are in the q-search. This burns memory bandwidth as well. And since the hash table is of finite size, it is going to end up filled with lots of zero-draft entries. In my tests, this will reduce the size of the tree by about 10% over a program that does not hash in the q-search.

2. If you do not hash in the q-search, you use much less memory bandwidth, strain the cache less, and you can run with a much smaller hash table since you will be storing far fewer positions than the q-search hasher. In my test, this is about 10% _faster_.

Bottom line is that it is close to a "wash". One will be faster but search a larger tree. The other will be slower but search a smaller tree. I chose to go faster with smaller hash.

You can probe in the q-search without storing but that is a loser overall as you waste time probing positions that were never stored, resulting in misses.

It probably used to make more sense 10 years ago, than it does now. Especially if you had an engine that did a lot of calculation for every node. Today's CPUs are incredibly fast and can execute hundreds of instructions in the time it takes to bring one cache line in from RAM for the hash probe. And being able to run efficiently with a smaller hash table would be handy, for underpowered machines (like my faithful old XP laptop that has only 256 MB of RAM).

[jwes]

The "when to terminate" is easy. If you find a mate in N, and you keep searching until you complete iteration 2N-1, there can't possibly be a shorter mate. I prefer my other solution as it is pointless to keep searching after you find a mate, just in the hope that you can find a shorter one.

I see there has been some interesting discussion around this point. I think in a tournament there is an argument for not wasting clock time at the expense of risking the game, but for a recreational program I think it makes sense to find the shortest win and the longest loss.

Another approach is to simply stop when you find the first mate, and make the move. But on the next move, you must search until you find a mate in N-1 so that you "make progress" rather than checking yourself into a repetition.

This makes alot of sense to me and is the direction I will likely pursue.

Note that I am assuming that you are correcting the mate scores before you store them so that they represent "mate in N moves from this ply" rather than "mate in X from the root ply". You also have to "uncorrect" them when you do a probe and get a hit.

Yes, I am doing all that, storing the win in the TT relative to the position, not the ply, and adjusting accordingly when removing from the TT.

On a slightly different note, I noticed that my implementation eval's all terminal nodes (probably because I based my implementation off of some pseudo-code which did the same). Is there any reason not to check the TT for an exact value of the position and use that instead for terminal nodes.

Hashing in the q-search has two sides.

1. If you do this, you have to both store and probe at every q-search node. This will overwrite cache significantly since something on the order of 90% of the total nodes searched are in the q-search. This burns memory bandwidth as well. And since the hash table is of finite size, it is going to end up filled with lots of zero-draft entries. In my tests, this will reduce the size of the tree by about 10% over a program that does not hash in the q-search.

2. If you do not hash in the q-search, you use much less memory bandwidth, strain the cache less, and you can run with a much smaller hash table since you will be storing far fewer positions than the q-search hasher. In my test, this is about 10% _faster_.

Bottom line is that it is close to a "wash". One will be faster but search a larger tree. The other will be slower but search a smaller tree. I chose to go faster with smaller hash.

You can probe in the q-search without storing but that is a loser overall as you waste time probing positions that were never stored, resulting in misses.

It probably used to make more sense 10 years ago, than it does now. Especially if you had an engine that did a lot of calculation for every node. Today's CPUs are incredibly fast and can execute hundreds of instructions in the time it takes to bring one cache line in from RAM for the hash probe. And being able to run efficiently with a smaller hash table would be handy, for underpowered machines (like my faithful old XP laptop that has only 256 MB of RAM).

I tried running crafty under AMD's CodeAnalyst and it claimed that crafty spent almost 5% of its time on the single line that read a TT entry.

[gschmidt]

Today's CPUs are incredibly fast and can execute hundreds of instructions in the time it takes to bring one cache line in from RAM for the hash probe.

The goal of probing at the horizon is not just to save eval time, but also to obtain an improved score since the position might be a transposition searched to some depth.

As far as minimal mate detection, I'm leaning towards one of the following approaches:

1) If a mate in N has been seen on a previous search, don't terminate the search until we've searched to a sufficent depth to find mate in N-2.

2) Once a mate has been returned by a search, clear out any mate scores in the TT after each subsequent search.

Both are fairly easy to do. #1 seems a bit more elegant since it involves no loss of information. I tried #2 (even easier than #1) and it seems to work fine. Thoughts?

-- Greg

[xsadar]

Today's CPUs are incredibly fast and can execute hundreds of instructions in the time it takes to bring one cache line in from RAM for the hash probe.

The goal of probing at the horizon is not just to save eval time, but also to obtain an improved score since the position might be a transposition searched to some depth.

As far as minimal mate detection, I'm leaning towards one of the following approaches:

1) If a mate in N has been seen on a previous search, don't terminate the search until we've searched to a sufficent depth to find mate in N-2.

2) Once a mate has been returned by a search, clear out any mate scores in the TT after each subsequent search.

Both are fairly easy to do. #1 seems a bit more elegant since it involves no loss of information. I tried #2 (even easier than #1) and it seems to work fine. Thoughts?

-- Greg

I'm not understanding method #2. Why would you want to do that? What does it accomplish? It sounds to me like you're just throwing away the most useful information you have, and I don't see what it's even supposed to give you.

[gschmidt]

2) Once a mate has been returned by a search, clear out any mate scores in the TT after each subsequent search.

I'm not understanding method #2. Why would you want to do that? What does it accomplish? It sounds to me like you're just throwing away the most useful information you have, and I don't see what it's even supposed to give you.

The goal is to terminate the search once a mate is found. This is desirable for at least the following reasons.
1) The program responds quicker when there is an obvious mate and therefore does not appear "dumb".
2) When setting the thinking time to "forever", the program will terminate when a mate is seen as opposed to stopping when it has exhaustively searched all paths (which could take a very long time).
3) During self play, the program should not oscillate between "Mate in 10", "Mate in 12", "Mate in 11", "Mate in 12" etc...
Note, my program is for recreational, not tournament play.

My program will terminate an iterative deepening search when it sees a mate. Since the program currently performs a full width search to a fixed depth, the first time it sees a mate, it will be minimal and the search will immediately terminate as expected. Call this "Mate in N"

The problem arises during the next search. Note I do not clear out the hash between moves. What can happen is that a shallow search finds a mate, but the mate is "Mate in N+d" where d is a number greater than 0. At shallow depths there is no guarantee of finding the "Mate in N" for a number of reasons such as the "optimal" hash entries happened to be overwritten. So we see the mate in N+d, report it and thereby oscillate.

One way to overcome this is via #1. If we know that we can mate in N on the last move, then we should search to at least N-2 the next time around.

#2 just sidesteps the problem by effectively saying "mate entries in the hash cause problems, so remove them". Admittedly, not the best solution (brute force), but it does work. Also, since the trees are smaller at the end game, ignoring them may not have much impact. I do agree with yout that it is better not to throw away information if that can be avoided.

-- Greg

[bob]

2) Once a mate has been returned by a search, clear out any mate scores in the TT after each subsequent search.

I'm not understanding method #2. Why would you want to do that? What does it accomplish? It sounds to me like you're just throwing away the most useful information you have, and I don't see what it's even supposed to give you.

The goal is to terminate the search once a mate is found. This is desirable for at least the following reasons.
1) The program responds quicker when there is an obvious mate and therefore does not appear "dumb".
2) When setting the thinking time to "forever", the program will terminate when a mate is seen as opposed to stopping when it has exhaustively searched all paths (which could take a very long time).
3) During self play, the program should not oscillate between "Mate in 10", "Mate in 12", "Mate in 11", "Mate in 12" etc...
Note, my program is for recreational, not tournament play.

My program will terminate an iterative deepening search when it sees a mate. Since the program currently performs a full width search to a fixed depth, the first time it sees a mate, it will be minimal and the search will immediately terminate as expected. Call this "Mate in N"

The problem arises during the next search. Note I do not clear out the hash between moves. What can happen is that a shallow search finds a mate, but the mate is "Mate in N+d" where d is a number greater than 0. At shallow depths there is no guarantee of finding the "Mate in N" for a number of reasons such as the "optimal" hash entries happened to be overwritten. So we see the mate in N+d, report it and thereby oscillate.

One way to overcome this is via #1. If we know that we can mate in N on the last move, then we should search to at least N-2 the next time around.

#2 just sidesteps the problem by effectively saying "mate entries in the hash cause problems, so remove them". Admittedly, not the best solution (brute force), but it does work. Also, since the trees are smaller at the end game, ignoring them may not have much impact. I do agree with yout that it is better not to throw away information if that can be avoided.

-- Greg

Clearing out the hash table mate scores is not the way to deal with this. All you need to do is when you find a mate, stop the search, and play the move. Then you start the next search and continue until you find a mate in N-1 (where the first mate was a mate in N). You do this for each succeeding search. Once you find a mate in N-1, stop the search, make the move, and then start again, making sure you don't stop until you reduce the mate distance by one each time.

Clearing mate scores from the hash table is just a kludge to try to work around the stored mate scores. If you continue searching, the scores will become unusable also, since the at some iteration, the draft on old entries will no longer be deep enough for the score or bound to be used...

[gschmidt]

Clearing out the hash table mate scores is not the way to deal with this. All you need to do is when you find a mate, stop the search, and play the move. Then you start the next search and continue until you find a mate in N-1 (where the first mate was a mate in N). You do this for each succeeding search. Once you find a mate in N-1, stop the search, make the move, and then start again, making sure you don't stop until you reduce the mate distance by one each time.

I agree that clearing out mate scores is a kludge. It was a quick test though that helped confirm the problem.

Not to be picky, but wouldn't that be N-2 due to the fact that the opponent moved since the last search?

-- Greg

[gschmidt]

Then you start the next search and continue until you find a mate in N-1 (where the first mate was a mate in N).

Keeping in mind that if any "unsafe" pruning occurs, there's a possibility you may never find the subsequent mate in N-1, correct? In that case, we'll rely on our depth limit to exit. It should be a pathological case, but my point is that we should still be tolerant of not finding N-1.

-- Greg

[bob]

Clearing out the hash table mate scores is not the way to deal with this. All you need to do is when you find a mate, stop the search, and play the move. Then you start the next search and continue until you find a mate in N-1 (where the first mate was a mate in N). You do this for each succeeding search. Once you find a mate in N-1, stop the search, make the move, and then start again, making sure you don't stop until you reduce the mate distance by one each time.

I agree that clearing out mate scores is a kludge. It was a quick test though that helped confirm the problem.

Not to be picky, but wouldn't that be N-2 due to the fact that the opponent moved since the last search?

-- Greg

If you are talking about minimax score, N-2 is correct. I announce mates as "mate in 10 moves", on the next turn it should be mate in 9 moves. Hence the -1.

[bob]

Then you start the next search and continue until you find a mate in N-1 (where the first mate was a mate in N).

Keeping in mind that if any "unsafe" pruning occurs, there's a possibility you may never find the subsequent mate in N-1, correct? In that case, we'll rely on our depth limit to exit. It should be a pathological case, but my point is that we should still be tolerant of not finding N-1.

-- Greg

I'm not sure how this would happen, assuming uniform timing. I've never seen a case where the mate in N-1 was not found, but I suppose it could if there are deep quiet moves. This is pretty rare in that many of the moves are checks, and the rest should be in the PV which means the primary path would not be reduced since those moves occur early in the move lists...