There are 3 steps
required to calculate the statistics given in the tables and
illustrated in the graphs.
1) For each board space, run an exhaustive tree search
of all possible Monopoly moves (including consequences of
doubles, Chance, Community Chest, Go to Jail, etc.). For each
possible path that starts on a given board space and ends on
another board space (including returning to where you started
 possibly for more than 1 visit), you will calculate the
probability of this particular path. Since there are many
different combinations that start at each board space and end
at another (or even the same) location, you will have to form
cumulative totals. The output of this will be a 2dimensional,
state to
state (board space to board space) transition matrix
that shows the probability of starting your turn on any of the
board spaces ending your turn on any board space.
2) The
state to
state transition matrix forms a Markov Chain (Markov
Matrix). When we solve this we will get the steady state
probability of residing in each possible state. (In Monopoly
this is the probability your game piece (token) will be on any
particular board space (or any of the three possible "In Jail"
states) at the end of your turn.)
3) For each board space (Markov Chain state), run
another exhaustive tree search. For each board space that you
visit, calculate the probability of this visit path and add
this amount to the cumulative totals that you are keeping for
all board spaces.
It's "just possible" the above sounds a little
complicated. Thus, we will look at a simple example of each
step, and then see how to expand this to solve the Monopoly
problem. First, let's look at Step 2.
Step 2
Suppose you are given the following problem, which uses
3 states:
At the end of each year, people living in Cal.,
NY., and Texas are free to move according to the following
rules. Of the people in California, 97% will stay in Cal., 1%
will move to NY, and 2% will move to Texas. Of the people in
NY, 3% will move to Cal., 95% will stay in NY, and 2% will
move to Texas. Finally, of those people living in Texas, 3%
will move to Cal., 1% will move to NY., and 96% will stay in
Texas. Assume we don't have to worry about births, deaths,
immigration, etc. and can let the system run as long as needed
until steady state conditions are reached. We then ask, what
proportion of the population will end up living in each of the
3 states?
First, let's change the percentages to probabilities and put
the numbers in a table.
<
Move to States
>
Cal.
NY
Texas

Current
> Cal.  .97  .01
 .02 
live in
> NY  .03 
.95  .02  Note: Each row must
States
> Texas  .03  .01
 .96  sum to 1.0000

One possible way to solve this problem is to put
an arbitrary number of people in one of the states (There are
no restrictions on the initial population distributions), and
then run the clock forward to see what happens. For example,
let's start with 100 people in NY and see what happens as the
years progress.
The table below shows how many people are living in each state
at the end of year 0, 1, 2, etc.
Year
Cal.
NY Texas
0 0.00
100.00 0.00
1 3.00
95.00 2.00
(Only need the rules from row 2)
2 5.82
90.30 3.88
(e.g.: Cal = keeps 97% of Cal.,)
etc.
(plus
3% of NY moves to Cal,)
(plus
3% of Texas moves to Cal.)
100
49.90
16.84 33.26
200
49.9998 16.6670
33.3332
Large
100*(1/2) 100*(1/6) 100*(1/3) "Steady
State Condition"
We note that the populations (proportions)
gradually converge toward the "Steady State Conditions". If we
calculated another row after "Large", we would get the
following: Cal = .97*50.000 + .03*16.667 + .03*33.333 which
again equals 50. Similar calculations for the other
states would show that their populations (proportions) don't
change either.
Thus, in this problem we have "Steady State Conditions" of:
Pc
(Proportion in California) = 0.500000
Pn (Proportion in
New York) = 0.166667
Pt (Proportion in
Texas) = 0.333333
Once we reach "Steady State Conditions", these
proportions don't change. Thus, "Pc" at time period "N+1" will
be the same as at time period "N".
We can then write:
Pc = .97*Pc + .03*Pn + .03*Pt
This is the general equation for California's proportion. It
is also the same equation we used for California's population
in year 2 when we "ran the clock forward" above. The decimal
numbers that are used are the same decimals that appear in
California's. column.
Similarly, we could write general equations for NY and Texas:
Pn = .01*Pc +.95*Pn + .01*Pt
Pt = .02*Pc + .02*Pn + .96*Pt
Finally, we note the sum of the proportions must equal 1.00:
Thus we have:
Pc + Pn + Pt = 1.00
We can take any 2 of the 3 state equations and combine them
with the last equation to form a set of simultaneous equations
that can be solved by ordinary algebra. For example:
Pc = .97*Pc + .03*Pn + .03*Pt
Pn = .01*Pc + .95*Pn + .01*Pt
Pc + Pn + Pt = 1.000
If we solve this, we will get the same "Steady
State Proportions" (Probabilities/Population) that we got when
we ran the clock forward a large number of times.
The original 3x3 table that we gave showing what
proportion of the population moved from each state to each
other state has a name. It is called a "State to State
Transition Matrix" (also called a Markov Matrix). The simple
problem that we solved is called a Markov Chain.
In this problem we only used 3 states, but the
process could be extended to all 50 states. Then you would
need 49 state to state equations plus the final equation where
the sum must equal 1.000. In our simple problem we used state
names, but we could apply the same solution to cities. (For
example: Boston, Chicago, and Seattle.) In fact we could
extend the solution process to anything that represents a
location. (For example: Mediterranean Ave., Community Chest,
Baltic Ave., etc.).
In our simple problem we arbitrarily defined the
numbers in the "State to State Transition Table". If you
wanted to solve a real problem involving all 50 states, you
would have to get Census data showing how many people moved
from state to state. Finally, if you want a "State to State
Transition Table" for Monopoly spaces, you will have to apply
"Step 1".
Step 1
What is a "Tree Search" and how can it generate a
"
State to
State Transition Table"?
We will start with a simple maze problem, and
show how a "Tree search" can systematically explore all the
passageways. At the end, we will give a few tips on how to
expand the process so you can run a tree search for Monopoly.
_____________


