for Chess-variant authors

[hgm]

The next release of the WinBoard / XBoard will support a protocol extension for improving the GUI functionality in non-standard variants that can only be played with legality testing off. Such variants typically involve pieces with moves different from any of the 22 piece types supported by XBoard. The consequence is that XBoard cannot use the 'show target squares' option, cannot do reliable check and mate detection, and produces lousy SAN with wrong disambiguation. All because it assumes the pieces move differently that they really do.

The new command allows the engine to load XBoard's move generator with a description of how the piece moves, after which all problems mentioned above disappear. The command syntax is

piece ID MOVEDESCRIPTION

where ID is the 1-letter piece code from the pieceToCharTable. So for engines that change the latter through a setup command, the piece commands will have to be sent after the setup command.

The MOVEDESCRIPTION encodes the capabilities of the piece in so-called Betza notation, where sets of symmetry-equivalent moves are indicated by a single capital (e.g. N for the 8 Knight moves). The maximum number of times this step can be repeated in the same direction for sliders/riders can be written behind it, and when the piece only has a subset of of the moves these are written in lower case in front of it. A lower-case m or c in front of the move indicates it is a non-capture only or capture only. When a piece makes moves of different strides, these are simply concatenated. The orthodox pieces B, R, Q, K can also be used, as shortcuts.

Currently this is all that XBoard understands, with the additional convention that a repetition count of 0 means 'infinite'. Future versions will also understand multi-leg moves and hoppers (which can be described as two-step movers).

Some examples:

Code: Select all

W  Wazir ((1,0) stepper, Xiangqi King)
W0 Rook
W3 range-3 Rook
RN Chancellor (Rook-Knight compound)
BW Crowned Bishop (Shogi Dragon Horse, King-Bishop compound)
F  Ferz ((1,1) stepper)
WF King (does not imply anything about royalty, just states how it moves)
fN Shogi Knight (only has the f=forward-most two moves)
fW Shogi Pawn (or Xiangqi Pawn before the River)
fsW Xiangqi Pawn that crossed the River (s = lr = sideway)
WfF Shogi Gold General
fWF Shogi Silver General
fmWfcF FIDE Pawn
mNcK piece that moves as Knight but captures as King

As you can see, highly symmetric pieces tend to have very compact descriptions, and the much rarer asymmetric or divergent pieces require much longer description.


This extension is mainly intended for variants that involve only a few pieces outside XBoard's standard repertoire. E.g. there exists a Makruk variant Ai-Wok, which replaces the Makruk Queen (a Ferz, like in Shatranj) with a very powerful piece (the 'Ai-Wok'), which moves like Knight, Rook or Ferz. An engine for this could send in response to the variant makruk command (when XBoard's legality testing is off)

setup (PNSR...AKpnsr...ak) rnskasnt/8/pppppppp/8/8/PPPPPPPP/8/RNSAKSNR w - - 0 1
piece A RNF
piece a RNF

(Note that XBoard will not automatically assume white and black pieces with the same ID move alike.)

[hgm]

As I was implementing support for this new feature in Shokidoki, for the purpose of playing Tori Shogi (where virtually all pieces move differently from regular Shogi), I immediately encountered one fatal and one inconveniencing shortcoming:

*) It was not possible to define moves for Shogi promoted pieces, which do not appear in the pieceToCharTable with a seperate ID, but just as a '+' (with the idea that in FEN or SAN notation they should use the ID of the unpromoted piece prefixed with a +). The ID field in the command now can also have a '+' prefix to indicate such pieces. E.g.

piece +S fAbD

would define the moves of a promoted Swallow (as Pawns in Tori Shogi are called).

*) It was really annoying to have to do white and black pieces with the same moves twice. So I added the convention that a '&' suffix on the ID field of a white piece (i.e. capitalized ID) will automatically use that same MOVEDESCRIPTION for the corresponding black piece. E.g.

piece +S& fAbD

Note that the meaning of directional specifiers such as f(orward) and b(ackward) were already always interpreted in the coordinate system of the corresponding player, so that by default the same description leads to the black piece being a 180-degree rotated version of the white piece.

[hgm]

Another problem that is still open is games with drops. There could be restrictions on which pieces can be dropped where, which are quite independent from how the piece moves when it is on the board. Common limitations are not allowing drops where the piece has no legal moves (Shogi), or to which the piece has no other legal moves (Crazyhouse). Or not allowing Pawns to be dropped only upto a certain maximum number per file (Shogi).

