Problem 61068. Average Number of Moves for the Royal Game of Err

Bored of tedious court assemblies, King Neduchadneddar the Procrastinator has found a cunning way to keep his advisors, councilors, viziers, and other courtly lackeys busy: he plays a simple and pointless board game with them.
Players move their pawn along a path of n squares, starting at square 1, with the goal of being the first to reach square n. On each turn, they roll an m-sided die to determine how many squares to move. However, if their move would take them beyond the nth square, they stay put. Also, players cannot land on any of the numbers that King Neduchadneddar has decided are the unlucky numbers of the day. If their move would land them on any of these squares, they stay put instead.
To keep his courtiers on their toes (so they have less time to plot his downfall), the king changes the number of squares (n), the number of sides of the die (m), and the list of unlucky forbidden squares each day.
Needing to know how much time he will waste with each game, the king in his wisdom (and/or insanity) has appointed you Chief Royal Mage of Matrix Computations and tasked you with determining the average number of moves it will take a player to complete a game according to today’s setup.
You can use the transition matrix for the game to do this. The transition matrix T is an n-by-n matrix where T(j,k) is the probability of moving from square j to square k in one move. Then gives the probability of moving from from square j to square k in m moves (where is a matrix power; that is, , using standard matrix multiplication).
is the probability of moving from square 1 to square n in m moves. That is, it is the probability of completing the game in m moves. However, once you reach square n you stay there forever. (In practice, the game would end at this point.) Therefore, increases monotonically towards 1 as m increases, and can be interpreted as the cumulative probability of completing the game in m moves. Or, in other words, the probability of completing the game in m moves or fewer.
This is convenient because there's a result in probability theory that allows you to calculate the expected value of m (that is, the average number of moves to complete the game) from the cumulative probability. Skipping the math details, the punchline is:
An infinite sum may not seem helpful, but remember that increases monotonically towards 1, which means the terms in the sum go to zero. Therefore, in practice, you can find the average number of moves to complete the game by summing until the terms are too small to make any practical difference.
Given a transition matrix T, return the average number of moves , accurate to 3 decimal places.
Example
With n = 8 and m = 3, and square 5 forbidden, the transition matrix is:
T = [0 1/3 1/3 1/3 0 0 0 0
0 1/3 1/3 1/3 0 0 0 0
0 0 1/3 1/3 0 1/3 0 0
0 0 0 1/3 0 1/3 1/3 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1/3 1/3 1/3
0 0 0 0 0 0 2/3 1/3
0 0 0 0 0 0 0 1];
avgm = avgmoves(T)
avgm =
6.3750
An inexact way to verify the result is to directly simulate playing the game many times:
function avgm = simulategame(n,m,nogo,nexp)
mv = zeros(nexp,1);
for g = 1:nexp
% Start game at 1
s = 1;
% Go until we reach the nth square
while (s < n)
% Roll die and see where we would land
snext = s + randi(m);
if (snext <= n) && ~any(snext == nogo)
% Move only if valid
s = snext;
end
% Increment number of moves for this game
mv(g) = mv(g) + 1;
end
% Go to the next game
end
avgm = mean(mv);
end
n = 8;
m = 3;
nogo = 5;
avgmsim = simulategame(n,m,nogo,1e4)
avgmsim =
6.3626
This approach would require too many simulations to be accurate to the required precision, but gives rough verification that the game takes 6.375 moves on average.
For n = 16, m = 5, and the forbidden squares are 4, 6, 10, 11, and 15, the transition matrix is:
idx = [1;17;18;33;34;35;65;66;67;69;98;99;101;103;115;117;119;120;133;135;136;137;183;184;185;188;200;201;204;205;217;220;221;222;252;253;254;256];
Tvals = [0.4;0.2;0.4;0.2;0.2;0.4;0.2;0.2;0.2;0.4;0.2;0.2;0.2;0.4;0.2;0.2;0.2;0.4;0.2;0.2;0.2;0.4;0.2;0.2;0.2;0.4;0.2;0.2;0.2;0.6;0.2;0.2;0.2;0.8;0.2;0.2;0.2;1];
T = zeros(16);
T(idx) = Tvals
T =
0.4000 0.2000 0.2000 0 0.2000 0 0 0 0 0 0 0 0 0 0 0
0 0.4000 0.2000 0 0.2000 0 0.2000 0 0 0 0 0 0 0 0 0
0 0 0.4000 0 0.2000 0 0.2000 0.2000 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0.4000 0 0.2000 0.2000 0.2000 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0.4000 0.2000 0.2000 0 0 0.2000 0 0 0 0
0 0 0 0 0 0 0 0.4000 0.2000 0 0 0.2000 0.2000 0 0 0
0 0 0 0 0 0 0 0 0.4000 0 0 0.2000 0.2000 0.2000 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0.4000 0.2000 0.2000 0 0.2000
0 0 0 0 0 0 0 0 0 0 0 0 0.6000 0.2000 0 0.2000
0 0 0 0 0 0 0 0 0 0 0 0 0 0.8000 0 0.2000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.0000
Computing the average number of moves from the transition matrix and from simulation:
avgm = avgmoves(T)
avgm =
11.4015
avgmsim = simulategame(16,5,[4 6 10 11 15],1e4)
avgmsim =
11.4266
Assumptions
The input will be a valid transition matrix for a game with n > m ≥ 2. The output should be a double-precision scalar that has the average number of moves, accurate to at least 0.001.
Solve

Solution Stats

50.94% Correct | 49.06% Incorrect
Last Solution submitted on Nov 11, 2025

Solution Comments

Show comments

Problem Recent Solvers21

Suggested Problems

More from this Author33

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!