Introduction
I recently read the following blog post that calculates the state space of the Royal Game of Ur programmatically. This is done exhaustively, and there is a challenge set forth for a closed form solution based on the number of pieces. I take up that challenge here and present a closed form.

I recommend giving the original post at least a skim before continuing here, as it outlines the rules of the game, which I won’t repeat here. It won’t be necessary to understand deeply the ways of modeling the game in the original post, since I’ll define my own notation here.

Model and Derivation

I model the game as following. Each player has $p$ pieces, which can be either at the start or finish, or on the board. Let the number of pieces player 1 has on the board be $p_1$ and the number player 2 has on the board be $p_2$.

The board has $m$ shared spaces, that is, $m$ spaces that can be occupied by either player’s pieces. Additionally, each player has access to $n$ unshared spaces, which can only have their pieces on them. The board in total then has $m + 2n$ spaces.

Let’s begin constructing our closed form solution by accounting for the pieces not on the board. For each player, this is $p-p_1$ and $p-p_2$. These pieces can be either at the start or finish, and are identical. Let's adopt a notation $(x,y)$, where $x$ is the number of pieces at the start, and $y$ is the number of pieces at the finish. For 1 piece, there are two possibilities (1,0) or (0,1). For 2 pieces, three possibilities (2,0), (1,1) or (0,2). In general for $q$ pieces, there are $q+1$ possibilities. So for off board possibilities we have a cardinality of $(p-p_1+1)(p-p_2+1)$. The off board state is independent of the on board state, so we will end up multipying them together.

For a given number of pieces $p$, each player's on board pieces are in the range $p_i = 0,1,...,\min(p,m+n)$. The case $p_i = p$ corresponds to the case where all of the players pieces are on the board, none are at the start or finish. We also need to bound for the case $p > m+n$ and make $p_i = m+n$, since the board can not hold more than $m+n$ pieces of a single player's. So we can write for $p$, considering only off board possibilities the state space:

$$\sum_{p_1 = 0}^{\min(p,m+n)}\sum_{p_2 = 0}^{\min(p,m+n)} (p-p_1+1)(p-p_2+1)$$

The on board cardinality is a little bit more complicated. We can approach it in the following way. Let $j$ be the number of player 1’s pieces on unshared spaces. There are $n \choose j$ ways to make these placements. The rest of player 1’s on board $p_1-j$ pieces must lie in the $m$ shared spaces. There are $m \choose p_1-j$ ways to make those placements. So considering only player 1’s pieces, we have ${n \choose j}{m \choose p_1-j}$ possibilities.

Now we just need to place player 2's pieces. We know that player 1 is taking up $p_1-j$ shared spaces, so the number of spaces available for player 2 to place in is $m+n-(p_1-j)$, and they have $p_2$ pieces to place. So the number of possibilities is $n+m-(p_1-j) \choose p_2$.

Now we simply need to iterate over all the possible j’s and sum. As a reminder, $j$ is the number of player 1’s pieces in unshared spaces. We can have 0 pieces on the unshared spaces, and up to the minimum of $p_1$ and $n$ (corresponding to running out of pieces to place, or squares to place on).

So without further ado, here is the closed form solution for the state space: $$S = \sum_{p_1 = 0}^{\min(p,m+n)}\sum_{p_2 = 0}^{\min(p,m+n)}\sum_{j = \max(0,p_1-m)}^{\min(p_1,n)} (p-p_1+1)(p-p_2+1) {n \choose j} {m \choose p_1-j} {m+n-(p_1-j) \choose p_2}$$ This solution agrees completely with the second table of the original blog post. For instance, for $m = 8$, $n = 6$ and $p=7$ we obtain $S = 137,913,936$ as our state space. Isn’t it nice when two different solution methods agree?

Accuracy
There are a couple of caveats that I want to cover here. This solution is not quite exact. There is 1 possibility included in our summation that is not a valid state. It presumably is not valid for both players to have all their pieces in the finish state, since the game should end as soon as one player gets all their pieces to the end. This is just one state, and we can just subtract it from our total. $$S_{\mathrm{bothwin}} = S - 1$$

Conditions and Considerations
We also would need to modify our solution if the final four spaces on the board are shared and not unshared. There are example gameboards of both types. If the last four spaces are shared, then the cases where one player has all of their pieces at the finish cannot include configurations of the opposing player having pieces in the final four squares. This can be represented by $$\Delta_{\mathrm{shared}} = 2 \sum_{p_1 = 4}^{\min(m+n),p} (p-p_1+1) {n+m-4 \choose p_1 - 4}$$ To understand this, assume player 2 has won, so there is exactly one state for their pieces, player 1's pieces can then be placed in the offending 4 end positions, and then anywhere else. The factor of 2 recognizes the symmetry between player 1 and player 2 here. So this counts that number of states, and could be subtracted in the case that the board has the last four spaces shared. $$S_{\mathrm{shared}} = S_{\mathrm{bothwin}} - \Delta_{\mathrm{shared}}$$

You may want to consider as part of the game state whose turn it is. If you wish to, a multiplication by 2 of the states will do it except again, for victory positions - where the game must have ended (The victory state would always have either the victorious player or losing player having the turn, by semantics and convention) The number of victory states is $$\Delta_{\mathrm{turns}} = 2\sum_{p_1 = 0}^{\min(m+n),p} (p-p_1 + 1) {n+m \choose p_1}$$ With similar reasoning as the term for the last four spaces being shared. So we have $$S_{\mathrm{turns}} = 2 S_{\mathrm{bothwin}} - \Delta_{\mathrm{turns}}$$

And we can consider both $\Delta$'s and the both win scenario if we need to $$S_{\mathrm{all}} = 2 S - \Delta_{\mathrm{turns}} - \Delta_{\mathrm{shared}}$$ Note that because the positions counted in $\Delta_{\mathrm{shared}}$ are a subset of those counted in $\Delta_{\mathrm{turns}}$ the totally invalid states are counted 0 times, the victory states where turns are irrelevant are counted once, and the non-victory states are imbued with a factor of two to represent whose turn it may be. We dropped our minus one from the "both win" scenario due to it being incorporated into $\Delta_{\mathrm{turns}}$ already. I've tried test cases for these and believe these corrections to be right. But I don't have full confidence since there aren't trusty computer calculations behind them.

We do not need to restrict the value of $p$ based on the size of the game board. Since as many pieces can wait at the start or finish as we desire, we don't clog the board up and overcount if this happens. It takes a little work to see that our summation accounts for this, but can be worked out from the property $k > n \implies {n \choose k} = 0$. Indeed, we can actually remove some of our summation limits and have this property take care of some extraneous cases.

Large case tests
With a closed form, we can see the state space for very large variants. For parameters $p = 140$, $m = 160$ and $n = 120$ (a game 20x larger than standard) we find a state space of $2.886*10^{151}$ without corrections, and $5.772*10^{151}$. With this truncation, exactly the factor of two from considering whose turn it is. The nitpicking around victory conditions doesn't matter too much as the games grow larger - the meat of the states are not going to include a player having achieved victory.

You can find the implementation of the original $S$ and corrections in python here. I have left it not subtracting 1 from each of the state spaces.