for Chess-variant authors

[hgm]

No problem, there is no obligation for any particular piece of software to implement everything. The only thing that is important is that it understands enough to tell it everything it can do.

Currently XBoard has the limitation that it can handle only a single side-effect capture per move. First I thought this would limit it to use at a single 'a', but it turned out this was way too pessimistic: it was no problem at all to have arbitrarily many 'non-destructive' legs. XBoard internally considers those as a single leg. The 'a' modifier in that case is just a syntactical device for specifying which squares should be tested to make sure it is not blocked or can make the obligatory hop. Because its move generator is really a Betza interpreter, it can makes the necessary tests on permissibility of the leg during the decoding.

I understand that compiling for a bitboard move generator might be much more difficult. I don't know how general Sjaak's handling of lame leapers is; if it cannot handle bent paths, then there is little reason to understand the 'a' modifier.

I am still wrestling with how to handle chirality, perhaps you have an opinion on that? The problem is that specifying a direction for a continiuation step that is not strictly linear means something not symmetry equivalent for the left-handed and right-handed Knight moves. This either forces inverse interpretation of 'r' and 'l' on half of the moves as a standard, or forcing separate specification of right- and left-handed moves, which can then each be specified using the normal interpretation of 'l' and 'r' to specify paths that are mirror images of each other.

I now lean to the latter, made bearable by introducing direction-set specifiers 'hr' and 'hl' to select the right-handed and left-handed moves of an oblique atom. The disadvantage is that you would always have to make the specification in duplicate, one for each handedness. But methods to avoid that get very contrived.

[Evert]

I understand that compiling for a bitboard move generator might be much more difficult. I don't know how general Sjaak's handling of lame leapers is; if it cannot handle bent paths, then there is little reason to understand the 'a' modifier.

Essentially, it does "(atom1) followed by (atom2), provided the result takes us to (atom1+atom2, coordinate-wise)". So can decompose the Xiangqi horse as "W followed by F, provided N could go there" or "(1,0) followed by (1,1), as long as it combines to (2, 1)". The latter is actually almost literally what the native move description looks like: "((1,0)+(1,1))&(2,1)". Usual symmetries apply. It can't be combined with sliding and there can only be two atoms to define the first leg. Sjaak has a more flexible definition of what constitutes an atom though: it's basically any type of leaper you have defined, so if you define KN, you can specify that as the first leg.
Having said that, I've only ever tested it for atom1=W or F.

I am still wrestling with how to handle chirality, perhaps you have an opinion on that? The problem is that specifying a direction for a continiuation step that is not strictly linear means something not symmetry equivalent for the left-handed and right-handed Knight moves. This either forces inverse interpretation of 'r' and 'l' on half of the moves as a standard, or forcing separate specification of right- and left-handed moves, which can then each be specified using the normal interpretation of 'l' and 'r' to specify paths that are mirror images of each other.

Tricky. As a human, I think I would intuitively understand the first notation better: l and r are flipped under symmetry transformations. I guess the question is which of them is clearer in practice though. Could you give an example?

[hgm]

The only case I encountered in practice so far that ran into the chirality problem was the Falcon of Falcon Chess: a lame CZ that can take any of the three shortest (measured in King steps) paths to the destination square. Two of the paths are easy: afafsK (two straight out in any of the 8 directions, then 45 degree forward (fs), and afsafK, one out, then a 45-degree turn and two in that direction). But the third path is a zig-zag path: afraflK or aflafrK, which cannot be combined to afsaf?K, because there is no way to denote that third step should bent the opposite way from the second.

Here you generated the chirality yourself, in the first two steps, so it is easy to generate it in a specific direction, explicitly specifying a right-handed or left-handed Horse move for the first two steps. But if a similar thing occurs from a Knight jump, e.g. afrN, it would be either a (3,3) or a (0,4) move depending on whether the first leg is a right-handed or left-handed Knight move.

So either we could by convention say one should always imagine the first step as an rfN (g1-h3) when specifying the following steps. This gets very awkward if the first step can only be taken in the lf direction; lfafrN would be a Knight that jumps slightly left of forward, and then turns 45-degree left, because the 'r' in arfN now means left.

The alternative is to always specify things as they are, but then you have to separate the left-handed set from the right-handed set of moves for pieces that have both. E.g. hrafrNhlaflN, from which it is clear that the Knight always bends away from the nearest orthogonal axis (and thus is a kind of lame G.

Of course 'hl' and 'hr' to specify the subset of 4 left-handed and 4 right-handed moves is a nice feature in itself, even for one-leg movers. The 'Chiral Knight' hrN (an interesting piece, as its color binding restricts it to 1/5 of the board!) would otherwise have to be described as rfbrlbflN (or rffllbbrN), which is not very readable.


I guess Sjaak would do the Falcon as a 3-step King 'area move' (aaK), intersecting the resulting moves with the CZ squares. That would work. But I don't see how you could efficiently 'convolute' the move sets of the first and second (or later) leg. Do you use Kogge-Stone fills for that? Or do you just extract the first-leg moves, (after clearing occupied squares), and or the next-leg-leaper attack sets for those squares?

I think the fastest method for the Falcon would be to generate its moves in 4 steps, each step generating the 4 moves in the same general orthogonal direction (e.g. ffCffZ). These depend on occupancy of 8 squares (the fWfFfDfAffN squares), and you could do that as magic bitboards.

[hgm]

Question: is there a way for me to not specify how one particular piece moves?
Of course that means the XBoard will not be able to do legality testing (at least not while those pieces are on the board), but it would be quite useful if there are some pieces that I can't easily tell it how they move could be skipped.

Unfortunately this is currently not possible. When XBoard receives any piece commands, it assumes the pieces for which it did not receive piece commands move according to XBoard's native idea of them, and starts testing legality accordingly. (So that you don't have to specify Bishops, Rooks, Knight and Pawns just because you are using a weird piece as Queen.)

