Preliminary trial: http://hgm.nubati.net/rules/applet.html
I am sure this has been done before (many times?), but what makes my implementation special is that it should be able to handle almost arbitrary Chess variants, through minimal configuration. So the board layout and piece overview are not hard-coded HTML elements, but are generated during page load by the JavaScript based on initialization of some of the JavaScript arrays specified by the page. E.g. dimensions of the board, number of piece type, piece IDs, names of the graphics file to be displayed for the pieces, etc.
One of the items to be initialized is the description of the piece move, as a text string in Betza notation. So one of the challenges was to develop JavaScript code for interpreting such strings, so they can be used to generate moves from. (Which then are used to highlight move targets of the picked-up piece considering the board position.) Now parsing Betza notation is a rather complex edeavor. For highlighting moves that is not a problem, as speed is not an issue there. But to keep the hope for an AI alive, a faster method should be used as parsing the text strings from scratch every time you want to generate moves.
So I separated the parsing of the text and the actual generation of moves, by implementing a (slow) Betza compiler (which generates some intermediate move code), and a (fast) interpreter of this intermediate code. Normally I just use a null-terminated list of board steps for each piece type, in a mailbox move generator for orthodox Chess. In general the same piece can have both slider and leaper moves, however (e.g. the Archbishop of Capablanca Chess), so you would have to indicate that on a per-move bases. And for handling the general case of 'divergent' pieces that capture differently from how they move would also require a per-move indicator whether the move is a capture or not. So in a variant engine like Fairy-Max each board step is accompanied by a 'flags' word which specifies what the piece can do with the given board step. To handle limited-range sliders the slider-vs-leaper flag can be generalized by specification of a range, where a range of 1 implies a leaper.
The intermediate code I have chosen for the Betza compiler elaborates on this design. The main problem to still be addressed is that of multi-leg moves: moves that do something (e.g. move to an empty square, hover above an occupied one, or capture a piece), and are then followed by more moving (in the same or another direction, possibly now able to do different things). So in general a move is not just a single (step, flags, range) combination, but a sequence of those, one for each leg of the move.
This raises the problem of failure to accomplish the move goal (e.g. a move that must move to an empty square hits upon an occupied one, or strays off board) in a leg that is not the final leg for that move. This then requires skipping of the remaining legs of that move, so that move generation can continue with the first (and perhaps only) leg of the next move of that piece (or finds the termination sentinel for the list of that piece).
The intermediate code handles this by including a 'skip' field for each leg, indicating how many following leg descriptors should be skipped in case of failure. (In case of success, e.g. a leg that must capture indeed finds an enemy on its destination square, it always continues with the next leg in the list.) So the intermediate move code consists of a list of (flags, step, range, skip) quadruples, where flags = 0 is used as a list terminator. I used one bit in the flags word to indicate if the leg is the final leg of the move, but I guess this also could have been deduced from the skip field being 0.
Each leg in the list specifies a unique direction. Betza notation in general specifies move in groups with the same step length, e.g. 'N' stands for all 8 Knight jumps. So the compilation process involves 'unrolling' such implied loops over directions. This can get complicated when a multi-leg description involves forking. E.g. a piece that can make two King steps in independent directions basically implies two nested loops over directions, one for each step, and thus would unroll into 64 different 'paths' of two legs each. A piece that can make 3 independent King steps even unrolls to 512 3-leg moves. That sounds like a lot of work for the move generator. Of course such a 'King cubed' is a rather complex piece; it might have to feel its moves through a maze of occupied squares. But the compiler can optimize this process by grouping those paths that start with the same step (64 of the 512), and set the skip field of the first leg to not just skip the remaining two legs of the path when it fails (e.g. because it bumps into a friend), but skip the following 63 paths as well. After all, they all start with the same leg that you just concluded will fail, and there is no need to try and fail in exactly the same way 63 more times. Similarly, failure of the second leg could skip the remaining leg plus the 7 following paths.
Apart from the directional unrolling, there is one other type of leg that implies looping, and would fork the path. This is a slider move with non-capture rights (i.e. allowed to end on an empty square) in the non-final leg of a move. Leaper moves with a given step always have a unique target, as do slider moves that must end on an occupied square. But when describing a Hook Mover (a Rook that can turn one 90-degree corner on any empty square), you woud specify it as a non-capture Rook move for its 1st leg, followed by a perpendicular Rook move. In general the first leg can now end on many different empty squares, which can all be used to alter direction, and consequently end up in different places.
In theory this implied loop over the empty squares along the ray could also be unrolled, by repeating it with ever larger strides for the 1st leg. The slider range is unlimited, but the board size would put a cap on it. This seemed a bit cumbersome, so I designed a different method. An otherwise invalid flags value of -1 makes the move-descriptor item not a true leg, but a 'loop directive'. This instructs the move generator to redo the follow-up legs of the sliding move. The way it works is that sliding non-final legs with non-capture rights immediately terminate in favor of the next leg when they hit the first square (and it was empty; otherwise they fail), and remember the square where they ended somewhere. A later loop directive then adds another board step to it (which it re-specified in its own step field) to that stored square number, and reloads it, while rewinding the 'current-leg pointer' to point to the original follow-up leg descriptor by subtracting the range field if that was successful. (I.e. when it stepped to an unoccupied square.) When the added step would not hit an empty square the loop directive fails.
This allows implementation of hook movers by just adding a simple loop directive behind the two-leg description, e.g.
Code: Select all
1. (noncapt, (1,0), inf, 2) // 1st leg, slide in (1,0) direction to empty. Skip 2 (to 4.) if blocked
2. (noncapt|capt, (0,1), inf, 0) // 2nd leg, slide in (0,1) direction and capt/noncapt there. Always continue with 3.
3. (loop, (1,0), 1, 0) // take one (1,0) step from square reached by 1, and continue with 3-1 = 2.
4. (noncapt, (1,0), inf, 2)
5. (noncapt|capt, (0,-1), inf, 0) // 2nd leg in perpendicular direction opposite from 2.
6. (loop, (1,0), 1, 0)
7. ...Finite-range slides in non-final non-capture legs can be simply unrolled by using successively larger strides for the 1st leg, e.g. for a max. range of 2:
Code: Select all
1. (noncapt, (1,0), 1, 3) // Only attempt one (1,0) step. skip to 4. if it is blocked
2. (noncapt|capt, (0,1), inf, 0) // 2nd leg, slide in (0,1) direction and capt/noncapt there. Always continue with 3.
3. (noncapt, (2,0), 1, 1) // Directly jump over (2,0), as (1,0) is known to be empty
4. (noncapt|capt, (0,1), inf, 0) // 2nd leg
5. ...