Can You Survive “The Floor”?

This Week's Fiddler

We can note a symmetry here such that there are three unique classes of squares to choose: corner, edge, and center (the problem reminds me quite a bit of Rubik's Cube in this sense).

Intuitively, since winning matches does not improve your chances at winning other matches, it's ideal to engage in the least number of matches possible, which is made most likely if you're in a corner and least likely if you're in the center (sorry, position E). I made a simulation of a million trials to test my suspicions:

import random
from collections import Counter


random.seed(12)
T = 10**6
c = Counter()
for t in range(T):
    adj = {
        'A': set('BD'),
        'B': set('ACE'),
        'C': set('BF'),
        'D': set('AEG'),
        'E': set('BDFH'),
        'F': set('CEI'),
        'G': set('DH'),
        'H': set('EGI'),
        'I': set('FH'),
    }
    while len(adj) > 1:
        winner = random.choice(tuple(adj.keys()))
        loser = random.choice(tuple(adj[winner]))
        if random.random() < 0.5:
            winner, loser = loser, winner
        adj[winner] |= adj[loser]
        adj.pop(loser)
        for neighbors in adj.values():
            if loser in neighbors:
                neighbors.discard(loser)
                neighbors.add(winner)
        adj[winner].discard(winner)
    c.update(adj.keys())

print(c)

Output:

Counter({'I': 128807, 'G': 128705, 'C': 128697, 'A': 128405, 'H': 100106, 'B': 99784, 'F': 99606, 'D': 99270, 'E': 86620})

Looks like the corner class (A/C/G/I)—each position with a probability from 12.8% to 12.9%—wins! Following that is the edge class (B/D/F/H) with 9.9% to about 10%. In dead last, the center class (E) with under 8.7%.

Answer: A/C/G/I

Extra Credit

While the simulation is fairly reliable for showing relative ranking, I decided to go with dynamic programming to find the exact probabilities for the 3 by 3 board.

My main struggle with programming this solution was figuring how best to represent the squares after some have been merged. I had considered tracking a list of edges, and at one point I even thought to use an integer bitmap of the edges for efficient memoization. In the end, I decided to use an adjacency list with some frozenset and dict conversions (since you can't memoize dicts) to make my life easier; Python really does a lot of work for you! And it runs pretty quickly since there are only 9 positions.

from fractions import Fraction
from collections import Counter
from copy import copy
from functools import cache


@cache
def probs(_adj: frozenset[tuple[str, frozenset[str]]]):
    adj = dict(_adj)
    if len(adj) == 1:
        a = max(adj)
        return Counter({a: Fraction(1)})
    totals = Counter({a: Fraction(0) for a in adj})
    for a, opps in adj.items():
        prob = Fraction(1, len(adj) * len(opps) * 2)
        for b in opps:
            for winner, loser in [(a, b), (b, a)]:
                next_adj = copy(adj)
                next_adj[winner] |= next_adj.pop(loser)
                for c in next_adj:
                    if loser in next_adj[c]:
                        next_adj[c] -= {loser}
                        next_adj[c] |= {winner}
                next_adj[winner] -= {winner}
                totals.update(
                    {x: p * prob for x, p in probs(frozenset(next_adj.items())).items()}
                )
    return totals


adj = {
    'A': frozenset('BD'),
    'B': frozenset('ACE'),
    'C': frozenset('BF'),
    'D': frozenset('AEG'),
    'E': frozenset('BDFH'),
    'F': frozenset('CEI'),
    'G': frozenset('DH'),
    'H': frozenset('EGI'),
    'I': frozenset('FH'),
}
frac_probs = probs(frozenset(adj.items()))
print(frac_probs)
print(Counter({x: float(p) for x, p in frac_probs.items()}))

Output:

Counter({'A': Fraction(95802636437, 743178240000), 'C': Fraction(95802636437, 743178240000), 'I': Fraction(95802636437, 743178240000), 'G': Fraction(95802636437, 743178240000), 'F': Fraction(8977833162901, 90296156160000), 'H': Fraction(8977833162901, 90296156160000), 'B': Fraction(8977833162901, 90296156160000), 'D': Fraction(8977833162901, 90296156160000), 'E': Fraction(3912371100007, 45148078080000)})
Counter({'A': 0.1289093669332945, 'C': 0.1289093669332945, 'I': 0.1289093669332945, 'G': 0.1289093669332945, 'F': 0.09942652649568777, 'H': 0.09942652649568777, 'B': 0.09942652649568777, 'D': 0.09942652649568777, 'E': 0.08665642628407096})

Looks quite consistent with our simulations.

The probabilities:

• A/C/G/I: $\frac{95802636437}{743178240000}\approx12.89\%$
  
  
• B/D/F/H: $\frac{8977833162901}{90296156160000}\approx9.94\%$
  
  
• E: $\frac{3912371100007}{45148078080000}\approx8.67\%$
  
  

As for larger board sizes, I'd love to see what a general solution would look like!

Answer: 12.89% for A/C/G/I, 9.94% for B/D/F/H, 8.67% for E