Can You Survive “The Floor”?

From John Hannon comes a puzzle inspired by a television game show. In The Floor, one hundred contestants occupy the squares of a $10\times10$ grid and duel their neighbours over trivia; the loser of each duel is eliminated and their territory is annexed by the winner.

Consider a simplified version with nine contestants on a $3\times 3$ grid. Each round proceeds in three steps. First, one of the remaining contestants is chosen at random, every contestant equally likely regardless of how many squares they control. Second, an opponent is chosen at random from those whose territory shares an edge with the chosen contestant, again all equally likely. Third, the two duel, each with a $50$ percent chance of winning; the loser is eliminated and their territory is added to the winner’s. Rounds repeat until one contestant remains.

The nine starting positions are numbered $$\begin{array}{ccc}1&2&3\\4&5&6\\7&8&9\end{array}$$ with position $5$ at the centre. Which position would you choose, to give yourself the best chance of being the overall winner?

The Fiddler, Zach Wissner-Gross, December 13, 2024(original post)

Solution

Start by stripping the game to what actually decides it. Every duel is a fair coin, so once two contestants meet, each is equally likely to survive; where you sit on the grid never tilts a single fight. Position can only change how often you are dragged into one. Each round a contestant is drawn uniformly from the survivors, then one of that contestant’s neighbours is drawn to fight. You enter a round in one of two ways: you are the one drawn, or you are the neighbour drawn against someone else. The first chance is the same for everyone; the second grows with how many distinct neighbours border your territory. Fewer borders means fewer coin flips that can end your run, and at the start a corner borders only two squares, an edge three, the centre four. That is the intuition. To turn it into exact numbers, track the full state.

Encode a position of the game as the map $s$ giving the current owner of each of the nine cells. Because territories only ever merge along shared edges, each owner’s cells always form one edge-connected block. Write $\operatorname{own}(s)$ for the set of surviving owners and $R=|\operatorname{own}(s)|$. While $R\ge 2$, a round transforms $s$ as follows: pick $c\in\operatorname{own}(s)$ with probability $1/R$; let $$N_c=\{\,\text{owner of cell }j : \text{cell } j \text{ borders a cell of } c,\ \text{owner}(j)\neq c\,\}$$ be the rival neighbours of $c$, with $E_c=|N_c|\ge 1$ (the grid is connected, so a survivor always has at least one rival); pick $o\in N_c$ with probability $1/E_c$; then with probability $\tfrac12$ each, either $o$’s block is annexed to $c$ or $c$’s block to $o$.

Let $W_o(s)$ be the probability that owner $o$ is the eventual sole survivor, starting from $s$, and write $W(s)$ for the vector of these over $\operatorname{own}(s)$. If $R=1$ the lone owner wins outright, so $W=1$ for that owner. Otherwise, averaging over the three random steps of one round, $$W(s)=\sum_{c\in\operatorname{own}(s)}\frac1R\sum_{o\in N_c}\frac1{E_c}\cdot\frac12\Bigl(W\!\left(s_{c\leftarrow o}\right)+W\!\left(s_{o\leftarrow c}\right)\Bigr),$$ where $s_{a\leftarrow b}$ denotes $s$ with $b$’s block relabelled to $a$. Every transition lowers $R$ by exactly one, so the recursion has depth at most eight and terminates; the values are pinned down bottom-up from the singleton states. Evaluating it in exact rational arithmetic from the start state $s_0=(1,2,\dots,9)$ gives $$W_{\text{corner}}=\frac{95802636437}{743178240000},\qquad W_{\text{edge}}=\frac{8977833162901}{90296156160000},$$ $$W_{\text{centre}}=\frac{3912371100007}{45148078080000},$$ that is $0.128909$, $0.099427$ and $0.086656$. Four corners, four edges and one centre, weighted by these, sum to exactly $1$, the check that no probability has leaked. The intuition survives the arithmetic: the corner, least exposed, is best, so

$$\boxed{\text{choose a corner: position }1,\,3,\,7\text{ or }9,}$$ which wins about $12.9$ percent of the time, against $9.9$ percent for an edge and only $8.7$ percent for the centre.

The computation

The recurrence is already the algorithm: the value of a state is the average of the values of the states its possible duels lead to. Evaluated naively it would revisit the same partition over and over, since many duel orders reach it, so we memoise on $s$ and recurse:

1. If $s$ is already in the memo, return its stored vector.

2. Let $O$ be the distinct owners in $s$. If $|O|=1$, the lone owner wins with probability $1$; return that.

3. Otherwise initialise $w\leftarrow\mathbf 0$ over $O$ and set $R\leftarrow|O|$. For each owner $c\in O$, build its rival set $N_c$; then for each rival $o\in N_c$, add $\tfrac1R\cdot\tfrac1{|N_c|}\cdot\tfrac12$ times the value of each of the two states the duel can produce, the one where $c$ annexes $o$ and the one where $o$ annexes $c$, into $w$.

4. Store $w$ in the memo and return it.

The reachable states are the territory partitions of the $3\times3$ grid with a marked owner per cell, only a few thousand in all, each visited once. That is why exact fractions are affordable and the answer emerges as a closed rational rather than a float. The Python below is a direct transcription, using fractions.Fraction so that every probability stays exact.

from fractions import Fraction as F
import sys
sys.setrecursionlimit(100000)
#  cells 0..8:  0 1 2 / 3 4 5 / 6 7 8
ADJ = [[] for _ in range(9)]
for r in range(3):
    for c in range(3):
        i = 3 * r + c
        if c < 2: ADJ[i].append(i + 1); ADJ[i + 1].append(i)
        if r < 2: ADJ[i].append(i + 3); ADJ[i + 3].append(i)

memo = {}
def win_vec(state):                       # state: owner of each cell -> {owner: P(win)}
    if state in memo: return memo[state]
    owners = set(state)
    if len(owners) == 1:
        return {next(iter(owners)): F(1)}
    res = {o: F(0) for o in owners}; R = len(owners)
    for c in owners:
        elig = {state[j] for i in range(9) if state[i] == c
                for j in ADJ[i] if state[j] != c}
        E = len(elig)
        for o in elig:
            s1 = tuple(c if state[i] == o else state[i] for i in range(9))  # c wins
            s2 = tuple(o if state[i] == c else state[i] for i in range(9))  # o wins
            w = F(1, R) * F(1, E) * F(1, 2)
            for t, p in win_vec(s1).items(): res[t] += w * p
            for t, p in win_vec(s2).items(): res[t] += w * p
    memo[state] = res
    return res

v = win_vec(tuple(range(9)))
print("corner", v[0], float(v[0]))        # 0.128909
print("edge  ", v[1], float(v[1]))        # 0.099427
print("centre", v[4], float(v[4]))        # 0.086656
print("sum", sum(v.values()))             # 1

Extra Credit

What is your probability of winning from each of the nine starting positions, and for an $N\times N$ board?

For the $3\times3$ board the nine values are the three above, placed by the square’s symmetry: corners $12.89\%$, edges $9.94\%$, centre $8.67\%$. The same recurrence defines the game on any $N\times N$ board, but the number of reachable partitions grows far faster than exact recursion can follow, so for $N\ge 4$ the honest tool is direct simulation of the rounds. It tells the same story: fewest initial borders wins, so the corners stay ahead. On a $4\times4$ board, simulation gives a corner about $8.0$ percent, a side square about $5.9$ percent, and an interior square about $5.1$ percent, against the flat average $1/16 = 6.25$ percent.

import random
def simulate(N, trials):
    n = N * N
    A = [[] for _ in range(n)]
    for r in range(N):
        for c in range(N):
            i = r * N + c
            if c < N - 1: A[i].append(i + 1); A[i + 1].append(i)
            if r < N - 1: A[i].append(i + N); A[i + N].append(i)
    wins = [0] * n
    for _ in range(trials):
        owner = list(range(n)); cells = {i: [i] for i in range(n)}; alive = set(range(n))
        while len(alive) > 1:
            c = random.choice(tuple(alive))
            elig = {owner[j] for i in cells[c] for j in A[i] if owner[j] != c}
            o = random.choice(tuple(elig))
            w, l = (c, o) if random.random() < 0.5 else (o, c)
            for i in cells[l]: owner[i] = w; cells[w].append(i)
            del cells[l]; alive.discard(l)
        wins[next(iter(alive))] += 1
    return wins

random.seed(1)
w = simulate(4, 200000)
print("4x4 corner", w[0] / 200000, "edge", w[1] / 200000, "inner", w[5] / 200000)