Custom fairy pieces in Fairy Stockfish

[hgm]

Current Fairy Stockfish allows the definition of custom pieces in its configuration file variants.ini, in which people can specify the rules of chess variants of their own design. To this end FSF has a large number of magic bitboard tables, computed at startup, for a variety of standard moves. Currently it has tables for Rooks, Bishops, the hopping and grasshopping versions of those (which contain the moves between the 1st and 2n obstacle in the path, or the square just after the 1st, rather than the moves up to the 1st obstacle), Nightriders and some lame leapers (Xiangqi Elephant and Horse, Janggi Elephant). Custom pieces can then select any number of those for being used in the generation of their moves, possibly selecting only a limited number of directions the full moves offer. (E.g. for a piece that move forward like a Bishop and backwards along a file (the 'Y') it would use the Bishop and Rook tables, masking away the unwanted slides afterwards.)

Obviously selection from a given set of possibilities limits what you can do to the possibilities on offer. Expanding on that by adding new tables is of course possible, but it just pushes the limits rather than removing those. And it leads to a proliferation of magic bitboard tables, most of which would never be used. (How many variants contain a Grasshopper. Or a Nightrider?)

So I decided to start working on another approach: not use a fixed set of tables initialized at startup, but create tables on the fly to serve the selected variant. The number of pieces in a typical variant might already be smaller than the number of different moves for which tables are now created at startup, saving time on the creation of the tables. In addition, tables can be generated for the board size in use, rather than the maximum supported board size (12x10 in the largeboards version), also saving time. An additional advantage is that the tables can be adapted to the individual pieces, often allowing the move generation to be done with fewer lookups than when using standard tables. E.g. the mentioned Y piece could easily generate all its three slides in a single lookup even on 12x10. While drawing on standard Rook and Bishop tables would have to combine lookups in each of those to generate Queen moves, of which it would then select the Y part using a mask.

So the aim is to automate generation of magic-bitboard tables from an (arbitrary) description of a piece move. This would then also allow implementation of pieces that don't slide along a straight path, but trurn corners, or move along circles. I will use this topic thread to blog on this project.

[hgm]

The way I envision this is as follows. The user will have some way to describe arbitrary piece moves, where a move is defines as the ability to move from the square it is on to a square at some relative position to it along a 'path' (= some collection of squares other than the start or destination), provided some condition on the occupancy of the squares in this path is satisfied. For instance, a slider like a Rook will have many moves in a particular direction, each landing at different distance from the Rook. The path of such a move will be all squares on the ray connecting start and destination (and in between those), and the condition on the occupancy is that all these squares should be empty.

This can be generalized by allowing paths that aren't straight lines, (e.g. a bent slider like the Griffon) or aren't contiguous (e.g. a Nightrider), and requiring a particular square on the path is occupied (e.g. a Grasshopper), or there is just one occupied square anywhere on the path (e.g. the capture move of a Xiangqi Cannon). Never mind how the user has to specify all of this for now, just suppose there is some formal way to specify any move you want.

For setting up magic bitboard, we need a (not nrcessarily very fast) to generate a bitboard with move destinations for a given board occupancy (the attacks bitboards), and a bitboard that tells us which board squares have no effect on the validity of the move no matter of their occupancy (the mask). The process to get those (for a given start square) will start with making a table of all potential destinations, and for each of those the set of squares the occupancy of which determines if the move is valid (the path).

If there are no moves with excessively long paths, a magic bitboard lookup can be used to generate that move as a bitboard (or an empty bitboard, if the move was not valid due to occupancy). Just AND the total board occupancy with the path bitboard, multiply with some constant and then shift to get a 'unique signature' of that occupancy in the low bits of an integer, and use that as index in a table to find the attacks bitboard for that occupancy.

The attractiveness of this method is of course determined by whether you can do this for many moves simultaneously. Many moves have paths containing just a few squares, and those can be combined into a single lookup: by ORing all the paths together to get a mask, the number of squares in that mask might still be small enough to use those for indexing a table with attacks for all these moves without needing excessively large tables.

