mcts.py

"""Investigating and implementing MCTS without the complications of the MTG simulator."""

from collections import Counter
from copy import deepcopy
import math
import random
import cProfile

compose = lambda f: lambda g: lambda *args, **kwds: f(g(*args, **kwds))

# Implementation of a very simple game: 3x3 Noughts and Crosses

DRAW = 2

class GameState:
    def __init__(self, board, move_history, active_player_idx):
        self.board = board
        self.move_history = move_history
        self.active_player_idx = active_player_idx

    def print_board(self):
        print(*self.board[0], sep='|')
        print('-----')
        print(*self.board[1], sep='|')
        print('-----')
        print(*self.board[2], sep='|')
        print()

    def but(self, board=None, move_history=None, active_player_idx=None):
        return GameState(board=self.board if board is None else board,
                         move_history=self.move_history if move_history is None else move_history,
                         active_player_idx=self.active_player_idx if active_player_idx is None else active_player_idx)

    def get_result(self):
        winner = self.winner()
        if winner is not None:
            return winner
        if len(self.moves()) == 0:
            return DRAW
        return None
    
    def game_over(self):
        return self.get_result() is not None

    def winner(self):
        for i in range(3):
            if self.board[i][0] == self.board[i][1] == self.board[i][2] != ' ':
                return int(self.board[i][0])
            if self.board[0][i] == self.board[1][i] == self.board[2][i] != ' ':
                return int(self.board[0][i])
        if self.board[0][0] == self.board[1][1] == self.board[2][2] != ' ':
            return int(self.board[0][0])
        if self.board[0][2] == self.board[1][1] == self.board[2][0] != ' ':
            return int(self.board[0][2])
        return None
    
    def is_valid_action(self, action):
        if action is None:
            return False
        i, j = action
        return self.board[i][j] == ' '

    @property
    def moves_taken(self):
        return len(self.move_history)
    
    @compose(list)
    def moves(self):
        if False:#self.moves_taken == 0:
            yield from [(0, 0), (0, 1), (1, 1)]
        elif False:#self.moves_taken == 1:
            if self.board[0][0] == '0':
                yield from [(0, 1), (1, 1), (0, 2), (1, 2), (2, 2)]
            elif self.board[0][1] == '0':
                yield from [(0, 0), (1, 0), (1, 1), (2, 0), (2, 1)]
            elif self.board[1][1] == '0':
                yield from [(0, 0), (0, 1)]
        else:
            for i in range(3):
                for j in range(3):
                    if self.board[i][j] == ' ':
                        yield (i, j)

    def turn_with_move(self, action):
        if not self.is_valid_action(action):
            raise RuntimeError(f'Invalid move: {action}')
        
        new_state = self.resolve_action(action)
            
        if self.game_over():
            return new_state
        
        return new_state.but(active_player_idx=(self.active_player_idx + 1) % 2)

    def resolve_action(self, action):
        i, j = action

        new_board = deepcopy(self.board)
        new_mh = deepcopy(self.move_history)
        
        new_board[i][j] = str(self.active_player_idx)
        new_mh.append((i, j))
        
        return self.but(board=new_board, move_history=new_mh)

class Game:
    def __init__(self, players):
        board = []
        for i in range(3):
            board.append([])
            for j in range(3):
                board[i].append(' ')
                
        self.state = GameState(board, [], 0)
        self.players = players

    @property
    def active_player(self):
        return self.players[self.state.active_player_idx]

    @property
    def board(self):
        return self.state.board

    def print_board(self):
        self.state.print_board()

    def turn(self, do_print=False):
        action = self.active_player.get_action(self)
        self.state = self.state.turn_with_move(action)
        if do_print:
            self.print_board()
        return self.state.get_result()


class Player:
    pass

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

    def get_action(self, game):
        return game.state.moves()[0]

class MCTSTree:
    """An MCTS search tree

    An iteration of MCTS (Monte Carlo tree search) has four steps: selection, expansion, simulation, and backpropagation.

    Selection: descend the tree until a node is reached with no children or a terminal node is reached
    Expansion: if the selected node is non-terminal, add one or more node(s) to the selected node and choose one as the new selected node.
    Simulation: simulate the game until the end, choosing all actions randomly.
    Backpropagation: update the values at each node from the selected node all the way up to the root node.
    """
    def __init__(self, state=None, root=None):
        if state is not None:
            self.root = MCTSNode(state, None)
        elif root is not None:
            self.root = root
        else:
            raise RuntimeError

    def iterate(self):
        node = self.select()
        if not node.state.game_over():
            node = node.expand()
        result = self.simulate(node)

        while node is not None:
            node.update(result)
            node = node.parent

    def select(self):
        node = self.root
        while node.has_children:
            node = max(node.children, key=MCTSNode.uct)
        return node

    def simulate(self, node):
        winner = node.state.get_result()
        if winner is not None:
            return winner
        state = node.state
        state = state.turn_with_move(random.choice(state.moves()))
        result = state.get_result()
        while result is None:
            state = state.turn_with_move(random.choice(state.moves()))
            result = state.get_result()
        return result

    def get_best_child(self):
        return max(self.root.children, key=MCTSNode.win_prob)

    def get_action(self):
        action = self.get_best_child().action
        #print('Get_action', action, self.root.state.board, [(n.action, n.num_simulations, n.uct(), n.win_prob()) for n in self.root.children])
        return action

    def count_nodes(self):
        return self.root.count_children()

