for Chess-variant authors

[hgm]

My first attempt at a reference guide is now at

http://hgm.nubati.net/Betza.html .

[Evert]

One of the complications I'm having in implementing a parser for this in Sjaak (a different problem from sending the piece moves to XBoard of course) is in handling the multiple ways in which piece moves can be encoded that are all equivalent, but don't naturally map that way.

Consider a two-square orthogonal slider. As I understand it, this can be encoded in Betza notation in a number of ways:

• W2
• WnD
• R2 (!)

Now, in Sjaak's move generator, the best way to encode this would be as a piece that takes up to two steps in the N,E,S,W directions ("step 2N,2E,2W,2S"). Now, I can probably make the first one work that way, but it requires some special-case detection. Normally it would try to map it as "W, followed by W, but restricted to squares reachable by WD". The second one would almost map to that too, except it would be mapped as "W, or W followed by W restricted to D". The third one would currently error out (I can't restrict sliders at the moment), but would most naturally map to "step 2N,2E,2S,2W" (requires special code again), ie, exactly what I would want.

What I find particularly gross is that W2 means the same thing as R2; I noticed you didn't include the latter use in your writeup (or I missed it), which is a good thing.

I guess part of the problem here comes from the fact that Betza notation wasn't designed as something that would be easy for computers to interpret, but for humans. As such, it's a bit fuzzy.

[hgm]

What I did in the parser I posted here is consider BRQ as a synonyms for FWK, but with another default for the range (0 = infinite, while the genuine atoms use 1). An actually written range then overrules this, making Wn and Rn fully equivalent already during the low-level parsing.

As for the W2 and WnD descriptions: aren't you too ambitions here? WnD is inferior Betza notation (using more atoms), so I don't think there is any reason to worry if it also compiles to inferior code. In Fairy-Max' internal encoding there are the same options: using a normal W-slider, (which can do anything on its first step), that turns into a W-leaper after one step (W2). Or, less efficiently, use a W-leaper and a separate W-slider without permission to do anything, which turns into a W-leaper that can do everything after the first step (nD). In the latter case you would examine the W board-squares twice, and waste your time on the nD step even after you found out that the W hit an occupied square in that direction.

Well, so be it. That is what you get for feeding it crappy Betza notation. The two-atom mechanism obviously has to be allowed to handle cases like WnH, for which there is no single-atom representation. Or, more common, for the double-push of the Pawn, WinD, where you cannot combine because the nD is only an initial move, while the W is always possible. It could also be written WiW2, but that is also ugly, because it contains the same move twice, for virgin pieces.

Writing a compiler does not necessarily involve writing an optimizer.

The 'again' operator that I introduced for describing the multi-leg Shogi pieces creates similar dilemmas. The most compact way to describe a Lion is pmcaK, saying it can hop, move or capture with its first King move, and then again do an unrestricted King move. This describes all direct jumps as hops or moves over empty squares, and single K steps in a quirky way as two-leg moves that took a detour. The problem is that the pmaK part alone describes 64 moves, while there are really only 25, so many duplicats. This form is poorly suited for generating moves in an engine. The notation KNADcaKmabK would be much more suitable for the latter: all 24 direct jumps are generated seapartely by KNAD, then caK requires the first leg to be a capture, and needs never go into the second when it isn't. And mabK describes the null move in 8 different ways. (Which is the only remaining overhead, but hard to avoid, as we might actually have to test all neighboring squares to know whether it can null move. The only thing you miss by literally following the prescription is that you might take a cutoff after discovering the first null move. This is a generic problem with null moves, as different pieces could each have null move, which is then also the same move.)

I think it is perfectly acceptable to require from a user that he would write 'good Betza' here, avoiding unnecessary duplicat moves, but otherwise minimizing the number of atoms.

[hgm]

I made some more extensions, so that it is now also possible to describe sliders that make 45-degree turns. The trick was to define the g-modifier as a general flavor-changing operator in non-final legs, turning leapers into riders and vice versa, but also upgrading 4-fold movers to 8-fold K or Q, so you can then also select non-perpendicular directions from them in the follow-up leg. This does not conflict with the old Betza meaning of 'g' as Grasshopper, as there it could be used on sliders, to change them into leapers after the hop, by resetting their range to 1. I just defined what it would do to other atoms in addition to that. And I introduced a new modifier 'y', which does the same thing, but not on hopping, but on an empty square, to describe trajectories that bend 'spontaneously'.

I think I am going to do a Chess variant with bifurcation pieces in Fairy-Max now: Rooks and Bishops that bounce 45-degrees in either direction from the first obstacle in their path: mRgabyabsR and mBgabyabsB.

Code: Select all

// configurable move generation from Betza notation sent by engine.
// Released in the public domain by H.G. Muller

