Two player card game min max algorithm

minmaxcardgame.py

"""
Two player card game min max 
Run with smaller parameters as it already runs a very long time in python
"""

import random
from dataclasses import dataclass
from collections import Counter, defaultdict
from itertools import combinations
from functools import lru_cache
from typing import Callable, List, Tuple
from functools import lru_cache

# ────────────────────────────────────────────────────────────────────────────────
#  Card rules
# ────────────────────────────────────────────────────────────────────────────────
@dataclass(frozen=True)
class Card:
    id: int
    name: str
    colour: str
    base_power: int
    ability: Callable[["Card", Tuple["Card", ...], Tuple["Card", ...]], int]

# ── ability helpers ─────────────────────────────────────────────────────────────
def no_ability(self, *_):
    return self.base_power

def double_if_friend_colour(colour: str):
    def _impl(self, mine, _):
        return self.base_power * 2 if any(c.colour == colour and c is not self
                                          for c in mine) else self.base_power
    return _impl

def plus_n_per_colour(n: int):
    def _impl(self, mine, _):
        unique = {c.colour for c in mine}
        return self.base_power + n * len(unique)
    return _impl

def plus_if_opponent_colour(colour: str, bonus: int):
    def _impl(self, _, opp):
        return self.base_power + bonus if any(c.colour == colour
                                              for c in opp) else self.base_power
    return _impl

def copy_highest_in_hand(self, mine, _):
    top = max(mine, key=lambda c: c.base_power)
    return top.base_power

def plus_if_specific_opponent(target_id: int, bonus: int):
    def _impl(self, _, opp):
        return self.base_power + bonus if any(c.id == target_id for c in opp) \
                                        else self.base_power
    return _impl

def bonus_if_losing(bonus: int):
    # needs outside score info; we’ll inject later with a wrapper
    def _impl(self, mine, opp):        # dummy, replaced at runtime
        return self.base_power
    return _impl

def random_extra(max_extra: int):
    def _impl(self, *_):
        return self.base_power + random.randint(0, max_extra)
    return _impl

# Cards definitions 
CARDS: List[Card] = [
    # 0-7: survivors from the first set
    Card( 0, "Azure Adept",         "Blue",    4, no_ability),
    Card( 1, "Tidal Trickster",     "Blue",    3, double_if_friend_colour("Blue")),
    Card( 2, "Verdant Vagrant",     "Green",   5, plus_if_opponent_colour("Red", 2)),
    Card( 3, "Sun-Blessed Sage",    "Yellow",  2, plus_n_per_colour(3)),
    Card( 4, "Ruby Raider",         "Red",     6, no_ability),
    Card( 5, "Crimson Crusher",     "Red",     7, no_ability),
    Card( 6, "Emerald Enforcer",    "Green",   7, no_ability),
    Card( 7, "Sapphire Sovereign",  "Blue",    8, no_ability),

    # 8-19: new toys
    Card( 8, "Violet Vortex",       "Purple",  4, plus_n_per_colour(1)),
    Card( 9, "Amber Arcanist",      "Yellow",  5,
         lambda s,m,o: s.base_power+3 if sum(c.colour=="Blue" for c in m)==2
                                         else s.base_power),
    Card(10, "Frostbite Phantom",   "Blue",    6, plus_if_opponent_colour("Red",2)),
    Card(11, "Scorching Salamander","Red",     5, plus_if_opponent_colour("Blue",2)),
    Card(12, "Dusk Doppelgänger",   "Black",   4, copy_highest_in_hand),
    Card(13, "Harmony Herald",      "Green",   3, plus_n_per_colour(1)),
    Card(14, "Crimson Calamity",    "Red",     4, plus_if_specific_opponent(7,3)), # hates Sovereign
    Card(15, "Golden Guardian",     "Yellow",  6, bonus_if_losing(2)),              # patched later
    Card(16, "Shadow Saboteur",     "Black",   3,
         lambda s,m,o: s.base_power+3 if
            max((sum(c.colour==s.colour for c in o)),0) >
            max((sum(c.colour==s.colour for c in m)),0) else s.base_power),
    Card(17, "Blossom Bard",        "Green",   2,
         lambda s,m,_: s.base_power*2 if any(c.colour=="Yellow" for c in m)
                                       else s.base_power),
    Card(18, "Celestial Champion",  "White",   7,
         lambda s,m,_: s.base_power + sum(1 for c in m if c.base_power<4)),
    Card(19, "Chaos Conductor",     "Purple",  5, random_extra(3)),
]

