Evaluation features at different time controls

[Evert]

I guess it's a well-known problem that evaluation features sometimes behave differently at different time controls. What is the general practice with regard to this?

Some context to make the question a bit less general. I know that in drop variants (say, Shogi) Sjaak is vulnerable to overlooking mate threats of the type "drop-with-check, evade, drop-with-mate". This mainly happens at very fast time controls. I know it's possible to do a special QS-like mate search that specifically looks for this pattern, and I'm considering coding one up to see how it does. However, the first thing I tried was a simple tweak to the king-shelter code: I award a larger penalty to holes in the shelter in front of the king.

I ran the patch against the earlier version, at 40 moves in 20 seconds, repeating and it passed a SPRT (0, 4) test very quickly. Good. I then re-ran the test at 40 moves in 60 seconds, and it's struggling quite badly. The test is still running, but I doubt it'll do better than break even.

So what to do? Since the problem mainly manifests itself at short time controls, it's tempting to discard the long TC struggles, but I don't think I should: even if the effect is smaller, I would still expect some benefit if the idea is sound. I guess the problem is essentially a search issue, so the correct solution is to modify the search rather than hack around with the evaluation.

Any similar experiences (and alternative suggestions) out there?

[hgm]

It is in general very difficult to make eval substitute for search. I would hypothesize that in deeper searches pre-existing 'holes' would already have been exploited if they were dangerous. So that your eval term would needlessly penalize non-dangerous holes. Or holes that are created during the final ply. But such holes might be easy to repair, by simply moving back. (Although in Shogi that is not always possible.) Putting things in eval that aren't really strategic (persistent) features of the position is often counter-productive. It just creates horizon effect. You start to sac advantage for reaching the position penalized by the eval just before the horizon, to see the compensation evaporate the next move.

Bonanza does these 3-ply 'tsume' searches even in QS. In Shokidoki I have never had any success in searching check-drops in QS. It always exploded. The Bonanza solution prevents that, because once you are going for the check-drops you are not allowed anymore to continue with captures, but must continue with checkmate. But the price is that there will be many things it overlooks. (Like giving the opponent enough material in hand for a mate in >=3.) But I assume it was optimized.

Some of these Shogi engines have amazing capabilities for finding tsume mates. When I play Shokidoki vs SPEAR, the latter often announces mate in 16 or 20, while Shokidoki then only starts to see any trouble when it is to be mated in 10. Of course the tsume search goes at the expense of the full-depth search, and Shokidoki is indeed quite efficient in gobbling up SPEARS non-royal material (before the mate strikes as a bolt from the blue). This is not imagined, as SPEAR admits in its own evaluation that its position is getting worse and worse.

I think one crucial concept that I have yet to exploit is 'futile interpositions'. These are defined as blocking a slider check with a piece that will be immediately taken by the checker, after which nothing really changed (except that you gave the opponent an extra piece in hand). In tsume problems such futile interpositions are not counted to the mate depth. But the problem is that they can only be precisely defined in hind-sight: If the 'best defence' according to Chess counting would involve an interposition, and not playing that interposition would get you mated one move faster through the same moves, the interposition was futile. Interposing on a protected square obviously is never futile, as it allows you to now capture the checker, which you initially could not. But sometimes you can interpose an unprotected piece to create an escape square for your King, to lure the checker to a place where a sideway move is blocked or where he is too close (in case he has to check a second time), or to enter the promotion zone prematurely.

It is especially the futile interpositions that make a tsume search explode. The checking side wastes his material on unsafe checks, evaded by capturing the checker, but never runs out of material to drop, because it alternates this with distant slider checks which then are evaded by futile interpositions which are then gobbled up.

I guess move ordering is crucial, as QS is a depth-first search, and there is no easy way to turn it in to breadth-first by some IID scheme. Interpositions are in general quite expensive evasions, as after he captures you are not only 2 moves deeper, but you now also have to 'ride out' the extra check by the piece he got in hand. That holds even if the interposed piece was protected. After check-drop A, interpose B, capture AxB, recapture CxB basically nothing was solved in 4 extra ply: the attacker replaced A in his hand by B, and C might have been dislodged from its optimal defensive position. It is more a delaying tactic than anything else, and one that might even show up as a gain in material eval (if A > B).

