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.
Custom fairy pieces in Fairy Stockfish
Moderator: Ras
-
hgm
- Posts: 28529
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
hgm
- Posts: 28529
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Custom fairy pieces in Fairy Stockfish
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).
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
- Posts: 28529
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Custom fairy pieces in Fairy Stockfish
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.
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
- Posts: 28529
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Custom fairy pieces in Fairy Stockfish
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.
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.