Duck Chess

[h.g.muller]

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).

[koistinen]

Sounds like there might be some fun optimizations there, esp. with the 2 duck positions idea.

[h.g.muller]

I was distracted from this project for a long time. But it seems too interesting to abandon it entirely. In particular it would be fun to make a web applet where you could play the KRK end-game in Duck Chess. Since this is ony a 3-men EGT, efficiency is not really an issue.

For propagating the DTx I designed the following code, which is actually a forward 1-ply search from all positions in the EGT that might need adjustment because some of their successors changed state:

Code: Select all

// retrograde propagation

int bestScore = WORST;      // common score of all non-exceptions
int exception[64];          // score of each exception
uint64_t exceptionMask = 0; // bitmap of squares that currently are exceptions

for(move = ALL_MOVES) {     // loop over moves from current position

  uint64_t blocks = BLOCKER_SET(move); // bitmap of squares where Duck can block this move
  int to = TARGET(move);               // index in EGT of position move leads to

  // probe EGT
  int score = EGT[to].score;           // the 'common' score (e.g. DTM) when followed by optimal Duck placement
  int eScore = EGT[to].eScore;         // the score if we have to move the Duck away from that
  int eSrq = EGT[t].eSqr;              // The best place to put the Duck after the move

  uin64_t placement = 1LL << eSqr;     // bitmap of placement exception
  if(eScore != score) placement = 0;   // exception might not be real
  placement &= ~blocks;                // or unreachable by blocking anyway

  if(score > bestScore) {                          // best common score so far

    uint64_t newBlocks = blocks & ~exceptionMask;  // but Duck locations that block the move don't profit

    while((sqr = NEXT_BIT(newBlocks))) {           // the new ones thus become exceptions
      exception[sqr] = bestScore;                  // and retain the old common score
      newBlocks -= 1LL << sqr;                     // done with this one
    }

    if(placement) {                                                // there is a placement exception
      int oldScore = bestScore;                                    // it used to have the old common score...
      if(placement & exceptionMask) oldScore = exception[eSqr];    // ... if it was not an exception already
      exception[eScore] = (eScore > oldScore ? eScore : oldScore); // and gets the new score if that is better
    }
    exceptionMask = placement | blocks; // only the blocks and placement exceptions are exceptions now
    bestScore = score;                  // all other Duck locations receive the new common score

  } else { // we already had equal or better common score

    uint64_t adjust = exceptionMask & ~blocks & ~placement;  // exceptions that could improve to 'score'
    while((sqr = NEXT_BIT(adjust))) {                        // loop over those
      int oldScore = exception[sqr];                         // their score
      if(score > oldScore) exception[sqr] = score;           // improve it if necessary
      adjust -= 1LL << sqr;                                  // done with this one 
    }

    placement &= exceptionMask;                              // existing exception
    if(placement) {                                          // if not it will not become a new exception
      if(eScore > exception[eSqr]) exception[eSqr] = eScore; // otherwise the best of its old and new score
    }
    exceptionMask &= blocks;    // 
    exceptionMask |= placement;

  }
}

// determine most annoying Duck placements
eScore = bestScore;                      // holds second best so far
while((sqr = NEXT_BIT(exceptionMask))) { // loop over exceptions (which all have lower scores)

  int score = exception[sqr];            // score for this Duck placement
  if(score < eScore) {                   // scores in top two
    if(score < bestScore) {              // hurts most so far
      eScore = bestScore;                // old best is now second best
      bestScore = score;                 // and this one best
      eSqr = sqr;                        // remember best Duck placement
    } else {                             // falls between best and second
      eScore = score;                    // so replaces second best
    }
  }
  exceptionMask -= 1LL << sqr;           // done with this one

}

EGT[this].score = bestScore;
EGT[this].eScore = eScore;
EGT[this].eSqr = eSqr

The assumption here is that each tabulated FIDE position gets assigned a common 'score', which is the DTx when the Duck sits where it hurts most. In general moves to it would place the Duck there. But if it is already there, it must be moved away, and the score for the side to move might be better (in his POV). We call this exception a 'placement exception', and tabulate both its 'eScore' and the 'eSqr' where the Duck has to be before it was moved in the move leading to the position, in order to get this score. In an efficient implementation these three quantities would probably be bit fields in a 16-bit word: 6 bits for the square, and 5 bits for each of the scores (allowing DTx up to 32).

Of course seen from the player that moves to this position, the exception score will be worse. In EGTs scoring is usually absolute, so we cannot use negamax, but have maximizing and minimizing iterations, which use opposit comparisons. The shown code is for a side-to-move (with a FIDE piece) who maximizes the score. But it then also calculate where his opponent would best place the Duck in the move before, which then minimizes.

An array exception[] holds the scores for the exceptions, but an exceptionMask bitmap indicates which of its elements are valid. There can be at most 8 exceptions to the common score, as in Chess a move can be blocked in at most 7 places. These can have a lower score than the common score of the best move, while that same move could provide one placement exception itself. Only few moves have such a long path, though, so the typical number of exceptions is much smaller. And consequently the loops over these exceptions.

[h.g.muller]

I think I got it working. I had a bit of trouble extracting the best move from the EGT in the proposed format. In particular the Duck part. Normally for an EGT that contains both wtm and btm positions you just do a 1-ply search from the current position, to select the target with the best DTM. But for each FIDE move the EGT only contained the best square to place the Duck, and originally only if the score for that Duck placement was different from any other placement.

Which of the two scores would have to be used in determining the best FIDE move could thus be decided by the current Duck placement. But if the DTM was the same, that just meant that the best and second-best Duck placement had the same DTM, so that you could always use one of those even if the Duck already was on the other, and had to be moved. So the score would not depend on where the Duck was, but it could still very much depend on where you moved it to, if it was not one of these 'best' squares.

Storing one of the equivalent best placements as 'exception square' in the EGT did not really solve this. It would offer the opportunity to move the Duck there when this position had the best DTM of all FIDE moves. But if the Duck already was there, you would not know the alternative placement that gave the same score.

So what I finally did for probing, once a FIDE move was selected that would give the best DTM for the current Duck placement, is redo the 1-ply search from that target position that is normally done for retrograde propagation. This would give you the DTM of that position for every Duck placement, as a common score and a number of exceptions. From which the best two scores and best Duck locationare then chosen for storage in the EGT. But the second-best Duck placement at that point is also known, and could be returned by the routine even if not used for storage in the EGT during propagation. This is then where it moves the Duck when it was already in the primary location.

Note that in an engine you would only need the best move in the root, where you actually have to play it. Other EGT probes are only interested in the scores and the exception square, niot by which move this score could be reached.

I forged the EGT generator and the routine to probe it into an engine, which can play the Duck Chess KQK, KRK, KBK and KNK end-games as 'variant egt-D' onder the WinBoard GUI, as a sub-variant of Duck Chess ('variant duck'). I was lucky that even the longest mate (KBK) takes only 30 moves, so that 5 bits was indeed enough to encode the DTM. Forcing mate in KNK is a bit easier (27 moves). KRK took 23 moves, KQK only 11. The end-game you want can be selected through an engine option 'piece'. As soon as you request the engine to think it will generate the corresponding EGT, and from then on only probes it to pick the moves while you play against it.

The engine can be downloaded from http://hgm.nubati.net/transfer/duckegt.exe .