class MCTSNode:
    def __init__(self, state, action, parent=None):
        self.state = state
        self.action = action
        self.children = None
        self.parent = parent
        self.num_simulations = 0
        self.num_wins = 0.0

    def __str__(self):
        return f'{self.state.moves_taken} {self.action}: {self.num_wins} / {self.num_simulations}'

    def __repr__(self):
        return f'MCTSNode({self.state}, {self.action}, parent={self.parent}, num_simulations={self.num_simulations}, num_wins={self.num_wins})'

    @property
    def has_children(self):
        return self.children is not None

    def count_children(self):
        if self.children is None:
            return 1
        return 1 + sum(child.count_children() for child in self.children)

    def expand(self):
        self.children = []
        for move in self.state.moves():
            node = MCTSNode(self.state.turn_with_move(move), move, parent=self)
            self.children.append(node)
        return random.choice(self.children)

    def update(self, result):
        assert self.num_wins <= self.num_simulations
        self.num_simulations += 1
        if result == DRAW:
            self.num_wins += 0.5
        elif result == (self.state.active_player_idx + 1) % 2:
            self.num_wins += 1.0
        else:
            self.num_wins += 0.0

    def win_prob(self):
        if self.num_simulations == 0:
            return 0.5
        return self.num_wins / self.num_simulations

    def uct(self):
        return self.win_prob() + math.sqrt(2 * math.log(self.parent.num_simulations + 1) / (self.num_simulations + 1))

class MCTSPlayer(Player):
    def __init__(self, name):
        self.name = f'{name}'
        self.tree = None

    def get_action(self, game):
        #print(f'Get action for game state {game.board} for player {self.name}')
        if self.tree is None:
            self.tree = MCTSTree(state=game.state)
        else:
            moves_seen = len(self.tree.root.state.move_history)
            moves_to_apply = game.state.move_history[moves_seen:]
            #print(f'Old root move_history ({self.name}):', self.tree.root.state.move_history)
            #print('New game state move_history', game.state.move_history)
            new_root = self.tree.root
            for move in moves_to_apply:
                new_root = next(node for node in new_root.children if node.action == move)
            new_root.parent = None
            self.tree = MCTSTree(root=new_root)
        for i in range(1000):
            self.tree.iterate()
        action = self.tree.get_action()
        return action

def main():
    player1 = MCTSPlayer('Player 1')
    player2 = MCTSPlayer('Player 2')
    game = Game([player1, player2])
    winner = game.turn(do_print=False)
    while winner is None:
        winner = game.turn(do_print=False)
    if winner == 2:
        print('Draw')
    else:
        print(f'{game.players[winner].name} wins!')
    return winner

if __name__ == '__main__':
    #cProfile.run('main()')
    counter = Counter()
    for i in range(30):
        counter[main()] += 1
    print(counter)

mtg.py

import itertools
import random
import time

compose = lambda f: lambda g: lambda *args, **kwds: f(g(*args, **kwds))

builtin_print = print
def print(*args, **kwds):
    pass
    
class PseudoColour:
    pass

class Colour:
    def __init__(self, name, symbol):
        self.name = name
        self.symbol = symbol

    def __repr__(self):
        return f'Colour({self.name!r}, {self.symbol!r})'
        
GENERIC = PseudoColour()
X_MANA = PseudoColour()

WHITE = Colour("White", "W")
BLUE = Colour("Blue", "U")
BLACK = Colour("Black", "B")
RED = Colour("Red", "R")
GREEN = Colour("Green", "G")

class Supertype:
    def __init__(self, name):
        self.name = name

BASIC = Supertype("Basic")
LEGENDARY = Supertype("Legendary")

class Type:
    def __init__(self, name):
        self.name = name

CREATURE = Type("Creature")
INSTANT = Type("Instant")
LAND = Type("Land")
SORCERY = Type("Sorcery")

class Subtype:
    def __init__(self, name):
        self.name = name

PLAINS = Subtype("Plains")
ISLAND = Subtype("Island")
SWAMP = Subtype("Swamp")
MOUNTAIN = Subtype("Mountain")
FOREST = Subtype("Forest")

