Stormtroopers Are Bad at Shooting?
Yes.

By Jordan Moles on July 23, 2023

 

The Monte Carlo Method

The Monte Carlo method is an efficient mathematical strategy that is applied to approximate results that are otherwise intractable to calculate with precision. It relies on the use of pseudo-random numbers to simulate random events and derive probabilistic outcomes. A simple illustration to grasp this method would be to envision an army of stormtroopers randomly firing upon a target. By virtue of the Monte Carlo method, we can estimate the stormtroopers’ precision rate by simulating their random shooting and counting the number of shots that strike the target. But especially they can estimate areas.

Tis method is grounded on the law of large numbers, which asserts that if a large number of independent random experiments are conducted, the frequency of the outcomes will converge towards the theoretical probability. For example, if you toss a balanced coin a very large number of times, it will appear tail or head half the time. To employ this method, one must first define a simulation space of random events, generate pseudo-random numbers to mimic these events, and tally the number of occurrences that transpire within a specific region of interest. This information is then used to estimate the probability of a particular event.

For instance, to estimate the precision rate of the stormtroopers, we could define a simulation space that represents the target, let them shoot, and count the number of shots that strike the target. By using the ratio of the number of shots that strike the target to the total number of shots, we can estimate the precision rate of the stormtroopers. To do so,

1. Put one stormtrooper in the closed and huge shooting range.
2. Let’s draw a circle of radius 25 meters in the center of the squared back wall of 50 meters.
3. Now, it’s time to order to the stormtrooper to fire.

“Stormtrooper, attention, target in the back wall in sight, fire one thousand shot.”

Figure 1: A stormtrooper trying to shot the target and the result obtained with one thousand shots.

According to the target, we have the proof that he is not really good at shooting. In fact, he shoots uniformly in the back wall, i.e., in mathematical terms, it means that the probability of striking a defined zone in the back wall is the same as striking another one with the same area. This probability is called continuous uniform distribution. These non-skills will be used to estimate the value of mathematical constants (such as π) and a lot more things.

 

Estimation of π and the Millennium Falcon’s Area

Before continuing, let’s recall that the area of a square of side R is \(S_{square}=R²\) and the area of a circle of radius R is \(S_{circle}=π R²\). We will start with the simplest estimation: that of π. This works by using the same steps as outlined previously

1. Put the army of one million and identical stormtroopers in the closed and huge shooting range.
2. Draw a circle of radius 25 meters within the squared back wall of 50 meters.
3. Recall the order.

“Stormtroopers, attention, target in the back wall in sight, fire one shot.”

1. Count the number of impacts (or points) that fall inside the circle.
2. Use the proportion of impacts inside the circle to the total number of impacts generated to estimate π. Specifically, you can use the following formula:

\begin{equation*}
\pi=\frac{S_{circle}}{S_{square}}=\frac{\text{Number of impacts in the circle}}{\text{Total number of impacts}}.
\end{equation*}

Repeat steps several times or increase your army to get a more precise estimate of π.

Figure 2: The army has arrived and launch first 10 thousands shots.

Figure 3: From left to right, 100 thousands and 1 million shots.

Similarly, one can use this method to estimate the area of the Millennium Falcon, a famous spaceship from the Star Wars series that measures 35 meters in length and 25 meters in width.

Figure 4: Here is the real spaceship photo and plan.

The methodology will almost be the same. We use a computer simulation where stormtroopers randomly shoot at the surface of the spaceship. Each point where a “stormtrooper” hits the surface is recorded and the total area is then calculated by counting the total number of points and comparing it to the total size of the spaceship’s surface. This method is very effective because it takes into account the irregular shapes of the spaceship’s surface, which could make it difficult for a more traditional area estimation. But, unfortunately, this will lead to the total destruction of the spaceship!

1. Put the army of stormtroopers in a closed and huge shooting range.
2. Draw a 35m x 25m rectangle to represent the surface of the back wall and stick the millennium falcon on it.
3. Order the stormtroopers to fire.
4. Count the number of shots that strike the surface of the Millennium Falcon.
5. Use the proportion of shots that strike the surface of the Millennium Falcon to the total number of shots to estimate the area of the Millennium Falcon. Specifically, you can use the following formula:
\begin{equation*}
\text{Area of Millennium Falcon}=35\times 25\frac{\text{Number of shots that strike the Millennium Falcon}}{\text{Total number of shots}}.
\end{equation*}
6. Repeat steps several times or increase the number of stormtroopers to get a more precise estimate of the area of the Millennium Falcon.

Figure 5: From left to right, with 10 thousands, 100 thousands and 1 million shots.

