1
$\begingroup$

I aplogize in advance for the somewhat long post. I've tried to split it into manageable paragraphs.

So in backgammmon, in the so-called "end-game", both players have their pieces in their respective final regions of the board, which each comprise six positions. So we can think of each player's pieces' position being a multiset of the set $\{1,2,3,4,5,6\}$ where the size of the multiset is the number of pieces left.

The goal is to finish "bearing off" before the opponent, which means removing all your pieces from the board. Each player takes turns rolling two six-sided dice on their turn, and basically the rules for bearing off are as follows: 1) A die can be played perfectly if the die roll is $k$ and a piece is at position $n \geq k$, in this case the piece can be moved to position $n - k$, and removed from the board if $n = k$. If either the two dice rolls can be played perfectly, then it must be. 2) If one of the die rolled is greater than all positions of pieces on the board, then the piece with greatest position must be removed from the board in order to play that die roll. Also, if the two dice rolled are equal, then the player makes $4$ moves of the dice face value instead of $2$.

Anyway, I've played backgammon for a while and some computer backgammon programs will auto-bear off for you. But is there an easy optimal or near-optimal way to do this? For example, if you have three or four pieces left on the board and your opponent has two pieces at positions $(1,1)$ or $(1,2)$, then your opponent will always win in one next roll so you should minimize the largest value of your pieces' positions so that you maximize the chance of winning by rolling doubles (which is the only way to win). This strategy seems clearly different than maximizing the number of pieces removed, or even maximizing the expected number of pieces removed on the next turn.

Since each player only has 15 starting pieces in backgammon, I can envision an at least feasibly fast fast dynamic programming algorithm that finds the next move that maximizes the probability of winning given each player's pieces' positions on the board as a multiset of $\{1,2,3,4,5,6\}$. But at least on the online backgammon games I've played against other players, there is only about a 10 second time limit to make a move before a reserve time counter starts counting down, and the reserve counter is typically only a few minutes total. So how do players best quickly decide how to bear off on each roll? is there an easy optimal or near-optimal solution that at least fairly "typical" trained humans can compute, or will brute-force dynamic programming solutions typically be a bit better?

$\endgroup$
  • $\begingroup$ I predict this post will not survive long. There's plenty of information about standard bearoff strategy elsewhere on the internet. I'll just say one thing: Exceptions to the bear-off-as-many-as-possible rule are very rare. In particular, that thing where you want to maximize the number of doubles that work with one play left to go is not an exception. Say you have one man on the 6 point, two on the 5 point and one on the 1 point. Moving 65 makes double fives work. But bearing a man off also makes doublr fives work. $\endgroup$ – David C. Ullrich Dec 22 '15 at 18:18
  • $\begingroup$ There are, I think, $54264$ possible positions for each player with up to 15 pieces, so $54264^2 = 2944581696$ possible situations considering both players. I don't think the dynamical programming solution is going to be all that quick in the cases where most pieces are still on the board. $\endgroup$ – Robert Israel Dec 22 '15 at 18:23
  • $\begingroup$ @RobertIsrael Especially when you consider that you don't want to maximize your chance of winning, you want to maximize your expectation. $\endgroup$ – David C. Ullrich Dec 22 '15 at 18:27
  • $\begingroup$ @RobertIsrael (in match play) $\endgroup$ – David C. Ullrich Dec 22 '15 at 19:02
  • $\begingroup$ @DavidC.Ullrich I apologize if my post seems trite, but my question really was intended to be mathematical -- I am aware of standard bear-off rules but I have not seen a proof that they are always optimal, or a computed worst-case probability (over all possible configurations) that they will lose when the true optimal solution would have won. And by maximizing "expectation" instead of probability of winning (taking into account all possible future rolls in either case), do you mean maximizing the expected number of points in a multi-point match, taking into account doubling and gammon bonus? $\endgroup$ – user2566092 Dec 24 '15 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.