HOUND = Subtype("Hound")
GOBLIN = Subtype("Goblin")
HUMAN = Subtype("Human")
SOLDIER = Subtype("Soldier")
WARRIOR = Subtype("Warrior")

class Keyword:
    def __init__(self, name):
        self.name = name

FLYING = Keyword('Flying')
FIRST_STRIKE = Keyword('First strike')
DOUBLE_STRIKE = Keyword('Double strike')

def BasicLand(name, subtype):
    return Card(name, types=[LAND], supertypes=[BASIC], subtypes=[subtype])

def Creature(name, mana_cost_string, subtypes, power, toughness):
    mana_cost = parse_mana_cost(mana_cost_string)
    return Card(name, types=[CREATURE], supertypes=[], subtypes=subtypes, mana_cost=mana_cost, power=power, toughness=toughness)

def LegendaryCreature(name, mana_cost_string, subtypes, power, toughness):
    mana_cost = parse_mana_cost(mana_cost_string)
    return Card(name, types=[CREATURE], supertypes=[LEGENDARY], subtypes=subtypes, mana_cost=mana_cost, power=power, toughness=toughness)

class Card:
    def __init__(self, name, *,
                 types,
                 supertypes,
                 subtypes,
                 power=None, toughness=None,
                 mana_cost=None,
                 abilities=None,
                 keywords=None,
                 allowed_many=False
            ):
        self.name = name
        self.types = types
        self.supertypes = supertypes
        self.subtypes = subtypes
        self.power = power
        self.toughness = toughness
        self.mana_cost = mana_cost
        self.additional_abilities = abilities if abilities is not None else []
        self.keywords = keywords if keywords is not None else []
        self.allowed_many = allowed_many

    def __repr__(self):
        return self.name

    @property
    def abilities(self):
        inherent_abilities = []
        if self.is_type(PLAINS):
            inherent_abilities.append(BasicLandManaAbility(WHITE))
        if self.is_type(ISLAND):
            inherent_abilities.append(BasicLandManaAbility(BLUE))
        if self.is_type(SWAMP):
            inherent_abilities.append(BasicLandManaAbility(BLACK))
        if self.is_type(MOUNTAIN):
            inherent_abilities.append(BasicLandManaAbility(RED))
        if self.is_type(FOREST):
            inherent_abilities.append(BasicLandManaAbility(GREEN))
        return inherent_abilities + self.additional_abilities

    def is_type(self, *types):
        for type in types:
            if type not in self.types:
                if type not in self.supertypes:
                    if type not in self.subtypes:
                        return False
        return True

    def has_keyword(self, keyword):
        return keyword in self.keywords

    @property
    def converted_mana_cost(self):
        if self.mana_cost is None:
            return 0
        return self.mana_cost.convert()

def parse_mana_cost(string):
    comps = {}
    for c in string:
        if c in "123456789":
            comps[GENERIC] = comps.get(GENERIC, 0) + int(c)
        elif c == "X":
            comps[X_MANA] = 0
        elif c == "W":
            comps[WHITE] = comps.get(WHITE, 0) + 1
        elif c == "U":
            comps[BLUE] = comps.get(BLUE, 0) + 1
        elif c == "B":
            comps[BLACK] = comps.get(BLACK, 0) + 1
        elif c == "R":
            comps[RED] = comps.get(RED, 0) + 1
        elif c == "G":
            comps[GREEN] = comps.get(GREEN, 0) + 1
        else:
            raise NotImplementedError(f"Haven't yet implemented symbol '{c}' in mana costs.")
    return ManaCost(comps.items())


class DeckBuilder:
    def __init__(self):
        self.cards = {}
        self.sideboard_cards = {}

    def add_card(self, name):
        quantity, card = self.parse_card_name(name)
        self.cards[card] = self.cards.get(card.name, 0) + quantity

    def add_sideboard_card(self, name):
        quantity, card = self.parse_card_name(name)
        self.sideboard_cards[card] = self.sideboard_cards.get(card.name, 0) + quantity

    def parse_card_name(self, name):
        quantity, *name_parts = name.split(' ')
        return int(quantity), CARDS[' '.join(name_parts)]

    def build(self):
        is_legal, reason = self.check_legality()
        if is_legal:
            return Deck(self.cards)
        raise RuntimeError(reason)

    def num_cards(self):
        return sum(self.cards.values())

    def num_sideboard_cards(self):
        return sum(self.sideboard_cards.values())

    def all_cards(self):
        for card, quantity in self.cards.items():
            if card in self.sideboard_cards:
                yield card, quantity + self.sideboard_cards[card]
            yield card, quantity
        for card, quantity in self.sideboard_cards.items():
            if card not in self.cards:
                yield card, quantity
                
    def check_legality(self):
        nc = self.num_cards()
        if nc < 60:
            return False, f"A Constructed deck must have at least 60 cards, but this deck has only {nc} cards."
        
        ns = self.num_sideboard_cards()
        if ns > 15:
            return False, f"A Constructed deck's sideboard may contain no more than fifteen cards, but this deck's sideboard contains {ns} cards."

        # The no-more-of-four rule is disabled.
        #for card, quantity in self.all_cards():
        #    if quantity > 4 and not card.is_type(BASIC, LAND) and not card.allowed_many:
        #        return False, f"A Constructed deck may no more than four of any card other than basic land cards, but this deck contains {quantity} copies of {card.name}."
            
        return True, ""

