for Chess-variant authors

[hgm]

Funny dilemma: I had the Betza interpreter consider the from-square as empty, to not block the generation of rifle captures. But this caused the generator to hang in Cylinder Chess, with Q or R on an otherwise empty rank.

So I make an exception now for moves that wrapped: when they reach the from-square, it is just considered for what it is. But that will cause 'self-hopping'. For Cylinder Xiangqi that would not be a problem, as there is nothing to capture. But with a Cylinder Grasshopper it can now hop itself!

Is that acceptable?

I guess the user could avoid the problem by specifying a max range equal to the circumference of the board. He could avoid the infinite-loop problem that way too, but if he fails to do so, the results are much more disastrous there.

[Evert]

Funny dilemma: I had the Betza interpreter consider the from-square as empty, to not block the generation of rifle captures. But this caused the generator to hang in Cylinder Chess, with Q or R on an otherwise empty rank.

So I make an exception now for moves that wrapped: when they reach the from-square, it is just considered for what it is. But that will cause 'self-hopping'. For Cylinder Xiangqi that would not be a problem, as there is nothing to capture. But with a Cylinder Grasshopper it can now hop itself!

Is that acceptable?

Only if it moves faster than the speed of light so it arrives back at its origin square before it left.

I guess the user could avoid the problem by specifying a max range equal to the circumference of the board. He could avoid the infinite-loop problem that way too, but if he fails to do so, the results are much more disastrous there.

Perhaps that's something that can be built into the interpreter? Infinite range then means "at most the size of the board" in whatever metric is relevant for the movement in question (#ranks or #files, I guess).

Cylinder chess has been on my TODO list for a while; it should be pretty easy to do, just tweak the bitmasks used to generate the moves. I'd interpret "cylindrical" as a property of the board rather than the pieces though, which might conflict with the Betza notation of assigning the property on a per-piece basis, especially if mixing cyllindrical and non-cyllindrical pieces…

[hgm]

Indeed, it always struck me as strange to see wrapping as a property of the piece (or even an individual move of it). OTOH, it was very useful for piece value determination to be able to play a wrapping Queen against a normal one.

The problem with automatically limiting the range to the largest board dimension is that on complex moves (using the 'again' modifier to lay out a complex path) it might not be easy to see how much you have to limit a slider leg of it to prevent self-hopping. OTOH, excluding the 'consider empty' on wrapping moves might hurt implementation of rifle captures that wrap. (But who in its right mind would want to do such things???). I guess this can be solved by putting an extra 'destroy' modality on the final leg ('md'), using the as-yet undocumented (but already implemented) 'd' modifier for 'canibalism'. After all, the path in rifle captures would be specified such that return to the from-square is guaranteed, so there is no risk you would capture another own piece than the mover.

As the decides what it plays, and how the user should configure that, I don't think there is a problem with considering cylindricity a board property. It simply means the negine would either prefix all moves in the piece commands it sends with 'o', or none, depending on the chosen board.

[Evert]

I wrote a couple of functions to turn Sjaak's internal movement tables into Betza strings.

