Daleks

I’ve wanted to write a post about the new Doctor Who series for a while, but this is not that post. Instead, this post is about a Macintosh game called Daleks, which I first played on a Mac 512 (running OS 3) in the mid-80’s. Research indicates that this game was based on a Unix game called robots, and that some wag came up with the idea of rebranding it under the name of the classic Doctor Who monster. The first version I played had a very peculiar high score table: all the high scores were attributed to a fellow named “fingers,” and the high scores were not in any sort of numerical order. Moreover, no matter what one scored, it was impossible to permanently make it onto the high score list. My second encounter with the game was during a summer research program with Alf van der Poorten in 94/95, where I was impressed to find that he had broken 10000. Later, I had a copy on an ancient laptop given to me by my brother, and still later, I played classic Daleks in classic mode under OS X. I am not ashamed to say that I am proud of my high score, 15670, a feat which is probably meaningless to almost everyone. Anyway, today’s post is about some mathematical problems related to this game. If you have a mac computer, I recommend playing around with some current incarnations of the game, for example super Daleks (presumably robot is available on Gnome games as well):

Consider the following game: the Doctor is positioned on the lattice \(\mathbf{Z}^2\) at the origin \((0,0)\), and Daleks are distributed on the rest of the lattice with uniform density \(\rho \in (0,1)\). It turns out that it is more convenient to work with the parameter \(q = 1 – \rho\), although all the graphs below are drawn with respect to \(\rho\). On each move, the Dalek at point P moves to the unique neighbouring square (out of 8) which is closest to the origin in the taxicab metric. In particular, Daleks always move diagonally towards the origin unless they lie on one of the axes. If two or more Daleks occupy the same square, then they crash and are destroyed, leaving a pile of debris which remains at that square forever. Moreover, any other Dalek which later moves on to the same square now occupied by the debris is also destroyed. If a Dalek reaches the origin unscathed, the Doctor is exterminated. However, if the debris resulting from Dalek collisions prevents all other Daleks from reaching the origin, then the Doctor survives. What is the probability that the Doctor survives? (In the computer game the Doctor can also move about, but not in our simplified version.)

If a Dalek starts on either the diagonal or the anti-diagonal then it will never crash with another Dalek (in general, Daleks can only crash on the axes). Hence, we modify the game by forbidding Daleks from either of these diagonals. This effectively separates the playing area into four quadrants which do not interact, and so we may as well confine ourselves to a single quadrant, and assume that all Daleks lie in the quadrant \((1,0) + Q\) where \(Q = (x,y)\) with \(x \ge |y|\). A sample game is as follows, with the positions at time \(t =\) 0, 1, and 2. The Doctor will win this game, because the debris at \((1,0)\) will prevent all other Daleks in the quadrant from reaching the origin (they will crash into the debris and be destroyed):

Let \(Q_d\) be the truncated quadrant consisting of \((x,y)\) with \(|y| \le x \le d\). Let \(w_d\) denote the probability of surviving the game where Daleks only exist with density \(\rho\) in this quadrant. It is clear that

\(1 – w_d = \displaystyle{\sum_{P \in (1,0) + Q_d} E(P)},\)

where \(E(P)\) is the expectation of being exterminated by a Dalek which originates at point P. (If there is a Dalek which kills the Doctor, it is unique.) Note that \(E(P)\) is independent of \(d\), providing that \(P \in (1,0) + Q_d\).

Definition: The occludation \(O(P)\) of P consists of the squares R different from P where a Dalek at square R will reach the origin before or at the same time as P, and which reach the \(x\)-axis at least as near to the origin as P reaches the \(x\)-axis.

The Daleks \(R \in O(P)\) are those for which R is in the shadow of R, namely, those R which eventually occlude P from the origin (thus the name). It is not a great name, but I couldn’t think of anything better. Explicitly, if \(P = (x,y)\), then

