Hello,

after my (mostly unsuccessful) tries with the "Murat Mutant" cubing
strategy (an outcome which, of course, I expected) some questions were
raised. I will try a thought experiment for explanation.

Let's start without Jacoby, Beavers, Gammons, and Backgammons. In a
situation with the cube alive, the take point is 20 %, something every
beginner gets taught. Many beginners do not understand that they should
"double in", rather than wait until they can double the opponent out.

1. Imagine two bots with "Expert" checker play, but a simplistic cube
strategy as follows: Double above GWC of 0.80, take above GWC of
0.20. Pitted against each other, no double will be taken and all
games result in 1 point.

2. As 1., but now double above GWC of 0.79. A few "double, take"
decisions will be the result.

3. As 2., but now double above GWC of 0.5. Lots of "double, take" and
"redouble, take" cube decisions will be the outcome.

4. As 3., but now with Beavers and Raccoons allowed. The cube will now
be raised to the sky. One could say that it is no doubling cube any
more, but rather a "times 8" cube, since most doubles will result in
immediate Beavers and Raccoons.

5. As 4., but now one side does "reasonable" doubling according to the
best bots' assessment. This is essentially the setup for my "Murat
Mutant" experiments. It boils down to a "times 8" cube for the mutant
(since it will double prematurely, gets beavered and will raccoon)
while the reasonable bot still has the standard "times 2" cube.

My Null hypothesis was that this strategy has an expected net score of
zero against GNU Backgammon. However, while after 1000 games the
results were close to allowing me to reject this hypothesis,
continuing the session did not result in the mutant leaving the 2
sigma confidence interval. In fact, it looked ever more unlikely that
it would, because due to the extremely high variance the confidence
interval was blown up beyond all recognition, see the results below:

Histogram after 3000 games

| Frequency | Points |
|-----------+--------|
| 152 | 1 |
| 453 | 2 |
| 283 | 4 |
| 10 | 6 |
| 1105 | 8 |
| 4 | 12 |
| 632 | 16 |
| 17 | 24 |
| 199 | 32 |
| 3 | 48 |
| 36 | 64 |
| 3 | 96 |
| 63 | 128 |
| 24 | 256 |
| 1 | 384 |
| 6 | 512 |
| 5 | 1024 |
| 1 | 2048 |
| 3 | 4096 |

Average: 2.18933
Variance: 21576.6
Maximum allowed lead: 16091
Actual lead: 6568

So the Jury was still out.

Now, since the cube got very high indeed (around 100 of the 3000 games
resulted in more than 128 points, and I even got more than 1000 points
each in 9 games), this reminded me on the famous "eternal redouble"
position, see:

https://bkgm.com/rgb/rgb.cgi?view+366

After reading "Under-doubling dice",

https://bkgm.com/rgb/rgb.cgi?view+429

as well, I thought that maybe scenarios 4, 5 (and even 3) jack up the
cube so quickly that we suffer from the problem of not having equities
any more and get to a Peterburg Paradoxon.

I think that these scenarios could be analyzed using Markov chains,
with states setup similar to what Gary Wong described in

https://bkgm.com/rgb/rgb.cgi?view+674

