Pointless delays

[hgm]

[d]k6r/5ppp/8/7R/8/8/4PPPP/6K1 w

What annoys me in engine play is that they often waste time on completely pointless threats. Like in the above position 1. Ra5+ Kb8 2. Rb5+ Ka8 3. Rf5. It could have played 1. Rf5 immediately. Presumably it interjects the 4 extra ply because Rf5 turns out to be not so good as it looks when searched at high depth, and looks better at low depth. In other words, the engine conveniently blinds itself to make poor moves look good, by reducing the search depth through playing a few forcing moves.

This cannot be good for playing strength. In any situation where such a pair of forced back-and-forward moving is possible, it can basically insert them as often as necessary in any branch, to tune it such that bad repercussions of foolish moves are just behind the horizon.

Has anyone ever tried a fundamental solution to this? The key in recognizing it seems that a piece moves to a square where it could have also moved directly from its previous location. My first thought would be: "you cannot move Rb5-f5 now, because that would give the same position as you could have reached 4 ply earlier, so if it was any good, youshould play it there (so you investigate it at larger depth)". In other words, prune such moves. This could lead to bad pollution of the hash entries for the intervening positions, however, if the pruned move was the only acceptable one.

Another method would be to not count the four time-wasting plies in the depth, i.e. extend this branch with 4 ply. This does sound very expensive, potentially explosive. OTOH, you only do it in positions that could have been reached in one move 5 ply earlier, and if they would not be pruned there (e.g. by alpha-beta), they should be searched there to the same depth anyway. So it seems that you would never search more than you would have searched the move there (and picked it up from the hash here). Which sounds quite innocent.

Of course the question still remains how to detect it in the first place. One way would be to maintain a list of all hash keys of positions that could be reached by one move from any node on the path to the current one. But that might be pretty expensive: you would basically calculate daughter hash keys during the move generation, to store them in a hash table that remers to which depth you are going to search those moves, and remove them from that table again when you return from the node.

[Brunetti]

What annoys me in engine play is that they often waste time on completely pointless threats. Like in the above position 1. Ra5+ Kb8 2. Rb5+ Ka8 3. Rf5.

Your analysis is very interesting but I've just tested the position on the following engines:

Deep Rybka 4.1
Houdini 3 Pro 64
Senpai 1.0
Critter 1.6a 64
Firebird 1.2
Toga II 3.0
Fruit 2.1
Chiron 2 64
Hakkapeliitta 1.0 64
Protej 0.5.8c
Protej 0.5.7
Stockfish DD
Gibbon 2.42c

and none of them plays the checks (up to depth 15/25)

Alex

[Sery]

What annoys me in engine play is that they often waste time on completely pointless threats... Has anyone ever tried a fundamental solution to this?

I think I have an idea.
In my engine I have evaluation function which depends on amount of reversible moves been made. If current node is a leaf node and all moves in a search were reversible, then value of position is decreased towards zero. The more reversible moves is done, the less absolute value of position.

Code: Select all

    // somewhere in the end of evaluation function
    if(reversibleMoves > ply)
        value = value * (FIFTY_MOVES - reversibleHalfMoves) / FIFTY_MOVES;

, where FIFTY_MOVES is equal to 101.

Maybe I'm wrong, but I think that's the way my engine tries not to make pointless moves.

[AlvaroBegue]

What annoys me in engine play is that they often waste time on completely pointless threats... Has anyone ever tried a fundamental solution to this?

I think I have an idea.
In my engine I have evaluation function which depends on amount of reversible moves been made. If current node is a leaf node and all moves in a search were reversible, then value of position is decreased towards zero. The more reversible moves is done, the less absolute value of position.

Code: Select all

    // somewhere in the end of evaluation function
    if(reversibleMoves > ply)
        value = value * (FIFTY_MOVES - reversibleHalfMoves) / FIFTY_MOVES;

, where FIFTY_MOVES is equal to 101.

Maybe I'm wrong, but I think that's the way my engine tries not to make pointless moves.

That would discourage pointless moves when you are ahead, but encourage them when you are behind. However, there is some value in doing that, because if you have enough pointless checks available you can draw the game.

[Sery]

Álvaro, yes, I've got nothing to do with pointless moves in a 'future' (inside search tree). I think my idea may be useful to avoid playing pointless moves by engine due to sorting of root candidates after each iteration.

[hgm]

Your analysis is very interesting but I've just tested the position on the following engines:
...
and none of them plays the checks (up to depth 15/25)

This was just a synthetic position I pulled out of the hat to explain the problem. To really make them play the checks, there must be something behind the horizon for the immediate move, which is not the case here.

