Loss-seeking extension/threatened pieces

[Evert]

I'm experimenting with a particular loss-seeking extension at horizon nodes.
The motivation for this is looking at some Capablanca-chess games where my program did poorly at short time controls because it was delaying the loss of a major piece by spite-checks. In other words, the classical search-horizon problem.
Clearly, the problem goes away with increased depth and longer time controls, but I'd like to find a sortof-cure at shorter times as well. The idea is to try to prove that the sequence of moves I've just played to get here is bad. The condition I came up with is the following:
If we're at the search horizon, we're in a PV node (we expect other lines to be worse anyway, so no point in trying to prove them even worse than we already think they are; should they fail high we'll get to it at that point anyway), the last move by the opponent was a check-evasion and we're not far from the root of the tree, then do a qsearch for the opponent. If this fails low by the value of a minor piece or so, extend the search by one ply.

The depth restriction is there because this is mainly a problem at low depth and also to prevent the tree from exploding (not much danger of that if the last move has to be a check evasion, but anyway). It probably will do nothing for playing strength at longer time controls, and I haven't had time to do a proper test at short time controls (I'll start that this evening). I was mainly wondering whether anyone would have an opinion about this idea.

Another idea I had, with essentially the same goal, is to simply give a penalty in the evaluation if the side to move has pieces en-prise. This is not picked up by the quiescence search (maybe I should do that: check if there are threatened pieces and force them to move, but that requires passing back more information from the evaluation than I currently do) and should be fairly easy to test for in the evaluation. The rationale for not doing the same for the side that is not on move is that those captures would have been searched by the QS, but maybe having an asymmetry like that is not a good idea.

[bob]

I'm experimenting with a particular loss-seeking extension at horizon nodes.
The motivation for this is looking at some Capablanca-chess games where my program did poorly at short time controls because it was delaying the loss of a major piece by spite-checks. In other words, the classical search-horizon problem.
Clearly, the problem goes away with increased depth and longer time controls, but I'd like to find a sortof-cure at shorter times as well. The idea is to try to prove that the sequence of moves I've just played to get here is bad. The condition I came up with is the following:
If we're at the search horizon, we're in a PV node (we expect other lines to be worse anyway, so no point in trying to prove them even worse than we already think they are; should they fail high we'll get to it at that point anyway), the last move by the opponent was a check-evasion and we're not far from the root of the tree, then do a qsearch for the opponent. If this fails low by the value of a minor piece or so, extend the search by one ply.

The depth restriction is there because this is mainly a problem at low depth and also to prevent the tree from exploding (not much danger of that if the last move has to be a check evasion, but anyway). It probably will do nothing for playing strength at longer time controls, and I haven't had time to do a proper test at short time controls (I'll start that this evening). I was mainly wondering whether anyone would have an opinion about this idea.

Another idea I had, with essentially the same goal, is to simply give a penalty in the evaluation if the side to move has pieces en-prise. This is not picked up by the quiescence search (maybe I should do that: check if there are threatened pieces and force them to move, but that requires passing back more information from the evaluation than I currently do) and should be fairly easy to test for in the evaluation. The rationale for not doing the same for the side that is not on move is that those captures would have been searched by the QS, but maybe having an asymmetry like that is not a good idea.

You have to be very careful when you start to violate basic minimax assumptions. One idea used/tried by some in the 70's was an attempt to expose horizon effect moves. When A PV was backed up all the way to the root, along with a score, one could step to the end of the PV, and do a very short search from that point. If the resulting score was worse, use that. Obvious idea being that if your last move was a dumb one, this would let the other side (at the horizon) punish it. Made programs play worse, and I don't know of anyone that used it to any serious extent. We used it for a while in some version of Blitz, but decided to remove it because at the last ply, you basically trust the move you found and do a short search to refute it. But there may well be another move at the last ply that can't be refuted. This quick-and-dirty approach will not recognize that, and you replace one type of error with another...

[Ferdy]

