The Game of Ur problem

The Game of Ur problem

Here’s a probability puzzle to ruin your week.

In the Royal Game of Ur, players advance tokens along a track with 14 spaces. To determine how many spaces to advance, a player rolls 4 dice with 4 sides. Two corners on each die are marked; the other two are not. The total number of marked corners — which is 0, 1, 2, 3, or 4 — is the number of spaces to advance.

For example, if the total on your first roll is 2, you could advance a token to space 2. If you roll a 3 on the next roll, you could advance the same token to space 5.

Suppose you have a token on space 13. How many rolls did it take to get there?

Hint: you might want to start by computing the distribution of k given n, where k is the number of the space and n is the number of rolls.  Then think about the prior distribution of n.

I’ll post a solution later this week, but I have to confess: I believe my solution is correct, but there is still part of it I am not satisfied with.

[UPDATE November 1, 2018]

Here’s the thread on Twitter where a few people discuss this problem.

And here’s my solution.  As you will see there are still some unresolved questions.

Here’s another solution from Austin Rochford, which estimates the posterior distribution by simulation.

And here’s a solution from vlad, also based on simulation, using WebPPL:

6 thoughts on “The Game of Ur problem”

  1. In webppl (if I’ve understood correctly):

    var rollUntil = function(sofar,limit) {
    if (sum(sofar) >= limit) {
    return sofar;
    }
    else {
    return rollUntil(sofar.concat([uniformDraw([0,1,2,3,4])]), limit)
    }
    }

    var d = function() {
    var rolls = rollUntil([],13)

    condition(sum(rolls) == 13)

    return rolls.length;
    }

    viz(Infer(d))

  2. Let f(n) = (4n choose 13) / 2^(4n), for n >= 4, and 0 for n <4
    Let s = sum of f(n) from 4 to infinity
    Prob of number of rolls being n = [16f(n) – f(n-1)]/ 15s

    Is that right?

    Finding the distribution by getting the sum from 4 to 20, I get:
    4 | 0.018229
    5 | 0.156576
    6 | 0.307546
    7 | 0.277728
    8 | 0.153945
    9 | 0.060953
    10 | 0.018864

  3. Here’s my code in WebPPL:
    var roll = function() {
    return flip() + flip() + flip() + flip();
    }

    var game = function() {
    var n = sample(RandomInteger({n: 20}));
    var s = sum(repeat(n, roll))
    condition(s === 13);
    return n
    }

    var dist = Infer(game);
    viz(dist);

  4. If we knew that the last roll was not a zero, it would be unambiguous.

    However, you can always have any number or zero rolls added on to a sequence of rolls and still get the same sum. There is no principle that would tell us whether 4,4,4,1 or 4,4,4,1,0 or 4,4,4,1,0,0 is more probable. We can know the probability ratios among roll sequences of the same length, however comparing probabilities among sequences of different lengths would require using some subjective Bayesian prior, whose choice does not follow from the problem statement.

    Or to be more precise, the problem is not with the difference in length, but with one sequence being a prefix of another.

    If we know that the last roll was not a zero, then we can implicitly aggregate over “all possible futures”, since no possible valid roll sequence is a prefix of another. In such a case there is an objective “signal for observation”, i.e. when the sum becomes 13. If adding on several zeros to the end is allowed, then there is no objective “rule” that would tell us when the observation would happen.

Comments are closed.

Comments are closed.