DuckSlayer: development of a 'bundle engine'

[hgm]

I opened this thread as a blog about the development of an engine for Duck Chess, based on a novel principle. Duck Chess belongs to the same family of chess variants as Refusal Chess. In the latter a turn consists of making a move according to FIDE rules, plus telling your opponent which move he cannot make in reply. Naively Refusal Chess seems to have an enormous branching factor, as there are some 40 moves you could make (39 if you discount the move forbidden by the opponent), in combination with some 40 moves you could forbid. So 1560 different ways to spend your turn. In practice, however it only has any effect when you forbid the opponent's best move; if you forbid any other he will happily make that best move.

So an engine for Refusal Chess can be quite simple; you do the normal negamax, but do not back up the best score towards the root, but the second best. The true branching ratio will still be around 40, because there is no real choice which move to veto. Rather than explicitly figuring out what to veto, you will just evaluate the moves in the normal way, and assume the best one will have been forbidden by the opponent in the previous turn. The effective branching ratio when using alpha-beta will be higher, though, as you now will need at least two moves above beta before you can cut off, as one of the two would be vetoed.

Duck Chess is very similar in spirit. Instead of forbidding a single move you can forbid the opponent to do a number of moves, by placing an obstacle (known as 'the Duck') on an empty square. This then blocks all moves over or to the square. You can place this Duck in at least 32 different locations, and this grows as the board gets emptier, superficially causing an enormous branching factor in combination with your 'FIDE move'. But the search strategy can be the same as in Refusal Chess: just search all FIDE moves like always, and then assume that the Duck will be placed such that as many of the top moves will be blocked, and back up the score of the best remaining one to the root.

So there is no explicit Duck on the board, that has to be moved around. You just calculate where it should be as an afterthought, as the best placement (for the opponent; i.e. where it hinders you most) the opponent could have given it in combination with the FIDE move he played in the preceding ply. Note that this distributes the turns in a funny way over the nodes: you group the FIDE move not with the Duck placement that followed it by the same player to complete his turn, but with the Duck placement by the opponent in the previous turn. As described so far that would result in a single score of the node. Which might not be the score of the best move, if the Duck could have blocked it. But sometimes it will be, because not every move is blockable. In particular, a contact capture cannot be prevented by the Duck.

Now Duck Chess has one refinement: you must move the Duck. If it already is in the best place to hinder your opponent in the following turn, you cannot leave it there, bt have to put in in a sub-optimal location ('duckzwang'). The Duck-placement algorithm that derives the score of the node has to take account of that. There is a location where the Duck blocks the maximum of best-scoring moves, and if the DUck was anywhere else, you would put it there. But you also have to find a second-best placement where it would go if duckzwang forces it to leave the best. So a node has to return two scores! One 'common score' valid for almost any Duck location, and one exceptional score for the location where there is duckzwang. Often the scores are the same, though: when there are multiple ways to block the best moves, and non of those accidentally blocks the second-best as well, the Duck can always be put on one of those squares, no matter where it was. If there can be duckzwang, though, the node would also have to report to its caller for which Duck location this occurred, to make further propagation of scores to the root possible.

[hgm]

Score bundles

Conceptually processing in a node consists of two stages. First we generate all FIDE moves (as if there was no Duck at all), and search these moves recursively. Each of those will return a (common score), with potentially an exception for one Duck placement. For each of the Duck placements we can then calculate a score, as the maximum of the score of all the moves for that Duck location. We will thus be dealing with a set of maximally 64 scores. We will call this a 'score bundle'.

Most scores in the bundle will simply be the highest common score amongst the searched moves. A score for a given Duck location can be different for two reasons: the move with the highest common score goes over or to that square, so that the Duck was blocking it. This can happen to maximally 7 locations, when the best move was a slider non-capture that went all across the board. Or it could be the duckzwang exception in the common move, which will always score less than its common score, because the Duck could not remain on the square where it harmed the opponent most after that move. So in the bundle that represents the maximum score over a set of moves, we can have at most 9 different scores: 8 individual ones, and then the same score for all others. This latter set of scores represents all locations where the Duck did not do anything useful.

