A Doomed Solitaire and Baby Poker

The Riddler for December 30, 2016. The Express is a card-counting game whose tidy-looking answer hides a derangement; the Classic is a tiny poker game where bluffing is provably optimal.

Riddler Express

You deal a shuffled 52-card deck one card at a time, chanting “ace, two, …, king, ace, two, …” as you go. If the rank you say ever matches the rank you deal, you lose. What is your probability of getting through the whole deck with no match?

The Riddler, FiveThirtyEight, December 30, 2016(original post)

Solution

The tempting shortcut is to say each card independently dodges its spoken rank with probability $\tfrac{12}{13}$, giving $(12/13)^{52} \approx 0.0156$. That is a good estimate but not exact, because the cards are not independent: there are only four of each rank, so dealing one ace makes the next ace rarer. The honest count has to respect that.

Set it up as a placement problem. There are $52$ slots; slot $i$ has a “spoken rank” $((i-1)\bmod 13)$, and slot $i$ is one of the four slots forbidden to that rank. Each of the 13 ranks has 4 cards and exactly 4 forbidden slots, and these forbidden groups are disjoint. We want the number of rank-arrangements with no card in a forbidden slot, a generalised derangement. By inclusion-exclusion, force $i$ of a rank’s four cards into its forbidden slots (choosing the slots $\binom{4}{i}$ ways, sign $(-1)^i$), and arrange the rest freely; per rank this contributes a factor $a_i = (-1)^i \binom{4}{i}/(4-i)!$. Collecting by the total number $M$ of forced cards, $$P(\text{win}) = \frac{(4!)^{13}}{52!}\sum_{M} (52-M)!\,\bigl[x^M\bigr]\Bigl(\textstyle\sum_{i=0}^{4} a_i x^i\Bigr)^{13}.$$ Evaluating exactly, $$P(\text{win}) \approx \boxed{0.01623},$$ about $1.6\%$. The independence estimate $(12/13)^{52} \approx 0.0156$ lands in the same neighbourhood by luck of large numbers, but the true value, $0.016233\ldots$, comes from the derangement count above.

The computation

Encode the exact inclusion-exclusion with rational arithmetic, then confirm by simulating shuffled decks.

from fractions import Fraction as F
from math import factorial, comb
import random
a = [F((-1)**i * comb(4, i), factorial(4 - i)) for i in range(5)]    # per-rank factors
poly = {0: F(1)}                                                      # (sum a_i x^i)^13
for _ in range(13):
    nxt = {}
    for e, c in poly.items():
        for i in range(5): nxt[e + i] = nxt.get(e + i, F(0)) + c * a[i]
    poly = nxt
valid = sum(poly[M] * factorial(52 - M) for M in poly)
P = valid / F(factorial(52), factorial(4)**13)
print("exact P(win):", round(float(P), 5))

ranks = [r for r in range(13) for _ in range(4)]; rng = random.Random(0); wins = 0
for _ in range(500_000):
    rng.shuffle(ranks)
    if all(ranks[i] != i % 13 for i in range(52)): wins += 1
print("simulated:", round(wins / 500_000, 5))
# exact P(win): 0.01623
# simulated: 0.0166

Riddler Classic

In baby poker, A and B each ante $1 and roll a hidden die. A may “call” (showdown for the $2, higher die wins) or “raise” $1. If A raises, B may “fold” (A takes the pot, B loses only the ante) or “call” the extra dollar (showdown for $4). Ties split. What are the optimal strategies, and how much should A pay B beforehand to make the game fair?

The Riddler, FiveThirtyEight, December 30, 2016(original post)

Solution

This is a finite zero-sum game, so an optimal pair of strategies exists and can be found by minimax. Two reductions cut the work. Player B should never bluff, calling only with high rolls, so her sensible strategies are “call with $x$ or higher”. Player A clearly raises his best rolls; the only question is whether to ever raise a bad roll as a bluff. Solving the game shows he should.

The optimal play is $$\boxed{ \begin{array}{l} \text{A: raise }5,6;\ \text{call }2,3,4;\ \text{with a }1,\ \text{raise }\tfrac23\text{ of the time.}\\ \text{B: call }4,5,6;\ \text{call }2,3\text{ w.p. }\tfrac13;\ \text{fold }1. \end{array}}$$ A bluffs his worst roll precisely because it is worthless in a showdown, so betting it loses nothing extra on average while forcing B to call light and pay off his genuine raises. Under optimal play the game is worth $$\frac{5}{54} \approx \$0.093 \text{ to Player A},$$ the advantage of moving first and setting the price of a call. To make it fair, A should pay B about nine cents before each hand.

The computation

Encode the game two ways. First solve it from scratch: build the payoff matrix over A’s raising-sets and B’s calling-thresholds and find the minimax value by linear programming. Then confirm the value exactly by evaluating the boxed mixed strategies with rational arithmetic.

from fractions import Fraction as F
import itertools, numpy as np
from scipy.optimize import linprog
def payoff(Araise, Bcall):                  # net dollars to A, averaged over 36 die pairs
    tot = 0
    for a in range(1, 7):
        for b in range(1, 7):
            if a not in Araise:             # A calls -> showdown for $2
                tot += 0 if a == b else (1 if a > b else -1)
            elif b not in Bcall:            # A raises, B folds
                tot += 1
            else:                           # A raises, B calls -> showdown for $4
                tot += 0 if a == b else (2 if a > b else -2)
    return tot / 36
A = [set(s) | {6} for r in range(6) for s in itertools.combinations(range(1, 6), r)]
A = [set(t) for t in {frozenset(s) for s in A}]            # A always raises 6 (dominance)
B = [set(range(x, 7)) for x in range(1, 8)]                # B calls iff >= x
M = np.array([[payoff(a, b) for b in B] for a in A])
nA, nB = M.shape                                            # maximise v s.t. p.M >= v
res = linprog(np.r_[np.zeros(nA), -1], A_ub=np.c_[-M.T, np.ones(nB)],
              b_ub=np.zeros(nB), A_eq=[[1]*nA + [0]], b_eq=[1],
              bounds=[(0, 1)]*nA + [(None, None)])
print("LP game value to A:", round(res.x[-1], 4))

pA = {1: F(2,3), 5: F(1), 6: F(1)}; pB = {2: F(1,3), 3: F(1,3), 4: F(1), 5: F(1), 6: F(1)}
val = F(0)
for a in range(1, 7):
    for b in range(1, 7):
        pr = pA.get(a, F(0)); pc = pB.get(b, F(0))
        call = F(0) if a == b else (F(1) if a > b else F(-1))
        rais = (1 - pc)*F(1) + pc*(F(0) if a == b else (F(2) if a > b else F(-2)))
        val += F(1, 36) * ((1 - pr)*call + pr*rais)
print("exact value to A:", val, "=", round(float(val), 4))
# LP game value to A: 0.0926
# exact value to A: 5/54 = 0.0926