TalkChess.com

I am thinking of adding a new command to WB protocol, which would allow an engine to send a description to the GUI for how to generate pseudo-legal moves for a certain piece type. Something like

piece ID NAME MOVESPEC

for example

piece A Archbishop BN
piece C Colonel FfsRbWfhN
piece Berolina_Pawn fmFfcW=Q,R,B,N
piece H Horse W-F
piece C Cannon mRpR-cR
piece G Grasshopper pQ-K
piece L Lance fR=+L
piece +L Gold WfF
piece W Contact_Withdrawer otmcK-bK-mQ
piece F Rifle_Withdrawer otcQ-ebQ-mQ

So the ID would be the letter that tells the GUI which piece of the FEN describing the initial position this refers to. Then follows a name, which can be used in menus for selecting promotion piece, setting up positions, etc. Finally the way the piece moves is described in extended Betza notation.

This would allow the GUI to play variants with arbitrary pieces; all the engine has to do is send a piece command for every piece the variant uses. The MOVESPEC would also contain information about possible promotion choices for the piece.

The extended Betza notation would allow specification of multi-leg moves, and has the following syntax:

<spec> := <path> | <path> <spec>
<path> := <slide> | <slide> - <path>
<slide> := <leg> | <leg> <dressed exponent>
<leg> := <modifiers> <atom>
<modifiers> := <special effects> <directionset> <modality>
<atom> := ( <spec> ) | <shotcut> | W | F | D | N | A | H | L | J | G
<shortcut> := K | Q | R | B
<directionset> := <direction> <directionset> | <direction>
<direction> := l | r | f | b | v | s | h | a | <empty>
<modality> := <action> | <action> <modality>
<action> := m | c | d | p | t | u | o | <empty>
<special effects> := <effect> | <effect> <special effects>
<effect> := x | e | i | <empty>
<dressed exponent> := <modifiers> <number>
<empty> :=

The atoms refer to sets of symmetry-equivalent moves of a certain length. The modifiers specify what these steps can do (modality), and optionally select a subset of directions from it (e.g. to support asymmetric pieces). The meaning of the directions is reasonably intuitive, if you realize that v (vertical) is a shortcut for fb = f or b, and s (sideway) a shortcut for lr = l or r.

The modality is more tricky; for legs of a multi-leg moves there are many possibilities, as the old occupant of the visited square doesn't have to be captured if you plan to move on. The meaning is the following:
The last 4 things you obviously cannot do in the final leg, as they would not leave you a place to land the piece on. When a leg cannot do any of the actions that its modality allows, because of the state of the square it wants to go to, that leg 'fails', and with it the whole move. But a spec in general specifies many alternative realizations (e.g. the simple spec 'K' represents a set of 8 moves), and some may fail (e.g. to squares that contain a friend), but the ones that don't (move or capture, because mc is the default modality) are the legal moves. A simple use of multi-leg is the Xiangqi Horse, mW-fmcF, which maing use of implied defaults for modality in the context of the chaining operator - would collapse to W-F. The W step to the orthogonal neighbor square is move-only, and thus blocked by friend or foe, (which make an m-step fail), but when it is empty, it succeeds, and the outward (f) diagonal step (F) is tried with 'capture or move' (mc) modality. (And might still fail if the target square contains a friend.)

Together these possible actions can specify moves that implement a wide variety of side effect. You can for instance specify side-effect captures by a multi-leg move that visits the squares to capture as intermediates. E.g. a Checker does one forward diagonal step to capture, and then mandatorily continues with s second step to move: fcF-fmF, where F is the 1-step diagonal atom. (The second 'f' is referred to the previousstep, i.e. 'forward' always means 'continue in the same direction'.)

Rifle captures can be done by capturing in the normal Chess way, and then in a second leg move back by an equal amount. A Rifle Rook would be mRcR-ebR, the mR part describing its non-capture moves, the cR-ebR the captures mandatorily followed by an equal (=e) Rook step in the opposite (=b) direction, to end where you started.

