Horizon effect

[hgm]

It is annoying that when you make chess engines weak (e.g. by limiting search depth) they also become stupid even in the eyes of a weak human player for which beating it consistently would still be a challenge. The kind of tactical errors it will make will often show an embarrassing lack of common sense. E.g. when it can realize a big gain, e.g. by capturing a hanging piece, but the offering is poisoned (e.g. because the piece was indirectly protected through an intermediate check, or because the more valuable capturing piece gets trapped and eventually lost)... Then it will try to push this unavoidable backlash beyond the horizon by a number of minor sacrifices (that nevertheless force the opponent to react) to eat away depth to the point where the poisoned capture starts to look good. While a human, once he had seen that the capture is poisoned, would no longer consider it at any depth, unless he could design a preparation that would disarm the trap.

I was thinking of the following heuristic to cure this: we have a small (always-replace) hash table for poisoned moves. When a PV move (obtained from an earlier iteration, either as TT move or in the process of IID) severely drops in score on the new depth, we store it in this hash table together with the depth, and its new score relative to the current evaluation. When the search then later encounters this move in this hash table, at a remaining depth that is less than the depth where it turned sour, it won't search it, but assigns it the score from the table (by adding the stored 'gain' to the evaluation of the current node). If the previous sequence of moves made from the position where the move was recognized as bad would have given away material, this would make the new branch that tried to perform this move later not eligible for new PV.

Of course this replaces one error for another, because it assumes that the moves that were put before it never can disarm the trap. But is seems statistically unlikely that randomly picked minor sacrifices would solve a given threat, so this seems this should hurt less to assume it doesn't solve the threat than to assume that it does always solve the threat that you know existed beyond the horizon.

I haven't checked how this affects the playing strength, but the errors that would result from assuming the trap cannot be disarmed when you have not enough depth to make sure it was disarmed seem much more human-like.

[dangi12012]

Good idea. Additional input:
You store the Bitboard of all Squares that are part of the poisoned (trap) position. (So all relevant vision squares towards the SEE exchange + intermediate checks etc.)

If any of the last moves changed the bitboard that are part of the trap - then you can invalidate it.

The main idea is sound: When you see a trap, or poisoned pawn you dont need to reevaluate it when you are entering the same structural tactic line.
A structural tactic line (trap) may be reevaluated if more depth is available or the traps relevant BB changed.

[Chessnut1071]

Good idea. Additional input:
You store the Bitboard of all Squares that are part of the poisoned (trap) position. (So all relevant vision squares towards the SEE exchange + intermediate checks etc.)

If any of the last moves changed the bitboard that are part of the trap - then you can invalidate it.

The main idea is sound: When you see a trap, or poisoned pawn you dont need to reevaluate it when you are entering the same structural tactic line.
A structural tactic line (trap) may be reevaluated if more depth is available or the traps relevant BB changed.

You better have a near perfect algorithm for the poison piece trap to work. That whole theory falls apart as the depth grows larger and larger. I'd be interested in seeing the end result after somebody does it, but, I suspect it won't lead to a significant change in ELO. Surprise me.

[Mike Sherwin]

Besides the horizon effect there is the 'parity' effect. The parity effect is when the best move changes due to the side that plays last before Qsearch. I suggest that both effects can be mitigated in the following way.

Do upper level iteration depths only at even ply 2,4,6 etc. The lower level search depth will be half that 1, 2, 3 etc. An example search would be an upper level iteration of 30. That means doing 30 15 ply searches as w/b/w/b/w/b etc essentially creating a game segment searched 45 moves deep.

On the Plus Side
The engine will play strategically better.

On the Negative Side
The engine might miss some deep tactic in the first 15 moves.
(I assume though that a good eval will make this rare.)

Just a thought.