MTaktikos wrote: ↑Sat Oct 15, 2022 10:27 am
Although your idea, to produce a normal chess game tree and then simply prune away the parts to be vetoed, looks at first glance interesting, I don't agree with it. Because in my implementation there appear sometimes positions where a King runs straight in check and blocks it afterwards with the Duck, so here are produced moves that could not have been produced by a normal chess movegenerator.
Depends. Some people return illegal moves as well because they will get verified later. Here the duck can be implemented the normal way.
Branching factor is interesting tho. It's a decrease of possible moves normally but a duck can extend the legal moves also.
It's state is not part of the tree, but then it might get pinned? (Sorry don't know the exact rules) in which case it's part of the tree while that's the case. On average I would expect it to decrease branching factor.
Other than that a knight can only get blocked 1/8 while rooks often get blocked totally. Arguably the value of 300cp for knights and bishops cannot hold. Knights seem to be more valuable.
Normally my move generators generate all pseudo-legal moves. So no problem at all with moves that are stepping into check. As long as you can veto the resulting King capture. So stepping into a contact check or double check would be punished.
hgm wrote: ↑Fri Oct 14, 2022 10:14 pm
Very simple variant. The branching ratio is not relevant. There are only about 32 times as many game states as without Duck. So after the first ply all Duck moves will be tranpositions, and only the root has more moves than normal Chess.
But even without TT it would not be hard to search. The only function of the Duck is to prevent the opponent's best move in the next ply. After that it can again be anywhere. So if you do not prevent the opponent's best move with the Duck, you might as well have taken it off the board; he will simply play his best move, and drop the Duck back onto the board.
So you first search the position without Duck, and then assume the Duck has been placed on one of the squares the best move passes through. Rather than just keeping track of the best move, you also keep track of the second best with another piece or in another direction. (In this respect it differs from Veto Chess, where you keep track of the second-best per se.) If the path of that second-best move intersects that of the best, then both can be 'vetoed' by placing the Duck on the intersection, and you would even need the next-best move. Moves that can be 'ducked' would not increase alpha, but as soon as the set of moves that already have received a score cannot be ducked all at once, alpha is increased to the worst that you cannot block.
There is still one complication: you must move the Duck, so you can get in 'duckzwang'. Once you have concluded what the most-annoying location of the Duck is in a certain node, you should communicate that to the parent, and the parent should also consider that you would have placed the Duck there on your previous move, rather than blocking his best. This is only needed if there is exactly a single way to block the best move. If the opponent has multiple ways to block your best move, he will never be in duckzwang. If he has none, it doesn't matter at all where he places the Duck.
So in short: you will not make the Duck part of the game state, but only search the FIDE part, pruning one or more of the best moves in every node.
I think you are underestimating this variant. It contains many unexpected surprises. How it alters play is much more substantial than what is readily apparent. Example: On the 1st move, White can play 1 e4@e2 and after Black plays their reply, the Duck must get moved off e2 enabling either Q or B or both to develop to wherever they please. So you see, it isn't just about blocking your opponents move, the Duck can also be used to keep yourself unblocked.
Try mating with K + R vs K for a taste of what is possible. The Duck totally changes the procedure. I'm able to do it, but I'm quite sure I am very inefficient. Note too that K + B vs K, K + N vs K can be quite winnable. I would be very much interested in a 3 and 4 man EGTB for the game.
It is not for nothing that this variant has become so popular. It contains many surprises that make it fun.
This is just the 'duckzwang' complication I mention above. It would not occur in 'Unforced Duck Chess', and I am pretty sure it could be solved elegantly in the real Duck Chess. The point is that besides determining how much the opponent's Duck move could have hindered you in playing your best move(s), you should also consider how much you could have suppressed the score of his best move by securing a better reply to it (by making his best veto impossible). And I don't think this would require an extra search. Each node can return the score in case of optimal blocking of his own moves, but also (higher) scores in cases various blocking squares would not be available. This would not require extra searches, it follows from altering the set of moves that can be blocked, and repeat determination of the best of the remaing. The parent can then use these scores to see how much it would get from the various Duck plays that would not prevent the opponent's best move.
One thing still seems valid: a Duck placement that does not block the opponent's best move, or block your own best reply to it (so that the opponent must unblock it with his Duck move), it will have no effect. So the number of Duck placements that have to be considered is very limited.
To convince the unbelievers, let me give a more formal desription of the search algorithm I have in mind:
First of all, note that the search tree consists of levels that alternately move a FIDE piece and a Duck. The same player during his turn first makes the FIDE move, and then Duck. But when we treat the search recursively, there is no need to treat the full turn of a player in a single node. We could have separate routines for searching Duck and FIDE moves calling each other. Or we could have a single recursive routine that first plays a Duck move of player A, followed by a FIDE move of player B. We will go for the latter design. This also seems to terminate move sequences more naturally in the leaves; After the FIDE move the position is by definition quiet, as the Duck move cannot be a capture or promotion, and at most would make a posiitonal contribution to the evaluation.
That one node combines levels of two players o f course means we cannot just take the value of the node as the maximum of all move combinations, but we must minimax the scores within the node. Within a node we will define the scores from the POV of the player that makes the FIDE moves; this means the scores resulting from the FIDE moves are maximized, but those from the Duck moves are minimized, and the minimum is returned from the node. The caller will than flip the scores, as is usual in negamax.
Rather than making a tree where the nodes connect through individual moves, we will merge all nodes that have the same position for the FIDE pieces. The reason is that the move list for positions only differing from each other by location of the Duck can be trivially derived incrementally from each other, by suppressing some of the moves from a list made when no Duck was present at all. So we only do a single move generation. The node then trats all Duck locations at once. That means scores are not just numbers, but an array of 64 numbers, one for each Duck location, which we will call a 'bundle'. (Not all elements in the bundle will be used; only those corresponding to empty squares.) So each FIDE move will receive a bundle of 64 scores from a child node, and return a bundle of 64 scores to their parent.
At fist glance the scores in a bundle could all be different, and when the FIDE level is maximizing each elements over the moves, the fact that different subsets of the moves contribute to different elements (because whether these are blocked or not depends on teh Duck location) could even create more inhomogeneity in the bundle that results from the maximizing. Formally we should, for each of teh 64 elements in the bundle, calculate the maximum over the FIDE moves of the corresponding bundle elements received from the child. ANd then apply a minimizing step over Duck moves on those, to return an entire bundle of scores. That sounds like a lot of work.
But the Duck is so mobile that the minimizing over the Duck moves will almost completely eradicate the inhomogeneity. Of all elements in the maximized bundle, one element (corresponding to one Duck location in the position from which the FIDE moves were made) will be the smallest. All positions with the Duck elsewhere will be able to reach this through a Duck move, and will thus all get that same smallest score in their minimizing step. Only the element that has the Duck in the same location cannot reach this; it gets the score of the second-lowest score in the maximized bundle. (And that might even be the same score.) So a bundle returned from a node will contain only 2 values: a unique one attained by only a single element of the bundle, and a 'common' one attained by all other elements. This could be encoded as two score values, plus a variable indicating which Duck location gets the exceptional one.
This will also limit the inhomogeneity that can accumulate in the maximized bundle. The FIDE moves will be treated one by one (through the usual MakeMove/UnMake), and their search will return a bundle of scores, 63 common scores and one exception. This will have to be combined with the maximum-so-far to get the maximized bundle including the new move. Suppose we also encode the maximum-so-far as a common value plus a list of specified exceptions. If the new move contains an exceptional score for a new Duck location (that was not exceptional in the maximum-so-far), and this is larger than the common score in the maximum-so-far, this will add a new exception. So the number of exceptions can grow as we treat more FIDE moves. It can also happen that a common score of a new move is higher than a lot of the exceptions in the maximum-so-far as well as the common score, and in that case they all get the new common score, and are no longer exceptions.
Note that FIDE moves that are not compatible with a certain Duck location would not increase the score of the corresponding elements in the maximum-so-far. This could lead to additional inhomogeneity in the maximum-so-far (i.e. creation of more exceptions). The algorithm for updating the maximum-so-far bundle would thus be:
* We assume the maximum-so-far score is kept as a mailbox board of scores.
* Together with that we keep a bitboard ex that marks which squares have scores different from the maximum-so-far common score. This tells us which elements of the mailbox board are valid.
* The latter is updated by the common score returned by a child in the usual way (i.e. as the maximum).
* We determine (as a bitboard b) which Duck locations would block the move to the child, and which would get the common score (bitboard c).
* If the common score was increased, the moves in that set which were not yet exceptions (b & c & ~ex) become exceptions (ex |= b & c) and get the old common score.
* Existing exceptions that do not block the move (ex & ~b & c) get their score increased to the common score returned by the child (if they had lower score before). If this makes their score equal to the new common score they cease to be exceptions (and their bit in ex gets cleared).
* If the exception returned by the child already was an exception and does not block the move ((~c & ~b & ex) != 0), its score becomes the maximum of its old score and the returned exception score.
* If, OTOH, it was not an exception and doesn't block the move ((~c & ~b & !ex) != 0), it gets a score max(oldCommonScore, returnedExceptionScore), and becomes an exception (ex |= ~c) if this is different from the new common score.
After all moves have been searched we can determine what is the lowest of all the scores (common or exceptions). That score will be returned as common score. If it was the score of an exception at square s, and no other exception has the same score, we return the one-but-lowest score as the exception at s; otherwise there is no exception returned.
Well, I suppose I could adapt the WinBoard Alien Edition, which already supports general multi-move games. So what remains is the problem that both players must be able to move the Duck. Which could be most easily implemented by 'promoting' the Duck to a Duck of the opposit color. An alternative would be to implement it as an Amazons variant, where after each move of a Queen you have to click an empty square to drop an Arrow there. This could indicate the new Duck location, without a need to select the Duck, like a new Duck is dropped. In that case the modification should be to remove the Duck from its old location after every drop.
I uploaded a version of the WinBoard Alien Edition to my website that implements Duck Chess. I bundled it together with a dummy engine (a N.E.G. derivative, which moves the Duck randomly) for testing the communication protocol. And with a version of UCI2WB that should be able to handle multi-moving. (I had nothing to test that on.) The included ini file configures WinBoard to use that as UCI adapter.
There is no way yet to select Duck Chess from the menu; to play it you have to specify the additional option
-variant duck
in the Startup Dialog.
For the user interface you have to click the square where you want the Duck to go after you entered the move. You should not try to select or grab the Duck. WinBoard will treat it as if the Duck came from the new location of the FIDE piece you moved. This had the advantage that the piece that moved stays highlighted. It leads to a somewhat quirky notation of the moves, though, e.g. e2e4,e4f5 if you wanted to put the Duck on e5. But the 'from-square' of the Duck can be ignored anyway, as it should always be clear where the Duck came from.
BTW, I assumed that at the start of the game the Duck is off board. I am not sure whether this is the official rule. But it should make no difference compared to starting it somewhere in the black half of the board.