This was pretty easy for sliders (which are basically stored as R, B or Q anyway), quite a bit more tricky for leapers, but I think the algorithm I came up with works reliably (find out which atom describes the leaper best, get those moves out of the way and repeat until you've covered them all or have to give up), although I haven't tried very hard to break it intentionally (which I could trivially by making the movement table depend on where a piece is, say move like a K on dark squares and as a N on light squares, but Betza doesn't handle that anyway).
Steppers are relatively straightforward again (they decompose in F and W with different modifiers and repeat counts), although there does appear to be a bug in there.

Anyway, this is what it spits out now for various variants:

Code: Select all

Chess:
   Knight               (N): N
   Bishop               (B): B
   Rook                 (R): R
   Queen                (Q): Q
   King                 (K): KisO2
   Pawn                 (P): fmWfceFfiW2

Spartan chess:
   Knight               (N): N
   Bishop               (B): B
   Rook                 (R): R
   Queen                (Q): Q
   King                 (K): KisO2
   General              (G): RF
   Warlord              (W): BN
   Lieutenant           (L): mFAsmWcFA
   Captain              (C): WD
   Pawn                 (P): fmWfcFfiW2
   Hoplite              (H): fmFfcWiAfiF

Shatar:
   Knight               (N): N
   Bishop               (B): B
   Rook                 (R): R
   Berse                (J): RF
   King                 (K): K
   Pawn                 (P): fmWfcF

Capablanca chess:
   Knight               (N): N
   Bishop               (B): B
   Rook                 (R): R
   Queen                (Q): Q
   Archbishop           (A): BN
   Chancellor           (C): RN
   King                 (K): KisO3
   Pawn                 (P): fmWfceFfiW2

shoshogi:
   Pawn                 (P): fW
   Lance                (L): fR
   Knight               (N): ffN
   Silver general       (S): FfW
   Bishop               (B): B
   Rook                 (R): R
   Drunk elephant       (E): FsfW
   Gold general         (G): WfF
   King                 (K): K
   Promoted pawn        (+P): WfF
   Promoted lance       (+L): WfF
   Promoted knight      (+N): WfF
   Promoted silver      (+S): WfF
   Crown prince         (+E): K
   Dragon horse         (+B): BW
   Dragon king          (+R): RF

shogi:
   Pawn                 (P): fW
   Lance                (L): fR
   Knight               (N): ffN
   Silver general       (S): FfW
   Bishop               (B): B
   Rook                 (R): R
   Gold general         (G): WfF
   King                 (K): K
   Promoted pawn        (+P): WfF
   Promoted lance       (+L): WfF
   Promoted knight      (+N): WfF
   Promoted silver      (+S): WfF
   Dragon horse         (+B): BW
   Dragon king          (+R): RF

Tori Shogi:
   Phoenix              (K): K
   Falcon               (F): FsfW
   Crane                (C): FvW
   Left quail           (L): fRbB
   Right quail          (R): fRbF
   Pheasant             (P): bFfD
   Swallow              (S): fW
   Goose                (+S): fAbD
   Eagle                (+F): KbRfBbF2

XiangQi:
   Horse                (H): nN
   Rook                 (R): R
   Cannon               (C): mRpcR
   Guard                (A): F
   Elephant             (E): nA
   Pawn                 (P): sfW
   King                 (K): W

Some of them are not optimal (mFAsmWcFA for the Spartan lieutenant could be simplified as FAsmW) and the Left and Right Quail for Tori Shogi are clearly wrong, not sure why yet.

On the whole, I'm quite happy with it.

[hgm]

This seems a hard thing to do, so congratulations!. In Fairy-Max I did not even attempt it, because I was sure the code to do it would be much longer than just writing the Betz definitions in the ini file by hand. And I figured that if I should do something complex, I'd probably better do the reverse, and switch the ini file completely to Betza format, and derive Fairy-Max' internal piece descriptions from it.

Some remarks: although you already point ot the Spartan Lieutenant is sub-optimal, it worries me a bit that Sjaak writes both mFA and cFA. Because this suggests that he thinks the m and c also apply to the A, which is not the case. If he would have written mFmAcFcA I would have felt better, because then the second appearance of A would be not totally redundant.

The Spartan Hoplite is wrong: that it says iA and not ifA might be excusable from the fact they start on 2nd rank, but there should at least be an m with it. And iF seems plain wrong: not only does it duplicate the initial fmF, but it includes a diagonal capture which should never be there.

Note that the current XBoard implementation would need the i first, and would not understand fiW2 on the Chess Pawn. It also needs cpR on the cannon in stead of pcR. This arguably can be considered XBoard bugs, but that is how it is now.

[Evert]

This seems a hard thing to do, so congratulations!. In Fairy-Max I did not even attempt it, because I was sure the code to do it would be much longer than just writing the Betz definitions in the ini file by hand. And I figured that if I should do something complex, I'd probably better do the reverse, and switch the ini file completely to Betza format, and derive Fairy-Max' internal piece descriptions from it.

Oh, it's definitely longer than just adding the description by hand! It was a fun little project though.
It's not always easy to figure out how to map Betza atoms to Sjaak's internal representation. The reverse is actually somewhat easier.

Some remarks: although you already point ot the Spartan Lieutenant is sub-optimal, it worries me a bit that Sjaak writes both mFA and cFA. Because this suggests that he thinks the m and c also apply to the A, which is not the case. If he would have written mFmAcFcA I would have felt better, because then the second appearance of A would be not totally redundant.

Argh. It originally spit out mFmAmsWcFcA, but I thought mFmA was equivalent to mFA, so I hacked in some code to simplify it to that. The good news is that it's easy to pull again.

The Spartan Hoplite is wrong: that it says iA and not ifA might be excusable from the fact they start on 2nd rank, but there should at least be an m with it. And iF seems plain wrong: not only does it duplicate the initial fmF, but it includes a diagonal capture which should never be there.

Ah, that's an oversight on my part: Sjaak's "special move" is always a non-capture, so whenever I write the "i" token I should write "im" instead.
Duplicating the normal move is something that needs to be filtered out by hand, since Sjaak actually replaces the normal move with the "special" move (instead of having the "special" move as an additional option). iA instead of ifA is just me being lazy and defining it that way, figuring it didn't matter on the second rank.

Note that the current XBoard implementation would need the i first, and would not understand fiW2 on the Chess Pawn. It also needs cpR on the cannon in stead of pcR. This arguably can be considered XBoard bugs, but that is how it is now.

Ok, I guess I misread the restrictions in the writeup. I'll fix those up too.

Found the bug that caused the quail to be messed up. They're correct now.

[Evert]

Ok, I've cleaned up the output (but not the code; string manipulations in C get very messy very quickly. I'll clean it up later) so now I get

Code: Select all

Chess:
   Knight               (N): N
   Bishop               (B): B
   Rook                 (R): R
   Queen                (Q): Q
   King                 (K): KisO2
   Pawn                 (P): fmWfceFifmW2

Spartan chess:
   Knight               (N): N
   Bishop               (B): B
   Rook                 (R): R
   Queen                (Q): Q
   King                 (K): KisO2
   General              (G): RF
   Warlord              (W): BN
   Lieutenant           (L): FAsmW
   Captain              (C): WD
   Pawn                 (P): fmWfcFifmW2
   Hoplite              (H): fmFfcWimA

Shatar:
   Knight               (N): N
   Bishop               (B): B
   Rook                 (R): R
   Berse                (J): RF
   King                 (K): K
   Pawn                 (P): fmWfcF

Capablanca chess:
   Knight               (N): N
   Bishop               (B): B
   Rook                 (R): R
   Queen                (Q): Q
   Archbishop           (A): BN
   Chancellor           (C): RN
   King                 (K): KisO3
   Pawn                 (P): fmWfceFifmW2

Tori Shogi:
   Phoenix              (K): K
   Falcon               (F): FsfW
   Crane                (C): FvW
   Left quail           (L): fRrbBlbF
   Right quail          (R): fRlbBrbF
   Pheasant             (P): bFfD
   Swallow              (S): fW
   Goose                (+S): fAbD
   Eagle                (+F): KbRfBbF2

shoshogi:
   Pawn                 (P): fW
   Lance                (L): fR
   Knight               (N): ffN
   Silver general       (S): FfW
   Bishop               (B): B
   Rook                 (R): R
   Drunk elephant       (E): FsfW
   Gold general         (G): WfF
   King                 (K): K
   Promoted pawn        (+P): WfF
   Promoted lance       (+L): WfF
   Promoted knight      (+N): WfF
   Promoted silver      (+S): WfF
   Crown prince         (+E): K
   Dragon horse         (+B): BW
   Dragon king          (+R): RF

shogi:
   Pawn                 (P): fW
   Lance                (L): fR
   Knight               (N): ffN
   Silver general       (S): FfW
   Bishop               (B): B
   Rook                 (R): R
   Gold general         (G): WfF
   King                 (K): K
   Promoted pawn        (+P): WfF
   Promoted lance       (+L): WfF
   Promoted knight      (+N): WfF
   Promoted silver      (+S): WfF
   Dragon horse         (+B): BW
   Dragon king          (+R): RF

XiangQi:
   Horse                (H): nN
   Rook                 (R): R
   Cannon               (C): mRcpR
   Guard                (A): F
   Elephant             (E): nA
   Pawn                 (P): sfW
   King                 (K): W

It still duplicates the normal pawn move (fmW ifmW2) and the hoplite still gets imA, but the code that is responsible for cleaning up the strings does just that: cleaning up strings. It doesn't understand what any of the tokens mean (and it lacks the context to replace imA by ifmA).

Still, all in all, not unhappy about how this turned out. I'll describe the algorithm in a bit more detail in a later post.

[Evert]

So, for anyone else who wants to do something similar, here's how I did the conversion from move tables to Betza in Sjaak.

Why do I do this? Obviously it is much easier to just enter the Betza string by hand, but I want Sjaak to be customizable and allow users to define their own pieces. If that can be done with Betza notation (there is some limited support for this) we're still good, but it's not a requirement (and the optimal way to describe moves in Sjaak is not easy to deduce from Betza).

First of all, it's important to know that for each piece type Sjaak has three bitmasks that describe move options: one for normal moves, one for captures and one for "special" (initial) moves. The common case is "move == capture" and "special = 0 (none)".

Each bitmasks describes four possible ways in which a piece can move, and pieces can combine these arbitrarily.

The first component is a "slider": it describes movement along a file (F), rank (R), diagonal (D) or anti-diagonal (A). A rook is FR, a bishop is AD and a queen is FRAD. Mapping this to Betza notation is trivial.

The second component is a "hopper", which is stored in exactly the same way and is equally trivial to turn into Betza notation. In the move generator sliders and hoppers use occupancy-lookup in tables (magic or kindergarten-like).

The third component is a "leaper" component. In principle this just indexes an array of bitboards that describe the movement of a piece on a given square. For "asymmetric leapers" there are distinct tables for white and black, and there is a special flag to indicate that the leaper is "lame" (can't jump over occupied squares). These are incidental to how the mapping to Betza notation is done.

For the Betza "fundamental" leapers, I actually store the (dx, dy) offsets of the move. Mapping these to Betza notation is again trivial.

Compounds of "fundamental" leapers (or asymmetric leapers) are where things get complicated. Betza notation is based on an infinite board, but chess boards are finite. A knight on a 4x4 board can never attack all its 8 squares at a time. I'm assuming that there is a square on the board where a piece's full movement potential is realised. If this is not the case, the code will fail to describe the motion of the piece accurately. This can be worked around, but it's not high on my TODO list, and of little practical importance.
The algorithm is:

Code: Select all

  1. Find the square where the piece has maximum mobility
      Prefer a square close to the centre of the board (the fundamental leapers should not be clipped by the edge of the board).
      Safe the move bitboard.
  2. Construct bitmasks for the forward, backward, left, right and other directions for this square.
  3. Loop over all fundamental leapers (W,F,D,N,A,H,C,Z,G).
      3a. Look up or calculate moves for the leaper from this square
      3b. Intersect the leaper moves with the piece moves. If empty, skip to the next loop
      3c. Loop over the direction bitmasks defined in step 2 and find the one that best matches the intersection of the leaper and piece moves [b]without introducing extra squares[/b]. (The best match to [b]fbrF[/b] is the full set ([b]F[/b]) but that adds a spurious [b]blF[/b]).
            Store the direction modifiers and clear the identified bits from the piece move bitboard. Continue at 3c until the intersection of piece and leaper moves is empty.
             Add the atom for the leaper to the direction modifiers.
  4. If there are still unidentified moves, they correspond to "long" leapers. These could be identified in a similar way, but I currently don't do that.

The algorithm can actually be sped up and simplified a bit from this description (instead of looping over leapers, we can just extract the first bit from the piece moves, identify what leaper would go there, do the mapping in 3c for that one and then continue until all moves have been processed), but this is the general idea. As described above, the King would be described as WF, but there is a special check that will identify it as K (not that it's strictly necessary).

The fourth and final movement type in Sjaak is the "stepper". Stepper moves are generated by bulk-shifting of a bitboard. It's really intended for bulk generation of pawn moves, but it can (and is) be used for pieces that move a limited number of steps along a ray direction that cannot be described using the slider tables (examples: the Lance in Shogi and the quail in Tori shogi, or the Short Rook). There are 8 compass directions (N, NE, E, SE, S, SW, W, NW) and I store the number of squares that can be travelled in each direction. The algorithm is as follows:

Code: Select all

   1. Define an array uint8_t compass_points[max(files, ranks)].
   2. For each compass point, check how far the piece can move in this direction. Say N steps. Set the corresponding bit in each of compass_points[0…N-1].
   3. Loop over the compass points array, starting with the last element.
       Skip elements that are 0.

       Intersect the compass points with the orthogonal leaper (W).
       Find the directional modifiers that best describe the movement directions (this is the same as step 3c. for leapers).
       Write out the directional modifiers, the move atom and the index in the array (corresponding to the extent of the move). Skip the index for the first or last element (corresponding to a single step or sliding to the edge of the board). In the last case, replace the atom W by R.

        Do the same for the diagonal leaper (F).

        Clear the bits that are set at this index at all lower indices (their moves have already been described).

That's basically it. The whole algorithm runs up to 3 times (for normal moves, captures and initial moves), and the output strings are manipulated to eliminate common elements between normal moves and captures and to insert appropriate "m" and "c" modifiers where needed.

Examples:
In Tori Shogi, Sjaak's move generator defines the Left Quail as step 7N,7SE,SW (actually wrong - it should be 6 rather than 7). The above algorithm turns this into fRrbBlbF. The Eagle is step 7NE,7NW,7S,2SE,2SW (again, should be 6 rather than 7), which gets turned into KbRfBbF2.

The Shogi Lance is defined as step 8N, which the algorithm turns into fR (without testing for sliding the length of the board, it would turn it into fW8, which is also fine). The Silver General is defined by the verbose aleap (0,1)|(1,1)|(1,-1)|(-1,-1)|(-1,1), which becomes FfW.

The XiangQi pawn is defined as aleap (1,0)|(-1,0)|(0,1) (with a special "prison" masks that prevents it from stepping side-ways before crossing the river). The algorithm turns it into sfW. Here it's important to make sure the test square (in step 1 for leapers) is somewhat central. I originally didn't have that condition, and the algorithm picked a back-rank square as the square with the largest number of moves. It then matched this up as W - which is correct for the back rank only.

[Evert]

I just ran into an issue with Embassy chess, where XBoard seems to reject all promotion moves. Can this have something to do with sending a "piece" command for the pawn (I know it's not necessary, but the program doesn't)?

EDIT: apparently so, because if I don't send any piece commands, pawn promotions are accepted...

[hgm]

Oh ****! This also breaks Berolina, where sending a piece command for the Pawn is necessary.

I guess XBoard accepts only promotion suffixes if the move generator explicitly says the move is a promotion. Currently the Betza generator submits all moves to the callback as 'Normal'.

So I guess I would have to test for the piece being a Pawn, (i.e. represented by XBoard's Pawn image according to the pieceToCharTable) and in that case generate moves to last rank as White/BlackPromotionToQueen.

Of course it would be better if the Betza notation could tag the piece as promoting, so that you could have differently moving Pawns that each promote in one army. Like defining a Betza pseudo-atom '=' that means 'promotes on last rank', with a possibility to append a range for deeper zones (like "=3" in Grand Chess). Of course this could be extended with some notation for what it can promote to, but XBoard doesn't support that anyway, and always offers full choice on all (non-Shogi-style) promotions. (It is up to the engine to refuse an illegal choice.)