Moves like castling (or catapult pieces) can be written by first capturing (or destroying, depending on who owns it) the piece you want to displace as a side effect, and with the unload operation you can then carry it elsewhere, before going to your own destination. E.g. Q-side castling could be specified on a Rook by latting it first capture its own King on e1, then carry it to c1, and finally move to d1: irdiW04-buW02-bmW. Here the i modifier means 'initial', i.e. for virgin piece only, the first leg is exactly 4 rW steps (04 means exactly, 4 woud mean 1-4) to pick up the virgin King, then double-back exactly 2 W steps to offload that King, and reverse direction again to move end up on d1.

x is an explosion operator, allowing multiple alternative realizations of a move spec to be all executed in parallel (i.e. capture stuff in all 8 directions, as in Atomic Chess, would be an -xacdK final leg piggy-backed on all capture moves).

The proposal looks very complicated for a limited use.

Can the same functionality not easier, and more generally, be obtained by a 'listmoves [ pos ]' command, which outputs all legal moves in the current or given position (and possibly the resulting FEN)? I can see other applications such as book making using that.

It is meant for playing many variants in winboard which right now is handled in a rather difficult way. I think HG is trying to simplify this by allowing engines to send piece movement information before game starts so that winboard would know if to refute illegal moves. Right now it does allow you to update the board for an arbitrary game but it trusts the engines to play legal moves etc, so the GUI becomes pretty much a spectator. So such protocol definition could help to avoid this problem by extracting the rules of the game from the engines.

@HG, I do not understand Betza notation but it looks like it is a common notation in variants. I will post my opinion once I understand that and read the details of the spec carefully.

mvk wrote:Can the same functionality not easier, and more generally, be obtained by a 'listmoves [ pos ]' command, which outputs all legal moves in the current or given position (and possibly the resulting FEN)? I can see other applications such as book making using that.

The main problem is conversion to and from SAN. When the GUI doesn't know how the pieces move, it could not decode SAN moves the engine sent it, if two or more pieces of the same type are present. So it must send moves in long-algebraic, which is a rule-independent notation. But the GUI would want to display the moves, and in particular the PV, in SAN. And then you don't want to have to send every position along the PV to the (playing or referee) engine to request a list of legal moves in that position, so you could convert that move to SAN. An engine might spit out some hundred moves in PVs in the first second...

Of course you could require the engine to send the PV both in long algebraic and in SAN. (With only SAN the variation board would not work.) But converting to SAN is actually on-trivial, and I don't want to put the burden on engine authors to add a SAN converter. Much simpler to let him tell at startup how his pieces move, with a handful of fixed printfs for fixed messages. And it is pretty ugly to send things in duplicate anyway.

Daniel Shawul wrote:@HG, I do not understand Betza notation but it looks like it is a common notation in variants. I will post my opinion once I understand that and read the details of the spec carefully.

It is indeed in very common use amongst variantists. Basically it decomposes the moves of the piece into' atoms', (indicated b capitals), which are the maximally symmetric sets of moves of a certain length (4 or 8 symmerty-equivalent moves). So the atom 'N' stands for all 8 Knight moves, and NA is a piece that can move as Knight + (Shatranj) Elephant. To decribe pieces with reduced symmetry, you can use lower-case directional prefixes to indicate a subset (e.g. fN = forward Knight, as in Shogi). By default a move can both capture and non-capture; with prefixes m and c you can limit their abilities to one of the two. So a piece that moves as King, but captures as Knight would be mKcN. You can also specify steps can be repeated, to turn leapers into sliders/riders. Most piece descriptions look very simple in Betza notation, as most variants use symmetric pieces. (with the notable exception of Shogi, where pieces like vRbB (vertical Rook + backward Bishop) are quite common).

That is basically all. But to make it sufficiently general, I proposed an extension for multi-leg moving (where blockable moves like that of the Xiangqi Horse are treated as a two-leg move to probe for a blocker with the first leg). A short overview of the extended system is at http://hgm.nubati.net/rules/Betza.html .

hgm wrote:

mvk wrote:Can the same functionality not easier, and more generally, be obtained by a 'listmoves [ pos ]' command, which outputs all legal moves in the current or given position (and possibly the resulting FEN)? I can see other applications such as book making using that.

