WB protocol: describing how a piece moves

[Vinvin]

"Zillions of games" had such descriptions (pieces, rules, end, ...) in .zrf files.

http://en.wikipedia.org/wiki/Zillions_o ... g_language

[hgm]

The latter indeed.

Well, then the re-usability you value is guaranteed by the the fact that public code is available to convert the description strings to a move list, in the form of the XBoard move generator. That would enable any application to generate the move list that they otherwise would have to acquire by cumbersome communication with an engine in situ. And it would save them the task of writing a parser for the move list, as the generator could provide the moves immediately in coordinate or square-number representation.

A generalized move could consist of a of a list (piece, square) pairs indicating the required board mutations. Where 'EmptySquare' would be considered a piece. In text form that could be something like e2-e4P, where '-' stands for EmptySquare: clear e2, and put a Pawn on e4. Promotion would be a7-a8Q (when there is a Pawn on a7), e.p. capture would be e5-f5-f6P, castling would be e1-g1Kh1-f1R (or e1-f1-g1Kf1R if we adopt the convention of clearing out squares first, which makes sense to avoid collisions). It would probably be necessary to use colored piece types, for the occasional variant where you can displace opponent pieces during your own turn (catapults and magnetic pieces).

[hgm]

"Zillions of games" had such descriptions (pieces, rules, end, ...) in .zrf files.

http://en.wikipedia.org/wiki/Zillions_o ... g_language

Yes, I know. Zillions is an amazing piece of software. But the game descriptions look more like programs than as simple descriptions, (sort of LISP-like, actually), and require a lot of skill to make.

I was looking for something far simpler. Betza notation is really quite trivial and intuitive, if you stick to regular Chess variants. It describes the pieces just as you would explain them in words. Like "moves like Bishop or Knight". OK, so it is BN. Or "moves as Queen, but captures as King": mQcK. "Moves forward and sideway like Rook, backward like Bishop": fsRbB, "Moves like Rook, but captures like Rook after jumping over an obstacle": mRpR-cR etc. It only gets (moderately) complex when you want to specify pieces that do complex things, depending on board context (e.g. can only move like a Knight if they are protected by a Knight, will remove a piece in the opposite direction as where they are going if an enemy is there, captures things it jumps over, when pieces explode to destroy their surroundings, etc.) But standard idiom could be available for the commonly encountered quirks, making that easy too. (Like: Rifle capture = normal capture and then move back: cX-ebX, explosion = -xxcdK suffix, etc.)

[mvk]

The latter indeed.

Well, then the re-usability you value is guaranteed by the the fact that public code is available to convert the description strings to a move list, in the form of the XBoard move generator.

There is some difference between making something possible and making the same task pleasant for the programmer, of course... The prospect of needing to rip code out of xboard doesn't sound attractive to me. It would be sufficient barrier to not go that way. I don't know how others see that.

[hgm]

There would be not much to 'rip'. All it would take is link with the Betza.o file you would get from compiling XBoard's Betza.c source file, (which would compile independently from any XBoard headers, other than Betza.h), and put a call in your program

Code: Select all

void ProcessMoves(char *moveString, closure, void *closure);

Betza_GenAllMoves( fen, pieceDescriptorString, ProcessMoves, closure);

when you wanted to provide your own function to process the moves, or use

Code: Select all

char moveList[];
Betza_GenAllMoves(fen, pieceDescriptorString, Betza_WriteMoves, moveList);

when you were happpy with the supplied callback for writing moves in a text array, so you could later process them yourself. Of course there would also be a call for generating moves of just a single piece (accepting a FEN and a square).

Writing the latter seems about two orders of magnitude simpler than writing code for starting up an engine through pipes, performing the protover handshake to see if it supports setboard, feeding it setboard or edit commands to set up a position, send it the listmoves command, staring another thread for listening at the engine, and collect the incoming move list. And then you would still have to write your own parser for interpreting the move list, to do with it what you wanted to do. You could not take the shortcut of only providing the routine to process a single move, and pass it to the generator as a callback.

I really don't know how it could be more simple than that. One line of code, and an #include to suppress some warnings...

Good entry points for general use could be

Code: Select all

void Betza_GenAllMoves(char *fen, char *pieceDescription, CallBackFunc cb, void *cl);
void Betza_GenPieceMoves(char *fen, char *square, char *pieceDescription, CallBackFunc cb, void *cl);
void Betza_Setboard(char *FEN, char *board);
int Betza_Square2number(char *square);
void Betza_Compile(char *pieceDescriptor, char **codePointer);
void Betza_Interpret(char *board, int squareNr, char *code);
void Betza_WriteMoves(char *move, void *closure);

[mvk]

About my application:

I already communicate with an engine, because I use the engine for evaluating positions for book making. I need a way to traverse the game graph. I use my own version of 'listmoves' for that. And I would like to do so from Python. I find it odd to use a text protocol and then have to jump into C to make use of what comes back. The point of text protocols is to provide access in a language agnostic way. I also have no need to parse move strings, they are just opaque strings to me that you can give to a move generator to create a new position.

Hope that helps explain the origin of the proposal.

[hgm]

