Backgammon EndsMizban Host
Mathematicians look at the world a bit oddly. We are interested in obscure things, we derive great satisfaction from being certain about things others might take for granted or never think about, and frequently we can apply these to make interesting statements about the “real world” (much to our embarrassment). I hope that you will agree that this is one of those interesting statements.
|Theorem (Curt McMullen, 1994): |
Backgammon ends with probability 1
That is, if one uses random dice (even mildly biased ones), and any legal playing strategy (even trying to lose), then the probability that the game has ended by the nth move gets arbitrarily close to 1 as n increases. There is some move such that the chance the game has ended by that move is at least 99%, at least 99.999%, etc. so the chance that a game continues forever is 0.
This result, like the bulk of mathematics, involves little computation. I haven’t seen the details written up anywhere yet, but this result should be accessible to any serious backgammon player. I’ll use 3 steps to demonstrate the theorem.
Step 1: Let us imagine a variation: Player A calls (chooses) the dice, and Player B has to make a legal move. It is enough to show that this modified game is a win for Player A as long as the initial position is legal.
Step 2: In this modified game, from any legal position Player A may choose the dice so that not both players are on the bar. (This can be done in 20 rolls.)
Step 3: From any position in which not both players are on the bar, Player A may end the game by calling 2-4 enough times in a row. (9000 is enough times.)
Why does it suffice to show that calling the dice can end the game? Let us suppose that from any position, some fixed number n of carefully chosen rolls will end the game. (We can take n to be the maximum number of rolls needed over the finite set of possible legal backgammon positions if we had a value for each position.) There is a chance of at least that the dice will behave as though called by Player A for n rolls. That’s not much, but suppose it doesn’t happen. Then after the first n rolls, if the game is still going on, there will again be at least a chance that the dice will behave as though called by Player A. For the game to continue, it must keep avoiding these chances. That will happen for a while, but with probability 1, eventually the probability event will occur, and the dice will behave as though possessed. If the lottery is fair and you keep playing, eventually you will win, and will even win infinitely often.
Ok, so how might a player calling the dice end the game? First, Player A can get at least one player off of the bar. That’s easy enough to do if the position is legal; it can’t be that both players are shut out. So if a player is not shut out, give them doubles of a number which is open. If this gets all of that player’s checkers off the bar, then we can move on to the next step. If not, then 4 checkers came off the bar, and at most one was hit. So there are now at least 3 fewer checkers on the bar. One can give a better estimate, but since there are 30 checkers total then after at most 10 exchanges (20 rolls) at least one player will have no checkers on the bar.
Finally, if at least one player is not on the bar, then repeatedly calling 2-4 will end the game. Part of Curt McMullen’s idea was that in this case at least one player must be able to play part of a 2-4. If you have made points 2 and 4 pips ahead of a checker of mine, then you have a 2 to play, from the point 4 ahead to the point 2 ahead. You might not be able to play this if you are on the bar, but then either you can move off the bar or I have made points 2 and 4 pips ahead of you, my 2 and 4 points. So the only possible way that we would both be stuck under this deluge of 2-4’s is if we are both on the bar with our 2 and 4 points made. That can’t happen from a position in which one player is not on the bar by a sequence of 2-4 rolls, since the only way for both players to be on the bar is if one hits from the bar, and if you hit me from the bar with a 2-4 it must be that my 2 or 4 point isn’t made. So although it might be the case that both players are on the bar, under successive 2-4’s starting from a position in which at most one player is on the bar at least one player can move.
Ok, but what if the players just keep sending each other back? Now the second part of Curt McMullen’s idea comes in: When you get hit, your checker goes to the bar, which is your 25 point. Henceforth, that checker will always be on an odd point if the dice always show 2-4. Your odd points are your opponent’s even points, so once a checker of yours is hit, it can’t hit a checker on one of your opponent’s odd points. Even though the pip count might oscillate, in some sense there is progress being made; a checker on an even point must advance eventually and cannot be sent back to an even point. This suggests using a modified pip count which decreases on each exchange whether or not hits are made.
Define the modified pip count to be the pip count of checkers on odd points plus 12.5 times the pip count of checkers on even points.
For example, in the above position, the modified pipcount for white is 6 odd pips plus 12.5 times 8 even pips = 106. For red, there are 51 odd pips and 12.5 times 6 even pips, so the modified pipcount is 126. The total modified pipcount is 106 + 126 = 232.
The modified pipcount decreases with every 2 or 4 played:
- If no checker is hit, clearly the pipcount decreases by at least 2, since either the odd pips or even pips decrease by 2 or 4.
- If you hit by moving a checker on an odd point of yours, it must hit a checker on an even point of your opponent. Your odd pip total decreases by at least 2. The hit checker contributed at least 25 pips (2 × 12.5) to your opponent’s modified pipcount, and now contributes exactly 25 (on the bar), so your opponent’s modified pipcount stays the same or decreases. So the total modified pipcount decreases by at least 2.
- If you hit by moving a checker on an even point of yours, it must hit a checker on an odd point of your opponent. This decreases your modified pipcount by at least 25 (2 even pips times 12.5). Your opponent’s modified pipcount increases by at most 22 (from 3 to 25), so the total decreases by at least 3.
Finally, the modified pipcount of a checker is greatest when it is on the 24 point, where its value is 24 times 12.5 = 300. There are 30 checkers, so the maximum possible modified pipcount is 300 times 30 = 9000. With each exchange, the modified pipcount decreases by at least 2, so after 9000 2-4’s in a row (4500 exchanges) the modified pipcount will have been reduced to 0, and the game will be over.
So from any legal position, there is at least a chance that the game will end within the next 9020 rolls, so backgammon ends with probability 1.
Of course, one can tighten the estimates somewhat, and more intelligent choices by player A would end the game much sooner. From the starting position, 8 5-5’s followed by 11 6-6’s would end the game. One could use 3-6 instead of 2-4. The proof can’t be tightened too much since it is possible for the game to last over 500 rolls of 2-4. This method of proof also provides no practical limit on the length of a game, since the universe will run down before the half-life of a backgammon game that ends with probability every 9020 rolls. Further, any digital random number generator will eventually cycle, and it is possible that a game played using such a generator could cycle, too.
On the other hand, this result means that there should be no draws in backgammon. If there is a cap on the cube or in match play, perfect play exists, and no matter how wild the position appears, there is some equity one may theoretically assign to the position. I don’t know about you, but I’ll sleep better at night knowing this.
Article by: Douglas Zare
Leave a Reply