# patch score-aware Golden Guardian
def golden_guardian_ability(self, mine, opp):
    # scores are injected via global during round evaluation
    if CURRENT_SCORES[ME_IDX] < CURRENT_SCORES[OPP_IDX]:
        return self.base_power + 2
    return self.base_power
CARDS[15] = Card(15, "Golden Guardian", "Yellow", 6, golden_guardian_ability)

# ────────────────────────────────────────────────────────────────────────────────
# Game parameters
# ────────────────────────────────────────────────────────────────────────────────
CARDS_PER_DECK  = 10      # keep it small to preserve exact search feasibility
CARDS_PER_ROUND = 6
ROUNDS_PER_GAME = 3
# Min Max search depth (dramatically increases rutime)
MAX_DEPTH = 2 


# Monty Card
NUM_GAMES       = 100   # 20k is still fine; lowered to run faster with new logic

# Tournament parameters
POOL_SIZE        = 40     # how many candidate decks you want
MATCHES_PER_PAIR = 3      # games each A-vs-B pairing
# ────────────────────────────────────────────────────────────────────────────────
# Helper functions
# ────────────────────────────────────────────────────────────────────────────────
def make_deck() -> List[Card]:
    return random.sample(CARDS, CARDS_PER_DECK)

def score_delta(p0: int, p1: int) -> Tuple[int, int]:
    if p0 > p1: return 1,0
    if p1 > p0: return 0,1
    return 0,0

# hooks so Golden Guardian can peek at running score
CURRENT_SCORES = [0,0]
ME_IDX, OPP_IDX = 0,1   # re-assigned each time we evaluate a card

def hand_power(hand: Tuple[Card, ...], opp_hand: Tuple[Card, ...],
               scores: Tuple[int,int], me_idx: int) -> int:
    global CURRENT_SCORES, ME_IDX, OPP_IDX
    CURRENT_SCORES = list(scores)
    ME_IDX, OPP_IDX = me_idx, 1-me_idx
    return sum(c.ability(c, hand, opp_hand) for c in hand)

# ────────────────────────────────────────────────────────────────────────────────
#  Perfect-play minimax
# ────────────────────────────────────────────────────────────────────────────────
State = Tuple[Tuple[Card,...], Tuple[Card,...], int, int, int, int]  

@lru_cache(maxsize=None)
def state_value(state: State) -> int:
    my_deck, opp_deck, rnd, my_sc, opp_sc, depth_left = state


    if rnd == ROUNDS_PER_GAME or depth_left == 0:
        # simple heuristic: current score diff plus
        # (sum of my remaining base power − opp remaining) / 10
        my_p  = sum(c.base_power for c in my_deck)
        opp_p = sum(c.base_power for c in opp_deck)
        return (my_sc - opp_sc) + (my_p - opp_p) / 10.0

    best = -float('inf')
    for my_hand in combinations(my_deck, CARDS_PER_ROUND):
        worst =  float('inf')
        for opp_hand in combinations(opp_deck, CARDS_PER_ROUND):
            p_my  = hand_power(my_hand,  opp_hand, (my_sc, opp_sc), 0)
            p_opp = hand_power(opp_hand, my_hand,  (my_sc, opp_sc), 1)
            d0,d1 = score_delta(p_my, p_opp)

            nxt = (my_deck, opp_deck, rnd+1,
                   my_sc+d0, opp_sc+d1, depth_left-1)
            worst = min(worst, state_value(nxt))
            if worst <= best: break   # β-cut
        best = max(best, worst)
    return best