It sounds like something that could be better done by the engine itself. I had Shokidoki make a mini-Shogi book by forcing the Window open at the top of Search() for any requested depth >= 12 (if that was the depth I wanted to use for analyzing the book positions), and abort the IID in open nodes whenever it reached depth >= 12 with a score too far from equality. That nicely 'perfts' through the tree of acceptable positions. And each time it does get a depth 12 score, it writes the path to it to a file, with the score behind it between braces, and a 1-0 or 0-1 behind it if the score is outside the equality window.. (So that WinBoard later sees that as a PGN file, from which I can let it create a book.)

Those were truly minimal changes to the engine; some 5 added code lines, perhaps.

Using an external tool to implement a perft with game rules it doesn't know just doesn't seem an application I should tailor the protocol to. Perft is something better left to the engine.

[mvk]

Using an external tool to implement a perft with game rules it doesn't know just doesn't seem an application I should tailor the protocol to. Perft is something better left to the engine.

I will stop responding after this. All I can say is that perft is an exhaustive, high speed search and booking is a highly selective, low speed, search, and is very unlike the type of search that you would perform during the game.

[hgm]

Well, so 'perfting' was perhaps not the right word. Point is that engines can both do selective searches (alpha-beta) and exhaustive searches (perft), and anything in between. It just depends on how far you force the window open in every node. With {-INF, +INF} you have perft, without forcing you have alpha-beta. Obviously booking is not as selective as true alpha-beta, as you would be interested in multiple moves per position to provide choice. But it is also not so exhaustive as perft. So you open the window to {min(alpha, -delta), max(beta, delta)} to get exact scores on non-best moves that differ an acceptable amount delta in score from the best move. If you want to be a bit more subtle then you could let the amount you open the window depend on how many moves you already have in that node, and what the requested depth is.

So that it is not what you would do during the game is really no indication at all an engine could not do it. You would not do multi-PV during a game, and there are plenty of engines where that is a standard feature... Point is that you want to walk a tree of legal moves, and that is what engines are good at / designed for. Using an external program to do it is just asking for trouble / duplicating effort.

As to the speed, I don't think you have a point. A perft that takes a minute per node is still a perft. Speed has just nothing to do with it.

[hgm]

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

Actually I settled on an interpretable intermediate code that seems simple, powerful and efficient to interpret. It would consist of a list of 2-byte instructions (opcode and operand). The interpreter would step through a sequence of those for generating a single move (starting) in a single direction. While doing so, it would keep track of which board square you are on, and would store side effects ordered by the instructions on two stacks (one for squares to clear, one for pieces to drop). Instructions could fail, (if they don't like the occupant of a square along the path), in which case the stacks are cleared. Or they can succeed, in which case the interpreter goes on with the next step. If the end of the chain is reached, the move is valid, and the move-generation callback is invoked, using the final square and side-effects step to define the move. (And then the stacks are cleared.)

STEP conditionFlags, sideEffects, boardStep
Make the boardStep,
Test if the occupant of that square agrees with the conditionFlags (empty, friend, foe, edge),
Abort move if it isn't,
Push specified side effects (clear square, or drop piece there) on stack.

SCAN conditionFlags, sideEffects, boardStep
Same as STEP, but auto-repeats for as many times as it can.

LOOP count, backwardJump
Take note we executed the preceding loop one more time,
If that was not yet 'count' times...
Goes 'backwardJump' instructions back in the chain,
to recursively call the (uni-directional) interpreter with one extra prefixed iteration,
and then continue with the next instruction.

Most pieces would never use more than those three instructions to specify each of their moves. (And the second one is not really needed, but only added for effciciency reasons, to allow the compiler optimizing some slider loops that have predictable ending.) The chains describing their moves in different directions or of different length would be packed next to each other iinto a 'bundle', prefixed by a byte indicating their length. The 'omni-directional' interpreter would use that length information to step to the next move recipe if it was done with the current one (which might have failed before reaching the end of the recipe). It could implement all leapers, sliders, hoppers, bent riders, lame leapers... Other instructions would only be needed for very special effects:

PIECES pieceSet
The operand is a bitmap specifying which piece types are allowed on the current square'.

SKIP forwardJump
Recursively call the uni-directional interpreter after skipping the specified number of instructions,
then continue with the next instruction.
(For sliding along curved paths, where the loop has to be unrolled because every iteration needs a step in a different direction.)

REPEAT backwardJump
Jump back exactly as many times as the previous slider move looped. (A fixed number of repeats, but not known at compile time, e.g. to make pieces that move in two equally long perpendicular Rook steps to simulate a Bishop.)

MARK
Remember the current square

BACK
Reset the current square to the remembered square

SUICIDE
Terminate succesfully (i.e. call the move generation callback) without putting the piece back on the board

EVAPORATE
Terminate without generating a move, (but reporting success to the caller of the interpreter), and without clearing the side-effect stacks, to accumulate side effects of alternative trajectories of explosion fragments

SCATTER forwardJump
Recursively call the omni-directional interpreter with the code 'forwardJump' instructions downstream, as the move can continue from here in all directions. (For pieces that can change direction arbitrarily between steps.) Typicaly a bundle of paths would at the end all jump to the same new bundle of continuation paths. Always succeeds.

DETECT forwardJump
Like SCATTER, but keeps track of the success of each of the move continuations in the bundle at 'forwardJump', and fails if the do not all succeed, but continues with the next instruction otherwise. (To probe for proximity of immobilizers and such.)