[Deal] [Alesia
Software Home Page]
Hackix - a Quick and Dirty Bridge Dealer
Here is a short Perl program:
$boards = shift; # how many boards for the session?
srand( time ); # seed based on wall clock
@c = split( '', '0123' x 13 ); # init: 52 tokens, 13 of each
while( $boards-- ) {
for $i ( reverse 1..52 ) {
push( @c, splice( @c, int(rand($i)), 1) ); # shuffle tokens
}
print @c, "\n"; # output the deal for one board
}
|
And here is an example of its output, given the input 10:
3200201213233210330013110103122203301200312121303221
1302111323022021303011210213220201132330001102032333
2221321210033133123202020100012333031110201203201313
3030322102101213013332321001233211211013202022310030
1223012130323213213000201122010200110133220101332333
0103321120320132130210003223102313100310021212231332
2313131001233222200011233111032032200301303112201023
1122023231020003303120130203333203120122131012132101
3100121023103320122122000323302120103111312212030333
1323320131330220303210310322011203110212332021120001
|
The program generates series of a random strings, each containing 13 zeroes,
13 ones, 13 twos, and 13 threes. Each of the possible D (D = 52!/13!/13!/13!/13!)
sequences are equally probable, assuming sufficient statistical soundness
of the rand function.
We will associate the directions North, East, South and West to the
numbers 0, 1, 2, and 3, respectively. We will also associate each of the
52 positions in a string with a card in the bridge deck: A, K,
..., 2. In this way, each string represents a bridge
deal.
In essence, we have a dealing program. Of course, the output needs to
be massaged in order to represent the deals in a relevant format, but we
can leave that to other hackers for the time being.
How good is the Hackix program?
-
Statistics (strong). The random number generator provided with Perl
5 is well behaved for short runs like this (52 calls per board), and the
dealing algorithm used does formally shuffle 52 tokens in such a way that
each permutation is equally likely. Tests made on 4000 runs of 40 boards
have shown that Hackix's output is indeed statistically indistinguishable
from random boards.
-
Non-repeating (medium). A sequence of boards generated for one event
must not be observably related to the boards generated for some other event.
Hackix is in reasonable shape here, because the algorithm uses chaining
(the previous board is input to the next board), so if a different run
gets into an old rut in the rand function, the shuffle of the tokens
might be identical to some previous run, but the tokens would be extremely
unlikely to be in the same place. However, if two runs are done within
the same second of wall clock time, the boards will be identical..
-
Clerically robust (none). Hackix does not in any way support clerical
procedures that help prevent inadvertent use of generated deals in an event
that they were not intended for.
-
Unpredictable (weak). If you can guess the time when the run is
made with an accuracy of one second, you have the boards. If you know the
date that the boards were dealt, a brute-force enumeration requires 86400
tries - which is just a matter of minutes of computer time.
-
No discernable pattern (weak). It is not possible for an honest
but knowledgeable player to predict the rest of the deals to be played
during a session, given the deals already played. Hackix is much too complicated
to analyse its behavior without dishonest use of computer assistance.
-
Users (weak). Hackix is suited only for use by a few users who know
and trust each other. It cannot be released to the general public and still
be used in serious tournaments.
-
Auditable (none). It is not at all possible to ascertain after the
event that the deals were not intentionally modified after dealing.
-
All boards possible as output (weak). This is a very popular requirement,
although it is somewhat irrational from a statistical point of view. Anyway,
Hackix does not fulfill this requirement at all. The seed determines the
boards deterministically. The seed is (I think) a 31-bit number in the
Perl rand function, and that limits the number of different sessions
possible. There will be up to 40 boards in each session. D is slightly
less than 96 bits, so only a tiny fraction (2**(-60)) of the D boards are
actually represented in the possible output.
updated 2000-02-06 / jbc