class Deck:
    def __init__(self, cards):
        self.cards = cards

class Agent:
    pass

class MCTSAgent(Agent):
    pass

class Actor:
    pass

class MCTSActor(Actor):
    """An actor that uses an MCTSAgent to make decisions."""
    def __init__(self, name):
        self.name = f'{name} (MCTS)'
        self.agent = MCTSAgent()

    def declare_attackers(self, game):
        raise NotImplementedError

    def assign_damage(self, game, attacker):
        raise NotImplementedError

    def declare_blockers(self, game):
        raise NotImplementedError

    def assign_blocking_damage(self, game, blocker):
        raise NotImplementedError

    def get_action(self, game):
        raise NotImplementedError

    def choose_modes(self, game, spell):
        raise NotImplementedError

    def choose_targets(self, game, spell):
        raise NotImplementedError

    def get_payment_action(self, game, costs):
        raise NotImplementedError

    def pay_mana_cost(self, cost):
        raise NotImplementedError

class CustomActor(Actor):
    """An actor that makes decisions based on the author's idea of what move is best."""
    def __init__(self, name):
        self.name = name

    def declare_attackers(self, game):
        possible_attackers = [p for p in self.player.battlefield
                              if p.is_type(CREATURE) and not p.is_summoning_sick and not p.tapped]
        return possible_attackers

    def assign_damage(self, game, attacker):
        return [attacker.power]
    
    def assign_blocking_damage(self, game, blocker):
        return [blocker.power]
    
    def declare_blockers(self, game):
        dont_block = False
        if self.name == 'Goblins':
            dont_block = sum(c.power for c in game.attacking_creatures) < self.player.life
            print(f'{sum(c.power for c in game.attacking_creatures)} is a non-lethal attack at {self.player.life} life, so don\'t bother blocking.')
        elif self.name == 'Humans':
            dont_block = (sum(c.power for c in game.attacking_creatures) < self.player.life and
                          sum(c.power for c in self.player.battlefield if c.is_type(CREATURE)) >= game.active_player.life)
            print(f'{sum(c.power for c in game.attacking_creatures)} is a non-lethal attack at {self.player.life} life and our next attack ({sum(c.power for c in self.player.battlefield if c.is_type(CREATURE))}) is lethal, so don\'t bother blocking')
        else:
            dont_block = False
            

        possible_blockers = [p for p in self.player.battlefield if p.is_type(CREATURE) and not p.tapped]
        blocks = {}
        for attacker, blocker in itertools.zip_longest(game.attacking_creatures, possible_blockers, fillvalue=None):
            if attacker is None:
                break
            if blocker is None or dont_block:
                blocks[attacker] = []
            else:
                blocks[attacker] = [blocker]
        return blocks

    def can_cast(self, card):
        return len([p for p in self.player.battlefield if p.is_type(LAND) and not p.tapped]) >= card.converted_mana_cost

    def get_action(self, game):
        if game.phase == PRECOMBAT_MAIN or game.phase == POSTCOMBAT_MAIN:
            return self.get_main_phase_action(game)
        return self.get_instant_action(game)

    def get_main_phase_action(self, game):
        if self.player.land_plays > 0:
            for card in self.player.hand:
                if card.is_type(LAND):
                    return PlayLandAction(card)
        for card in sorted(self.player.hand, key=Card.converted_mana_cost.fget, reverse=True):
            if card.is_type(CREATURE) or card.is_type(SORCERY):
                if self.can_cast(card):
                    return CastSpellAction(CardSpell(card))
        return self.get_instant_action(game)
                
    def get_instant_action(self, game):
        for card in sorted(self.player.hand, key=Card.converted_mana_cost.fget, reverse=True):
            if card.is_type(INSTANT):
                if self.can_cast(card):
                    return CastSpellAction(CardSpell(card))

    def choose_modes(self, game, spell):
        raise NotImplementedError

    def get_payment_action(self, game, costs):
        """Choose an action to perform when asked to pay the given costs"""
        actions = []

        # currently only support a single mana cost (otherwise we'd activate lands multiple times or something like that)
        assert len([cost for cost in costs if isinstance(cost, ManaCost)]) <= 1
        
        for cost in costs:
            if isinstance(cost, ManaCost):
                untapped_lands = [p for p in self.player.battlefield if p.is_type(LAND) and not p.tapped]
                actions.extend([ActivateAbilityAction(l.abilities[0], l) for l in untapped_lands[:cost.convert()]])
            elif isinstance(cost, TapCost):
                pass
            else:
                raise NotImplementedError

        return actions

    def pay_mana_cost(self, cost):
        # our mana pool only has one colour of mana in it at the moment
        return self.player.mana_pool[:cost.convert()]
        

