Duck Chess EGT
Posted: Mon Mar 25, 2024 11:38 am
As a 'prove of principle' I tried to write an EGT generator for 3-men Duck-Chess end-games. The code still is horribly inefficient, but who cares? For 3-men it will always be fast enough. I didguised the generator as en engine, so that it can play according to the table it generates.
The algorithm I used doesn't treat the DUck as an extra man, so there are only 64^3 = 256K board positions in the EGT. (Strictly speaking 64*63*62, but I leave in the broken positions; most of those can be thought of as giving a peek into the 2-men EGT one converted to by capturing the piece that occupies the same square, and are scored accordingly.) Each board position is represented by a 32-bit int, the upper half for the black-to-move position, the lower half for white-to-move. Each of these 16-bit halves contains three bit fields: two DTM each 5 bit, and one 'exception square' of 6 bit.
The first DTM is the score this position has if the Duck is on the exception square (usually to block the best move from that position). The second DTM is for when the Duck was placed in the second-best position, to which you have to fall back if you could not put it in the best position, because it already was there.
This seems to work well for generating the EGT; The DTMs it calculates seem to make sense on optical inpection. An interesting aspect that I had not forseen is that Bishops (and probably Knights, although I did not try that yet) also appear to have mating potential in Duck Chess.
I encounter a problem in extracting the best move from the EGT, though, rather than just the evaluation. Usually one does this through a 1-ply search, and pick the best evaluation. That is true here too for the FIDE move. But it doesn't tell you where to place the Duck. In particular, if the best move can be blocked in two places, the perfect play assumed by the EGT would always be able to block the move, no matter where the Duck was: if it was in one of the places, you just move it to the other. The two DTM for the position are equal, and there is no exception. But that doesn't exclude that placing the Duck anywhere else is completely fatal (such as not blocking an attack on your King). Even if I would record the position in the EGT as a 'fake exception' with two equal DTM, arbitrarily picking one of the possible blocking squares as the exception, it would not tell where to move the Duck if it happened to be already there.
I hope I can find a solution for this that doesn't require storing of the second-best Duck placement in the EGT. Perhaps a two-ply search when playing.
The algorithm I used doesn't treat the DUck as an extra man, so there are only 64^3 = 256K board positions in the EGT. (Strictly speaking 64*63*62, but I leave in the broken positions; most of those can be thought of as giving a peek into the 2-men EGT one converted to by capturing the piece that occupies the same square, and are scored accordingly.) Each board position is represented by a 32-bit int, the upper half for the black-to-move position, the lower half for white-to-move. Each of these 16-bit halves contains three bit fields: two DTM each 5 bit, and one 'exception square' of 6 bit.
The first DTM is the score this position has if the Duck is on the exception square (usually to block the best move from that position). The second DTM is for when the Duck was placed in the second-best position, to which you have to fall back if you could not put it in the best position, because it already was there.
This seems to work well for generating the EGT; The DTMs it calculates seem to make sense on optical inpection. An interesting aspect that I had not forseen is that Bishops (and probably Knights, although I did not try that yet) also appear to have mating potential in Duck Chess.
I encounter a problem in extracting the best move from the EGT, though, rather than just the evaluation. Usually one does this through a 1-ply search, and pick the best evaluation. That is true here too for the FIDE move. But it doesn't tell you where to place the Duck. In particular, if the best move can be blocked in two places, the perfect play assumed by the EGT would always be able to block the move, no matter where the Duck was: if it was in one of the places, you just move it to the other. The two DTM for the position are equal, and there is no exception. But that doesn't exclude that placing the Duck anywhere else is completely fatal (such as not blocking an attack on your King). Even if I would record the position in the EGT as a 'fake exception' with two equal DTM, arbitrarily picking one of the possible blocking squares as the exception, it would not tell where to move the Duck if it happened to be already there.
I hope I can find a solution for this that doesn't require storing of the second-best Duck placement in the EGT. Perhaps a two-ply search when playing.