I'm experimenting with a particular loss-seeking extension at horizon nodes.
The motivation for this is looking at some Capablanca-chess games where my program did poorly at short time controls because it was delaying the loss of a major piece by spite-checks. In other words, the classical search-horizon problem.
Clearly, the problem goes away with increased depth and longer time controls, but I'd like to find a sortof-cure at shorter times as well. The idea is to try to prove that the sequence of moves I've just played to get here is bad. The condition I came up with is the following:
If we're at the search horizon, we're in a PV node (we expect other lines to be worse anyway, so no point in trying to prove them even worse than we already think they are; should they fail high we'll get to it at that point anyway), the last move by the opponent was a check-evasion and we're not far from the root of the tree, then do a qsearch for the opponent. If this fails low by the value of a minor piece or so, extend the search by one ply.

The depth restriction is there because this is mainly a problem at low depth and also to prevent the tree from exploding (not much danger of that if the last move has to be a check evasion, but anyway). It probably will do nothing for playing strength at longer time controls, and I haven't had time to do a proper test at short time controls (I'll start that this evening). I was mainly wondering whether anyone would have an opinion about this idea.

I encountered this problem in the past, what I do is re-check my repetition code, I also re-check extension code. If the score is really bad while doing this futile checking, do you use futility prunning or reduction perhaps? Also if I observed that there is severe speed issue, I do profiling, especially when there are new codes added.

Another idea I had, with essentially the same goal, is to simply give a penalty in the evaluation if the side to move has pieces en-prise. This is not picked up by the quiescence search (maybe I should do that: check if there are threatened pieces and force them to move, but that requires passing back more information from the evaluation than I currently do) and should be fairly easy to test for in the evaluation. The rationale for not doing the same for the side that is not on move is that those captures would have been searched by the QS, but maybe having an asymmetry like that is not a good idea.

Richard has mentioned that before going to qsearch (because of zero depth), check if opponent has some nasty threats, if so just extend and continue with your main search. Detecting these nasty threats are a bit of challenge, though some engines have free access to these threats

[Evert]

I encountered this problem in the past, what I do is re-check my repetition code, I also re-check extension code. If the score is really bad while doing this futile checking, do you use futility prunning or reduction perhaps?

Yes, I do.

Also if I observed that there is severe speed issue, I do profiling, especially when there are new codes added.

Speed optimsations are of course always good, and Sjaak is pretty slow. Unfortunately there's only so much I can do with it because it's a general variant engine, so a lot of simplifications and short-cuts that are possible in a normal chess engine are not possible. I do try to optimise the common or typical cases, of course. It also doesn't help that it's using 128-bit boards for large variants, which are slower than 64 bit boards.

Richard has mentioned that before going to qsearch (because of zero depth), check if opponent has some nasty threats, if so just extend and continue with your main search. Detecting these nasty threats are a bit of challenge, though some engines have free access to these threats

That is indeed similar to what I'm doing. I guess it would be possible to keep track of major threats in the tree, then at the horizon (or when nearing the horizon) check whether the threat still exists or has merely been delayed.

[Evert]

You have to be very careful when you start to violate basic minimax assumptions.

Would that be more of an issue with this type of extension than with other extensions?

One idea used/tried by some in the 70's was an attempt to expose horizon effect moves. When A PV was backed up all the way to the root, along with a score, one could step to the end of the PV, and do a very short search from that point. If the resulting score was worse, use that. Obvious idea being that if your last move was a dumb one, this would let the other side (at the horizon) punish it. Made programs play worse, and I don't know of anyone that used it to any serious extent.

Interesting. I did once try effectively extending the PV by one ply compared to other moves, with a similar idea. The result wasn't too great, since it just meant it was harder to replace a dumb move.

We used it for a while in some version of Blitz, but decided to remove it because at the last ply, you basically trust the move you found and do a short search to refute it. But there may well be another move at the last ply that can't be refuted. This quick-and-dirty approach will not recognize that, and you replace one type of error with another...

Ok, I see. That does make sense. It would help in some obvious cases and do badly in many others.

I'll test the idea anyway. I don't expect it to actually help much, even if it seems good in quick tests.

[Evert]

I'll test the idea anyway. I don't expect it to actually help much, even if it seems good in quick tests.

Well, the idea started out looking pretty bad early on in the test, coming in at -30 elo or so. However, it ended up being dead-even in the end (but still +/- 16 elo). I could continue the test and play more games to get the error-bar down, but I don't think it's worth it.