Unfortunately I am not familiar enough with Markov chains (I tried to
kind of "merge" the information from "Under-doubling dice" and Gary's
post, but could wrap my head around the asymmetric doubling strategies
and I am neither sure what states/transitions would be needed in
total.

The question I would really like to answer is: How can a money session
be protected against "abuse" by maniac gambling/doubling strategies to
prevent a Peterburg Paradoxon from occurring? Is it sufficient to just
eliminate Beavers? Or does the cube need to be capped (say at 64,
which would be the most natural solution)?

If anyone could assist with the states for the Markov chain and the
asymmetry of the doubling behavior, I would be very happy to
provide/generate more data from my "mutant" experiments.

As usual, any thoughts most welcome!

Axel

On 11/4/2021 2:59 PM, Axel Reichert wrote:
> My Null hypothesis was that this strategy has an expected net score of
> zero against GNU Backgammon. However, while after 1000 games the
> results were close to allowing me to reject this hypothesis,
> continuing the session did not result in the mutant leaving the 2
> sigma confidence interval.

I'm not sure exactly what you're doing, but it doesn't sound
statistically correct to me. Simply formulating a null hypothesis
that the strategy has an expected net score of zero doesn't allow
you to calculate the probability of observing what you observe
since you haven't specified anything about the probability
distribution.

The kind of thing you need here is a nonparametric test. For
example, the Mann-Whitney U test tests the null hypothesis that,
for randomly selected values X and Y from two populations, the
probability of X being greater than Y is equal to the probability
of Y being greater than X. No assumption is needed about the
shape of the probability distributions of X and Y, and you don't
calculate sample variances or anything like that.

Unfortunately, I don't think you want the Mann-Whitney test here,
because one can certainly imagine a skewed distribution that has
zero mean but not zero median.

As I said in my previous message, I don't think that you should be
thinking in terms of hypothesis testing here. What you're engaged
in here is nonparametric estimation: there's an unknown probability
distribution and you're trying to figure out something about it by
sampling from it. It's perfectly reasonable to calculate the sample
variance to get some sense of what's going on, but you should not be
using terminology such as "95% confidence interval" because that does
not make sense here.

> Histogram after 3000 games
>
> | Frequency | Points |
> |-----------+--------|
> | 152 | 1 |
> | 453 | 2 |
> | 283 | 4 |
> | 10 | 6 |
> | 1105 | 8 |
> | 4 | 12 |
> | 632 | 16 |
> | 17 | 24 |
> | 199 | 32 |
> | 3 | 48 |
> | 36 | 64 |
> | 3 | 96 |
> | 63 | 128 |
> | 24 | 256 |
> | 1 | 384 |
> | 6 | 512 |
> | 5 | 1024 |
> | 1 | 2048 |
> | 3 | 4096 |
>
> Average: 2.18933
> Variance: 21576.6
> Maximum allowed lead: 16091
> Actual lead: 6568
>
> So the Jury was still out.
>
> Now, since the cube got very high indeed (around 100 of the 3000 games
> resulted in more than 128 points, and I even got more than 1000 points
> each in 9 games), this reminded me on the famous "eternal redouble"
> position, see:
>
> https://bkgm.com/rgb/rgb.cgi?view+366

Yes. You're now thinking along similar lines to what I was thinking in
the "Expectation maximization versus Kelly criterion" thread. If one
wants to try to argue that "maximizing equity" a la GNU isn't the "best"
thing to do, then it is natural to consider situations where the cube
value increases without limit.

Your histogram is very interesting. I agree with you that the behavior
with the high cube values indicates that your histogram hasn't yet
"converged." If you have the patience, I would encourage you to keep
collecting more statistics to see if you can get the frequencies of
the high cube values to "settle down." That's where all the interesting
things are happening. Also I think that what you're doing here is new,
and could eventually lead to a publication in a backgammon magazine that
might attract considerable attention if your data are compelling enough.

> After reading "Under-doubling dice",
>
> https://bkgm.com/rgb/rgb.cgi?view+429
>
> as well, I thought that maybe scenarios 4, 5 (and even 3) jack up the
> cube so quickly that we suffer from the problem of not having equities
> any more and get to a Peterburg Paradoxon.
>
> I think that these scenarios could be analyzed using Markov chains,

I'd suggest forgetting about the mathematics of Markov chains, at least
at first, and focus on trying to making precise the phenomena that you
think you're observing. Start by writing down a verbal narrative that
describes how the cube gets higher and higher, and try to make that
narrative as precise as you can. So instead of just saying "lots of
double/take and redouble/take cube decisions," try to quantify it. How
often do you think GNU will offer a redouble in the course of a game?
How often does the mutant offer a redouble? Try to write down
some specific probabilities that lead to non-negligible probabilities
that the cube gets up to 2^n. If you develop a plausible story then
you can worry later about formalizing it with Markov chains.

> The question I would really like to answer is: How can a money session
> be protected against "abuse" by maniac gambling/doubling strategies to
> prevent a Peterburg Paradoxon from occurring? Is it sufficient to just
> eliminate Beavers? Or does the cube need to be capped (say at 64,
> which would be the most natural solution)?

I don't know why one would want to protect against such "abuse." The
only reason I can see is if you think someone is jacking up the cube but
isn't willing to cough up the money if he or she loses. But if you have
someone like that in your chouette then you have a problem that simple
rule changes aren't going to fix.

---
Tim Chow

Timothy Chow <tchow12000@yahoo.com> writes:

> you haven't specified anything about the probability distribution

[...]

> there's an unknown probability distribution and you're trying to
> figure out something about it by sampling

O. K., thanks for explaining, I think I got your point.

> keep collecting more statistics to see if you can get the frequencies
> of the high cube values to "settle down."

I intended to do so, but there is a small problem: GNU Backgammon does
not allow a cube value higher than 4096. And depending on the mutant
strategy this will be reached occasionally (more easily with raccoons,
obviously).

> I'd suggest forgetting about the mathematics of Markov chains, at
> least at first

I had the idea of pursuing this path because it might avoid the capped
cube: Neither the mutant nor GNU Backgammon care about the absolute
value of the cube when redoubling/beavering/raccooning. So if I get a
rough estimate about how likely transitions from "mutant holds the cube
at x" to "gnubg holds the cube at 8x" are, I could work around the 4096
limit.

> How often do you think GNU will offer a redouble in the course of a
> game? How often does the mutant offer a redouble?

Perhaps I could get good quality results by forbidding beavers and later
adjust the histogram by assuming that most doubles of the mutant result
in raccoons.

[Preventing a Peterburg Paradoxon]

> I don't know why one would want to protect against such "abuse."

To avoid both accusations of gambling and attraction of gamblers.

> But if you have someone like that in your chouette then you have a
> problem that simple rule changes aren't going to fix.

That's of course right. (-:

Thanks for your comments!

Axel

On 11/5/2021 1:20 PM, Axel Reichert wrote:
> Timothy Chow <tchow12000@yahoo.com> writes:
>> keep collecting more statistics to see if you can get the frequencies
>> of the high cube values to "settle down."
>
> I intended to do so, but there is a small problem: GNU Backgammon does
> not allow a cube value higher than 4096. And depending on the mutant
> strategy this will be reached occasionally (more easily with raccoons,
> obviously).

Ah, yes, that would be a problem. How hard is it to modify the code
to raise this ceiling?

>> I'd suggest forgetting about the mathematics of Markov chains, at
>> least at first
>
> I had the idea of pursuing this path because it might avoid the capped
> cube: Neither the mutant nor GNU Backgammon care about the absolute
> value of the cube when redoubling/beavering/raccooning. So if I get a
> rough estimate about how likely transitions from "mutant holds the cube
> at x" to "gnubg holds the cube at 8x" are, I could work around the 4096
> limit.

Yes, I understand. But my point is that if you aren't very fluent with
the mathematics of Markov chains, don't let that stop you. The crux of
the matter is spelling out in detail some scenario where the cube gets
very high. Figuring out this part doesn't require technical knowledge
so much as clear thinking. Once you get this far, the Markov chain math
should be relatively straightforward.

I will say, by the way, that my intuition is that even though 4096 seems
high, I doubt that the strategy you outlined will run into St.
Petersburg problems. After all, one side is standard GNU, so it's
probably not going to be jacking up the cube all that much. The
exception, though, might be superbackgames that GNU completely
misunderstands. Have you manually examined the 4096-cube games to
see if the positions are so wild that standard GNU has no idea what
is going on, and is beavering when it's losing?

>> I don't know why one would want to protect against such "abuse."
>
> To avoid both accusations of gambling and attraction of gamblers.

Oh, well, in that case, don't play money games. Just play matches.

---
Tim Chow

On November 5, 2021 at 7:25:40 PM UTC-6, Tim Chow wrote:

> On 11/5/2021 1:20 PM, Axel Reichert wrote:

>> To avoid both accusations of gambling and attraction of gamblers.

> Oh, well, in that case, don't play money games. Just play matches.

Indeed and, in fact, just play "cubeless!" matches at that... :))

