Retrograde Backgammon?
Douglas Zare
Money game cube action?
+24-23-22-21-20-19-------18-17-16-15-14-13-+
| X X O O O O | | O O X |
| X O O O | | X |
| | | |
| | X | |
| | | |
| |BAR| |
| | | |
| | O | |
| | | |
| O X X X | | O |
| O O X X X X | | X X O |
+-1--2--3--4--5--6--------7--8--9-10-11-12-+
Pipcount X: 169 O: 169
CubeValue: Any
Once one thinks about how the entering numbers play, I think it becomes
clear that this is both double/take with the cube centered and
redouble/take if the side on roll has the cube. (I don't think it would
be a take without the substantial value of holding the cube.) Since one
fails to enter 1/4 of the time, the variance of this position (related
to the expected square of the final payoff) is infinite, since the
contribution to the expected square of the payoff from entering after
one throw is positive and equals the contribution from the possibility
of entering after the nth throw, for any n.
If this position can be reached by _optimal_ play, then the variance of
backgammon is infinite. This should not be a surprise, since that is
what happens in the continuous limit (doubling in at 80%). It has been
claimed that there are positions where the equity doesn't exist. It is
actually pretty easy to construct positions like the one above
(redouble/take with both sides on the bar against a 3-point board), but
this one seems more promising than most to arise from actual play.
So, can you construct a sequence of die rolls and plays that you are
confident are optimal (or at least that JF or Snowie would play) which
leads to this position? Less satisfying but still of interest would be a
game ending in this such that one side has played optimally, and the
other side might have erred. If this position can't be reached by
optimal play, or even by plausible play by strong players, then it is
not nearly as interesting an example.
What would it mean if variance doesn't exist? In long money sessions,
the results would not approach a classic bell-curve. One can try to
apply variance reduction techniques when the variance is infinite; I'll
say more about this later.
Douglas Zare
Gary Wong
> I'm interested in the following position:
>
> Money game cube action?
> +24-23-22-21-20-19-------18-17-16-15-14-13-+
> | X X O O O O | | O O X |
> | X O O O | | X |
> | | X | |
> | | | |
> | |BAR| |
> | | | |
> | | O | |
> | O X X X | | O |
> | O O X X X X | | X X O |
> +-1--2--3--4--5--6--------7--8--9-10-11-12-+
>
> If this position can be reached by _optimal_ play, then the variance of
> backgammon is infinite. This should not be a surprise, since that is
> what happens in the continuous limit (doubling in at 80%). It has been
> claimed that there are positions where the equity doesn't exist. It is
> actually pretty easy to construct positions like the one above
> (redouble/take with both sides on the bar against a 3-point board), but
> this one seems more promising than most to arise from actual play.
This is very interesting. Unfortunately Deja News won't let us at the
discussions on r.g.b. (from late '97) about undefined equity
positions, but essentially I believe (given only some assumptions
about the results of the games once either player enters) that you can
prove that the correct cube action for both the positions discussed
then and your position above is redouble/take. Such arguments do not
rely on the equity or volatility; rather, I can prove that any
behaviour other than redouble/take is suboptimal, or equivalently,
that it is better to double n+1 times and then stop doubling than it
is to double n times and stop, for all n. From there I conclude that
either the optimal strategy is redouble/take, or that no optimal
strategy is defined; it comes down to a matter of definition.
I hadn't previously considered positions where the equity was defined
but the variance was not, but I do believe yours is one (again, given
the assumptions about the equity once either player enters). So it
appears that positions exist where both equity and variance are
defined (non-contact positions are trivial examples of this); and
others also exist where equity is defined but variance is not
(including yours), and also those where neither equity nor variance
exist (e.g. the one Paul Tanenbaum posted in '97).
To generalise a bit, what can we say about the higher order moments
beyond equity and variance? (Equity is, loosely speaking, the first
moment; variance is the second; the third would be related to the
result of the game to the third power, which is, er, the cube cubed.
Some of these moments are raw (measured about zero) and some are
central (measured about the mean), but we can gloss over that for
now.) Obviously in all non-contact positions, all moments must be
defined, because the finite pip count must decrease with every move
made and that places an upper bound on the cube value. But given
sufficient contact, we could find a positive probability that the cube
will reach any given level, and so interesting things could happen at
higher moments.
I once proposed a model for the probability distribution function of
the cube value/game result based on some empirical data; the article
(tentatively) survives at:
http://www.dejanews.com/=dnc/getdoc.xp?AN=491955947
If we assume this model holds, then we believe that once the cube has
been accepted at n (n>=2), it will be redoubled and accepted at 2n
with probability 0.152. This probability is low enough that variance
(i.e. the second order moment) is defined in general, because the
probability of successive terms of the series decreases by a factor of
0.152 per term while the squares of the results only increase by 2^2,
and so the series converges. But at the third moment, the results
increase by a factor of 2^3 per term, which exceeds the decay from the
probability; the series diverges and the third (and higher) moments
are undefined.
> So, can you construct a sequence of die rolls and plays that you are
> confident are optimal (or at least that JF or Snowie would play) which
> leads to this position?
I don't know. What about the general question? Prove or disprove:
for all positions P that may be legally reached, there exists a
sequence of dice rolls D such that an optimal play of D from the start
position leads to P.
Cheers,
Gary.
--
Gary Wong, Department of Computer Science, University of Arizona
ga...@cs.arizona.edu http://www.cs.arizona.edu/~gary/
David desJardins
> I don't know. What about the general question? Prove or disprove:
> for all positions P that may be legally reached, there exists a
> sequence of dice rolls D such that an optimal play of D from the start
> position leads to P.
I'm sure that's not true. Here's an example of a position (with X to
move) which is legally reachable, but where O's last move cannot have
been optimal:
+24-23-22-21-20-19-------18-17-16-15-14-13-+
| O X X X X | | X |
| O | | |
| O | | |
| (15) | | |
| |BAR| |
| (10) | | |
| X | | |
| X | | |
| X | | |
+-1--2--3--4--5--6--------7--8--9-10-11-12-+
O's last roll was either 5-2 or 6-2, played without hitting; in either
case, hitting would have been better.
David desJardins
David desJardins
double-2).
Here's a better example of a position (X to move) which is reachable
with legal play, but where O must have made a suboptimal move:
+24-23-22-21-20-19-------18-17-16-15-14-13-+
| O | | |
| O | | |
| O | | |
| (14) | | |
| |BAR| |
| | | |
| | | |
| X X X X X X | | |
| X X X X X X | | O X X X |
+-1--2--3--4--5--6--------7--8--9-10-11-12-+
O's last move didn't move the man on the 7 point, when it obviously
would have been better to do so.
David desJardins