## 23 December 2008

### The Mathematics of ... Candyland???

I mentioned Markov-chains a while back (not to be confused with Markov Chaney), and I though that might make an interesting topic to relate to games. It seems though that several many others have beaten me to the punch, and written very well on this subject, so instead I'm going to point out one or two other fine efforts, review, and comment.

[Image taken from lscheffer.com, who also has a nice analysis.]

In my own words, a Markov-chain is a series of random states. A trivial example might be flipping a coin; the coin is either in a state of "heads" or "tails" and has a 50% chance of changing state with each flip. It can get more complicated, with the probabilities of changing to a different state dependent on the current or even (correct me if I am wrong) previous states. A state which ends the series (if any) is called an absorbing state. In my recent Netrek post the number of planets a team controls would be the state, and the absorbing state would be one team conquering all the planets, thus ending the series and the game (oversimplified, but true).

Candyland is a Markov-chain if you reshuffle the deck of cards after every draw. Each square (rhomboid?) on the board represents a state, and players advance randomly towards the end of the game. Reshuffling is required so that the probability of changing states remains independent of previous card-draws (if you were wondering). There is a nice summary and history of the game itself here.

Speaking of fine work, Greg Costikyan wrote about this a few weeks back, and it has traveled far in the blogosphere. The really interesting part here is (for me) the discussion of whether or not it really is a game; all moves are random, so if the player doesn't actually do anything is it really a game? My answer: Yes. Not the most interesting game we may ever play by any means, but most definitely a game. Games where players make decisions and enact strategies are more difficult, and for most, more interesting.

I should not end without mentioning an older game that is a Markov-chain to start with - no reshuffling required - known to most as Snakes and Ladders.

[Image from DKimages]