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)
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)
Solvability of backgammon  (Gary Wong, June 1998)
Undefined equity  (Paul Tanenbaum+, Aug 1997)
Under-doubling dice  (Bill Taylor, Dec 1997)
Variance reduction  (Oliver Riordan, July 2003)

 From GammOnLine         Long message         Recommended reading         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