I thought it would be better to start on a clean
slate to continue discussing the three main
topics from the thread "rigged backgammon",
within the context of deducing seeds and/or
predicting future dice numbers from RNG's, in
a more organized, structured manner.
Hopefully nobody will try to patronize me with
their math PHD's, which seemingly aren't very
useful without the ability for analytical thinking,
so that I won't be driven to retaliate.
Subtopic 1: How many rolls of any combination
are needed to deduce a 32-bit RNG seed?
======================================
We'll discuss this subtopic "assuming that it can
be done".
Let's start with comments from Tim in this post:
https://groups.google.com/g/rec.games.backgammon/c/Dh33pOhN-dE/m/6EoHCzQcBgAJ
After he said: "..... many of the commonly used
RNGs (e.g., Mersenne Twister) would no longer
be suitable, because the seed could be deduced
after some number of rolls",
I asked: "Has this been ever tried to find out
approximately in how few rolls could it be done?
If not, do you or anyone here has an educated
guess?",
And he replied:
This is easy to estimate.
Let's say the seed is 32 bits. That means that
there are 2^32 possible seeds.
There are 21 possible rolls. They're not all
equally likely, but we're just trying to estimate,
so let's ignore that nuance. Now
21^7 < 2^32 < 21^8
So you should be able to infer a 32-bit seed
after 8 rolls.
His estimate is plumb wrong because of the false
premise that "there are 21 possible rolls" which has
been going around for decades in gamblegammon
circles, perpetuated in books, articles, videos, etc.
by the prominent gamblers, and has been parroted
by the rest of their followers.
If you serach the Internet for "21 possible dice rolls",
you will find hundreds of matches, like this article by
Kit Woolsey, for example:
https://www.bkgm.com/articles/GOL/Jan00/roll.htm
In the third line of article, he says: "Since there are 21
possible dice rolls at every turn"..., which can actually
be true in only one specific situation where the same
undiscernible (i.e. same size, color, etc.), manual dice
are rolled by both players, such as the tiny white dice
used while playing classical BG in the Middle East.
What is meant by this may be better worded as "there
are 21 possible uniquely playable dice combinations"
because in all other situations, especially where dice
rolls are produced by RNG's, it is plainly false. (Ironicly
the title of his article is "Computers and Rollouts").
Anytime dice of different colors are used or numbers
are produced one at a time by an RNG, there are not 21
but 36 possible rolls, (and with no "nuance" needed).
This matters for two reasons.
a) For statistical purposes. I had advocated in the past
that the order of dice numbers should be preserved in
game records by bots and in manual transcripts. If you
label the red die as #1 and the blue die as #2, after just
700 or so rolls in a 25-point match, you may already see
that the red die may be rolling too many 5's, for example.
With RNG's, if you roll 36 million times, you would expect
and may indeed get 2 million 61's and 16's counted as a
single roll and thus satisfy the distribution requirements.
But if you differentiate between the two, you may get 1.5
million 61's and only 0.5 million 16's, and thus discover
that your RNG is buggy.
b) For purposes of deducing an RNG seed from rolls. In
this case, the order of dice numbers is even more critical
because while a 61 and 16 together are 2 in 36, counted
individually each is 1 in 36.
To continue, I'll skip all the comments about producing a
working code, etc. What mattered is that Tim wasn't able
to demonstrate, through whatever means he would use,
that he could infer a 32-bit seed after 8 rolls. Then maybe
as a "nuance", he injected "luck" into his "math" by saying
"Unless you're very unlucky, only one of the 32-bit seeds
will give you a match", in this post:
https://groups.google.com/g/rec.games.backgammon/c/Dh33pOhN-dE/m/vMJR5EUNAAAJ
When I pressed by asking "And how many 32-bit seeds
will give me a match, if I'm indeed very unlucky?",
He offered this guess-planation:
I'd say at most two, and I doubt that even this would
ever happen. But without analyzing the specific
details of how the program converts RNG output into
dice rolls, I can't be sure that it would be impossible
to get more than one match after 8 rolls. In any case,
if you run into such a rare situation, a 9th roll will
disambiguate between them.
After clarifying again that the bots generate dice rolls
by taking modulo 6 of RNG produced numbers, I kept
pressing by asking "Is "9" your final answer..??", which
he hasn't answered. I'm not sure if because he realized
that his 21^8 calculation was monstrously wrong or for
some other reason. Either way, this is where we are on
this subtopic at this point.
2- About guessing the seed after seven 21's in a row. ===========================================
After Tony said that he rolled 7 consecutive 2-1 in the
"endgame to lose spectacularly from a very winning
position" (to his opponent I'll call "Joe"), and asked if
the LCG seed used could be deduced from this.
Tim's starting to answer by saying "7 consecutive rolls
is *probably* not going to be enough to prove anything"
wasn't so bad but his saying that "The probability of 7
consecutive 2-1 rolls is about 1 in 600 million", (and all
else he said based on that), was so blatantly wrong.
Again, since we are talking about numbers produced by
RNG's, the order of the numbers does matter. While a 21
and 12 together are 2 in 36, individually each is 1 in 36.
If Tony lost by dropping a cube, Joe must have rolled 6
times; or 7 times if Joe won on his last roll. Thus there
had to be 13 or 14 rolls by both players.
Tim said "if there's some flexibility about when exactly
the sequence starts (one or two rolls earlier or later,
perhaps), then more seeds will fit the bill" not sounding
sure and indeed he wrong because there can't be more
seeds in both cases.
Based on an average game lasting 54 rolls, a 14 or 13
roll sequence can't start later than 40th or 41th roll. But
individual games can be shorter or longer than average
by varying amounts. Thus, if a game is shorter and the
sequence starts earlier, then there will be more seeds
but if a game is longer and the sequence starts later,
then there will be fewer seeds ("that fit the bill").
Tim was also wrong in saying, (about Joe's rolls), "This
is completely irrelevant. Since we don't care what the
opponent's rolls are, the calculation is exactly the same.
It's still an event with probability approximately 1 in 600
million, so the number of seeds is going to be the same."
Tony said he lost "from a very winning position", rolling
many small numbers eroding his lead. That means Joe
had to roll bigger numbers on the average. In the most
extreme case, if Joe also rolled 7 consecutive 21's, Tony
wouldn't lose his lead at all. Thus, when compounding the
odds, not only it matters that Tony *must* roll all 21's but
it also matters that Joe *must not* roll all 21's, (or other
small rolls). The odds of this particular event happening
is much smaller than approximately 1 in 600 million.
3 - Does it matter how dice rolls produced from 32bit
RNG numbers?
===========================================
Recovering a Mersenne Twister seed is possible only
if you know all 624 integers it generates.
If a bot uses an irreversible function like modulo 6 to
produce dice numbers from those 624 integers, then
you lose the capability of knowing all 624 integers and
thus it becomes impossible to recover the seed.
Curiously, instead of using the mod() function, Noo-BG
divides them by 715,827,882 (which is the same thing).
I purposefully mentioned the modulo 6 several times in
order to give him the hint that it makes it impossible to
recover the seed, not after 8 or 9 rolls, but not after any
amount of rolls.
But I didn't want to cut the discussion short because of
this, since Tim could possibly offer a lossless, reversible
way to produce dice numbers from those 624 integers.
And when he said "if you were able to use the full 19937
bits available for the Mersenne Twister, then this same
calculation would say that you would need over 4500
rolls to determine the seed", I thought he may be referring
to such a process. Because if an irreversible function is
used, not 4,500 but not any amount of rolls will be enough.
In replying to Tony and then to me on the same question,
he was right to say that 7 consecutive rolls are so few
that it would be impossible to infer the seed regardless of
which of the "several different ways apps turn the output
of the RNG into dice rolls". So, maybe he can tell us which
specific ones of those various ways can make recovering
the seed after however many number of rolls..?
=============================================
Having said all this, I don't exepect that Tim will admit to
ever being wrong about anything, as his egotism seems
to be bordering narcissism.
One of the last things he said in the original thread was,
(to Bradley):
I engage with Murat only when I find his rantings to be
entertaining, and/or if I think that my explanations
might be instructive to other r.g.b. readers. When I get
bored with him, I stop.
It looks like he was already paving the path for himself
to bail out with any lame excuse, as he has done many
times before. Let's give him the benefit of the doubt and
see...
MK
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)