Introduction

This game was surprisingly fun to play. Each player starts with three tokens– buttons or coins if you’re playing with kids, or dollar bills or even higher denominations if the adults want to make it more exciting. On each player’s turn, they roll one die for each of their tokens (up to a maximum of three dice rolled):

• If a 1 is rolled, pass the token to the player’s left.
• If a 2 is rolled, put the token in the “pot” in the center of the table.
• If a 3 is rolled, pass the token to the player’s right.
• If a 4, 5, or 6 is rolled, keep the token.

If a player has three or more tokens on their turn, only three dice are rolled. If a player has just one or two tokens, then they roll one or two dice, respectively. Most importantly, if a player has no tokens, they are not out of the game, since they might later receive tokens during a neighboring player’s turn; play simply passes to the next player with at least one token.

Play continues until only one player remains with any tokens. That player wins the game, collecting all of the tokens or bills or whatever, including those in the center pot.

I say “surprisingly fun” because, as was quickly observed during play, this is a “game” of pure chance. There is no skill involved; there are no decisions to be made. All of the token-passing game mechanics are merely a more time-consuming– but fun– way of randomly selecting which player will eventually win the game.

But that random selection isn’t quite uniform. Someone has to be the first player, the first to start risking loss of tokens, while the last player at the table gets to wait and watch. It’s an interesting problem to compute exactly how much effect playing order has on probability of winning.

Analysis results

The following table shows the exact probabilities (to given precision) of winning for each player, along with the expected number of turns to determine a winner, for games from two to seven players. (A turn is a roll of the dice, so that we do not count a turn for skipping a player without any tokens.) The Python code is available on GitHub.

The table layout is the same as this presentation of a Monte Carlo simulation analysis of the game. However, because those simulation results are only estimates, the order statistics indicated by red (lowest probability) and green (highest) are different in some places. For example, with five players, the first player, not the second, has the lowest probability of winning, and the next-to-last player has the greatest advantage.

These are close shaves– certainly close enough not to matter in a game played with children. But if this were a game played for money, then even these small differences in advantage are comparable to, for example, the magnitude of difference between an edge for the house or the player depending on minor variations in the rules for single-deck blackjack.

A sequence of linear systems

There were a few interesting implementation details. As discussed here before, we can compute the above probabilities (or expected values) as the solution of a system of linear equations. There is a variable for each possible game state , where is a -tuple indicating the number of tokens held by each of players, and is an integer indicating which player is to roll for the next turn.

Each variable represents the probability of the first player winning the game (or the expected number of additional turns to complete the game), conditioned on the corresponding current game state . That’s a lot of variables: variables, which for players is already over 8 million variables.

But we don’t have to solve the entire system at once. The number of tokens in play never increases, so we can solve the very small subsystem involving only the game states with just one token in play, then use those cached results to construct and solve the subsystem of game states with two tokens in play, etc.

Ranking and unranking game states

To compute the resulting sparse matrix representing each of these linear systems, it is convenient to perfectly hash the game states to matrix row and column indices. In each game state, the tuple is a weak composition of the total number of tokens remaining among the players (i.e., not in the center pot). Hashing weak compositions of with parts reduces to hashing -subsets of .

In most of the literature this process of perfect hashing from an object– in this case, a subset, or combination– to a consecutive integer index and back is referred to as ranking and unranking. We’ve done this before with permutations; for combinations, ranking is pretty straightforward:

def rank_subset(S, n=None):
    """Return colex rank of k-subset S of {0..n-1}."""
    return sum(math.comb(c, j + 1) for j, c in enumerate(S))

Note that this simple combinadic formula ranks subsets in colexicographic order. Lexicographic order take a bit more work, but in many applications such as this one, we just need an ordering, we don’t really care which one.

Unranking, or converting an integer index back to the corresponding subset, is the interesting subproblem that really motivated this post. Following is the basic guess-and-check algorithm:

def unrank_subset(r, n, k):
    """Return k-subset S of {0..n-1} with colex rank r."""
    S = [0] * k
    while k > 0:
        n = n - 1
        offset = math.comb(n, k)
        if r >= offset:
            r = r - offset
            k = k - 1
            S[k] = n
    return S

Those binomial coefficient calculations can be expensive, depending on the implementation, caching, etc. The following version implements the same basic algorithm, but takes advantage of the fact that the binomial coefficients needed at each iteration are “adjacent,” and thus differ by a simple factor:

def unrank_subset(r, n, k):
    """Return k-subset S of {0..n-1} with colex rank r."""
    S = [0] * k
    offset = math.comb(n, k)
    while k > 0:
        # Decrease n and update offset to comb(n, k).
        offset = offset * (n - k) // n
        n = n - 1
        if r >= offset:
            r = r - offset
            k = k - 1
            S[k] = n
            if k < n:
                offset = offset * (k + 1) // (n - k)
    return S

Finally, the following binary search version is generally worse than either of the above implementations when amortized over unranking of all possible subsets (as is needed in this game analysis), but it’s safer, so to speak, in that it still works in a reasonable amount of time even for astronomically large universal sets, i.e., when .

def unrank_subset(r, n, k):
    """Return k-subset S of {0..n-1} with colex rank r."""
    S = [0] * k
    while k > 0:
        # Use binary search to decrease n until r >= comb(n, k).
        lower = k - 1
        while lower < n:
            mid = (lower + n + 1) // 2
            if r < math.comb(mid, k):
                n = mid - 1
            else:
                lower = mid
        r = r - math.comb(n, k)
        k = k - 1
        S[k] = n
    return S

But after all this, it’s worth acknowledging that none of this is strictly necessary for this particular problem. There is a space-time tradeoff to weigh here, where we could skip the ranking and unranking altogether, and simply pre-compute a dictionary mapping game states to array indices, via enumerate(itertools.combinations(...)) or any other convenient means of generating all states… that in this problem we have to store anyway to cache the probabilities (or expected values).