188 Monopoly Walker

Description

Your task this week is to simulate players walking about a Monopoly board. You are not implementing the whole game; rather, you are to simulate and track just the players’ movement. Throw dice, move tokens. Keep track of the properties where players land and how often.

Your output should be a table showing the relative frequency each property is landed upon. Now, if you only paid attention to the dice, this should be pretty even across the board. To make it slightly more interesting, you do need to pay attention to the “Go to Jail” space, as well as the Chance and Community Chest cards.

For the cards, don’t worry about money tracking or anything like that; again, we’re only interested in movement, and the few Chance and Community Chest cards that affect movement should have an impact on the relative landing frequency.

Some helpful links:

If there is version differences, use information from these pages pertaining to the Standard (American edition) as of Sept 2008.

Summary

Writing a simulator for a complete Monopoly game isn’t overly complex, but it does require a lot of attention to detail in order to accurately reflect the game rules. Writing a simulator for just the movement portion of the game should be much simpler – you can ignore property purchases and auctions, money tracking, rent, hotels, etc.

What makes such a simulator non-trivial is the possibility of jumping around. If the only way to move around the board was via a dice rolls, the expected pattern to landing on properties would be even; that is, no one property would be more valuable than any other. However, when the Community Chest and Chance cards are added in, along with the Jail, the distribution is no longer even. When running the submission from Daniel Moore for 10,000,000 iterations, the top ten properties show up as:

Jail/Just Visiting    - 5.0660%
GO                    - 4.4057%
Reading Railroad      - 3.7458%
Mediterranean         - 3.4747%
Income Tax            - 3.3711%
Baltic                - 3.3506%
Community Chest       - 3.2478%
Oriental              - 2.8945%
Illinois              - 2.6351%
New York              - 2.5123%

Now, four of those properties cannot be owned. The other six amount to almost 20% of property landings. And, interestingly, two of the highest properties are Mediterranean and Baltic, which form a monopoly.

I’ll note here that I believe Daniel’s simulation to be a good start, but has some problems. I found one bug. It does not simulate the rolling of doubles to escape Jail, which would have an impact on the twelve properties that follow. Also, I’m not certain the handling of Community Chest and Chance cards is mathematically accurate, but may be reasonably close. Additionally, the human factor is completely removed here, which may be significant.

In any case, while you may want to improve the script before preparing for your next game of Monopoly, we can certainly look at what Daniel has done. Let’s begin with the overall simulation:

class Board
  # ...
  def simulate(moves)
    @moves = moves
    position = 0

    @moves.times do
      position += roll

      # Land on the properties and keep following the cards until we stay put
      while( position != (new_position = (@properties[position % BOARD_SIZE]).land) ) do
        position = new_position
        # Track the extra moves
        @moves += 1
      end
    end
  end
  # ...
end

board = Board.new
board.simulate((ARGV[0] || 100000).to_i)

One parameter is pulled from the command line to be the number of simulation steps (i.e. dice rolls) to make, defaulting to 100,000 is no argument is provided. The board is created and simulate called.

Inside, we loop, calculating the next position, finding the corresponding property, and calling land on that property. land will return new position, often itself, unless some condition causes the player to move elsewhere. If that happens (and so position will not equal new_position), we update position and increase @moves, just to keep track of how many moves were made overall (compared to how many rolls, the original parameter). When we look at land, we’ll see the bookkeeping for tracking landing counts.

There is a bug here, however: the calculation of position. In most cases, when you don’t move beyond the roll, land will return the index into @properties: that is, position % BOARD_SIZE. Usually, this will be the same as position, except when passing Go (e.g. 46 != 6). In such a case, the move count will be incremented inappropriately, and land will be called once too often. To fix, change the loop to:

	@moves.times do
	  position += roll
	  position %= BOARD_SIZE

	  # Land on the properties and keep following the cards until we stay put
	  while( position != (new_position = (@properties[position]).land) ) do
	    position = new_position
	    # Track the extra moves
	    @moves += 1
	  end
	end

A seemingly minor bug, but this is why Baltic, Mediterranean, and Oriental showed up near the top of the distribution; they are the properties that would be hit more frequently when moving past Go. When this bug is fixed, the top ten distribution of properties is:

Jail/Just Visiting    - 5.4544%
Illinois              - 2.9668%
GO                    - 2.9018%
New York              - 2.8461%
B&O Railroad          - 2.8458%
Reading Railroad      - 2.7957%
Community Chest       - 2.7122%
Pennsylvania Railroad - 2.7024%
Tennessee             - 2.6937%
Free Parking          - 2.6587%

Now we see Illinois Avenue, B&O Railroad and GO are closer to the top, which are the three most landed on properties according to most sources I’ve seen, including the Monopoly wiki. (Not sure why Jail is so high… and New York would drop in rank once in-Jail rolls are handled correctly).

