Royal Game of Ur (Background)

2021-10-29

Updated 2021-12-17: A closed-form solution has been submitted

The Royal Game of Ur, also known as the Game of Twenty Squares, is one of the oldest known board games, with attestations from 3000 to 250 BC. It was an enduringly popular game, played across multiple civilizations and across the Middle East. As a racing game, two players compete to move their pieces along and off the board, where their own pieces can act as road blocks to their own movement but can also send the other’s players pieces back to the beginning. In this article (part I), I present the rules for the game and discuss the game complexity metrics. In part II, I will discuss solving the game by computing the optimal strategy.

Rules

Contrary to claims that the rules have been fully discovered, we are still unsure how this game was played historically. Indeed, with a lifespan nearing 3000 years and being played by different cultures and geographies, there may have been many variants of the rules and changes over time. We know that in the latter period of time, the board straightened itself out (see figure). The path around the board, significance of the rosettes, and how to interpret dice rolls are all educated guesses. My copy of the game from Masters Traditional Games lists three routes and four rule variants. The path denoted in the figure is the “RC Bell” route.

“Standard” version

The “standard” version is the set of rules you are likely to find implemented in electronic versions. This version of the rules was established by Irving Finkel based on archaeological copies of the board, inferences from the Itti-Marduk-balāṭu tablet, and experimentation. I imagine most people became aware of the game through the Youtube match between Irving Finkel and Tom Scott:

(User tracking should be disabled unless you play the video.)

Since analyzing a half-dozen variants of the game would be tedious, I’ll be focusing on this set of the rules.

The game’s objective is for a player to move their seven pieces along their route and off the board before the other player can do the same.

1. All pieces begin in the “starting pool” and are not on the board.
2. On a player’s turn, they roll four tetrahedral dice to determine how far they can move a piece. Each die allows only a result of zero or one, so the range of results of a throw is between 0 and 4 inclusive. (A zero result is a lost turn.) In Johnstone/standard dice notation ¹, this is a roll of 4d2 - 4.
3. Only one piece can be moved per roll and a piece must move forward. Pieces may be moved from those on the board or in the starting pool. If no pieces can be moved, the player loses the turn.
4. A piece cannot move forward onto a piece owned by the same player and only one piece may occupy a square at a time. If a piece lands on a square owned by the opposing player, the opposing player’s piece is placed back in the starting pool (off the board). However, the middle rosette square is “safe” and a piece on this square cannot be ejected from the board.
5. If the piece lands on a rosette, the player must roll again. The next move does not need to use the same piece.
6. Pieces are removed from the board on an exact roll.

Humorously, in the video Finkel makes a big scene about Tom Scott calculating the odds for a roll of the dice and Finkel proclaims he’s never had any use for maths. But in his own paper, he works out the odds for the various rolls.

Itti-Marduk-balāṭu - Gambling version

Irving Finkel’s On the rules for the Royal Game of Ur ² describes a different, more complex game based on a tablet written by Itti-Marduk-balāṭu. Since the game in the tablet is a modification of a “base” game, the standard version is (partly) defined by reverse-engineering the tablet’s version of the rules. In contrast to the standard version, the tablet version has five labeled pieces and a mechanism to be bet or gamble during play. This version is played on the elongated or revised board.

Each player has five pieces, labeled Swallow, Storm-bird, Raven, Rooster, and Eagle respectively.

There are two types of dice: a standard tetrahedral 1d4 and a yes/no die or 1d2. The rules for how to interpret the dice from the tablet allow many options, but for sake of choosing a single option, a player will first roll the 1d4. They may then roll the yes/no die. If the roll is ‘no’, the turn is lost. If the roll is ‘yes’, the 1d4 result is transformed to 1->5, 2->6, 3->7, and 4->10.

Each player starts with 15 counters and the game pool starts with 20 counters initially.

Similar to the standard version, players move their pieces around the board and attempt to exit all pieces before their opponent. While playing, players may gain by landing on the rosettes and lose points by skipping over them. A player also loses points based on pieces remaining on the board at the game end. The winner is the one with the most points at the end.

1. To launch a piece onto the board, a specific role must be made. The swallow requires a 2, the storm-bird a 5, the raven a 6, the rooster a 7, and the eagle a 10. When launched, the swallow appears on the first rosette (position 4), while the others start at positions 5, 6, 7, and 10 respectively.
2. Pieces must be launched in sequence. If a player has the swallow and storm-bird in play (or in the completed pool), they can only launch the raven on a 6, even if a 7 or 10 is rolled. If the storm-bird and raven are in play, but the swallow is sent back to the starting pool, the swallow will need to be re-launched before the rooster can be launched.
3. When a player lands a piece on the rosette, they win from the game pool a number of counters equal to the piece’s value. The swallow has a value of 3, the storm-bird, raven, and rooster have a value of 4, and the eagle has a value of 5.
4. If a piece moves over the rosette without landing on it, the player loses a number of counter equal to the piece’s value.
5. Rosette positions are safe; a piece can not be knocked off the position by another piece.

