HG,
I just want to wish you good luck!
I'd love to see this completed!
New project: very general engine for variants
Moderators: hgm, Rebel, chrisw
-
catugocatugocatugo
- Posts: 14
- Joined: Thu Feb 16, 2023 12:56 pm
- Full name: Florea Aurelian
-
hgm
- Posts: 27931
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: New project: very general engine for variants
High time to continue on this...
Initializing the trajectory table
The way pieces move is specified in the variant definition through XBetza notation. This notation sub-divides a move into 'legs'. The legs are limited-range rides: they repeat the same board step (in the same direction!) a number of times, up to a given maximum. When that maximum equals 1, we have a leaper leg, when it is infinite, we have a regular slider leg. Non-empty squares always terminate a slider leg. Most chess pieces are leapers or sliders, and their move consists of a single leg.
XBetza notation specifies piece moves as move sets: all 8 moves of the Knight together are described by the single letter N. To single out moves, or specify subsets, you would have to prefix that with 'directional modifiers'. These same modifiers are also used for indicating direction changes between consecutive legs of a move. These can also be sets of direction changes, causing the move path to branch. This makes the XBetza notation quite compact, but also a bit cumbersome.
Fortunately the Interactive Diagram already contains a (JavaScript) compiler for XBetza notation, transforming it to a move table. Each possible combination of leg directions that the XBetza notation allowed will be generated, and for each such combination a sequence of 'leg descriptions' will be put in the move table. A leg description consist of a fully-defined board step (delta_x, delta_y), the maximum number of times it can be repeated, and some flags for indicating what occupancies are allowed in the destination square of the leg, whether such occupants should be removed or left undisturbed, and whether the individual steps can or must jump.
This move table, as it is already in use by the GUI can be communicated to the engine. The latter should then build a trajectory for each (possibly multi-leg) move in the move table, based on the leg descriptions there. The trajectories can also consist of multiple legs. But a trajectory only has to transition to a new leg when there was a choice (dictated by board occupancy) where to start the next trajectory from the previous one. Which implies that this previous one should be a ride rather than a leap. A sequence of leaper legs, which had to be different legs in the XBetza descriptor and the resulting move table, e.g. because they changed direction or stride, or required different occupancy in their destination, can be combined to a single trajectory leg. Because such a trajectory leg in itself already consists of a sequence of MoveTarget cells.
For instance, a piece like the Griffon, which steps diagonally, and then continues to slide outwards like a Rook, needs separate legs for the diagonal step and the orthogonal slide in the move table. But this will result in a single trajectory leg, consisting of MoveTarget cells with relative destination (1,1), (2,1), (3,1), (4,1)... (These destinations would of course be stored as square-number differences, as the board is mapped to a 1-dimensional array.) Because there are two possible orthogonal directions that qualify as 'outward', we could actually have a tree-like trajectory, which from (1,1) would have a second continuation (on an empty square) (1,2), (1,3), (1,4), ... This would be more efficient than using separate trajectories for the left- and right-bending path both starting from the piece, as these would cause double marking of the (1,1) square in the attack table. (Which then would have to be handled by giving only one of these two the power to terminate (and thus possibly capture) there, while the other would only be able to 'pass through'.)
To benefit from tree-like trajectories, we would have to compare consecutive moves in the move table, to test whether these have an initial part in common. Moves that start out with different directed steps would still each have their own trajectory, be it linear or a tree. Another difference between the engine's trajectory table, and the GUI's move table, is that in the engine each piece of a given type would need its own set of trajectories. (Even 'potential pieces' that could result from promotions!) This makes variants where pieces can morph into each other problematic: some algorithm would be needed to determine how many pieces of each type could maximally be simultaneously present. (Poor-man's solution: assume the piece count of any type can become the total number of pieces present. For variants were a move can create new pieces even that would not work, and the upper limit is the number of board squares.)
Initializing the trajectory table
The way pieces move is specified in the variant definition through XBetza notation. This notation sub-divides a move into 'legs'. The legs are limited-range rides: they repeat the same board step (in the same direction!) a number of times, up to a given maximum. When that maximum equals 1, we have a leaper leg, when it is infinite, we have a regular slider leg. Non-empty squares always terminate a slider leg. Most chess pieces are leapers or sliders, and their move consists of a single leg.
XBetza notation specifies piece moves as move sets: all 8 moves of the Knight together are described by the single letter N. To single out moves, or specify subsets, you would have to prefix that with 'directional modifiers'. These same modifiers are also used for indicating direction changes between consecutive legs of a move. These can also be sets of direction changes, causing the move path to branch. This makes the XBetza notation quite compact, but also a bit cumbersome.
Fortunately the Interactive Diagram already contains a (JavaScript) compiler for XBetza notation, transforming it to a move table. Each possible combination of leg directions that the XBetza notation allowed will be generated, and for each such combination a sequence of 'leg descriptions' will be put in the move table. A leg description consist of a fully-defined board step (delta_x, delta_y), the maximum number of times it can be repeated, and some flags for indicating what occupancies are allowed in the destination square of the leg, whether such occupants should be removed or left undisturbed, and whether the individual steps can or must jump.
This move table, as it is already in use by the GUI can be communicated to the engine. The latter should then build a trajectory for each (possibly multi-leg) move in the move table, based on the leg descriptions there. The trajectories can also consist of multiple legs. But a trajectory only has to transition to a new leg when there was a choice (dictated by board occupancy) where to start the next trajectory from the previous one. Which implies that this previous one should be a ride rather than a leap. A sequence of leaper legs, which had to be different legs in the XBetza descriptor and the resulting move table, e.g. because they changed direction or stride, or required different occupancy in their destination, can be combined to a single trajectory leg. Because such a trajectory leg in itself already consists of a sequence of MoveTarget cells.
For instance, a piece like the Griffon, which steps diagonally, and then continues to slide outwards like a Rook, needs separate legs for the diagonal step and the orthogonal slide in the move table. But this will result in a single trajectory leg, consisting of MoveTarget cells with relative destination (1,1), (2,1), (3,1), (4,1)... (These destinations would of course be stored as square-number differences, as the board is mapped to a 1-dimensional array.) Because there are two possible orthogonal directions that qualify as 'outward', we could actually have a tree-like trajectory, which from (1,1) would have a second continuation (on an empty square) (1,2), (1,3), (1,4), ... This would be more efficient than using separate trajectories for the left- and right-bending path both starting from the piece, as these would cause double marking of the (1,1) square in the attack table. (Which then would have to be handled by giving only one of these two the power to terminate (and thus possibly capture) there, while the other would only be able to 'pass through'.)
To benefit from tree-like trajectories, we would have to compare consecutive moves in the move table, to test whether these have an initial part in common. Moves that start out with different directed steps would still each have their own trajectory, be it linear or a tree. Another difference between the engine's trajectory table, and the GUI's move table, is that in the engine each piece of a given type would need its own set of trajectories. (Even 'potential pieces' that could result from promotions!) This makes variants where pieces can morph into each other problematic: some algorithm would be needed to determine how many pieces of each type could maximally be simultaneously present. (Poor-man's solution: assume the piece count of any type can become the total number of pieces present. For variants were a move can create new pieces even that would not work, and the upper limit is the number of board squares.)