To bring the GUI move generator fully up-to-date, the 'piece' commands would have to contain information about that too. I am not sure what would be a sufficiently general and powerful way to encode that. Perhaps the rank or range of ranks where the piece could be dropped, like 2-7 in Crazyhouse. Perhaps followed by a list of pieces the presence of which in the file would prevent a drop there. Then Shogi Pawns could be described as

piece P& fW 1-8P1

indicating it could not be dropped on rank 9, and that the presence of 1 Pawn forbids the drop. Default would be drops allowed on every empty square.

[hgm]

Some progress that will still go into XBoard 4.8.0:

It was not possible to describe e.p. capture, which again made it impossible to redefine the moves of a Pawn that should have e.p. capture. I introduced a new move modality (next to m and c), namely 'e', which stands for e.p. capture. A move that has an e prefix can only be made if it ends on the e.p. square, which is the square that an initial double-push just skipped over in the previous ply.

To define initial double pushes there is the 'i' prefix, and a newly implemented modifier 'n', for 'non-jumping'. Currently the effects of this in WinBoard are only defined for orthogonal or diagonal jumps of 2 squares, and means the move can be blocked on the square it jumps over. The current code is pretty stupid, so the modifiers have to come in the order

i <directional> m c e n

in order to be understood. With this notation it is now possible to fully define a Berolina Pawn:

fmFfceWifmnA

The FIDE Pawn would be

fmWfceFifmnD

but WinBoard of course knows that already.

Another improvement is that a redefinition of the King would have it keep its standard castling moves, unless you redefine those. If you want a King that cannot castle, you can just switch off the castling rights in the initial position. Castlings can be defined by the O symbol, followed by a number to indicate how many steps the King will move, an 'i' prefix (as it is only allowed on a virgin King), and an 'l', 'r' or 's' prefix to indicate the direction. Normal castling would thus be

isO2

That it must be a non-capture is implied; in fact all squares between King and corner have to be empty, and the Rook will end up next to the King.

[hgm]

I decided to put the following code to generate moves from a simple Betza-notation text string in the public domain.

Code: Select all

/****************************************************/
/* Configurable move generation from Betza notation */
/* Placed in the public domain by H.G.Muller        */
/****************************************************/

//  alphabet      "abcdefghijklmnopqrstuvwxyz"
char symmetry[] = "FBNW.FFW.NKN.NW.QR....W..N";
char xStep[]    = "2110.130.102.10.00....0..2";
char yStep[]    = "2132.133.313.20.11....1..3";
char dirType[]  = "01000104000200000260050000";
//  alphabet   "a b    c d e f    g h    i j k l    m n o p q r    s    t u v    w x y z "
int dirs1[] = { 0,0x3C,0,0,0,0xC3,0,0,   0,0,0,0xF0,0,0,0,0,0,0x0F,0   ,0,0,0   ,0,0,0,0 };
int dirs2[] = { 0,0x18,0,0,0,0x81,0,0xFF,0,0,0,0x60,0,0,0,0,0,0x06,0x66,0,0,0x99,0,0,0,0 };

int rot[][4] = { // rotation matrices per direction
  { 1, 0, 0, 1 },
  { 0, 1, 1, 0 },
  { 0, 1,-1, 0 },
  { 1, 0, 0,-1 },
  {-1, 0, 0,-1 },
  { 0,-1,-1, 0 },
  { 0,-1, 1, 0 },
  {-1, 0, 0, 1 }
};

