Piece drops and horizon effect

[hgm]

I have little experience with Crazyhouse engines. But I noticed that many of the weaker Shogi engines show the same characteristic foolish behavior:

1) Drop a Pawn at X so it attacks an opponent Pawn at Y
2) Y x X
3) Piece x X
4) P@Y {attacking the Piece}
5) Withdraw Piece {usually to where it came from}

Much of this sequence is forced: if Y would not capture X in (2), then X could capture Y in (3), often with promotion. So you cannot ignore the drop (1) and start wih your own attack, even if you have a profitable one. Using the Pawn to capture, however, compromises your Pawn wall, through which the recapturing piece might enter, capturing something that before was shielded by the Pawn. This forces (4) to close hole.

At the end of the sequence everything is back where it started, but the other side now has the move. So the sequence wastes a tempo for the side that initiated it. If he withdraws the recapturing piece to another square then were it came from, it does not even waste a tempo, but is equivalent to moving the piece there directly (if that was possible). It just inserts 4 extra ply.

Now wasting a tempo is only penalized if it pushes useful moves (with positive score) over the horizon. A 'side-to-move bonus' would not help, as who is to move at the leave node is only dependent on the depth, not on whether you waste a tempo along the branch. If there is trouble coming towards you, the 4 inserted ply are actually a rather cheap way to push it beyond the horizon. This probably explains why the sequence of moves is so popular; it is like you are allowed to play R=4 null moves in the PV: head in the sand, and don't move a muscle while the opponent gradually closes in on you without meeting any resistance.

Even when there is no real threat, but the engine simple doesn't see anything to strive for, it will engage in this practice. This is similar to Chess engines starting to move there Rook back and forth when they don't know what to do anymore.

I wonder how this kind of nonsense can be suppressed. With path-dependent scoring it would be easy enough to recognize the pattern in the path (like moving the same piece multiple times to places where it could have moved at once, or already was), and penalize that. But that interferes badly with hashing. Now hashing is in fact somewhat helpful to suppress the horizon effect that inserting the exra 4 plies causes: The null move in stead of (1) would bring you to the same position as after (5), and would have been searched before you attempted (1), and apparently failed low, or you would not even try (1). So you should get a hash hit on it, grafting the misery you tried to push over the horizon. Except if this was a PV node where you did not search a null move. Or when you were closer than 4 ply to the horizon, so that you can nicely stand pat after (4), ignoring that you now have to rescue your Piece, and at the same time have the trouble that made the original null move fail coming at you.

So I am looking for other ways to discourage this. If I cannot do so at the leave node by making the eval path dependent, I can perhaps affect the propagation of this eval towards the root. For instance, I could subtract a penalty from the score of any Pawn drop in front of another Pawn. That way, the score from a null move in stead of (1) that you retrieve from the TT after (5) would always seem worse than taking the immediate null move. The problem is that you don't want to discourage Pawn drop (1) when it is good, e.g. because (2) is not possible at all, the Pawn at Y being pinned, so that there now is an extra Pawn attacker of it. So you only want to penalize these Pawn drops if they are indeed refuted by capture (2).

Now if (1) fails high at large remaining depth it could not have taken the full path to (5), where a hash hit would await it that fails low, and there wouldn't be any reason to mistrust (1). If (1) already fails low by itself, there is nothing to worry about. When it is PV then it should return a PV, on which we can do a pattern match to see if it is planning a time-wasting sequence of moves (be it the drop-capture sequence or just moving a slider back and forth). Making the score of a move dependent on the path leading from it, rather than to it, does not introduce any inconsistencies with hashing. You could simply subtract a penalty from a PV move that is planning to take a path that you recognize as pointless or harmful, forcing it to take the shorter path in stead, and prove there that the position you are aiming for is any good (at higher depth).

This would also solve a case encountered in normal Chess, when you can give a perpetual when you are ahead (so drawing is not attractive), but are facing a setback in one of the moves. The search will then start to insert some moves of the perpetual wherever it can, (basically every other move), to push the setback beyond the horizon. So after check1 - evade1 - moveA - moveB - check2 - evade2 as leading PV moves, when check2 - evade2 are the reverse moves of check1 - evade1, it should recognize that, and realize that any improvement this PV gives over an immediate moveA - moveB must be illusory.

[Daniel Shawul]

Well I do not like path-dependent solutions in general since that cause hash table problems. At least in this case the engine is losing only a tempo, but I am sure there are other delaying move patterns that are used by engines to hide eminent danger. Drop moves in general were very problematic for me so I chose consider them as inferior moves so that the engine tries out all other on-board moves before starting to drop pieces. If you can't handle them, hide them! I do not try them in qsearch, though they can be very important especially when chasing the king to checkmate. I am sure dedicated shogi programs have superior tactical algorithms but there is so much you can do with a general engine. The major problem is they are too many because a piece can be dropped anywhere in the 64 squares. Also if drop moves are put at the front of the move list in the main search, LMR will be triggered heavily for all on-board moves. So I put them at the end of the move list there too. I am sure many sequences like the one you explained here will be missed, and there is not much I can do about it right now. If somehow the good drop moves that attack a piece, check the king, etc are filtered, then it maybe possible to improve the engine tactically. I can not encode specific patterns in a general engine, but it maybe possible to have a general heuristic to score drop move. Currently the only way drop moves are favoured is through a bonus of +50 for a piece on-board, but trying them first in both main and qsearch seems to lower nebiyu's strength. Shokidoki probably does something different which explains the depth difference.

[hgm]

In Shokidoki I also save drop moves for last. I even generate them later (as staged move generation), in the hope I would not have to generate them at all. Useless drops score worse than the null move, because pieces in hand are in general worth more than on the board.

But I think the problem is pretty general. You get to a position through a number of moves that you could have reached in a single move (perhaps a notoriously poor one, like the null move). It is supect if the PV contains such detours. Perhaps unless you are using delayed loss bonus and there is an unavoidable loss somewere along the PV, which it likes to postpone as much as possible.

This should be recognizable in general by getting an over-deep hash hit in a PV node on an entry from the current search, with a score higher than the current evaluation. Normally you would not do null move in a PV node, though.

Perhaps rep detection should recognize reepetition of positions with the other side to move, and trigger some special code for them. Normally I store the hash key without stm correction in the repeat stack, and run through it in steps of two to compare only positions with the same stm. But in a PV node you could also compare the key of the position you want to move to (where the opponent has the move) with the positions when you had the move. If there is a match there, you have effectively played a null move with a sequence of real moves. Which is fishy if you are supposed to be heading for a gain; a null move is usually not a good start for winning something. (In positions where zugzwangs can be expected, this should obviously be switched off.) You could incorporate a flag in the PVs that you back up, saying "watch out: here you have lost the turn compared to the position on ply X". When the node at ply X would have to backup this PV as the new one, it should think twice before doing it. I don't think it would be crazy to have it explicitly play an unreduced null move as verification that the conclusion this move is good also holds if you would not have reduced the effective depth by taking the detour.

Of course you could also have given a hefty extension at the point where you reached the pseudo-repeat, giving all the depth back that was lost in pursuing the detour. I am not sure if this could give rise to search explosion. In principle it would be equivalent to having searched (unreduced) null move in the node where the position occured before (with the other stm), which would not be explosion-prone. This would do something path-dependent to the node, namely extending it. But that would not interfere with hashing: you would store it with a draft equal to the extended draft, and that would be equally valid for hits that reach it through another path. They just might not have a reson for extendeing it. But deeper is supposed to be better, so they are just lucky in this case. Which occurs quite commonly anyway.