Optional
Exit>

 3
____
____
 




2 Rows

____ 

Enter
>

1
_____________
1
2 3
Columns
This small 3x3 maze has 3 rows and 3 columns. It
is somewhat like a tictacktoe pattern with an addition of an
outside border plus some of the interior lines have been
removed to leave a maze. (This is a method computer programs
can use to generate random mazes.)
An easy rule that will solve any "simple" maze
(one that doesn't have any circle routes) is to start with
your left hand on a wall, and then walk through the maze
always keeping your left hand on a wall. (You could also do
the same thing with your right hand.) We also note that if the
"Optional Exit" is closed, either method would give you a
complete tour of the maze and return you to the starting
location. In the traversal that will generate the Monopoly
transition matrix, we want to do a complete tour of all
possible moves in one turn along with the necessary Monopoly
calculations. For our maze problem, we will also derive a
method of making a complete tour, but our only calculation
will be to leave a number at each row/col location showing how
far we are from the entrance to the maze. When we are finished
it will look like:
_____________


Optional
Exit> 7 6 7  3
____
____
 


2  5 4  2 Rows

____ 

Enter
> 1 2
3  1
_____________
1
2 3
Columns
Another set of rules that would work (and is also easy for a
computer algorithm) would be the following:
(As you traverse the maze, leave a trail of "came from"
direction arrows (cookie crumbs) to trace your progress.)
Start
at "Enter"
At the center of
each "Row,Col" cell that you come to...{
Leave a
number counting how far you are into the maze.
If you
can turn left and move one space (cell), then do so.
(and jump to start of loop)
If you
can't go left or have finished exploring to the left
and can move one space
straight ahead, then do so.
(and jump to start of loop)
If
you
can't go straight ahead or have finished exploring in that
direction
and you can turn right
and move one space, then do so.
(and jump to start of loop)
If
you
are down to here, you have reached a dead end.
Use
the arrows to retrace your steps by one cell.
Then use the arrows at this location to sequence to the
next straight, right,
or retrace step.
} Repeat
until
you have returned to the entrance. You have completed the
tour and performed the necessary calculations.
Let's see how we would implement this via a
computer program. Computers are not very good at understanding
English, but they're really good at processing numbers. Thus,
for the direction to move we will define the following table.
English
Computer
Column
Row
Direction
Direction
Change
Change
UP (North)
0
0 +1
RIGHT (East)
1
+1 0
DOWN (South)
2
0 1
LEFT (West)
3
1 0
We can sequence through all four directions by
incrementing the computer direction. If at any time we
calculate a direction that is >3, we just subtract 4 from
the total to get it back in range. (i.e. Use Mod(4)
arithmetic). We can also use the table values to find our new
Col, Row coordinates by simply adding the above changes to our
old position. If we are at Col 3, Row 2 and move LEFT, we just
add the above changes to get our new position .
When we traversed the maze by hand, we left
arrows (bread crumbs) to trace our route. In our computer
traverse we will use a "stack" to keep track of information.
As we traverse the maze, we will keep track of 5 different
pieces of information. 1) Our col. position, 2) Our row
position, 3) The direction we came from when we first entered
the cell, 4) The last direction we tried to move, 5) A
count of how deep we are inside the maze.
We will give the computer algorithm and then follow it through
a few steps to show how the stack works.
Initialize the system
Do until we return to "Enter"
Increment the "Last Direction" at our current
location (use mod(4) arithmetic)
If this number is now equal to the "Came From"
direction, we have finished exploring all
pathways beyond our current position.
Backtrack one level (Decrement the stack pointer)
If the Stack Pointer is now 0,
the search is complete (Break out of the loop.)
Else try this new direction. If we can not move,
then go to the top of the "Do loop"
Else we can move in this direction. Move to the
new cell and fill in the stack data as follows.
Increment the Stack
Pointer
Update our col, row
coords using the direction we moved.
Our new "came from"
direction is the direction we moved plus 2. (Subtract 4 if the
result is >3)
Initialize the new "last
direction" with this same number.
Our only "calculation" is
to keep track of how deep we are inside the maze. Add 1 to
our
last position.
Repeat loop until we back out of the entrance.
Now let's see how this works in practice. If you draw a copy
of the maze on a piece of paper you can follow the "picture"
progress. Here, we will trace what the numbers look like in
the computer stack.
Initialize system. We are at col = 1, row = 1, CameFromDir =
3, LastDir = 3, Depth = 1
The computer stack looks like:
StackPtr
= 1 >
1 1
3
3 1
(Use
StackPtr to)
Col Row Came
Last Maze
(index
into the stack) Pos Pos
From Dir Depth
Increment the "Last
Dir" (use mod(4) arithmetic)
StackPtr = 1 >
1 1
3 0
1
Col
Row CF
LD MD
LD does not equal CF and we are able to move in this direction
(LD = 0 = UP). Increment the StackPtr and initialize the next
row up in the stack. The stack now looks like.
StackPtr
= 2 > 1
2 2
2 2
1
1
3
0
1
Col
Row CF
LD MD
The lowest level in the stack has not changed. We
left it as it was so we will know what we were doing when we
return to this position. We have moved deeper into the maze.
Thus we added a new layer to the stack. The direction that we
moved comes from the "Last Direction" at our old cell
location. This was "0" which is "Up". We use the Col & Row
change values from the LookUp table to get our new Col, Row
location. The old "Last Direction" was "0". We added 2 to this
(Use MOD(4)). The result was 0 + 2 = 2, and we initialize the
new CF and LD values with this 2. Finally, our only data
calculation is to add 1 to the Maze Depth. The only thing we
have to do with it is to update the original graph with this
number to show how deep we are into the maze. (Monopoly
calculations require more complex calculations.)
On each of the next three times through the loop
the only thing that happens is that we update the "Last
Direction" number at level 2 in the stack. It will cycle from
2 to 3, to 0 (remember MOD(4)), to 1. Nothing happens as we
have no possible move. Finally, on the next round "Last
Direction" equals "Came From" and we decrement the StackPtr
which takes us back to the cell at col = 1, row = 1. The stack
now looks like:
1
2 2
2 2 (Old garbage can be ignored)
StackPtr = 1 >
1 1
3 0 1
Col
Row CF LD MD
As we start through the loop again we increment the "Last
Direction" at our current location. The Stack now looks like:
StackPtr = 1 > 1
1 3
1 1
Col
Row CF LD MD
We can move this new direction (Right) and once again we
increment the StackPtr and store the new data.
StackPtr = 2 > 2
1 3
3 2
1
1 3
1 1
Col
Row CF LD MD
After two more trips through the loop, we can move right
again. The stack now looks like:
StackPtr = 3 > 3
1 3 3 3
2
1 3 1 2
1
1 3 1 1
It might be a worthwhile exercise for the reader
to continue this process until the entire maze is traversed.
If nothing else, we used the term "exhaustive tree search",
and this will definitely illustrate the "exhaustive" part. It
is called a "tree" for a couple of reasons. First, if you use
a pencil to trace your path in larger mazes, the result will
resemble an ordinary tree. Also, from graph theory, a
connected series of lines (with or without branches) is a tree
if and only if there are no pathways that could lead you in a
circle. In a Monopoly search, when we start at some board
space, there are usually many different paths that can lead to
some other board space, but the rules of the game don't let
you cycle using these other paths.
The branches and paths in a Monopoly tree search
are far more complex than the four possible directions that we
moved in this maze example. The 4 possible directional
movements will expand to include all possible dice rolls,
"Chance" instructions, "Community chest" instructions,
doubles, etc. Also, you will have to assign a value to board
spaces to indicate they have a special operation such as
"Chance", "Go to Jail", etc. Yet the principle of
systematically trying all possible combinations of whatever
operation is involved remains the same. In the maze problem,
the only data calculation that was involved was the depth
inside the maze. In both "Part 1" and "Part 3" of the Monopoly
search you will have to keep track of the resultant
probability of all steps in the stack. For "Part 1" of the
Monopoly search, every time you hit a dead end, it represents
an "endofturn". Whatever probability you have at this point
must be added to the appropriate Row,Col position in the "
State to
State Transition Matrix". The tree search for "Part 3"
is very similar except you update the visit probability table
each time you visit a location even though it is not at a
"Dead End" yet.
The actual computer code for all of this is hundreds of lines
long. However, with a little practice, a good programmer
should be able to write his own
code.
Return to
the Monopoly main page
Web page generated via Sea Monkey's Composer HTML editor
within a Linux Cinnamon Mint 18 operating system.
(Goodbye Microsoft)