Playing Odd-Even Cricket, is there a perfect strategy

Question

This is a simple two-player game. One if the people is picked to 'bat'.

Both players simultaneous choose a number from 1 to 6. (When playing against a person, you use your hands to show the number). If both players show the same number, the person 'batting' is out. Otherwise, the person batting gets points (runs) equal to the number he picked.

This process repeats until the person batting is out. His final score is the sum of all the points he scored.

The person batting and the other player switch roles. The same process occurs. Whoever scored more points wins.

Is there a perfect strategy for this game?

When playing against a computer, you stand exactly 1/2 chance of winning. You may sometimes be able to predict humans and play better. Assume you don't know who you are playing? Is the perfect strategy just to always pick random numbers, or to predict the opponent's future moves based on his current ones?

Answer 1

First a word on the concept of a "perfect strategy". This is a math site, so if you ask about games here, people (including me, below) will give you mathy answers based on mathematical game theory. Don't listen to them. If you know your friend's lucky number, you may well be better off trying to make use of that than assuming that your friend is the hypothetical hyperrational creature that game theory presupposes.

That having been said, the game-theoretical concept that approximates that of a "perfect strategy", namely a Nash-equilibrium pair of strategies, does have practical value. It doesn't try to make use of your opponent's psychological weaknesses but it also doesn't allow your opponent to make use of yours. It's defined as a pair of strategies such that neither player can gain from switching strategies.

It turns out that your game is a very nice example to apply the theory of Nash equilibria to, and we can go a longer way towards "solving" it than one might think at first sight. Some of the results are surprising – for instance, it turns out that the players play quite asymmetric roles and the strategy of one of them is much closer to a uniform distribution over the numbers than that of the other.

For definiteness, I'll assume that the player who bats first wins in case of a tie in the scores.

We'd like to treat each of the "throws" of two numbers being chosen as a separate game, but we don't initially know the payoffs for these, since they depend on later throws. In such a situation, backward induction is useful, that is, reasoning backwards from the end of the game where the payoffs are known.

So let's consider the second "innings", in which the second player bats. When she misses (i.e. the numbers are equal), she loses, with payoff $0$. If she reaches more runs than her opponent, she wins, with payoff $1$. If she scores runs but doesn't win yet, the payoff is the expected value for the new score difference, some number between $0$ and $1$. Let's call the expected payoff when she scores $i$ runs $v_i$. Then the payoff matrix is

$$ \pmatrix{ 0&v_1&v_1&v_1&v_1&v_1\\ v_2&0&v_2&v_2&v_2&v_2\\ v_3&v_3&0&v_3&v_3&v_3\\ v_4&v_4&v_4&0&v_4&v_4\\ v_5&v_5&v_5&v_5&0&v_5\\ v_6&v_6&v_6&v_6&v_6&0\\ }\;. $$

Let $p_i$ be the probability with which the batter chooses $i$, and $q_j$ the probability with which the bowler chooses $j$. Then the expected payoff is

$$ V=\sum_i\sum_{j\neq i}p_iq_jv_i=\sum_ip_iv_i\sum_{j\neq i}q_j=\sum_ip_iv_i(1-q_i)\;. $$

At equilibrium, all numbers have non-zero probabilities: If $q_k$ were zero, the batter could steal runs for free by choosing $k$, and if $p_k$ were zero, the bowler would benefit from switching to a strategy with $q_k$ zero. Thus, the derivative of the expected payoff with respect to all $p_i$ and $q_j$ must vanish, where we need to include Lagrange multiplier terms $\lambda\sum_i p_i$ and $\mu\sum_j q_j$ in the payoff to account for the normalization conditions $\sum_ip_i=1$ and $\sum_jq_j=1$, respectively. Then

$$v_i(1-q_i)=\lambda$$

and

$$v_ip_i=\mu\;.$$

Solving for $p_i$ and $q_i$ and using the normalization conditions yields

$$\frac\lambda5=\mu=\left(\sum_jv_j^{-1}\right)^{-1}\;,$$

$$\frac{1-q_i}5=p_i=v_i^{-1}\left(\sum_jv_j^{-1}\right)^{-1}\;.$$

Substituting into the expected payoff gives

$$ V=\sum_ip_iv_i(1-q_i)=5\left(\sum_jv_j^{-1}\right)^{-1}\;. $$

If you're like me, all those reciprocals are beginning to get on your nerves, so let's get rid of them by considering the reciprocals $R=1/V$ and $r_i=1/v_i$ of the payoffs. That makes things look a whole lot nicer:

