Parsing the move description
Now let's turn attention to the parser. First we have to know what format the user has to specify the moves in, to know what we have to parse. The basis for this format is Betza notation. This specifies the type of move (in term of how it displaces the piece) as a capital letter, e.g. N for the groups of 8 Knight jumps. This can be tweeked by lower-case prefixes, to specify a subset of directions the piece can make this leap in, or what the move can do (capture and or move to empty squares). There can be a digit suffix indicating how often the basic leap can be repeated (in the same direction) if the move is a ride, while an unlimited ride is indicated by doubling the capital.
These basic notations can then be chained to indicate more complex paths, consisting of more than a single 'leg'. This is done by separating notations for the legs by hyphens, and enclosing this in square brackets. E.g. [R-sR] would indicate a Rook that can turn a corner, as the prefix 's' means sideways (compared to motion in the previous leg). When a question mark is used instead of a hyphen it means the following legs are optional; otherwise the move must be followed to the end. A leg with a prefix p indicates that the square it ends on must be occupied; [pR-R] would indicate a Rook that must jump over exactly one occupied square to move: first a rook move to that square, and then another Rook move continuing in the same direction. (The default for continuation legs; as an independent move the default would be all (4 or 8) directions.) So like a Janggi Cannon.
A p before an entire move (be it a simple one or a path specification within brackets) would mean the move is only valid if there is a single occupied square in the path. An n or j prefix means the unvisited squares on the ray the move or leg follows must all be empty or occupied.
A (simplified) formal syntax description is
<move description> ::= <homogeneous move> <move description>
<homogeneous move> ::= <leg> | <modifiers> '[' <path> ']'
<path> ::= <path> '-' <leg> | <path> '?' <leg> | <leg>
< leg> ::= <modifiers> <atom> <range>
<modifiers> ::= <isoini> <directional modifiers> <modes> <sweep>
<isoini> = 'i' | 0
<directional modifiers> ::= <direction> <directional modifiers> | 0
<direction> ::= 'f' | 'b' | 'r' | 'l' | 'v' | 's' | 'h'
<modes> ::= <mode> <modes> | 0
<mode> ::= 'm' | 'c' | 'd' | 'p'
<sweep> ::= 'n' | 'j' | 0
<range> ::= <number> | 0
<atom> ::= 'W' | 'F'' | 'D' | 'A' | 'N' | 'G' | 'H' | 'C' | 'Z' | 'U' | 'K' | 'Q' | 'R' | 'B' | 'DD' | 'AA' | 'NN' | 'CC' | 'ZZ' | 'GG' | 'HH'
The simplification is that this syntax allows many non-sensical move descriptions, because they contain redundant, meaningless or contradictory modifiers. This could have been improved in many cases by using a much more complex syntax. But we will let the parser solve it semantically, by ignoring what is meaningless and obeing only the last of a conflicting set of specifications.
The purpose of the parser is to convert the leg descriptors to a structure containing a direction set (that was specified by the directional modifiers interpreted in the context of the atom), a leap encoded as x and y displacement, a multiplier for those displacements, a number indicating the range (= maximum number of repetitions of the indicated leap), and a word that packs flags for indicating which isoini, modes and sweep modifiers were present.
A homogeneous move will be a sequence of such structures, (as many as the move has legs), and all these, for all homogeneous moves in the descriptor, will be held in an array. This data serves as input for the move-path generator that was described earlier.
A lookup table will translate the atom into a leap in the standard direction (strictly forward for orthogonal and diagonal moves) slightly to the right of forward for oblique moves), a multiplier, a default direction set and a default range, by a table lookup. If a range was specified, it will overrule the default. Likewise, directional modifiers would overrule the default. What the directional modifiers mean can depend on the atom, e.g. 'f' (forward) is a single direction for a Rook, but a pair for a Bishop.
The absence of a sweep modifier n or j will cause multiplication of the leap coordinates by the tabulated multiplier, which is then set to 1 in the structure. In presence of such a modifier the leap and multiplier will simply be copied to the structure, and a flag will record whether there was a j. (There is no need to record whether there was an n; this is assumed if there was no j. The n and j only are applied on steps of a ride that are not a multiple of the multiplier, and the latter would be 1 if there was neither an n nor a j, so that assuming an n has no effect if there was none.)
Custom fairy pieces in Fairy Stockfish
Moderator: Ras
-
hgm
- Posts: 28540
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
hgm
- Posts: 28540
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Custom fairy pieces in Fairy Stockfish
Parser: directional modifiers
Interpreting the diectional modifiers is the most cumbersome part of parsing Betza notation. Moves can have up to 8 directions, but it must be possible to indicate 12 individual directions, as not all directions that can be mentioned make sense on every piece. E.g. a Knight does not have a move that goes purely forward. So 12 directions can be named: 4 orthogonal ones (f(orward), b(ackward), l(eft) and r(ight)), 2 of those v(ertical), two s(ideway). For naming the intermediate directions a vertical and horizontal direction can be combined, and since the order may matter here, this can be done in 8 ways.
So the parser must decide which adjacent directional modifiers it should combine to indicate an intermediate direction. This is done in the order they are encountered when processing the descriptor string left to right. There is a table listing the type(s) of modifier that each lower-case letter represents, and two of these types are directional, namely VERTICAL (f,b,v) or SIDEWAYS (l,r,s). If the upcoming letter is followed by a directional modifier of the other type, the two will be combined. To prevent unwanted combination a modifier can be repeated, so modifiers can also combine with themselves. The h modifier is used to indicate groups of dierections, and can combine with all 4 orthogonal modifiers, so it is both of VERTICAL and SIDEWAY type.
The initial parsing will just record as a bitmap (representing a dial with 12 directions) which combinations were detected. These must be mapped onto the 4 or 8 possible directions that moves of a given kind can have, but this mapping can only occur later, when we encounter the capital that indicated the kind of move we are dealing with (orthogonal, diagonal or oblique = other). E.g. diagonal moves have only 4 intermediate directions, and the order of the modifiers in the pair that specifies them can be ignored. I.e., fr and rf are the same. But for a Knight (an oblique) they are different, while for orthogonal moves they fould have to be split into seperate f and r moves.
To facilitate such later combining and splitting, we assign the expressible directions to bits in a non-obvious way, namely in the order (low bit to high bit) f, rf, r, br, b, lb, l, fl, fr, -, rb, -, bl, -, lf. That makes it easy to align the oppositly ordered intermediates by shifting right 7, after which directions that might have to be split because they indicate a pair of moves are adjacent to what they have to be split in. Note that the rf, br, lb, fl group of direction can be indicated by hr (the 'righthanded set'), and rf, rb, bl, lf by hl (lefthanded set). Likewise, hr, hl, hf, and hb represent the (overlapping) sets of 5 directions that contain an r, l, f or b respectively.
This is implemented in the following code:
Interpreting the diectional modifiers is the most cumbersome part of parsing Betza notation. Moves can have up to 8 directions, but it must be possible to indicate 12 individual directions, as not all directions that can be mentioned make sense on every piece. E.g. a Knight does not have a move that goes purely forward. So 12 directions can be named: 4 orthogonal ones (f(orward), b(ackward), l(eft) and r(ight)), 2 of those v(ertical), two s(ideway). For naming the intermediate directions a vertical and horizontal direction can be combined, and since the order may matter here, this can be done in 8 ways.
So the parser must decide which adjacent directional modifiers it should combine to indicate an intermediate direction. This is done in the order they are encountered when processing the descriptor string left to right. There is a table listing the type(s) of modifier that each lower-case letter represents, and two of these types are directional, namely VERTICAL (f,b,v) or SIDEWAYS (l,r,s). If the upcoming letter is followed by a directional modifier of the other type, the two will be combined. To prevent unwanted combination a modifier can be repeated, so modifiers can also combine with themselves. The h modifier is used to indicate groups of dierections, and can combine with all 4 orthogonal modifiers, so it is both of VERTICAL and SIDEWAY type.
The initial parsing will just record as a bitmap (representing a dial with 12 directions) which combinations were detected. These must be mapped onto the 4 or 8 possible directions that moves of a given kind can have, but this mapping can only occur later, when we encounter the capital that indicated the kind of move we are dealing with (orthogonal, diagonal or oblique = other). E.g. diagonal moves have only 4 intermediate directions, and the order of the modifiers in the pair that specifies them can be ignored. I.e., fr and rf are the same. But for a Knight (an oblique) they are different, while for orthogonal moves they fould have to be split into seperate f and r moves.
To facilitate such later combining and splitting, we assign the expressible directions to bits in a non-obvious way, namely in the order (low bit to high bit) f, rf, r, br, b, lb, l, fl, fr, -, rb, -, bl, -, lf. That makes it easy to align the oppositly ordered intermediates by shifting right 7, after which directions that might have to be split because they indicate a pair of moves are adjacent to what they have to be split in. Note that the rf, br, lb, fl group of direction can be indicated by hr (the 'righthanded set'), and rf, rb, bl, lf by hl (lefthanded set). Likewise, hr, hl, hf, and hb represent the (overlapping) sets of 5 directions that contain an r, l, f or b respectively.
This is implemented in the following code:
Code: Select all
int ParseDirections(String descriptor, int n)
{
int directionSet = 0, t, t2;
char c, c2;
while((t = type[c = descriptor[n]] & DIRECTION)) {
if(c == 'a') { // take care of (uncombinable) 'all'
directionSet |= 0x55EF; // omit b
n++; continue;
}
if(t2 = type[c2 = descriptor[++n]] & DIRECTION && (t | t2) == DIRECTION) n++; // combinable, read away
else if(c == c2) n++; // doubled, read away
else c2 = c; // duplicate to get second letter
directionSet |= Interpret(c, c2);
}
return directionSet;
}
int Interpret(char c1, char c2)
{
int dial = 0;
// split v = f or b and s = l or r
if(c1 == c2) {
if(c1 == 'v') return Interpret('f', 'f') | Interpret('b', 'b');
if(c1 == s') return Interpret('l', 'l') | Interpret('r', 'r');
}
if(c1 == 'v') return Interpret('f', c2) | Interpret('b', c2);
if(c1 == 's') return Interpret('r', c2) | Interpret('l', c2);
if(c2 == 'v') return Interpret(c1, 'f') | Interpret(c1, 'b');
if(c2 == 's') return Interpret(c1, 'r') | Interpret(c1, 'l');
// handle chiral sets
if(c1 == 'h') return c2 == 'r' ? 0xAA : 0x5500; // hr or hl chiral sets
// rh, lh, fh, bh sets
if(c2 == h) switch(c2) { // 'half': groups of 5 adjacent directions
case 'f': return 0x4183; // f, fl, fr, rf, lf
case 'b': return 0x1438; // b, bl, br, rb, lb
case 'l': return 0x50E0; // l, fl, bl, lf, lb
case 'r': return 0x050E; // r, fr, br, rf, rb
}
// map single direction spec to bit
s = concatenate(c1, c2);
switch(s) {
case "ff": dial |= 1<<0; break;
case "rf": dial |= 1<<8; break;
case "fr": dial |= 1<<1; break;
case "rr": dial |= 1<<2; break;
case "br": dial |= 1<<10; break;
case "rb": dial |= 1<<3; break;
case "bb": dial |= 1<<4; break;
case "lb": dial |= 1<<12; break;
case "bl": dial |= 1<<5; break;
case "ll": dial |= 1<<6; break;
case "fl": dial |= 1<<14; break;
case "lf": dial |= 1<<7; break;
default: break;
}
return dial;
}
-
hgm
- Posts: 28540
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Custom fairy pieces in Fairy Stockfish
Directions revisited and revised
The system of encoding direction sets that I described earlier has some problems. There are 2 types of directonal systems: degenerate (meaning two moves are equally forward or outward) and non-degenerate (only a single move is most forward/outward). Each of those can occur in a 4-move or 8-move case. In particular, Bishop and Knight belong in the degenerate case, Rook and Queen in the non-degenerate.
This is important in the case of multi-leg moves, where 'forward' in follow-up legs means 'outward', i.e. in the direction most similar to the one taken by the previous leg. And if, say, an N leg follows a Q leg two Knight moves qualify as most outward (no matter whether the first leg was diagonal or orthogonal), but if it follows another N leg, outward is simply continuing in the same direction. So it is important to be able to distinguish while a set of 8 moves contains the oblique (N-like) or orthogonal+diagonal (Q-like) moves. We also see that the directional system that must be used is not solely dependent on the type of move it applies to, but depends on the direction of the leg that came before it as well.
So we redesign direction sets as integers containing 16 possible directions, slipping the oblique moves as seperate bits between those for the orthogonal and diagonal moves. This makes both Knight moves in the first quadrant (i.e. to (2,1) = fr and (1,2) = rf) distinguishable from the diagonal direction there ((1,1), which in this text we will denote as f.r = r.f). The bits will be assigned clockwise, i.e. in the order f, rf, r.f, fr, r, br, r.b, rb, b, ...
A certain sequence of directional modifiers in Betza notation has a meaning that depends on the directional system it is specifying a direction of. Thus each possible combination of 1 or 2 modifiers can indicate more than one direction; the move type that they prefix (in combination with the direction of the previous leg, if any) then determines which of those directions is the one that was meant. E.g. the text 'fr' can refer to an oblique move fr or a diagonal f.r = r.f, but not to the oblique rf. So combinations of two perpendicular directions refer to 2 moves. An uncombinable orthogonal direction can refer to 3 moves, though: 'f' would be used to indicate a forward orthogonal f, and the two forward-most oblique moves rf and lf.
The context then determines which moves to pick. In an oblique context the even bits are cleared, which makes the meaning of combinations like fr unique, and leaves a pair of equivalent moves for single modifiers like f. In other cases we select the 8 even bits, with a similar result. That would be OK for selecting directions from a Queen, which indeed can move in 8 directions. But for purely orthogonal or diagonal systems, which have only 4 moves, only half of the directions that could have been mentioned can have its proper meaning. The intermediate directions refer to a pair of equivalen moves. In the diagonal context the principal direction f would refer to both r.f and l.f, i.e. must be interpreted as the two adjacent allowed directions. In the orthogonal case it is similar, but now the combined directions would have to be split: r.f becomes a pair of moves, in the directions r and f. In other words, they should never have been combined in the first place. (But the parser could not know that yet.)
This leads to a new routine for parsing the directional modifiers:
The system of encoding direction sets that I described earlier has some problems. There are 2 types of directonal systems: degenerate (meaning two moves are equally forward or outward) and non-degenerate (only a single move is most forward/outward). Each of those can occur in a 4-move or 8-move case. In particular, Bishop and Knight belong in the degenerate case, Rook and Queen in the non-degenerate.
This is important in the case of multi-leg moves, where 'forward' in follow-up legs means 'outward', i.e. in the direction most similar to the one taken by the previous leg. And if, say, an N leg follows a Q leg two Knight moves qualify as most outward (no matter whether the first leg was diagonal or orthogonal), but if it follows another N leg, outward is simply continuing in the same direction. So it is important to be able to distinguish while a set of 8 moves contains the oblique (N-like) or orthogonal+diagonal (Q-like) moves. We also see that the directional system that must be used is not solely dependent on the type of move it applies to, but depends on the direction of the leg that came before it as well.
So we redesign direction sets as integers containing 16 possible directions, slipping the oblique moves as seperate bits between those for the orthogonal and diagonal moves. This makes both Knight moves in the first quadrant (i.e. to (2,1) = fr and (1,2) = rf) distinguishable from the diagonal direction there ((1,1), which in this text we will denote as f.r = r.f). The bits will be assigned clockwise, i.e. in the order f, rf, r.f, fr, r, br, r.b, rb, b, ...
A certain sequence of directional modifiers in Betza notation has a meaning that depends on the directional system it is specifying a direction of. Thus each possible combination of 1 or 2 modifiers can indicate more than one direction; the move type that they prefix (in combination with the direction of the previous leg, if any) then determines which of those directions is the one that was meant. E.g. the text 'fr' can refer to an oblique move fr or a diagonal f.r = r.f, but not to the oblique rf. So combinations of two perpendicular directions refer to 2 moves. An uncombinable orthogonal direction can refer to 3 moves, though: 'f' would be used to indicate a forward orthogonal f, and the two forward-most oblique moves rf and lf.
The context then determines which moves to pick. In an oblique context the even bits are cleared, which makes the meaning of combinations like fr unique, and leaves a pair of equivalent moves for single modifiers like f. In other cases we select the 8 even bits, with a similar result. That would be OK for selecting directions from a Queen, which indeed can move in 8 directions. But for purely orthogonal or diagonal systems, which have only 4 moves, only half of the directions that could have been mentioned can have its proper meaning. The intermediate directions refer to a pair of equivalen moves. In the diagonal context the principal direction f would refer to both r.f and l.f, i.e. must be interpreted as the two adjacent allowed directions. In the orthogonal case it is similar, but now the combined directions would have to be split: r.f becomes a pair of moves, in the directions r and f. In other words, they should never have been combined in the first place. (But the parser could not know that yet.)
This leads to a new routine for parsing the directional modifiers:
Code: Select all
int ParseDirections(descriptor, int *n, Leg *ld)
{
ld->directionSet = 0;
while((d = OneDirection())) ld->directionSet |= d;
}
int OneDirection(descriptor, int *n)
{
c = descriptor[*n];
t = type[c]; // types are indicated by bits, and can be vertical, sideway, both (for h) and other (non-directional)
if(t & DIRECTION) { // vertical or sideways
if(c == 'a') return 0xFEFF; // all but backward
// look for combinable second
c2 = descriptor[++(*n)];
t2 = type[c2];
if((t | t2) == DIRECTION || c1 == c2) (*n)++; // combinable or doubled, read away
else c2 = c; // uncombinable single, fake double
}
// split v = f + b and s = l + r
if(c == 'v') return Interpret('f', c2) | Interpret('b', c2);
if(c == 's') return Interpret('r', c2) | Interpret('l', c2);
if(c2 == 'v') return Interpret(c, 'f') | Interpret(c, 'b');
if(c2 == 's') return Interpret(c, 'r') | Interpret(c, 'l');
return Interpret(c, c2);
}
Interpret(c1, c2)
{
int d = 0;
s = concat(c, c2);
switch(s) {
case "ff": d |= 0x8003; break; // including adjacent obliques
case "rf": d |= 0x0006; break; // diagonal or oblique
case "fr": d |= 0x000C; break;
case "rr": d |= 0x0038; break;
case "br": d |= 0x0060; break;
case "rb": d |= 0x00C0; break;
case "bb": d |= 0x0380; break;
case "lb": d |= 0x0600; break;
case "bl": d |= 0x0C00; break;
case "ll": d |= 0x3800; break;
case "fl": d |= 0x6000; break;
case "lf": d |= 0xC000; break;
case "fh": d |= 0xE00F; break; // notation for 'forward half'
case "rh": d |= 0x00FE; break;
case "bh": d |= 0x0FE0; break;
case "lh": d |= 0xFE00; break;
case "hr": d |= 0x2222; break; // chiral sets of obliques
case "hl": d |= 0x8888; break;
// note that fb and rl, which could occur from expanding vv or ss, are ignored
}
return d;
}
-
hgm
- Posts: 28540
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Custom fairy pieces in Fairy Stockfish
Generating move paths
The absolute direction into which a follow-up leg of a multi-leg move continues can be determined from the direction sets discussed above in two steps. First we have to decide whether interpretation has to be done in the N, B, R or Q system, to pick from the multiple meanings the directional modifiers can have. (I.e. whether f means f, rf+lf or r.f+l.f.) Then we have to rotate the assigned meaning into the direction of the previous leg, so that 'forward' points in that direction.
The systems are assigned as follows (left column direction of previous leg, top row the type of move specified for the follow-up leg)
So an R leg after a diagonal (B) move is interpreted in the degenerate 4-move (B) system, because two of the Rook moves go equally outward after a diagonal step. Since Q does not truly have an 8-fold symmetric move, but is a compound of B and R, switching to a 4-move leg would not have consistent behavior between the orthogonal and diagonal Q moves, and we will forbid it. The mixed Q system is only introduced for convenience; you can always express moves without it by specifying the orthogonal and diagonal moves seperately. (E.g. RB instead of Q.) Its use can safe a lot of writing; OTOH, there is no reason to have it cause confusion.
Use of an oblique (N) leg after a mixed (Q) leg is more natural; both after a diagonal and an orthogonal move there are two N moves that would qualify as most forward, and they are truly mirror images of each other. Q after N is more dubious; the Q directions ly in between the N directions, so the two that bends slightly left and slightly right of a given N move both seem to qualify as going equally well in the same direction. But one is orthogonal and one diagonal, so they are not truly equivalent. But we can still allow it, using the degenerate 8-fold (=N) system.
The tricky case is B or R after N. Each oblique move sits between an orthogonal and a diagonal ray. As mentioned above these are indicated as lf and rf. But both R and B have only one of these moves, so it would be more natural to use that single move as 'forward' direction. For R moves that would go in the long direction of the oblique, for B moves in the same quadrant. That means the reference direction does not strictly run in the same direction as the previous leg, but is rotated 1/16 of a full circle left or right. Which the table indicates as R+ and R-.
This makes it posible to write a Grant-Acedrex Unicorno as [N-B], without having so slam a directional modifiers on it. There would be a problem with that anyway, as the N moves are not all rotated versions of each other, but half of them are mirror images of the other half. And mirrors swap left and right. It is always clear what forward or backward is.
The absolute direction into which a follow-up leg of a multi-leg move continues can be determined from the direction sets discussed above in two steps. First we have to decide whether interpretation has to be done in the N, B, R or Q system, to pick from the multiple meanings the directional modifiers can have. (I.e. whether f means f, rf+lf or r.f+l.f.) Then we have to rotate the assigned meaning into the direction of the previous leg, so that 'forward' points in that direction.
The systems are assigned as follows (left column direction of previous leg, top row the type of move specified for the follow-up leg)
Code: Select all
N B R Q
N Q R+ R- N
B N R B Q
R N B R Q
Q N - - Q
Use of an oblique (N) leg after a mixed (Q) leg is more natural; both after a diagonal and an orthogonal move there are two N moves that would qualify as most forward, and they are truly mirror images of each other. Q after N is more dubious; the Q directions ly in between the N directions, so the two that bends slightly left and slightly right of a given N move both seem to qualify as going equally well in the same direction. But one is orthogonal and one diagonal, so they are not truly equivalent. But we can still allow it, using the degenerate 8-fold (=N) system.
The tricky case is B or R after N. Each oblique move sits between an orthogonal and a diagonal ray. As mentioned above these are indicated as lf and rf. But both R and B have only one of these moves, so it would be more natural to use that single move as 'forward' direction. For R moves that would go in the long direction of the oblique, for B moves in the same quadrant. That means the reference direction does not strictly run in the same direction as the previous leg, but is rotated 1/16 of a full circle left or right. Which the table indicates as R+ and R-.
This makes it posible to write a Grant-Acedrex Unicorno as [N-B], without having so slam a directional modifiers on it. There would be a problem with that anyway, as the N moves are not all rotated versions of each other, but half of them are mirror images of the other half. And mirrors swap left and right. It is always clear what forward or backward is.