The Snake Problem

Most of the problems in the world cannot be solved by simple mathematical equations. In fields of gambling, stock market trading, physics and so on, where it involves amount of uncertainty and randomness, there is a simulation method called “Monte Carlo” helps people to cope with such complicated problems. In this article, I will demonstrate how Monte Carlo Simulation facilitates us with the Snake Problem.

Get code


Problem:

A snake is a one-dimensional object of length 30cm. It moves at a speed of 1 cm/second. It lives in a cage of 1000cm x 1000cm. The snake can only move horizontally or vertically. At random intervals (1 every 5 seconds in average) the snake can turn left or right. If the snake intersect itself, the snake bites itself and dies. The snake starts moving at the center of the cage.

The question is whether it is good to bet $1000 on that the snake will bite itself before it reaches the end of the cage.

 


Break Down:

The problem is asking if betting $1,000 on a snake, that it will bite itself before it reaches the end of the cage, is a good bet. To answer it, first of all, we need to know the probability that the snake bite itself before it reaches the end of the cage, then calculate the expectation value of this bet. If the expectation value is greater than 0, it is a good bet. If not, it is not a good bet.

Expectation value:

E[X]=\sum { p(x)\cdot f(x) }=p(bite\_ itself)\cdot 1000+p(reach\_ the\_ edge)\cdot (-1000)

Since the problem is too complicate to calculate the probability that the snake bite itself before it reaches the end of the cage or it reaches the cage, we need to do the Monte Carlo simulation.

 


Snake Object:

Before doing Monte Carlo simulation, we have to build a snake object to imitate a snake. In the object, a snake is initialized with body, direction, vital status, and game completeness status. First, the body is a python list containing (0, 0), (1, 0), … ,(29, 0). We can consider these dots are a snake lying on coordinate plane where its head is (0, 0) and its tail is (29,0). Second, the direction is another object to control the snake to move in a certain direction. The value store in the direction object is a lambda taking a dot (head dot) as input and return a new dot toward current direction. This will be explained more clearly later. Third, the vital status (self.dead) is a Boolean value for checking whether a snake bites itself (fail the game). Last, the game completeness status (self.completed) is also a Boolean value for checking whether a snake reach the edge (beat the game).

class snake():
    def __init__(self):
        self.body = [(i,0) for i in range(30)]
        self.direction = left
        self.dead = False
        self.completed = False
    def move(self):
        del self.body[-1]
        newhead = self.direction.val(*self.body[0])
        if newhead in self.body:
            self.dead = True
        elif self.__reach_edge(newhead):
            sefl.complete = True
        self.body.insert(0, newhead)

    def __reach_edge(self, point):
        return any(axis<=-500 or axis>=500 for axis in point)

    def change_dir(self, clockwise=False): ### default: turn left
        if clockwise:
            self.direction = self.direction.R
        else:
            self.direction = self.direction.L

 

The move method in snake object could simulate one move (on the coordinate plane) that a snake does. It basically, remove the tail dot, pass the current head into the lambda stored in the direction object, and add the returned value to the first place in the body list (as a new head). While moving, it will check if the new head dot exists in the body list. If so, the vital status will change (from default alive) to dead. On the other hand, it also checks if the new head reaches the given edge. If so, the game completeness status will turn True.

def move(self):
    del self.body[-1]
    newhead = self.direction.val(*self.body[0])
    if newhead in self.body:
        self.dead = True
    elif self.__reach_edge(newhead):
        self.complete = True
    self.body.insert(0, newhead)

 

The __reach_edge function is a private function to test whether the pass-in dot (new head) reaches the edge. If any values on axes of the pass-in dot is greater/equal to 500 or lesser/equal to -500, which means the snake reaches the cage of 1000×1000, it returns True.

def __reach_edge(self, point):
    return any(axis<=-500 or axis>=500 for axis in point)

 

Before explaining the last class method in the snake object, we have to understand what the direction object does. The direction object is actually the two-way linked list having a directional-moving lambda as its value. The reason for using the two-way linked list is the direction for a snake is relative, not absolute. To illustrate, while we look at a snake, we can see the snake moving up, down, left, or right (absolute direction). However, for the snake, it only has three directions, moving toward, turning left, or turning right and this is always true for the snake no matter what the current direction it is (relative). Therefore, we could benefit from using the two-way linked list (circled) for our convenience.

