Computational Methods for Games 2: Markov Chains

In many games, tabletop or otherwise, there are a series of positions, board states, or other features that occur in some kind of order. In monopoly, for example, you travel in a circle. Each property is a ‘state’ that your piece (battleship!) can be in. In something like Candyland, Chutes and Ladders, or Mr. Bacon’s Big Adventure, there is a goal state to reach, and you do things (roll die, draw cards, etc.) to try to get there.

What makes these more complicated than say, just figuring the combined probability of rolling a certain sum for many die, is that the game states branch. Branching just means that you can reach more than 1 state after your current one. Markov Chains are a powerful tool for analyzing a game’s progress through it states, and this post will show you an example of that, using the game Betrayal at House on the Hill.

Markov Chains

Markov chains (MCs) are fairly simple in their concept. An MC contains a finite number of states (it doesn’t have to, but we don’t have to worry about that) in its state space. For Monopoly, the state space could be all the spots that you can land on. For Zombie Dice, it could be the number of brains, shotguns, and the set of die in the cup. The other property that an MC needs to have is that it must be ‘memoryless’.

By ‘memoryless’, we just mean that the probabilities of transitioning from the current state to a new state do not depend on the sequence of events that got us to the current state. In Monopoly, it doesn’t matter how you got to Park Place. The chances of passing GO are the same no matter what.

Markov Chains work in ‘steps’ or ‘turns’. Given a current state, the MC will tell you (with a matrix multiplication) what states you might end up in, and with what probabilities. If you repeat that for several turns, you’ll build a probability distribution of which game states you might end up in.

Absorbing Markov Chains

It is possible for a state to return to itself with some probability. In Monopoly, there is a chance that you stay in jail a couple of turns. That’s based on the probability of rolling doubles. If a state returns to itself with a probability of 1 (in other words, that state cannot be exited), then it is called absorbing.

Absorbing MCs are analyzed in a bit different way. Regular MCs can be used to find a ‘steady state distribution’, which is just the probability of being in every state after an infinite number of moves. Absorbing MCs don’t have a steady state, because after an infinite number of moves, you can only be in one of the absorbing states.

What you can find, though, are things like the expected number of moves to ‘absorb’. If you have a game with a goal state, this lets you calculate how many turns it might take to win on average!

Some Markov Math

Markov chains are built around what is called a transition matrix. For obvious reasons, I like to call that matrix T The T matrix is an n x n matrix, where n is the number of states. The entry T[i,j] represents the probability of moving from state i to state j.

The sum of each row must equal 1:

\sum^n_{j=1} T[i,j] = 1

This just follows the rules of probabilities and state spaces. A state cannot have anything other than a probability of 1 to transition during each step. Absorbing states transition only to themselves.

The only other thing to cover right now is how to do states. Markov chains use a row vector with n entries to represent the probabilities of being in any state. This vector is usually denoted as \pi. The ith entry of \pi equals the probability that you are in state i.

To take a step (from the 0th turn to the 1st turn) in the MC, we just do:

\pi_1 = \pi_0 T

This generalizes to, for k turns:

\pi_k = \pi_0 T^k

That covers the real basics. Let’s move on to an actual game!

Betrayal!

The Rules (that we care about)

Full disclosure: I’ve never actually played Betrayal at House on the Hill. From reading about it, though, it looks like a really fun game! There was a question on the boardgame subreddit about the chances of meeting certain conditions on a roll (side note, Reddit user zebraman7 has been asking several game math problems, which you should try on your own!).

The question was already solved, but there was a lot of talk about a key mechanic in the game. In Betrayal, players explore rooms (that are drawn from a pile) on their turns. Based on how far they can walk, they can open up new rooms. New rooms contain symbols that direct the player to draw certain kinds of cards and act on them. One set of cards is the ‘Omen’ set. Omens control an important game transition.

