Sven wrote:You may be right. Nevertheless, If I had enough time for such a project I would definitely give it a try because only generating complete release chains sounds straightforward and clean to me.
To start with this last remark: I think we have to distinguish search strategy and implementation. When we agree that release chains should be generated in a perft-like manner, hashing transpositions and detecting repetitions in the process, it becomes so much like normal search that in my minimalist implementation I can use the same function for both, by giving it an extra parameter that restricts the move generation to just one piece (the released one), and doesn't flip side-to-move and eval signs. But that is only an implementation matter. I still can force search of all possible release chains in that implementation, by extending every release move one full ply. Like conventional QS extends all good captures one full ply. So the discussion is really about how much rlease moves should be extended, a full ply or just some fraction of it. Currently I extend 0.75 ply, which protects me from search explosion even without repetition detection, but does cause some undesirable other effects. In a somewhat more advanced engine you could make this dependent on whether it is theoretically possible that a released piece could capture the King (i.e. 'Amazon contact' between the enemy King and a paired piece, and a piece in 'the cloud' that could make that move). You could extend more aggressively whe thi sis the case.
Agreed - following my proposal is certainly not trivial. But I think it should be the right direction, since otherwise you might run into other problems, like not seeing a mate in 1 that would be possible with a very long release chain.
Very true; my engine can currently overlook mate in 1 turn, because the required release chain is too long and exteds beyond the horizon. But so what? If to find that 'mate in 1' by perfting a release tree that is larger that the alpha-beta tree of ordinary moves to find a mate in 4... Why would I then rather see the mate in 1 than the mate in 4? You want to maximize the chances to see any mate, and hunting for those that require very much effort to find before searching for those that could be easy to find doesn't seem a good way to achieve that goal. I realize that mates in the minimax tree are less likely, because the opponent tries to resist them, while in the perft tree it is like searching for help mate. So probably it does help to make the perft tree larger than the minimax tree.
Also I do not understand how you generate "incomplete chains": what do you do with the last piece being released when reaching the horizon (minus one ply)? You certainly do not remove it from the board, so the only way would be to generate normal moves for it and ignore any of its further chain moves.
At remaining depth = 0 I only consider stand pat and King hugging. I set currentEval = -INF for a release node, to suppress stand pat and delayed-loss bonus. So if a release chain uses up the last quarter ply of the depth budget, and cannot capture the King from that point with the released piece, it will score -INF, so it would be preferred to finish the chain on the last ply before the horizon, by playing to an empty square or hugging a lone opponent. So effectively I do not generate incomplete chains, but just refrain from generating chains above a certain length. Which then grows longer on iterative deepening. You could also see that as pruning too long chains near the horizon, and doing iterative widening.
Such a release-chain TT would not be too complicated, and I think it can be quite small. You only need to keep track of friendly non-pawn, non-king pieces that are either part of a pair in the beginning or that start the chain (as a single piece). That would usually be up to 7 pieces, or at most 15, depending on the number of promoted pawns so far. Releasing a pawn makes the former part of the chain non-repeatable.
Well, for detecting repeats the table could be cleared after a Pawn move, but for detecting transpositions you would have to keep everything, because getting to a transposition involves UnMake(). But even then, the number of permutations of 7 pieces can be huge. Look at the following example:
[d]6Q1/8/5B2/3N4/4BR2/2N4k/3P4/8 w - - 0 1
Only the Queen is supposed to be free here; the other white pieces are all paired. Note that Qg3 is checkmate, as the King cannot hug, and cannot escape from being hugged by the Queen. But that is 'hug-in-3' in terms of minimax turns.
Now look what release chains can do. First note that the Knights and Bishops form a 'release cycle': They can alterate BxN, NxB, and after 4 releases get the 'release square' back to where it started. This would 're-activate' the piece that activated them. So after Qxd5-(f6-c3-e4-d5) the Queen is released again (the cycle indicated by parentheses). So the Queen can use d5 as a 'relay point', essentially making two moves. But the pattern of the N & B will have rotated 180 degrees by this, which does not affect their ability to do this. So the Queen can use her second move to step into the cycle at another point, Qxe4-(c3-f6-d5-e4), and the Queen is again activated for a 3rd step. It cannot only emerge from d5, but also from e4! But it doesn't stop there: continue with Qxf4 to release the Rook there, Now the Rook can step into the cycle: Rxf6-(c3-e4-d5-f6), and is re-activated, to go back to f4, activating the Queen for a 4th step. The Queen can also emerge from f6! But it can also countinue the free ride by Qxf6-(d5-e4-c3-f6), then Qxc3-(e4-d5-f6-c3) and finally Qxh3#. A release chain of 26 steps hits the King. There is no other path from Q to K over 'pair squares' than g8-d5-e4-f4-f6-c3-h3, and each step along this path (except the last) takes 4 steps for re-activation.
But now suppose there was a Pawn on d3, blocking the Queens only path to it. We already established a Queen could emerge from any of the pair squares, and certainly a Knight can easily emerge from any of the squares on the B-N cycle. But how about f4? This is a Knight-jump away from the cycle where the Knights are, so there is hope. So start with Qxd5-(...)-e4-(...)-f4, where '...' indicates the B-N cycle (11 steps so far). From there continue with Rxf6 (after two cycles there is again a Bishop there) Bxc3, Nxd5, Nxf4, Qxf6, Rxf4, Nxh3# (18 steps)! This was actually faster than manoeuvring the Queen to c3, and thus could be preferred even without the Pawn.
It seems highly unreasonable to me to require that it should discover these release chains before the simple hug-in-3, just because formally they are hugs-in-1...
(more later).