The main problem is conversion to and from SAN. When the GUI doesn't know how the pieces move, it could not decode SAN moves the engine sent it, if two or more pieces of the same type are present. So it must send moves in long-algebraic, which is a rule-independent notation. But the GUI would want to display the moves, and in particular the PV, in SAN. And then you don't want to have to send every position along the PV to the (playing or referee) engine to request a list of legal moves in that position, so you could convert that move to SAN. An engine might spit out some hundred moves in PVs in the first second...

Of course you could require the engine to send the PV both in long algebraic and in SAN. (With only SAN the variation board would not work.) But converting to SAN is actually on-trivial, and I don't want to put the burden on engine authors to add a SAN converter. Much simpler to let him tell at startup how his pieces move, with a handful of fixed printfs for fixed messages. And it is pretty ugly to send things in duplicate anyway.

That is the reason I proposed to output resulting FENs with 'listmoves' alongside the moves, the resulting FEN to be used for all displaying and highlighting purposes and the move seen as an opaque string. Then the SAN can be used for decoration purposes, no need to parse it in the GUI. (FWIW, even replying with 'longmove shortmove resulltingFEN' would work). If bandwidth is a concern, which I don't immediately see because PVs can already be sent in SAN, then specify a 'makemove'-like command that asks the engine to converts the current or a specific FEN plus a move string into the resulting FEN. So an alternative command besides dumping all moves with 'listmoves'.

Essentially the difference is that the original proposal tries to communicate an executable function to the GUI, which will never be complete as new variants can always invent new types of moves not anticipated in the notation, and the alternative proposal offers a service hiding all the details, just mapping position strings to move strings and new position strings.

mvk wrote:That is the reason I proposed to output resulting FENs with 'listmoves' alongside the moves, the resulting FEN to be used for all displaying and highlighting purposes and the move seen as an opaque string.

This indeed makes sense, and in the Alien Edition of the protocol it is exactly what we do for the moves at game level. Let the engine send a board after every move.

Then the SAN can be used for decoration purposes, no need to parse it in the GUI. (FWIW, even replying with 'longmove shortmove resulltingFEN' would work). If bandwidth is a concern, which I don't immediately see because PVs can already be sent in SAN, ...

The problem with PVs in SAN is that the variation board would not work. So the PV would not have so much have to be sent in SAN, they would have to be sent as FENs.

This is asking a lot from the engine, however.

Essentially the difference is that the original proposal tries to communicate an executable function to the GUI, which will never be complete as new variants can always invent new types of moves not anticipated in the notation, and the alternative proposal offers a service hiding all the details, just mapping position strings to move strings and new position strings.

This is true, but perhaps requiring it to be able to handle everything is just expecting too much. I would be quite happy if it would handle 99% of the cases, if handling 0.9% more would require it to be a hundred times more complex. And in particular I would be happy if it solves problems that actually exist, rather hypothetical problems. In particular it annoys me that a simple variant such as Chess with Different Armies that happens to employ Unicorns, which moves forward as a Knight and backward or sideways as a King, produces awful notation. A departure from ortho-Chess that could be made by a simple modification of the move-generator (or even just the tables it uses). Would it really be resaonable to require from the engine author to require that he now lets the engine play out every PV to generate FENs after every move of it, and send those to the GUI. (Or create the FENS during search, and back them up together with the PV in a tri-angular array of FENs.) To me that sounds very unreasonable. (Especially since I am the author of that engine! )

Sending complete FENs after every move does seem overkill for this problem. There are hardly any games that change the complete board with every single move. Even the most unfavorable case in Atomic just changes 9 squares from what you would have expected in ortho-Chess. So sending unexpected board mutations as extra moves is easily an order of magnitude simpler. With moves to drop a piece, and an extra notation for a move to drop an empty square, you can always do anything.

Even requiring the engine to produce SAN seems a highly unreasonable request to me. For every move it puts in a PV it would now have to figure out if there is another legal move of a piece of the same type that could go to the same square.

