New project: very general engine for variants

[catugocatugocatugo]

HG,
I just want to wish you good luck!
I'd love to see this completed!

[hgm]

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.)

[catugocatugocatugo]

While working on a my 10x10 chess with different armies, I stumbled on a piece, namely FafyafFafasF (in XBetza), i.e. a piece that moves like a bishop except it cannot stop at the second square but it may turn from the second square to the adjected camel squares. The regular XBetza notation move parser would test the availability of the ferz square twice once for the ferz move and once for the afyafF part. But your initial tabulating (like in Alpha zero I presume) would have this problem only once in the beginning of the program. So, now I now where tabulating is useful. As I build engines specifically for these games, this is not a problem for me as each piece's move generator is manually crafted, but for a general program this is useful.

[catugocatugocatugo]

I have a proposal. It would take time until we get to that, but I'm afraid I would forget until it comes to that.
About shuffling the initial position I think we should think an algoritm which associates an integer to a certain initial position. I have done something like this in my two old apothecary games: https://www.chessvariants.com/rules/apothecary-chess-2 and https://www.chessvariants.com/rules/apothecary-chess-2 . For games that have only one shuffling group there is an alghorithm that assigns an integer to a permutation. For games involving more groups (like in the old apothecary chess) it is just the fact that each group gets to have it's own orderring and the max posibilities are group one posibilities times group two possibilities times so on. And if the groups are disjoined the integer is unique given by the formula: group1rank+group2rank*group1max+group3rank*group1max*group2max and so on. This could lead to redundancies if a piece appears in different groups, but I think we ca live with that.

[fire_varan]

Project looks exciting! May I ask which Shogi Variants it covers?

[ovenel]

I remember reading the article you had written about Paco Shako on the Chess Variants website and being happily surprised at the fact that the interactive diagram could actually play the variant. So I'm definitely excited to see how this project progresses.

Do the movement and "capture" rules in Paco Shako complicate the designs for moves that you've been discussing here? In particular the capture rules wherein pieces join together into a combined piece that may be moved by either player seems complicated. But I think the fact that each player still uses the standard movement rules of their piece probably makes it simpler than I'm thinking it is. The chaining of released pieces also seem like a complication as it means that one player may make multiple moves in a single turn, and also that moving away from one square does not necessarily mean that the original square is now unoccupied. I think that your "Hook Moves" cover this concept, but I'm not sure if the lack of actual captures on these squares is an issue.

[hgm]

Project looks exciting! May I ask which Shogi Variants it covers?

Basically all those without piece drops. But board size might be a concern. I suppose we should be a bit generous with the data sizes, i.e. not assume that the square numbers must fit in a single byte.

[hgm]

I remember reading the article you had written about Paco Shako on the Chess Variants website and being happily surprised at the fact that the interactive diagram could actually play the variant. So I'm definitely excited to see how this project progresses.

Especially the release chains are troublesome. I had to write a lot of dedicated code for that to get the Interactive Diagram to play it. Paco Shako is so different from any other chess variant that it doesn't make much sense to configure a general chess-variant engine for it. The engine I had in mind in this project would be limited to more regular chess variants, where a move consists of changing the position (and possibly type) of a single piece of the player that is on move, plus making a certain number of pieces (say maximally three) disappear elsewhere. And allow the pieces that move to basically move along any conceivable path.

Pako Shako doesn't conform to that model; it has pieces that can be moved by both players.

Paco Shako could best be played by a dedicated engine. Play could be improved enormously by making an analysis of release networks as a prelude to move generation. It should recognize closed-loop release chains, and label those plus all piece pairs that attack it as a transporter network, building a table for where each piece type that enters the network in a given node could emerge from it. That would releave it from searchin enormous trees of possible releases.

E.g. suppose in the Diagram below the white Bishop and two white Rooks are paired with some black piece:

[d]B2n3k/8/2R2R2/8/8/Q7/8/8 w
The Rooks attack each other, and form the closed-loop core of a transport network. The Bishop makes an attack on this core, and is thus also a transport node. The (unpaired) Queen can now travel through this network, via a8 - c6 - f6 - h8 to capture the black King. In terms of moves this would require Qxh8 Bxc6 Rxf6 Rxc6 Bxa8 Qxc6 Rxf6 Rxc6 Qxf6 Rxc6 Rxf6 Kxh8. So searching per move would require a 12 ply search to see you can capture the King in this turn. Recognizing a8, c6 and f6 as transport nodes, already reduces this to Qxh8 Qxc6 Qxf6 Qxh8, i.e. only 4 ply. You can skip the internal functioning of the network needed to transfer the move back to the piece that entered it. An even more advanced analysis would have told you that a Queen can leave the network anywhare, no matter where it entered, because all nodes are connected by Queen moves. That redusces the number of ply to search to two: Qxh8 enters the network, Qf6xh8 leaves it, and you don't have to worry about how exactly the Queen moved through the network.

[catugocatugocatugo]

I was hoping for drop games to work, too. For the interactive diagram, from chessvariants.com this was virtually impossible as it is very shallow in terms of search depth. This being a C++ local functioning program should have this problem ameliorated. Also, NNUE could help here too. On the other hand, you know your craft very well, so I think if you say it is difficult to do, maybe it is.

[fire_varan]

Project looks exciting! May I ask which Shogi Variants it covers?

Basically all those without piece drops. But board size might be a concern. I suppose we should be a bit generous with the data sizes, i.e. not assume that the square numbers must fit in a single byte.

Thanks for the answer, would enjoy an opportunity to test your engine in my GUI which supports 10 Shogi Variants already:
https://github.com/fire-lizard/QBoard/r ... /tag/0.9.9