class Phase:
    pass

BEGINNING = Phase()
PRECOMBAT_MAIN = Phase()
COMBAT = Phase()
POSTCOMBAT_MAIN = Phase()
ENDING = Phase()

class Step:
    pass

UNTAP = Step()
UPKEEP = Step()
DRAW = Step()

BEGINNING_OF_COMBAT = Step()
DECLARE_ATTACKERS = Step()
DECLARE_BLOCKERS = Step()
COMBAT_DAMAGE = Step()
END_OF_COMBAT = Step()

END = Step()
CLEANUP = Step()

class Action:
    pass

class PlayLandAction(Action):
    def __init__(self, card):
        self.card = card

class CastSpellAction(Action):
    def __init__(self, spell):
        self.spell = spell

class ActivateAbilityAction(Action):
    def __init__(self, ability, permanent):
        self.ability = ability
        self.permanent = permanent

class TapPermanentAction(Action):
    def __init__(self, permanent):
        self.permanent = permanent

class Permanent:
    def __init__(self):
        self.tapped = False

    def untap(self):
        self.tapped = False

    def tap(self):
        self.tapped = True

class CardPermanent(Permanent):
    "A permanent that is a card."
    def __init__(self, card):
        super().__init__()
        self.card = card
        self.name = card.name
        self.damage = 0

    def __getattr__(self, name):
        return getattr(self.card, name)
    
    @property
    def abilities(self):
        return self.card.abilities

    def __repr__(self):
        return f'{self.card}'

class Spell:
    pass

class CardSpell(Spell):
    "A spell that is a card."
    def __init__(self, card):
        self.card = card

    def is_type(self, *types):
        return self.card.is_type(*types)

    @property
    def mana_cost(self):
        return self.card.mana_cost

    @property
    def converted_mana_cost(self):
        return self.card.converted_mana_cost

    def __repr__(self):
        return f'Spell({self.card})'

class Effect:
    pass

def comma_and_join(strings):
    assert len(strings) != 0
    if len(strings) == 1:
        return strings[0]
    return ', '.join(strings[:-1]) + ' and ' + strings[-1]

class AddManaEffect(Effect):
    def __init__(self, *mana):
        self.mana = mana

    def __str__(self):
        mana_str = comma_and_join(['{%s}' % m.symbol for m in self.mana])
        return f'Add {mana_str}'

class Cost:
    pass

class TapCost(Cost):
    def __init__(self, permanent):
        self.permanent = permanent

class TapIconCost(Cost):
    def __str__(self):
        return '{T}'

class ManaCost(Cost):
    def __init__(self, comps):
        self.comps = comps

    def convert(self):
        return sum(quantity for colour, quantity in self.comps)

class Ability:
    def is_mana_ability(self):
        return self.targets == 0 and any(isinstance(e, AddManaEffect) for e in self.effects)

    def __str__(self):
        cost_str = ', '.join(str(cost) for cost in self.costs)
        assert len(self.effects) == 1
        return f'"{cost_str}: {self.effects[0]}."'

class BasicLandManaAbility(Ability):
    def __init__(self, colour):
        self.targets = 0
        self.costs = [TapIconCost()]
        self.effects = [AddManaEffect(colour)]

class Player:
    def __init__(self, deck, actor):
        self.life = 20
        self.land_plays = 0

        self.mana_pool = []
        self.library = Library(deck)
        self.battlefield = []
        self.graveyard = []
        self.exile = []
        self.hand = []
        
        self.actor = actor
        self.actor.player = self

    def draw_card(self):
        if len(self.library.contents) == 0:
            print(self.actor.name, 'loses the game (drawing from an empty library)')
            exit()
        self.hand.append(self.library.pop())
        print(self.hand[-1].name, end=', ')

    def draw(self, n):
        if n == 1:
            print(f'{self.actor.name} draws a card:', end=' ')
        else:
            print(f'{self.actor.name} draws {n} cards:', end=' ')
        for _ in range(n):
            self.draw_card()
        print()

class Library:
    def __init__(self, deck):
        self.deck = deck

        contents = []
        for card, quantity in self.deck.cards.items():
            for _ in range(quantity):
                contents.append(card)

        self.contents = contents
        random.shuffle(contents)

    def pop(self):
        return self.contents.pop()

class GameLoss(BaseException):
    pass