It is true that only a function could handle every conceivable piece. But the extended Betza notation I defined is extremely powerful, and there isn't much that it could not do. Writing an interpreter for it to use as GUI move generator could be much simpler than writing code to have an engine convert its PV to SAN. And it would only have to be done for the GUI. Engines just have to print fixed string.\\Ad one doesn't have to exclude the other. There is nothing against allowing engines to define simple (and most not-so-simple) pieces to the GUI in these piece commands, and still allow it to send FENs or other cues with its PV that allows performing the moves by an ignorant GUI.

I'm not convinced the alternative proposal requires every engine to implement SAN. Only the rule-giving engine, maybe, if the details get worked out with care.

Anyway, the proposal is based on a complexity argument and on reuse in different contexts. I will not argue complexity further, because those are not fruitful discussions in general. I should point out reuse in other contexts, for example automated opening graph exploration. For this it is extremely useful to have access to the generator and make move function.

Lets put it in another perspective: if, hypothetically, the 'listmoves/makemove'-like commands were already present in the engine protocol, would you then still need an additional language at startup to convey piece movements? Probably not. On the other hand, those applications that benefit from a game state traversal service can't do much with the raw piece descriptions unless they are willing to implement an interpreter. So there would still be need for the service.

'Need' is a relative concept. I don't need an airplane to go to Greece, I could walk. But from the practical POV, I am convinced it would not work acceptably at all when the GUI, for each move of any PV it receives from the playing engine, would have to put an engine in that position, and then request the entire move list for it to see what disambiguators the SAN would need.

And your question is not so hypothetical; XBoard might not have a 'listmoves' command yet, but it has the 'lift SQUARE' command, which it can use to interrogate the engine for the moves of a particular piece. It gets back the answer as a FEN of move targets, but that is in fact a reasonably compact way to express the moves. If one Knight moves, it would only have to 'lift' the other Knight in that position, to check if the to-square of the moved Knight is also a target of the other one. That single highlight FEN would be much more compact than the entire movelist for the position.

So I could use that, but I have zero confidence that it will work. It would be awful to step a referee engine through all moves of a PV send by the playing one, remember on each input event you get back for it what is supposed to be coming in, and keep the engines in sync. (E.g. what if the playing engine already ends me a new PV while the referee has not send me all the movelists for the previous PV yet? Should I queue them? What if the pipe to the referee fills up so that the GUI blocks when writing it?)

It seems an order of magnitude simpler to just ask the engine: "give me your move generator, please", and do the job yourself.

'Reusing in other contexts' for me means that Fairy-Max and XBoard could use the same move generator, driven by the same piece-descriptor strings. Of course XBoard would have a move generator, and use the strings it received to control its operation, which currently is hard-coded. But perhaps I do not properly understand what you mean by 'other applications'. I assume 'other tasks performed by XBoard', but perhaps you mean 'other independent programs that also talk to an engine'.

If I would put a 'Betza-string-to-moves' interpreter in Fairy-Max, so that its fmax.ini file in the future would allow piece description in Betza strings rather than the cumbersome custom format it uses now (which requires you to specify the moves in each direction separately), it would be public domain, and everyone could use it. I would probably write it as a compiler rather than an interpreter, compiling to some intermediate code similar to Fairy-Max' current move-generator tables (i.e. creating separate code for each direction, but a bit more general (Fairy-Max only allows two 'legs' per move, possibly alternating them, and I would want to up that to an arbitrary number.) The actual move generator would then 'interpret' the intermediate code, which would be something like triples (board-step, move-rights, range) for each leg of the move, where the move-rights would imply whether another leg will follow given the way the current one terminated.

hgm wrote:I am convinced it would not work acceptably at all when the GUI, for each move of any PV it receives from the playing engine, would have to put an engine in that position, and then request the entire move list for it to see what disambiguators the SAN would need.

That is not a necessary consequence of the proposal.

But perhaps I do not properly understand what you mean by 'other applications'. I assume 'other tasks performed by XBoard', but perhaps you mean 'other independent programs that also talk to an engine'.

The latter indeed.