This article presents a tool for calculating single-shot probabilities in backgammon, then talks a bit about the combinatorics behind it.
The Single Shot With Blockages Tool (SSWBT) is usable by anyone who plays backgammon.
The mathematical exposition should be accessible (and hopefully interesting) to those familiar with (or willing to learn about) the basics of set theory and generating functions.
SSWBT
There are only two hard things in Computer Science: cache invalidation and naming things.
- Phil Karlton
How to use it
This tool shows the number of ways to hit a single shot while taking into account opponent-occupied points in the way.
Shot: a chance to hit a blot.
Single shot: a chance to hit a single blot.
Blot: a lone checker, susceptible to being hit.
Hit: to land on an opponent’s blot and send that checker to the bar.
Question: In Figure 2, what are Player X’s chances of hitting Player O’s blots on points \(18\) and \(17\)?
The checker of interest in this scenario is X’s checker on point \(24\), so all distances will be relative to that checker. Player O is occupying points at \(2\) and \(5\) pips, so from the drop down menu, titled \(S\), we select \(S=\{2,5\}\). The updated table shows there are \(16\) ways to hit \(6\) and \(4\) ways to hit \(7\).
A point is “occupied” if there are two or more checkers on that point. Checkers may not land on a point that occupied by the opposing player’s checkers.
Answer: Player X has a \(16/36\approx44\%\) probability to hit \(6\), and a \(4/36\approx11\%\) probability to hit \(7\).
Of course, Figure 2 presents a double shot, not just a single shot. The number of ways to hit a double shot is the sum of the ways to hit the single shots, less the number of ways to hit both. In this case, that would be \(16\) ways to hit \(6\), plus \(4\) ways to hit \(7\), less \(2\) ways to hit them both. That is \(16+4-2=18\) ways to hit either the \(6\) or \(7\).
Double shot: a chance to hit two blots.
There are two rolls that hit both: \((1,6)\) and \((6,1)\).
Slightly better answer: Player X has a \(18/36=50\%\) probability to send at least one of Player O’s checkers to the bar.
Math
Let \(D\) be the set of all possible values a six-sided die may take on, \[D=\{1,2,3,4,5,6\},\] and let \[S_p\subseteq D\] be the set of distances from a checker on point \(p\) to opponent-occupied points. For example, in Figure 2, \(S_{24}=\{2,5\}\). If there is no concrete board under discussion, \(p\) is left unspecified.
The equation governing SSWBT is as follows:
\[ F_S(x)=B_S(x)-\sum_{s\in S}[x^s]B_S(x)x^s, \tag{1}\]
\([x^s]B_S(x)\) means: the coefficient of the \(x^s\) term in the series \(B_S(x)\).
For example, \([x^2](1 + 3 x + 3 x^2 + x^3)=3\).
where \[ B_S(x)=A_D(x)-A_S(x), \tag{2}\] and
\[ A_Z(x)=\sum_{z\in Z}\sum_{1\leq i\leq 4} x^{iz} + \sum_{\{a,b\}\in\binom{Z}{2}} 2\left(x^a + x^b +x^{a+b}\right). \tag{3}\]
\(\binom{Z}{2}\) means: the set of all subsets of \(Z\) of cardinality \(2\).
For example, if \(Z=\{1,2,3\}\), then \(\binom{Z}{2}=\{\{1,2\},\{1,3\},\{2,3\}\}\).
We will proceed by examining Equation 3, then Equation 2, then finally Equation 1.
Equation \(3\): \(A_Z(x)\)
A generating function
“Answer to ‘What are generating functions?’” Mathematics Stack Exchange, May 5, 2013.
Chapter 6 of Applied Combinatorics by Alan Tucker is also a good introduction.
I started this whole investigation by trying to find a generating function for all the ways to hit a single shot. This is what I came up with:
\[ A(x)=\sum_{\left(i,j\right)\in D^2} \begin{cases} x^i +x^{2i} + x^{3i} + x^{4i} \,&,& i = j \\ x^i + x^j + x^{i+j} \,&,& i \ne j. \\ \end{cases} \tag{4}\]
\(D^2\) means: the Cartesian product \(D\times D=\{(1,1),(1,2),...(6,5),(6,6)\}.\) This is the sample space—the set of all possible rolls—of which there are \(36.\)
When we roll doubles, i.e. \((i,j)\in D^2 \text{ and } i=j,\) we move the number on the die four times instead of twice; hence first case of the piecewise. When we roll non-doubles, i.e. \((i,j)\in D^2 \text{ and } i\ne j,\) we allocate each die to two distinct checkers or we move a single checker \(i+j\) pips; hence the second case of the piecewise.
The expansion of \(A(x)\) is as follows:
\[ \begin{aligned} A(x)=\, &11 x + 12 x^2 + 14 x^3 + 15 x^4 + 15 x^5 + 17 x^6 + 6 x^7 + 6 x^8 + \\ &5 x^9 + 3 x^{10} + 2 x^{11} + 3 x^{12} + x^{15} + x^{16} + x^{18} + x^{20} + x^{24}. \end{aligned} \tag{5}\]
For each term \(c_nx^n\), the coefficient \(c_n\) is the number of ways to hit \(n\) pips from a given checker. For example, we read from the term \(2x^{11}\) that there are two ways to hit \(11\); namely \((5,6)\) and \((6,5).\)
So there we have it: the number of ways to hit every hittable distance. Note that the sample space \(D^2\) has \(36\) elements, but that the sum of coefficients of \(A(x)\) is clearly greater than \(\left|D^2\right|=36\). That’s because a single roll permits multiple hits.
A parameterized generating function
In order to account for blockages, we need a way to isolate the contribution of specific elements of \(D,\) say \(Z\subseteq D.\) We could just replace \(D^2\) with \(Z^2\) in Equation 4, however, to do away with the piecewise cases, we will consider each element \(z\in Z\) directly, instead of the ordered pairs \((i,j)\in Z^2\).
Each piecewise case of Equation 4 is brought down from \(Z^2\) into \(Z\) as follows:
\[ \sum_{(i,j)\in Z^2,\,i=j} x^i +x^{2i} + x^{3i} + x^{4i} = \sum_{z\in Z} x^z +x^{2z} + x^{3z} + x^{4z}, \] and \[ \sum_{(i,j)\in Z^2,\,i\ne j} x^i + x^j + x^{i+j} = \sum_{\{a,b\}\in\binom{Z}{2}} 2\left(x^a + x^b +x^{a+b}\right). \]
Note that the right hand side of the preceding equation is multiplied by two because each subset \(\{a,b\}\in \binom{Z}{2}\) corresponds to two distinct ordered pairs \(\{(a,b),(b,a)\}\subset Z^2\). And so we have arrived at Equation 3 from Equation 4.
To make an example of Equation 3, let’s find what hits are made possible with \(Z=\{2,5\}.\)
\[ \begin{aligned} A_{\{2,5\}}(x) &= \sum_{z\in \{2,5\}}\sum_{1\leq i\leq 4} x^{iz} + \sum_{\{a,b\}\in\binom{\{2,5\}}{2}} 2\left(x^a + x^b +x^{a+b}\right)\\\\ &= x^2 + x^4 + x^6 + x^8 + x^5 + x^{10} + x^{15} + x^{20} + 2 (x^2 + x^5 + x^7)\\\\ &= 3 x^2 + x^4 + 3 x^5 + x^6 + 2 x^7 + x^8 + x^{10} + x^{15} + x^{20}. \end{aligned} \]
The set of all possibles rolls \(Z^2\) with \(Z=\{2,5\}\) is
\[Z^2=\{(2,2),(2,5),(5,2),(5,5)\}.\]
Looking at this set, we can verify that there are indeed \(3\) ways to hit a \(2\), \(1\) way to hit a \(4\), \(3\) ways to hit a \(5\), and so on.
For each term \(c_nx^n\), the coefficient \(c_n\) is the number of ways to hit \(n\) pips from a given checker.
Equation \(2\): \(B_S(x)\)
The number of ways to hit a shot is given by Equation 5; the number of ways to hit a shot using only \(Z\subseteq D\) is given by Equation 3. The number of ways to hit a shot, taking into account opponent occupied-points in the way, the distance from our shooting checker to the blockages being elements of the set \(S\subseteq D\), is given by Equation 2.
No blockages
Without any blockages, as in Figure 3, X has the following number of ways to hit the shots: \[ [x^6]B_{\emptyset}(x)=17,\quad [x^7]B_{\emptyset}(x)=6. \]
\([x^n]B_S(x)\) means: the coefficient of the \(x^n\) term in the series \(B_S(x)\). For each term \(c_nx^n\), the coefficient \(c_n\) is the number of ways to hit \(n\) pips from a given checker.
One blockage
If O occupied point \(22\), as in Figure 4, so that \(S_{24}=\{2\}\), X’s chances to hit wouldn’t be much hindered, as the only roll blocked is \(S_{24}^2=\{(2,2)\}\): \[ [x^6]B_{\{2\}}(x)=16,\quad [x^7]B_{\{2\}}(x)=6. \]
If O occupied point \(19\), as in Figure 5, so that \(S_{24}=\{5\}\), X’s chances to hit wouldn’t be hindered at all, as the only roll blocked is \(S_{24}^2=\{(5,5)\}\): \[ [x^6]B_{\{5\}}(x)=17,\quad [x^7]B_{\{5\}}(x)=6. \]
Two blockages
If, however, O occupied both points, as in Figure 2, such that \(S=\{2,5\}\), more than just a single roll would be blocked: \[\{2,5\}^2=\{(2,2),(2,5),(5,2),(5,5)\}.\] One of the blocked rolls would have hit \(6\), and two rolls would have hit \(7\). X’s chances are hindered accordingly: \[ [x^6]B_{\{2,5\}}(x)=16,\quad [x^7]B_{\{2,5\}}(x)=4. \]
Equation 1: \(F_S(x)\)
There is one last thing to correct for. Looking over the series \[ \begin{aligned} B_{\{2,5\}}(x)=11 x &+ 9 x^2 + 14 x^3 + 14 x^4 + 12 x^5 + 16 x^6 + 4 x^7 + 5 x^8 \\ &+ 5 x^9 + 2 x^{10} + 2 x^{11} + 3 x^{12} + x^{16} + x^{18} + x^{24}, \end{aligned} \] one might notice something funny: we see that \[ [x^2]B_{\{2,5\}}(x)=9\ne 0\quad\text{and}\quad[x^5]B_{\{2,5\}}(x)=12\ne 0. \] The points are \(2\) and \(5\) pips from our shooting checker are supposed to be opponent-occupied—and according to the rules of backgammon, there are exactly \(0\) ways to hit an opponent-occupied point—so the set of all \([x^s]B_S(x)\) such that \(s\in S\) should be \(\{0\}\). Hence, the correcting term \[ -\sum_{s\in S}[x^s]B_S(x)x^s. \]
With \(S=\{2,5\},\) the correcting term would be \[ -(9 x^2 + 12 x^5), \] which achieves the intended effect.
And so we have arrived at Equation 1 from Equation 2.
Conclusion
We have reached the end of the mathematical exposition. I hope the explanations were not lacking. I do have aspirations to develop more backgammon-related tools/widgets; perhaps building directly from this one, or perhaps starting anew on some other aspect of the game.
Anyways, I hope SSWBT proves helpful, or interesting, or some combination of those—and I thank you for your time.
Cheers.