 |
Shufflix: Frequently Asked Questions
|
How does Shufflix prevent that the same hands are
used twice?
Every once in a while, hands from one tournament show up in another
tournament.
This is always embarrassing to the tournament organizers. The latest
mishap of this sort was at the Junior Teams World Championships in Brazil
in August 2001. At this event, the same hands were accidentally used
for two different sessions.
This mishap usually does not happen because the software in use has
generated the same sequence of hands in two different runs. Instead,
the accident is usually caused after the hands have been generated by the
dealing software. This can happen in several ways, e.g.:
-
A file with a sequence of hands generated for one session is
accidentally
reused in another session.
-
The boards form another session are reuseed for a later session, and
accidentally
the duplication of the hands into the boards was skipped.
The dealing software in itself cannot guarantee against mishaps like these,
but it can incorporate features that make these accidents unlikely,
especially
if supported by administrative routines for handling the boards and hand
records.
This is the procedure used at DBF (Denmark) to guard against using a
sequence of hands for a session where it was not intended:
-
When the hands are dealt, the operator has explicitly named the
tournament,
session, and planned playing date as part of the input to the dealing
process.
-
This tournament identification data is carried along with the dealt
sequence
of hands in all file formats where it is at all possible. Thus the
tournament identification also appears on printed hand records.
-
When the boards are delivered to the tournament site, they are
accompanied
by a sealed envelope with the hand records, including the identification
of the session.
-
As part of the process of distriubuting boards to the playing table, a
tournament
director breaks the seal on the hand records, selects a board from each
set of boards, and verifies that the board corresponds to the hand
records.
-
The tournament director also verifies that the session listed on the
hand
records is actually the session about to be played.
Steps (1) and (2) have been included as part of KG since the first release
in 1990, and this practice is carried over into Shufflix. Steps (4)
and (5) depend on ample training of tournament directors, including the
self-discipline to perform a checking task that almost never catches any
mistake.
If a set of boards accidentally have been delivered to a session without
being properly duplicated, this problem is usually discovered at step
(4).
And if a set of boards has accidentally been reused for a session that
it was not intended for, this problem is usually discovered at step (5).
Like all procedures for human work, this procedure is not
infallible.
In practice, however, it reduces the frequency of the mishaps
considerably.
Well, Shufflix could have generated the same run of
boards twice anyway, right?
Wrong. There are two ways that Shufflix can generate the same sequence
of boards.
-
Because it got into a rut, e.g. started each sequence with the same
seed.
-
By pure chance - since there is always a chance that each board is
identical
to some other board dealt earlier.
Shufflix cannot get into a rut like that. For Shufflix to generate
the same boards in the same way on two different runs, the following start
conditions have to be identical:
-
The tournament (and session) name, as entered by the user.
-
The date of the event, as entered by the user.
-
The date and time of the run of Shufflix (measured in seconds).
-
The 128 random bits used to make the result unpredictable.
By definition, if the user intends his boards for a different event, he
will also enter different tournament identification data. Shufflix
then already is in a different rut.
Now the, what if the same board sequence gets generated twice by pure
chance? Let us look at that probability. There are about 296
different possible boards. If a session is, say, 25 boards, that
gives about 22400 different possible sequences of boards for
a session. The statistical phenomenon called the birthday paradox
tells us that we need to run about 21200 sequences before the
probability that we will have run two identical sequences of 25 boards
approaches 50%. 21200 is such a huge number that this
possibility can be ruled out.
So what happens if the operator always gives the
same session id and date?
Well, in this case the operator is making himself vulnerable to human error
in the subsequent handling of the boards, as described in another question
above. Experience shows that within 10 years of operation - often
much sooner - some human error is going to cause the same boards to be
reused by accident.
However, assuming infallible human operations, let us see what the
chances
are in this scenario of generating the same boards twice. Since the
operator does not vary his identification, we are left with the variation
of the computer clock and the 128 random bits used to make the result
unpredictable.
That still leaves 2128 different sequences that can be
generated
by the operator input - and every time a second passes on the computer
clock, these 2128 sequences are replaced by a new set of 2128
different possible sequences. The birthday paradox agains tells us
that Shufflix needs to generate 264 sequences in any given
second
for the probability of that two identical sequences are generated during
that second to approach 50 %. With the incredibly huge numbers we
discussed above, 264 may not seem very big. But it is.
It is more than one billion (about 230) sequences for every
living person on Earth (about 233); and we were talking about
one second here.
So the conclusion would have to be that if the same Shufflix sequence
shows up twice, this really is because the result of the same run of
Shufflix
has been used twice by accident.
Is human error also the cause of reuse of sequences
for other dealing programs?
Almost certainly. Other dealing programs used for serious tournaments also
have huge numbers of different possible sequences that they can
generate.
Hans van Staverens Bigdeal generates 2160 equally probable
sequences
for each installation. KG from Alesia Software uses a concept of
preshuffling (more than 2200 different outcomes) and then
generates
more than 247 different sequences for each preshuffling, yielding
a possible variation of more than 2247 different sequences.
Can the operator guess the hand sequence produced
by Shufflix in advance?
No. To do so, he would initially have to guess 128 unpredictable
random bits. That is infeasible.
Can the Shufflix programmer guess the hand sequence
produced by Shufflix in advance?
No. To do so, he would initially have to guess 128 unpredictable
random bits. That is infeasible.
But the Shufflix programmer can cheat in the code,
right?
Presumably. However, the code is publicly
available
for all sceptics to read. And, the code is not very complicated nor very
voluminous. That should give some kind of assurance that the programmer
did not cheat.
Can the operator rig the cards?
Yes. He can alter the output of the Shufflix run. Or he can mock up a
sequence
of hands that looks as if it was produced by Shufflix. There is really
no way to prevent that. But it is possible to run an audit that
reveals
whether he has done so. Shufflix accompanies all files containing
the sequence of hands produced with all the input that went into producing
them. It is then possible for an auditor to verify that a run of
Shufflix with this input does indeed produce this sequence of hands.
Also, note that it is not feasible for the operator to generate input that
will produce a desired output.
The possiblity of auditing helps keep operators honest. The
operators
were probably honest in the first place. So more importantly, the
audit trail helps build confidence in the public and the among the
participants
that the deals are not rigged.
But the operator can still generate thousands of runs
and select an "interesting" one, right?
Well, yes. If he is in collusion with a participant, he can also
out of a thousand runs select one where the spade ace is in an agreed hand
for the first four boards. But if he is in collusion with a
participant,
he might as well slip that participant a copy of the hand records.
To keep the operator honest - in the sense that he only does one run
for a given session - Shufflix can be used in a special procedure that
makes it at least very difficult for the operator to generate several runs
and choose one of the results. Here is a sketch of such a procedure:
-
A number of independent auditors - these could be players in the event
- participate in the dealing process. Let us assume that are four
such auditors.
-
Just before the dealing is to take place, each of the four auditors
selects
8 unpredictably random hexadecimal digits (by flipping a coin 32 times
or by some equally unpredictable process). These 32 hexadecimal
digits
are published immediately and appended to the tournament identification.
-
Shufflix is run to generate the hands of the tournament. The
resulting
output (in casu the .tso file) is hashed to a message digest, which is
also published immediately.
-
After the session has been run, the hand records are published.
-
Based on the hand records, the message digest of the .tso file can be
verified
by auditing; this demonstrates that the dealt hands were not altered
after
the message digest was published.
-
Based on the hand records, it can be verified that the auditors' random
digits were indeed used. This demonstrates that the Shufflix run
was not made before the 32 random hexadecimal digits were made
available.
Note that this procedure does not affect the basic properties of Shufflix:
the sequence of deals is as unbiased an unpredictable as ever.
This procedure is probably mostly of theoretical interest. In
practice, the operator is going to part of a trusted organization with
internal mutual checks.
How does Shufflix guard against snoopers on the
Internet?
Shufflix uses the HTTPS protocol, which protects the transmission by means
of encryption. This is the same mechanism that is used to protect bankning
transactions on the internet.
Why can't someone else read my boards with his
browser, when I can?
You can access the deals yourself because the path name to the deals is
embedded in the encrypted response you get from Shufflix when your boards
are dealt.
Someone else trying to read the deals is not so lucky:
-
The snooper does not know the path name of your deals. That path
name contains an unpredictable random sequence of 32 hexadecimal digits
(128 unpredictable random bits). The snooper has a one chance in
2128 of guessing that on each try. So he won't guess
the
path name needed.
-
Once you are done with your deals, you should press the red delete
button for your deals. The files with the deals are then removed
from the server. At this stage, it is no longer helpful to guess
the path name correctly. Even you yourself can no longer retrieve
the deals.
Shufflix cleans up old deals continually. Therefore, even if
you don't press the delete button, Shufflix will eventually remove the
files that contain your deals.
Is every different bridge board possible in every
sequence generated?
Certainly. There are around 296 different ways a bridge
board can be dealt. And there are 2128 different ways
that Shufflix can generate a sequence of boards for any given input.
Since 2128 / 296 = 232, that yields an
average of around 232 different ways that any sequence for a
session can start with any deal. 232 is around 4 billion.
Version 2017-09-26 / jbc