README.md

Description

Tool to calculate the EV of an intentional draw for a player in a Swiss-pairings tournament (such as Magic: The Gathering)

NOTE: WIP -- it is not complete, and this is just a basic structure for keeping track of the tournament structure, as well as the calculations for a players' own points, as well as the various tiers of tiebreakers.

The intention is to build this basic framework into a tool that can do Monte Carlo style simulations (either exhaustive or sampled) to calculate the EV of intentional draws.

Currently a bit stuck on whether or not I should track results at the Game level, or simply at the Match level. Either way, I'm a little stuck on knowing how to determine if a Match is complete via intentional draw, and it's something that I might just have to special-case. Regardless, it's a tricky situation because I'm also trying to write this to support multiplayer, as well as mixed draw+loss resulst being in a single 4-player game (I.E., two players lose, and the final two players take an intentional draw). I might need to cut out full multiplayer support for the first version in the name of efficiency, but we'll see.

topcut_eval.py

# Top-cut Eval: A tool to evaluate the EV of intentionally drawing in any particular round of a Swiss-paired tournament (such as Magic: The Gathering).
from enum import Enum
from collections import Counter
from typing import List, Dict
from __future__ import annotations
import random

class Result(Enum):
    UNKNOWN = 0
    WIN = 1
    LOSS = 2
    DRAW = 3

class Tiebreaker(Enum):
    OPPONENT_MATCH_WIN_PERCENTAGE = 0
    GAME_WIN_PERCENTAGE = 1
    OPPONENT_GAME_WIN_PERCENTAGE = 2
    RANDOM = 3

class Tournament:
    def __init__(self, players: list[Player], cut_size:int = 8, players_per_match:int = 2, point_structure:dict[Result, int] = {Result.WIN: 3, Result.DRAW: 1, Result.LOSS: 0}, wins_per_match:int = 2):
        self.players = players
        self.rounds = []

        # Ensure that every Result has a corresponding point value (default to 0 if not specified)
        for result in Result:
            if result not in point_structure:
                point_structure[result] = 0

        self.point_structure = point_structure # What is the point value of each possible match result?
        self.wins_per_match = wins_per_match # How many games are required to win a match?

def sort_players(playera:Player, playerb:Player):
    # Sort players by points, then by tiebreaker
    playera_points = playera.get_current_points()
    playerb_points = playerb.get_current_points()
    if playera_points == playerb_points:
        for breaker in [Tiebreaker.OPPONENT_MATCH_WIN_PERCENTAGE, Tiebreaker.GAME_WIN_PERCENTAGE, Tiebreaker.OPPONENT_GAME_WIN_PERCENTAGE, Tiebreaker.RANDOM]:
            breakera = playera.get_tiebreaker(breaker)
            breakerb = playerb.get_tiebreaker(breaker)
            if breakera != breakerb:
                return breakera > breakerb
    else:
        return playera_points > playerb_points

class Round:
    def __init__(self, tournament:Tournament):
        self.tournament = tournament

        # Pair the round
        unpaired_players = tournament.players.copy()

        # Sort players using the sort_players function
        unpaired_players.sort(key=lambda player: sort_players(player))

        # Starting at the top, pair each player with the next highest-ranked player that they haven't yet played against
        self.matches = []
        while len(unpaired_players) > 0:
            player = unpaired_players.pop(0)
            opponents = [player]
            for potential_opponent in unpaired_players:
                if potential_opponent not in player.get_previous_opponents():
                    opponents.append(potential_opponent)
                    if len(opponents) >= tournament.players_per_match:
                        break

            # Remove all opponents from unpaired_players
            for opponent in opponents:
                if opponent in unpaired_players:
                    unpaired_players.remove(opponent)

            # Whether or not we found an opponent, create a match.
            # If we were unable to find valid opponents, then this player gets a bye for the round (is in a match by themselves)
            opponents.append(player)
            self.matches.append(Match(opponents, self, tournament))

