Theory

Forum Archive : Theory

 
Proof that backgammon terminates

From:   Robert Koca
Address:   koca@orie.cornell.edu
Date:   23 May 1994
Subject:   termination of backgammon
Forum:   rec.games.backgammon
Google:   2rqv9e$5i7@falcon.ccs.uwo.ca

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.

Bob Koca koca@orie.cornell.edu
bobk on FIBS

Dick King  writes:

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.

Robert Koca  writes:

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 indeed
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.

C. T. McMullen  writes:

Here is a proof that backgammon terminates with probability 1, or
equivalently that the dicemaster has a winning strategy from any legal
position.  This proof is inspired by Koca's observation above.

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.

Christopher Yep  writes:

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.

C. T. McMullen  writes:

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.
 
Did you find the information in this article useful?          

Do you have any comments you'd like to add?     

 

Theory

Derivation of drop points  (Michael J. Zehr, Apr 1998) 
Double/take/drop rates  (Gary Wong, June 1999) 
Drop rate on initial doubles  (Gary Wong, July 1998) 
Error rate--Why count forced moves?  (Ian Shaw+, Apr 2009) 
Error rates--Repeated ND errors  (Joe Russell+, July 2009) 
Inconsistencies in how EMG equity is calculated  (Jeremy Bagai, Nov 2007)  [GammOnLine forum]
Janowski's formulas  (Joern Thyssen+, Aug 2000) 
Janowski's formulas  (Stig Eide, Sept 1999) 
Jump Model for money game cube decisions  (Mark Higgins+, Mar 2012) 
Number of distinct positions  (Walter Trice, June 1997) 
Number of no-contact positions  (Darse Billings+, Mar 2004) 
Optimal strategy?  (Gary Wong, July 1998) 
Proof that backgammon terminates  (Robert Koca+, May 1994)  [Recommended reading]
Solvability of backgammon  (Gary Wong, June 1998) 
Undefined equity  (Paul Tanenbaum+, Aug 1997)  [Recommended reading]
Under-doubling dice  (Bill Taylor, Dec 1997)  [Recommended reading]
Variance reduction  (Oliver Riordan, July 2003)  [Long message]

[GammOnLine forum]  From GammOnLine       [Long message]  Long message       [Recommended reading]  Recommended reading       [Recent addition]  Recent addition
 

  Book Suggestions
Books
Cheating
Chouettes
Computer Dice
Cube Handling
Cube Handling in Races
Equipment
Etiquette
Extreme Gammon
Fun and frustration
GNU Backgammon
History
Jellyfish
Learning
Luck versus Skill
Magazines & E-zines
Match Archives
Match Equities
Match Play
Match Play at 2-away/2-away
Miscellaneous
Opening Rolls
Pip Counting
Play Sites
Probability and Statistics
Programming
Propositions
Puzzles
Ratings
Rollouts
Rules
Rulings
Snowie
Software
Source Code
Strategy--Backgames
Strategy--Bearing Off
Strategy--Checker play
Terminology
Theory
Tournaments
Uncategorized
Variations

 

Return to:  Backgammon Galore : Forum Archive Main Page