Application of Markov Chain to Game of Life Board Game

1.3k Views Asked by At

I need to calculate the expected outcomes for the Game of Life. I believe that if I multiply the probability of landing on a particular square with the payoff of said square and add up all these values, I can get the expected payoff for the entire path of the board, at least I think thats how I can calculate the expected outcome.

I was thinking of using a Markov Chain to calculate the probabilities of landing on the squares. I made the transition matrix P like so with each "state" corresponding to a square on the board ($s_1$ is the first square, $s_2$ is the second square, etc. The board forks in various places, but I would only be considering 1 path ata time for the transition matrix)

$$ P = \begin{bmatrix} 0 & 1/10 & 1/10 & 1/10 & ... & 0\\ 0 & 0 & 1/10 & 1/10 & ... & 0 \\ ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & ... & 0 & 1 \end{bmatrix} $$

(Im using 1/10 because the spinner on the board game goes from 1-10)

The last state represents the end, which is "Millionaire acres" or the farm place (name's not important). It's an absorbing state so this is an absorbing Markov Chain. All the other squares are transient states (I believe, I'm still new to Markov Chains). According to my online research, I can find the probability of landing on transient state j from transient state i from the ij entry of the matrix H where

$$ H = (N - I)N_{dg}^{-1} $$

N is the fundamental matrix and I is the identity matrix. Will adding up the columns from H give me the overall probability of landing on a certain square, for example, a square where there's a salary payoff? Or am I doing all of this incorrectly?

Any help that would clarify this would be greatly appreciated.