Every time a player pulls an omen card, they must roll 6 die (each with sides 0,0,1,1,2,2). If the sum is less than the number of omen cards that have been drawn, then the game changes phases (a haunting happens). I was curious about how many turns it might take to reach that phase change.

Thinking Markov

A Markov chain is a good idea for answering that question because we have the following features in the question:

  • Probabilities of getting omen cards
  • Probabilities of not getting omen cards
  • Probabilities of rolling certain sums (that can cause the game to change
  • A defined goal state (the state after failing a roll on an omen card)

We need to figure out what the states are going to be. It would be incredibly complex (and require defining a strategy) to keep track of each player and worry about the probabilities (or desires) for actually opening up new rooms! To avoid this, we will assume that on every turn, someone opens up a new room. Notice that this means that any estimates for the number of turns will be a lower bounds, relative to real game play.

With that assumption, we can define a state as: (number of omen rooms in play, number of rooms in play). With those two values, we can calculate the probability of drawing an omen or non-omen card.

Making the States

I made the states using the following python code. There are 13 omen rooms in 45 total rooms. I assumed that the starting room the same each time (based on the tutorial on their site), so I knocked down the room count to be 44 draw-able rooms.

n_rooms = 44
states = [(0,0)]
for state in states:
    n_omen = state[0]
    n_cards = state[1]
    omen_left = 13-n_omen
    non_omen_left = n_rooms-n_cards-omen_left
    if omen_left > 1:
        # then we can draw an omen
        v = (n_omen+1,n_cards+1)
        if v not in states:
            states.append(v)
    if non_omen_left >= 1:
        # then we can draw a card
        v = (n_omen,n_cards+1)
        if v not in states:
            states.append(v)
 
states.append("haunting")

Once you reach 13 omens you can’t win, so I ignored states with 13 omens. This gives us 417 possible game states!

Building the Transition Matrix

To build the T matrix, I looped over each state and calculated the probabilities of moving to the states that it could move to (add 1 omen and roll high, add 1 room, or add 1 omen and roll low). I used Python’s fractions library to try to avoid the usual floating point errors that plague this sort of thing, but NumPy arrays convert them right to floats. The error is small, so I just ignored it.

import numpy as np
# Not shown: making the roll_probs dictionary. That dictionary
# just contains the probability of rolling a particular sum
# ...
n_states = len(states)
T = np.zeros((n_states,n_states))

for i,u in enumerate(states):
    if u == "haunting":
        # this is the absorbing goal state
        T[i,i] = 1.0
    else:
        # get the probability of drawing an omen card
        p_omen = fractions.Fraction(13-u[0],n_rooms-u[1])
        if u[0] + 1 <= 12:
            v = (u[0]+1,u[1]+1)
            p_survive = sum(p for val,p in roll_probs.items() if val >= u[0]+1)
            j = states.index(v)
            T[i,j] = p_omen*p_survive
            # set the probability of the haunt hitting
            T[i,-1] = p_omen*(1-p_survive)
        elif u[0]+1 == 13:
            # then we lose no matter what on an omen draw
            T[i,-1] = p_omen
        # the probability of drawing a non-omen room
        # we can only add non-omen rooms if there are any to add
        if u[1] + 1 <= n_rooms and u[1] + 1 <= n_rooms-(13-u[0]):
            v = (u[0],u[1]+1)
            j = states.index(v)
            T[i,j] += 1-p_omen

Calculation!

With the transition matrix in hand, we can start doing estimations of various kinds. Let’s start by finding out where we might be after two turns of drawing rooms. To find this, we do (in math, then code):

\pi_2 = \pi_0 T^2

init_state = np.zeros(n_states)
# we put a 1 in the first index to indicate that we are in the first state
init_state[0] = 1

final_state = np.dot(init_state,np.linalg.matrix_power(T,2))

These are the results, which show the states that can be reached in 2 steps, along with the probability that we are in those states:

End state  : Probability
------------------------
    (2, 2) : 0.0815
    (1, 2) : 0.4254
    (0, 2) : 0.4915
'haunting' : 0.0015

Note how unlikely it is to reach the haunting stage this early. It’s also fairly unlikely to draw two omen rooms in a row, since we have a full stack of room cards.

We can repeat this for all the possible turn numbers. Remember that we can’t take more than 44 turns. At the 44th turn (if we somehow get there) we would pull an omen room and not be able to win the roll. Using the following code to get the probabilities of being in the final state for each turn length:

init_state = np.zeros(n_states)
init_state[0] = 1
curr_state = init_state

turn_probs = []
for n_turns in xrange(n_rooms+1):
    next_state = np.dot(curr_state,T)
    turn_probs.append(next_state[-1])
    curr_state = next_state

The probabilities that we just got are shown below:

TurnEndingProbs

It looks like we reach a 50/50 shot of the game phase change around 18 to 19 turns. In other words, after 18 turns you’re nearly equally likely to still be un-haunted as you are likely to have reached the haunted state.

Absorption Chances

When working with an absorbing MC, there is some nice math that lets us get what is called the N matrix. That matrix gives the expected number of visits to a transient (non-absorbing) state j starting from a transient state i (before being absorbed). We use that matrix to get a t vector, which is a vector of the expected number of steps it will take to get from state i to absorption (reaching our goal). The first entry of that vector is the expected number of turns to reach the game phase shift.

Here’s the code to get that vector:

Q = T[:-1,:-1]
R = T[:-1,-1].T
Ir = np.array([[1]])

N = np.linalg.inv(np.eye(n_states-1)-Q)
t = np.dot(N,np.ones(n_states-1))
# the expected number of turns
t[0]

The result is that we expect 19.38 turns, on average, until the phase shifts. Remember that this is a conservative estimate due to our simplifying rules.

We could have also found that number by recognizing that the plot we made above is a Cumulative Distribution Function (CDF). We can convert that to the Probability Mass Function (PMF), because the difference between each CDF point is the PMF value.

That gives us this PMF:

TurnHauntingProbs

The expected value of that PMF is 19.38! What’s neat about this is that it shows how the matrix math we just did essentially builds PMFs for each state, and then does the weighted summation to get the expected value.

Chances of Reaching Other States

The chances of reaching 32 or more turns looks really slim. We can use the chart from above to calculate the chance of reaching one of those turns. All we have to do is recognize that 1 minus the CDF of haunting by a turn is the probability of reaching that turn. Here’s the CDF of probabilities for reaching at least a given turn:

TurnReachingProbs

Notice that we have a 100% chance of getting more than 1 turn, so we’ve done the math right. We only have a ~10% of getting 28 turns or more. For 32 turns or more, that probability is 2.31%!

Finally, let’s get the probability for reaching what is probably a very unlikely state: only omen rooms left in the pile.  Using the H matrix that the wiki page references, we get the probability of reaching that state to be: 1.926e-11. If you’re seeing that, someone probably stacked the deck.

Wrap-Up

We’ve seen how Markov Chains can be used to estimate properties of playing games, especially turn counts and probabilities of being in a given state. I think some of the key takeaways are:

  1. It’s OK to simplify a problem to make it tractable by MC methods
  2. The hardest part is defining the states. The rest is just basic probability and some matrix math
  3. Goal states (absorbing chains) are the key to letting us find out things like “how many turns should I expect to take”, which is a big question for planning in games
  4. To be discussed: Markov Chains are best for understanding very low probability events

I recommend also simulating with Monte Carlo and comparing the results. It’s also helpful to compare the time it takes to code and run these things, because that’ll help you decide which methods you prefer! Keep in mind things like accuracy and state space coverage. With the probability of having only all the omens left in the stack being so small, how many Monte Carlo runs would it take for you to find it?

Finally, let the Markov stuff be a fun project to learn more about your favorite games, but don’t get bogged down in Analysis Paralysis. If you do play with someone who takes forever on a turn, this kind of method might help you plan how long your game will take!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s