I won't dare participate in your discussion yet since I don't understand
it all but I'm trying as best as I can.

On the other hand, I think you're trying to one-up the other uselessly
with increasingly complicated math arguments about a pink elephant.

It reminded of something, if you have 20 seconds to read. In 1980, I
was hired as a junior programmer before even I finished my first
semester taking English-101, Basic, Fortran and "computer math". I
was 6 months into developing an auto parts store software on a
Commodore PET. A guy nicknamed "genius" in that small company
had figured how to wire an IBM Selectric typewriter to a serial port.
It was the best ("LQ = Letter Quality") printing solution at the time.

The same guy had also devised a serial port dongle to copy protect
the software we would sell, also an impressive invention at the time.
They were going to patent it and market jointly with Commodore.

One they, while they were having a joint executive meeting about it,
I asked if they would attach one to a PET to see if I could break it.
They were polite enough to not laugh and only smile but they obliged.
In about 45 minutes I knocked on their door to give them the shocking
news. :)

They had invented and improved on all that overly technical complicated
stuff but were ignorant about a simple little feature of the PET operating
system and basic language. Two nifty functions called "peek" and "poke"
to directly read and write to the memory. After peeking and poking around
for a few minutes, I had located and defeated their encryption function. :)

Anyway, sorry for reminiscing publicly but I feel that this is what is going
on with the cube skill thing. You all are soaring so high that you can't
see the simplest logical argument that defeats all of your elaborate ones.

But please keep at it, though. It's much much more interesting to read
than your stupid position discussions.

MK

Timothy Chow <tchow12000@yahoo.com> writes:

> On 11/5/2021 1:20 PM, Axel Reichert wrote:
>>
>> I intended to do so, but there is a small problem: GNU Backgammon does
>> not allow a cube value higher than 4096. And depending on the mutant
>> strategy this will be reached occasionally (more easily with raccoons,
>> obviously).
>
> Ah, yes, that would be a problem. How hard is it to modify the code
> to raise this ceiling?

I don't write C, but tried to read it. Maybe Philippe Michel can comment
whether a re-compile with

#define MAX_CUBE ( 1 << 15 )

instead of 12 in backgammon.h might work (there are only 4 bits in the
match-id for log2 of the cube value, so going still higher would likely
be too large a surgery). This would give leeway for another raccoon,
perhaps sufficient to get a "converged" histogram.

> But my point is that if you aren't very fluent with the mathematics of
> Markov chains, don't let that stop you. The crux of the matter is
> spelling out in detail some scenario where the cube gets very high.
> Figuring out this part doesn't require technical knowledge so much as
> clear thinking. Once you get this far, the Markov chain math should
> be relatively straightforward.

Well, I have already gathered some states and transitions between
them. It is not as simple as in Gary's post that I linked previously,
though.

> I doubt that the strategy you outlined will run into St. Petersburg
> problems. After all, one side is standard GNU, so it's probably not
> going to be jacking up the cube all that much.

Yes, GNU Backgammon has a "times 2" cube (it will almost never be
beavered when playing against its own take/pass decisions), but if its
opponent essentially wields a "times 8" cube and a symmetric "times 3"
cube already gives rise to a Petersburg Paradoxon, then I am not so
sure.

> Have you manually examined the 4096-cube games to see if the positions
> are so wild that standard GNU has no idea what is going on, and is
> beavering when it's losing?

No, and by now the session files are gone, but thanks for the idea, I
will look out for this in my current tries (the runs continue ...)

> Oh, well, in that case, don't play money games. Just play matches.

Which is possible, but from a logistics point of view less flexible in a
chouette setting.

Best regards

Axel