// Some notes about two-leg moves: move generation works in two modes, depending on whether a 'kill-
// square has been set: without one is generates all moves, and a global int legNr flags in bits 0 and 1
// if the move has 1 or 2 legs. Only the marking of squares makes use of this info, by only marking
// target squares of leg 1 (rejecting null move). A dummy move with MoveType 'FirstLeg' to the relay square
// is generated, so a cyan marker can be put there, and other functions can ignore such a move. When the
// user selects this square, it becomes the kill-square. Once a kill-square is set, only 2-leg moves are
// generated that use that square as relay, plus 1-leg moves, so the 1-leg move that goes to the kill-square
// can be marked during 2nd-leg entry to terminate the move there. For judging the pseudo-legality of the
// 2nd leg, the from-square has to be considered empty, although the moving piece is still on it.

Boolean pieceDefs;

//  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";
char upgrade[]  = "AKCD.QGH.JQL.NO.KK....Q..Z";

//  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 dirs3[] = { 0,0x38,0,0,0,0x83,0,0xFF,0,0,0,0xE0,0,0,0,0,0,0x0E,0xEE,0,0,0xBB,0,0,0,0 };
int dirs4[] = { 0,0x10,0,0,0,0x01,0,0xFF,0,0,0,0x40,0,0,0,0,0,0x04,0x44,0,0,0x11,0,0,0,0 };

