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
            )

En penney, jo separaria el que és una instància de la simulació (una iteració del bucle exterior de penney) del que és repetir la simulació per cada parell d'estratègies: de fet, el bucle exterior l'únic que fa és repetir la mateixa computació per diversos parells d'estratègies, per tant el cos del bucle és un bon candidat per extreure una funció. També separaria la simulació en sí del càlcul de les mètriques (probabilitat i profit).

Per exemple:

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

    :param strategy_tuple: 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(*strategy_tuple) for _ in range(num_games))
    count_by_strategy = Counter(results)
    return count_by_strategy


SimulationResult = namedtuple(
    "SimulationResult",
    field_names=["strategy_tuple", "win_counts", "probability", "profit"],
)


def compute_metrics(win_counts: 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 = main_strategy_count - other_strategies_total
    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.strategy_tuple))
            file.write(f"{strategy_tuple_str} {result.profit}\n")


def main(
    shots=3,
    num_games=10_000,
    main_strategy_index: int = 0,
    out_filename="profit.txt",
    verbose=True,
):
    all_strategy_pairs = strategies_calc(shots=shots)

    results = []
    for i, strategy_tuple in enumerate(all_strategy_pairs):
        main_strategy = strategy_tuple[main_strategy_index]

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

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

        results.append(result)

    write_profit_file(results, filename=out_filename)

Quant a estil, segons les guies d'estil PEP8, no s'ha de dexiar cap línia en blanc entre el final del docstring i el principi del cos de la funció (pero això ja són gustos).

Com a recomanació personal, us recomano black com a linter automàtic. No té (casi) cap configuració, per tant mai haureu d'estar pensant si queda millor d'una manera o d'una altra, simplement delegueu el treball a l'eina per un resultat determinístic i consistent.

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