The problem is that we don't want to do this after we have searched all moves. In order to be able to do beta cutoffs we have to keep track of how the scores in the bundle evolve move by move, so that we can take the cutoff as soon as they all get above beta.

We could simply represent a score bundle by an array of 64 scores, one for each square. (And then ignore the elements for squares occupied by FIDE pieces, as the Duck could not exist there.) And update that after the score bundle from a newly searched move comes in, by taking (element by element) the maximum of the score in bundle returned by the newly searched move, and the previous maximum. But since so many scores will be the same (or don't cares) this will involve a lot of unnecessary work. In DuckSlayer I have chosen a less straightforward but more efficient method, as follows:

We keep a single scalar variable which keeps track of the maximum of all common scores. We still have a 64-element array to hold the scores per square, but we keep track of which of these elements contain a score that is different from the common maximum. (Of which there are at most 8.) This could be done through a bitboard indicating the Duck locations that cause exceptional scores, but in DuckSlayer I chose to put the exceptional squares in a linked list. (So there are also two 64-element arrays for the forward and backward links.) That makes it trivial to run through all exceptions (while((sqr = next[sqr]) != ENDCODE) {}, where a bitboard would need a bit-extraction loop), and also not too much work for adding or deleting an exception to/from the list (which for a bitboard would just mean clearing or setting the corresponding bits).

For each existing exception we would have to check whether it will remain an exception; if the move is valid for that Duck location, and raises the common score, and the Duck location is not the exceptional score of the move, the score for that Duck location would also be raised to the common maximum, and ceases to be an exception. OTOH, when a move raises the common score, Duck locations that block that move, or which were the (single) exception in the returned bundle, now become new exceptions in the maximum bundle when they weren't exceptions already.

DuckSlayer handles this by running through the linked list of existing exceptions, for each of those testing whether their score should be raised (and whether that would remove them as exceptions). It also keeps a set of Duck locations that would block the current move, and removes the exceptions that were in the list from that set. Remaining Duck locations that would block the move would become exceptions if the common score was raised by the move. So only in that case, we run through the set to add these to the linked list of exceptions, with the old common score. If the exception of the returned bundle was not yet in the exception list, it has to be added as a new exception as well. (Again, only in the case that the common score is raised by the move; if not the exception score would not raise it either (as it is always lower), and all the moves that had the common maximum score will just keep that.

The return bundle

After the maximization of scores over all FIDE moves we are thus left with a score bundle consisting of a common score, and a linked list of up to 8 Duck locations with deviating (lower) scores. The opponent would want to have put the Duck on the square that gave us the lowest score, which will be one of the exceptions (if that list is not empty). For the case the Duck was already there, he is in duckzwang, and will move the Duck to the location with the second-lowest score. So what we do after having searched all moves (or in case of a beta cutoff: sufficiently many cut-moves) we will have to run through the list of exceptions to find the lowest two scores (and if the list contains only 0, or 1 exception, the missing ones will be the common score). The lowest one will be returned as the common score of the node (all Duck locations but one would put the Duck on the square that had that score), the second-lowest will be returned as the exception.

The exception square will be the square that has the lowest score. At ply level 1, we will also have to return the square where the Duck pushed down the score to the second-lowest value, for the benefit of the root: should the Duck already be in the best position, the root will have to know where it should be moved as the next-best alternative, in order to output the move we want to play. This is a consequence of dividing up a turn over two levels of nodes: the Root (ply level 0) only considers the FIDE moves from the current game position; the best Duck move of that same turn is calculated in the nodes at ply level 1.

It also follows that the root is special: it cannot optimize Duck placement, because that Duck placement already took place in the preceding game move. So the Duck location there is known, and the root only has to maximize the returned scores for moves for that single Duck location (be it common scores or the exception) that were not blocked by a Duck in that location.

[hgm]

An Example

To give a practical example, consider the following (approximately equal) position
[fen]6k1/6p1/p6p/5r2/R6n/P7/1PBN1PPP/4r1K1 w - - 0 1[/fen]
White is to move here, and his best move would be RxN, for a score of +3. (Never mind he is in check; he can cure that by putting the Duck on f1, i.e. play Rxh4,f1. Second best would be BxR, which gains him the exchange (+2), as the Rook is protected, and recapturing with the Knight conveniently solves the threat against the latter.

So where would black have best put the Duck to cause maximal obstruction? The best move can be blocked everywhere on the rank b4-g4. But only on e4 would it also block BxR.

Both BxR and RxN have an exception to the returned score, though, namely f1. Both these captures are only viable (and reap their 'common score' +2 or +3) if they can be combined with putting the Duck on f1 to cure the check. If the Duck is already on f1 this cannot be done, and the Duck has to be moved away to the second-best location. In this particular case that is fatal, because there is no second-best location; evacuating f1 will unavoidably expose white's King to capture, and thereby lose the game. (Note a Duck on f1 would also block interposition of the Knight on f1.) So the exception score on both BxR and RxN are -INF, both for square f1. The only move that doesn't have this same exception is Kh2. In combination with that white is again free to move the Duck anywhere.

So after maximization of the bundle scores over all moves, the 'bestScore' bundle will look as follows:
f1 will have score 0 (from move Kh2), e4 will have score +1 (from Rxa6), b4, c4, d4, f4 and g4 will have score +2 (from Bxf5), and all other squares have the 'common score' +3. Note that blocking BxR on d3 or RxP on a5 is possible, but completely pointless, as these were not the the best move.

So white will be maximally hindered by a Duck on f1, and this is where black should have put his Duck in the preceding turn. Except that he would not have been able to do that in the case the Duck was already on f1. In that single case he would put the Duck on e4 for the second-best result (from white POV). So the returned score bundle for this posiiton should have common score 0, and exception score +1 for f1. The 'backup square' would be e4, which would only be of interest when this bundle is returned to the root, and the Duck indeed happens to be on f1 there.

During the maximalization of the bestScore bundle, it would go through the following states:
* after BxR (MVV/LVA-wise the best move), the common score would be +2, for d3 and e4 the score would have stayed at -INF (or alpha, with fail-hard) because BxR would not be possible there, and f1 (the score exception returned from BxR) would also be -INF.
* after a subsequent RxN, the common score would become +3, and d3 would be raised to this common score and cease to be an exception. The score of b4, c4, d4, f4 and g4 would stay at +2 (as RxN would not be possible for those), e4 at -INF (same reason), and f1 also at -INF (because it also is a score exception for RxN).
* after Kh2 the score for f1 would be raised to 0; all other scores stay as they were. Since 0 now is the lowest score in the bundle, we can raise alpha if it was below zero. And if beta was smaller than zero, we could now take a beta cutoff.

Finally, note that the situation would be different if the white King was on h8: then f1 would not be a score exception of BxR or RxN, because white could combine these with moving the Duck from f1 to g1, and still be out of check. So the f1 score would end up as the common +3 score as well, and the returned common score would be +1, with an exception score +2 for e4 (which then would be second best).

[hgm]

Some actual code

The following code indicates how DuckSlayer implements this. And yes, it is tested code! DuckSlayer now actually exists, and is working. For those who don't follow the general Duck Chess thread: it can be downloaded (bundled with WinBoard) at http://hgm.nubati.net/Duck2.zip .

Code: Select all

// global tables and their initialization
signed char rawList[480] *direct = rawList+120, rayLen=rawList+360; // to allow negative indexing

  // Duck Chess direction & ray-length lookups
  dir = firstDir[KING]; // 'pointer' to zero-terminated list of King steps
  while((step = steps[dir++])) {
    for(i=1; i<8; i++) direct[i*step] = step, rayLen[i*step] = i;
  }
  dir = firstDir[KNIGHT]; // 'pointer' to zero-terminated list of Knight steps
  while((step = steps[dir++])) direct[step] = step, rayLen[step] = 1;



// local variables in Search()
unsigned char next[129], prev[129];
int exScores[128];

        // processing (common) 'score' and exception (exScore, exSqr) returned from searching 'move'.
        int lowest = beta, nextLowest = beta, n=0, bestDuck;
        int moveDir = direct[to-from];                      // direction code...
        int moveDist = rayLen[to-from] - (victim != 0);     // ... and length of free path that move traversed
        int k = 128, mask = 0;                              // mask represents squares on ray where Duck could block move
        int ex = (score == exScore ? -1 : exSqr);           // test whether there is a score exception
        if(exSqr == from) exScore = score;                  // the opponent cannot prevent that we put the Duck on our from-square
        if(!ply) {                                          // in root duck location is known; only calculate for that
          int d = rayLen[duck-from];
          if(d > moveDist || direct[duck-from] != moveDir) {// move not blocked by current Duck
            if(duck == ex) score = exScore;
            if(score > bestScore) bestScore = score;
          }
        } else {
          while((k = next[k]) != 128) {                     // loop through existing exceptions
            int d = rayLen[k-from];
            if(d > moveDist || direct[k-from] != moveDir) { // move allowed for this Duck location
              if(k == ex) {                                 // returned exception already existed
                if(exScores[k] < exScore) exScores[k] = exScore;// raise its score if needed
              } else if(score >= bestScore) {
                next[prev[k]] = next[k], prev[next[k]] = prev[k]; // ceases to be exception
                exScores[k] = score;
              } else { // score < bestScore; exceptions remain exceptions, but can still benefit
                if(exScores[k] < score) exScores[k] = score;// raise if needed
              }
            } else mask |= 1 << d;                          // move blocked, but the blocking does not create a new exception
            if(exScores[k] < lowest) lowest = exScores[k], bestDuck = k;
            if(k == ex) ex = -1;                            // kludge to flag returned exception is already in list
          }
          if(score > bestScore) {
            mask = (1 << moveDist) - 1 - (mask >> 1);       // find remaining cases of blocking
            if(mask && bestScore < lowest) lowest = bestScore;
            while(mask) {                                   // make all these new exceptions
#            define BSF(X) asm(" bsf %1, %0\n" : "=r" (bit) : "r" (X)) // assembler for doing bit = NrOfTrailingZeros(X);
              int bit; BSF(mask);
              k = from + (bit + 1)*moveDir;                 // blocking square
              exScores[k] = bestScore;                      // keeps (old) bestScore
              prev[k] = 128; next[k] = next[128];           // add exception to list
              next[128] = prev[next[128]] = k;
              if(k == ex) ex = -1;                          // forget the returned exception, as it blocks the move.
              mask &= mask - 1;
            }
            if(ex >= 0) {                                   // the returned exception did not exist yet, and does not block the move
              exScores[ex] = exScore;                       // give it the returned score
              prev[ex] = 128; next[ex] = next[128];         // and add it to the list
              next[128] = prev[next[128]] = ex;
              if(exScore < lowest) lowest = exScore, bestDuck = ex;
            }
            bestScore = score;
          }
        }

// when returning from Search():
    int k=128, w1 = bestScore, w2 = bestScore, sqr = -1, sqr2 = -1;
    while((k = next[k]) != 128) { // optimize Duck move, by finding lowest two scores
      int s = exScores[k];
      if(s < w2) {
        if(s < w1) w2 = w1, sqr2 = sqr, w1 = s, sqr = k; else w2 = s, sqr2 = k;
      }
    }
    bestScore = w1;
    exSqr = sqr; exSqr2 = sqr2; exScore = - w2 - (w2 < refScore); // return exception in global variables.

  return bestScore + (bestScore < refScore); // delayed-loss bonus

The score processing code in DuckSlayer is actually a bit larger; the section here for the not-root case would work in any situation, but is a bit overkill for the cases where moveDist equals zero or one. So DuckSlayer distingushes those cases, and only applies the shown code when moveDist > 1. For moveDist == 1 it is much easier to test whether the single square where the move could be blocked is already in the exception list, and to figure out which square to add when it was not. For moveDist == 0 there are no blockers at all, so there is nothing to test and nothing to add.

The code with the 'mask' was perhaps better handled as a bitboard; in fact it now makes use of a 'bit ray', where each bit in 'mask' corresponds to a square in the path of the current move. There can be at most 7 of those. The mapping from bit to actual square goes through from + bitNr*moveDir.

[hgm]

Unsolved issues

If DuckSlayer already exists and is released, what is there still to develop, you might wonder. Well, what I have addressed so far is basically just how a minimax search would work when using score bundles. But minimax is of course a very inefficient search algorithm. We would like to use alpha-beta. This poses the issue of manipulating the bounds of the search window. DuckSlayer does some of that, but I have the feeling it doesn't nearly set the window as small as it could be.

A related problem is to extract the PV. In alpha-beta search a move becomes a new PV if it scores between alpha and beta. But when alpha and beta are not optimally determined, this needs not be true. The PV is not a bundle property, but an individual line that uses only a single Duck location of the node that handles it. And this doesn't have to be the best Duck placement; the preceding PV move could have forced it to be the exception.

Finally there is the issue of the Transposiiton Table. We have seen that a single move scoring above beta is not enough to cause a beta cutoff, if that move can be blocked by the Duck. Even an unblockable move might have an exception for the Duck square where you must optimally hinder the reply. You might have to search a number of moves before all scores in the bundle have been raised to above beta. To search a minimum number of moves in a cut-node it would be helpful when the TT stores the set of moves that together can bring the entire bundle above beta. And for causing hash cutoffs, it should not just supply a single score (the common score), but also the exception score and square. As this is what nodes normally return.

[MTaktikos]

Some actual code

The following code indicates how DuckSlayer implements this. And yes, it is tested code! DuckSlayer now actually exists, and is working. For those who don't follow the general Duck Chess thread: it can be downloaded (bundled with WinBoard) at http://hgm.nubati.net/Duck2.zip .

Code: Select all

// global tables and their initialization
signed char rawList[480] *direct = rawList+120, rayLen=rawList+360; // to allow negative indexing

  // Duck Chess direction & ray-length lookups
  dir = firstDir[KING]; // 'pointer' to zero-terminated list of King steps
  while((step = steps[dir++])) {
    for(i=1; i<8; i++) direct[i*step] = step, rayLen[i*step] = i;
  }
  dir = firstDir[KNIGHT]; // 'pointer' to zero-terminated list of Knight steps
  while((step = steps[dir++])) direct[step] = step, rayLen[step] = 1;



// local variables in Search()
unsigned char next[129], prev[129];
int exScores[128];

        // processing (common) 'score' and exception (exScore, exSqr) returned from searching 'move'.
        int lowest = beta, nextLowest = beta, n=0, bestDuck;
        int moveDir = direct[to-from];                      // direction code...
        int moveDist = rayLen[to-from] - (victim != 0);     // ... and length of free path that move traversed
        int k = 128, mask = 0;                              // mask represents squares on ray where Duck could block move
        int ex = (score == exScore ? -1 : exSqr);           // test whether there is a score exception
        if(exSqr == from) exScore = score;                  // the opponent cannot prevent that we put the Duck on our from-square
        if(!ply) {                                          // in root duck location is known; only calculate for that
          int d = rayLen[duck-from];
          if(d > moveDist || direct[duck-from] != moveDir) {// move not blocked by current Duck
            if(duck == ex) score = exScore;
            if(score > bestScore) bestScore = score;
          }
        } else {
          while((k = next[k]) != 128) {                     // loop through existing exceptions
            int d = rayLen[k-from];
            if(d > moveDist || direct[k-from] != moveDir) { // move allowed for this Duck location
              if(k == ex) {                                 // returned exception already existed
                if(exScores[k] < exScore) exScores[k] = exScore;// raise its score if needed
              } else if(score >= bestScore) {
                next[prev[k]] = next[k], prev[next[k]] = prev[k]; // ceases to be exception
                exScores[k] = score;
              } else { // score < bestScore; exceptions remain exceptions, but can still benefit
                if(exScores[k] < score) exScores[k] = score;// raise if needed
              }
            } else mask |= 1 << d;                          // move blocked, but the blocking does not create a new exception
            if(exScores[k] < lowest) lowest = exScores[k], bestDuck = k;
            if(k == ex) ex = -1;                            // kludge to flag returned exception is already in list
          }
          if(score > bestScore) {
            mask = (1 << moveDist) - 1 - (mask >> 1);       // find remaining cases of blocking
            if(mask && bestScore < lowest) lowest = bestScore;
            while(mask) {                                   // make all these new exceptions
#            define BSF(X) asm(" bsf %1, %0\n" : "=r" (bit) : "r" (X)) // assembler for doing bit = NrOfTrailingZeros(X);
              int bit; BSF(mask);
              k = from + (bit + 1)*moveDir;                 // blocking square
              exScores[k] = bestScore;                      // keeps (old) bestScore
              prev[k] = 128; next[k] = next[128];           // add exception to list
              next[128] = prev[next[128]] = k;
              if(k == ex) ex = -1;                          // forget the returned exception, as it blocks the move.
              mask &= mask - 1;
            }
            if(ex >= 0) {                                   // the returned exception did not exist yet, and does not block the move
              exScores[ex] = exScore;                       // give it the returned score
              prev[ex] = 128; next[ex] = next[128];         // and add it to the list
              next[128] = prev[next[128]] = ex;
              if(exScore < lowest) lowest = exScore, bestDuck = ex;
            }
            bestScore = score;
          }
        }

// when returning from Search():
    int k=128, w1 = bestScore, w2 = bestScore, sqr = -1, sqr2 = -1;
    while((k = next[k]) != 128) { // optimize Duck move, by finding lowest two scores
      int s = exScores[k];
      if(s < w2) {
        if(s < w1) w2 = w1, sqr2 = sqr, w1 = s, sqr = k; else w2 = s, sqr2 = k;
      }
    }
    bestScore = w1;
    exSqr = sqr; exSqr2 = sqr2; exScore = - w2 - (w2 < refScore); // return exception in global variables.

  return bestScore + (bestScore < refScore); // delayed-loss bonus

The score processing code in DuckSlayer is actually a bit larger; the section here for the not-root case would work in any situation, but is a bit overkill for the cases where moveDist equals zero or one. So DuckSlayer distingushes those cases, and only applies the shown code when moveDist > 1. For moveDist == 1 it is much easier to test whether the single square where the move could be blocked is already in the exception list, and to figure out which square to add when it was not. For moveDist == 0 there are no blockers at all, so there is nothing to test and nothing to add.

The code with the 'mask' was perhaps better handled as a bitboard; in fact it now makes use of a 'bit ray', where each bit in 'mask' corresponds to a square in the path of the current move. There can be at most 7 of those. The mapping from bit to actual square goes through from + bitNr*moveDir.

Thx for the above piece of code. Although you said that bitboards may had been faster, it's very good to see more understandable code without this everywhere-present bitboards, even if it is 10% or 15% slower. (One of the easiest understandable engines I've ever seen is Evert Glebeeck's Postduif, with a mailbox-movegenerator and accepting move descriptions in Betza notation) A dream will be a fork of Fairy-Stockfish with such a mailbox movegenerator instead of bitboards. It may calculate a bit slower, but without the known limitations of board size and special moves, the development of games will become much easier