Re: another dice topic
- From: Michael Petch <mpetch@xxxxxxxxxxxxxxxx>
- Date: Wed, 30 May 2007 22:30:39 GMT
Howdy.
On 5/30/07 2:05 PM, in article
1180555533.451576.89960@xxxxxxxxxxxxxxxxxxxxxxxxxxxx, "CooperedKen"
<jcr723@xxxxxxxxx> wrote:
I think fibs is great and am thankful that it exists. I've seen posts
analyzing the dice at fibs. If I recall, all was good. Plus, there
would be no reason to cook the dice there. But the above behavior
seems too common and if I'm not mistaken the dice use the system clock
as a seed for the random number generator (RNG)...so rolls that occur
near in time to each other + some latency in "refreshing" the RNG
might result in what I think I'm seeing
Is there any consensus on this?
Overly paranoid I think. The brain isn't wired to perceive randomness
correctly (Trying to find patterns in chaos). I've played at Fibs and many
other sites and don't have any complaints. I know of one site where the dice
could be hacked, but that was solved (This was a free game site so it didn't
much matter).
As a developer myself, and one who has some development experience in RNG's
(both for business and recreational uses) - How you use develop an RNG/PRNG
can affect how random something may appear. But to see the non randomness
can be very difficult.
In your example you talk about RNG's. Seeds, and timing (Whih means likely a
Pseudo RNG). In this particular example you can code this badly and end up
with one result and code it well and end up with another. We are
specifically dealing with PRNG's (Pseudo RNG) since they are generally the
only ones that need a seed. A seed it a starting point from which all future
numbers are generated.
This is bad (I am just going to use Pseudo-code and doesn't necessarily
represent good program design ):
do forever
SetRNGSeed (get system clock time in milliseconds)
value1 = getNextValuefromRNG();
roll1 = ConvertValuetoNumBetween1and6 (value1)
value2 = getNextValuefromRNG();
roll2 = ConvertValuetoNumBetween1and6 (value2)
end do
The reason this is bad is that you set the seed before you get each roll. I
have seen this type of misuse of seeding quite a lot - some developers don't
know what's going on with Pseudo RNG's and use them improperly. The problem
here is that seeding becomes time dependent on every roll. One could
theoretically try to time the throwing of rolls to generate a bias toward
certain values. Secondly, by reseeding every time you negate much of the
random distribution that a seeded RNG is suppose to give. Pseudo RNG's use a
mathematical algorithm to compute the next random value based on the
previous state of the RNG. By reseeding every time you throw away that
distribution.
The above code will provide very poor results. A much improved version
would be:
SetRNGSeed (get system clock time in milliseconds)
do forever
value1 = getNextValuefromRNG();
roll1 = ConvertValuetoNumBetween1and6 (value1)
value2 = getNextValuefromRNG();
roll2 = ConvertValuetoNumBetween1and6 (value2)
end do
The seed it set once when the program is started. After that there is no
time dependence in the generation of future rolls. With code like this the
situation describe can't occur because each roll is not dependent on time,
but on a mathematical equation. On a side note generally speaking if you
seed an PRNG with the same start value, you can reproduce the same sequence
of rolls.
So hypothetically if a programmer started the above with this line (note the
fixed value 5000 rather than the system clock),
SetRNGSeed (5000)
and he restarted his server every morning at the same time, and lets say
there is only one table playing on this server and you are the only ones
playing after the server restart - you would find that the sequences of
rolls would be identical every day. That's because the number used to seed
the RNG never changes.
So one can say that the more random the seed value when a server is started
means it is less likely for someone to predict the dice. Most programmers
set the seed based on the system clock (which is always changing but can
sort of be predicted by an external user).
So
SetRNGSeed (get system clock time in milliseconds)
Is better than
SetRNGSeed (5000)
Most keen developers will use a less predictable mechanism than passing the
system time to SetRNGSeed just to avoid potential predictability issues. I
won't go into it but on most modern OS's there is an equivalent to a
"Random" device that returns a number (seed) based on a combination of
potentially pseudo random data such as system time, what is at a certain
memory location, memory usage, process identifiers, mouse acceleration,
keyboard typing speed etc etc). By creating a seed value from a number of
potentially semi-random data you can create an initial seed value that is
not very easily predictable, so we end up with something like:
SetRNGSeed (GetaValueFromUnpredictableDataSource())
So hopefully with this whenever your random number generator starts, it
won't be a predictable value. Predictable seeds means users in some
circumstances would be able to guess future rolls.
So far we've dealt with the seed. Next is the PseudoRNG. Assume that you
have a random enough starting seed, the algorithm itself comes into
question. Many built in pseudo RNG's of many development tools come with
very basic algorithms (this is changing) for their RNG's. Some algorithms
might produce more streaks than another, some might be more repetitive than
another etc.
I can name a few sites without a real hardware RNG driving it - use the
Mersenne Twister algorithm. This particular algorithm requires a reasonably
random seed and generated (Mathematically) a sequence of numbers that have
been shown to pass generally accepted tests of randomness (Same tests used
in the cryptography field where randomness is paramount). These tests
include streaks, repetitiveness, distribution etc.
A human looking at the numbers from a well constructed server using Mersenne
Twister could not tell if the source was computer generated or not (Over the
course of a game of backgammon). If a person complains about dice from such
server then its likely they also complain about real world dice (which are
probably more likely to be skewed because of slight imperfections of the
dice themselves - perfectly weighted dice are not 100% perfect - they are
close enough thought to be as fair as possible).
There is one other area that I have seen RNG's introduce slight bias and
that's in the line:
roll1 = ConvertValuetoNumBetween1and6 (value1)
Most computers computers deal in data (values) that are multiples of 8 bits.
8 bits = 1 byte, and 1 byte can hold the values 0-255. 2 bytes hold
256*256=65536 (0-65535) and so on.
The problem is that a programmer has to generate a roll between 1 and 6
inclusive. A computer will generally return a value bigger than 1 and 6. To
get around this the values generate by the RNG are massaged to be in the
range needed (1 to 6). The most prevalent (and most simple mechanism - but
not the only one by any means) is using Modulo arithmetic. Most people who
are not computer literate will understand this concept if they learned long
division.
In long division you know the modulo by the term "remainder". You divide one
number into another and you get a whole number and a remainder.
Lets say the PRNG returns values between 0 and 255. In Backgammon we want
rolls between 1 and 6 (incl). So most programmers take the value from the
RNG and divide it by 6 and use the remainder. If you divide any number by 6,
the remainder will always be a number between 0 and 5. If you add 1 to the
remainder you end up getting numbers between 1 and 6! Great for dice.
The problem here is that many developers don't take into account that 6
doesn't divide evenly into the value 256 (number of values represented by 1
byte). 256 divided by 6 is 42 with remainder 4. This means that 4 values
will appear slightly more often than the others - just because 4 values will
have a slight bias (more likely to appear). In the industry this bias is
called "Modulo Bias", and is probably one thing that is overlooked by most
people. One way I see people try to minimize this is to take use 4 bytes of
data (Which store the numbers 0 to 4,294,967,295) rather than 1 byte like
above. 6 doesn't divide into that number evenly either. The bias still
exists but because the maximum value is so much larger the error becomes
proportionately smaller.
Ideally you want to eliminate this bias. There are a number of ways to do
this, and are beyond the scope of this post. If a server takes a 1 byte
value and generates a number between 1 and 6 using simple modulo arithmetic
- I would let them know they should reprogram this part to eliminate the
bias. What good is a nice Pseudo RNG (Like Mersenne Twister) when the final
computation to convert a number between 1 and 6 adds bias and makes some
numbers show up more than others.
One other factor in all this is that on top of the randomness of the Pseudo
RNG, a well crafted server will generate dice rolls for all the games being
played. If there are 100 games being played, you don't know which table is
going to get which roll from the Pseudo RNG because you can't predict when
those requests will come in. This in itself is a semi random event which
only furthers the potential randomness of the algorithms themselves.
If I have a server that hosts hundreds (thousand etc) of matches I would
create a centralized process or thread that initializes the RNG seed as
talked about - only when the server/process is started and simply allows
multiple sources (in our case BG tables) to request values from this process
via some predefines mechanism (Pipes, files, sockets etc).
What you don't want to do is initialize an RNG with a new seed before every
game. That should be done once when the server is started, and all requests
for a random value are brokered through an RNG server/process. This also has
the advantage of abstracting the actual RNG from the game itself (Each BG
game simply asks the RNG server (Give me a value between 1 and 6) with no
knowledge of how this was generated.
This centralized type of architecture also works well for true hardware
RNG's. These are devices that hook up to your computer (Through an external
port or a card in your PC - or even built into some mother boards) and
generate random data based on real world random events. Nuclear decay,
circuit noise, atmospheric noise, thermal noise to name a few. There are
many products on the market and I know that I have used them for some of my
projects, and do know that TrueMoneyGames uses them as well.
Rather than an algorithm to generate a random number you poll one of these
hardware devices for a value which is based on some random event in nature
and not a mathematical formula.
But again, over the course of games of backgammon a human could not perceive
the difference between a well constructed Pseudo RNG that is implemented
properly, and one of these hardware devices. Incorrect use of these devices
can render skewed results (Modulo Bias would be a potential concern with a
hardware device).
For backgammon, all you need is a well constructed Pseudo RNG without bias,
and programmed correctly to generate numbers that are basically as random as
any real world event. I would also suggest that such RNG's will provide
(imho) more accurate rolls than real world dice (Even the perfectly weighted
ones), nor would I concern myself with my opponent not properly shaking his
rolls or releasing them properly. A well crafted RNG doesn't care who is
playing.
Which leads to the question. Do some servers "fix" the dice for some users?
That's another story, but I highly doubt it. I've never seen it, but
anything is possible. If I can't see the internals of someone's server
software - anything could be done. And that's a risk with any online site
(for any game) - do you trust that the operators don't rig it.
I don't gamble for money online, and when I do (for fun) I have the
expectation I can lose it all. If I lose it I accepted the risks. Do I feel
that I have ever been cheated by any online site by any opponent getting
unusually good rolls, or have I ever seen anything that wouldn't be
accepted as potentially random - the answer to both is "NO". I believe the
dice on modern BG servers is more than sufficiently random for the game of
backgammon, and I don't have any complaint with randomness on Fibs, TMG, GE,
Play65, WGC etc etc.
Mike
.
- Follow-Ups:
- Re: another dice topic
- From: eskimo
- Re: another dice topic
- References:
- another dice topic
- From: CooperedKen
- another dice topic
- Prev by Date: Re: another dice topic
- Next by Date: Re: another dice topic
- Previous by thread: Re: another dice topic
- Next by thread: Re: another dice topic
- Index(es):
Relevant Pages
|