At the end of the game, a player loses a number of counter equal to the sum of value of pieces on the board.

State representation for the standard version

On the original board, a piece moves from the “ready pool” (position 0) through the first four safe positions, then through eight contended spaces, and finally through two safe positions before exiting the board to the “completed pool” (position 15). Thus, a position can be encoded in 4 bits for the 16 potential locations. Since each player has seven pieces, a player’s pieces can be encoded in 7 * 4 bits and both players pieces can be encoded in 2 * 7 * 4 or 56 bits.

Alternatively, we can model the game from the perspective of the squares rather than the pieces. The 14 middle positions (which have a capacity of one) can be modeled in 14 bit and the number of pieces available in the starting pool require 3 bits. (The number of pieces in the ending pool can be calculated based on the difference of the total number of pieces and the number in the starting pool plus on the board.) This requires 17 bits of storage per player or 34 bits total.

Naively, the state space for this board in the first representation allows \(2^{56}=72,057,594,037,927,936\) possible states, or approximately 72 quadrillion. This is a big number (half-way to the age of the Earth in seconds), but this representation also contains many symmetrical games (piece 1 on position 3 and piece 2 on position 6 is identical to piece 1 being on position 6 and piece 2 on position 3) and invalid games (multiple pieces on the same position).

The alternative representation allows for \(2^{34} = 17,179,869,184\) possible states or approximately 17 billion. This representation also contains many invalid games.

Can we compute a more precise value for the number of possible states?

How many possible, valid states for the standard version?

We can approximate the state space by using the “ball and urn” mental framework. We are trying to place pieces (balls) into board positions (urns). Each player has 16 urns (although some are shared) and all but two urns have a maximum capacity of one ball. The player’s pieces are identical to each other but the urns are distinct.

If we simplify the rules and state that all urns have a maximum capacity of one ball, then we can leverage the helpful Twelvefold Way table. (There are multiple versions of this table; I find Cook’s one of the more readable on the web.) The entry for “unlabeled” balls, “labeled” urns, and a maximum capacity of one is equivalent to a n choose k or binomial coefficient calculation.

Table: \(\binom{n}{p}\) Values for \(n=16\) and \(p\) pieces

This is an approximation and includes invalid states where the two players are contesting the same slot while also excluding cases where multiple places may be in the starting and ending pool, but as we shall see, this is a pretty good approximation. (Since combinations are symmetric, e.g. \(\binom{16}{2} = \binom{16}{14}\), the approximation breaks down as \(p\) increases.) Furthermore, these numbers are fairly small, so it seems practical to have a computer iterate (smartly) through the cases as 131 million is far more reasonable than 17 billion.

I wrote a program in Rust that will generate and count all valid states. I use a recursive, depth-first search approach. Each player is modeled via a vector which represents a placement into a labeled urn. Since some positions allow multiple placements we cannot generates states via a standard lexicographic combination algorithm, but do so via a slight modification of the algorithm that will generate duplicate 0 and 15 positions.

Within the search, our base case is a solution being found. Due to the functional design, the two player’s states are valid on entry to the function, so a valid full solution just requires a check that all placements have been made. If so, we pass the solution to a Visitor class that abstracts away what to do for every solution. (The visitor either prints out the solution or increments counts depending on the program’s mode.)

fn search_games_dfs(pieces: usize, visitor: &mut ModalVisitor, p1state: &mut Vec<usize>, p2state: &mut Vec<usize>) {
    if p1state.len() == pieces && p2state.len() == pieces {
        visitor.found(p1state, p2state)
    } else {
        // states are ordered monotonically; if the last move is the starting or ending pool,
        // we can create a new state in the same pool. Otherwise, place in the next potentially
        // valid spot.
        let min_i = match (*p1state).last() {
            Some(0) => 0,
            Some(15) => 15,
            Some(min) => min + 1,
            None => 0
        };
        let min_j = match (*p2state).last() {
            Some(0) => 0,
            Some(15) => 15,
            Some(min) => min + 1,
            None => 0
        };

        for i in min_i..16 {
            p1state.push(i);
            for j in min_j..16 {
                p2state.push(j);
                if is_valid(p1state, p2state) {
                    search_games_dfs(pieces, visitor, p1state, p2state);
                }
                p2state.pop();
            }
            p1state.pop();
        }
    }
}

