CECP: Chess variants with dice

[hgm]

In some Chess variants you have to roll dice (or draw cards, which is somewhat equivalent) to decide what moves you are allowed to choose from. E.g. the Alfonso codex mentions a version of Grant Acedrex where you have to decide what piece type to move by throwing an 8-sided die.

The current version of XBoard protocol could do this in a kludgy way for human-engine games, by letting the engine decide which piece type you must move, and tell that to the user at the beginning of that user's move through a popup ordered with a "telluser" command (e.g. "telluser You must now move a Bishop"). It can then reject all moves with other pieces as illegal.

This seems pretty annoying, however. But there might be a better way: XBoard with legality checking off allows engines to click squares on behalf of the user, through a "click" command. (This was originally intended for implementing one-click moving in variants with unknown rules, so that the engine could finish the move with a to-click if the from-click implied there would be only a single legal move with that piece.) The engine could simply send a "click" command to pre-select a piece of a type it randomly picked at the beginning of every opponent turn. The user would see the piece selected, and knows he should move that, or at most would be allowed to select another piece of a similar type. The engine could either reject moves with other pieces when they are made, or immediately deselect any other piece the user tries to grab (as revealed to it by a "lift" command) with a second "click" command on that square, or repeat the selection of the piece of the right type. This sounds more convenient than using popups.

For engine-engine games none of this works (no clicks on the board in this mode, and telluser messages are not relayed to the opponent engine). Engines for variants with rules unknown to the GUI must be able to check the legality of their opponent moves themselves, so that disagreements will brought to the attention of the user. And they cannot be allowed to throw the dice themselves, as this offers to much of an opportunity to cheat.

So I want to extend CECP with a bidirectional command "dice":

When an engine sends "dice N" to the GUI, the latter interprets this as a request to generate a pseudo-random integer homogeneously distributed in the range 1-N. The GUI will send a command "dice M" in reaction to this, to BOTH engines, with 1 <= M <= N, notifying them that dice were used, and what the outcome was. The engine that is on move should make the dice request if it wants to make a move that involves dice, and should then do a move that conforms to the outcome of the roll. The opponent also got the outcome of the roll, and thus can check the legality of the move, given this outcome. It should be prepared for a long wait between the "dice" command and the corresponding move, as the opponent would usually throw the dice at the beginning of his turn, and then start thinking on the move. It would probably only start to ponder after receiving the dice result.

[stegemma]

In some Chess variants you have to roll dice (or draw cards, which is somewhat equivalent) to decide what moves you are allowed to choose from. E.g. the Alfonso codex mentions a version of Grant Acedrex where you have to decide what piece type to move by throwing an 8-sided die.

The current version of XBoard protocol could do this in a kludgy way for human-engine games, by letting the engine decide which piece type you must move, and tell that to the user at the beginning of that user's move through a popup ordered with a "telluser" command (e.g. "telluser You must now move a Bishop"). It can then reject all moves with other pieces as illegal.

This seems pretty annoying, however. But there might be a better way: XBoard with legality checking off allows engines to click squares on behalf of the user, through a "click" command. (This was originally intended for implementing one-click moving in variants with unknown rules, so that the engine could finish the move with a to-click if the from-click implied there would be only a single legal move with that piece.) The engine could simply send a "click" command to pre-select a piece of a type it randomly picked at the beginning of every opponent turn. The user would see the piece selected, and knows he should move that, or at most would be allowed to select another piece of a similar type. The engine could either reject moves with other pieces when they are made, or immediately deselect any other piece the user tries to grab (as revealed to it by a "lift" command) with a second "click" command on that square, or repeat the selection of the piece of the right type. This sounds more convenient than using popups.

For engine-engine games none of this works (no clicks on the board in this mode, and telluser messages are not relayed to the opponent engine). Engines for variants with rules unknown to the GUI must be able to check the legality of their opponent moves themselves, so that disagreements will brought to the attention of the user. And they cannot be allowed to throw the dice themselves, as this offers to much of an opportunity to cheat.

So I want to extend CECP with a bidirectional command "dice":

When an engine sends "dice N" to the GUI, the latter interprets this as a request to generate a pseudo-random integer homogeneously distributed in the range 1-N. The GUI will send a command "dice M" in reaction to this, to BOTH engines, with 1 <= M <= N, notifying them that dice were used, and what the outcome was. The engine that is on move should make the dice request if it wants to make a move that involves dice, and should then do a move that conforms to the outcome of the roll. The opponent also got the outcome of the roll, and thus can check the legality of the move, given this outcome. It should be prepared for a long wait between the "dice" command and the corresponding move, as the opponent would usually throw the dice at the beginning of his turn, and then start thinking on the move. It would probably only start to ponder after receiving the dice result.

