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
            )

Unused import:

import pprint as pp

:)

I el numpy també el treuria si només l'utilitzes per random; utilitza el mòdul estàndard així no necessites cap dependència externa:

import random

Jo posaria les constants H/T en un enum:

import enum

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

I llavors accedir-hi amb Outcomes.H i Outcomes.T. O pots fer H = Outcomes.H i T = Outcomes.T si no vols escriure tant 😆

Això també serveix per una altra cosa que diré després.

Línia 26:

shot = np.random.randint(H, T + 1)

aquí millor un random.choice:

shot = random.choice([H, T])

o

shot = random.choice(list(Outcomes))

Faria una classe per Strategy per no haver de fer una funció repr_strategy a part:

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

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

Aquí aprofito que els membres de l'enum Outcome tenen la proprietat name (que serà "H" o "T", o com ho hagis definit a l'enum).

Llavors pots eliminar repr_strategy i a la línia 103 escriure:

repr_strategies = " ".join(map(str, strategy))

Línia 31:

if shot is strategy[hit]:

Aquí, conceptualment, estem comparant el valor del resultat de l'assaig amb la "predicció" de l'estratègia, no si són idènticament el mateix objecte. Jo utilitzaria == en comptes de is. Aquí no passa res perquè estàs comparant sempre amb les mateixes constants (idènticament), però si per exemple la estratègia fós una llista d'ints sense utilitzar H o T, podria fallar la comparació en principi.

A mi personalment no m'agrada treballar amb índex i referències "indirectes". Reescriuria la funció play de manera que retornés l'objecte estratègia en sí:

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

    Example:
    ```
    game_strategy = [(H, H, H), (H, T, T)]
    play(game_strategy) is game_strategy[1]
    ```
    """
    max_hits = len(game_strategy[0])
    hits = Counter()

    while max(hits.values()) < max_hits:
        shot = random.choice([Outcomes.H, Outcomes.T])

        for strategy in game_strategy:
            hit = hits[game_strategy]

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

    return hits.most_common()[0][0]

Per tant reescriuria penney així:

def penney(
    num_games: int, probability_strategy_index: int, shots: int, verbose: bool = False
) -> list:
    """
    Returns a list of tuples with the played strategy,
    the games count, the probability of winning for the
    given `probability_strategy_index` and its profit.
    """

    strategies = strategies_calc(shots)
    game_strategies = []

    for i, strategy_pair in enumerate(strategies):
        probability_strategy = strategy_pair[probability_strategy_index]
        
        games = []
        for _ in range(num_games):
            winning_strategy = play(strategy_pair)
            games.append(winning_strategy)

        repr_strategies = " ".join(map(repr, strategy_pair))
        count_by_strategy = Counter(games)

        rest_games = [
            count
            for strategy, count in count_by_strategy.items()
            if strategy is not probability_strategy
        ]
        
        probability = count_by_strategy[probability_strategy]/num_games
        profit = count_by_strategy[probability_strategy] - sum(rest_games)

        # [...]

A la funció strategy_calc, faria un product de les estratègies per simplificar—en realitat un "match" entre dues estratègies iguals és igual de vàlid que qualsevol altre! Ho pots utilitzar com a "control": quan les estratègies són iguals, la probabilitat empírica haurà de ser prop del 50% i el profit proper a 0. (Encara que ara m'he adonat que caldria modificar play de manera que no li afectin els duplicats.)

def strategies_calc(shots: int) -> list:
    """
    Returns the list of all possible strategy pairs of a given length (`shots`).
    """
    strategies = map(Strategy, itertools.product([Outcomes.H, Outcomes.T], repeat=shots))
    pairs = list(itertools.product(strategies, repeat=2))
    return pairs

O, si vols filtrar les que són iguals, utilitzaria itertools.product encara (que és "mandrós") i després filtraria amb un list comprehension:

def strategies_calc(shots: int) -> list:
    """
    Returns the 56 strategy pairs list.
    """
    strategies = map(Strategy, itertools.product([Outcomes.H, Outcomes.T], repeat=shots))
    pairs = itertools.product(strategies, repeat=2)
    return [(x, y) for x, y in pairs if x != y]

Altre cop utilitzaria == o != en comptes de is.

Línia 104:

count_by_strategy = dict(Counter(games))

No cal convertir a dict perquè un Counter ja és un dict; a més ofereix funcionalitat especialitzada per contadors/multisets. Per tant:

count_by_strategy = Counter(games)

Reescriuria el càlcul de profit en penney així, per fer-ho més senzill:

        main_strategy = strategy_tuple[probability_strategy_index]

        # [...]

        count_by_strategy = Counter(games)
        main_strategy_count = count_by_strategy[main_strategy]
        other_strategies_total = num_games - main_strategy_count

        probability = main_strategy_count/num_games
        profit = main_strategy_count - other_strategies_total

Per la funció play, si saps que sempre passaràs o requeriràs exactament dos estratègies, ho faría explícit amb dos paràmetres, en comptes d'acceptar un sol paràmetre que pot ser una llista de qualsevol longitud:

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)
    max_hits = len(strategy1)
    hits = Counter()

    while max(hits.values(), default=0) < max_hits:
        shot = random.choice([Outcomes.H, Outcomes.T])

        for strategy in strategies:
            next_hit = hits[strategy]

            if shot == strategy[next_hit]:
                hits[strategy] += 1
            else:
                hits[strategy] = 0

    return hits.most_common()[0][0]

i llavors, dins penney (nótese l'asterisc):

    for i, strategy_tuple in enumerate(strategies):
        # [...]

        games = []
        for _ in range(num_games):
            winning_strategy = play(*strategy_tuple)
            games.append(winning_strategy)

O si voleu acceptar un número arbitrari d'estratègies podeu for això:

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

    Example:
        >>> strategy_pair = [(H, H, H), (H, T, T)]
        >>> play(*strategy_pair) is strategy_pair[1]
    """
    strategies = set(strategies)
    max_hits = len(strategy1)
    assert all(len(s) == max_hits for s in strategies)
    hits = Counter({s: 0 for s in strategies})

    while max(hits.values()) < max_hits:
        shot = random.choice([Outcomes.H, Outcomes.T])

        for strategy in strategies:
            next_hit = hits[strategy]

            if shot == strategy[next_hit]:
                hits[strategy] += 1
            else:
                hits[strategy] = 0

    return hits.most_common()[0][0]