class Match:
    def __init__(self, players:list[Player], round:Round, tournament:Tournament):
        self.players = players
        self.round = round
        self.tournament = tournament
        self.games = []

    def get_winner(self):
        # If a player has won the required number of games, they win the match
        # Otherwise, return None

        # Check for the required number of wins
        for player in self.players:
            results = self.get_results(player)
            if results[Result.WIN] >= self.tournament.wins_per_match:
                return player
            
        # TODO: Otherwise, if the match is complete, return the player with the most wins

        # Whether the match is complete or not, return None
        return None
    
    # TODO: Need a mechanism to properly evaluate whether or not a match is intentionally drawn.

    def get_results(self, player):
        # Build a dictionary of the counts of each result for this player
        game_results = Counter()
        for game in self.games:
            game_results[game.results[player]] += 1

        return game_results
    
    def get_results(self):
        game_results = {}
        for player in self.players:
            game_results[player] = self.get_results(player)

        return game_results

class Game:
    def __init__(self, match):
        self.match = match
        self.results = {}

        for player in self.match.players:
            self.results[player] = Result.UNKNOWN

    def get_unreported_players(self):
        return [player for player in self.players if self.results[player] == Result.UNKNOWN]

    def set_result(self, player, result):
        self.results[player] = result
        # If the reported result is a draw, then every other unreported player is also a draw
        if result == Result.DRAW:
            for player in self.get_unreported_players():
                self.results[player] = Result.DRAW

        # If the reported result is a win, then every other unreported player is a loss
        if result == Result.WIN:
            for player in self.get_unreported_players():
                self.results[player] = Result.LOSS

        # If the reported result is a loss, then if there is only one unreported player, then that player has won
        if result == Result.LOSS:
            if len(self.get_unreported_players()) == 1:
                self.results[self.get_unreported_players()[0]] = Result.WIN

    def is_complete(self):
        return len(self.get_unreported_players()) == 0

class Player:
    def __init__(self, name, tournament):
        self.name = name
        self.tournament = tournament

    def get_matches(self):
        # Return all matches in the tournament that contains this player
        return [match for match in self.tournament.matches if self in match.players]
    
    def get_current_match(self):
        return self.get_matches()[-1]
    
    def get_previous_opponents(self):
        # Return all players that this player has played against in the tournament
        return [match.players[0] if match.players[1] == self else match.players[1] for match in self.get_matches()]

    def get_current_points(self):
        # Return the total number of points this player has earned in the tournament
        return sum([self.tournament.point_structure[result] for result in self.get_results()])
    
    def get_total_points_min(self):
        # If the player loses the current match, how many points will they have?
        current_points = self.get_current_points()

        if self.get_current_match().results[self] == Result.UNKNOWN:
            current_points += self.tournament.point_structure[Result.LOSS]

        return current_points
    
    def get_total_points_max(self):
        # If the player wins the current match, how many points will they have?
        current_points = self.get_current_points()

        if self.get_current_match().results[self] == Result.UNKNOWN:
            current_points += self.tournament.point_structure[Result.WIN]

        return current_points
    
    def get_tiebreaker(self, tiebreaker):
        if tiebreaker == Tiebreaker.GAME_WIN_PERCENTAGE:
            # Calculate the percentage of games won by this player
            total_games = 0
            games_won = 0
            for match in self.get_matches():
                for game in match.games:
                    if game.results[self] == Result.WIN:
                        games_won += 1
                    total_games += 1

            return games_won / total_games
        elif tiebreaker == Tiebreaker.OPPONENT_GAME_WIN_PERCENTAGE:
            # Calculate the average percentage of games won by this player's opponents
            total_games = 0
            games_won = 0
            for opponent in self.get_previous_opponents():
                for game in opponent.get_current_match().games:
                    if game.results[opponent] == Result.WIN:
                        games_won += 1
                    total_games += 1

            return games_won / total_games
        
        elif tiebreaker == Tiebreaker.OPPONENT_MATCH_WIN_PERCENTAGE:
            # Calculate the average percentage of matches won by this player's opponents
            total_matches = 0
            matches_won = 0
            for opponent in self.get_previous_opponents():
                if opponent.get_current_match().get_winner() == opponent:
                    matches_won += 1
                total_matches += 1

            return matches_won / total_matches
        elif tiebreaker == Tiebreaker.RANDOM:
            # Return a random value
            return random.random()