If we are not at the base case, we either initialize a placement (min_i, min_j) at the zero position (no former placements have been made), try to continue at 0 or 15 (the pools that can handle more than one assignment), or the next entry (since all other urns have a maximum capacity of one and we are searching the space in ascending order).

Then, we attempt all possibilities for player one and player two, verify they are valid (is_valid), and if so recursively check the next depth. The is_valid code verifies that placements are distinct (when necessary) within a player’s placements and distinct within the eight contended squares.

NB: This is not the most efficient representation of the board. If we used the 14-bit representation of the board, we could detect collisions by masking off the first four bits, use the and-bitwise operator and test against zero. Furthermore, the representation does not allow modeling of more than one piece within a position, so the first check in the code can be eliminated entirely.

fn is_valid(player1: &[usize], player2: &[usize]) -> bool {
    // verify each individual player's pieces are unique or in the starting/ending pools
    let mut seen = [false; 16];

    // The placement logic ensures that these constraints are respected, so this code could
    // be skipped when called from search_games_dfs. Skipping this check halves the run-time.
    for player in [player1, player2].iter() {
        for placement in player.iter() {
            match *placement {
                0 => (),
                15 => (),
                place if seen[place] =>
                    return false, // duplicate
                place =>
                    seen[place] = true
            }
        }
        seen.fill(false);  // reset for next player
    }

    for player in [player1, player2].iter() {
        for placement in player.iter() {
            match *placement {
                place if place >= 5 && place <= 12 =>
                    if seen[place] {
                        return false
                    } else {
                        seen[place] = true
                    },
                _ => ()
            }
        }
    }

    return true;
}

Table: Programmatic Count of Valid States with \(p\) pieces

Computations are relatively quick. Finding all 138 million solutions for p=7 took less than three minutes (with the first block of checks in is_valid skipped) on a 2017 “Coffee Lake” Intel i7.

The average branching factor at \(p=7\) is 5.3; this means that on a given ply (move), a player is making a potential decision between 5 different options, although depending on the roll an option may not be possible (e.g. the move is blocked by another piece). The branching factor is computed as the sum of at-most-one move from the starting pool, all moves on the board, and no moves from pieces in the ending pool.

Comparing our earlier approximations and the programmatic counts finds the deltas to be (proportionally) small:

Instead of leveraging a computer, can we count the number of positions using a closed form equation?

Closed form?

Whoever wants to go about generating all partitions not only immerses himself in immense labor, but also must take pains to keep fully attentive, so as not to be grossly deceived.

— Leonhard Euler, De Partitione Numerorum (1750)

A reader has worked out the following closed form equation:

$$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}$$

In the above notation, \(p_i\) are the number of pieces from player i on the board, there are m shared slots on the board and n unshared/uncontested slots.

Alas, I have been unable to find a closed-form solution. As the Euler quote warns, although one can use the inclusion/exclusion method to iterate toward the correct number, it is very easy to forget a case or include some duplicates. Graphically, here are the conflicting states for p=1 to 3 (an index refers to a lexicographically ordered single player’s valid position):

As expected, conflicts are symmetric along the main diagonal. However, there are a number of sub-patterns that I’ve had trouble modeling. I may return to this problem (or some reader may solve it), but at this point a closed form solution is convenient but not necessary.

How big are these numbers?

Not very big, but beyond trivial. Using log-10 notation, the state space size is 8 (or 9 if we round up), which is less than the 10 for Nine men’s morris, 20 for Checkers, and 44 for Chess.

A different measurement for a game is the game tree size; this represents the total number of games that can be played. This differs from the state space because there may be multiple paths to a given state. The game tree size is technically infinite for this game (since on a ply the player may roll a zero or players may constantly return each other’s pieces to the start). In practice, games tend to be quick and thus avoid becoming bogged down.

We can approximate the gate tree size by raising the average branch to the average number of plies in a game, or \(b^{d}\). For an individual ply, a player needs to make a single decision of which piece to move; that decision is shared among all pieces on the board and at most one piece in the starting pool the board (since all pieces in the pool are identical). Through enumeration, we have found the average branch factor as 5.3. I don’t have statistics for the average number of plies, but in uncontested play, you will need on average 8 plies to move a piece to the end (since the mode is 2) and with 7 pieces you could expect 56 plies. If we estimate 70 as the average number of plies per player, that would be 140 total plies. The log10 of \(5.3^{120}\) is 87. In comparison, Checkers is 40 and Chess is 123.

These numbers allow us to compare games against each other, but they do not explain what makes a game fun or engaging. For the ancients, this game had the benefit of low cost of entry (there are example boards etched in the floor), rapid play, and allowing of multiple strategies but with an element of chance. The central squares force interaction between the players while the safe squares allow the readying of “reserve” troops to threaten the other player. These combination of factors, in my view, are what makes the game fun and make the sum better than the parts.

References