Using Symbolic Computation to analyze the ”Count Your Chickens!” Board Game

Shalosh B. EKHAD and Doron ZEILBERGER

Abstract. In a delightful recent article that appeared in Mathematics Magazine, David and Lori Mccune analyze the board game ”Count Your Chickens!”, recommended to children three and up. Alas, they use the advanced theory of Markov chains, that presupposes a knowlege of linear algebra, that few three-years-olds are likely to understand. Here we present a much simpler, more intuitive, approach, that while unlikely to be understood by three-year-olds, will probably be understood by a smart 14-year-old. Moreover, our approach accomplishes much more, and is more efficient. It uses symbolic, rather than numeric computation. The article is accompanied by a general Maple package, CountChickens.txt, that can handle, in a few seconds, any such game, not just this particular one.

The Maple package. This article is accompanied by a Maple package CountChickens.txt that can be obtained, along with an input and output file, from the front of this article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/countchicks.html .

The Count Your Chickens! board game

The games ”Snakes and Ladders” (that became ”Chutes and Ladders” in the USA, since snakes are too scary) is too stressful for the gentel soul of a typical three-year-old. Hence CandyLand that involves picking colored cards, rather than spinning a spinner, is not recommended, since it is competitive, there being a winner and loser, and three-years-old (and not only) hate to lose, making them cry. Hence game inventor, Peggy Brown came up with a fun, stress-free, ‘cooperative’ game for kids, where there is only one team and ‘everyone wins together and loses together’ (so it is really a solitaire game) called ”Count Your Chickens!” manufactured and marketed by the Peaceable Kingdom toy company.

In a delightful article that appeared recently in Mathematical Magazine, the mathematical couple David and Lori Mccune, who play this game with their young children, use the sophisticated theory of Markov Chains, that entails a knowledge of matrices, and matrix inverses to compute the probability of winning, and the expcted number of chicks at the end. They got 0.6410 for the probability and 39.22 for the expected number of chicks (see below). Our, simpler, faster, and more efficient approach agrees with their probability, but gave the more precise value of 0.6410373996231 …, and got a slightly higher value for the expected number of chicks, namely 39.32230439142343 …. We believe that they had a typo.

One of us (DZ) wrote a Maple package CountChickens.txt, mentioned above, that can handle, very fast, any such kind of tame. So let us first define an ‘abstract’ Count Your Chickens! game.

Let N and K be two positive integers.

The game consists of

• a board with 1 + N squares where the 0-th location is the starting place of Mama Chicken and N is the terminal square. Each square is either empty or labelled with of K animals.

• a spinner with K + 1 choices, all equally likely, labelled by the K farm animals, plus an extra one called the Fox.

• a subset of {1, …, N} called the set of blue squares.

The rules are as follows. Mama Chicken starts out at location 0. At every turn, the player spins the spinner. If it is a Fox, then you lose a chick (if you currently have no chicks, then nothing happens) and stay where you are. Otherwise you go to the first location labelled by the animal that you got. The three-year-old counts the number of squares moved and collects that number of chicks. If the new location is a blue square, then you get an extra chick.

Sooner or later, with probabilty 1, you would get to the last square, that is labelled by all the K animals.

If win the game if you have at least N chicks, and you lose otherwise.

In the simplified example of [MM], N=8, K=2, the board is

0.ST ART , 1.EMP T Y 2.SHEEP 3.COW 4.EMP T Y 5.COW 6.EMP T Y, 7.SHEEP 8.{COW, SHEEP } ,

and the set of blue squares is {2.5}.

In the original version, K = 5 and N = 40.

In [MM] the game is modeled as a Markov chain with a huge number of states, essentially O(N^{2}). For the problem of just computing the probability of winning (for N = 40), they manage to reduce it considerablly 163), but for the hader problem of computing the expected number of chicks they needed 668 states, and the matrices were huge.

Our approach is also, essentially a Markov chain, but we don’t use any of the standard theory, and our number of states is O(N) (obviously the EMPTY squares can be ignored). We use Gian-Carlo Rota’s seminal idea of an ‘umbral operator’.

