Duck Chess
Posted: Sat Jan 21, 2023 11:05 am
I am thinking about generating EGT for Duck Chess. The Duck can of course be treated like an extra piece. This would lead to an extremely large branching ratio, as both the Duck and another piece must be moved independently in each turn, and the Duck can be moved anywhere. It also drives up the memory requirement, by about a factor 64.
A better way to do it seems to not treat the Duck as a piece at all, but let the EGT contain two DTx for each position: one for when the Duck would be in a location where it would hinder the side to move most, and another for the next-best placement of the Duck. The latter is needed because of the rule that the Duck must move and cannot stay where it was. So it can happen that a player is not able to cause maximum obstruction for his opponent, because the Duck was already at the required location before his move. Only in that case he would move the Duck to the second-best location; in all other cases he is allowed to (and would) move it to the best.
Of course it would also have to be stored what the location of the Duck must be for maximum obstruction. So each position would require storage of a 6-bit square number and two DTx. That is still a lot better than having to store 64 DTx (one for each Duck location), which would be the case when the Duck was treated as a piece. The proposed scheme can be viewed as a compression technique that makes use of the fact that for a given position of the FIDE pieces most Duck locations are equivalent, and thus have the same DTx. The large mobility of the Duck is the cause of that; it doesn't matter much where the Duck is, because you can move it to where it needs to be from (almost) anywhere.
Note that the DTx stored in the EGT are not the scores at the start or end of a turn, but refer to the situation after the FIDE move, before the Duck is placed. Only at those times the number of DTx is limited to two, because the Duck would be placed in the best location no matter where it is, except in the single case that it already is there. After the Duck placement the same FIDE position could have deviating scores for more than two Duck locations, as the best move could be blockable on more than one square, and the DTx for those placements can depend on whether the second-best move is blocked at the same time. But all except two are the result of sub-optimal Duck placement, and thus would not have to be considered in EGT generation.
Retrograde propagation of the DTx becomes a bit more difficult, though. It could be most efficient to first identify all the (FIDE) positions that might be affected by assigning DTx in one iteration through retrograde FIDE moving. And then, for the next iteration, do a 1-ply forward search from each of these. This to prevent that you have to do the rather complex forward search (which will basically be 64 searches, for 64 different Duck locations) multiple times when more than one successor positions have changed DTx.
The forward search would have to determine the best move for all possible Duck placements, and then pick the two Duck placements for which this is worst to get the new pair of DTx for the FIDE position. Most of the Duck placements will be equivalent, though, so the most efficient way to do this seems keeping a 'common score' and list of exceptions (Duck location and corresponding score).
A better way to do it seems to not treat the Duck as a piece at all, but let the EGT contain two DTx for each position: one for when the Duck would be in a location where it would hinder the side to move most, and another for the next-best placement of the Duck. The latter is needed because of the rule that the Duck must move and cannot stay where it was. So it can happen that a player is not able to cause maximum obstruction for his opponent, because the Duck was already at the required location before his move. Only in that case he would move the Duck to the second-best location; in all other cases he is allowed to (and would) move it to the best.
Of course it would also have to be stored what the location of the Duck must be for maximum obstruction. So each position would require storage of a 6-bit square number and two DTx. That is still a lot better than having to store 64 DTx (one for each Duck location), which would be the case when the Duck was treated as a piece. The proposed scheme can be viewed as a compression technique that makes use of the fact that for a given position of the FIDE pieces most Duck locations are equivalent, and thus have the same DTx. The large mobility of the Duck is the cause of that; it doesn't matter much where the Duck is, because you can move it to where it needs to be from (almost) anywhere.
Note that the DTx stored in the EGT are not the scores at the start or end of a turn, but refer to the situation after the FIDE move, before the Duck is placed. Only at those times the number of DTx is limited to two, because the Duck would be placed in the best location no matter where it is, except in the single case that it already is there. After the Duck placement the same FIDE position could have deviating scores for more than two Duck locations, as the best move could be blockable on more than one square, and the DTx for those placements can depend on whether the second-best move is blocked at the same time. But all except two are the result of sub-optimal Duck placement, and thus would not have to be considered in EGT generation.
Retrograde propagation of the DTx becomes a bit more difficult, though. It could be most efficient to first identify all the (FIDE) positions that might be affected by assigning DTx in one iteration through retrograde FIDE moving. And then, for the next iteration, do a 1-ply forward search from each of these. This to prevent that you have to do the rather complex forward search (which will basically be 64 searches, for 64 different Duck locations) multiple times when more than one successor positions have changed DTx.
The forward search would have to determine the best move for all possible Duck placements, and then pick the two Duck placements for which this is worst to get the new pair of DTx for the FIDE position. Most of the Duck placements will be equivalent, though, so the most efficient way to do this seems keeping a 'common score' and list of exceptions (Duck location and corresponding score).