def choose_hand_minimax(my_deck, opp_deck, rnd, scores, me_idx):
    """
    Pick the 6-card hand that maximises my worst-case outcome,
    searching MAX_DEPTH rounds ahead (depth-0 = heuristic only).
    """
    # -- unpack scores *before* anything else or you get UnboundLocalError!
    my_sc, opp_sc = scores if me_idx == 0 else scores[::-1]

    best_val  = -float("inf")
    best_hand = None

    for hand in combinations(my_deck, CARDS_PER_ROUND):
        worst = float("inf")                      # opponent minimises me

        for opp_hand in combinations(opp_deck, CARDS_PER_ROUND):
            p_my  = hand_power(hand,  opp_hand, scores, me_idx)
            p_opp = hand_power(opp_hand, hand,  scores, 1 - me_idx)
            d0, d1 = score_delta(p_my, p_opp)

            # absolute (player-0) score update
            new_scores = (my_sc + d0, opp_sc + d1) if me_idx == 0 \
                         else (opp_sc + d1, my_sc + d0)

            nxt_state = (tuple(my_deck), tuple(opp_deck), rnd + 1,
                         new_scores[0], new_scores[1], MAX_DEPTH - 1)
            worst = min(worst, state_value(nxt_state))
            if worst <= best_val:                 # α–β prune
                break

        if worst > best_val:
            best_val, best_hand = worst, hand

    # safety fallback (should never hit)
    if best_hand is None:
        print("fallback hit")
        best_hand = next(iter(combinations(my_deck, CARDS_PER_ROUND)))

    return list(best_hand)

def choose_hand_ai(idx, decks, scores, rnd):
    return choose_hand_minimax(decks[idx], decks[1-idx], rnd, tuple(scores), idx)

# ────────────────────────────────────────────────────────────────────────────────
#  Play one game
# ────────────────────────────────────────────────────────────────────────────────
def play_game():
    decks  = [make_deck(), make_deck()]
    scores = [0,0]

    for r in range(ROUNDS_PER_GAME):
        hands = [choose_hand_ai(i,decks,scores,r) for i in (0,1)]
        p0 = hand_power(tuple(hands[0]), tuple(hands[1]), tuple(scores), 0)
        p1 = hand_power(tuple(hands[1]), tuple(hands[0]), tuple(scores), 1)
        d0,d1 = score_delta(p0,p1)
        scores[0]+=d0; scores[1]+=d1


    if scores[0]>scores[1]: return 0,decks
    if scores[1]>scores[0]: return 1,decks
    return None,decks

# ────────────────────────────────────────────────────────────────────────────────
#  Tournament driver 
# ────────────────────────────────────────────────────────────────────────────────


def play_game_fixed(deck0, deck1):
    """
    Same as play_game() but uses the provided decks (they *do not* shrink).
    """
    decks  = [list(deck0), list(deck1)]
    scores = [0, 0]

    for rnd in range(ROUNDS_PER_GAME):
        hands = [choose_hand_ai(i, decks, scores, rnd) for i in (0, 1)]

        p0 = hand_power(tuple(hands[0]), tuple(hands[1]), tuple(scores), 0)
        p1 = hand_power(tuple(hands[1]), tuple(hands[0]), tuple(scores), 1)
        d0, d1 = score_delta(p0, p1)
        scores[0] += d0
        scores[1] += d1

    if scores[0] > scores[1]:
        return 0
    if scores[1] > scores[0]:
        return 1
    return None   # draw

def build_deck_pool(n: int = POOL_SIZE) -> List[List[Card]]:
    # Return n unique random decks (no duplicates).
    pool: List[List[Card]] = []
    seen: set[Tuple[int, ...]] = set()

    while len(pool) < n:
        deck = make_deck()                              # draw a candidate
        key  = tuple(sorted(c.id for c in deck))        # canonical form
        if key not in seen:                             # uniqueness check
            pool.append(deck)
            seen.add(key)
    return pool

def run_tournament(pool, games_per_pair=MATCHES_PER_PAIR):
    win_cnt   = Counter()           # deck-id → wins
    play_cnt  = Counter()           # deck-id → games played

    for i, deckA in enumerate(pool):
        for j, deckB in enumerate(pool):
            if i >= j:              # only unique unordered pairs
                continue
            for _ in range(games_per_pair):
                winner = play_game_fixed(deckA, deckB)
                play_cnt[i] += 1
                play_cnt[j] += 1
                if winner == 0:
                    win_cnt[i] += 1
                elif winner == 1:
                    win_cnt[j] += 1
                # draws just count as games played
    # compute win-rates
    win_rates = {idx: win_cnt[idx] / play_cnt[idx]
                 for idx in play_cnt}
    return win_rates