So it would probably be best to search interposition check evasions last, and interpositions on unprotected squares even later. Perhaps you should prune them outright, in a QS/tsume search. Even in full-width search it is not clear to me how these moves should be handled. You know them to be delaying tactics that likely are bad in the long run, but might look good in the short run. So you cannot reduce them; to recognize they are bad you should even extend them. But that would mean you start to concentrate search effort on moves that are likely poor, which is also the last thing you want.

So the solution could be to prune the moves on the mere suspicion they will be bad, until the natural search depth is high enough to prove them bad in spite of the delay they provide. E.g. when after searching all other evasions (King evacuation, capturing the checker) you stand to get mated in N, you should prune unprotected interpositions for any depth < N+1, as with lower depth they will just put that same mate over the horizon. Only at d >= N+1 you can hope to find out if the interposition really helped. For protected interpositions this would even be d >= N+2. Most of the time they would then confirm what you already suspected, namely that you were to be mated. I guess when you prune them you could correct the returned score to mated-in-N+1 or N+2.

I guess the same technique could be used to handle spite checks. Sort checks last, if you are mated-in-N without them, prune them when d < N+1 under the assumption they will just delay the mate.

[Ferdy]

I guess it's a well-known problem that evaluation features sometimes behave differently at different time controls. What is the general practice with regard to this?

Some context to make the question a bit less general. I know that in drop variants (say, Shogi) Sjaak is vulnerable to overlooking mate threats of the type "drop-with-check, evade, drop-with-mate". This mainly happens at very fast time controls. I know it's possible to do a special QS-like mate search that specifically looks for this pattern, and I'm considering coding one up to see how it does. However, the first thing I tried was a simple tweak to the king-shelter code: I award a larger penalty to holes in the shelter in front of the king.

If tuning values gave inconsistent results by time, try adding a new feature. The kind of feature that you will add will be based on the problem after thorough analyses of those games and of course based also on your existing eval features.
There are also things you can do in the search, one is having a good conditions of pruning and reductions.
For games with drop moves I would like to explore on the methods and conditions of search extensions, like don't go to qsearch if opponent has material on-hand and you have weak squares in you camp, well it depends on what you do in qsearch too.

[Evert]

Bonanza does these 3-ply 'tsume' searches even in QS. In Shokidoki I have never had any success in searching check-drops in QS. It always exploded. The Bonanza solution prevents that, because once you are going for the check-drops you are not allowed anymore to continue with captures, but must continue with checkmate. But the price is that there will be many things it overlooks. (Like giving the opponent enough material in hand for a mate in >=3.) But I assume it was optimized.

I tried to look how Bonanza does it, but not being familiar with the code I find it somewhat hard to work out.