On 11/6/2021 6:26 AM, Axel Reichert wrote:
> Timothy Chow <tchow12000@yahoo.com> writes:
>> I doubt that the strategy you outlined will run into St. Petersburg
>> problems. After all, one side is standard GNU, so it's probably not
>> going to be jacking up the cube all that much.
>
> Yes, GNU Backgammon has a "times 2" cube (it will almost never be
> beavered when playing against its own take/pass decisions), but if its
> opponent essentially wields a "times 8" cube and a symmetric "times 3"
> cube already gives rise to a Petersburg Paradoxon, then I am not so
> sure.

The size of the cube doesn't have anything to do with it. It's all
about the frequency with which the "paradoxical" positions occur.
And it takes two to tango, so to speak; the cube won't get arbitrarily
high unless standard GNU is redoubling with sufficiently high
probability.
>> Oh, well, in that case, don't play money games. Just play matches.
>
> Which is possible, but from a logistics point of view less flexible in a
> chouette setting.

If you're worried about getting a reputation for gambling then don't
play in a chouette.

---
Tim Chow

On 2021-11-06, Axel Reichert <mail@axel-reichert.de> wrote:

> Timothy Chow <tchow12000@yahoo.com> writes:

>> Ah, yes, that would be a problem. How hard is it to modify the code
>> to raise this ceiling?
>
> I don't write C, but tried to read it. Maybe Philippe Michel can comment
> whether a re-compile with
>
> #define MAX_CUBE ( 1 << 15 )
>
> instead of 12 in backgammon.h might work (there are only 4 bits in the
> match-id for log2 of the cube value, so going still higher would likely
> be too large a surgery). This would give leeway for another raccoon,
> perhaps sufficient to get a "converged" histogram.

The matchid is used only for copying and pasting positions. Internally a
different key is used and it doesn't depend on the cube value for money
play. See the EvalKey() function in eval.c.

Still, it's difficult to be sure the above change is harmless without
thorough checking.

Offhand, what I would try instead is to add something like:

if (ms.nCube > 64)
ms.nCube = ms.nCube / 64;

at the beginning of the ComputerTurn() function in play.c, and find the
final cube value in another way, for instance by counting the doubles in
the game log.

If this works, as a bonus, it would remove any limit to the cube level.

Timothy Chow <tchow12000@yahoo.com> writes:

> On 11/6/2021 6:26 AM, Axel Reichert wrote:
>>
>> Yes, GNU Backgammon has a "times 2" cube (it will almost never be
>> beavered when playing against its own take/pass decisions), but if
>> its opponent essentially wields a "times 8" cube and a symmetric
>> "times 3" cube already gives rise to a Petersburg Paradoxon, then I
>> am not so sure.
>
> The size of the cube doesn't have anything to do with it. It's all
> about the frequency with which the "paradoxical" positions occur.

I am not necessarily talking about positions like "perpetual recube",
but about the usual swings in a "normal" game, with several moves in
between. If these swings occur frequently enough and at least one player
is rather cube-happy, then scenarios like

https://bkgm.com/rgb/rgb.cgi?view+429

seem plausible to me, at least with raccoons.

> the cube won't get arbitrarily high unless standard GNU is redoubling
> with sufficiently high probability.

Which it will do if it ends up in its normal doubling window after a
swing.

> If you're worried about getting a reputation for gambling then don't
> play in a chouette.

