4
$\begingroup$

I've been playing with my son a simple board game where you roll a regular 6 faced die and move as many positions as you roll.
So nothing fancy, just pure luck game.
Lately I've been trying to teach him that is not OK for him to always go first. It's not fair. Then he asked me a good question. "WHY?".
The answer is obvious, because you get a better chance of reaching the end of the board first. You may have an extra roll to reach the end of the board.
But I would like to see some numbers / probabilities. Not to explain my son, but for my inner peace.

So my question is: Is there a formula that shows the chances of winning if you go first depending on the board length?

For simplicity, let's say that there are 2 players only and the traps and bonuses from the board are ignored.

I tried an incremental approach.

  • board has the length 1 => Player 1 always wins.
  • board has the length 2 => Player 2 wins only if P1 rolls a 1 and P2 rolls 2 or more so P2 wins with a probability of $\frac{1}{6} \times \frac{5}{6} = \frac{5}{36}$ and P1 with a probability of $\frac{31}{36}$.
  • board has the lenght of 3 => I got lost in the math and my head hurts.

Just for the record, my board has the length of 45.
It seams logical that the bigger the board the closer the chances get to $\frac{1}{2}$ for each player. But is there a formula?

$\endgroup$

2 Answers 2

3
$\begingroup$

I am not sure about your rules, but the games I play have rule that if the first-moving player reaches the end, she wins only if the other second-moving player does not reach the end in the subsequent move. Otherwise, the players tie.

Anyway, your question is related to the expected number of rolling a dice needed to reach certain sum. The questions have been discussed here, here, here, here and since it is a hard problem, approximation with normal distribution discussed here can help. This is a nice article on the topic.

On average (for many rolls), with $6$-sided die, you would expect the first-moving player to be $3.5$ moves ahead of the second-moving player after the first-moving player has moved. That is, on average, you would expect the first-moving player to win, but this is the intuition you had already.

Update 1: Computation is certainly possible. I got interested in how the advantage changes with the cut-off required for victory, $w_{c}$. The following is a Matlab function that estimates the advantage via simulation.

enter image description here

Plotting the advantage over $w_{c}$ ranging from $1$ to $100$ gives this.

enter image description here

Update 2: You can think about this problem via states. Let $(x,y)$ be a state, where $x,y\in\{0,\ldots,w_{c}-1\}$, which captures the state in which player 1 is about to move and in all previous rounds player $1$ accumulated $x$ on her dice and player $2$ accumulated $y$ on her dice. Let me also define states where $x\geq w_{c}$ to have value of $1$ and states where $x<w_{c}$ and $y\geq w_{c}$ to have value of $0$. The former states are those in which player $1$ has already won and the latter states are those in which player $2$ has already won.

Now value of a state $(x,y)$ is a probability of player $1$ winning the game. One can calculate values of states recursively since given $(x,y)$, the roll of a dice by player $1$ and then by player $2$ induces a uniform distribution over states $(x+i,y+j)$, where $i,j\in\{1,\ldots,6\}$. That is, value of state $(x,y)$, $v_{xy}$, is $v_{xy}=\sum_{i\in\{1,\ldots,6\},j\in\{1,\ldots,6\}}\frac{1}{36}v_{(x+i)(y+j)}$. Following code implements this idea and replicates the plot above, albeit in a smoother fashion. (The non-monotonicity below $10$ is still there.)

enter image description here

$\endgroup$
1
  • $\begingroup$ Thanks for the links. Just for the record, the rule we use is simple. The first to reach the end wins. There cannot be a tie. $\endgroup$
    – Marius
    Jan 26, 2017 at 12:04
2
$\begingroup$

Let total length of a board be $M$, let probability of reaching the end within $n$ rolls be $p_{M,n}$. Obviously, for $M>6$ $p_{M,n} = {1 \over 6}(p_{M-1,n-1}+p_{M-2, n-1}+...+p_{M-6, n-1})$. Formally stating $p_{M,n}=1 | M \le 0$ makes this expression universal. Also, obviously $p_{M,n} = 1 | n \ge M$

Probability of reaching the end in exactly $n$ turns is $p_{M,n} - p_{M,n-1}$. Probability of winning when going first is sum of probabilities to win in 1, 2 and so on turns: $$F =p_{M,1} + (1-p_{M,1})(p_{M,2} - p_{M,1}) + ... + (1-p_{M,M-1})(p_{M,M}-p_{M,M-1}) = \\ p_{M,1}^2-p_{M,1}p_{M,2}+p_{M,2}^2-p_{M,2}p_{M,3}+...+p_{M,M-1}^2-p_{M,M-1}p_{M,M}+p_{M,M}$$ When going second: $$S = (1-p_{M,1})p_{M,1} + (1-p_{M,2})(p_{M,2} - p_{M,1}) + ... + (1-p_{M,M-1})(p_{M,M-1}-p_{M,M-2}) = \\ -p_{M,1}^2+p_{M,1}p_{M,2}-p_{M,2}^2+p_{M,2}p_{M,3}+...+p_{M,M-2}p_{M,M-1}-p_{M,M-1}^2 + p_{M,M-1}$$ Easy to check $F+S = 1$ and "advantage" $F-S$ is $$p_{M,1}^2 + (p_{M,2}-p_{M,1})^2 + ... + (p_{M,M}-p_{M,M-1})^2$$, sum of squares of probabilities to win on any given turn. Directly computing it is possible (C#):

    const int size = 45;
    static double[,] mem = new double[size+1, size+1];

    static double p(int M, int n)
    {
        if (n >= M || M <= 0) return 1;
        else if (n <= 0) return 0;

        if (mem[M, n] != -1) return mem[M, n];
        double ret;
        if (n == 1) ret = M > 6 ? 0 : (7 - M) / 6.0;
        else ret = (p(M - 1, n - 1) + p(M - 2, n - 1) + p(M - 3, n - 1) + p(M - 4, n - 1) + p(M - 5, n - 1) + p(M - 6, n - 1)) / 6.0;
        return mem[M, n] = ret;
    }

    static void Main(string[] args)
    {
        for (int i = 0; i < size+1; ++i) for (int j = 0; j < size+1; ++j) mem[i, j] = -1;
        double result = 0.0;

        for (int n = 1; n <= size; ++n) result += (p(size, n) - p(size, n - 1)) * (p(size, n) - p(size, n - 1));

        Console.WriteLine(result);
    }

, giving ~$0.16$, or chances 58:42 for first and second participants. This gradually gets lower with field size increase: ~$0.108$ for $M=100$, ~$0.034$ for $M=1000$. Since majority of games are concluded within three sigma of average $M / 3.5$ rolls, I would expect first turn advantage to be approximately proportional to the $\sqrt{1 \over M}$.

$\endgroup$
1
  • $\begingroup$ This looks like what I need, and it matches my suspicions. I need to double check the math, because I got lost in it at one point. And I will translate the code into some language that I'm more familiar with and get back to you. Thanks for taking the time. $\endgroup$
    – Marius
    Jan 26, 2017 at 13:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .