Win scores in the TT causing problems

[bob]

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.

In my search I define a "minimum possible value" (minValue) and a "maximum possible value" (maxValue) for the root node based on this rule at the very beginning of each new iteration, like this:

Code: Select all

// 'it' := number of current iteration, starting at 1
minValue = -(MATE_VALUE - 2 * ((it + 1) / 2));
maxValue =   MATE_VALUE - 2 * it / 2 - 1;
if (hasOnlyBareKing(side))     maxValue = min(maxValue, 0);
if (hasOnlyBareKing(opponent)) minValue = max(minValue, 0);

I stop the search if the best value [EDIT: at the end of an iteration] is either maxValue (in case of a mate that's the 2N-1 rule in fact), or minValue and negative. Since shorter mates than given by minValue are already excluded I can safely stop if all of my moves lead to minValue; I will not be able to improve on that by a deeper search.

minValue and maxValue are also used as limiting borders for the aspiration window (and this closely cooperates with stopping the search as shown above). Here minValue tells me that when I am starting iteration 'it', there was no mate in either (it-1) or (it-2) plies [depending on 'it' being odd or even] found against me, so now the worst case is either mate in (it+1) or (it) plies. Similar things are done for maxValue. Using maxValue as beta sometimes helps my engine to find a mate slightly faster, and I have not found any negative impact of doing it this way.

I do quite the same at each full search node, too, only I additionally take into account the current search depth, which helps to do quick qutoffs frequently as soon as some mate has been found before and incorporated into alpha.

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 think that very strong engines should also be strong in playing the shortest mate *if there is enough time left on the clock*. It may be right to say that this does not improve an engine's Elo but I'm pretty sure it satisfies a couple of users, and on the other hand it does not hurt anyone, provided search time is sufficient for that. And it's simple to implement, so why should it be pointless to look for a mate in 5 or 6 when a mate in 7 has been found during iteration no. 8, where we only know that there is no mate in 4?

Sven

Simple answer: If you lose, you get zero points, if you draw, you get 1/2 point. If you win, you get one point. You don't get anything for finding the shortest mate. Or the most appealing mate. I want to see the game end as quickly as possible. Once I find a forced mate and move, the remainder of the moves will be played almost instantly anyway, which gets the game over. If you use endgame tables, this is particularly difficult. You will _never_ find the shortest mate anyway, so why do it sometimes and not others???

[bob]

The surprise to me is that one can have a "correct" implementation here and still have problems due to iterative deepening and the TT interacting in non-obvious ways. What happens is that at shallow iterations, one can stumble upon a non-optimal win score and all competing branches are not in the TT and thus pruned due to an eval which is much lower than a win score.

If I understand correctly what you mean the usual way to solve this is not to use transposition table scores in assumed PV. This is usually bad idea anyway since we cannot check for repetition or fifty move rules.

It isn't what you meant, but in any case, your suggestion (not using table scores in a PV) is simply wrong. EXACT scores are not the only problem. fail highs and fail lows are also wrong, because they do not correctly account for the 50 move rule or repetitions either. So you _really_ want to ignore all trans/ref scores and just use the best move?

J. Wesley wrote:
"Second, don't terminate on wins until you have searched deeply enough to know there are no shorter wins."

It's unclear to me how one would know when to terminate as how does one know that there are no shorter wins. Here's an idea, terminate early if you find a win that's shorter than the win found in the previous search - does that seem reasonable?

I guess there are two approaches to this:

* You could terminate when for example two or three iterations in row return a mate score. If your search tree is not highly imbalanced, it's quite likely that you have already found the shortest mate.

* Another way (AFAIK Rybka does like this) is not even try to find a shortest win. If last move we had mate in 12, now don't stop until we find at least mate in 10.

[Sven]

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 think that very strong engines should also be strong in playing the shortest mate *if there is enough time left on the clock*. It may be right to say that this does not improve an engine's Elo but I'm pretty sure it satisfies a couple of users, and on the other hand it does not hurt anyone, provided search time is sufficient for that. And it's simple to implement, so why should it be pointless to look for a mate in 5 or 6 when a mate in 7 has been found during iteration no. 8, where we only know that there is no mate in 4?

Sven

Simple answer: If you lose, you get zero points, if you draw, you get 1/2 point. If you win, you get one point. You don't get anything for finding the shortest mate. Or the most appealing mate. I want to see the game end as quickly as possible. Once I find a forced mate and move, the remainder of the moves will be played almost instantly anyway, which gets the game over.

So you compile with -DSATISFY_BOB. Why don't you also compile with -DSATISFY_OTHER_USERS?

If you use endgame tables, this is particularly difficult. You will _never_ find the shortest mate anyway, so why do it sometimes and not others???

I do not try to be perfect. However, I try to do things that are easy to be done if they do not hurt and sometimes let the engine appear to play better chess from a human's point of view. Also, if I see that it is impossible to do something consistently everywhere then my conclusion is not necessarily that I never do that "something"; instead I try to do it where possible.

Sven

[gschmidt]

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.

[bob]

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 think that very strong engines should also be strong in playing the shortest mate *if there is enough time left on the clock*. It may be right to say that this does not improve an engine's Elo but I'm pretty sure it satisfies a couple of users, and on the other hand it does not hurt anyone, provided search time is sufficient for that. And it's simple to implement, so why should it be pointless to look for a mate in 5 or 6 when a mate in 7 has been found during iteration no. 8, where we only know that there is no mate in 4?

Sven

Simple answer: If you lose, you get zero points, if you draw, you get 1/2 point. If you win, you get one point. You don't get anything for finding the shortest mate. Or the most appealing mate. I want to see the game end as quickly as possible. Once I find a forced mate and move, the remainder of the moves will be played almost instantly anyway, which gets the game over.

So you compile with -DSATISFY_BOB. Why don't you also compile with -DSATISFY_OTHER_USERS?

If you use endgame tables, this is particularly difficult. You will _never_ find the shortest mate anyway, so why do it sometimes and not others???

I do not try to be perfect. However, I try to do things that are easy to be done if they do not hurt and sometimes let the engine appear to play better chess from a human's point of view. Also, if I see that it is impossible to do something consistently everywhere then my conclusion is not necessarily that I never do that "something"; instead I try to do it where possible.

Sven

I compile with the "SATISFY_FIDE_RULES option on at all times. All I care about is that I mate my opponent when it is possible. There is not a single program on the planet that finds the shortest mate for every position, particularly the EGTB case I mentioned. If I can't get 'em _all_ right with the shortest mate, what's the reasoning to try to get a few right where nobody can tell which is actually right or wrong anyway?

It is easy to fool yourself into thinking you have solved a problem, until you look at it carefully and realize it isn't solved at all.

[hgm]

Most of us do not care about points at all. Whether our engine wins or loses, it doesn't make us a dime. The chess it produces only serves the purpose of being aestethically pleasing. In general wins are more pleasing than losses. But some wins leave you with a nasty taste. Like needing 100 moves to win KQQK, or seeing your opponent crash and forfeit on time when he is to mate you in 7. I'd rather lose through a brilliant move of the opponent than have such a win.

So a win is not a win at all. You can win, and still radiate stupidity. Which is not what most of us are looking for...

[bob]

Most of us do not care about points at all. Whether our engine wins or loses, it doesn't make us a dime. The chess it produces only serves the purpose of being aestethically pleasing. In general wins are more pleasing than losses. But some wins leave you with a nasty taste. Like needing 100 moves to win KQQK, or seeing your opponent crash and forfeit on time when he is to mate you in 7. I'd rather lose through a brilliant move of the opponent than have such a win.

So a win is not a win at all. You can win, and still radiate stupidity. Which is not what most of us are looking for...

I do not believe that finding a mate in N quickly, vs taking 10 minutes to find a mate in N-2 "radiates stupidity". If you use EGTBs you already "radiate stupidity" all over the place for obvious reasons...

[bob]

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.

[gschmidt]

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.

I do not do hash insertions near the leaf nodes, but my thought was to do probes at leaf nodes since it seemed like there might be a good chance that a transposition of a shallower node exists there. I believe you are saying that finding transpositions at the leaf is rare.

-- Greg

[bob]

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.

I do not do hash insertions near the leaf nodes, but my thought was to do probes at leaf nodes since it seemed like there might be a good chance that a transposition of a shallower node exists there. I believe you are saying that finding transpositions at the leaf is rare.

-- Greg

There are a ton of options here. Amir once said that he does not hash within one ply of the horizon, to save hash accesses and entries. Whether probes without stores beyond the basic horizon will work or not is hard to say. It is easy enough to check. My only concern is with performance. You can add all sorts of code to the basic search code with little impact on speed. But when you add something to Quiesce(), no matter how small, you can measure the impact on speed quite easily since that gets executed so many times in a normal search position.