$$ \frac{1-q_i}5=p_i=\frac{r_i}{\sum_jr_j}\;, $$

$$ R=\frac{\sum_jr_j}5\;. $$

So the solution is actually surprisingly simple: the batter should choose probabilities proportional to the reciprocal payoffs, the bowler should choose "avoidances" proportional to the reciprocal payoffs, and the reciprocal expected payoff is just a slightly scaled average of the reciprocal payoffs (scaled because the average would have a $6$ where the result has a $5$).

Since this is all so nicely linear now, we can actually solve the second innings analytically. Assume we know the reciprocal expected payoffs for score differences of $k-1,\ldots,k-6$; denote them by $R_{k-1},\ldots,R_{k-6}$. Then $R_{k-i}$ is the payoff $v_i$ in the game at score difference $k$. We can calculate $R_k$ and form a new vector of six values $R_k,\ldots,R_{k-5}$, and since everything turned out to be linear (in the reciprocals), we can write this as a matrix multiplication:

$$ \pmatrix{R_k\\R_{k-1}\\R_{k-2}\\R_{k-3}\\R_{k-4}\\R_{k-5}}= \pmatrix{ 1/5&1/5&1/5&1/5&1/5&1/5\\ 1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ } \pmatrix{R_{k-1}\\R_{k-2}\\R_{k-3}\\R_{k-4}\\R_{k-5}\\R_{k-6}}\;, $$

which is a recurrence relation of the form $\vec x_k=A\vec x_{k-1}$, with solution $\vec x_k=A^k\vec x_0$ (where the initial value $\vec x_0$ is a vector of all $1$s representing the wins from hitting any number at score difference $0$). We could use the spectral decomposition of $A$ to write $\vec x_k$, and hence $R_k$, and hence $V$ and the $p_i$ and $q_i$ at every step, in closed form.

Unfortunately the eigenvalues of $A$ turn out not to have analytical forms. Sage finds that the largest (and the only one with magnitude $\ge1$) is $\lambda_{\mathrm{max}}\approx1.054717925023537$, and its minimal polynomial is the characteristic polynomial of $A$, $x^6-\sum_jx^j/5$. For large $k$ this eigenvalue dominates, and the $R_k$ approximately form a geometric sequence, $R_k\approx\lambda_{\mathrm{max}}^k$. Thus, in the long run, the expected payoff drops by a factor of $\lambda_{\mathrm{max}}$ for every point of score difference.

Since the eigensystem of the matrix isn't nice, I didn't bother to decompose the initial vector of $1$s into its eigencomponents to explicate the analytical solution; instead I wrote a Java program to calculate the (rational) probabilities and payoffs.

These are the $p_i$ at score differences up to $25$ ($i=1$ brown at the top; $i=6$ red at the bottom):

These are the $q_i$ at score differences up to $25$ ($i=1$ again brown, now at the bottom; $i=6$ again red, now at the top):

And this is a logarithmic plot of the expected payoffs at score differences up to $25$, with a line of slope $-\log\lambda_{\mathrm{max}}$ fitted to the last $10$ of them:

Note that the limiting probabilities (with $1-q_i^\infty=5p_i^\infty\propto \lambda_{\mathrm{max}}^{-i}$) are quite similar to the ones that Micah got by optimizing the expected number of runs; they're approximately given by

$$ \begin{array}{c|c|c} i&p_i^\infty&q_i^\infty\\ \hline 1&0.18962&0.05188\\ 2&0.17979&0.10107\\ 3&0.17046&0.14770\\ 4&0.16162&0.19192\\ 5&0.15323&0.23384\\ 6&0.14528&0.27359 \end{array} $$

Unfortunately, the first innings is considerably harder to treat, for two reasons: There's no starting point to begin at and work backwards from, and we no longer have $0$s on the diagonal of the payoff matrix, since the expected payoff in case of a miss is minus the expected payoff of the second innings, with score difference the score achieved so far. This second problem we can solve by subtracting this "losing payoff" from all payoffs to get back to $0$s on the diagonal. This constant additive shift doesn't change the strategies, but it does destroy the linearity of the reciprocal payoffs.

To at least get an accurate computational solution, let's determine the asymptotic behaviour for large games. Then we can start with a good approximation at some unrealistically high score and work our way backwards. A moment's reflection shows that the expected payoffs must have the same long-term decay rate as the ones in the second innings and hence must asymptotically be given by $W_k=-cV_k$, where $k$ is the score and $c\gt0$ is yet to be determined. The payoff for missing at $k$ is $-V_k$ (since this starts the second innings with a score difference of $k$), and the payoff for scoring $i$ runs is $W_{k+i}$. Thus, subtracting $-V_k$ from all payoffs and adding it back in the expected payoff, we obtain