I have experimented with 'wild-card pieces', but it was not very satisfactory. The Falcon and Cobra are still treated by XBoard as wild-cards: any move will be accepted (if the engine did not redefine them), but it will never be considered to deliver check.

The problem is that you cannot simply define the piece as something that is upward compatible (e.g. the Falcon as a CZ because you cannot convey the specific lameness), because XBoard will imagine checks there aren't, and then forbid all kind of perfectly legal moves for the opponent.

Perhaps I should introduce a modifier for 'non-checking', that could be used to solve this; you could use that as an emergency measure on 'over-dimensioned' pieces. XBoard would allow you to move in check (by those pieces) then, but the engine can always reject this, and you would have the benefit of target-square highlighting for the other pieces.

Let's use 't' ('tame') on a final leg for that. An XBoard wildcard piece then would be a tU (U = Universal Leaper, also not implemented yet).

Of course there always is the alternative to use the highlight protocol, to overrule the highlighting by XBoard's move generator, even when you configured the latter through piece commands. Legality testing with legality testing 'off' is purely based on the board markings.

[Evert]

Ah, the Falcon. I remember I looked at it once and then closed the window very quickly. It looked like a very complicated piece. I'll have to think about that a bit.

I guess Sjaak would do the Falcon as a 3-step King 'area move' (aaK), intersecting the resulting moves with the CZ squares.

It would, if it could do three legs. Unfortunately, it can only do two.

But I don't see how you could efficiently 'convolute' the move sets of the first and second (or later) leg. Do you use Kogge-Stone fills for that? Or do you just extract the first-leg moves, (after clearing occupied squares), and or the next-leg-leaper attack sets for those squares?

Yes, do the first leg, clear occupied squares, then serialise it and apply the second leg, finally apply a bitmask:

Code: Select all

attacks = 0;
first_leg = w_table[square] & ~occupied_squares;
while (first_leg) {
   int square = pop_square(first_leg);
   attacks |= f_table[square];
}
attacks &= n_table[square];

except I haven't hard-coded any of the tables. It works quite well for a direction agnostic solution, but it's a bit ugly how it generates an intermediate move bitboard with moves that aren't actually legal.

I think the fastest method for the Falcon would be to generate its moves in 4 steps, each step generating the 4 moves in the same general orthogonal direction (e.g. ffCffZ). These depend on occupancy of 8 squares (the fWfFfDfAffN squares), and you could do that as magic bitboards.

Indeed. I actually onceworked out how to do magic bitboards for Nightriders. Never got round to implementing it though...

[hgm]

With two legs only it seems you can only do lame leapers that can be blocked on at most a single square. That makes it unlikely they would ever have many blocking squares. The worst I can imagine that still makes sense would be something like Q2 = nDnA or (in our new notation) hrafrWhrafrF, the compound of a Chiral Mao and a Chiral Moa, which all have only 8 blocking squares. Magic generation based on the occupation of those 8 squares seems pretty cheap in terms of table size, and enormously faster than serializing the first leg.

[Evert]

With two legs only it seems you can only do lame leapers that can be blocked on at most a single square. That makes it unlikely they would ever have many blocking squares. The worst I can imagine that still makes sense would be something like Q2 = nDnA or (in our new notation) hrafrWhrafrF, the compound of a Chiral Mao and a Chiral Moa, which all have only 8 blocking squares. Magic generation based on the occupation of those 8 squares seems pretty cheap in terms of table size, and enormously faster than serializing the first leg.

Maybe. When I wrote the above code, the priority was to make it work. It's only a tiny part of the move generator, and only runs for lame leapers. Serialising a bitboard also isn't too slow on 64 bit hardware. Still, doing occupancy lookup can quite possibly be faster - provided you can extract the occupancy bits efficiently. That's relatively straightforward if they're on a ray, but for something more general it's a bit more complicated.
What I worked out for Nightriders is how to transform the board so the knight jumps are along rays. I think you need two different transformations (for the l and r fork), but I'll have to dig out my notes for the details (or recreate them).
I guess for the general case, you could build up a lookup table that tells you how to calculate the bitmask (first bit = square+offset1, second bit = square+offset2). Any off-the-board squares would produce random junk, but we don't necessarily care about that (you just map all those entries to the same attack set anyway). What I worry about is the scalability of such an approach with more pieces…

