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 2-dimensional, 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.



  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".



   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 tic-tack-toe 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
  If you can't go straight ahead or have finished exploring in that direction
  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 Look-Up 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 "end-of-turn". 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 KompoZer