class Game:
    def __init__(self, *players):
        self.players = list(players)
        self.delayed_triggers = []
        self.stack = []

    def start(self):
        for pl in self.players:
            pl.draw(7)

    @property
    def active_player(self):
        return self.players[0]

    @property
    def current_step(self):
        if self.phase is BEGINNING:
            if self.step is UNTAP:
                return 'Untap'
            elif self.step is UPKEEP:
                return 'Upkeep'
            elif self.step is DRAW:
                return 'Draw'
            else:
                return 'Beginning Phase'
        elif self.phase is PRECOMBAT_MAIN:
            return 'Precombat Main Phase'
        elif self.phase is COMBAT:
            if self.step is BEGINNING_OF_COMBAT:
                return 'Beginning of Combat Step'
            elif self.step is DECLARE_ATTACKERS:
                return 'Declare Attackers Step'
            elif self.step is DECLARE_BLOCKERS:
                return 'Declare Blockers Step'
            elif self.step is COMBAT_DAMAGE:
                return 'Combat Damage Step'
            elif self.step is END_OF_COMBAT:
                return 'End of Combat Step'
            else:
                return 'Combat Phase'
        elif self.phase is POSTCOMBAT_MAIN:
            return 'Postcombat Main Phase'
        elif self.phase is ENDING:
            if self.step is END:
                return 'End Step'
            elif self.step is CLEANUP:
                return 'Cleanup Step'
            else:
                return 'Ending Phase'

    def next_active_player(self):
        ap = self.players.pop(0)
        self.players.append(ap)

    def handle_triggers(self):
        return False

    def handle_state_based_actions(self):
        for player in self.players:
            if player.life <= 0:
                print(f'{player.actor.name} loses the game.')
                self.players.remove(player)
                raise GameLoss(f'{player.actor.name} loses the game.')
            for permanent in player.battlefield:
                if permanent.is_type(CREATURE):
                    if permanent.damage >= permanent.toughness:
                        player.battlefield.remove(permanent)
                        player.graveyard.append(permanent.card)
                        return True
        return False

    def get_action(self, player):
        #print(f'{player.actor.name} gets priority in {self.current_step} of {self.active_player.actor.name}\'s turn')
        self.prepriority()
        return player.actor.get_action(self)
    
    def handle_priority(self):
        any_took_action = True
        while any_took_action:
            any_took_action = False
            for pl in self.players:
                action = self.get_action(pl)
                while action is not None:
                    any_took_action = True
                    self.perform_action(pl, action)
                    action = self.get_action(pl)
        # Everyone has passed. Resolve the top thing on the stack.
        while self.stack:
            self.resolve(self.stack[-1])
            self.stack.pop()
            self.handle_priority()

    def prepriority(self):
        """Performs state-based actions and puts triggers onto the stack

        Repeated until no more state-based actions can be performed and no more triggers can be put on the stack.
        Returns whether any state-based actions were performed or any triggers were put onto the stack.
        """
        ever_any = False
        sb_result = self.handle_state_based_actions()
        tr_result = self.handle_triggers()
        while sb_result or tr_result:
            ever_any = True
            sb_result = self.handle_state_based_actions()
            tr_result = self.handle_triggers()
        return ever_any

    def resolve_creature_spell(self, spell):
        spell.controller.battlefield.append(CardPermanent(spell.card))
        spell.controller.battlefield[-1].is_summoning_sick = True

    def resolve_ability_effects(self, ability):
        for effect in ability.effects:
            if isinstance(effect, AddManaEffect):
                ability.controller.mana_pool.extend(effect.mana)
            else:
                raise NotImplementedError

    def pay_costs(self, player, costs):
        for cost in costs:
            if isinstance(cost, ManaCost):
                colours = player.actor.pay_mana_cost(cost)
                for colour in colours:
                    player.mana_pool.remove(colour)
            elif isinstance(cost, TapCost):
                cost.permanent.tap()
            else:
                print(cost)
                raise NotImplementedError                

    @compose(list)
    def determine_ability_costs(self, ability, permanent):
        for cost in ability.costs:
            if isinstance(cost, TapIconCost):
                yield TapCost(permanent)
            elif isinstance(cost, ManaCost):
                yield cost
            else:
                raise NotImplementedError

    def determine_spell_costs(self, spell):
        return [spell.mana_cost]

    def perform_land_play(self, player, action):
        print(f"{player.actor.name} plays {action.card.name}")
        assert player.land_plays > 0
        assert action.card in player.hand
        player.hand.remove(action.card)
        player.battlefield.append(CardPermanent(action.card))
        player.land_plays -= 1

    def perform_spell_cast(self, player, action):
        print(f"{player.actor.name} casts {action.spell.card.name}")
        
        assert action.spell.card in player.hand
        player.hand.remove(action.spell.card)
        
        action.spell.controller = player
        
        self.stack.append(action.spell)
        
        costs = self.determine_spell_costs(action.spell)
        costs_actions = action.spell.controller.actor.get_payment_action(self, costs)
        for cost_action in costs_actions:
            self.perform_action(player, cost_action)
            
        self.pay_costs(player, costs)

    def perform_ability_activation(self, player, action):
        if action.ability.is_mana_ability:
            pass#print(f"{player.actor.name} activates the {action.ability} mana ability of {action.permanent.name}")
        else:
            print(f"{player.actor.name} activates the {action.ability} ability of {action.permanent.name}")
            
        action.ability.controller = player

        if not action.ability.is_mana_ability:
            self.stack.append(action.ability)

        costs = self.determine_ability_costs(action.ability, action.permanent)
        costs_actions = action.ability.controller.actor.get_payment_action(self, costs)
        for cost_action in costs_actions:
            self.perform_action(player, cost_action)

        self.pay_costs(player, costs)

        if action.ability.is_mana_ability:
            self.resolve(action.ability)

    def resolve(self, spell_or_ability):
        #print(f"Resolving {spell_or_ability}")
        if isinstance(spell_or_ability, Spell):
            if spell_or_ability.is_type(INSTANT) or spell_or_ability.is_type(SORCERY):
                self.resolve_spell_effects(spell_or_ability)
            elif spell_or_ability.is_type(CREATURE):
                self.resolve_creature_spell(spell_or_ability)
        elif isinstance(spell_or_ability, Ability):
            self.resolve_ability_effects(spell_or_ability)
        else:
            raise NotImplementedError
        
    def perform_action(self, player, action):
        #print(f"{player.actor.name} performs {action}")
        if isinstance(action, PlayLandAction):
            return self.perform_land_play(player, action)
        if isinstance(action, CastSpellAction):
            return self.perform_spell_cast(player, action)
        if isinstance(action, ActivateAbilityAction):
            return self.perform_ability_activation(player, action)
        raise NotImplementedError()

    def beginning_phase(self):
        self.step = UNTAP
        self.untap_step()
        
        self.step = UPKEEP
        self.upkeep_step()
        
        self.step = DRAW
        self.draw_step()
        
    def untap_step(self):
        self.active_player.land_plays = 1
        for permanent in self.active_player.battlefield:
            permanent.untap()
            permanent.is_summoning_sick = False

    def upkeep_step(self):
        self.handle_priority()

    def draw_step(self):
        self.active_player.draw(1)
        self.handle_priority()

    def main_phase(self):
        self.handle_priority()

    def combat_phase(self):
        self.step = BEGINNING_OF_COMBAT
        self.beginning_of_combat_step()

        self.step = DECLARE_ATTACKERS
        self.declare_attackers_step()

        # 508.8. If no creatures are declared as attackers or put onto the battlefield attacking,
        #        skip the declare blockers and combat damage steps.
        if len(self.attacking_creatures) > 0:
            self.step = DECLARE_BLOCKERS
            self.declare_blockers_step()

            self.step = COMBAT_DAMAGE
            self.combat_damage_step()

        self.step = END_OF_COMBAT
        self.end_of_combat_step()

    def beginning_of_combat_step(self):
        # Multiplayer lets you choose who you attack
        assert len(self.players) == 2

        self.defending_player = self.players[1]

        self.handle_priority()

    def declare_attackers_step(self):
        creatures = self.active_player.actor.declare_attackers(self)
        print('attackers:', creatures)
        for creature in creatures:
            creature.tap()
        self.attacking_creatures = creatures

        if len(creatures) > 0:
            attackers_str = comma_and_join([attacker.card.name for attacker in creatures])
            print(f'{self.active_player.actor.name} attacks with {attackers_str}.')

        self.handle_priority()

    def declare_blockers_step(self):
        declared_blocks = self.defending_player.actor.declare_blockers(self)
        print('blocks:', declared_blocks)
        
        self.attacking_damage_order = {}
        self.blocking_damage_order = {}
        
        for attacker in self.attacking_creatures:
            if len(declared_blocks[attacker]) == 0:
                self.attacking_damage_order[attacker] = []
                self.unblocked_creatures.append(attacker)
            elif len(declared_blocks[attacker]) == 1:
                self.attacking_damage_order[attacker] = declared_blocks[attacker]
                self.blocked_creatures.append(attacker)
            else:
                self.attacking_damage_order[attacker] = self.active_player.actor.choose_damage_order(declared_blocks, attacker)
                self.blocked_creatures.append(attacker)
            for blocker in declared_blocks[attacker]:
                self.blocking_damage_order[blocker] = self.blocking_damage_order.get(blocker, [])
                self.blocking_damage_order[blocker].append(attacker)

        for blocker in self.blocking_damage_order:
            attackers = self.blocking_damage_order[blocker]
            if len(attackers) > 1:
                self.blocking_damage_order[blocker] = self.defending_player.actor.choose_blocking_damage_order(declared_blocks, blocker, attackers)
            self.blocking_creatures.append(blocker)

        if len(self.blocking_creatures) > 0:
            blockers_str = comma_and_join([blocker.card.name for blocker in self.blocking_creatures])
            print(f'{self.defending_player.actor.name} blocks with {blockers_str}.')

        self.handle_priority()

    @property
    def creatures_in_combat(self):
        return self.attacking_creatures + self.blocking_creatures

    def combat_damage_step(self):
        if any(cr.has_keyword(FIRST_STRIKE) or cr.has_keyword(DOUBLE_STRIKE) for cr in self.creatures_in_combat):
            raise NotImplementedError('First strike damage phase not yet implemented. Whoops!')

        self.combat_damage_to_player = 0

        for attacking_creature in self.unblocked_creatures:
            self.combat_damage_to_player += attacking_creature.power

        for attacking_creature in self.blocked_creatures:
            damage_assignment = self.active_player.actor.assign_damage(self, attacking_creature)
            assert sum(damage_assignment) == attacking_creature.power
            assert len(damage_assignment) == len(self.attacking_damage_order[attacking_creature])
            for blocker, damage in zip(self.attacking_damage_order[attacking_creature], damage_assignment):
                blocker.damage += damage

        for blocking_creature, attackers in self.blocking_damage_order.items():
            damage_assignment = self.defending_player.actor.assign_blocking_damage(self, blocking_creature)

        self.defending_player.life -= self.combat_damage_to_player
            
    
    def end_of_combat_step(self):
        self.attacking_creatures = []
        self.blocking_creatures = []
        self.unblocked_creatures = []
        self.blocked_creatures = []

    def ending_phase(self):
        self.step = END
        self.end_step()

        self.step = CLEANUP
        self.cleanup_step()

    def end_step(self):
        self.handle_priority()

    def cleanup_step(self):
        if len(self.active_player.hand) > 7:
            print(f'{self.active_player.actor.name} discards to hand size')
            new_hand = self.active_player.hand[:7]
            extra_cards = self.active_player.hand[7:]
            self.active_player.hand = new_hand
            self.active_player.graveyard.extend(extra_cards)
        
        result = self.prepriority()
        if result:
            self.handle_priority()
            
        for player in self.players:
            for permanent in player.battlefield:
                permanent.damage = 0

    def turn(self):
        self.phase = BEGINNING
        self.beginning_phase()

        self.phase = PRECOMBAT_MAIN
        self.main_phase()

        self.phase = COMBAT
        self.combat_phase()
        
        self.phase = POSTCOMBAT_MAIN
        self.main_phase()

        self.phase = ENDING
        self.ending_phase()
        
        self.next_active_player()


