Pirate Monte Carlo Method
I am working on a simple Monte Carlo simulation script, which I will continue later for a larger project. script is a basic crawler trying to navigate from point A to point B on the grid. Point A's coordinates are (1,1) (this is the top-left corner) and point B's coordinates are (n, n) (this is bottom-right corner, n is the grid size).
Once the finder starts to move, there are four options: it can go left, right, up or down (diagonal movement is allowed). If any of these four options satisfy the following:
- The new point must still be within the nxn grid
- The new location should not be visited earlier
the new point will be chosen randomly among the remaining valid parameters (as far as I know, Python uses the Mersenne Twister algorithm to select random numbers).
I would like to run the simulation 1000,000 times (the code below only works 100) and each iteration must be completed either:
- Scanner gets stuck (no valid options to move)
- The crawler hits the final destination (n, n) on the grid.
I thought I had implemented the algorithm correctly, but obviously something is wrong. Regardless of how many times I run the simulations (100 or 1,000,000), I only get one successful event with which the robot manages to get to the end, and the rest of the attempts (99, or 999,999) are unsuccessful.
I bet there is something simple that I'm missing but somehow can't see. Any ideas?
Thanks a bunch!
EDIT: Corrected some typos in the text.
import random
i = 1 # initial coordinate top left corner
j = 1 # initial coordinate top left corner
k = 0 # counter for number of simulations
n = 3 # Grid size
foundRoute = 0 # counter for number of cases where the final point is reached
gotStuck = 0 # counter for number of cases where no valid options found
coordList = [[i, j]]
while k < 100:
while True:
validOptions = []
opt1 = [i - 1, j]
opt2 = [i, j + 1]
opt3 = [i + 1, j]
opt4 = [i, j - 1]
# Check 4 possible options out of bound and re-visited coordinates are
# discarded:
if opt1[0] != 0 and opt1[0] <= n and opt1[1] != 0 and opt1[1] <= n:
if not opt1 in coordList:
validOptions.append(opt1)
if opt2[0] != 0 and opt2[0] <= n and opt2[1] != 0 and opt2[1] <= n:
if not opt2 in coordList:
validOptions.append(opt2)
if opt3[0] != 0 and opt3[0] <= n and opt3[1] != 0 and opt3[1] <= n:
if not opt3 in coordList:
validOptions.append(opt3)
if opt4[0] != 0 and opt4[0] <= n and opt4[1] != 0 and opt4[1] <= n:
if not opt4 in coordList:
validOptions.append(opt4)
# Break loop if there are no valid options
if len(validOptions) == 0:
gotStuck = gotStuck + 1
break
# Get random coordinate among current valid options
newCoord = random.choice(validOptions)
# Append new coordinate to the list of grid points visited (to be used
# for checks)
coordList.append(newCoord)
# Break loop if lower right corner of the grid is reached
if newCoord == [n, n]:
foundRoute = foundRoute + 1
break
# If the loop is not broken, assign new coordinates
i = newCoord[0]
j = newCoord[1]
k = k + 1
print 'Route found %i times' % foundRoute
print 'Route not found %i times' % gotStuck
source to share
Your problem is that you never clear your visited places. Modify the block that breaks out of the inner loop while
to look something like this:
if len(validOptions) == 0:
gotStuck = gotStuck + 1
coordList = [[1,1]]
i,j = (1,1)
break
You will also need to change your block, where you get:
if newCoord == [n, n]:
foundRoute = foundRoute + 1
coordList = [[1,1]]
i,j = (1,1)
break
Alternatively, you can just place this code right before the inner loop while
. The beginning of your code will look like this:
k = 0 # counter for number of simulations
n = 3 # Grid size
foundRoute = 0 # counter for number of cases where the final point is reached
gotStuck = 0 # counter for number of cases where no valid options found
while k < 100:
i,j = (1,1)
coordList = [[i,j]]
while True:
#Everything else
source to share