I invented a game, and it goes like this. We’re going to pick a 20 digit number by taking turns choosing each digit. I choose the first digit, then you choose the second digit, I choose the third and so on. Once we’ve chosen all the digits, we use our number as the seed to a random number generator. The random number generator picks a number between 0 and 1, and if the number is greater than 0.5 then I win; if it’s less than 0.5 then you win.

Obviously this isn’t meant to be a “fun” game, it’s more of an open-ended math problem. What’s the strategy? Is there a strategy? Who wins?

The idea behind the random number generator, is that it’s deterministic, and yet opaque. Given any particular seed, the random number generator will consistently pick the same result—either you win, or I do. But there’s no particular pattern to it. It behaves as if the result were randomly chosen. The only way to predict the game’s outcome is to individually plug in each random seed into the random number generator. However, this might be intractable, as there are 10^20 possible seeds.

This game is deterministic, finite, and perfect information—much like Chess. However, it appears that the only real strategy is brute force, by plugging in seeds into the random number generator.

Who wins?

Nonetheless, we know with near certainty who will win. The last player wins. That’s because on the last turn, you have ten options. You can just plug in each of the ten options into the random number generator to see which one wins. It’s very likely (99.9%) that at least one of your options wins, so you just pick that one.

On the other hand, there are still the 0.1% of cases where the last player loses. If the second-to-last player looks ahead two moves, they might be able to engineer the situation. They have 10 options, and if each option has 0.1% chance of winning, then there’s about 1% chance that the second-to-last player has a winning move.

And then what happens when the players look 3 moves ahead? 4 moves ahead?

A mathematical solution

Let’s define the quantity p_i, the probability that the first player will win when the game is i turns long. This is assuming perfect ability to look infinite number of turns into the future.

Let’s also define the number N, which is the number of digits that you can choose from. We were initially thinking about N=10, since there are ten digits 0-9, but we might want to change N later on.

Another rule in my initial statement of the game, was that you would win if the generated random number was greater than 0.5. Let’s turn this into a variable. The last player wins if the random number generator produces a number greater than x.

So suppose we have a game with i turns. The first player looks at their N available options, and each option is equivalent to an (i-1)-turn game where the second player goes first. For each of the available (i-1)-turn games, the second player wins with probability p_i-1 (and these probabilities are assumed to be independent). The first player can win if they can choose a move that causes the second player to lose. So we can calculate the probability p_i in terms of the probability p_i-1. The equation looks like this:

p_i = 1 – (p_i-1)^N

If you think about the 1-turn game, you will find that

p₁ = 1 – x^N

So it is convenient to define p₀ = x.

I don’t have an explicit formula for the probabilities, but it’s easy to input the iterative expression into a spreadsheet. For N = 10 and x = 0.5, here are the first several probabilities:

p₀ = 0.5
p₁ = 0.999023438…
p₂ = 0.009722821…
p₃ = 0.999999999999999999992…
p₄ ~ 7*10^-20

This follows our intuition that the last player nearly certainly wins. And it gets worse the longer the game is. However, you can level the playing ground by increasing x or by decreasing N. I found that if you let N=2 and x=(sqrt(5)-1)/2, then neither player clearly comes out ahead no matter how long the game.

Imperfect information

Obviously, in practice the players can’t look an infinite number of moves ahead. So we can consider the case where players can only look M moves ahead. If there are more than M turns left, then the players can do no better than choose randomly. So the first turn of the game that actually matters is when there are M turns remaining. At that point, the current player will have p_M probability of winning.

What happens when one player can look more turns into the future than can the other player?

Here’s another scenario. What if each player can check 100 random numbers per turn? So when there are two turns left (with N=10), they can look ahead all the way to the end. But when there are 3 turns left, they can only see 10% of the possible outcomes. There must be a way to sample outcomes to maximize the probability of winning.

Unfortunately I’m going to leave these questions as exercises to the reader. I think they’re solvable problems, it just might take longer than I’m willing to write out.

Discussion

I’m mostly interested in this game as a pure math problem. However, I do think it’s worth pointing out that this is a game that doesn’t really involve any chance, since we’re using a deterministic random number generator. And yet, the best way to analyze the game is in terms of probabilities. The probabilities don’t really represent chance, but rather they represent our lack of knowledge of the behavior of the random number generator.

In a way, it’s rather analogous to chess. Although Chess is deterministic, we lack knowledge about the gamestate 10 moves in advance. In a sense, Chess is not just a game of skill, but also a game of luck.

But unlike Chess, I wouldn’t say the Random Number Game is a game of skill at all. In Chess, I think you can look at a board and tell whether it’s a good position for white or black. In the Random Number Game, there really isn’t any way to tell who’s winning until there are only a few turns left.