forked from johannesgerer/jburkardt-cpp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsnakes_and_ladders.html
261 lines (223 loc) · 7.45 KB
/
snakes_and_ladders.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
<html>
<head>
<title>
SNAKES_AND_LADDERS - Game Simulation
</title>
</head>
<body bgcolor="#eeeeee" link="#cc0000" alink="#ff3300" vlink="#000055">
<h1 align = "center">
SNAKES_AND_LADDERS <br> Game Simulation
</h1>
<hr>
<p>
<b>SNAKES_AND_LADDERS</b>,
C++ programs which
investigate the game of Snakes and Ladders.
</p>
<p>
Snakes and Ladders is a children's game played on a 10x10 numbered
board. A player's turn consists of rolling a single die, and moving
the indicated number of squares. If the final square is the foot of
a ladder, the player moves up to a higher numbered square. If the
final square is the mouth of a snake, the player moves downward.
</p>
<p>
It is a simple exercise to create a simulation of the game for
several players.
</p>
<p>
Since the game is essentially a race, with no other competition between
the players, it can be studied in a simplified version in which there
is only one player.
</p>
<p>
For the one-player version of the game, it is interesting to pose the
question of the average length of a game, that is, how many rolls of
the die it takes in order to reach the final square.
</p>
<p>
By adding a square 0, where the player begins, the game board can
be modeled as a vector of length 101, and the transitions from one
square to another can be modeled by a transition matrix. Most commonly,
the entries in row I will be zero except that columns I+1 through
I+6 will have the value 1/6. However, rows which correspond to a
snake or ladder, and rows for which I+6 is greater than 100, must
be handled specially.
</p>
<p>
Given the transition matrix A, the one player game can be modeled as
a Markov Chain Monte Carlo system. In particular, given an initial
starting vector v, the probability distribution after one move is
the vector A' * v, and repeated multiplication by A' will display
the exact probability distribution at every step.
</p>
<h3 align = "center">
Licensing:
</h3>
<p>
The computer code and data files made available on this web page
are distributed under
<a href = "../../txt/gnu_lgpl.txt">the GNU LGPL license.</a>
</p>
<h3 align = "center">
Languages:
</h3>
<p>
<b>SNAKES_AND_LADDERS</b> is available in
<a href = "../../c_src/snakes_and_ladders/snakes_and_ladders.html">a C version</a> and
<a href = "../../cpp_src/snakes_and_ladders/snakes_and_ladders.html">a C++ version</a> and
<a href = "../../f77_src/snakes_and_ladders/snakes_and_ladders.html">a FORTRAN77 version</a> and
<a href = "../../f_src/snakes_and_ladders/snakes_and_ladders.html">a FORTRAN90 version</a> and
<a href = "../../m_src/snakes_and_ladders/snakes_and_ladders.html">a MATLAB version</a> and
<a href = "../../py_src/snakes_and_ladders/snakes_and_ladders.html">a Python version</a>.
</p>
<h3 align = "center">
Related Data and Programs:
</h3>
<p>
<a href = "../../cpp_src/duel_simulation/duel_simulation.html">
DUEL_SIMULATION</a>,
a C++ program which
simulates N repetitions of a duel between two players, each of
whom has a known firing accuracy.
</p>
<p>
<a href = "../../cpp_src/fair_dice_simulation/fair_dice_simulation.html">
FAIR_DICE_SIMULATION</a>,
a C++ program which
simulates N tosses of 2 dice, making a histogram of the results.
</p>
<p>
<a href = "../../cpp_src/high_card_simulation/high_card_simulation.html">
HIGH_CARD_SIMULATION</a>,
a C++ program which
simulates a situation in which you see the cards in a deck one by one,
and must select the one you think is the highest and stop.
</p>
<p>
<a href = "../../cpp_src/ising_2d_simulation/ising_2d_simulation.html">
ISING_2D_SIMULATION</a>,
a C++ program which
carries out a Monte Carlo simulation of an Ising model,
a 2D array of positive and negative charges,
each of which is likely to flip to be in agreement with neighbors.
</p>
<p>
<a href = "../../cpp_src/poisson_simulation/poisson_simulation.html">
POISSON_SIMULATION</a>,
a C++ library which
simulates a Poisson process in which events randomly occur with an
average waiting time of Lambda.
</p>
<p>
<a href = "../../cpp_src/reactor_simulation/reactor_simulation.html">
REACTOR_SIMULATION</a>,
a C++ program which
is a simple Monte Carlo simulation of the shielding effect of a slab
of a certain thickness in front of a neutron source. This program was
provided as an example with the book "Numerical Methods and Software."
</p>
<h3 align = "center">
Reference:
</h3>
<p>
<ol>
<li>
Steve Althoen, Larry King, Kenneth Schilling,<br>
How long is a game of Snakes and Ladders?,<br>
The Mathematical Gazette,<br>
Volume 77, Number 478, March 1993, pages 71-76.
</li>
<li>
Nick Berry,<br>
A Mathematical Analysis of Snakes and Ladders,<br>
http://www.datagenetics.com/blog/november12011/index.html
</li>
<li>
Desmond Higham, Nicholas Higham,<br>
MATLAB Guide,<br>
SIAM, 2005,<br>
ISBN13: 9780898717891.
</li>
</ol>
</p>
<h3 align = "center">
Source Code:
</h3>
<p>
<ul>
<li>
<a href = "snakes.cpp">snakes.cpp</a>, the source code.
</li>
<li>
<a href = "snakes.hpp">snakes.hpp</a>, the include file.
</li>
<li>
<a href = "snakes.sh">snakes.sh</a>,
BASH commands to compile the source code.
</li>
</ul>
</p>
<h3 align = "center">
Examples and Tests:
</h3>
<p>
<ul>
<li>
<a href = "snakes_prb.cpp">snakes_prb.cpp</a>,
a sample calling program.
</li>
<li>
<a href = "snakes_prb.sh">snakes_prb.sh</a>,
BASH commands to compile and run the sample program.
</li>
<li>
<a href = "snakes_prb_output.txt">snakes_prb_output.txt</a>,
the output file.
</li>
</ul>
</p>
<p>
Some graphics files are created.
<ul>
<li>
<a href = "snakes_commands.txt">snakes_commands.txt</a>,
GNUPLOT command file.
</li>
<li>
<a href = "snakes_data.txt">snakes_data.txt</a>,
GNUPLOT data file.
</li>
<li>
<a href = "snakes.png">snakes.png</a>,
a PNG image of the sparsity structure of the transition matrix.
</li>
</ul>
</p>
<h3 align = "center">
List of Routines:
</h3>
<p>
<ul>
<li>
<b>SNAKES</b> sets up the Snakes and Ladders matrix.
</li>
<li>
<b>SPY_GE</b> plots a sparsity pattern for a general storage (GE) matrix.
</li>
<li>
<b>TIMESTAMP</b> prints the current YMDHMS date as a time stamp.
</li>
</ul>
</p>
<p>
You can go up one level to <a href = "../cpp_src.html">
the C++ source codes</a>.
</p>
<hr>
<i>
Last modified on 19 September 2014
</i>
<!-- John Burkardt -->
</body>
</html>