The accuracy of the Monte Carlo method for estimating areas depends on the number of randomly generated shots. The more impacts you generate, the more accurate your estimate will be. However, it is important to note that even if you generate a large number of impacts, you will never be able to calculate the exact value of the area you consider. For example, with 1 million stormtroopers, you can get an estimate of π with an accuracy of about 2 decimal places. For the millenium falcon area, we get approximately 400.855m².

 

The importance of lack of precision

The Monte Carlo method relies heavily on the generation of random numbers to simulate random events. This is where the lack of precision of the stormtroopers comes in. In the previous example, the stormtroopers’ lack of precision in shooting represents the randomness required for the Monte Carlo method to work effectively (here, they shoot perfectly bad). Without this randomness, the method would not be able to accurately approximate results.

Let me explain this concept by introducing Han Solo, a highly skilled marksman, into the simulation. The distribution of shots fired would no longer be uniformly random, but rather, it would be weighted towards the areas where Han Solo aims. More precisely, if we estimate its precision rate as we did with the stormtroopers, we observe that he shoots almost perfectly well.

Figure 6: Han solo firing one million shots.

Maybe because Chewbacca is bothering him or because he has dust in his eye, and this is why its precision rate is not 100 percent (he says). Now, how good is he at estimating π? By using the same formula
\begin{equation*}
\pi=\frac{\text{Number of impact in the circle}}{\text{Total number of impact}},
\end{equation*}
it seems that π is more or less equal to 4 with 1 million of shots.

This highlights an important consideration when using the Monte Carlo method – the accuracy of the results depends heavily on the random nature of the simulation. Introducing biases or non-uniform distributions can greatly impact the effectiveness of the method. Roughly speaking, it means that to be accurate, the random numbers generated must be truly random and not follow a predictable pattern or being precise.

 

Generation of random numbers

Generating random numbers is a fundamental task in many fields, ranging from computer science to cryptography and simulations. While we often think of randomness as something that occurs naturally, such as the roll of a die or the flip of a coin, many random numbers used in computing are actually generated through sophisticated algorithms or physical phenomena.

One widely used method is the pseudo-random number generator, which produces a sequence of numbers that appears random, but is actually calculated deterministically from an initial “seed” value. Although not truly random, pseudo-random generators are highly efficient and unpredictable enough to meet most practical needs. However, they are subject to periodicities and correlations in the sequences produced, which can pose security risks in certain applications. By using the Star Wars analogy, it consists in taking a perfect imperial sniper which follows a shooting pattern; you only have to order the first target to hit and each shoot will be a defined function of the previous one.

Figure 7: An imperial sniper with a part of his shooting pattern.

Now, imagine that you are a rebel spy and you want to send a secret message to your base. For this, you need a random number that will serve as an encryption key. You could use a pseudorandom number generator to create one, but there is always a risk that the Empire has been able to predict the sequence of numbers you are going to use. To make sure that your encryption key is truly random, you could use a quantum number generator.

In this example, the pseudorandom number generator would be like an Empire soldier who follows a predefined and easily predictable attack plan as the imperial sniper. On the other hand, the quantum number generator would be like a scientist rebel who exploits the unique properties of light sabers to find unpredictable solutions to each situation. As quantum numbers are generated from unpredictable quantum phenomena such as polarization, phase, or frequency of photons, the Empire cannot predict the sequence of numbers you will use, making your secret message much safer. These generators produce numbers that are truly random and impossible to replicate. While still relatively new and expensive, quantum random number generators hold great promise for applications requiring the highest levels of security and unpredictability.

 

The Versatility and Power of the Monte Carlo Method

To sum up, the Monte Carlo method is a versatile and powerful mathematical technique that allows for the approximation of complex results that are otherwise difficult to calculate precisely. The use of random or pseudo-random numbers to simulate random events and determine probabilistic outcomes makes it an effective tool for various applications, as demonstrated by the simulations of stormtroopers’ shootings. The method’s applications extend beyond estimating mathematical constants and areas of irregular shapes, to include predicting the outcome of elections, simulating population growth, and estimating the probability of rolling a certain number on a dice game.

 The Monte Carlo method is a valuable tool for numerous fields, such as physics, engineering, and finance, making it an essential component of the mathematician and statistician’s toolkit.

Bibliography

M. Kalos, P. Whitlock, Monte Carlo Methods, 2008.

D. P. Kroese, T. Taimre, Z.I. Botev, Handbook of Monte Carlo Methods, 2011.

D. P. Kroese, T. Brereton, T. Taimre, Z.I. Botev, Why the Monte Carlo method is so important today, 2014.

S. Weinzierl, Introduction to Monte Carlo methods, 2000.


import random
import matplotlib.pyplot as plt