\(O(P) \cup P = \{(a,b) \in (1,0) + Q \ \text{such that} \ a \le x, \ \text{and} \ a – |b| \le x – |y|\}\)

The Doctor can only be killed by Dalek at point P if the occludation \(O(P)\) is empty of Daleks. The reason is that any Dalek R in the occludation can only crash at points on the \(x\)-axis where P must eventually travel, and R will reach this point either at or before P does. We have

\(|O(P)| = |O((1,0) + (x,y))| = x^2 – y^2 – 1.\)

On the other hand, conditional on the assumption that the occludation contains no daleks, then the probability that P exterminates the Doctor only depends on \(y\); namely, it is equal to the probability of surviving the game with \(Q_d\) and \(d = |y|\). (This the the quadrant not in the occludation of \(P\).) It follows that

\(E(P) = q^{|O(P)|}(1-q) w_{|y|} = q^{x^2 – y^2-1}(1-q) w_{|y|},\)

and hence

\(1 – w_d = \sum_{n=1}^{d} \sum_{|m| < n} E((n,m)) = \sum_{n=1}^{d} \sum_{|m| < n} q^{n^2 – m^2 – 1}(1-q) w_{|m|}.\)

We may simplify this slightly by writing

\(w_{d-1} – w_{d} = (1-w_{d}) – (1-w_{d-1}) = \sum_{|m| < d} q^{d^2 – m^2 – 1}(1-q) w_{|m|},\)

This simplifies even further to

$latex \begin{aligned}
& (w_{d} – w_{d+1}) – q^{2d+1} (w_{d-1} – w_{d}) \\
= & \sum_{|m| < d+1} q^{(d+1)^2 – m^2 – 1}(1-q) w_{|m|}
– q^{2d+1} \sum_{|m| < d} q^{d^2 – m^2 – 1}(1-q) w_{|m|} \\
= & \ 2 q^{2d}(1-q) w_{d}, \end{aligned}$

and hence, subject to \(w_0 = 1\) and \(w_1 = q\),

\(w_{d+1} = (3 q^{2d+1} – 2 q^{2d} + 1) w_d – q^{2d+1} w_{d-1}.\)

The resulting recurrence relation for \(w_d\) gives a decreasing convergent sequence (for each fixed \(q\) and also in \(\mathbf{Z}[[q]]\)) with limit

\(w_{\infty} = q – 3q^3 + 3q^4 – 2q^5 + 2q^6 + 4q^7 – 13q^8 + 13q^9 + \ldots \)

Here is a graph of this function (with respect to \(\rho\), remember that \(\rho = 1 – q\)):

Although it appears from the graph that the maximum occurs at \(\rho = q = 1/2\), closer inspection reveals that the optimal density is \(\rho = 0.517208\ldots\) The maximum value is approximately \(\sim 0.28116\ldots\), which means that, on an entire plane with all four quadrants, the largest possible chance of winning (with daleks on the diagonal and anti-diagonal removed) is approximately 1 in 160.

Reverse the Polarity: Here is a different way to estimate \(w_{\infty}\), this time from below. In order for the Doctor to survive, two or three Daleks must eventually coincide at \((1,0)\). Call such Daleks savior Daleks. All savior Daleks must be in the same row, and at least one such Dalek must lie on the edge of the quadrant. Let us now consider the probability \(s_n\) that one will be “saved” by a Dalek in the \(n\)th row. If \(P = (n,n-1)\) is a savior Dalek, then the Dalek \(P\) creates the first crash at the point \((0,1)\), and no Dalek exterminates the Doctor before this point. It follows that no Daleks may occlude \(P\), and hence \(O(P)\) must be free of Daleks, with the possible exception of \(-P\). Note that \(|O(P)| = n^2 – (n-1)^2 – 1 = 2n\). Suppose that \(-P\) is not occupied. Then (assuming that \(O(P)\) is empty) \(P\) will be a savior Dalek if and only if the remaining restricted quadrant of size \(n-1\) would otherwise result on the Doctor being exterminated at the final term, equivalently, the probability that, from a quadrant of size \(n-1\), the Doctor would be exterminated by a Dalek in the last row. Yet the probability of this is