The algorithm I came up with (but haven't tried yet) is something like this:

Code: Select all

1. Perform a mate-search (tsume-search, I guess) if
    a. We are close to the root
    b. Close to the tips
    c. After a null-move (?)
    d. Other considerations?
2. Apply some limit on the depth of the mate we're looking for: near the tips, something like 3 ply. Near the root with large remaining depth, maybe go deeper (may not be needed, in which case condition a is redundant). Say we look for mate in M ply.
3. Generate all checking drops and do a fixed-depth evasion/checking-only search, up to depth M. The result is either mate-in-M-or-less, or not mate.
4. Feed the moves in the mate search back to the main search through the killer and transposition tables.
5. Cache the results in a special hash table, just so we don't do the same thing over and over again.

The idea is to limit this as much as possible. I was thinking of also applying constraints on the number of available moves for the king, but perhaps that is too complicated to justify. In the end, it's not going to catch all cases, but if it catches some of them before they become a problem, that will already be an improvement.

I think one crucial concept that I have yet to exploit is 'futile interpositions'. These are defined as blocking a slider check with a piece that will be immediately taken by the checker, after which nothing really changed (except that you gave the opponent an extra piece in hand). In tsume problems such futile interpositions are not counted to the mate depth. But the problem is that they can only be precisely defined in hind-sight: If the 'best defence' according to Chess counting would involve an interposition, and not playing that interposition would get you mated one move faster through the same moves, the interposition was futile. Interposing on a protected square obviously is never futile, as it allows you to now capture the checker, which you initially could not. But sometimes you can interpose an unprotected piece to create an escape square for your King, to lure the checker to a place where a sideway move is blocked or where he is too close (in case he has to check a second time), or to enter the promotion zone prematurely.

It is especially the futile interpositions that make a tsume search explode. The checking side wastes his material on unsafe checks, evaded by capturing the checker, but never runs out of material to drop, because it alternates this with distant slider checks which then are evaded by futile interpositions which are then gobbled up.

I guess move ordering is crucial, as QS is a depth-first search, and there is no easy way to turn it in to breadth-first by some IID scheme. Interpositions are in general quite expensive evasions, as after he captures you are not only 2 moves deeper, but you now also have to 'ride out' the extra check by the piece he got in hand. That holds even if the interposed piece was protected. After check-drop A, interpose B, capture AxB, recapture CxB basically nothing was solved in 4 extra ply: the attacker replaced A in his hand by B, and C might have been dislodged from its optimal defensive position. It is more a delaying tactic than anything else, and one that might even show up as a gain in material eval (if A > B).

So it would probably be best to search interposition check evasions last, and interpositions on unprotected squares even later. Perhaps you should prune them outright, in a QS/tsume search. Even in full-width search it is not clear to me how these moves should be handled. You know them to be delaying tactics that likely are bad in the long run, but might look good in the short run. So you cannot reduce them; to recognize they are bad you should even extend them. But that would mean you start to concentrate search effort on moves that are likely poor, which is also the last thing you want.

So the solution could be to prune the moves on the mere suspicion they will be bad, until the natural search depth is high enough to prove them bad in spite of the delay they provide. E.g. when after searching all other evasions (King evacuation, capturing the checker) you stand to get mated in N, you should prune unprotected interpositions for any depth < N+1, as with lower depth they will just put that same mate over the horizon. Only at d >= N+1 you can hope to find out if the interposition really helped. For protected interpositions this would even be d >= N+2. Most of the time they would then confirm what you already suspected, namely that you were to be mated. I guess when you prune them you could correct the returned score to mated-in-N+1 or N+2.

I guess the same technique could be used to handle spite checks. Sort checks last, if you are mated-in-N without them, prune them when d < N+1 under the assumption they will just delay the mate.

This is indeed a possible issue. At least the situation where an interposition is immediately refuted by a capture by the checking piece can be recognised in some circumstances (if the interposition was a drop it can't have any side-effects). In principle you should also be able to record the path to mate and then search that first after the capture (somewhat like a PV table). In the end you probably can't beat down the exponential tree-growth in the general case though. I guess the question is whether a solution that only captures a sub-set of possible problems is still worthwhile.

[hgm]

I haven't really looked at the Bonanza code at all. (Except for the protocol driver, to convert it to WB.) The story about the 3-ply tsume search in QS node was what its author told me, when we met in Tilburg.

This is indeed a possible issue. At least the situation where an interposition is immediately refuted by a capture by the checking piece can be recognised in some circumstances (if the interposition was a drop it can't have any side-effects). In principle you should also be able to record the path to mate and then search that first after the capture (somewhat like a PV table). In the end you probably can't beat down the exponential tree-growth in the general case though. I guess the question is whether a solution that only captures a sub-set of possible problems is still worthwhile.

The problem with storing the 'path to mate' is that it is not really a path, but a tree. Usually there are multiple evasions at every step, and each evasion will then have a different follow-up.

The tree should of course be already stored in the TT. So perhaps the following would be a good idea: pass around an 'analogy key'. I.e. if you have reason to suspect that the previous two ply were an irrelevant delaying tactic (spite check in a quiet position, futile interposition when in check), pass the modification these two ply made to the hash key along to the entire sub-tree hanging from those two moves. Each node could then modify its true key by this analogy key (a simple XOR or subtraction) to do a hash probe on the analogous node without the delaying tactic, (the entry for which should still be cached), and use the hash move it finds there as a 'evasion killer', to be searched immediately after the true hash move (or just after there is none).

A more aggressive use of this would be to take the (mate) score of the analogous node in the cases where you don't have any depth left to play the hash move. When the depth after the delaying tactic then isn't enough to reach the mate before the horizon, but the tree is still exactly the same, all leaves would pick up the 'over-the-horizon mate' from the undelayed tree. But if the 'delaying tactic' was more than just that, and really created an extra defense option (e.g. escape square) or blocked an attack move, there would be no analogue found in the TT. You would have proved that the interposition (or spite check) was not futile, and the new move would have to be searched on its own merit (meaning by default it would assumed to not lead to mate, when you survive to the leaves), or the attacker would have to search for alternatives to his blocked move.

BTW, interpositions on a protected square are not necessarily better than unprotected ones (although they delay more). E.g.
[d]2k5/1pppr3/4b1R1/6P1/8/6N1/6PK/6B1 b - - 1 1
After 1... Rh7 2. Nh5 (unprotected) works because it creates an escape square (2... Rxh5 3. Kg3), but 2. Rh6 Rxh6 3. gxh6 R@h3# makes recapture by the 'protector' impossible.

[bob]

It is in general very difficult to make eval substitute for search. I would hypothesize that in deeper searches pre-existing 'holes' would already have been exploited if they were dangerous. So that your eval term would needlessly penalize non-dangerous holes. Or holes that are created during the final ply. But such holes might be easy to repair, by simply moving back. (Although in Shogi that is not always possible.) Putting things in eval that aren't really strategic (persistent) features of the position is often counter-productive. It just creates horizon effect. You start to sac advantage for reaching the position penalized by the eval just before the horizon, to see the compensation evaporate the next move.

Bonanza does these 3-ply 'tsume' searches even in QS. In Shokidoki I have never had any success in searching check-drops in QS. It always exploded. The Bonanza solution prevents that, because once you are going for the check-drops you are not allowed anymore to continue with captures, but must continue with checkmate. But the price is that there will be many things it overlooks. (Like giving the opponent enough material in hand for a mate in >=3.) But I assume it was optimized.

Some of these Shogi engines have amazing capabilities for finding tsume mates. When I play Shokidoki vs SPEAR, the latter often announces mate in 16 or 20, while Shokidoki then only starts to see any trouble when it is to be mated in 10. Of course the tsume search goes at the expense of the full-depth search, and Shokidoki is indeed quite efficient in gobbling up SPEARS non-royal material (before the mate strikes as a bolt from the blue). This is not imagined, as SPEAR admits in its own evaluation that its position is getting worse and worse.

I think one crucial concept that I have yet to exploit is 'futile interpositions'. These are defined as blocking a slider check with a piece that will be immediately taken by the checker, after which nothing really changed (except that you gave the opponent an extra piece in hand). In tsume problems such futile interpositions are not counted to the mate depth. But the problem is that they can only be precisely defined in hind-sight: If the 'best defence' according to Chess counting would involve an interposition, and not playing that interposition would get you mated one move faster through the same moves, the interposition was futile. Interposing on a protected square obviously is never futile, as it allows you to now capture the checker, which you initially could not. But sometimes you can interpose an unprotected piece to create an escape square for your King, to lure the checker to a place where a sideway move is blocked or where he is too close (in case he has to check a second time), or to enter the promotion zone prematurely.

It is especially the futile interpositions that make a tsume search explode. The checking side wastes his material on unsafe checks, evaded by capturing the checker, but never runs out of material to drop, because it alternates this with distant slider checks which then are evaded by futile interpositions which are then gobbled up.

I guess move ordering is crucial, as QS is a depth-first search, and there is no easy way to turn it in to breadth-first by some IID scheme. Interpositions are in general quite expensive evasions, as after he captures you are not only 2 moves deeper, but you now also have to 'ride out' the extra check by the piece he got in hand. That holds even if the interposed piece was protected. After check-drop A, interpose B, capture AxB, recapture CxB basically nothing was solved in 4 extra ply: the attacker replaced A in his hand by B, and C might have been dislodged from its optimal defensive position. It is more a delaying tactic than anything else, and one that might even show up as a gain in material eval (if A > B).

So it would probably be best to search interposition check evasions last, and interpositions on unprotected squares even later. Perhaps you should prune them outright, in a QS/tsume search. Even in full-width search it is not clear to me how these moves should be handled. You know them to be delaying tactics that likely are bad in the long run, but might look good in the short run. So you cannot reduce them; to recognize they are bad you should even extend them. But that would mean you start to concentrate search effort on moves that are likely poor, which is also the last thing you want.

So the solution could be to prune the moves on the mere suspicion they will be bad, until the natural search depth is high enough to prove them bad in spite of the delay they provide. E.g. when after searching all other evasions (King evacuation, capturing the checker) you stand to get mated in N, you should prune unprotected interpositions for any depth < N+1, as with lower depth they will just put that same mate over the horizon. Only at d >= N+1 you can hope to find out if the interposition really helped. For protected interpositions this would even be d >= N+2. Most of the time they would then confirm what you already suspected, namely that you were to be mated. I guess when you prune them you could correct the returned score to mated-in-N+1 or N+2.

I guess the same technique could be used to handle spite checks. Sort checks last, if you are mated-in-N without them, prune them when d < N+1 under the assumption they will just delay the mate.

I have mentioned this problem in the past, but here goes again.

In 1985 I was getting ready to move to Birmingham AL to work on my Ph.D. And during the Summer, before we moved, I worked on Cray Blitz to get ready for the 1985 ACM tournament in Denver. I did most of my testing on a Vax, which was Far slower than the Cray 4 cpu machine we used for tournaments, and we played a bunch of games against the Super Constellation that summer. We only lost an occasional game, but each time it was in almost-endgame positions where our pawn structure was a little "loose" and had holes the opponent could infiltrate on. I added a simple eval term to penalize such holes, and for the next month we didn't lose another game during testing.

When we got to Denver, we lost an unexpected game in the first round, and then lost to HiTech later. Both games saw pretty passive play where Cray Blitz had always been fairly aggressive with king-side attacks in prior years. I just assumed "looks like everyone is catching up to us..." and didn't think any more about it. In the 1986 WCCC event in Cologne, we lost in the first round to a program that should have been no competition. I looked at the game carefully and noticed that CB was simply refusing to push pawns. In thinking about it, I wondered if that "anti-hole patch" was hurting. It was just a couple of lines of code, so I commented them out and went back through the game we lost again. This time it played sensibly, made pawn breaks when it should. I then went back to the 1985 games and played over them and once again, it pushed when it should have, didn't when it wasn't needed. I left the code disabled, we won the next 4 rounds and the 1986 WCCC.

Turns out that our evaluation had code that understood weak squares (not defendable by pawns). Our mobility factored this in, the outpost knight/bishop code factored this in. And then the new eval term did it again. It was too much. Shallow searches could not see how to exploit the holes so the new penalty was good. But searches 2x deeper could not only see how to exploit the holes, but also penalized them even if they were not harmful.

That was the last time I tuned anything running on any hardware but the Cray. I did lots of Vax testing, but everything was then validated on the Cray before it made it to "prime time".

[Evert]

I'm currently testing the impact of a special mate-search. It only looks at check-evade-check-evade-mate type mates (no quiet moves), which I guess are the common pit-falls in Shogi. Looks good so far, but test is still running.

The mate-search is heavily restricted (I haven't even tried optimising this yet): it's called at ply 0 and 1 (so near the root, mainly to detect mate threats against the current mainline), when remaining depth is larger than 8 (so it will find deeper threats eventually, but calling it at the tips is far too expensive, judging from a quick test), or when we're doing a mate-search anyway (as judged from the alpha/beta window).
The mate-search is initially limited to 3 ply mates, but near the root the mate-depth is increased for every 4 plies of search-depth (so it will eventually find longer drop-mates).

The mate-search itself is pretty straightforward: it's basically a normal alpha/beta search, with an extra cut-off at the last ply (where we're supposedly mated) after the first legal evasion. All non-mate scores are treated equal (as non-mate). Positions that are on a mating path are stored in the main TT and killers are also recorded normally.
The only extra feature is that I record whether a position has been subjected to a mate-search before. If it has been and the position was found to not be mate (within the depth limit), it is not examined again. This ends up saving quite a bit of time.

Depending on how it works out at different time controls and what sort of tweaks I want to make to it I may disable it by default, but I'll probably add an engine option to switch it on or off. Certainly for analysis it may make sense to always have it on (but then the engine might behave differently in analysis mode than it does in a normal search, I'm not sure how useful that is).