Implementation of the winning probabilities in Penney’s game

penney.py

import collections
import itertools
import operator
import random
import sys
from enum import Enum


class Outcomes(Enum):
    H = 0
    T = 1


class Strategy(tuple):
    def __str__(self):
        return "".join(outcome.name for outcome in self)

    def __repr__(self):
        return f"<Strategy({str(self)})>"


def play(*strategies: tuple) -> Strategy:
    """
    Plays a game match with the given `strategies`
    and returns the winning strategy.

    Example:
    ```
    strategy_pair = [(H, H, H), (H, T, T)]
    play(*strategy_pair) is strategy_pair[1]
    ```
    """
    max_hits = len(strategies[0])
    assert all(len(s) == max_hits for s in strategies)
    assert all(
        all(isinstance(x, Outcomes) for x in strategy) for strategy in strategies
    )

    current_sequence = collections.deque(maxlen=max_hits)
    while True:
        shot = random.choice(list(Outcomes))
        current_sequence.append(shot)

        for strategy in strategies:
            element_comparisons = itertools.zip_longest(strategy, current_sequence)
            if all(itertools.starmap(operator.eq, element_comparisons)):
                return strategy


def strategies_calc(shots: int, players: int, allow_eq_pairs: bool = False) -> list:
    """
    Returns the list of all possible strategy pairs of a given length (`shots`).
    """
    strategies = map(Strategy, itertools.product(list(Outcomes), repeat=shots))
    pairs = list(itertools.product(strategies, repeat=players))

    if allow_eq_pairs:
        return pairs
    else:
        return [(x, y) for x, y in pairs if x != y]


def penney(strategies: tuple, num_games: int) -> collections.Counter:
    """
    Simulates running Penney's game multiple times for a fixed strategy pair/tuple.

    :param strategies: Strategies of each of the participating players.
    :param num_games: Number of times to simulate the same game.
    :return: A counter keyed by strategy of the number of games won.
    """
    results = (play(*strategies) for _ in range(num_games))
    count_by_strategy = collections.Counter(results)
    return count_by_strategy


def compute_metrics(win_counts: collections.Counter, strategy: Strategy) -> tuple:
    num_games = sum(win_counts.values())
    main_strategy_count = win_counts[strategy]
    other_strategies_total = num_games - main_strategy_count

    probability = main_strategy_count / num_games
    profit = probability - other_strategies_total / num_games
    return probability, profit


def write_profit_file(results: list, filename: str) -> None:
    """
    Writes a file with the profit of all played strategies.
    """
    with open(filename, "w") as file:
        for result in results:
            strategy_tuple_str = " ".join(map(str, result.strategies))
            file.write(f"{strategy_tuple_str} {result.profit:.4f}\n")


SimulationResult = collections.namedtuple(
    "SimulationResult",
    field_names=["strategies", "win_counts", "probability", "profit"],
)


def compute_penney_results(
    all_strategies: list,
    num_games: int = 10_000,
    main_strategy_index: int = 0,
    verbose: bool = True,
):
    results = []
    for i, strategies in enumerate(all_strategies):
        main_strategy = strategies[main_strategy_index]

        win_counts = penney(strategies, num_games)
        probability, profit = compute_metrics(win_counts, main_strategy)
        result = SimulationResult(
            strategies=strategies,
            win_counts=win_counts,
            probability=probability,
            profit=profit,
        )

        if verbose:
            print(
                f"{i+1:>2}. {' '.join(map(str, strategies))}\t\t"
                f"{win_counts=}\t{probability=}\t{profit=:.4f}",
                file=sys.stderr,
            )

        results.append(result)

    return results


def main(
    shots: int = 3,
    players: int = 2,
    num_games: int = 10_000,
    main_strategy_index: int = 0,
    allow_eq_pairs: bool = False,
    out_filename: str = "profit.txt",
    verbose: bool = True,
):
    all_strategies = strategies_calc(shots, players, allow_eq_pairs)

    results = compute_penney_results(
        all_strategies,
        num_games,
        main_strategy_index,
        verbose,
    )

    write_profit_file(results, filename=out_filename)

penney_test.py

import penney as p
import unittest


H = p.Outcomes.H
T = p.Outcomes.T


class TestPenney(unittest.TestCase):
    def test_probabilities(self):
        all_strategies_probabilities = {
            (p.Strategy((H, H, H)), p.Strategy((T, H, H))): 7 / 8,
            (p.Strategy((H, H, T)), p.Strategy((T, H, H))): 3 / 4,
            (p.Strategy((H, T, H)), p.Strategy((H, H, T))): 2 / 3,
            (p.Strategy((H, T, T)), p.Strategy((H, H, T))): 2 / 3,
            (p.Strategy((T, H, H)), p.Strategy((T, T, H))): 2 / 3,
            (p.Strategy((T, H, T)), p.Strategy((T, T, H))): 2 / 3,
            (p.Strategy((T, T, H)), p.Strategy((H, T, T))): 3 / 4,
            (p.Strategy((T, T, T)), p.Strategy((H, T, T))): 7 / 8,
        }

        results = p.compute_penney_results(
            all_strategies=all_strategies_probabilities.keys(), main_strategy_index=1
        )

        for result in results:
            self.assertAlmostEqual(
                all_strategies_probabilities[result[0]], result[2], delta=0.01
            )

Ah, I el més important de tot, que entre tant refactoring m'he passat de llarg! He estat veient les probabilitats que surtien i alguna cosa no quadrava... I efectivament, la implementació de play no és del tot correcta: en particular, quan hi ha un mismatch, posa el contador a 0:

            if shot is strategy[hit]:
                hits[i] += 1
            else:
                hits[i] = 0

però això no és necessariament correcte! Per exemple, si la meva estratègia és HHT i a un punt la seqüència fa ...HHH, no hem de resetejar el comptador a 0, sinó a 2, ja que si trobem una altra T ja guanyo!

Això em recorda a l'algorisme KMP: si volem fer aquest "scan" linear de la seqüència sense mirar enrere, hem de resetejar el comptador al número de la longitud del "border" més llarg de l'estratègia (si la representem com un string). O sinó podem fer la versió simple de força bruta ;)

Per exemple:

from collections import deque
import operator


def play(strategy1: Strategy, strategy2: Strategy) -> Strategy:
    """
    Plays a game match with a strategy pair
    and returns the winning strategy.

    Example:
        >>> strategy_pair = [(H, H, H), (H, T, T)]
        >>> play(*strategy_pair) is strategy_pair[1]
    """
    strategies = {strategy1, strategy2}
    assert len(strategy1) == len(strategy2)
    assert all(
        all(isinstance(x, Outcomes) for x in strategy) for strategy in strategies
    )
    max_hits = len(strategy1)

    current_sequence = deque(maxlen=max_hits)
    while True:
        shot = random.choice(list(Outcomes))
        current_sequence.append(shot)

        for strategy in strategies:
            element_comparisons = itertools.zip_longest(strategy, current_sequence)
            if all(itertools.starmap(operator.eq, element_comparisons)):
                return strategy