Check out the Latest Articles:
Simulating Board Games: Rejection Sampling

There are a lot of ways to analyse a board game scenario: you can try to work out the values analytically – that is, try to come up with an exact mathematical formula, or you can try to simulate real world scenarios with computer code, and see how often the situation you are looking for happens, or somewhere between these two methods.

The most basic technique of simulating a game is called rejection sampling. That is, you try your best to simulate every possible variable in a game (or in the piece you are studying), and then randomly pick values for the variables and measure the outcomes. After some amount of time, you just stop, and tabulate the results.

It's called rejection sampling because, typically, you are measuring the likelihood of one particular event happening, and you do this by randomly simulating as above, and throwing away all of the results where the event did not happen. It's by far the laziest and usually easiest way to measure something in a system such as a board game.

In addition to being the laziest way, it is also good for confirming the results of other types of analysis – it is unlikely for your rejection sampling technique to be wrong, unless the model is bad or the events you are trying to measure are extremely unlikely.

To demonstrate how I use rejection sampling, we can use it to confirm the Monty Hall riddle. Basically, you are a contestant on a game show, and are asked to pick on of three doors, behind one of which is a new car that you win if you pick it. After picking a door, the host then reveals one of the other doors without a car in it, and offers to let you switch your choice. So, should you switch? The answer is always yes, though I won't go into details: suffice it to say that it's a non-intuitive probability calculation. If you switch, you have a 2/3 chance of winning the car, and if you stay the course, you have a 1/3 chance of winning.

The following is a piece of Python code to simulate this using rejection sampling.

import random
# reproducible results
def monty_hall():
  doors = [0, 1, 2]
  winner = [0, 0, 1] # three doors, only one with a win
  random.shuffle(winner) # shuffle the doors
  mydoor = random.sample(doors, 1)[0] # pick a random door
  # reveal one of the two doors
  revealed = random.sample(doors, 1)[0]
  # sanity check: don't reveal the door with the prize
  if winner[revealed] == 1: revealed, doors = doors[0], [revealed]
  # would you like to switch to the other door?
  mydoor = doors[0] # switch
  return winner[mydoor]
# perform rejection sampling 10,000 times
total = 10000
wins = 0
for i in xrange(total):
  if monty_hall() == 1: wins += 1
print "Won:", 100.0 * wins / total, "percent of the time"

Produces the output:

Won: 66.68 percent of the time

The code is pretty straightforward as far as Python board game simulation code goes. There's no odd probability counting going on, no calls to permuted choice functions, no brute force or clever backtracking. Just simply doing a run and seeing if you win, repeat.

This demonstrates two key principles for board game simulations: you should almost always do some kind of rejection sampling code as a reality check of any other results you come up with, and probabilities are weird and often counter-intuitive, so tread lightly.

Photo — Debaird

  1. It‘s quite in here! Why not leave a response?