Game rules

A game is characterized by two parameters:

Number range, later called values or $V$
Number of fields, later called fields or $F$

A game is played by rolling an integer $F$ times. The integer $I$ is sampled without repetition from the range $0 ≤ I < V$. The player has to place the rolled integer $I$ on one of the fields, so that after $F$ rolls all fields contain a value and the values in the fields are increasing. If there is no valid placement that keeps the field values increasing, the game is lost.

Instructions

Gameplay

Select values and fields game properties. Press New Game button. $F$ boxes should appear on your screen, they are sorted by number in top left corner.
Click Roll a number button to get next number to place. If there is no valid placement the game is lost, go to step 1.
Place the number by clicking one of the green boxes. If all fields are occupied the game is won. Otherwise go back to step 2.

Extra

Before each roll, Win probability without roll is displayed. It assumes optimal play by the player. To see how it is computed, see the Solution section.
If the show hints checkbox is set, each valid placement box will display the win probability. The box with the best probability will be light green instead of green.
Change use exponential notation to switch between exponential notation and decimal notation

Solution

Calculating win probability

Let's define the probability of winning the game with optimal play as $Win(V, F)$, where $V$ is the number of possible rolled values and $F$ is the number of fields.

Let's think of the base cases first. If there are no fields to place values on, the game is won. Thus: $$Win(V,0)=1$$ If there are more fields than values to choose from, we can't win the game since the values are drawn without repetition. $$Win(a,b)=0 \text{ if } a < b$$

Let $Roll(V, F, r)$ be the probability of winning the game with $V$ values and $F$ fields, having rolled $r$. Since the roll is uniform we get: $$Win(V, F) = \dfrac{1}{V} \sum_{r=0}^{V-1} Roll(V, F, r)$$

So what is $Roll(V, F, r)$? The player has to choose a field $f$ to place it on. Let $Place(V, F, r, f)$ be the probability of winning the game with initial parameters $V, F$, having rolled $r$ and placing it on field $f$. Assuming optimal play, the player chooses the optimal field, resulting in the formula: $$Roll(V, F, r) = \max_{f=0}^{F-1} Place(V, F, r, f)$$

How do we calculate $Place(V, F, r, f)$? After placing $r$ on field $f$, we are left with two sets of contiguous fields: lower $0\ldots f-1$ and upper $f+1\ldots F-1$. The lower set must be filled with values from the range $0\ldots r-1$, and the upper from the range $r+1\ldots V-1$. Thus $Place(V, F, r, f)$ is the probability that of the remaining $F-1$ rolls, $f$ end up in the lower fields and $F-f-1$ in the upper fields, multiplied by the probability of solving the lower and upper subproblems. The lower subproblem is exactly $Win(r,f)$ and the upper is $Win(V-r-1,F-f-1)$. What is the probability that future rolls will be correctly split between lower and upper fields? We calculate the number of ways it could occur and divide by all ways it could be distributed. With $V-1$ values remaining and $F-1$ rolls to do (without repetition), there are $\binom{V-1}{F-1}$ possible sets of rolls. For the correct split, we need $f$ rolls from $r$ numbers in the lower fields and $F-f-1$ rolls from $V-r-1$ numbers in the upper fields. The number of ways this can happen is $\binom{r}{f}\binom{V-r-1}{F-f-1}$. Thus: $$Place(V, F, r, f) = \dfrac{\binom{r}{f}\binom{V-r-1}{F-f-1}}{\binom{V-1}{F-1}}Win(r,f)Win(V-r-1,F-f-1)$$

With these equations we have defined $Win(V,F)$ in terms of $Win(a,b)$ where $a < V \text{ and } b < F$. This gives us a simple divide-and-conquer solution using dynamic programming, i.e. storing intermediate results of $Win$.

Time complexity

When calculating $Win(V,F)$ we will have to calculate $Win(a,b), a \leq V \text{ and } b \leq F$ at most once since we are storing the result. Thus $Win$ will be calculated $O(V F)$ times.

Each calculation of $Win(a,b)$ iterates over $a$ rolls and for each roll calculates $b$ placements. We also need to compute binomials; let's call this $A$ arithmetic operations. Thus the time complexity of a single $Win$ is $O(V F A)$.

This yields a total time complexity of $O(V^2F^2A)$.

Optimization

Let's assume that $f$ is the optimal placement for $Roll(V, F, r)$. We can observe that the optimal placement for $Roll(V, F, r+1)$ is in $\{f,f+1\}$. I will leave the proof as an exercise to the reader. :)

With this optimization, each calculation of $Win$ no longer needs to iterate over all fields, bringing the total time complexity down to $O(V^2FA)$.

Now we can calculate the result. I chose python in my implementation as it supports big integers and has math.comb for fast binomial calculation. $Win(1000, 20)$ computes in 12 seconds which is a reasonable result.

Win probability from any state

So far we are able to calculate the probability from the starting state. With a bit of effort we can also determine the optimal placement given any roll. Having rolled a number $r$, we look for the gap it belongs to. A gap is a maximal set of contiguous unassigned fields. Let $V_G$ be the number of values that could be assigned to a gap and $F_G$ be the number of fields in that gap. The optimal choice given any state is computed by finding the gap that the roll belongs to and basing placement on $Win(V_G,F_G)$.

Computing the probability from any state is done similarly to computing $Place(V, F, r, f)$, except now there may be many gaps instead of just 2. Suppose the game has parameters $V, F$. Let $D$ be the number of rolls completed and $G_1\ldots G_n$ be the non-empty gaps. The probability of winning is the probability of future rolls fitting into the gaps multiplied by the probability of winning each gap. This yields the formula: $$State(V,F,D,G_1\ldots G_n) = \dfrac{\binom{V_{G_1}}{F_{G_1}}\cdots\binom{V_{G_n}}{F_{G_n}}}{\binom{V-D}{F-D}}Win(V_{G_1},F_{G_1})\cdots Win(V_{G_n},F_{G_n})$$