if __name__ == '__main__':
    CARDS = {
        "Plains": BasicLand("Plains", PLAINS),
        "Mountain": BasicLand("Mountain", MOUNTAIN),
        "Eager Cadet": Creature("Eager Cadet", "W", [HUMAN, SOLDIER], 1, 1),
        "Isamaru, Hound of Konda": LegendaryCreature("Isamaru, Hound of Konda", "W", [HOUND], 2, 2),
        "Goblin Piker": Creature("Goblin Piker", "1R", [GOBLIN, WARRIOR], 2, 1),
        "Goblin Assailant": Creature("Goblin Assailant", "1R", [GOBLIN, WARRIOR], 2, 2),
    }

    db1 = DeckBuilder()
    db1.add_card("20 Mountain")
    db1.add_card("40 Goblin Piker")
    deck1 = db1.build()

    db2 = DeckBuilder()
    db2.add_card("20 Plains")
    db2.add_card("40 Eager Cadet")
    deck2 = db2.build()

    game_count = 2
    assert (game_count % 2) == 0
    
    count = {'Goblins': 0, 'Humans': 0}
    
    for i in range(game_count // 2):
        game = Game(Player(deck2, actor=MCTSActor('Humans')), Player(deck1, actor=MCTSActor('Goblins')))
        game.start()
        try:
            while True:
                #time.sleep(5)
                game.turn()
        except GameLoss:
            count[game.players[0].actor.name] += 1
            
    for i in range(game_count // 2):
        game = Game(Player(deck1, actor=MCTSActor('Goblins')), Player(deck2, actor=MCTSActor('Humans')))
        game.start()
        try:
            while True:
                #time.sleep(5)
                game.turn()
        except GameLoss:
            count[game.players[0].actor.name] += 1

    player1, player2 = list(count.keys())
    win_percent = int(100 * count[player1] / game_count)
    builtin_print(player1, f"wins {win_percent}% of {game_count} games against", player2)

#Player 2 blocks with Goblin Piker.
#Player 2 loses the game.
#{'Player 1': 81, 'Player 2': 19}