Great work and it is nice to know some basic endgame conclusion of a chess variant. I wonder how 3-men duck chess EGT is computationally more complicated compared to 4-men regular chess EGT?
Duck Chess end-game tables
Sort:
It does raise the question perhaps: what popular fairy chess pieces can't checkmate alone in duck chess?
Could an alfil do so, for example?
Alfil and Ferz cannot generally force mate. For Wazir the verdict is still out; my EGT generator encodes the Distance To Mate in 5 bits, so it can only calculate to mated-in-30. (A work-around would be to not caluclate the entire EGT at once, but in DTM ranges; to get the range 31-60 you would then frist calculate all DTM 0-30, and collapse these to the same code used for DTM=0, and then resume the calculation from there. But I have not yet implemented that.) For the Wazir the number of won positions per DTM is still increasing at DTM=30, so my guess is that it is able to force checkmate.
As to the computational complexity: a 3-men Duck EGT should be more comparable to a 3-men FIDE EGT than to a 4-men FIDE EGT. The algorithm I used does not treat the Duck as an extra man. Since storage is usually a bigger problem than computation in EGT generation this seemed the proper thing to do; treating the Duck as a piece would blow up the required size by a factor 64.
Instead I make use of the fact that the Duck location directly after the FIDE move is almost irrelevant, because the Duck is so mobile that it can be placed anywhere no matter where it is. Except for this single exception, when you would want to place it where it already is. So each FIDE position has only two scores, the better one (from the POV of the player who will have to do the next FIDE move) for when the Duck already was at the optimal location, and now must leave that to go to the second best, and the 'common score' for all other Duck locations. So there are only two scores for each FIDE position, not 64. But you have to store the square for which the 'exception score' applies in the EGT as well.
The way I implemented it uses 16 bits per FIDE position, 5 bits for each of the two scores, and 6 bits for indicating the Duck location for which the exception score applies. And I store both the white-to-move and black-to-move info. Normally (e.g. in the checkmating applets at chessvariants.com) I store DTM in 7 bits for black-to-move positions only, and use a single bit for indicating whether the white-to-move position is won, and then do the retrograde propagation in 2-ply steps. So the algorithm I used requires 4 times more memory than a regular 3-men EGT.
Since these were only 3-men EGT, I did not put any effort in optimizing the speed; some things are actually done in an utterly stupid way. (Like extracting the lowest set bit of an integer, for which there exist fast algorithms even if you don't want to use the dedicated machine instruction for this, and I now just loop over the bits.) It only recalculates the DTM for every position in all iterations. A smart algortithm would first 'mark' the positions for which the DTM could have possibly changed, because one of the successors changed, through retrograde FIDE moving, and then not spend time on unmarked positions. But it still only takes a few seconds to generate the EGT.
What about in atomic? I understand only the queen can force a win on her own in atomic (as you cannot take a king if a king is next door); is the same true when you add a duck?
In Atomic even KQK is a draw, if the lone King can connect to the other. (If not it is very easy to force mate with the Queen alone, as you can drive the King to the edge with contact checks.) Even when the King of the strong player is in a corner (say a1) there are still 3 squares adjacent to it, all connected by King moves. So there is no way to force the bare King away from those with only one other piece.
I think that with a Duck you can prevent the bare King from following your own, by putting the Duck on the square you just left. I would have to think some more about that.
I generated some 3-men end-game tables for Duck Chess. If I did it right then it seems that all pieces can force checkmate. For K+Q vs K this takes at most 11 moves, and for K+R vs K 23 moves. K+B vs K is the slowest, and can take up to 30 moves. K+N takes 27 moves.
At first I was surprised that Bishop and Knight had mating potential. But it is of course the Duck that has the mating potential. K + a white Duck vs K would be an easy win. So the player with the bare King cannot afford to use the Duck moves for just hindering the other piece; it must spend them on hindering the King or King + Duck alone would checkmate him. But then it is basically the other piece plus the Duck that will checkmate him.
I forged the EGT generator and a routin that plays according to the EGT once it is generated into a kind of Chess engine, which can be played in the WinBoard GUI (the version that supports Duck Chess).