Monte Carlo

monte.py: 14 points


Real-World Motivation

One of the most efficient ways to solve really complicated problems in computer science is to repeat a bunch of random trials that simulate something in the real-world, then combine all of the results of those trials to create a solution. For example, using artificial intelligence, computers can now routinely win against the best human players in the world in classic games such as Go and chess by mentally playing different moves, then estimating a large number of future outcomes to see which leads to wins the most frequently. Ongoing research here at Oberlin is developing similar methods that could be used by robots to decide how to put out wildfires to protect people and property from natural disasters. This type of solution is called a Monte Carlo method, which we will explore in this problem.

Calculating Pi using Darts

One of the most famous numbers in the world is the number pi ($\pi = 3.14159265…$), which has important applications in geometry, architecture, graphic design, and even baking (no pun intended). The number $\pi$ is irrational, meaning that it cannot be expressed as a simple fraction and it has an infinite number of values after the decimal point. This makes calculating the exact value of $\pi$ difficult…in fact it’s impossible in finite time! We can, however, estimate the value of $\pi$ to some precision.

In the monte.py program, we will calculate an approximate value of $\pi$ by randomly throwing darts at a dartboard. How does that help us?!? Imagine that we have a circular dartboard in front of a square part of the wall, similar to the picture below.

Say that the width of the square part of the wall (also the diameter of the circle of the dartboard) is equal to $w$. Then geometry tells us that the total area of the square part of wall is $w^2$, and the total area of the dartboard is $\pi \times ($circle’s radius$)^2 = \pi \times (\frac{w}{2})^2 = \frac{\pi \times w^2}{4}$. That means that the dartboard takes up $\frac{\pi}{4}$ of the area of the wall behind it.

How does this help us calculate $\pi$? Imagine now that you are blindfolded and throw n darts at the wall. Without being able to see anything, your darts would land randomly all over on the dartboard and on the wall around it. Now, if you count how many darts land on the dartboard (yay, you got kind of close) and divide that by the number of darts you threw, you have a good approximation of the fraction of the wall taken up by the dartboard. Which we already said above is equal to $\frac{\pi}{4}$. So, with a little bit of algebra, multiplying 4 by the number of darts that hit the dart board and dividing by the number of darts you threw gives us an answer that is close to $\pi$. Indeed, the more darts you throw, the better your approximation becomes, and the closer your answer is to $\pi$!

Implementing our Experiment

Let’s put the experiment above into algorithm form.

  1. Draw an image for the square part of the wall and a circle in front of that square. This is the dartboard. Let’s say w = 400 is the width of the square and also the diameter of the circle.
  2. Ask the user for a number, n, of darts to throw.
  3. Throw that number of darts.
    1. We pick a random location (randX, randY) on the square where the dart should land.
    2. We draw a small circle on the location where the dart landed to visualize its throw.
    3. We calculate whether the dart landed on the dartboard or not. If it did, we increase a count called hits.
    4. We multiply 4 with the number of hits and divide by the number, n, of darts thrown to calculate the value of $\pi$
  4. Save your picture of the dartboard and darts. picture.save_picture("pi_darts.png") should be the last line in your code.

Randomly Throwing Darts

To calculate a random location where the dart lands, we will use the random module in Python. To use the random module, add the following line to the top of your program:

import random

You can get a random integer between 0 and w with the following line.

randX = random.randrange(w)    # returns an integer in [0,w-1]

Since the square has width w, you can think about this number randX representing a random x-coordinate where the dart lands. Repeating that line of code to create a variable randY gives us a random y-coordinate for the dart to land. To display the dart throw, we can draw a small circle centered at the (randX, randY) point that was just randomly chosen (please use a color that can be seen on top of the color you choose for your dartboard).

Deciding if a Dart Hits the Dartboard

Once we know the location of a dart, the next question is: did this dart land on the dartboard? This sounds like a conditional, so we can use an if statement here! If the diameter of the dartboard is w = 400, then its radius is 200, meaning that any location within 200 pixels of the center of the dartboard is part of the dartboard, and any location farther away lands on the wall. We can calculate the distance using this formula:

$$ dist = \sqrt{(randX - centerX)^2 + (randY - centerY)^2} $$

where for us, centerX = 200 and centerY = 200 since the dartboard is in the middle of the wall.

The math module in Python provides us with the square root function needed to calculate distance. Like the random module, we can use the math module by adding the following line to the top of your program:

import math

Then, we can use:

dist = math.sqrt(equation)

to calculate the distance dist, where equation is the equation inside the square root described above. Finally, an if statement checks if the dart hits the dartboard.

if dist < 200:
    hits = hits + 1

Reminder

Remember to periodically commit and push your changes!

Example Outputs

This program approximates the value of π by
simulating the random placement of darts thrown onto
a round target on a square wall.

How many darts do you want to throw? 1
The approximation of π after 1 iterations is 4.0
This program approximates the value of π by
simulating the random placement of darts thrown onto
a round target on a square wall.

How many darts do you want to throw? 100
The approximation of π after 100 iterations is 3.2
This program approximates the value of π by
simulating the random placement of darts thrown onto
a round target on a square wall.

How many darts do you want to throw? 1000
The approximation of π after 1000 iterations is 3.092

Accuracy vs Number of Darts

If you only throw a small number of darts (< 100), your approximation of $\pi$ might be closer to 4 than 3.14159265… The more darts you throw, the closer your answer should get to the actual value of π. Of course, we are relying on randomness here, so bad luck could result in a large number of darts still giving an estimate that isn’t close, or good luck could result in a close estimate with only a few darts. Running your program over and over should give different answers, even for the same number of darts.