Let f_{i}(t) be the probability generating function of lending at square i, where the coefficient of t^{j} is the probability that you currently have j chicks. To indicate that is currently at location i we will denote it by s^{i}f_{i}(t). If you got a Fox this becomes s^{i}f_{i}(t)/t (followed by replacing t^{−1} by 1, if necessary). Otherwise, the Chicken goes to a new location, let’s call it j, and the new state becomes s^{j}f_{i}(t)t^{j−i} if j is not a blue square, and s^{j}f_{i}(t)t^{j−i+1} if it. If we get a power of t larger than N, we replace it by t^{N}.

This introduces an ‘evolution operation’ that we call the pre-umbra.

In the [MM] simplied game we have

s^{0} → \frac{1}{3}(s^{0} + s^{2} t^{2−0+1} + s^{3} t^{3−0} = \frac{1}{3}(1 + s^{2}t^{3} + s^{3}t^{3})

F (t)s^{2} → \frac{F (t)}{3}(s^{2}/t + s^{3} t^{3−2} + s^{5} t^{5−2+1} = \frac{F (t)}{3}(s^{2}/t + s^{3}t + s^{5}t^{4})

F (t)s^{3} → \frac{F (t)}{3}(s^{3}/t + s^{5} t^{5−3+1} + s^{7} t^{7−3} = \frac{F (t)}{3}(s^{3}/t + s^{5}t^{3} + s^{7}t^{4})

F (t)s^{5} → \frac{F (t)}{3}(s^{5}/t + s^{7} t^{7−5} + s^{8} t^{8−5} = \frac{F (t)}{3}(s^{5}/t + s^{7}t^{2} + s^{8}t^{3})

F (t)s^{7} → \frac{F (t)}{3}(s^{7}/t + s^{8} t^{8−7} + s^{8} t^{8−7} = \frac{F (t)}{3}(s^{5}/t + s^{7}t^{2} + s^{8}t^{3})

F (t)s^{8} → F (t)s^{8}

(since 8 is an absorbing state). This must be followed by a ”clean-up” operation. Replacing t^{−1} by 1 (you can’t have a negative number of chicks), and replacing t^{9}, t^{10}, … by t^{8}. This is the preumbra, defined on every monomial s^{i}, let’s call it T. If we have a polynomial in s (and of course t), we extend it by linearity. It is readily seen that applying this operator, starting with the initial state s^{0}, describes the ‘evolution’ of the process. While, in principle, the game can last for over (you keep getting foxes), life is finite, so we decide that we are only playing K rounds. The probability generating function after 1 round is T (s^{0}) = \frac{1}{3}(1 + s^{2}t^{3} + s^{3}t^{3}). After two rounds is T^{2}(s^{0}). Sooner or later we will encounter s^{8} (in general s^{N}), here is our algorithm. Let X be yet another variable. Input: A general Count Your Chickens! game, and two variables t and X. Output: A polynomial P (X, t) of degree K in X and degree N in t, such that the coefficient of X^{i} is the probability generating function of the number of chicks you ended with, assuming that you ended after exactly i rounds. It also outputs the probability of the game lasting longer than K rounds. We define recursively for i = 0 …, K,

Q_{0}(X, t) = s^{0} , R(X, t) := 0
Q′_{i}(X, t) = T (Q_{i−1}(X, t)) ,

Q_{i}(X, t) = Q′_{i}(X, t) − (Coefficient of s^{N}inQ′_{i}(X, t))s^{N}
R(X, t) := R(X, t) + (Coefficient of s^{N}inQ′_{i}(X, t))X^{i}

If you roll a Fox, then the new porbabil

At the beginning Mama Chicken is located at the START square, and N is the number of squares.

The game consists of a spinner with K + 1 e

References

[MM] David Mccune and Lori Mccune, Counting your chickens with Markov chains, Mathematics Magazine 92 (2019), 162-172.

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org .

Written: July 12, 2019.