The size of Ur

How big is the kingdom of Ur? To compute the number of ROGOUR positions we start with a smaller configuration, one whose size is relatively easy to figure out. Let \(C_{g,r,m}\) be the number of configurations with \(g\) green and \(r\) red pieces on the board, with \(m\) green pieces in the common strip (squares 1-8). The \(g-m\) pieces on abcdyz can be placed in \(\binom{6}{g-m}\) ways, the \(m\) pieces on 1-8 in \(\binom{8}{m}\) ways, and the \(r\) pieces in \(\binom{14-m}{r}\), since \(m\) squares are occupied by green pieces.

\[C_{g,r,m} = \binom{6}{g-m} \binom{8}{m} \binom{14-m}{r}.\]

Summing over \(m\) would give us \(C_{g,r}\), the number of configurations with \(g\) green and \(r\) red pieces on the board:

\[C_{g,r} = \sum_{m=0}^g C_{g,r,m}.\]

The remaining \(7-g\) green pieces can be distributed between the home (waiting to start the race) and off (born out of the board) in \(1+7-g\) ways, and so the total number of positions with \(g\)/\(r\) Green/Red pieces on the board is

\[N_{g,r} = (8-g) C_{g,r} (8-r).\]

And the total number of Ur positions is:

\[N_{ur} = \sum_{g=0}^7 \sum_{r=0}^7 N_{g,r},\]

which comes up to, Ta-Dam, 137,913,936 positions.

Not a small number, but tiny in the world of games. Chess has somewhere around \(10^{50}\) positions, Backgammon \(10^{19}\) (18,528,584,051,601,162,496 to be precise). 138 million is definitely within reach, and one of the reasons I got excited. Even more exciting is this breakdown by number of green/red pieces borne off.

Ur positions by Green/Red borne-off pieces
g/r 0 1 2 3 4 5
0 \(10^{7.3}\)
1 \(10^{7.5}\) \(10^{7.2}\)
2 \(10^{7.3}\) \(10^{7.2}\) \(10^{6.7}\)
3 \(10^{7.0}\) \(10^{6.9}\) \(10^{6.7}\) \(10^{6.1}\)
4 \(10^{6.6}\) \(10^{6.5}\) \(10^{6.3}\) \(10^{5.9}\) \(10^{5.2}\)
5 \(10^{6.1}\) \(10^{5.9}\) \(10^{5.7}\) \(10^{5.4}\) \(10^{4.9}\) \(10^{4.0}\)

Since a borne-off piece never returns to the board it is possible to analyze the game in stages. First all 6/6 positions, i.e. a single green piece vs. a single red piece, then 6/5 (2 green vs. one red), which always lead either to a 6/6 position or to the game end, then 5/5 and so on. This is quite nice when you don’t have a Google farm at your disposal.