\((1 – w_{n-1}) – (1 – w_{n-2}) = w_{n-2} – w_{n-1},\)

and hence the contribution to \(s_n\) is

\(2q^{2n-2}(1-q)(w_{n-2} – w_{n-1}).\)

On the other hand, if both \(P\) and \(-P\) are to be savior Daleks, then one simply requires that, in addition to the rest of occlusion \(O(P)\) being empty, that in the remaining quadrant of size \(n-2\) (removing the final row and the occlusion) no Doctor is exterminated, and this has probability \(w_{n-2}\). Hence

\(s_{n} = 2q^{2n-2}(1-q)(w_{n-2} – w_{n-1}) + q^{2n-3} (1-q)^2 w_{n-2}.\)

Let \(t_n\) be the probability that there exists a savior Dalek at a row at most \(n\). Then clearly

\(t_{n} = \sum_{m=1}^{n} s_m.\)

Moreover, we naturally have inequalities \(w_n \ge t_n\), and

\(w_{\infty} = \lim_{n \rightarrow \infty} w_n = \lim_{n \rightarrow \infty} t_n,\)

where the limit is pointwise and \(q \ne 1\). However, the behavior of \(w_n\) and \(t_n\) is quite different in the regime \(\rho \rightarrow 0\) or \(q \rightarrow 1\), as the following graph of \(w_5 \ge t_5\) shows:

Behavior as \(\rho \rightarrow 0\):

In order to estimate the behavior of \(w_{\infty}\) as \(q \rightarrow 1\), we consider the following problem:
What is the probability that the first row with any Dalek contains exactly two Daleks, and that at least one of these Daleks lies at the edge of the quadrant? In such a situation, the Daleks necessarily annihilate one another at \((1,0)\), and the Doctor is saved. Call the resulting function \(A(q)\), so \(w_{\infty} > A(q)\). Since there are \((4n-1)\) pairs of elements in \(1,\ldots,2n+1\) which contain at least one of the end points, we have

$latex \begin{aligned}
A(q) = & \ \sum_{n=1}^{\infty} (4n-1) q^{n^2}(q^{2n-1} (1-q)^2) = (q-1)^2 q^{-2}
\sum_{n=2}^{\infty} (4n-5) q^{n^2} \\
= & \ (q-1)^2 q^{-2} \left(5 + q + \sum_{n=0}^{\infty} 4n q^{n^2} – 5 \sum_{n=0}^{\infty} q^{n^2}\right) \\
= & \ (q-1)^2 q^{-2} \left(\frac{5}{2} + q +2 \sum_{n=-\infty}^{\infty} |n| q^{n^2} – \frac{5}{2} \sum_{n=-\infty}^{\infty} q^{n^2}\right) \\
= & \ (q-1)^2 \left(2 \sum_{n=-\infty}^{\infty} |n| q^{n^2} – \frac{5}{2} \sum_{n=-\infty}^{\infty} q^{n^2}\right)(1 + O(1))
+ O((q-1)^3).\end{aligned}$

Let \(q = e^{-\tau}\). As \(q \rightarrow 1\), we have \(\tau \rightarrow 0\), and so \(1-q \sim \tau\). On the other hand, by Poisson summation, we have

\(\displaystyle{\sum_{n=-\infty}^{\infty} e^{-n^2 \tau} \sim \sqrt{\frac{\pi}{\tau}} + O(\tau^N),} \)

\(\displaystyle{\sum_{n=0}^{\infty} |n| e^{-n^2/\tau} \sim \frac{1}{\tau} – \frac{1}{6} – \frac{\tau}{60} – \frac{\tau^2}{252} + O(\tau^3),} \)