Of course this limits you to 8 possible ray directions. As I said, Sjaak's "atoms" are actually more general than that, so I could make a piece that moves like mKN first, followed by N. That requires more than 8 bits of occupancy. It's a bit academic though, since I don't think I've ever seen such a piece, or felt the need to create one.

A different and possibly better approach would be to construct masks for each of the possible 8 (or, in general, more) directions and record what squares need to be empty in order to take that step:

Code: Select all

attacks = 0
for &#40;n=0; n<number_of_directions&#91;piece&#93;; n++) &#123;
   if (&#40;occupied & mask&#91;piece&#93;&#91;square&#93;&#91;n&#93;) == 0&#41;
      attacks |= attack_for_direction&#91;piece&#93;&#91;square&#93;&#91;n&#93;
&#125;

that way arbitrary squares could be marked as "need to be free". This would make it easy to make lame long leapers as well as funny things like a "fat ferz" that cannot squeeze between two enemy pieces (I guess that's a W2 that changes direction between steps in such a way that it ends up with a F step in the end), or, indeed, the Falcon.

[hgm]

I am not sure about the ray thing. As long as the number of relevant occupancy bits is not above 8, magic move generation should be able to do it for arbitrarily scattered squares.

It is true that lame leapers are pretty rare. But there is a connection to sliders, as slider moves can be decomposed into a sequence of lame leaper moves of ever increasing range: R=WnDnHn(0,4)... These have overlapping sets of blocker squares, and so it is very convenient to treat them as a group in order to benefit from that. That holds both for bitboards and mailbox, and it is of course what the standard methods do. Falcon is very similar to a slider in this respect, as it also has large overlap between the blocking squares of adjacent moves.

Sliders that move along bent trajectories are more common. Of course there are also pieces that require certain squares to be occupied rather than empty for a move to be allowed. For slider-like bitboard-based generation this doesn't really make a difference; you can make attack sets for an XQ Cannon or the orthogonal moves of a Grasshopper just as easily as for a Rook. It is just a matter of filling the tables differently.

[Evert]

I am not sure about the ray thing. As long as the number of relevant occupancy bits is not above 8, magic move generation should be able to do it for arbitrarily scattered squares.

True, but you do need a mapping that maps those scattered squares to (ideally) an unambiguous 8-bit occupancy index (it may be larger of course, but that leads to bigger tables, as is the case already for rooks with vanilla magics).

I don't actually do "real" magic move generation, by the way. I think what I use is what is called "kindergarten" on the wiki. The reason is Sjaak's bitboards don't necessarily represent an 8x8 board, so the required masks and any magic multipliers would need to be generated from scratch for each particular board size. Doable, but it seems like a debugging nightmare waiting to happen, not to mention unforeseen pathological cases. Kindergarten is a bit more robust against such things.

It is true that lame leapers are pretty rare. But there is a connection to sliders, as slider moves can be decomposed into a sequence of lame leaper moves of ever increasing range: R=WnDnHn(0,4)... These have overlapping sets of blocker squares, and so it is very convenient to treat them as a group in order to benefit from that.

True. The difference is there is a lot of stuff about slider move generation using bitboards out there and not a whole lot about lame leapers, so it's more work to work out how to do it efficiently. Still, it might be worth it.

Sliders that move along bent trajectories are more common. Of course there are also pieces that require certain squares to be occupied rather than empty for a move to be allowed. For slider-like bitboard-based generation this doesn't really make a difference; you can make attack sets for an XQ Cannon or the orthogonal moves of a Grasshopper just as easily as for a Rook. It is just a matter of filling the tables differently.

Yes. In fact, that's exactly how I generate cannon moves: when I initialise the "hopper" table I just ignore the first occupied square. I've been considering instead to do two lookups in the rook table: the first to find the cannon mound, the second for moves with the mound removed. The cannon attacks are the difference between the two sets. It's two table lookups and some calculations versus one lookup, but I do get to re-use the rook table (actually, bishops use the same table), so it may be worth it if I'm starved for cache space.

The same trick wouldn't work for locusts, which need the first empty square after the mound only, so I'd use a separate table for those.

[hgm]

Note that in Kindergarten you can live with non-contiguous packing of the relevant occupancy bits, as long as it isn't too bad, because you can interleave the overly large tables. E.g. a King neigborhood (needed for nDnA) on 8x8 could be mapped by multiplying with 0x2001, which maps the original

1110000020200000333

(where the number indicates the rank the bits are on, and 0 = don't care) pattern to

20200111333

by shifting 2 ranks - 3 = 13 bits. That is an index of 11 bits, rather than 8, but 3 of the bits are unused, and guaranteed to be zero. So you could map the file number of the from-square into those when constucting the table, by setting the start index for square s to (s&3)<<6 | (s&4)<<7. (And then shift the entire bitboard rank-wise afterwards.) Even if you don't want to organize the attacks[square][index] as an array of pointers to arrays, it would be cheap enough to do that calculation at run time, e.g. attacks[((s&3) + (s&4) << 6) + index].