I think that the use of a dice should be handled as a chess-variant, so it is the GUI that inform the engine that it should use a dice number, to move, not the engine that requires a dice number to the GUI. This could be done sending from the GUI the "dice" command to the engine before the GO command (or as an extension to GO command: "go dice N". An "odice N" command should be sent back to the engine after the GUI received a move, to inform the engine itself of the dice used for the Opponent (if not snet, the engine have to ponder on any possible value).

So, the "dice" itself should be an option of chess-variants, i think.

[hgm]

This seems to assume the GUI would know the game rules. Which is normally not the case. In general only the engine knows the rules. So the engine would have to tell the GUI at some point to use dice, either interactively per case, or as a general rule at the start of the game.

It would be pretty hard, however, to devise a general method to instruct the GUI when to use dice, and what the value range should be. It is even doubtful this is possible in principle.

E.g. in Raindrop Chess you start with all pieces next to the board, and you have to draw cards that specify which piece to drop on the board. But you can also move pieces that are already on the board, without drawing a card. You cannot draw a card, and if you don't like what it says, decide to move on the board rather than drop what the card specifies. Drawing a card commits you to dropping the corresponding piece. But you can still make the choice where to drop it dependent on what piece that was.

I don't see how this could be implemented other than by having the engine explicitly request the card (which is abstracted as asking for a random number with a range equal to the number of cards left in the deck). Only the engine can know how many cards there are left in the deck, because the GUI does not have the slightest idea how numbers correspond to card numbers that decrease every time you draw one, or indeed that they are in any way connected to piece drops. So it seems essential that the engine should specify the range of the random number it wants to receive.

Even if the GUI would know the rules of Raindrop Chess (which XBoard certainly doesn't), it could not predict whether a player is going to make a drop move or not.

[Werner Taelemans]

they cannot be allowed to throw the dice themselves, as this offers to much of an opportunity to cheat.

You could use a cryptographic dice protocol (using SHA-256).
That way everything remains between the two engines, and the GUI isn't involved.

Here's my suggestion:

1) At the start of the game the engines generate a 32 byte random number. Let's call it
dice1 for engine1, and dice2 for engine2.

2) When engine2 needs a random number in the range 1-N, it sends the command "throwdice N" to engine1.

3) Engine1 calculates a new (pseudo)random number: R=sha256(dice1 ^ N)

4) Engine1 sends the command "dice R" to engine2

5) Both engines can now calculate the random number, engine2 asked for: M=(R & 0xffffffff) % N + 1

6) Engine1 updates it's dice: dice1^=R;

7) At the end of the game both engines exchange their original dice-number, so that they can verify that the
other side didn't cheat during the game.

[Uri Blass]

they cannot be allowed to throw the dice themselves, as this offers to much of an opportunity to cheat.

You could use a cryptographic dice protocol (using SHA-256).
That way everything remains between the two engines, and the GUI isn't involved.

Here's my suggestion:

1) At the start of the game the engines generate a 32 byte random number. Let's call it
dice1 for engine1, and dice2 for engine2.

2) When engine2 needs a random number in the range 1-N, it sends the command "throwdice N" to engine1.

3) Engine1 calculates a new (pseudo)random number: R=sha256(dice1 ^ N)

4) Engine1 sends the command "dice R" to engine2

5) Both engines can now calculate the random number, engine2 asked for: M=(R & 0xffffffff) % N + 1

6) Engine1 updates it's dice: dice1^=R;

7) At the end of the game both engines exchange their original dice-number, so that they can verify that the
other side didn't cheat during the game.

I wonder how you can verify not cheating after the game without some knowledge of the interface about dice1 and dice2 before the game.

An engine that cheat in the first move may search and find after it cheat a dice number that produce the output that it tried to get.

[hgm]

This is an interesting idea, but engines never communicate directly with each other. They always communicate only with the GUI. So the GUI would have to be involved by recognizing the "throwdice" and "dice" commands as something to be passed to the opponent engine, and passing them on. Seen from the GUI it isn't much more complex to send back a pseudo-random number to the same engine than to pass on the request to the other engine. This would save the engine programmer the trouble of servicing requests for dice throws. And for verification of opponent fair play at the end of the game, as the source of the random numbers is now the GUI.

It might be a good idea to keep distinct names for the engine->GUI request for a random number ("throwdice") and the GUI->engine command supplying it ("dice"). I guess it would also be good to have the engine announce its need for dice through a command "feature dice=1" at startup. So that when the feature is rejected by the GUI, the engine can either exit with an error popup ("telluser"), or take its own, less satisfactory measures for obtaining the random number, rather than sending "throwdice" and hang, waiting for an answer that will never come.