int rot[][4] = { // rotation matrices for each 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
OK (Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR cl)
{
    (*(int*)cl)++;
}

void
MovesFromString (Board board, int flags, int f, int r, int tx, int ty, int angle, char *desc, MoveCallback cb, VOIDSTAR cl)
{
    char buf[80], *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, ds2, retry=0, initial=0, jump=1, skip = 0;
	char *cont = NULL;
	if(*p == 'i') initial = 1, desc = ++p;
	while(islower(*p)) p++;  // skip prefixes
	if(!isupper(*p)) return; // syntax error: no atom
	dx = xStep[*p-'A'] - '0';// step vector of atom
	dy = yStep[*p-'A'] - '0';
	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)
		    if&#40;tx < 0&#41; &#123; // for continuation legs relative directions are orthogonal!
		      while&#40;islower&#40;*desc&#41; && &#40;i = dirType&#91;*desc-'a'&#93;) != '0') &#123;
			int b = dirs1&#91;*desc-'a'&#93;; // use wide version
			if&#40; islower&#40;desc&#91;1&#93;) &&
				 (&#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; & dirs1&#91;desc&#91;1&#93;-'a'&#93;;      // intersect wide & perp wide
			    desc += 2;
			&#125; else desc++;
			dirSet |= b;
		      &#125;
		      dirSet &= 0xAA; if&#40;!dirSet&#41; dirSet = 0xAA;
		      break;
		    &#125;
	  case 'R'&#58; expo = 0;    // rook, slide
	  case 'W'&#58;              // orthogonal atom &#40;non-deg 4-fold&#41;
		    while&#40;islower&#40;*desc&#41; && &#40;dirType&#91;*desc-'a'&#93; & ~4&#41; != '0') dirSet |= dirs2&#91;*desc++-'a'&#93;;
		    dirSet &= 0x55; if&#40;!dirSet&#41; dirSet = 0x55;
		    dirSet = &#40;dirSet << angle | dirSet >> 8-angle&#41; & 255;   // re-orient direction system
		    break;
	  case 'N'&#58;              // oblique atom &#40;degenerate 8-fold&#41;
		    if&#40;tx < 0&#41; &#123; // for continuation legs relative directions are non-degenerate!
		      while&#40;islower&#40;*desc&#41; && &#40;i = dirType&#91;*desc-'a'&#93;) != '0') &#123;
			int b = dirs2&#91;*desc-'a'&#93;; // when alone, use narrow version
			if&#40;desc&#91;1&#93; == 'h') b = dirs1&#91;*desc-'a'&#93;, desc += 2; // dirs1 is wide version
			else if&#40;*desc == desc&#91;1&#93; || 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 or same&#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;
		    &#125;
	  case 'Q'&#58; expo = 0;    // queen, slide
	  case 'K'&#58;              // non-deg &#40;pseudo&#41; 8-fold
		    while&#40;islower&#40;*desc&#41; && &#40;i = dirType&#91;*desc-'a'&#93;) != '0') &#123;
			int b = dirs4&#91;*desc-'a'&#93;;    // when alone, use narrow version
			if&#40;desc&#91;1&#93; == *desc&#41; desc++; // doubling forces alone
			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 or same&#41;
			    b = dirs3&#91;*desc-'a'&#93; & dirs3&#91;desc&#91;1&#93;-'a'&#93;;      // intersect wide & perp wide
			    desc += 2;
			&#125; else desc++;
			dirSet |= b;
		    &#125;
		    if&#40;!dirSet&#41; dirSet = 0xFF;
		    dirSet = &#40;dirSet << angle | dirSet >> 8-angle&#41; & 255;   // re-orient direction system
		    ds2 = dirSet & 0xAA;          // extract diagonal directions
		    if&#40;dirSet &= 0x55&#41;            // start with orthogonal moves, if present
		         retry = 1;               // and schedule the diagonal moves for later
		    else dx = 1, dirSet = ds2;    // if no orthogonal directions, do diagonal immediately
		    break;       // should not have direction indicators
	  default&#58;  return;      // syntax error&#58; invalid atom
	&#125;
	if&#40;mine == 2 && tx < 0&#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;*desc == 'p') mode |= 32, desc++;
	if&#40;*desc == 'g') mode |= 64, desc++;
	if&#40;*desc == 'o') mode |= 128, desc++;
	if&#40;*desc == 'y') mode |= 512, desc++;
	if&#40;*desc == 'n') jump = 0, desc++;
	while&#40;*desc == 'j') jump++, desc++;
	if&#40;*desc == 'a') cont = ++desc;
	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;
        if&#40;!cont&#41; &#123;
	    if&#40;!&#40;mode & 15&#41;) mode = his + 4;          // no mode spec, use default = mc
	&#125; else &#123;
	    if&#40;mode & 32&#41; mode ^= 256 + 32;           // in non-final legs 'p' means 'pass through'
	    if&#40;mode & 64 + 512&#41; &#123;
		mode |= 256;                          // and 'g' too, but converts leaper <-> slider
		if&#40;mode & 512&#41; mode ^= 0x304;         // and 'y' is m-like 'g'
		strncpy&#40;buf, cont, 80&#41;; cont = buf;   // copy next leg&#40;s&#41;, so we can modify
		while&#40;islower&#40;*cont&#41;) cont++;         // skip to atom
		*cont = upgrade&#91;*cont-'A'&#93;;           // replace atom, BRQ <-> FWK
		if&#40;expo == 1&#41; *++cont = '0';          // turn other leapers into riders 
		*++cont = '\0';                       // make sure any old range is stripped off
		cont = buf;                           // use modified string for continuation leg
	    &#125;
	    if&#40;!&#40;mode & 0x30F&#41;) mode = his + 0x104;   // and default = mcp
	&#125;
	if&#40;dy == 1&#41; skip = jump - 1, jump = 1;        // on W & F atoms 'j' = skip first square
        do &#123;
	  for&#40;dir=0, bit=1; dir<8; dir++, bit += bit&#41; &#123; // loop over directions
	    int i = expo, j = skip, hop = mode, vx, vy;
	    if&#40;!&#40;bit & dirSet&#41;) continue;             // does not move in this direction
	    if&#40;dy != 1&#41; j = 0;                        // 
	    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;;
	    if&#40;tx < 0&#41; x = f, y = r;                  // start square
	    else      x = tx, y = ty;                 // from previous to-square if continuation
	    do &#123;                                      // traverse ray
		x += vx; y += vy;                     // step to next square
		if&#40;y < 0 || y >= BOARD_HEIGHT&#41; break; // vertically off-board&#58; always done
		if&#40;x <  BOARD_LEFT&#41; &#123; if&#40;mode & 128&#41; x += BOARD_RGHT - BOARD_LEFT; else break; &#125;
		if&#40;x >= BOARD_RGHT&#41; &#123; if&#40;mode & 128&#41; x -= BOARD_RGHT - BOARD_LEFT; else break; &#125;
		if&#40;j&#41; &#123; j--; continue; &#125;              // skip irrespective of occupation
		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;x == f && y == r&#41;          occup = 4;     else                         // start square counts as empty
		if&#40;board&#91;y&#93;&#91;x&#93; < BlackPawn&#41;   occup = 0x101; else
		if&#40;board&#91;y&#93;&#91;x&#93; < EmptySquare&#41; occup = 0x102; else
					      occup = 4;
		if&#40;cont&#41; &#123;                            // non-final leg
		  if&#40;occup & mode&#41; &#123;                  // valid intermediate square, do continuation
		    if&#40;occup & mode & 0x104&#41;          // no side effects, merge legs to one move
			MovesFromString&#40;board, flags, f, r, x, y, dir, cont, cb, cl&#41;;
		    if&#40;occup & mode & 3 && &#40;killX < 0 || killX == x && killY == y&#41;) &#123;     // destructive first leg
			int cnt = 0;
			MovesFromString&#40;board, flags, f, r, x, y, dir, cont, &OK, &cnt&#41;;  // count possible continuations
			if&#40;cnt&#41; &#123;                                                         // and if there are
			    if&#40;killX < 0&#41; cb&#40;board, flags, FirstLeg, r, f, y, x, cl&#41;;     // then generate their first leg
			    legNr <<= 1;
			    MovesFromString&#40;board, flags, f, r, x, y, dir, cont, cb, cl&#41;;
			    legNr >>= 1;
			&#125;
		    &#125;
		  &#125;
		  if&#40;occup != 4&#41; break;      // occupied squares always terminate the leg
		  continue;
		&#125;
		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;;
	  &#125;
	  dx = dy = 1; dirSet = ds2;  // prepare for diagonal moves of K,Q
	&#125; while&#40;retry-- && ds2&#41;;      // and start doing them
	if&#40;tx >= 0&#41; break;            // don't do other atoms in continuation legs
    &#125;
&#125; // next atom

[Evert]

Or, more common, for the double-push of the Pawn, WinD, where you cannot combine because the nD is only an initial move, while the W is always possible. It could also be written WiW2, but that is also ugly, because it contains the same move twice, for virgin pieces.

Writing a compiler does not necessarily involve writing an optimizer.

True, but what is "good" will depend on how the engine works internally, and that's not something a user could know (and it'll be different for different engines as well).
Case in point, WiW2 is actually what I would have to translate WinD into, since (at least in the development version) the "special" (initial) move replaces the normal move in Sjaak's move generator.

I think it is perfectly acceptable to require from a user that he would write 'good Betza' here, avoiding unnecessary duplicat moves, but otherwise minimizing the number of atoms.

Again though, what is "good Betza" is not so obvious and depends on the engine. Avoiding duplicate moves looks like an obviously good thing, but if the move generator actually pulls possible destination squares from a bitboard that was initialised based on the string it doesn't matter - and in fact it might be better to define (say) BW as BK, since I can then just re-use the movement table for the king instead of making up a new set for a piece that is not in the game.

As I said, it's going to be very engine-specific what the "best" notation is, which isn't necessarily bad (we don't really want to tell each other how we should write our engines), but it'd be nice if at least the obvious alternatives would work equally well...

[hgm]

OK, this is true. But some things seem obviously bad, whether the engine is bit-board based or mailbox. Like putting squares where you can go to and where another move can be blocked in different atoms, which is exactly what WnD does. If a set of moves can be combined to a trajectory that is traversed in a slider-like fashion, like Wn, this should certainly be done.

And I wonder how much can be gained by combining leaper tables that accidentally are the same for different pieces. That sounds like a kind of micro-optimization that you cannot expect from a general table-driven system.

[hgm]

I update the Betza reference guide with the newly conceived modifiers. To do the bifurcator pieces I had to add a 'y' for spontaneous range toggling from one leg to another, and a 't' to specify friendly-hops only. But after that it worked without a hitch. (Well, Fairy-Max also had to be upgraded to support 'early hopping' and friends-only hopping.)



I wonder if I still should build in a provision for 'long leapers', with ranges larger than the Betza system defines atoms for. One way would be to allow (x,y) to indicate such atoms. OTOH, with the 'again' operator you could describe them as two steps with a 'universal non-destructive' intermediate. E.g. a (2,4) leaper can be described as mpafN: two knight steps which go through empty or hop in between. In principle any move can be made through a succession of King steps with such all-purpose intermediates. This is of course quite awkward, but unlikely to be needed much.

[Evert]

And I wonder how much can be gained by combining leaper tables that accidentally are the same for different pieces. That sounds like a kind of micro-optimization that you cannot expect from a general table-driven system.

It's checked when the piece descriptions are loaded into the move generator, so it's fast. The test is crude, the code will not try to generate the minimal (or optimal) set of tables it can, just re-use when possible.

It makes a small, but measurable difference in speed for the move generator.

[Evert]

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.

[Evert]

I wonder if I still should build in a provision for 'long leapers', with ranges larger than the Betza system defines atoms for. One way would be to allow (x,y) to indicate such atoms. OTOH, with the 'again' operator you could describe them as two steps with a 'universal non-destructive' intermediate. E.g. a (2,4) leaper can be described as mpafN: two knight steps which go through empty or hop in between. In principle any move can be made through a succession of King steps with such all-purpose intermediates. This is of course quite awkward, but unlikely to be needed much.

I haven't yet, but I'm going to add (x, y) for long leapers to Sjaak's Betza compiler. Adding more atoms isn't going to be scalable, and such pieces are not very common or usable, even on large boards.
Implementing "again" is going to be rather awkward with the way Sjaak's move generator works, so I'm leaving that out for now. Multi-leg moves aren't really what it was designed to handle gracefully anyway (except for lame leapers).