def estimate_pi(n):
    num_points_circle = 0
    num_points_total = 0
    circle_x, circle_y = [], []
    square_x, square_y = [], []

    # Loop for generating random points and estimating π
    for _ in range(n):
        x = random.uniform(-1, 1)
        y = random.uniform(-1, 1)
        distance = x**2 + y**2
        if distance <= 1:
            num_points_circle += 1
            circle_x.append(x)
            circle_y.append(y)
        else:
            square_x.append(x)
            square_y.append(y)
        num_points_total += 1

    # Plotting the points on a graph
    plt.figure(figsize=(5, 5))
    plt.scatter(circle_x, circle_y, color='blue', s=0.1)
    plt.scatter(square_x, square_y, color='red', s=0.1)
    plt.xlim(-1.1, 1.1)
    plt.ylim(-1.1, 1.1)
    plt.title("Estimation of π using the Monte Carlo method\nN = {}".format(n))
    plt.show()

    # Calculating and returning the estimated value of π
    return 4 * num_points_circle / num_points_total

print(estimate_pi(10000))




import cv2
import numpy as np
import random

# Load the image and convert it to grayscale
img = cv2.imread("/Users/.../falcon2.png", cv2.IMREAD_GRAYSCALE)

# Apply thresholding to get a binary image
ret, thresh = cv2.threshold(img, 127, 255, cv2.THRESH_BINARY)

# Invert the colors so that black becomes white and vice versa
thresh = cv2.bitwise_not(thresh)

# Find contours in the image
contours, hierarchy = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)

# Create a black image to draw the contours
contour_img = np.zeros((img.shape[0], img.shape[1], 3), np.uint8)

# Draw the contours in white on the black image
cv2.drawContours(contour_img, contours, -1, (255, 255, 255), 2)

# Get the size of the image in pixels
height, width = img.shape[:2]

# Retrieve the size of the image in pixels
size = img.shape[:2]

# Define the real dimensions of the Millennium Falcon
real_length = 35  # in meters
real_width = 25   # in meters

# Define the resolution of the image in pixels/meter
resolution = 144

# Calculate the total number of pixels of the ship's surface
total_surface_pixels = int(real_length * real_width * resolution**2)

# Number of random points to generate for the estimation
n = 1000000

# Number of points inside the black figure
num_points_inside = 0

# Generate random points in the image and count the number of points inside the black figure
for i in range(n):
    # Generate a random point in the image
    x = random.randint(0, width-1)
    y = random.randint(0, height-1)

    # Check if the point is inside the black figure
    if cv2.pointPolygonTest(contours[0], (x, y), False) == 1:
        num_points_inside += 1
        # Draw the point in blue
        cv2.circle(contour_img, (x, y), 1, (255, 0, 0), -1)
    else:
        # Draw the point in red
        cv2.circle(contour_img, (x, y), 1, (0, 0, 255), -1)

# Estimation of the area of the black figure using the Monte Carlo method
estimated_area = (num_points_inside / n) * (width * height)

# Display the image with points in blue and red
cv2.imshow('Image with points', contour_img)

# Wait for the user to press a key to close the window
cv2.waitKey(0)
cv2.destroyAllWindows()

# Display the estimated area of the black figure
print("Estimated area of the black figure:", estimated_area)





import random
import math
import matplotlib.pyplot as plt

num_shots = 1000000
circle_hits = 0
square_hits = 0
circle_x = []
circle_y = []
square_x = []
square_y = []

for i in range(num_shots):
    x = random.gauss(0, 0.05) # shots centered at the circle's center
    y = random.gauss(0, 0.05)
    distance = math.sqrt(x**2 + y**2)
    if distance <= 1:
        circle_hits += 1
        circle_x.append(x)
        circle_y.append(y)
    else:
        square_x.append(x)
        square_y.append(y)
    square_hits += 1
    if random.random() < 0.1: # 10% chance of shooting in the circle
        if distance <= 1:
            circle_hits -= 1
            circle_x.pop()
            circle_y.pop()
        else:
            circle_hits += 1
            circle_x.append(x)
            circle_y.append(y)
        square_hits -= 1

pi_estimation = 4 * circle_hits / square_hits
print("Estimation of pi:", pi_estimation)

fig, ax = plt.subplots(figsize=(6, 6))
ax.set_xlim([-1.2, 1.2])
ax.set_ylim([-1.2, 1.2])
ax.set_aspect('equal')
ax.scatter(square_x, square_y, color='red', s=1, label='Outside the circle')
ax.scatter(circle_x, circle_y, color='blue', s=1, label='Inside the circle')
circle = plt.Circle((0, 0), 1, color='black', fill=False)
ax.add_artist(circle)
ax.legend()
plt.show()



To find the Millenium Falcon area, we used the following image.