Let’s now look a bit at the Property class, that which tracks how often a player lands on the property.

class Property
  @@property_count = 0
  attr_accessor :count

  def initialize(name, block)
    @count = 0
    @name = name.gsub('_', ' ')
    @position = @@property_count
    @@property_count += 1
    @move_block = block
  end

  # Record that the token landed on this cell
  # Return any bonus move (new location)
  def land
    @count += 1
    # Sometimes cells have a bonus move, this returns
    # the new location, could be the same if no bonus move.
    @move_block.call(@position)
  end
  #...
end

The basics of this class is pretty simple: a @count data member is initialized to zero at creation, and incremented once for each call to land. attr_accessor provides a way to get the count later. @name is also initialized at creation.

@move_block is also assigned at creation; this is a code block that, given a position, will return another position. The idea here is that some spots on the board (such as Chance, Community Chest, and Go to Jail) will immediately move the player somewhere else. Calling this block (provided elsewhere) will return the new position. In most cases, where the player does not move, the stay_put block is used; given the current position, it returns that same position – the player will stay in one place.

stay_put = Proc.new {|cur_pos| cur_pos}

My main concern with the Property class is the duplication of effort found in @@property_count. The idea is to have each newly created property receive a unique index, stored in @position. However, this information is already provided externally by the PROPERTY_NAMES constant array, which dictates the order in which properties are created. Whenever you have two data “masters”, you run the risk that they disagree. My revision would be to lose @@property_count and pass an extra parameter into the initializer.

class Property
  #...
  def initialize(pos, name, block)
    @count = 0
    @position = pos
    @name = name.gsub('_', ' ')
    @move_block = block
  end
  #...
end

Also, I would like to change attr_accessor to attr_reader, but the count field is written to later in the code. However, it is reused for a purpose other than the count; it would be better to provide a separate data member, appropriately named, rather than overlap use of count. Or, better yet, calculate the frequency on the fly, since it’s a simple calculation that doesn’t need to be stored.

The last thing I’ll look at here is one of the code blocks used to handle special movement around the board. There are a few of them, but let’s look at the block for handling Chance cards. (The other blocks are reasonably similar.)

CHANCE_EFFECT = Proc.new do |cur_pos|
  case Kernel.rand(CHANCE_CARDS)
  when 0
    GO_POSITION
  when 1
    ILLINOIS_POSITION
  when 2
    # Nearest Utility
    if (cur_pos >= WATER_WORKS_POSITION) || (cur_pos < ELECTRIC_COMPANY_POSITION)
      ELECTRIC_COMPANY_POSITION
    else
      WATER_WORKS_POSITION
    end
  when 3..4
    # Nearest Railroad
    case cur_pos
    when 5..14
      15
    when 15..24
      25
    when 25..34
      35
    else
      READING_POSITION
    end
  when 5
    ST_CHARLES_POSITION
  when 6
    # Go back three spaces
    cur_pos - 3
  when 7
    JAIL_POSITION
  when 8
    READING_POSITION
  when 9
    BOARDWALK_POSITION
  else
    # This card does not have an effect on position
    cur_pos
  end
end

Each time the block is called, a “card” is chosen at rand, and the player’s new position is returned. In many cases (i.e. the else statement), the current position is returned; that is, there is no addition movement beyond the where the player is located.

In most other cases, constants (e.g. ILLINOISPOSITION) are used to provide the new location. The case statement is a decent, straightforward mechanism for sorting this out. (I can imagine other ways to do this, but I leave those as an exercise for the reader. Ha.)

What I will mention here are how those constants are initialized, and also the use of some hardcoded numbers. For the latter, the approach that worked for the “nearest utility” case would be suitable for the railroads. (Personally, I’d probably turn it into a mathematical formula.) But even assuming we turn the hardcoded numbers into constants, how are those defined?

GO_POSITION = 0
ILLINOIS_POSITION = 24
BOARDWALK_POSITION = 39

Now, normally, this would be the place to put the literal integers; however, as mentioned before, this is another “master” in generating board position numbers. All this information is present in the array PROPERTY_NAMES. To make use of that master array, rather than providing redundant information, I would do this:

GO_POSITION = PROPERTY_NAMES.index("GO")
ILLINOIS_POSITION = PROPERTY_NAMES.index("Illinois")
BOARDWALK_POSITION = PROPERTY_NAMES.index("Boardwalk")

Likewise,

BOARD_SIZE = PROPERTY_NAMES.size

instead of:

BOARD_SIZE = 40

Note, while the property names are being repeated here, it is (in a way) not redundant information, since it is not acting as an authority for property names (as the literal integers were). Also note, with the flexibility of Ruby, this could be made even less redundant and more compact, but that’s not something I’m going to get into here.


Wednesday, February 04, 2009