$$ \frac1{W_k+V_k}=\frac15\sum_i\frac1{W_{k+i}+V_k}\;, $$

and thus

$$ \frac1{1-c}=\frac15\sum_i\frac1{1-c\lambda_{\mathrm{max}}^{-i}}\;, $$

Sage tells me that this $6$-th order equation for $c$ has $6$ real solutions, $5$ of which are $\gt1$, whereas we want the other one, $c_{\mathrm min}\approx0.554509471152537$. Its minimal polynomial is of degree $36$ ($6$ from this equation and $6$ from the one for $\lambda_{\mathrm{max}}$):

$$ \left(4449462890625000000x^{36} - 24172330078125000000x^{35} + 49046693990625000000x^{34} - 41769983095650000000x^{33} + 6262303815585000000x^{32} + 10466684507347200000x^{31} - 4138402685549220000x^{30} - 582487240632840000x^{29} + 1047434350651164000x^{28} - 82564347696768000x^{27} - 916144313873313600x^{26} + 170063128160164800x^{25} + 266506356802489200x^{24} - 6276611448694800x^{23} - 40016162958292800x^{22} - 5235939057854880x^{21} + 2435166236985120x^{20} + 1284349230559440x^{19} - 304732164386520x^{18} - 6301109644560x^{17} - 554379054984x^{16} + 2195605890144x^{15} - 480507324552x^{14} - 143513421840x^{13} + 84252155508x^{12} - 15843100428x^{11} + 478048608x^{10} + 592215264x^9 - 152515620x^8 + 13933764x^7 + 1008678x^6 - 544548x^5 + 93798x^4 - 10020x^3 + 738x^2 - 36x + 1\right)/\,4449462890625000000\;. $$

Using this to seed the backward induction for $W_k$ at $k=94,\ldots,99$, I calculated the expected payoffs and equilibrium strategies for the first innings (also with the code linked to above, now using floating-point arithmetic and not exact rational numbers). Here are the results in the same three diagrams as for the second innings ($p_i$, $q_i$, $-W_k$ plotted logarithmically):

The deviations from the limiting values are much less pronounced; the deviations in the second innings are basically smoothed out by being "convolved" with the distribution of runs scored in the first innings.

The limiting values are quite similar but not identical to the ones in the second innings; they're now given by $1-q_i^\infty=5p_i^\infty\propto\left(1-c\lambda_{\mathrm{max}}^{-i}\right)^{-1}$:

$$ \begin{array}{c|c|c} i&p_i^\infty&q_i^\infty\\ \hline 1&0.18787&0.06066\\ 2&0.17765&0.11174\\ 3&0.16894&0.15530\\ 4&0.16144&0.19282\\ 5&0.15491&0.22545\\ 6&0.14919&0.25403 \end{array} $$

The overall value of the game for the second batter comes out as $-W_0\approx0.47528$, so there's a slight advantage for the first batter – which isn't terribly surprising, since I resolved ties in her favour. If the ties are resolved in the second batter's favour instead, the value of the game for the second batter is approx. $0.52004$, now with a similar but slightly smaller advantage for the second batter. If a tie counts as half a win for each player (payoff $0.5$), then the value of the game for the second batter is approx $0.49819$, which is much closer to $0.5$ than I would have expected, given the asymmetrical setup of the game. It turns out that the asymmetry very slightly favours the first batter.

P.S.: I computed some statistics: The expected number of throws ($n_{\mathrm t}$) and of runs ($n_{\mathrm r}$) in the entire game, in each innings and after a point in the asymptotic tail of each innings.

With $\rho_i=\lambda_{\mathrm{max}}^{-i}$ and $\sigma_i=\left(1-c\lambda_{\mathrm{max}}^{-i}\right)^{-1}$, the asymptotic values are calculated as

$$ \begin{eqnarray} \left<n_t\right>=1+\left<n_t\right>\sum_ip_i\left(1-q_i\right)\quad&\longrightarrow&\quad\left<n_t\right>=\left(1-5\frac{\sum_i\rho_i^2}{\left(\sum_i\rho_i\right)^2}\right)^{-1}\simeq6.25852\;,\\ \left<n_r\right>=\sum_ip_i\left(1-q_i\right)\left(i+\left<n_r\right>\right)\quad&\longrightarrow&\quad\left<n_r\right>=\frac{5\sum_i\rho_i^2i}{\left(\sum_i\rho_i\right)^2-5\sum_i\rho_i^2}\simeq16.78199 \end{eqnarray} $$