void
MovesFromString (Board board, int flags, int f, int r, char *desc, MoveCallback cb, VOIDSTAR cl)
//  board is the current board position
//  f, r are the file and rank coordinate of the piece to generate moves for
//  desc is a text string describing the piece in Betza notation
//  cb is the function to be called (with argument cl) for each pseudo-legal move
{
    char *p = desc;
    int mine, his, dir, bit, occup, i;
    if(flags & F_WHITE_ON_MOVE) his = 2, mine = 1; else his = 1, mine = 2;
    while(*p) {                  // more moves to go
        int expo = 1, dx, dy, x, y, mode, dirSet, retry=0, initial=0, jump=1;
        if(*p == 'i') initial = 1, desc = ++p;
        while(islower(*p)) p++;  // skip prefixes
        if(!isupper(*p)) return; // syntax error: no atom
        dirSet = 0;              // build direction set based on atom symmetry
        switch(symmetry[*p-'A']) {
          case 'B': expo = 0;    // bishop, slide
          case 'F':              // diagonal atom (degenerate 4-fold)
                    while(islower(*desc) && (i = dirType[*desc-'a']) != '0') {
                        int b = dirs1[*desc-'a']; // use wide version
                        if( islower(desc[1]) &&
                                 ((i | dirType[desc[1]-'a']) & 3) == 3) {   // combinable (perpendicular dim)
                            b = dirs1[*desc-'a'] & dirs1[desc[1]-'a'];      // intersect wide & perp wide
                            desc += 2;
                        } else desc++;
                        dirSet |= b;
                    }
                    dirSet &= 0x99; if(!dirSet) dirSet = 0x99;
                    break;
          case 'R': expo = 0;    // rook, slide
          case 'W':              // orthogonal atom (non-deg 4-fold)
                    while(islower(*desc) && (dirType[*desc-'a'] & ~4) != '0') dirSet |= dirs2[*desc++-'a'];
                    dirSet &= 0x55; if(!dirSet) dirSet = 0x55;
                    break;
          case 'N':              // oblique atom (degenerate 8-fold)
                    while(islower(*desc) && (i = dirType[*desc-'a']) != '0') {
                        int b = dirs2[*desc-'a']; // when alone, use narrow version
                        if(desc[1] == 'h') b = dirs1[*desc-'a'], desc += 2; // dirs1 is wide version
                        else if&#40;islower&#40;desc&#91;1&#93;) && i < '4'
                                && (&#40;i | dirType&#91;desc&#91;1&#93;-'a'&#93;) & 3&#41; == 3&#41; &#123; // combinable &#40;perpendicular dim&#41;
                            b = dirs1&#91;*desc-'a'&#93; & dirs2&#91;desc&#91;1&#93;-'a'&#93;;      // intersect wide & perp narrow
                            desc += 2;
                        &#125; else desc++;
                        dirSet |= b;
                    &#125;
                    if&#40;!dirSet&#41; dirSet = 0xFF;
                    break;
          case 'Q'&#58; expo = 0;    // queen, slide
          case 'K'&#58;              // non-deg &#40;pseudo&#41; 8-fold
                    dirSet=0x55; // start with orthogonal moves
                    retry = 1;   // and schedule the diagonal moves for later
                    break;       // should not have direction indicators
          default&#58;  return;      // syntax error&#58; invalid atom
        &#125;
        if&#40;mine == 2&#41; dirSet = dirSet >> 4 | dirSet << 4 & 255; // invert black moves
        mode = 0;                // build mode mask
        if&#40;*desc == 'm') mode |= 4, desc++;
        if&#40;*desc == 'c') mode |= his, desc++;
        if&#40;*desc == 'd') mode |= mine, desc++;
        if&#40;*desc == 'e') mode |= 8, desc++;
        if&#40;!mode&#41; mode = his + 4;// no mode spec, use default = mc
        if&#40;*desc == 'p') mode |= 32, desc++;
        if&#40;*desc == 'g') mode |= 64, desc++;
        if&#40;*desc == 'n') jump = 0, desc++;
        while&#40;*desc == 'j') jump++, desc++;
        dx = xStep&#91;*p-'A'&#93; - '0';                     // step vector of atom
        dy = yStep&#91;*p-'A'&#93; - '0';
        if&#40;isdigit&#40;*++p&#41;) expo = atoi&#40;p++);           // read exponent
        if&#40;expo > 9&#41; p++;                             // allow double-digit
        desc = p;                                     // this is start of next move
        if&#40;initial && &#40;board&#91;r&#93;&#91;f&#93; != initialPosition&#91;r&#93;&#91;f&#93; ||
                       r == 0              && board&#91;TOUCHED_W&#93; & 1<<f ||
                       r == BOARD_HEIGHT-1 && board&#91;TOUCHED_B&#93; & 1<<f   ) ) continue;
        if&#40;expo > 1 && dx == 0 && dy == 0&#41; &#123;          // castling indicated by O + number
            mode |= 16; dy = 1;
        &#125;
        do &#123;
          for&#40;dir=0, bit=1; dir<8; dir++, bit += bit&#41; &#123; // loop over directions
            int i = expo, hop = mode, vx, vy;
            if&#40;!&#40;bit & dirSet&#41;) continue;             // does not move in this direction
            vx = dx*rot&#91;dir&#93;&#91;0&#93; + dy*rot&#91;dir&#93;&#91;1&#93;;     // rotate step vector
            vy = dx*rot&#91;dir&#93;&#91;2&#93; + dy*rot&#91;dir&#93;&#91;3&#93;;
            x = f; y = r;                             // start square
            do &#123;
                x += vx; y += vy;                     // step to next square
                if&#40;y < 0 || y >= BOARD_HEIGHT || x < BOARD_LEFT || x >= BOARD_RGHT&#41; break;
                if&#40;!jump    && board&#91;y - vy + vy/2&#93;&#91;x - vx + vx/2&#93; != EmptySquare&#41; break; // blocked
                if&#40;jump > 1 && board&#91;y - vy + vy/2&#93;&#91;x - vx + vx/2&#93; == EmptySquare&#41; break; // no hop
                if&#40;board&#91;y&#93;&#91;x&#93; < BlackPawn&#41;   occup = 1; else
                if&#40;board&#91;y&#93;&#91;x&#93; < EmptySquare&#41; occup = 2; else
                                              occup = 4;
                if&#40;hop & 32+64&#41; &#123; if&#40;occup != 4&#41; &#123; if&#40;hop & 64 && i != 1&#41; i = 2; hop &= 31; &#125; continue; &#125; // hopper
                if&#40;mode & 8 && y == board&#91;EP_RANK&#93; && occup == 4 && board&#91;EP_FILE&#93; == x&#41; &#123; // to e.p. square
                    cb&#40;board, flags, mine == 1 ? WhiteCapturesEnPassant &#58; BlackCapturesEnPassant, r, f, y, x, cl&#41;;
                &#125;
                if&#40;mode & 16&#41; &#123;              // castling
                    i = 2;                   // kludge to elongate move indefinitely
                    if&#40;occup == 4&#41; continue; // skip empty squares
                    if&#40;x == BOARD_LEFT   && board&#91;y&#93;&#91;x&#93; == initialPosition&#91;y&#93;&#91;x&#93;) // reached initial corner piece
                        cb&#40;board, flags, mine == 1 ? WhiteQueenSideCastle &#58; BlackQueenSideCastle, r, f, y, f - expo, cl&#41;;
                    if&#40;x == BOARD_RGHT-1 && board&#91;y&#93;&#91;x&#93; == initialPosition&#91;y&#93;&#91;x&#93;)
                        cb&#40;board, flags, mine == 1 ? WhiteKingSideCastle &#58; BlackKingSideCastle, r, f, y, f + expo, cl&#41;;
                    break;
                &#125;
                if&#40;occup & mode&#41; cb&#40;board, flags, NormalMove, r, f, y, x, cl&#41;; // allowed, generate
                if&#40;occup != 4&#41; break; // not valid transit square
            &#125; while&#40;--i&#41;;             // next step
          &#125;                           // next direction
          dx = dy = 1; dirSet = 0x99; // prepare for diagonal moves of K,Q
        &#125; while&#40;retry--);             // and start doing them
    &#125; // next atom
&#125;

[Evert]

Awesome.

I just skimmed through your description on the chessvariants pages, do you plan to document the final version somewhere for easy reference?

I've added basic Betza-style parsing to the development version of Sjaak. It works, but some of it is going to be tricky to map to Sjaak's internal representation of piece moves (it has sliders/hoppers and leapers and it can do at least some lame leapers and it can do riders in any of the eight compass directions, but that's it). If I can get that to work well enough, it's probably easier to define moves that way and send that on to XBoard rather than trying to convert Sjaak's internal representation to Betza notation.

I need to wrap my head around the differences between the various f/fh/ff/fs/fv possibilities when it comes to knight moves though. From what I understand, 'ff' is the Shogi horse (the 90 degree wedge between the main diagonals), 'fs' would be its compliment in the forward direction, plain 'f' is the union of the two and 'fv' == 'ff' and 'fh' == 'f'. Is that right?

[hgm]

I always interpreted ff = f, writing the Shogi Knight as fN. But I realize now that this can cause ambiguity in parsing of a concatenation of directional prefixes, where there would be no way to order them without one being intended as a singe-character direction to combine syntactically with the first character of a following one. I guess this can happen when you want the two forward and the two rightmost Knight moves: both frN and rfN would describe a Knight with a single move.

So I think that it would be best to outlaw single f, b, r and l completely on oblique leapers. With every direction set indicated by a pair of letters, things like ffrrN would be completely unambiguous (which, unfortunately, is not the same as readable!). I definitely got that wrong in my Betza 2.0 proposal, and also in the XBoard implementation given above. I'd better fix that...

That means fh = ff + fs. Note that fr and rf are not the same: fr = fh*rr, with * denoting set intersection. So the first letter always indicates a 'wide' set, and the second then a perpendicular 'narrow' set, so their intersection will always be a single move. 'v' normally means (f+b) and obeys distributivity; i.e. rv = r(f+b) = (rf+rb). As the first character indicates a wide set, v makes no sense as first character of a pair: vh = fh + bh = everything. So a lone 'v' (or 's') will never cause any ambiguity, and always means ff+bb.


It would be great if an engine could relate its internal representation to Betza notation in one direction or the other, because then it could never be inconsistent. But for the time being I have Fairy-Max simply send pre-configured Betza strings with each variant that needs them, without it having any idea what they mean. In the future I might equip Fairy-Max with a 'Betza compiler', which accepts Betza strings in the fmax.ini game-definition file, and would convert those to Fairy-Max' internal representation. Fairy-Max can currently do more than original Betza notation can describe, however, in particular hoppers that turn corners at the platform (known as 'bifurcators', as they usually can proceed in two symmetric directions, although in Fairy-Max I would have to specify these as separate moves).


I will certainly make a 'reference version' for what XBoard currently understands, and what it might understand in the future.

[hgm]

I replaced the line

Code: Select all

                       else if&#40;islower&#40;desc&#91;1&#93;) && i < '4' 

by

Code: Select all

                       else if&#40;*desc == desc&#91;1&#93; || islower&#40;desc&#91;1&#93;) && i < '4' 

So that two identical modifiers will also always be considered 'combinable'. As they combina a narrow and wide angle range in the same direction, the result is identical to that of the narrow range. If there is nothing combinable behind it, interpretation as a single character still works. So fN and ffN are both valid for the Shogi Knight.

[Evert]

Ok, so if I try to picture this at bitboard masks (which is what I'll probably end up using for the construction of these things in Sjaak), I guess it boils down to the following.

Let FH be the "forward half", anything that is strictly in front of a given rank (I call this "north" in Sjaak). Let FF by "strictly forward", what would correspond to the region between compass directions NE-N-NW. Similarly for backward, left and right:

Code: Select all

 fh fh fh fh fh 
 fh fh fh fh fh 
 .  .  *  .  .       FH, BH
 bh bh bh bh bh 
 bh bh bh bh bh 

 lh lh . rh rh
 lh lh . rh rh
 lh lh * rh rh       LH, RH
 lh lh . rh rh
 lh lh . rh rh

 ff ff ff ff ff 
 .  ff ff ff . 
 .  .  *  .  .       FF,BB
 .  bb bb bb . 
 bb bb bb bb bb 

 ll .  . .  rr
 ll ll . rr rr
 ll ll * rr rr       LL, RR
 ll ll . rr rr
 ll .  . .  rr

V := FF + BB
S := RR + LL

Then I can get the direction "fl" by intersecting the sets FH and LL, and the direction "lf" by intersecting the sets LH and FF. The intersection (FF * LL) is simply the diagonal. I suppose one could define the sets to be completely orthogonal, but this also seems useful.

So forward knight moves would be fN := N * FF, if N is the 8-point symmetric set of knight moves.
Should be easy enough to implement.

[hgm]

Indeed, that is basically it. But it really applies only to degenerate 8-fold moves like N. For 4-fold moves the system can be simpler. You would never need 'fh' or 'ff'; forward is just forward, one orthogonal or two equivalent diagonal moves. For orthogonal every direction is a single letter. For diagonal a single letter specifies a pair of directions, and a pair of letters from orthogonal directions intersects the pairs to leave one one direction. There is no difference between rf and fr, though.

Code: Select all

lf lf  f rf rf
fl lf  f rf fr
 l  l  .  r  r
bl lb  b lb bl
lb lb  b lb lb

This is why the code I posted uses a switch on the symmetry-type of the following atom, to interpret the directional modifiers.

K is not really an atom, but it is often very convenient to treat it as such. But it would be a non-degenerate 8-fold mover. Putting directional modifiers on it is asking for trouble, however. I think you could do it by combining the orthogonal and diagonal systems, requiring the orthoganal moves to be indicated by duplicated letters again:

Code: Select all

lf ff rf
ll  . rr
lb bb rb

fh fh fh
 .  .  .
bh bh bh

lh  . rh
lh  . rh
lh  . rh

fs  . fs
 s  .  s
bs  . bs

lv  v rv
 .  .  .
lv  v rv

It would usually be simpler to decompose into W and F first. E.g. Shogi Silver could be fhsbK, but FfW is much clearer. In a system with allows continuation steps it can be convenient, though. E.g. a Queen that could make 90-degree corners could be Q-sQ, in stead of (R-sR)(B-sB).