Hi-Ho! Cherry-O
Description
In this game, the players take turns spinning a wheel that tells them how many cherries to add to or subtract from their bucket. The object of the game is to fill your bucket with the 10 cherries on your tree. If your spinner lands on numbers 1-4 you take that number of cherries from your tree and put them in your bucket. If your spinner lands on either the dog or bird, then you take out two cherries from your bucket and place them on your tree. If your spinner lands on a spilt bucket, then you put all the cherries from your bucket back on the tree.
In this project, we analyze the game length using a Markov chain, by considering the number of cherries in the bucket as a state in state space. We construct an 11x11 transition matrix corresponding to each of the 11 possibilities (0-10 cherries). We only consider a single player in this analysis.
Downloads
Results
- Minimum game length: 3
- Expected game length: 15.8
- Maximum game length: Unbounded
- 50th percentile (median): 12
- 95th percentile: 40
- 25th percentile: 7
- 75th percentile: 21
Discussion
Markov chains are square matrices which describe probabilistic transitions between states. The (m,n) component of the matrix A corresponds to the probability that a player goes from n cherries to m cherries in one turn. The matrix A is a diagonal strip of non-zero entries. One band is two above the diagonal, corresponding to the bird/dog outcome. Then there are 4 bands below for the case where 1-4 cherries are removed. In addition, the first row corresponds to the case where the bucket is spilled.
An important problem in the universe of Hi-Ho! Cherry-O problems is to know roughly how long it takes to finish the game. Small children are unlikely to be willing to play a game that goes on and on. One may notice that the (11,1) entry in the matrix is zero. This means that the probability of the game ending on the first spin is zero, i.e., it is impossible for the game to end after one spin. To determine the probability that the game ends on the second spin, we can look at the (11,1) term of A^2=A x A -- this will also be zero. However, repeating this, we find a non-zero entry for A^3. This means that it is possible for the game to end after 3 moves. By iterating powers of A, we can find the probabilities of the game ending for each number N. We plot this below (probability density function).
We remark that since A is an 11x11 matrix, it's not practical to analyze powers by hand. Hence, we employ Matlab to compute for us (see link for Matlab code above).
There is no maximum game length. In other words, it's theoretically possible for a game of Hi-Ho! Cherry-O to last forever. However, it is not likely. Hence, to answer the impending question of how long does it take to play a game of Hi-Ho! Cherry-O, we look at the probability distribution function and report the percentile rankings. We see that half of the players will finish the game in 12 (or less) spins. We also see that 95 percent of the time, the game will not exceed 40 spins. We also see that the middle range is between 7 and 21 spins.
- Minimum game length: 3
- Expected game length: 15.8
- Maximum game length: Unbounded
- 50th percentile (median): 12
- 95th percentile: 40
- 25th percentile: 7
- 75th percentile: 21
Discussion
Markov chains are square matrices which describe probabilistic transitions between states. The (m,n) component of the matrix A corresponds to the probability that a player goes from n cherries to m cherries in one turn. The matrix A is a diagonal strip of non-zero entries. One band is two above the diagonal, corresponding to the bird/dog outcome. Then there are 4 bands below for the case where 1-4 cherries are removed. In addition, the first row corresponds to the case where the bucket is spilled.
An important problem in the universe of Hi-Ho! Cherry-O problems is to know roughly how long it takes to finish the game. Small children are unlikely to be willing to play a game that goes on and on. One may notice that the (11,1) entry in the matrix is zero. This means that the probability of the game ending on the first spin is zero, i.e., it is impossible for the game to end after one spin. To determine the probability that the game ends on the second spin, we can look at the (11,1) term of A^2=A x A -- this will also be zero. However, repeating this, we find a non-zero entry for A^3. This means that it is possible for the game to end after 3 moves. By iterating powers of A, we can find the probabilities of the game ending for each number N. We plot this below (probability density function).
We remark that since A is an 11x11 matrix, it's not practical to analyze powers by hand. Hence, we employ Matlab to compute for us (see link for Matlab code above).
There is no maximum game length. In other words, it's theoretically possible for a game of Hi-Ho! Cherry-O to last forever. However, it is not likely. Hence, to answer the impending question of how long does it take to play a game of Hi-Ho! Cherry-O, we look at the probability distribution function and report the percentile rankings. We see that half of the players will finish the game in 12 (or less) spins. We also see that 95 percent of the time, the game will not exceed 40 spins. We also see that the middle range is between 7 and 21 spins.
Markov chains are square matrices which describe probabilistic transitions between states. The (m,n) component of the matrix A corresponds to the probability that a player goes from n cherries to m cherries in one turn. The matrix A is a diagonal strip of non-zero entries. One band is two above the diagonal, corresponding to the bird/dog outcome. Then there are 4 bands below for the case where 1-4 cherries are removed. In addition, the first row corresponds to the case where the bucket is spilled.
An important problem in the universe of Hi-Ho! Cherry-O problems is to know roughly how long it takes to finish the game. Small children are unlikely to be willing to play a game that goes on and on. One may notice that the (11,1) entry in the matrix is zero. This means that the probability of the game ending on the first spin is zero, i.e., it is impossible for the game to end after one spin. To determine the probability that the game ends on the second spin, we can look at the (11,1) term of A^2=A x A -- this will also be zero. However, repeating this, we find a non-zero entry for A^3. This means that it is possible for the game to end after 3 moves. By iterating powers of A, we can find the probabilities of the game ending for each number N. We plot this below (probability density function).
We remark that since A is an 11x11 matrix, it's not practical to analyze powers by hand. Hence, we employ Matlab to compute for us (see link for Matlab code above).
There is no maximum game length. In other words, it's theoretically possible for a game of Hi-Ho! Cherry-O to last forever. However, it is not likely. Hence, to answer the impending question of how long does it take to play a game of Hi-Ho! Cherry-O, we look at the probability distribution function and report the percentile rankings. We see that half of the players will finish the game in 12 (or less) spins. We also see that 95 percent of the time, the game will not exceed 40 spins. We also see that the middle range is between 7 and 21 spins.