class node():
    def __init__(self, val):
        self.val = val
        self.L = None
        self.R = None

left = node(lambda x,y: (x-1, y))
up = node(lambda x,y: (x, y+1))
right = node(lambda x,y: (x+1, y))
down = node(lambda x,y: (x, y-1))

left.L, up.L, right.L, down.L = down, left, up, right
left.R, up.R, right.R, down.R = up, right, down, left

 

After we understand what the direction object does, we could continue to talk about the last class method in the snake object. The change_dir method has one parameter (clockwise) set False as default. When this method is called, if the argument passed in is True, it changes the current direction to its relative right, else it changes to its relative left. (see Fig. 1)

def change_dir(self, clockwise=False): ### default: turn left
    if clockwise:
        self.direction = self.direction.R
    else:
        self.direction = self.direction.L

 

 


Simulate Once:

Since we have built the snake object and direction control mechanism, we could start our simulation (once).

def simulate_once():
    my_snake = snake()
    while True:
        ###Turn every 5 seconds in average
        seconds = ceil(expovariate(0.2))

        ##before every turn, move forward in current direction
        for i in range(seconds):
            my_snake.move()
            if my_snake.dead:
                return 0
            elif my_snake.completed:
                return 1
        
        ### change direction
        turn = choice(['left', 'right'])
        if turn == 'left':
            my_snake.change_dir(clockwise=False)
        else:
            my_snake.change_dir(clockwise=True)

 

The function above consists of three parts, initialization of a snake, moving toward, and changing direction. After initializing a snake, it starts a while loop.

In the while loop, first, the snake moves x centimeter toward (current direction) based on exponential distribution with ƛ = 0.2. To illustrate, since we know the time between two random turns follows exponential distribution and exponential probability formula is , we could calculate its Cumulative Density Function,  . Then, we could invert this CDF to get an exponential random value for simulating the time between every two turns that a snake makes.

The inverted formula:

x=-\frac { 1 }{ \lambda } logu

By passing a uniform random value, u in [0, 1], into the inverted formula, the derived x is the length of time interval following exponential distribution with ƛ = 0.2 (a snake makes a turn every 5 seconds).

Once we have an exponential random value, the time interval till next turn, we could know how many centimeters that a snake moves until it turns based on its 1cm/second speed. For example, if we get an exponential random value “4”, we know that after 4 seconds, the snake will make a turn, which exactly means that after moving 4 cm in the current direction, the snake will make a turn. After we know how many steps (one step 1cm) the snake will take, we have the snake move this amounts of steps and check whether it bites itself and whether it reaches the edge in every step. If the prior happens, return 0. If the later happens, return 1.

In the second part of the while loop, after the snake finishes the steps within the current time interval (exponential random value), it makes either a right turn or left turn. This is controlled by random choice provided in python. It has 50% to choose left and 50% to choose right. If it chooses left, it calls the class method change_dir and pass in clockwise=False. If it chooses right, it calls change_dir and pass in clockwise=True. By recognizing the argument, change_dir method will make a relative turn to its current direction.

This simulate_once function will keep repeating moving toward and changing direction until the snake hits itself or the edge.

 


Visualization:

Once we have the simulation function, we could record the snake movement and visualize it. The below animation is one of the simulation results.

 


Simulate Many:

Since we could simulate whether a snake completes or fails in a trail. We could count the total successes and total number of trails to get the probability according to the frequentist definition of probability.

Frequentist probability:

Prob(A)\equiv \lim _{ x\to \infty } \frac { { N }_{ A } }{ N }

def simulate_many(times):
    total = positive = 0
    for i in range(times):
        positive += simulate_once()
    return positive/times

 

This simulate_many function counts the total number of trial and the number of successes.

>>> simulate_many(100000)
0.0
>>>

 


Conclusion:

For this question, it is a very good bet because we literally have 0 probability to lose based on one hundred thousand simulations.

People might feel the setting of cage is too big so that the answer is quite obvious. However, Monte Carlo Method provides us anther way to examine complex problems. Imagine that, now you are the banker taking bets against whether the snake dies or reaches the end of the cage of 100cm x 100cm before it bites itself. How would you set the odds if you want to earn 5% whatever players take their bets? The problem is getting not that intuitive right? Yet, with this simulation method, we could approach the probabilities to find out what odds earn us that 5%.