The real-life case that started me thinking about this is from Shogi (where Pawns capture straight ahead, and captured pieces can be dropped), so I figured it would not be the best example to use here. It looks somewhat like this:
[d]6nr/4kbb1/pppppppp/8/8/8/PPPPPP1P/6R1 w
1. P@g5 {the dropped Pawn threatens to capture g6 and promote there, forking the Bishops, a threat so severe that it almost never can be ignored} 1... Pg6xg5 2. Rxg5 {threatens 3. Rxg7} 2... P@g6 {Rg5 is now hanging and must retreat}

This sequence can happen any time a Rook is aimed at a weak (only once protected) spot in the opponent's Pawn wall, which is quite common. Even super-strong engines like Bonanza frequently play it. The Rook often has no better move than to retreat where it came from, (3. Rg1), giving up a pure tempo, or just does a net pointless move along the g-file, handing the turn back to the opponent. Which then does the first move of his plan the result of which was so conveniently pushed over the horizon, after which the sequence is performed again to give up another turn, etc. An additional problem is that once white starts this manouevre, there is no way to abort it without loss of material.

@Sergey:

Agreed, penalyzing reversible moves this way would discourage it (when you are ahead). But only by a little amount, while the problem that is pushed over the horizon can be arbitrarily bad. So the engine would still blind itself against being mated or losing a Queen, by believing that the delaying checks would save it at the cost of the moderate penalty. (It could for instance grab a poisoned Pawn that would get it mated, thinking it can dodge the mate just by incurring the penalty for 4 reversible moves, which would make it worth it.) I would want to force it to consider the actual consequences of the immediate move when it is judging the branch where it is stalling. Of course in the example a check extension already helps combatting the problem (you stall only 2 ply, rather than 4). But you could also chase an unprotected Bishop or Knight in stead of checking, and there are no extensions for saving those.

Also note that in the Shogi case, there aren't any irreversible moves ever, as captures can always be undone by drops.


I did get an idea for facilitating recognition of this, however. When you can reach a position that you could have reached before in a single move, it means that the opponents pieces must all be in the same location. So if you would keep separate hash keys for the white and black pieces, you could check whether the opponent's key is a repeat, and only if it is, do more extensive checks on your own pieces.

To prevent that you have to update two keys, you could make all Zobrist keys for the white pieces have one half of the bits (e.g. the odd bits) zero, and for the black pieces the other half. I am not sure if this increases the chances on key collissions too much, however. An alternative could be to give all white pieces keys that have (say) bits 56-63 cleared, and the black pieces 48-55. That would mean that bits 56-63 are only affected by the black pieces (castling, e.p. and stm keys could have 48-63 cleared). So by comparing this byte with all keys in the repeat table, you could detect possible candidates for 'half-repeats'. With 8 bits you would expect 1 in 256 tries to be false positives, but that is low enough to do something very complex in that case without having a measurable impact on preformance.

In the Chess case testing for an actual repeat of the opponent's position 4 ply earlier could be done by checking if the two moves the opponent did in that sequence are each other's inverse. With drops it would be more complex, however. A necessary condition is that the opponent would have dropped what he captured in the other move (or the hands would not be the same), in the location where his board move started, and that the piece he moved was of the same type as the piece he captured, and would be captured itself in the sequence (or he would have more pieces of that type on the board).

I still wonder if the rule "extend 4 ply when the last 5 ply amount to a single move" would give an insignificant or a disastrous slowdown. I guess there is no way to find out other than try it.

[Edmund]

Your problem reminds me of this paper:
https://webdocs.cs.ualberta.ca/~jonatha ... Search.pdf

[hgm]

Indeed, this 'pre-searching' is exactly what I had in mind as a possible solution. (Thank you for the link!) But I would not want to pre-search just any node that occurs anywhere else in the tree (such as those from true transpositions, or when both sides have been wasting time, such as in 1.e3 e6 2.e4 e5 vs 1.e4 e5), but only those where you can reach a node that is a direct daughter of one of the nodes on the current branch. OTOH I would want to do it recursively.

Even if I do the pre-search, when the branch with the pointless delay is searched first, it would still get the same score as the direct move, so it would be preferred. If you are in a position where you have to cede some eval points, and the engine uses a delayed-loss bonus (as all my engines do), it is even worse, and it would always prefer to insert the delay. In that case this is not wrong, of course, but if it happens in the root where it affects move choice, it is still annoying. In Xiangqi this situation also occurs very frequently, when you can give perpetual check (which is usually possible throughout a significant part of almost any game), and just interject as many checks as you are allowed without repeating between all useful move you do. Xiangqi engines therefore often have an option 'give all checks', which can be switched off to suppress this annoying behavior.

I guess this should be implemented by special treatment of PV nodes. You could propagate a flag towards the root to indicate whether the score is based on a pre-search. Or actually backup the level of the pre-searched move. So that when you arrive at that level, it can remove the pointless delay from the backed-up PV, and replace it by the single move from that node that would reach the same position.