# ────────────────────────────────────────────────────────────────────────────────
#  Monty Carlo Simulation driver
# ────────────────────────────────────────────────────────────────────────────────
def run_sim(n_games=NUM_GAMES):
    wins, plays, deck_wins = Counter(), Counter(), defaultdict(int)
    for _ in range(n_games):
        winner, final_decks = play_game()
        for c in final_decks[0]+final_decks[1]:
            plays[c.id]+=1
        if winner is not None:
            for c in final_decks[winner]:
                wins[c.id]+=1
            deck_wins[tuple(sorted(c.id for c in final_decks[winner]))]+=1
    return wins, plays, deck_wins

# MAIN! 
if __name__ == "__main__":
    # Monty Carlo
    # wins, plays, deck_wins = run_sim()
    # print("Card performance over", NUM_GAMES, "perfect-play games")
    # hdr = f"{'ID':>2}  {'Name':<20} {'Base':>4} {'WinRate':>8}"
    # print(hdr); print("─" * len(hdr))
    # card_rates = [(cid, wins[cid] / plays[cid] if plays[cid] else 0.0)
    #               for cid in plays]
    # for cid, wr in sorted(card_rates, key=lambda kv: kv[1], reverse=True):
    #     c = CARDS[cid]
    #     print(f"{cid:>2}  {c.name:<20} {c.base_power:>4} {wr:>8.3f}")

    # Tournament Style 
    pool = build_deck_pool()
    deck_rates = run_tournament(pool)

    print("\nTop five decks in the pool (round-robin, perfect-play):")
    top_5 = sorted(deck_rates.items(), key=lambda kv: kv[1], reverse=True)[:5]
    for rank, (idx, rate) in enumerate(top_5, 1):
        names = ", ".join(f"{c.name}" for c in pool[idx])
        print(f"{rank:>2}.  WinRate {rate:>5.2%}  →  {names}")

Randomly picking decks, and the percentage of wins if the card is present in the deck.

Card performance over 50000 perfect-play games
ID  Name                 Base  WinRate
──────────────────────────────────────
 3  Sun-Blessed Sage        2    0.618
 8  Violet Vortex           4    0.538
18  Celestial Champion      7    0.537
10  Frostbite Phantom       6    0.520
 7  Sapphire Sovereign      8    0.519
13  Harmony Herald          3    0.512
 6  Emerald Enforcer        7    0.501
 5  Crimson Crusher         7    0.498
12  Dusk Doppelgänger       4    0.496
19  Chaos Conductor         5    0.493
 2  Verdant Vagrant         5    0.493
15  Golden Guardian         6    0.490
11  Scorching Salamander    5    0.487
 9  Amber Arcanist          5    0.481
 4  Ruby Raider             6    0.476
 0  Azure Adept             4    0.458
 1  Tidal Trickster         3    0.451
14  Crimson Calamity        4    0.447
16  Shadow Saboteur         3    0.417
17  Blossom Bard            2    0.414

Tournament with 40 random decks, 3 plays each

Top five decks in the pool (round-robin, perfect-play):
 1.  WinRate 100.00%  →  Golden Guardian, Sun-Blessed Sage, Scorching Salamander, Violet Vortex, Dusk Doppelgänger, Verdant Vagrant, Crimson Calamity, Sapphire Sovereign, Chaos Conductor, Emerald Enforcer
 2.  WinRate 89.74%  →  Sun-Blessed Sage, Amber Arcanist, Celestial Champion, Harmony Herald, Crimson Crusher, Golden Guardian, Frostbite Phantom, Sapphire Sovereign, Azure Adept, Violet Vortex
 3.  WinRate 88.89%  →  Amber Arcanist, Violet Vortex, Frostbite Phantom, Ruby Raider, Harmony Herald, Sun-Blessed Sage, Blossom Bard, Scorching Salamander, Crimson Calamity, Emerald Enforcer
 4.  WinRate 88.89%  →  Sun-Blessed Sage, Golden Guardian, Harmony Herald, Violet Vortex, Sapphire Sovereign, Tidal Trickster, Scorching Salamander, Verdant Vagrant, Azure Adept, Chaos Conductor
 5.  WinRate 87.18%  →  Frostbite Phantom, Dusk Doppelgänger, Violet Vortex, Sun-Blessed Sage, Golden Guardian, Amber Arcanist, Emerald Enforcer, Verdant Vagrant, Crimson Crusher, Scorching Salamander