Can You Track The Delirious Ducks?

The Riddler for January 17, 2020. The Express is a small zero-sum game: a football coach choosing between a one- and a two-point conversion against a defence that overhears the play call. The Classic tracks two random-walking ducks on a grid of rocks and asks how long until they reunite.

Riddler Express

The Riddler Football League playoffs are here. As coach you line up 2 yards out and may attempt either a 1-point or a 2-point conversion; the defence can properly guard only one of the two and must guess which. If you go for 1 and it is properly defended you score 90% of the time, otherwise 100%. If you go for 2 and it is properly defended you score 40% of the time, otherwise 60%. Your coordinator announces the probability of each attempt, and (because of league-wide spying) the defence hears it. What attempt probabilities maximise your average points, what should the defence do, and how many points do you score on average?

The Riddler, FiveThirtyEight, January 17, 2020(original post)

Solution

Let $q$ be your probability of going for the 1-point conversion (so $1-q$ for the 2-point), and let $p$ be the defence’s probability of guarding the 1-point try (so $1-p$ for the 2-point). This is a zero-sum game: your average points are exactly the defence’s loss, so you maximise and they minimise the same quantity.

Tabulate the points scored in each of the four attempt-versus-guess cases. Going for 1 earns $0.9$ points when guarded and $1.0$ when not; going for 2 earns $2\cdot0.4 = 0.8$ when guarded and $2\cdot0.6 = 1.2$ when not. The 1-point try is guarded with probability $p$; the 2-point try is guarded with probability $1-p$. So your expected points are $$E(q,p) = q\bigl[0.9p + 1.0(1-p)\bigr] + (1-q)\bigl[0.8(1-p) + 1.2p\bigr].$$

The clean way to read this is to gather the terms in $p$: $$E(q,p) = \bigl[0.8 + 0.2\,q\bigr] + p\,\bigl[0.4 - 0.5\,q\bigr].$$ If you choose $q = 0.8$, the coefficient of $p$ vanishes and $E = 0.8 + 0.2(0.8) = 0.96$ no matter what the defence does. So you can guarantee $0.96$ points. Symmetrically, gathering the terms in $q$ gives $E = [0.8 + 0.4p] + q\,[0.2 - 0.5p]$, and the defence setting $p = 0.4$ kills the coefficient of $q$, holding you to $0.96$ whatever you do. Neither side can improve, so $0.96$ is the value of the game:

The computation

Encode the four-case payoff directly and search the saddle point: your guaranteed score is $\max_q \min_p E(q,p)$, and the optimal $q,p$ are the maximiser and minimiser.

import numpy as np
def E(q, p):
    return q*(0.9*p + 1.0*(1-p)) + (1-q)*(0.8*(1-p) + 1.2*p)
qs = ps = np.linspace(0, 1, 1001)
value = max(min(E(q, p) for p in ps) for q in qs)
q_star = qs[np.argmax([min(E(q, p) for p in ps) for q in qs])]
p_star = ps[np.argmin([max(E(q, p) for q in qs) for p in ps])]
print(value, q_star, p_star)          # 0.96  0.8  0.4

The grid search reports value $0.96$ at $q=0.8$ (your offence) and $p=0.4$ (the defence), as boxed.

Riddler Classic

Two delirious ducks swim on a pond containing a $3\times 3$ grid of rocks. Every minute each duck hops independently to a uniformly random neighbour (up, down, left or right, not diagonal): the centre rock leads to one of four sides, a side to one of two corners or the centre, and a corner to one of two sides. Both ducks start at the centre. On average, how long until they are on the same rock again? Extra credit: what if there are three or more ducks, all starting at the centre?

The Riddler, FiveThirtyEight, January 17, 2020(original post)

Solution

Color the nine rocks like a checkerboard: the centre and the four corners are one color (five rocks), the four sides the other (four rocks). Every hop changes a duck’s color, so two ducks that start together on the centre stay on matching colors forever, minute by minute. They can therefore always meet, and we never have to worry about them being trapped on opposite colors.

Track the state by the tuple of duck positions. Reaching “all on the same rock” is an absorbing target, and the expected time to hit it solves the linear system $T(\text{state}) = 1 + \text{average of } T$ over the next minute’s joint moves, with $T = 0$ once all ducks coincide. Because the ducks start together, the answer is one minute plus the average of $T$ over the first joint hop out of the centre. Solving over the reachable (matching-color) states gives $$\begin{aligned} \text{two ducks:} \quad &\boxed{\tfrac{363}{74}} \approx 4.905 \text{ minutes},\\[2pt] \text{three ducks:} \quad &\boxed{\tfrac{3171}{172}} \approx 18.44 \text{ minutes}. \end{aligned}$$ A third duck nearly quadruples the wait, since all three must coincide at once.

The computation

Encode the walk: list every state in which the ducks share a color, set up the hitting-time equations toward the all-equal target, and solve exactly. The same routine handles any number of ducks.

import sympy as sp
from itertools import product
nb = {(i, j): [(i+d, j) for d in (-1, 1) if 0 <= i+d < 3]
             + [(i, j+d) for d in (-1, 1) if 0 <= j+d < 3]
      for i in range(3) for j in range(3)}
cells = list(nb); par = lambda p: (p[0] + p[1]) % 2
def meet_time(k):
    same = lambda s: len({par(p) for p in s}) == 1     # ducks share a color
    states = [s for s in product(cells, repeat=k) if same(s)]
    idx = {s: i for i, s in enumerate(states)}
    A = sp.zeros(len(states), len(states)); b = sp.zeros(len(states), 1)
    for s in states:
        i = idx[s]; A[i, i] = 1
        if len(set(s)) == 1:
            continue                                  # all ducks already together
        b[i] = 1; moves = list(product(*[nb[p] for p in s]))
        w = sp.Rational(1, len(moves))
        for m in moves:
            A[i, idx[m]] -= w
    T = A.LUsolve(b)
    hops = list(product(nb[(1, 1)], repeat=k))     # first hop from centre
    return 1 + sp.Rational(1, len(hops)) * sum(T[idx[m]] for m in hops)
print(meet_time(2), meet_time(3))                     # 363/74, 3171/172