Particularly attractive is the case where one path is included entirely in that of another. This is the common situation for slider moves: the path to a closer destination is just a subset of that to a more distant destination in the same direction. The paths of such moves can be combined without getting a mask that is any alrger than the longest path in that direction. The closer destinations on that path can then be generated in the same lookup at no extra cost (in terms of table size). Often slides in different directions can be combined as well; in particular straight slides in opposit directions anti-correlate in size: if one board edge constarining slide length is far away, the opposit edge will be close, and the total number of 'blocking squares' in the combined mask will be constant (and hopefully always below the acceptable value).

[hgm]

Outline of an algorithm

To forge these ideas in an algorithm:

Step 1 is to generate every potential move, as a (destination square, path bitboard, occupancy bitboard) structure. These structure are put into a table, and are also put into a linked list for their destination square. (So they must also contain some link to the next element as well.) There is a mailbox board for pointing to the first element of the list for each square, and a bitboard indicating which board squares have potential moves to them.

Step 2 removes duplicats and detours. We should be prepared for a move description specifying multiple moves to the same square. E.g. a piece that makes up to 3 King steps in independently chosen directions has many ways to go from e4 to e5: directly in a single step, via d4, d5, f5, or f4 in two steps, or f.e. via d4 - d5 in 3 steps. All the multi-step moves are redundant; they can be blocked on the intermediate squares, but even if they are the piece can get to e5 using its single step. In general, if for two moves to the same destination the path of one is entirely contained in that of the other, and on that path the two require the same occupancy, the move with the longer path (i.e. the path that is not contained in that of the other, but has additional squares) is a detour, and can be removed. If the paths are equally long the moves are identical, and one of those can be removed.

Step 3 initializes a list of 'lookups'. Each lookup is specified by a mask and a (linked) list of moves (= the structures of step 1). Initially each lookup will contain a single move, copying the path of the latter as mask, and setting a link to point to the move. The per-square lists of the moves can be destroyed at this time. (So using the same link field in the structure now for these new lists.)

Step 4 will combine the lookups. At any stage of this step it will look for the next pair of lookups it should combine. The criterion for this is based on the number of squares in the joined (ORed) and in the intersected (ANDed) masks: if the number of bits in the joined masks is above some value (say 12), the pair is disqualified for combining. For other pairs, we preferably combine the pair with the largest number of common squares (i.e. in the intersection). As a tie breaker we will take the pair with the most squares in the joined masks. The combined lookup will use the ORed masks as mask, and will append the lists of moves to each other; the original lookups are then deleted.

Step 4 will be repeated until no lookups qualify for further joining.

Ideally all lookups can be combined, so the generation of the sliding moves can be done in a single lookup. But for powerful pieces (even a Queen on 8x8 qualifies) their complete move set contains too many blocking squares to make this feasible, and multiple lookups are necessary. E.g. a lookup in the Rook table and one in the Bishop table, ORing the results.

Step 5 determines a magic multiplier for the mask of the lookup.

Step 6 is to initialize the attacks tables for each of the lookups. For this we loop through all possible occupancies of the mask squares. For each such occupancy we generate the actual attacks as follows:

