Rolling dice

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
hgm
Posts: 25009
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Rolling dice

Post by hgm » Wed May 27, 2020 8:07 am

Some chess variants use dice or cards to introduce a random element. E.g. in medieval chess one sometimes used a die to determine which piece type had to be moved. Contemporary chess variants that use dice (and are popular amongst AI researchers) are Dice (mini-)Shogi (where a dice roll determines what file your move has to end in), and Einstein Würfelt Nicht. (Although one can argue whether the latter really is a chess variant.) Other variants involve randomization that is more like drawing cards: in Dark Chines Chess all piece (which are flat disks) start shuffled face down, and are only flipped open when you first move them. Which would be equivalent to determining their type by drawing a card at that time. The commercial variant Raindrop Chess starts with an empty board, and instead of moving a piece you can draw a card to determine which piece you must drop on the board. (But you cannot capture before your King is placed.)

GUIs so far only offered the possibility to either let the engine simulate a virtual dice roll, or have it ask for the human opponent to roll a physical die, and enter the result. The latter is slow and not automated, and both methods offer the possibility for cheating, either by the engine or by the user. So it would be better to outsorce a virtual dice roll to a trusted referee, the GUI.

To make this possible I extended CECP ('WB protocol') with a few commands. (See http://hgm.nubati.net/CECP.html for a tentative new specs document.) An engine can send "dice N" to the GUI to request the roll of an N-sided die, to which the GUI will then reply with 'pips K/N', where K = 1...N the outcome of the virtual roll. In engine-engine mode this 'pips' command would go to both engines, so that the opponent can verify whether the followng move complies with the outcome K, and whether there was no cheating with regard to N. The commands can also be used to request rolling several dice at once (e.g. "dice 6 8 4" could be replied to with "pips 1/6 5/8 4/4").

Only engines that printed "feature dice=1" at startup will get the 'pips' command when their opponent rolls the dice. Engines should not send the 'dice' command to GUIs that have not accepted this feature first. In engine-engine mode the 'dice' command of the engine not on move will be ignored, so that engines can always ask for dice roll on behalf of their opponent (which is convenient when the opponent is human).

In engine-human games it is important that (of course) the user can see what the GUI rolled on his behalf. In the implementation I made in XBoard this is shown in the title bar of the board window. But it accumulates the info from all 'pips' commands sent during that turn, to prevent cheating of the form where an engine would keep requesting dice rolls until it gets an outcome that is favorable, giving the user no time to notice the earlier outcomes. Also, during the user's turn, the accumulated outcomes of the previous engine turn remain in view, to prevent an engine could mask what it has done by moving instantly and requesting a dice roll for the human opponent. I tested the implementation with my Einsten Würfelt Nicht engine Pips.

The new specs also propose commands for drawing cards, similar in spirit to the dice/pips protocol. I have not implemented that yet. The situation here is a bit complex, because card draws are not independent events. So you cannot alternate draws of decks of different size like you can switch rolling dice of different size; once a deck of a certain size is used, its new state must be remembered for the rest of the game. There also is the issue of whether both players draw from the same deck, or each have their own. And finally, it makes sens to allow the players to put cards back into the deck. A first XBoard implementation will probably allow each player to use only a single deck; the engine has to specify the size of it when he draws a card, and stick to the same size for the duration of the game. By specifying negative size you can draw from the deck that formally belongs to the opponent.
Get rid of the shit: vote for SHID!

Ras
Posts: 1465
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Rolling dice

Post by Ras » Wed May 27, 2020 11:34 am

hgm wrote:
Wed May 27, 2020 8:07 am
GUIs so far only offered the possibility to either let the engine simulate a virtual dice roll, or have it ask for the human opponent to roll a physical die, and enter the result.
There is a third way that I have seen in the backgammon program GnuBG: you can download high quality random data from some randomness website, and that will be used for the dice rolls. Or you can have a sophisticated RNG along the GUI, maybe a plugin as CLI program, that the GUI can call to generate a random data file without internet connection. That would be much easier to add and doesn't require additional engine or protocol support because the engine would just perceive it as manual rolls which are already implemented.
Rasmus Althoff
https://www.ct800.net

User avatar
hgm
Posts: 25009
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Rolling dice

Post by hgm » Wed May 27, 2020 12:04 pm

I don't understand this. How are 'manual rolls already implemented' if there is no protocol for it? Does the engine somehow communicate to the user directly? Or do you assume there already exists standard protocol for GUI-mediated engine-user communication, such as the CECP 'askuser' command? Are you proposing to reserve one particular reply tag in the 'askuser' command for asking for die rolls, and then have GUIs recognize that tag, and instead of relaying the question to the user in a popup, then supply the answer themselves? In a sense this would also be a protocol extension, but if the reserved tag is sufficiently unlikely, indeed a much less invasive one. E.g. the command "askuser xxxcastdicexxx Result of N M-sided dice rolls:" could be recognized, and the M and N extracted.

Now that I think about it, the CECP 'askuser' command is in fact a general method for 'engine-defined protocol extension'.

One problem I see is that it would probably be undesirable to request a dice roll on behalf of the user, though: in GUIs that do not provide the facility they would then have to enter the result in a popup for seemingly no reason. So it would be convenient if the engine could know whether it is the user or the GUI answering the requests. But it could probably do that from the timing: if the request for its own turn is instantly satisfied, it can assume the GUI supplied it, and safely ask on behalf of the user as well. Or the GUI could put something in the answer that does identify it as a source, like specifying K/N instead of just K (as a user would do).

Hmm... I must say I am starting to like this idea.

How exactly the GUI would get the random numbers seems an unrelated problem, and I never considered it a real problem. It is not that difficult to put a PRNG of sufficient quality in the GUI. It needs random numbers anyway, for the purpose of probing the GUI book.
Get rid of the shit: vote for SHID!

Ras
Posts: 1465
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Rolling dice

Post by Ras » Wed May 27, 2020 12:44 pm

hgm wrote:
Wed May 27, 2020 12:04 pm
How are 'manual rolls already implemented' if there is no protocol for it?
You wrote:
GUIs so far only offered the possibility to either let the engine simulate a virtual dice roll, or have it ask for the human opponent to roll a physical die, and enter the result.
How can GUIs offer manual rolls if it's not possible to implement that? Or did I misunderstand and what you meant was GUIs in general, unrelated to this specific domain?
in GUIs that do not provide the facility they would then have to enter the result in a popup for seemingly no reason.
I think that's not a problem with the CECP feature negotiation because the GUI is supposed to reject unknown ones. Therefore, the engine knows when it has to roll the dice itself. And even if it didn't, it could default to rolling itself, which a GUI without support for manual rolls would never change.

Why I think manual rolls are a good idea: GnuBG is insanely good at "getting lucky". That's because it sets up its position in a way that maximises the expectation value, which is another way of saying its playing dang well. Of course, users think GnuBG is cheating, and they would think the GUI is cheating, too, e.g. by telling the engine beforehand what the dice rolls will be. A manual dice roll makes sure that nobody can know what's going to be rolled next. And guess what, GnuBG gets insanely lucky even with manual dice. :shock:
Rasmus Althoff
https://www.ct800.net

chrisw
Posts: 3810
Joined: Tue Apr 03, 2012 2:28 pm

Re: Rolling dice

Post by chrisw » Wed May 27, 2020 2:16 pm

Ras wrote:
Wed May 27, 2020 12:44 pm
hgm wrote:
Wed May 27, 2020 12:04 pm
How are 'manual rolls already implemented' if there is no protocol for it?
You wrote:
GUIs so far only offered the possibility to either let the engine simulate a virtual dice roll, or have it ask for the human opponent to roll a physical die, and enter the result.
How can GUIs offer manual rolls if it's not possible to implement that? Or did I misunderstand and what you meant was GUIs in general, unrelated to this specific domain?
in GUIs that do not provide the facility they would then have to enter the result in a popup for seemingly no reason.
I think that's not a problem with the CECP feature negotiation because the GUI is supposed to reject unknown ones. Therefore, the engine knows when it has to roll the dice itself. And even if it didn't, it could default to rolling itself, which a GUI without support for manual rolls would never change.

Why I think manual rolls are a good idea: GnuBG is insanely good at "getting lucky". That's because it sets up its position in a way that maximises the expectation value, which is another way of saying its playing dang well. Of course, users think GnuBG is cheating, and they would think the GUI is cheating, too, e.g. by telling the engine beforehand what the dice rolls will be. A manual dice roll makes sure that nobody can know what's going to be rolled next. And guess what, GnuBG gets insanely lucky even with manual dice. :shock:
Commercial backgammon programs get endlessly and repetitively and forcefully accused of cheating with dice rolls, I can remember reams of letters from the same people, and nothing could convince them. The people that continued on the biz later also get the same thing. Maybe some bg apps do cheat , but it’s immensely irritating to be on the receiving end of complaints when “innocent”, so to speak.

User avatar
hgm
Posts: 25009
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Rolling dice

Post by hgm » Wed May 27, 2020 2:25 pm

Ras wrote:
Wed May 27, 2020 12:44 pm
How can GUIs offer manual rolls if it's not possible to implement that? Or did I misunderstand and what you meant was GUIs in general, unrelated to this specific domain?
Ah OK. I thought you were talking about GnuBG. And my earlier remark referred to GUIs fully implementing CECP, although there could of course be GUIs in other domains that allow similar things.
I think that's not a problem with the CECP feature negotiation because the GUI is supposed to reject unknown ones. Therefore, the engine knows when it has to roll the dice itself. And even if it didn't, it could default to rolling itself, which a GUI without support for manual rolls would never change.
Indeed, a new feature would solve it, but that was part of the protocol extension I proposed (feature dice=1). But I thought you meant it could be done in a transparent (to the engine) way, requesting the GUI dice roll the same way as a manual one (and thus through existing protocol). And even if you did not mean that, you seem to have been right about it anyway! :lol:

The old way I did it was using 'askuser' (an almost entirely forgotten CECP command) to ask for the manual dice roll at the start of each turn by default, but offered an engine-defined option that would entrust the engine with rolling the dice automatically. And I did not bother to have the engine ask explicitly for the manual role of the opponent; it would just accept a move with any piece, assuming that the user had chosen the piece corresponding to the dice roll.

Perhaps the GUI should be made to automatically send the engine (and show the user) the result of a dice roll at the start of the human turn, when the engine had requested a dice roll for itself in the preceding turn. That still leaves the problem in the first turn when the user starts.
Why I think manual rolls are a good idea: GnuBG is insanely good at "getting lucky". That's because it sets up its position in a way that maximises the expectation value, which is another way of saying its playing dang well. Of course, users think GnuBG is cheating, and they would think the GUI is cheating, too, e.g. by telling the engine beforehand what the dice rolls will be. A manual dice roll makes sure that nobody can know what's going to be rolled next. And guess what, GnuBG gets insanely lucky even with manual dice. :shock:
This should be less of a concern when the GUI isn't a dedicated GUI for the program, but provided by an independent party. Anyway, it should be a GUI option to decide whether dice-roll requests by the engine should be satisfied automatically (and from which source), or given as user input. The engine should not have to worry about such things.

There also is a very large drawback of manual dice rolls: they are slow, and prevent you from doing enough games to average out the effect of luck.
Get rid of the shit: vote for SHID!

Ras
Posts: 1465
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Rolling dice

Post by Ras » Wed May 27, 2020 3:07 pm

chrisw wrote:
Wed May 27, 2020 2:16 pm
and nothing could convince them.
What convinced me is that it was the same with manual rolls where I knew cheating was technically impossible for the program.
hgm wrote:
Wed May 27, 2020 2:25 pm
But I thought you meant it could be done in a transparent (to the engine) way, requesting the GUI dice roll the same way as a manual one (and thus through existing protocol).
Yeah once that's implemented, the engine wouldn't even know how the GUI came up with the rolls.
The old way I did it was using 'askuser' (an almost entirely forgotten CECP command) to ask for the manual dice roll at the start of each turn by default
The advantage is that this doesn't require additional GUI support, but it limits the options to engine rolls or fully manual ones. The way with external file with high quality random data would require an extremely dirty hack, i.e. the GUI intercepting this specific askuser message.
Perhaps the GUI should be made to automatically send the engine (and show the user) the result of a dice roll at the start of the human turn, when the engine had requested a dice roll for itself in the preceding turn.
That would be useful so that the user can see what the input for the engine was, and guessing which move options the engine even had.
That still leaves the problem in the first turn when the user starts.
If it's the user's turn, the engine won't need to request anything, so this is only between user and GUI. The GUI can have some dice configuration tab, and probably default to a setting which would work smoothly and with all engines: letting the engine roll itself and let the GUI roll and display the dice for the user. That would also be the fallback solution for engines that don't support dice input.
There also is a very large drawback of manual dice rolls: they are slow, and prevent you from doing enough games to average out the effect of luck.
Correct, but it gives the user the option to make sure no software can fudge with the rolls. See my comment for GnuBG - I just needed the manual option to figure out that the program would beat me even then.
Rasmus Althoff
https://www.ct800.net

Post Reply