(-:

In the meantime, my little Markov chain program was ready and was fed
the probability data from two mutant sessions: I have run 10000 games
(0 beavers, no Jacoby) and then another session (1 beaver, no
Jacoby). From the second run (which luckily never reached GNU
Backgammon's maximum cube value of 4096), I could reasonably adapt the
transition probabilities (and the game values) to account for
raccoons: After getting beavered, the mutant would always racoon, and
I think I can safely assume that gnubg would take the raccoon.

Then I ran the Markov chain program several billion times with an ever
growing number of tries, for the transitions probabilities with 0
beavers, 1 beaver, and 2 beavers (raccoons) and monitored the expected
value per game to see whether it is growing or converging. Here are
the results:

| Number of games | 0 beavers | 1 beaver | 2 beavers |
|-----------------+-----------+----------+-----------|
| 1000 | 5.061 | 17.575 | 34.833 |
| 2000 | 4.688 | 15.190 | 60.086 |
| 5000 | 4.454 | 12.679 | 62.037 |
| 10000 | 4.709 | 18.704 | 54.358 |
| 20000 | 4.800 | 18.619 | 919.218 |
| 50000 | 4.263 | 16.019 | 81.098 |
| 100000 | 4.365 | 17.399 | 74.955 |
| 200000 | 4.337 | 15.342 | 110.093 |
| 500000 | 4.368 | 16.853 | 138.879 |
| 1000000 | 4.361 | 15.497 | 120.395 |
| 2000000 | 4.348 | 17.958 | 311.474 |
| 5000000 | 4.401 | 16.902 | 285.184 |
| 10000000 | 4.340 | 24.388 | 793.178 |
| 20000000 | 4.358 | 17.626 | 176.234 |
| 50000000 | 4.348 | 20.283 | 212.273 |
| 100000000 | 4.357 | 19.130 | 204.241 |
| 200000000 | 4.355 | 20.328 | 206.505 |
| 500000000 | 4.350 | 19.709 | 263.348 |

To me, this looks like convergence without beavers and divergence
(hence Petersburg Paradoxon) with raccoons. For one beaver it seems
unclear whether the outcome is stable or not. Of course it could be
that 500 million games are still to few to "prove" a stable outcome,
but this is certainly much more than I will be able to play in my
lifetime.

Maybe it is possible to come up with the parameters for a (geometric)
distribution in the histogram and proceed analytically from there, but
I have no idea how to fit the parameters from a histogram and so
provide them for others here:

Histogram after 10000 games:

| Points | 0 beavers | 1 beaver |
|--------+-----------+----------|
| 1 | 465 | 464 |
| 2 | 5198 | 1566 |
| 3 | 1 | 0 |
| 4 | 2908 | 4562 |
| 6 | 71 | 29 |
| 8 | 1017 | 2154 |
| 12 | 17 | 38 |
| 16 | 237 | 670 |
| 24 | 3 | 9 |
| 32 | 63 | 332 |
| 48 | 2 | 1 |
| 64 | 14 | 111 |
| 96 | 1 | 4 |
| 128 | 1 | 36 |
| 256 | 1 | 17 |
| 512 | 1 | 4 |
| 1024 | 0 | 2 |
| 2048 | 0 | 1 |

Following your recommendation, I checked the 3 games with a cube of at
least 1024. Nothing special, perfectly reasonable doubles by gnubg in
a garden variety of games, just a couple of swings.

Any hints on how to proceed to "prove" that beavers are stable or
unstable using this simplistic doubling "strategy"? In case someone
needs further information of data: I still have the complete session
files, a mere GB of ASCII text each. Lots of room for analysis using
sed, awk and the like. (-:

Feel free to throw your suggestions at me, I will be happy to follow
up where I can.

Best regards

Axel

Philippe Michel <philippe.michel7@free.fr.invalid> writes:

> Offhand, what I would try instead is to add something like:
>
> if (ms.nCube > 64)
> ms.nCube = ms.nCube / 64;
>
> at the beginning of the ComputerTurn() function in play.c, and find the
> final cube value in another way, for instance by counting the doubles in
> the game log.

Thanks for this very "hackish" idea! I will keep it in my notes. For the
time being I was lucky since in the 10000 games with beaver the 4096
cube limit was not reached, so my data are "clean" in this respect.

> If this works, as a bonus, it would remove any limit to the cube level.

Sure. I might come back to this. Thanks again!

Axel

On 11/9/2021 5:38 PM, Axel Reichert wrote:
> I am not necessarily talking about positions like "perpetual recube",
> but about the usual swings in a "normal" game, with several moves in
> between. If these swings occur frequently enough and at least one player
> is rather cube-happy, then scenarios like
>
> https://bkgm.com/rgb/rgb.cgi?view+429
>
> seem plausible to me, at least with raccoons.

I don't think I've ever seen that analysis before. Very interesting!

It leads me to wonder about the following scenario. Suppose two players
behave as follows. They play D/T every single turn. They move the
checkers the way a bot such as GNU does at DMP. For simplicity let
us say that gammons and backgammons don't count. Does it make sense to
talk about "expected payoff" in such a situation? Of course, by
symmetry, if the expected payoff exists then it must be zero. But it
is not immediately obvious that the expected value exists. If the
probability that a game lasts n rolls drops off slower than 1/2^n then
I think the expected payoff does not exist.

It still seems to me that if only one side is doubling this aggressively
then we're not going to get undefined expected values, but I see now
what you're suggesting.

By the way, I have some sad news to share about the author of that
old article. Bill Taylor died of a heart attack on July 27, 2021.

https://www.lambandhayward.co.nz/obituaries/william-bill-frank-chatterton-taylor/4013/

> In the meantime, my little Markov chain program was ready and was fed
> the probability data from two mutant sessions: I have run 10000 games
> (0 beavers, no Jacoby) and then another session (1 beaver, no
> Jacoby).

If it's not too complicated, can you post a description of your Markov
chain?

---
Tim Chow

Timothy Chow <tchow12000@yahoo.com> writes:

> Suppose two players behave as follows. They play D/T every single
> turn. They move the checkers the way a bot such as GNU does at DMP.
> For simplicity let us say that gammons and backgammons don't count.
> Does it make sense to talk about "expected payoff" in such a
> situation? Of course, by symmetry, if the expected payoff exists
> then it must be zero. But it is not immediately obvious that the
> expected value exists. If the probability that a game lasts n rolls
> drops off slower than 1/2^n then I think the expected payoff does
> not exist.

Fully agree. And I am very sure that this ends up in Peterburg.

> It still seems to me that if only one side is doubling this
> aggressively then we're not going to get undefined expected values,
> but I see now what you're suggesting.

In the meantime I could add three lines to my previous table:

| Number of games | 0 beavers | 1 beaver | 2 beavers |
|-----------------+-----------+----------+-----------|
| 1000 | 5.061 | 17.575 | 34.833 |
| 2000 | 4.688 | 15.190 | 60.086 |
| 5000 | 4.454 | 12.679 | 62.037 |
| 10000 | 4.709 | 18.704 | 54.358 |
| 20000 | 4.800 | 18.619 | 919.218 |
| 50000 | 4.263 | 16.019 | 81.098 |
| 100000 | 4.365 | 17.399 | 74.955 |
| 200000 | 4.337 | 15.342 | 110.093 |
| 500000 | 4.368 | 16.853 | 138.879 |
| 1000000 | 4.361 | 15.497 | 120.395 |
| 2000000 | 4.348 | 17.958 | 311.474 |
| 5000000 | 4.401 | 16.902 | 285.184 |
| 10000000 | 4.340 | 24.388 | 793.178 |
| 20000000 | 4.358 | 17.626 | 176.234 |
| 50000000 | 4.348 | 20.283 | 212.273 |
| 100000000 | 4.357 | 19.130 | 204.241 |
| 200000000 | 4.355 | 20.328 | 206.505 |
| 500000000 | 4.350 | 19.709 | 263.348 |
|-----------------+-----------+----------+-----------|
| 1000000000 | 4.353 | 18.755 | 639.952 |
| 2000000000 | 4.352 | 19.226 | 650.204 |
| 5000000000 | 4.354 | 18.862 | 356.384 |

Without beavers, the expectation has settled, and by now I think that
1 beaver does not cause a Petersburg paradoxon either. But for 2
beavers my results are still far away from stability or there is no
expectation any more. My gut feeling says the latter.

> can you post a description of your Markov chain?

Sure. The states and transition probabilities (for 1 beaver) are as
follows:

1. Single win (Terminal, winner gets 1 * cube value)

2. Gammon win (Terminal, winner gets 2 * cube value)

3. Backgammon win (Terminal, winner gets 3 * cube value)

4. Cube centered
- gnubg doubles, mutant takes (0.1104): Go to 5
- gnubg doubles, mutant beavers, gnubg takes (0.0000): Go to 5
- gnubg wins a single game, including drops (0.0418): Go to 1
- gnubg wins a gammon (0.0023): Go to 2
- gnubg wins a backgammon (0.0000): Go to 3
- mutant doubles, gnubg takes (0.1933): Go to 6
- mutant doubles, gnubg beavers, mutant takes (0.6476): Go to 6
- mutant wins a single game, including drops (0.0046): Go to 1
- mutant wins a gammon (0.0000): Go to 2
- mutant wins a backgammon (0.0000): Go to 3

5. Cube owned by mutant
- gnubg doubles, mutant takes (0.0000): Go to 5
- gnubg doubles, mutant beavers, gnubg takes (0.0000): Go to 5
- gnubg wins a single game, including drops (0.3807): Go to 1
- gnubg wins a gammon (0.1330): Go to 2
- gnubg wins a backgammon (0.0060): Go to 3
- mutant doubles, gnubg takes (0.1922): Go to 6
- mutant doubles, gnubg beavers, mutant takes (0.1867): Go to 6
- mutant wins a single game, including drops (0.1014): Go to 1
- mutant wins a gammon (0.0000): Go to 2
- mutant wins a backgammon (0.0000): Go to 3

6. Cube owned by GNU Backgammon
- gnubg doubles, mutant takes (0.3502): Go to 5
- gnubg doubles, mutant beavers, gnubg takes (0.0001): Go to 5
- gnubg wins a single game, including drops (0.2672): Go to 1
- gnubg wins a gammon (0.0205): Go to 2
- gnubg wins a backgammon (0.0012): Go to 3
- mutant doubles, gnubg takes (0.0000): Go to 6
- mutant doubles, gnubg beavers, mutant takes (0.0000): Go to 6
- mutant wins a single game, including drops (0.2554): Go to 1
- mutant wins a gammon (0.1014): Go to 2
- mutant wins a backgammon (0.0041): Go to 3

The many (redundant) 0 transition probabilities made it more general and
the coding simpler. Can you cope with Lisp?

Of course you need to do some book-keeping for the cube value for
states 5 and 6. In case of two beavers (= raccoons) allowed, I have
assumed that the mutant always raccoons after getting beavered and
gnubg always takes, so the transition probabilities do not change,
just the cube value for book-keeping. So with 1 beaver it is
multiplied by 4, with 2 beavers it is multiplied by 8. Without
beavers, the transition probabilities are of course different. Since I
consider this case to be settled, I have not listed them here, let me
know if you want/need them.

The transition probabilities come from my "real" games between the
mutant and gnubg, 10000 without beavers, 10000 with 1 beaver, all
below the cube limit of 4096. The mutant doubled with cubeless GWC >
0.5 and took all beavers. Other take decisions (2-ply) and checker
play (0-ply) like gnubg.

Please let me know if you need something else. I would be most
interested in your thoughts about the histograms (coming out of my real
games as well as out of the Markov chains), any fit of them to a
(geometric) distribution and then perhaps analytic results along the
lines of Bill Taylor.

Best regards

Axel

On November 11, 2021 at 12:53:01 PM UTC-7, Axel Reichert wrote:

> ... Since I consider this case to be settled, I have not listed
> them here, let me know if you want/need them.

Can you translate all that to English?

> The transition probabilities come from my "real" games
> between the mutant and gnubg, 10000 without beavers,
> 10000 with 1 beaver, all below the cube limit of 4096.

Why is the need for substituting fantasy for fact? Lack of
needed CPU time? Or the writing on the wall?

> The mutant doubled with cubeless GWC 0.5 and took all
> beavers. Other take decisions (2-ply) and checker play
> (0-ply) like gnubg.

The mutant should take also at a lower GWC or else it
defeats the purpose of marginalizing the cube skill (in
this context, more specifically the value of the cube
ownership).

> Please let me know if you need something else.

Even though you're not asking me, how can I download
the text file of those 20,000 "real" games?

MK

On 11/11/2021 2:52 PM, Axel Reichert wrote:
> Timothy Chow <tchow12000@yahoo.com> writes:
>
>> Suppose two players behave as follows. They play D/T every single
>> turn. They move the checkers the way a bot such as GNU does at DMP.
>> For simplicity let us say that gammons and backgammons don't count.
>> Does it make sense to talk about "expected payoff" in such a
>> situation? Of course, by symmetry, if the expected payoff exists
>> then it must be zero. But it is not immediately obvious that the
>> expected value exists. If the probability that a game lasts n rolls
>> drops off slower than 1/2^n then I think the expected payoff does
>> not exist.
>
> Fully agree. And I am very sure that this ends up in Peterburg.

Yes, now that I think about it, the probability that a game lasts
n rolls has to be at least some constant times (25/36)^n, because
as soon as you get a position where both players are on the bar
against a five-point board, the probability that they keep dancing
is (25/36)^n.

> Without beavers, the expectation has settled, and by now I think that
> 1 beaver does not cause a Petersburg paradoxon either. But for 2
> beavers my results are still far away from stability or there is no
> expectation any more. My gut feeling says the latter.

Interesting. Your data certainly exhibit more "instability" than
I was expecting, so you might be right.

> > can you post a description of your Markov chain?
>
> Sure. The states and transition probabilities (for 1 beaver) are as
> follows:

Here's something I'm curious about. I don't know if it's easy to
answer this question with your data, but suppose you plot a histogram
that shows how frequently a game lasts n rolls. Does the histogram
coming from real games look close to the histogram you get from the
Markov chain? That would provide a sanity check as to whether the
Markov chain is a plausible model of the real game.

---
Tim Chow

MK <murat@compuplus.net> writes:

> On November 11, 2021 at 12:53:01 PM UTC-7, Axel Reichert wrote:
>
> Why is the need for substituting fantasy for fact? Lack of needed CPU
> time?

This is not fantasy, but a rock-solid mathematical technique. And yes,
CPU time is the reason.

>> The mutant doubled with cubeless GWC 0.5 and took all beavers. Other
>> take decisions (2-ply) and checker play (0-ply) like gnubg.
>
> The mutant should take also at a lower GWC

I know, we have discussed this. The session with "Take if GWC > 0" is
still running.

> how can I download the text file of those 20,000 "real" games?

Sorry, I will not provide 2.5 GB of ASCII text.

Axel

Timothy Chow <tchow12000@yahoo.com> writes:

> plot a histogram that shows how frequently a game lasts n rolls

That would be a simple Unix command line for the "real" games. However
....

> Does the histogram coming from real games look close to the histogram
> you get from the Markov chain?

.... this information is not modelled in the states of the Markov chain,
since all wins are lumped together, no matter how long it took. I could
use a different organization of states, but this would of course require
different transition probabilities, to be extracted from the GNU
Backgammon session files.

> That would provide a sanity check

Any other ideas that I could check? Or would you be able to provide
estimates for how many "games" I should run the Markov chains? Or any
hints on how to fit my session histogram to a (geometric) distribution
in order to further pursue the analytical path?

Best regards

Axel

On 11/15/2021 4:03 PM, Axel Reichert wrote:
> Any other ideas that I could check? Or would you be able to provide
> estimates for how many "games" I should run the Markov chains? Or any
> hints on how to fit my session histogram to a (geometric) distribution
> in order to further pursue the analytical path?

Earlier you said there were some aspects of Markov chain theory that
you weren't familiar with. When I say something like, you should
diagonalize the transition matrix in order to compute stationary
probabilities, do you know what I mean? If not, I can walk you
through it.

What histogram exactly are you trying to fit to a geometric
distribution? In any case, one approach to fitting a geometric
distribution is to take the logarithms of the values, since these
should lie on a straight line, which you can estimate by doing a
least-squares fit.

---
Tim Chow

On November 15, 2021 at 12:36:07 PM UTC-7, Axel Reichert wrote:

> MK <mu...@compuplus.net> writes:
>> Why is the need for substituting fantasy for fact? Lack of needed
>> CPU time?

> This is not fantasy, but a rock-solid mathematical technique. And
> yes, CPU time is the reason.

I guess I don't like it because I don't understand what all those
constants come from and what the results will prove??

>> The mutant should take also at a lower GWC

> I know, we have discussed this. The session with
> "Take if GWC > 0" is still running.

This is too drasctic but let's see what comes out of it anyway.

>> how can I download the text file of those 20,000 "real" games?

> Sorry, I will not provide 2.5 GB of ASCII text.

The size doesn't make sense. Even a long 1-pointer wouldn't be
more than 5K in text format. Two sets of 10,000 games should
be about 100Mb. Your 2.5Gb works out to 125K per game which
doesn't sound real. What am I missing?

MK

MK <murat@compuplus.net> writes:

> Your 2.5Gb works out to 125K per game which doesn't sound real. What
> am I missing?

Run

gnubg -t

from the command line and play one game. Multiplied by 10000, this gives
my session file.

Axel

Timothy Chow <tchow12000@yahoo.com> writes:

> When I say something like, you should diagonalize the transition
> matrix in order to compute stationary probabilities, do you know what
> I mean?

Not quite, since my 6 states do not all have 6 transitions and I believe
that the transition matrix should be a square one. I have no idea, e.g.,
how to cope with the difference in my state 5 (mutant owns cube) and the
two transitions for a simple take versus a take with beaver and how to
ensure that the cube value is carried through the process. So yes, I
would be very happy if you could walk me through, especially since I
guess it is the stationary probabilities that we are after.

By the way, I think I understand what to with the terminals (1 on the
diagonal, 0 elsewhere), but again not how to keep track of the results.

> What histogram exactly are you trying to fit to a geometric
> distribution?

The one with the number of cubings per game, as in Bill Taylor's post:

[snip]
Then the number of cubings is a geometric random variable with

p_1 = (1-p) (p_0 = 0 as it must get to one of the K-points first),
p_2 = (1-p)p
p_3 = (1-p)p^2 etc. So the expected number of cubings is 1/(1-p).

For the standard M = 2; K = 0.8 , p = 1/4, E[#] = 4/3.
[snip]

With values for p and M from my Markov process my vague idea is to be
able to show whether the expectation gets infinite or not.

> In any case, one approach to fitting a geometric distribution is to
> take the logarithms of the values, since these should lie on a
> straight line, which you can estimate by doing a least-squares fit.

(Dumbfounded): Of course, I was losing the forest for the trees in my
thinking process. I should have known this. Thanks for the pointer!

Best regards

Axel

On 11/16/2021 2:24 PM, Axel Reichert wrote:
> Timothy Chow <tchow12000@yahoo.com> writes:
>
>> When I say something like, you should diagonalize the transition
>> matrix in order to compute stationary probabilities, do you know what
>> I mean?
>
> Not quite, since my 6 states do not all have 6 transitions and I believe
> that the transition matrix should be a square one. I have no idea, e.g.,
> how to cope with the difference in my state 5 (mutant owns cube) and the
> two transitions for a simple take versus a take with beaver and how to
> ensure that the cube value is carried through the process. So yes, I
> would be very happy if you could walk me through, especially since I
> guess it is the stationary probabilities that we are after.

There is a straightforward way to handle this if you're willing to
deal with more states. For each of your 6 states, you need to create
a bunch of states, each with a different cube value. (There is a slight
annoyance here in that to keep things finite, you'll have to put a cap
on the cube value.)

Not having all transitions doesn't matter. That just means that the
transition probability is zero. The transition matrix is indeed square.
The value of A_{i,j} is the probability of transitioning from state i
to state j.

Depending on how high you let the cube get, your matrix will have
dozens, or maybe more than a hundred, rows, but this should not be a
big problem if you have some standard software package to do numerical
linear algebra. If you don't have access to such software then I can
probably do the computation for you if you send me the matrix.

---
Tim Chow

Timothy Chow <tchow12000@yahoo.com> writes:

> For each of your 6 states, you need to create a bunch of states, each
> with a different cube value. (There is a slight annoyance here in
> that to keep things finite, you'll have to put a cap on the cube
> value.)

Quite an annoyance! But I could of course use the same transition
probabilities from cube 2 to 4 as from cube 1048576 to 2097152. May
result in some lines of code to populate the transition matrix. But
100x100 should do.

> If you don't have access to such software then I can probably do the
> computation for you if you send me the matrix.

That would be great. Might take some time for me to come back to
you. Many thanks for your offer!

Best regards

Axel

On November 16, 2021 at 12:03:26 PM UTC-7, Axel Reichert wrote:

> MK <mu...@compuplus.net> writes:
>> Your 2.5Gb works out to 125K per game which doesn't
>> sound real. What am I missing?

> Run
> gnubg -t
> from the command line and play one game. Multiplied by
> 10000, this gives my session file.

Oh, I see. I never ran Gnubg from comman line but you had
to in order to automate the process. And it sounds like the
text files you are talking about contain ascii representations
of all positions(??). If that's the case, can you export them
as game/match files made of only the dice rolls and moves
in text?

At least how about the first 1,000 or even 100 of each? I just
would like to see what they look like for myself.

MK

MK <murat@compuplus.net> writes:

> it sounds like the text files you are talking about contain ascii
> representations of all positions

Yes.

> can you export them as game/match files made of only the dice rolls
> and moves in text?

No, not any more, the sessions have been closed.

Axel

On November 18, 2021 at 1:54:20 PM UTC-7, Axel Reichert wrote:

> MK <mu...@compuplus.net> writes:
>> it sounds like the text files you are talking about contain ascii
>> representations of all positions

> Yes.

Thanks for doing this experiment. I've been asking for years
for this kind of experiments. It wasn't exactly what I proposed
but it was close enough and the first/only one anyone has
ever done. Maybe we can come up with more ideas and run
short sessions not to prove something but just to get a peek
at "possibilities" to further explore. Maybe even other people
will get excited/interested to do similar experiments also.

>> can you export them as game/match files made of only the
>> dice rolls and moves in text?

> No, not any more, the sessions have been closed.

I hope you don't delete the files which are all we have of their
kind. They may be opened in gnubg and re-exported or they
may be converted using a simple program/macro. Someone
from the gnubg team may be able to help.

MK