termination of backgammon
Robert Koca
backgammon skill.
What is the probability that a game has infinite # of rolls? I conjecture
that it is zero (even if both players are trying to make it last forever)
but proving this is difficult.
Bob Koca ko...@orie.cornell.edu
bobk on FIBS
Dave Hughes
: Here is a useless question to those who want to improve their
: backgammon skill.
I would say that it *is* possible for a game of backgammon to last
indefinitely...just that as the number of moves increases towards infinity,
probability of the match decreases...What would be a more enlightening
question would be to compare the expected length of play for various players
of different strengths...
I'll see if I can do some work on it for you,
Dave Hughes
Department of Mathematics
University of York
England
dm...@tower.york.ac.uk
Gerry Tesauro
Robert Koca <ko...@orie.cornell.edu> wrote:
>
> What is the probability that a game has infinite # of rolls? I conjecture
>that it is zero (even if both players are trying to make it last forever)
>but proving this is difficult.
>
that seemed to produce games that last forever when it
played against itself. The basic ingredients of its
strategy were: make and hang on to the 24 and 19 points,
(i.e. the opponent's 6 point and ace point), never build
any points in its own home board, hit opponent blots whenever
possible, and spray blots around the outfield whenever
possible. This strategy, when implemented against itself,
produced what looked like a very stable steady-state
solution, with neither side making any progress toward
winning, even after letting it run for millions of moves.
Pretty amusing to watch.
-- Gerry Tesauro (tes...@watson.ibm.com)
C. T. McMullen
>that it is zero (even if both players are trying to make it last forever)
>but proving this is difficult.
>
Imagine a new game, Trigammon, with THREE players;
in addition to the usual X and O, a Dicemaster
who PICKs the roll of the dice on each play.
In this new game, X and O co-operate
to try to make the game last for ever, and the
Dicemaster tries to make it terminate.
Do you think the Dicemaster always wins this
game? [This should be easy to determine by
actually playing it! My guess is yes, but it's
not obvious.]
In any case there is an easy theorem:
The Dicemaster has a winning strategy at Trigammon
if and only if the probability of an infinite
game (with co-operating players) is zero.
The reason is simply that backgammon has only a finite
number of possible states, so in an infinite game,
any finite sequence of "bad rolls" must happen
infinitely often. In other words, X and O must
be able to beat malicious dice to play forever.
Christopher Yep
Newsgroups: rec.games.backgammon
Subject: Re: termination of backgammon
Summary:
Expires:
References: <2rqv9e$5...@falcon.ccs.uwo.ca> <2rrlma$o...@agate.berkeley.edu>
Sender:
Followup-To:
Distribution:
Organization: Compuker Science Undergraduate Association, UC Berkeley
Keywords:
Cc:
In article <2rrlma$o...@agate.berkeley.edu>,
C. T. McMullen <c...@minsk.berkeley.edu> wrote:
|>In article <2rqv9e$5...@falcon.ccs.uwo.ca>,
|>
|>Imagine a new game, Trigammon, with THREE players;
|>in addition to the usual X and O, a Dicemaster
|>who PICKs the roll of the dice on each play.
|>In this new game, X and O co-operate
|>to try to make the game last for ever, and the
|>Dicemaster tries to make it terminate.
|>
|>Do you think the Dicemaster always wins this
|>game? [This should be easy to determine by
|>actually playing it! My guess is yes, but it's
|>not obvious.]
|>
|>In any case there is an easy theorem:
|>
|> The Dicemaster has a winning strategy at Trigammon
|> if and only if the probability of an infinite
|> game (with co-operating players) is zero.
|>
|>The reason is simply that backgammon has only a finite
|>number of possible states, so in an infinite game,
|>any finite sequence of "bad rolls" must happen
|>infinitely often. In other words, X and O must
|>be able to beat malicious dice to play forever.
Actually, I think you should say: "Dicemaster has a winning strategy at
Trigammon for *ever* legally possible position if and only if the
probability of an infinite game (with cooperating) players) is zero."
It is possible that Dicemaster could have a winning strategy for the
opening (initial) position (each player: 2 men on 24, 5 on 13, 3 on 8,
5 on 6) , but that if the players can achieve a certain position (or
actually a position in a certain set of positions), then they
can prolong the game forever, always able to cycle within this certain set
of positions, no matter what rolls the dicemaster rolls. Does such a
"steady-state set" exist? It's easy to begin to eliminate positions
which can not belong in such a set, but is it possible to eliminate them
all? (all legally possible positions, that is)
My initial guess was that such a set did not exist, however, maybe
Tesauro could share some of his enlightenment with us:
>From tes...@ferrari.watson.ibm.com Tue May 24 01:47:51 PDT 1994
>I once stumbled upon a neural network with random weights
>that seemed to produce games that last forever when it
>played against itself. The basic ingredients of its
>strategy were: make and hang on to the 24 and 19 points,
>(i.e. the opponent's 6 point and ace point), never build
>any points in its own home board, hit opponent blots whenever
>possible, and spray blots around the outfield whenever
>possible. This strategy, when implemented against itself,
>produced what looked like a very stable steady-state
>solution, with neither side making any progress toward
>winning, even after letting it run for millions of moves.
>Pretty amusing to watch.
>
>-- Gerry Tesauro (tes...@watson.ibm.com)
A personal request for Gerry Tesauro: if you have time, could you like
more into this? Many thanks if you do! (i.e. either in describing the
strtegy(-ies) above more precisely, and/or looking at the strategies to
determine whether or not "Dicemaster" could always defeat them from any
starting position (see above))
Chris
Dick King
|> Here is a useless question to those who want to improve their
|> backgammon skill.
|>
|> What is the probability that a game has infinite # of rolls? I conjecture
|> that it is zero (even if both players are trying to make it last forever)
|> but proving this is difficult.
|>
Sooner or later one player will get hit and will be unlucky enough to dance for
enough rolls in a row for the other player to have no choice but to win.
-dk
Robert Koca
Sooner or later one player will get hit and will be unlucky enough to dance for
enough rolls in a row for the other player to have no choice but to win.
--
This is a good idea for the proof. However one has to make sure the point
in the home board can't be dissassembled and that the player can indded scamper
home.
One interesting thing to consider is many many 2-2's in a row. Eventually this
will end the game or give a position in which neither player can move. (note
that X's entering pieces and O's entering pieces have opposite parity and will
stay that way while 2-2 is being rolled.) Also a player can't have 3 or more
many points in a row so the other player will be able to scamper home with
the right dice. Tighten this argument and you can show that if a player makes
his 1 point the dicemaster can finish the game. With a little bit of
work a similar argument works for making the 2 point (consider many 33's, then
hit opponents blot and he repeatededly fans. Can scamper home with rolls not
using a 1, so cant break the 2 point). A similar argument works for the 3
point after considering many 22's.
bobk
C. T. McMullen
or equivalently that the dicemaster has a winning strategy from any
legal position. This proof is inspired by Koca's observation (see below).
The strategy is very simple:
MAKE EVERY ROLL 2-4.
Then the game will terminate.
It works like this. Say a checker has the right parity (R) if it is on a point
of the same color it would be if entered by an even number from the bar.
Otherwise it has the wrong parity (W).
Since all the rolls in this game are even, any time a checker is hit,
it has the right parity from that point onward.
The only possible hits are R hits W and W hits R. Every time R hits W
the number of W-parity checkers decreases, so that can only happen a
finite number of times. Every time W hits R, a W checker advances, so
that can only happen a finite number of times (the only way a W can get
sent back is to turn in to an R).
Thus in any game where only even rolls occur, there are only a finite
number of hits. (An explicit upper bound is 30 + 24x30/2 = 390, the maximal
number of W checkers plus the maximal combined pip-count for the W
checkers, divided by 2 since all moves are even.)
Now we just have to verify that we can keep both sides moving using only
even dice, indeed using only 2's and 4's.
But this is obvious. If a checker X cannot move 2 or 4
because both moves are blocked by O, then O can move 2.
QED.
-Curt McMullen
In article <2rvvgi$8...@falcon.ccs.uwo.ca>,
Gerald E Mortensen
this is assuming that eventually a position will develop where a
dance is possible -- i.e. that a point is made in the home board. i
don't think is necessarily going to happen. its possible for me to
unmake the 6 point before you ever get hit. then i think the question of
whether i will necessarily make a point in the home board again is very
similar to the original question of whether the game will necessarily end.
jay
--
** Gerald E. Mortensen (aka Jay) Syracuse Research Corp. ***
** Research Engineer Merrill Lane ***
** (315)426-3269 -- gmor...@mailbox.syr.edu Syracuse, NY 13210 ***
Christopher Yep
Unfortunately, this is not always true. If the position which dicemaster
is given (the position with which he "starts with," before he begins his
streak of 2-4s) is a position in which both X and O are on the bar, with
both players owning their own 2 and 4 pts., then neither X nor O can move.
The parity idea is a nice one though, and I'm thinking about this
question myself now.
C. T. McMullen
Christopher Yep <chri...@soda.berkeley.edu> wrote:
>
> If the position which dicemaster
>is given (the position with which he "starts with," before he begins his
>streak of 2-4s) is a position in which both X and O are on the bar, with
>both players owning their own 2 and 4 pts., then neither X nor O can move.
This is a very good point which I thought about but did not include
in my post. To explain it, we might first ask, what if the position
given to the dicemaster has both boards closed and both X and O on the bar?!
Then no one can move and the dicemaster loses.
HOWEVER, this position cannot arise in
legal play: the only way both X and O can be on the bar is if one of
them has hit upon entering, which means the board was not closed.
Similarly, if both X and O have closed their 2 and 4 points, and both
X and O are on the bar, then either X or O was hit by an entry
OTHER than 2 or 4.
So my solution (the dicemaster plays 2-4 at every roll)
works for any starting position where X and O are not BOTH on
the bar. Since with probability one, this situation (not both on
the bar) arises infinitely often in any game, it is still true that
backgammon terminates. Alternatively, given a position with both
X and O on the bar, the correct dicemaster strategy is to first
force one of them entirely off, and play 2-4 from then on.
-Curt McMullen
Seth Breidbart
Larry Hunter <Hun...@nlm.nih.gov> wrote:
>
>Re: Robert Koca's question about the probability that a game has an infinite
>number of rolls.
>
>Although it's probably obvious to everyone, no one has mentioned this yet,
>so I thought I might.
>
>It is at least possible to devise a game with an infinite number of rolls.
>There are lots of situations where a sequence of rolls returns the players
>to the original position (hitting with double 5's helps to make the
>sequences short!). So if you aren't doing a worst case analysis (e.g. the
>discussion with a dicemaster trying to terminate the game, and two players
>trying to extend it), then the probability of an infinitely long game with
>cooperative players is at least non-zero.
Not so. Consider a simple game: the first player to roll double 6's
wins. Then any two rolls without winning returns to the initial
"position", yet the probability of an infinite game is zero.
The probability of any finite sequence of rolls is non-zero; the
probability of any infinite sequence of rolls is zero.
Seth
Larry Hunter
Re: Robert Koca's question about the probability that a game has an infinite
number of rolls.
Although it's probably obvious to everyone, no one has mentioned this yet,
so I thought I might.
It is at least possible to devise a game with an infinite number of rolls.
There are lots of situations where a sequence of rolls returns the players
to the original position (hitting with double 5's helps to make the
sequences short!). So if you aren't doing a worst case analysis (e.g. the
discussion with a dicemaster trying to terminate the game, and two players
trying to extend it), then the probability of an infinitely long game with
cooperative players is at least non-zero.
Larry
--
Lawrence Hunter, PhD.
National Library of Medicine
Bldg. 38A, MS-54
Bethesda. MD 20894 USA
tel: +1 (301) 496-9300
fax: +1 (301) 496-0673
internet: hun...@nlm.nih.gov
encryption: public key via RIPEM server or "finger hun...@work.nlm.nih.gov"
Kit Woolsey
: C. T. McMullen (c...@maize.berkeley.edu) wrote:
: : Here is a proof that backgammon terminates with probability 1,
: : MAKE EVERY ROLL 2-4.
: : -Curt McMullen
: Excellent proof ( at least I don't see any flaws ).
: Any subtler strategies for Dicemaster that do the job?
: Igor
Sure. Just give each player 6-6 (after the opening roll) until nobody
can move any more. Then give each player 5-5 from then on, and I think
you will find the game comes to a quick conclusion.
Kit
Robert Macmillan
Nice idea but first you have to show that there is necessarily a prime in
the home quarter. What you are showing is that we can assume that there
is *no* prime in the home quarter.
Robert Macmillan -------------------------------------------
"I shall sit here," he said, "on and off, for days and days"
- Alice's Adventures in Wonderland
Igor Sheyn
: MAKE EVERY ROLL 2-4.
: -Curt McMullen
Christopher Yep
Now, that Curt McMullen has nicely proved that backgammon terminates, let
me go a little further, formalizing the dicemaster idea and how it
actually relates to a real game.
If dicemaster has a winning strategy from every legally possible bg
position, then for each position, let m(position) be the maximum number
of moves with which dicemaster can terminate the game, assuming the
players play optimally (optimally means cooperating to maximally prolong
the game!). Thus, if this particular position is reached, then there is
at least a 1 - (35/36)^m chance of the game terminating. Note that there
is an upper bound for m, namely the total number of bg positions, since
obviously if dicemaster is picking the dice, no position will repeat (we
are assuming that dm is also playing optimally -- ie trying to terminate
the game as quickly as possible). Then let M = max. of all m's.
Now that we've established this, we don't need the idea of dicemaster
anymore.
So, we can say that from legally possible bg position, there is at least
a 1- (35/36)^M chance of the game terminating. So, let T = 1 - (35/36)^M,
and consider the game in cycles of M dice rolls. At the beginning of
each cycle, there is at least T chance of the game terminating. If after
M rolls, the game still hasn't terminated, then there is at least T chance
that the game will terminate in the next cycle.
Thus, in order for the game to last indefinitely, the players must
survive in infinite number of cycles. This happens with prob.
(1 - T) ^ (infinity), which is exactly 0.
Thus, if dm has a winning strategy for every legally possible position,
then the game terminates with prob. 1
Chris
Christopher Yep
Ok, your proof is 100% complete now (ignoring some "handwaving" :-)).
The next question to ask is: does bg still terminate with prob. 1 if we
change the board size from 24 pips to 23 pips. (In this case all numbers
except 5s divide into (23+1=24=board size counting the bar). A similar
parity argument is unlikely to work here, if the statement is indeed
true. Also, if the statement is false, then how much do we have to
decrease the initial allotment of checkers (from 15) to, before it
becomes true. And what generalizations can be made for the general case
(board size, #checkers)?
Chris
Stephen Turner
|> The way I see it - It does not take a Harvard Graduate to realize that a
|> backgammon game can last forever. This is very in probable - but indeed
|> possible.
|>
|> I.e. - The game could avoid ever starting by a rolling doubles all of the
|> time.
|>
|> Other methods of eternal play are much more complex to prove. - And
|> require near the same probability as infinite number of doubles.
|>
Certainly there are some sequences of rolls that make the game last for
ever. But the question is whether these sequences happen with zero
probability or not. In fact they do, and so we say that in this sense
backgammon always terminates.
The idea of an event happening with probability 1 although we can
conceive of its opposite happening is one which many people find hard to
grasp. The following example might help. What is the probability that
you will never roll a 66 again however many games of backgammon you play?
It is 0 -- eventually you will roll a 66 if you play for long enough.
And yet there are infinitely long sequences of rolls which do not contain
66. It's just that the probability of rolling such a sequence is 0.
Stephen Turner
Stochastic Networks Group, Statistical Laboratory,
University of Cambridge, CB2 1SB, England
e-mail: S.R.E....@statslab.cam.ac.uk
Frank Bommarito
backgammon game can last forever. This is very in probable - but indeed
possible.
I.e. - The game could avoid ever starting by a rolling doubles all of the
time.
Other methods of eternal play are much more complex to prove. - And
require near the same probability as infinite number of doubles.
Frank Bommarito
- champion on FIBS
--
------------------------------------------------------------------------------
\ The above does not represent OIT, UNC-CH, laUNChpad, or its other users. /
------------------------------------------------------------------------