%countchicks.tex:  Using Symbolic Computation to analyze the "Count Your Chickens!" Board Game
%%a Plain TeX file by Shalosh B. Ekhad and Doron Zeilberger (x pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\C{{\cal C}}
\def\N{{\cal N}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\M{{\cal M}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf  
Using Symbolic Computation to analyze the "Count Your Chickens!" Board Game
}
\bigskip
\centerline
{\it Shalosh B. EKHAD and Doron ZEILBERGER}
\bigskip


{\bf 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, {\tt CountChickens.txt}, that can handle, in a few seconds,
{\it any} such game, not just this particular one.


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

{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/countchicks.html} \quad .



{\bf 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 {\it competitive}, there
being a winner and {\it 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\dots$, and got a slightly higher value for the expected number of chicks, namely
$39.32230439142343\dots$ . We believe that they had a typo.

One of us (DZ) wrote a  Maple package {\tt CountChickens.txt}, mentioned above, that can handle, very fast, {\it 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

$\bullet$ 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.

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

$\bullet$ a subset of $\{1, \dots , N\}$ called the set of {\it 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 {\bf 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.START \,, \, 1. EMPTY \, 2. SHEEP \, 3. COW \, 4. EMPTY \, 5. COW \, 6. EMPTY, 7. SHEEP \, 8. \{COW,SHEEP\} \quad,
$$
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 {\it pre-umbra}.

In the [MM] simplied game we have
$$
s^0 \rightarrow \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^3t^3 )
$$
$$
F(t) s^2 \rightarrow \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^5t^4)
$$
$$
F(t) s^3 \rightarrow \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 \rightarrow \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 \rightarrow \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 \rightarrow F(t)s^8
$$
(since $8$ is an {\it 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}, \dots$ 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^3t^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.

{\bf Input}: A general Count Your Chickens! game, and two variables $t$ and $X$.

{\bf 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 \dots, K$,

$$
Q_0(X,t)=s^0 \quad, \quad  R(X,t):=0
$$
$$
Q'_i(X,t)= T( Q_{i-1}(X,t) )  \quad ,
$$
$$
$$
$$
Q_i(X,t)= Q'_i(X,t)- (Coefficient \quad of \quad s^N in  Q'_i(X,t))s^N
$$
$$
R(X,t):=R(X,t)+(Coefficient \quad of \quad s^N in  Q'_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


{\bf References}

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

\bigskip
\hrule
\bigskip
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. \hfill\break
Email: {\tt ShaloshBEkhad at gmail dot com}   \quad .
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt DoronZeil at gmail  dot com}   \quad .
\bigskip
\hrule
\bigskip
{\bf Exclusively published in the Personal Journal of Shalosh B.  Ekhad and Doron Zeilberger and arxiv.org \quad .}
\bigskip
\hrule
\bigskip
Written: July 12, 2019.
\end