for the second innings and

$$ \begin{eqnarray} \left<n_t\right>=1+\left<n_t\right>\sum_ip_i\left(1-q_i\right)\quad&\longrightarrow&\quad\left<n_t\right>=\left(1-5\frac{\sum_i\sigma_i^2}{\left(\sum_i\sigma_i\right)^2}\right)^{-1}\simeq6.19442\;,\\ \left<n_r\right>=\sum_ip_i\left(1-q_i\right)\left(i+\left<n_r\right>\right)\quad&\longrightarrow&\quad\left<n_r\right>=\frac{5\sum_i\sigma_i^2i}{\left(\sum_i\sigma_i\right)^2-5\sum_i\sigma_i^2}\simeq16.78137 \end{eqnarray} $$

for the first innings. The remaining statistics I collected from the code (using the asymptotic values as seeds in the first innings):

$$ \begin{array}{c|ccc} &\text{game}&\text{1$^{\text{st}}$ innings}&\text{2$^{\text{nd}}$ innings}\\ \hline n_t&9.47542&6.19873&3.27669\\ n_r&25.64678&16.78067&8.86611 \end{array} $$

(The smaller numbers for the second innings aren't because of a worse performance of the second batter but because the innings ends when the (possibly low) score of the first batter is reached.)

It's striking how relatively independent the numbers are of the specific circumstances. For instance, the expected number of runs in the first innings, in the asymptotic tail of the first innings and in the asymptotic tail of the second innings are all $16.78$ up to two digits, and this is also, up to two digits, the value Micah calculated by optimizing the expected number of runs.

Answer 2

(Too long for a comment)
When scores are tied, either player can pick a number a random. The batsman would then win at least 5/6 times, whatever the bowler did; and the bowler would win at least 1/6 times, whatever the batsman did.
With 2 runs to win, say the batsman chose $1$ with probability $1-5p$, and any other number with probability $p$ each. If the bowler picks $1$, he wins with probability $1-5p$, and for any other number he wins with probability $p+(1/6)(1-5p)=(1/6)+(1/6)p$. So the batsman should choose $p=5/31$, and the bowler can't do any better than $6/31$.
With 2 runs to lose, say the bowler chose $1$ with probability $1-5q$, and any other number with probability $q$ each. Again, the batsman's chances of winning by picking $1$ are $(5/6)(5q)$, and any other choice, it is $1-q$. So the bowler should set $25q/6=1-q$, $q=6/31$, and the batsman can do no better than $25/31$.
So each play has a strategy that guarantees at least $25/31$, or $6/31$; and that is the probability with 2 runs to win. (I gave a tie as a win for the bowler; you could fix that.)

Answer 3

This is also not a complete answer, but it maybe approximates one under the right circumstances.

The simplest reasonable heuristic that gives an answer in every situation is to compute the strategy that maximizes your expected value (i.e., instead of playing to win, you're playing for a penny per run). This should be nearly correct when either you need a lot of runs to win or there's a lot of uncertainty about how many you need.

Suppose the batsman adopts the strategy of choosing the number $k$ with probability $a_k$, and the bowler chooses $k$ with probability $b_k$. It's actually useful (because it makes things more symmetric) to write things in terms of the bowler's inverse probability $\overline{b}_k=1-b_k$. Then the expected number of runs $E$ that will be scored by the batsman is given by: $$ E=\sum_{k=1}^6 (k+E)a_k\overline{b}_k $$ (this is saying that if the batsman plays $k$ and the bowler doesn't, the batsman scores $k$ runs and then gets to start over). The problem also implies the constraints $$ \sum_{k=1}^6 a_k = 1, \quad\sum_{k=1}^6 \overline{b}_k = 5,\\ \quad a_k, \overline{b}_k \in [0, 1] \text{ for all } k \in \{1,2,3,4,5,6\} $$

This will yield a finite value for $E$ whenever $\sum a_k\overline{b}_k < 1$, which the bowler can guarantee by choosing $\overline{b}_k < 1$ for all $k$. So the game terminates with probability $1$ unless the bowler is extremely foolish, and it's reasonable to ask about optimal strategies.

These will be given by saddle points of the function $E(a_k,\overline{b}_k)$. To deal with the constraints, we write $a_1,\overline{b}_1$ in terms of the other variables, so $$ E=\sum_{k=2}^6 (k+E)a_k\overline{b}_k + (1+E)\left(1-\sum_{k=2}^6 a_k\right)\left(5-\sum_{k=2}^6 \overline{b}_k\right) $$

Then, differentiating, we have

$$ E_{a_k}=(k+E)\overline{b}_k +E_{a_k}a_k\overline{b}_k+\left[(1+E)(-1) + E_{a_k}\left(1-\sum_{k=2}^6 a_k\right)\right]\left(5-\sum_{k=2}^6 \overline{b}_k\right) \\ E_{\overline{b}_k}=(k+E)a_k+E_{\overline{b}_k} a_k \overline{b}_k + \left[(1+E)(-1) + E_{\overline{b}_k}\left(5-\sum_{k=2}^6 \overline{b}_k\right)\right]\left(1-\sum_{k=2}^6 a_k\right) $$ At a critical point of $E$, we must have $E_{a_k}=E_{\overline{b}_k}=0$. So these equations reduce to $$ 0=(k+E)\overline{b}_k -(1+E)\overline{b}_1\\ 0=(k+E)a_k - (1+E)a_1 $$ which yield the relations $$ a_k=\frac{1+E}{k+E} a_1 \\ \overline{b}_k=\frac{1+E}{k+E} \overline{b}_1 $$ (strictly speaking, we've only derived these relations when $k>1$, but they clearly also hold when $k=1$).

Note that this means that $a_k$, $\overline{b}_k$ both decrease as $k$ increases. Since $a_k$ decreases as $k$ increases, the batsman wants to have a bias toward lower numbers. Why? Because $\overline{b}_k$ decreases as $k$ increases, which means $b_k$ increases as $k$ increases. That is, the bowler is preferentially defending the higher numbers, and so the batsman would rather stay away from them — and keep playing — than take the risk of getting out in exchange for a slightly higher score in the current round.

Continuing with our solution, we have $$ \sum_{k=1}^6 \frac{1+E}{k+E} a_1 = 1, \\ \sum_{k=1}^6 \frac{1+E}{k+E} \overline{b}_1 = 5 $$ which yields $\overline{b}_1=5a_1$, and so $\overline{b}_k=5a_k$ for all $k$.

Plugging all of this back into the original equation for $E$, we have $$ E = \sum_{k=1}^6 (k+E) a_k \overline{b}_k = \sum_{k=1}^6 \frac{(1+E)^2}{k+E}a_1\overline{b}_1=(1+E)^2a_1\overline{b}_1 \sum_{k=1}^6 \frac{1}{k+E} $$ which implies that $$ E = (1+E)\overline{b}_1,\\ E = 5(1+E)a_1 $$ and so $a_1=\frac{E}{5(1+E)}$, $\overline{b}_1=\frac{E}{1+E}$. Finally, this gives us a $1$-variable equation for the optimal value of $E$: $$ E=\frac{E^2}{5}\sum_{k=1}^6 \frac{1}{k+E} $$ which, upon dividing through by $E$, reduces to a sextic with only one meaningful root: $E \approx 16.777$. Since this is the only critical point and $E$ can be either zero or infinite on the boundary, it must be a saddle point — thus it gives the minimax strategy we're looking for. Plugging this back into the relations for $a_k$, $\overline{b}_k$ and using the fact that $b_k=1-\overline{b}_k$, we get $$ \begin{array}{cc} a_1 \approx 0.18875 & b_1 \approx 0.05625\\ a_2 \approx 0.17870 & b_2 \approx 0.10651\\ a_3 \approx 0.16966 & b_3 \approx 0.15169\\ a_4 \approx 0.16150 & b_4 \approx 0.19252\\ a_5 \approx 0.15408 & b_5 \approx 0.22960 \\ a_6 \approx 0.14732 & b_6 \approx 0.26342 \end{array} $$ So the batsman should actually choose pretty close to uniformly. The bowler, on the other hand, should work fairly hard at defending against the high-scoring plays.

Qualitatively, I think the right way to make sense of this is as follows. Since $6 \gg 2$, the batsman can score more in the long run by not getting out than by maximizing his scoring potential in the current round. The best way to not get out is to be as unpredictable as possible — that is, to keep his distribution near-uniform. If you grant that the batsman's distribution will be near-uniform, the bowler has very little control over how long the game goes — the probability of stopping in any given round will be near $\frac{1}{6}$ no matter what she does. So all she has left to play for is score in the current round, meaning she wants to mostly play large numbers (while playing small numbers just enough to keep the batsman honest). Finally, this means that whatever deviation the batsman makes from uniformity should be in the direction of playing smaller numbers — this will keep the game going for slightly longer.