Conway's Army Percolation

Abstract

We analyze a probabilistic version of Conway’s soldiers puzzle: given a fixed constant $p\in [0,1]$, place checker pieces in the cells of an infinite checkerboard lying below the horizontal axis independently with probability $p$. A seminal result due to Conway is that one cannot reach line five. We prove rigorous lower and upper bounds on $D_{k}(p)$, the probability that one can reach a fixed cell on row $k$, $1\leq k\leq 4$. We complement these rigorous results by empirical estimates (employing a SAT solver). These rigorous and empirical results suggest that $D_{k}(p)$ are smooth functions of $p$ for all $k=1,\ldots, 4$. We then show that our results are connected to a percolation model on hypergraphs. Specifically, we define a dynamics that corresponds to Conway’s army when the time is reversed. We define a notion of “percolation of safe configurations” for this dynamics and show that, for a $k$-uniform $r$-ary hypergraph analog $B_{k,r}$ of the Bethe lattice, the critical value for this percolation of valuable configurations on $B_{k,r}$ is $\frac{1}{(k-1)(r-1)}$. Interestingly, the proof of this result extends the original argument (based on branching processes) for percolation on the Bethe lattice.