function a = snakes_matrix ( )
%*****************************************************************************80
%
%% snakes_matrix() sets up the Snakes and Ladders transition matrix.
%
% Discussion:
%
% Snakes and Ladders, also known as Chutes and Ladders, is a game
% played on a 10x10 board of 100 squares. A player can be said to
% start at square 0, that is, off the board. The player repeatedly
% rolls a die, and advances between 1 and 6 steps accordingly.
% The game is won when the player reaches square 100. In some versions,
% the player must reach 100 by exact die count, forfeiting the move
% if 100 is exceeded; in others, reaching or exceeding 100 counts as
% a win.
%
% Play is complicated by the existence of snakes and ladders. On
% landing on a square that begins a snake or ladder, the player is
% immediately tranported to another square, which will be lower for
% a snake, or higher for a ladder.
%
% Typically, several players play, alternating turns.
%
% Given a vector V(0:100) which is initially all zero except for the
% first entry, the matrix-vector product A'*V represents the probabilities
% that a player starting on square 0 will be on any given square after one
% roll. Correspondingly, (A')^2*V considers two moves, and so on. Thus,
% repeatedly multiplying by A' reveals the probability distribution
% associated with the likelihood of occupying any particular square at a
% given turn in the game.
%
% There is a single eigenvalue of value 1, whose corresponding eigenvector
% is all zero except for a final entry of 1, representing a player who
% has reached square 100. All other eigenvalues have norm less than 1,
% corresponding to the fact that there are no other long term steady
% states or cycles in the game.
%
% Note that no two descriptions of the Snakes and Ladders board seem to
% agree. This is the board described by Nick Berry. The board described
% by Higham and Higham is close to this one, but differs in the description
% of two of the jumps.
%
% While most commentators elect to move immediately from a snake mouth or
% ladder foot, I have decided there are reasons to treat the game in such a
% way that when you land on a ladder foot or snake mouth, you stay there
% as though you had landed on an ordinary square; the difference arises on
% your next turn, when, instead of rolling a die, you move up the ladder
% or down the snake. This allows the player to "register" a stop at the
% given square, may be suitable for certain applications, and makes for
% a transition matrix whose structure is more obvious to understand.
%
% Licensing:
%
% This code is distributed under the MIT license.
%
% Modified:
%
% 16 September 2014
%
% Author:
%
% John Burkardt
%
% Reference:
%
% Steve Althoen, Larry King, Kenneth Schilling,
% How long is a game of Snakes and Ladders?,
% The Mathematical Gazette,
% Volume 77, Number 478, March 1993, pages 71-76.
%
% Nick Berry,
% Mathematical Analysis of Chutes and Ladders,
% http://www.datagenetics.com/blog/november12011/index.html
%
% Desmond Higham, Nicholas Higham,
% MATLAB Guide,
% SIAM, 2005,
% ISBN13: 9780898717891.
%
% Output:
%
% real A(0:100,0:100), the matrix.
%
o = 1;
for i = 0 : 100
jump(i+o) = i;
end
jump( 1+o) = 38;
jump( 4+o) = 14;
jump( 9+o) = 31;
jump(16+o) = 6;
jump(21+o) = 42;
jump(28+o) = 84;
jump(36+o) = 44;
jump(48+o) = 26;
jump(49+o) = 11;
jump(51+o) = 67;
jump(56+o) = 53;
jump(62+o) = 19;
jump(64+o) = 60;
jump(71+o) = 91;
jump(80+o) = 100;
jump(87+o) = 24;
jump(93+o) = 73;
jump(95+o) = 75;
jump(98+o) = 78;
a(0+o:100+o,0+o:100+o) = 0.0;
%
% A(I,J) represents the probability that a dice roll will take you from
% square I to square J.
%
% Starting in square I...
%
for i = 0 : 100
%
% If I is a snake or ladder, go to the next spot.
%
if ( i ~= jump(i+o) )
j = jump(i+o);
a(i+o,j+o) = 1.0;
%
% Otherwise, roll a die
%
else
for d = 1 : 6
%
% so theoretically, our new location J will be I + D,
%
j = i + d;
%
% but if J is greater than 100, move us back to J,
%
if ( 100 < j )
j = 100;
end
a(i+o,j+o) = a(i+o,j+o) + 1.0 / 6.0;
end
end
end
return
end