from which it follows easily that \(A(q) \sim 2 \tau \sim 2(1-q)\), and thus

\(\limsup_{q \rightarrow 1} w_{\infty} \ge 2(1-q).\) In fact, we can actually prove that

\(w_{\infty}(e^{-\tau}) = \displaystyle{\frac{2}{\tau} + O \left(\frac{1}{\sqrt{\tau}}\right)}.\)

In other words, the simple model above is very accurate in the limit \(q \rightarrow 1\). However, the combinatorics required to prove this are actually somewhat involved and annoying, and this is a blog, so I will omit it here. (The arguments are somewhat timey–wimey.)

A conditional game:

Consider the game which is pre-conditioned on the first square \((1,0)\) being empty. Since that square containing a Dalek is not consistent with survival, the new game results in a win with probability:

\(\displaystyle{c_{\infty} = \frac{w_{\infty}}{1 – \rho} = \frac{w_{\infty}}{q}.}\)

Apropos of nothing, here’s Davros enjoying a cuppa:

The TARDIS:

Suppose that the Doctor has a TARDIS. This allows him, at any point, to dematerialize and the materialize somewhere else. In the context of the classic Daleks game, the player appears at a random point in the plane with uniform distribution. Although this doesn’t quite make sense on an infinite plane, we can take it to mean that we have moved sufficiently far away from the axes that it is as if the game has started again. Hence this will be the context in which we shall consider rematerialization, namely, as if the game has started again. The catch with using the TARDIS is that the Doctor may materialize next to a Dalek, in which case he is immediately exterminated. The optimal strategy is to continue to continue rematerializing until one has a winning game. The chance of surviving a rematerization is \((1 – \rho)\); the resulting game is the same, but now conditional on not being annihilated by the initial Dalek, hence is equivalent to the conditional game descibed above. It follows that the chances of survival are:

$latex d_{\infty}:=w_{\infty} + (1 – w_{\infty})(1 – \rho)(c_{\infty} + (1 – c_{\infty})(1-\rho)(c_{\infty} + \ldots
= \displaystyle{\frac{(2-q) w_{\infty}}{1 – q + w_{\infty}}}.$

The asymptotic behavior of this function as \(\rho \rightarrow 1\) (or \(q \rightarrow 1\)) requires the correct asymptotic \(w_{\infty} \simeq 2(1-q)\), and from this we can deduce that

\(d_{\infty} \rightarrow 2/3 \ \text{as} \ \rho \rightarrow 0.\)

In this case, we see that the optimal probability is that the density \(\rho\) tends to zero. Here is a graph of \(d_{\infty}\):

The Sonic Screwdriver: Like John Nathan-Turner, I find the sonic screwdriver to be somewhat ridiculous. Although it does exist in some versions of the game, I will only mention a minor modification here. The “sonic” in the game allows the Doctor to survive for one round when he would otherwise be exterminated; it has only one use. We shall additionally assume that the sonic can only be used on the very first round. This essentially changes the game (at the beginning) into the conditional game described above. If one is allowed to use the TARDIS as above, the resulting probability of winning is

\((c_{\infty} + (1 – c_{\infty})(1-\rho)(c_{\infty} + (1 – c_{\infty})(1-\rho)(c_{\infty} + \ldots = \displaystyle{\frac{w_{\infty}}{q(1-q + w_{\infty})}}.\)

As \(\rho \rightarrow 1\), this function tends to 1, and as \(\rho \rightarrow 0\), it tends to \(2/3\). The behavior of this function in a neighbourhood of \(0\) appears to be of the form

\(2/3 – A \rho^{1/2} + \ldots \)

for some constant \(A\), possibly around \(0.3\). Note that this function is not monotone; the most dangerous density of Daleks is approximately \(\rho = 0.127\), where the resulting probability of surviving dips below \(3/5\).

Here’s an example of the vanilla game at the optimal \(\rho \sim 0.517\): the Doctor lives!