Step 6a loops through the list of moves associated with the lookup. For each move it tests whether the required occupancy for the move matches the current occupancy of the mask on the path of the move (which can be smaller than the lookup's mask, because of the combining). If it does, the destination square of that move is added to the attacks bitboard for that occupancy.

Each piece type will get a variable that specifies (through setting corresponding bits) which magic-bitboard lookups should be performed (and ORed together) for generating the attacks of that piece. This is what FSF currently already does ('RiderTypes'). The difference is that the RiderTypes bits would not have a fixed meaning, referring to a standard set of tables, but would refer to dynamically generated tables designed for the board size and piece types of the current variant.

[hgm]

Riders

Step 4 could be rather expensive. E.g. a Rook on a 12x10 board would have 11 moves along the rank and 9 along the file, 20 in total. That makes 20 x 19 / 2 = 190 pairs of lookups we would have to pick the next to combine from in each iteration, and up to 19 iterations might be necessary to combine all lookups. (In practice we will be left with two lookups that have too large masks to combine, but that still requires 18 iterations.) And remember we have to do that for every board square.

Fortunately pieces with very many moves are usually riders. I.e. pieces that follow the same path for many of their moves, but just to a larger distance. The move generator will produce these moves in order of length. It will traverse the path starting at the piece, adding square after square at the end to extend it, and emit a new move every time it does that. This applies not only to linear sliders like the Rook, but also to riders with bent or non-contiguous trajectories.

The moves belonging to the same ride then have paths that are subsets of the path of the most distant move on that path. That means they can all be combined without producing lookups with larger masks than you already have. This is important, because in the combination process you don't want to 'paint yourself into a corner'. E.g. when the joining of all lookup masks for a piece would give a mask of, say, 20 squares, you would like to end with two lookups each with masks of 10 squares. But combining in the wrong order could at some point lead to three lookups with masks of size 6 + 7 + 7. And those are all too large to combine further. This is the rationale behind trying to combine the largest masks first, so that large masks originate when there are still many small masks around that coul be used to 'top them up' to maximally allowed size.

But if combination of lookups effectively means the one with the smaller mask disappears, whithout altering the mask of the larger one, this would not block any future possibilities for combining. So it would pay to insert an extra step 4a in the algoritm, which loops through the lookups immediately after their creation, to examine consecutive pairs of lookups (which in case they were produced from a ride would be a ride of N and a ride of N+1 steps), and combine them (effectively absorbing the smaller into the larger) immediately. Without trying to look for a better pair to combine. Because you cannot do better as just making a lookup disappear without complicating any other.

So in the Rook case you would not have to consider 190 pairs of lookups to get rid of one (and then 19 x 18 / 2 = 171 to get rid of the next, etc), but would have reduced the number of lookups to 4 (or even lower) by just considering 19 pairs of consecutive lookups. You would be left with 4 lookups, one for the slide in each direction, with a mask size that depends on how far the start square is from the corresponding board edge.

Only then you would try to combine further, but in the first iteration there would only be 4 x 3 / 2 = 6 pairs to consider. On a non-edge square the sum of the mask sizes in the two sideway moves would be 9, and in the two directions it would sum to 7, so you would be left with two lookups in relatively small tables.

[hgm]

Optimizing table size

There is a bit of tension between what is acceptable and what is achievable, and the algorithm I outlined seems to attach too much importance to the former. In particular, when you have a piece that can make 4 sliding moves with each 4 blocking squares, you would want to prevent it arrives at two lookups, with masks of 12 bits and 4 bits respectively. Because that would require attacks tables of 4K and 16 bitboards. While combining the slides differently to have two masks of 8, would require only 256 + 256 = 0.5K. And if it keeps combining lookups to get the largest acceptable mask at every iteration, 12 + 4 is exactly what it would arrive at when 12 is the maximum acceptable mask size.

So it seems prudent to first determine how many lookups you are aiming for, and what would be a reasonable mask size for each of those. If there are multiple lookups the minimum total table size is obtained by having the masks as equal in size as possible. To achieve this we should first OR all masks together, to get the total number of blocking squares. In the mentioned case that would be 4 x 4 = 16. That is larger than what is maximally acceptable, so we will need multiple lookups. But with two lookups it seems reasonable to strive for 8 + 8.

So instead of selecting the pair of lookups for which combining them would produce the largest acceptable mask, we should try to combine such that the mask size is closest to 8. This could be done by using the minimum of joined_mask_size - 8 squared as the tie breaker, (for cases with maximum number of common blocking squares) rather than maximum joined_mask_size.

Another improvement in the combination of the lookups could be made at the point where there are only 4 lookups left to combine. You could then consider every possible way to combine those: 6 where you combine a pair of those, and not the others, 3 where you combine 2 by 2, and 4 where you combine 3 of them.

[hgm]

A move-path generator

Below is the pseudo-code for a move generator

Code: Select all

typedef struct { // structure to specify an individual move with a unique destination
  Square destination;   // number of the square where the move ends
  Bitboard path;           // indicating squares on the occupancy of which the validity of the move depends
  BitboardOccupancy;  // the required occupancy for the above squares
  int next;                   // link for chaining Move structures
} Move;

Move move[MAXMOVES];
int nrOfMoves;

Bitboard reachableDestinations;
int move_by_square;

EmitMove(destination, path, occupancy)
{ // put move in a table
  move[nrOfMoves].destination = destination;
  move[nrOfMoves].path = path;
  move[nrOfMoves].occupancy = occupancy;
  move[nrOfMoves].next = moves_by_square[destination];
  // and into a list
  moves_by_square[destination] = nrOfMoves;
  reachableSquare |= destination;
  nrOfMove++;
}

NextLeg(currentSquare, currentOrientation, pathSoFar, requiredOccupancy, *descriptorTail)
{ // routine for generating moves according to the user's description

  // extract info from descriptor
  directionSet = DIRECTIONS(descriptorTail); // directions in which move can continue
  range = RANGE(descriptorTail);             // rider range (= 1 for a leap)
  multiplier = MULTIPLIER(descriptorTail);   // length of lame or jumping step
  baseStep = STEP(descriptorTail);           // leap of ride (has length 1 when lame or jumping)
  hops = HOP_ON_LEG(descriptorTail);         // whether leg must end on occupied square
  jumps = IS_JUMP(descriptorTail);           // whether leaps jump (rather than being lame)
  final = CAN_END(descriptorTail);           // whether follow-up legs are present and/or mandatory

  // generate next leg
  for(direction = ALL_DIRECTIONS(directionSet)) {

    direction += currentOrientation; // convert relative direction to absolute one
    direction &= 7;                  // there are only 8 directions
    step = Rotate(step, direction);  // aim step into required direction

    // set up ride
    square = currentSquare;
    newPath = pathSoFar | currentSquare; // destination of previous leg is added
    newOccupancy = occupancy;            // desired occupancy of that square was already specified

    for(dist=1; dist<=range*multiplier; dist++) {
      square += step;                              // next square on path
      if(OFF_BOARD(square)) break;
      if(dist % multiplier == 0) {                 // for lame of jumping multiplier > 1
        if(hops) newOccupancy |= square;
        else if(final) {                           // this can be the move's destination
          EmitMove(square, newPath, newOccupancy); // so emit it
          if(final == 2)                           // an optional leg follows
            NextLeg(square, direction, newPath, newOccupancy, descriptorTail+1); // also trace that
        }
      } else                                       // square over which leap passes
      if(jumps)                                    // if leap is mandatory jump
        newOccupancy |= square;                    // require that in the occupancy
    }
  }
}

// Initial call:
NextLeg(startSquare, color==WHITE ? 0 : 4, EMPTY_BOARD, EMPTY_BOARD, descriptor); 

Moves in general consist of a number of legs, where each leg is one or more leaps of a given length in a given direction. (In orthodox Chess all moves only consist of a single leg.) The required occupancy at the final square of each non-final leg can also be specified. (For now capture can occur only on the final destination of the entire move, and for non-final legs that must reach an occupied square the occupant of that square is left undisturbed when the piece leaves again for the next leg.) Repeating of leaps ('rides') never continues beyond an occupied square. Squares on the ray of the ride that cannot be visited can be required to be empty, occupied or don't cares, and if they do not have the required occupancy the ride must end before it reaches them.

Heart of the move generator are the nested loops over directions and distances. The user-supplied move descriptor allows specification of multiple directions, (so consecutive legs can change direction, sometimes in more than one way), and the leap it specified can be made several times in the same direction if the move is specified as a ride (i.e. range > 1).

In each of the iterations of the distance loop the path to the current location is updated, as well as the required occupancy of the squares along this path. Note that (possibly repeated) leaps to non-adjacent squares can either ignore the squares it jumps over, require these are all empty ('lame leap') or all occupied ('jumping'). In the latter two cases the leap in the descriptor is already reduced to unit length, (so that the distance loop also visits the intermediate squares) and a multiplier specifies the true length of the leap (where the leg can end).

If mandatory legs follow, no moves are emitted, but a recursive call is performed for appending these follow-up legs to the move. The latter is also done if the follow-up leg is only optional. But in that case, or if there isn't a follow-up leg, each step along the ride emits a move.

[hgm]

Computing the attacks

Code: Select all

typedef struct {
  Bitboard mask;
  int first, last, next;
} Lookup;

Bitboard ComputeAttacks(Lookup *lookup, Bitboard maskOccupancy, Boolean isHopper)
{
  int k = lookup->first;         // index of first move handled by this lookup in move table
  Bitboard bb = EMPTY_BOARD;
  while(1) {
    Bitboard pathOccupancy = move[k].mask & occupancy;  // obstacles in move path
    int ok = isHopper ? popcount(pathOccupancy) == 1
                      : pathOccupancy == move[k].mask;                 
    if(ok) // occupation requirement satisfied
      bb |= move[k].destination; // so destination of this move is reachable
    if(k == lookup->last) break; // no more moves in this lookup, so done
    k = move[k].next;            // proceed with next move handled by this lookup
  }
  return bb;
}

void InitializeAttackTable(Lookup *lookup, Bitboard attacks[], Boolean isHopper)
{
  Bitboard occupancy = EMPTY_BOARD;
  do {
    int i=Index(occupancy);
    attacks[i] = ComputeAttacks(lookup, occupancy, isHopper);
    occupancy |= ~lookup->mask; // force carry propagation to next mask bit
    occupancy++;                // increment the mask
    occupancy &= lookup->mask;  // delete non-mask squares
  }
}

Initializing the attack tables is straightforward. For each possible occupancy of the mask we have to calculate a bitboard with destinations of all the moves allowed for that occupancy. This is then written in the table in the entry returned for this occupancy.

To calculate whether the destination for one of the handled moves is reachable, we distinguish the case of hoppers from the other cases; for hoppers there must be one occupied square in the path (the mount), without caring where. For other pieces the actual occupancy must be exactly the pattern that the move requires. Which usually is that all squares on the path are empty, but could require some specific squares are occupied instead.

[hgm]

Leaper treatment

The attacks getter in FSF currently works as follows:

For each piece type there is a variable riderTypes, which indicates the lookups that have to be performed in the pre-computed standard tables. The results of these are all ORed together, as well as with a bitboard for the leaper moves of this piece. Since the standard tables are all for fully symmetric pieces (i.e. having the type of ride in all directions), the result is ANDed with a mask that selects the directions for which the piece actually has that type of ride, to account for a possible asymmetry.

This method is not fool proof, and can fail when rides with overlapping paths are involved. E.g. a piece that moves forward like a Rook, and backward as a Dababbarider (moving like a Rook, but only to squares an even number of steps away, ignoring what is on the odd squares). The final selection would then select (amongst others) forward Rook moves. But this would also allow forward Dababbarider moves that would be included in the lookup in the Dababbarider table. So the piece would not only be allowed to move forward as a normal Rook, but could also jump over anything that is an odd number of steps away on that ray. Which was not what was intended.

The proposed method does not have this problem; it would already account for any asymmetry in the attacks table, which were tailored to the piece. For the mentioned piece it would likely do the forward and backward moves in a single lookup. There would never be any moves in the looked-up attacks bitboards that would have to be masked away.

The question is how to handle the leaper moves. These do not require tables indexed by occupancy, as they are independent of any occupancy. So FSF tabulates these specifically for each piece already, taking account of possible asymmetries. The proposed method could do this as well. It doesn't really have to; since the rider tables are piece-specific, the leaper moves could be piggybacked onto the attacks bitboard of one of the rider moves. Not every piece does have rider moves, though. So there is the dilemma of either doing an extra OR with a leaps bitboard obtained by a simple table lookup (rather than by a magic multiplikation of a masked occupancy bitboard) that was unnecessary for pieces with rider moves, or add dummy rides with a zero mask to handle leaps of pure leapers.

There is also a table-size issue, though. (Which can affect speed through cache pressure.) Pieces that slide like Rook or Bishop, but have some additional leaper moves (e.g. as Knight or King) are very common occurrances amongst fairy pieces. If multiple such pieces occur in the variant, not having their leaper moves piggybacked onto the lookup for their rider moves would make them identical, and thus allow them to share their rider table. E.g. in Capablanca Chess there are two unorthodox pieces, the Archbishop and teh Chancellor. Without their Knight moves these would become Bishop and Rook, and could do tehir rider lookup in the table for those. A Queen would have to be split into two rides even on 8x8, as it has too many blocker squares to be handled in a single lookup. And we also might use the ordinary R and B tables as those two lookups.

Totally symmetric orthogonal and diagonal slides are quite common in fairy pieces, and most variants also feature the orthodox Rook and Bishop. It therefore seems best to always add these two rides as standard tables, and then add some code to recognize the case where a custom piece uses these moves (without selecting a directional subset). And then make them use the standard tables rather creating their own dedicated rides (which might lead to duplicats). Their leaper moves, and possibly other rides would then handled by tables specifically made for the piece. Other types of rides, or asymmetric pieces are sufficiently rare to always generate their tables on the fly.