On a GUI that does support the dice feature the engine could also use it to prove its honesty in human-engine games on the moves it makes, by not generating random number by itself, but requesting them from the GUI. A GUI equipped for this could show any such requested dice throw to the user. (This might not be very helpful in the case where the number represents the location of a card in an ordered deck of remaining cards, however.) In human-engine games the engine should also decide what the user can move or drop, and could send a throwdice command to the GUI to obtain that. Which in principle would enable the user to verify if the engine cheats, when the GUI shows the number.

[Werner Taelemans]

...find after it cheat a dice number that produce the output that it tried to get.

This is supposed to be impossible, since SHA-256 is a cryptographically secure one-way function: https://en.wikipedia.org/wiki/One-way_function

[Evert]

I don't see how this will work unless the GUI can somehow verify the intended meaning of the number it generates. You generate "5", and the engine moves a Rook. The next time you generate "3" and the engine again moves a Rook. Is it cheating?

Maybe. If the numbers correspond to piece types. Maybe not, if the numbers are just the ordinate number starting with the first piece encountered from a1-h1. There's no way to know.

That's before getting into numbers not (necessarily) meaning the same thing between different engines.

There is no way for the GUI to know if an engine is cheating without knowing the rules of the game, so it seems pointless to leave it to the GUI to generate a random number as an anti-cheating measure. I think you ultimately have to accept that there is no way to know that engine does not cheat, and assume that it doesn't until you can show that it does (which should show up by skewed statistics). In practice this probably doesn't come up though.

Note that the GUI can already restrict what pieces are allowed to move through the include/exclude mechanic, so if you want to build support specifically for that, then I would re-use that (even though the feature is currently meant for analysis).

[hgm]

This is why the generated random number goes to BOTH engines. The GUI might not know what the number means, but the opponent will. If engine A asks for a dice roll, gets an 8, and then moves a Pawn, the opponent gets both the 8 and the Pawn move, and can then reject the latter as illegal, because it knows that "8" means "move a King". It is the same as in OTB play, really. Using dice only works when both players can see the result of the roll. If only the person having to use the result can see it, you might as well let him do whatever he wants. You must be able to check both that he really lets the impartial laws of physics (or the GUI) determine the outcome, and that he obeyed it.

In human-engine games the human can similarly check the engine, when the GUI would also show him the result of the roll, and if he knows what the numbers mean. In Grant Acedrex with dice this is easy and part of the game rules. You also can only play it OTB if you know which number of pips corresponds to which piece. You can then check both if the engine moves a piece specified by the GUI rather than one of his own choice, and whether the engine allows you to grab the randomly determined piece type through click tricks.

Unfortunately, when the number represents the location of a card in a deck of remaining cards, the relation number -> piece gets very obscure for a human. But that is only because he is playing semi-blindfolded if he doesn't have a physical deck of cards. If he does have the cards, he can simply stack them before the game as the engine does, and draw the card the GUI-generated random specifies, by counting from the top of the deck, and remove that card (or do with it whatever the game rules specify). So the basic problem is that the GUI did simulate a board, but it did not simulate the deck of cards.

A GUI designed for this kind of games could of course display the card deck as well as the board. For that it would need card images, just as for displaying the board it needs piece images.

I even see possibilities for XBoard to do that, in the logo field. XBoard could be made to recalculate an engine logo with a filename that contains %d after each "throwdice", by replacing the %d by the outcome, and loading the corresponding logo image. This assumes a fixed relation between the generated random number and image, which would not exist when drawing cards from a shrinking stock. So perhaps it is better to have the command "throwdice -N" request a random number 1-N, different from any random number produced before. Or define a separate command "takecard" for that purpose. (This would still require different flavors, however, where both players draw from the same stock or each have their own.) To prevent proliferation of CECP commands it might be better to put a second parameter in the "throwdice" command, which can specify the type of random event (for now independent, without put-back from a common pool, or without put-back from private pools).

[Evert]

This is why the generated random number goes to BOTH engines. The GUI might not know what the number means, but the opponent will. If engine A asks for a dice roll, gets an 8, and then moves a Pawn, the opponent gets both the 8 and the Pawn move, and can then reject the latter as illegal, because it knows that "8" means "move a King".

How do you guarantee this? This mapping of piece-ID to die-roll is not public information, there is no defined standard. Implementing the relevant CECP protocol is not enough, you also need to know how other engines label their pieces.

It's a bit similar to assigning piece-ID letters, except that it's an implementation detail that should normally be hidden from the user. Even then, I would argue that the inability of the protocol to translate piece-ID's between two engines that use different IDs is a short-coming, and something that should be avoided for extensions to the protocol like this...