Conway's Army Percolation

Gabriel Istrate, Mihai Prunescu (Universitatea din Bucuresti)

We study a probabilistic version of the celebrated Conway's Army game. In this game the lower semiplane of an infinite chessboard is filled with checker pieces. A celebrated result due to Conway (1961) shows that one cannot move a checker piece in a finite number of steps to a position on row 5 (rows 1-4 are reachable).

In the version that we are interested in, inspired by percolation theory, we assign pieces to all cells of the lower semiplane independently by flipping a coin with success probability $p$ (where $p$ is a fixed constant between 0 and 1). We are interested in estimating $D_{k}(p)$, the probability that one can reach a fixed cell on line $k$, for $k=1,2,3,4$. We derive several results that provide lower and upper bounds on this probability. These results show that $0<D_k(p)<1$ for every $p\neq 0,1$, and suggest the fact that the $D_{k}(p)$ is an analytical function of $p$.

We then explain why the problem we study can be regarded as a type of percolation problem on hypergraphs. We also report on how to use SAT solvers to study the problem experimentally.