Amb el mateix ús a penney.

Relacionat amb el comentari anterior: no sé si cal escollir a cada "trucada" (:laughing:) de penney l'índex de l'estratègia de la qual es vol calcular la probabilitat. Per simplificar-ho, jo ho especificaria "per convenció" a la funció, e.g. la primera estratègia és sempre la "principal", la que s'està evaluant. Per exemple amb un paràmetre amb valor per defecte:

def penney(
    num_games: int,
    shots: int,
    verbose: bool = False,
    main_strategy_index=0,
) -> list:
    """
    Returns a list of tuples with the played strategies, the game counts, 
    the probability of the first (unless otherwise specified by `main_strategy_index`) 
    strategy winning and its profit.
    """
    strategies = strategies_calc(shots)
    game_strategies = []

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

        games = []
        # TODO: more_itertools repeatfunc
        for _ in range(num_games):
            winning_strategy = play(*strategy_tuple)
            games.append(winning_strategy)

        count_by_strategy = Counter(games)
        main_strategy_count = count_by_strategy[main_strategy]
        other_strategies_total = num_games - main_strategy_count

        probability = main_strategy_count / num_games
        profit = main_strategy_count - other_strategies_total

        repr_strategies = " ".join(map(str, strategy_tuple))
        summary = (repr_strategies, count_by_strategy, probability, profit)

        if verbose:
            print(f"{i}.\t{summary}")

        game_strategies.append(summary)

    return game_strategies

Això:

        games = []
        for _ in range(num_games):
            winning_strategy = play(*strategy_tuple)
            games.append(winning_strategy)

també ho simplificaria a això:

games = [play(*strategy_tuple) for _ in range(num_games)]

    file = open(filename, 'w')
    for strategy in game_strategies:
        file.write(f'{strategy[0]} {strategy[3]}\n')
    file.close()

Sempre millor utilitzar un with per obrir i tancar un arxiu, així no hi ha risc de no tancar l'arxiu (fins i tot si hi ha una excepció):

    with open(filename, "w") as file:
        for strategy in game_strategies:
            file.write(f'{strategy[0]} {strategy[3]}\n')

Pel verbose, crec que sempre és millor escriure a stderr en comptes de stdout si són missatges de debug:

import sys

print(..., file=sys.stderr)

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