hlynurd / open-mtg

A python implementation of Magic: The Gathering with an AI that plays it using Monte Carlo move evaluation.

OpenMTG

An experimental framework for writing, testing and evaluating agents for the card game Magic: The Gathering.

Dependencies

• Jupyter notebook
• itertools
• NumPy
• math
• random
• copy

Authors

• Hlynur Davíð Hlynsson - hlynurd

License

This project is licensed under the MIT License - see the LICENSE.md file for details

Contributing

Please see the Issues tab.

Usage

A game is initialized with two players, which are initialized with a python decklist of cards:

from decklists import *
from game import *
game = Game(Player(get_8ed_core_gold_deck()), Player(get_8ed_core_silver_deck()))
game.start_game()

The state of the game determines which player is allowed to act. The game logic always assumes that the player with priority is the currently acting player. This holds even if the acting player does not have priority a strict sense, for example where blockers are declared.

A simple game loop where two players perform random actions against each other:

while not game.is_over():
    legal_moves = game.get_moves()
    move = random.choice(legal_moves)
    game.make_move(move)

The list of legal moves returned by game depend on the state of the game. Currently this project supports lands and sorcery speed actions. An action to pass priority is returned as the string "Pass" or an empty list. The most important one is which phase or step it is, accessed by:

game.phases[game.current_phase_index]

Below, when we reference "player" it is always the acting player, kept in:

game.player_with_priority

Main phase

Game returns a list of performable actions by the player. This is a list of indexes of cards in hand that can be played: Lands if the player has not played a land yet, or spells if the player has mana in their mana pool to pay for it. The list also contains indexes of activatable abilities by permanents they control.

Declare Attackers Step

All combinations of eligible attackers are computed and indexed. Game returns a list of indices, and the combination that corresponds to this index is declared as attackers when the index is passed to make_move.

Declare Blockers Step

This step is handled with the player taking decisions over several moves: Until each eligible blocker has been considered, the legal moves are the indices of the attackers or an additional index, corresponding to a "no block" choice.

509.2 "Damage Assignment Ordering"

This step is also handled in several moves: For each attacker, the player choose an index corresponding to an indexed list of permutations of blockers.

510.1c "Damage Assignment

Double loop of moves, until no more choices are necessary: For each creature, and for each blocker assigned to that creature (in the damage assignment order), the legal moves is the legal amount of damage to be assigned to that blocker by that creature.

Corollary choices

For spells or abilities that require a target, the player must get an additional list of legal moves from the game to finish resolving that spell or ability. Paying for generic mana cost is also delayed, so the player must get a list of legal combinations to pay for generic mana and pay for it before passing priority.

open-mtg's Issues

Define cards in JSON

Overloading MCTS nodes with garbage data

open-mtg/mcts.py

Line 87 in 8ad261f

while node.untried_moves == [] and node.child_nodes != []: # node is fully expanded and non-terminal

        # Select
        while node.untried_moves == [] and node.child_nodes != []:  # node is fully expanded and non-terminal
            node = node.uct_select_child()
state.make_move(node.move)

This MCTS is broken. Please try to understand, I will explain a scenario:

Node is a node in the tree which points to states. The states are only copied the first time they are visited.

open-mtg/mcts.py

Line 34 in 8ad261f

self.child_nodes.append(n)

So let's say your tree tells you to:
0) Do some things and end your turn, no randomness involved. But your opponent's deck is shuffled.

1. Opponent Draws a card (it turns out it's lava axe)
2. Opponent Plays Mountain
3. Opponent Plays Lava Axe.
4. Opponent goes to combat phase.

Great, no problems yet. But the second (or more) time through:

0. Do some things and end your turn, no randomness involved.
1. Opponent Draws a card (it turns out it's a Mountain instead!)
2. Opponent Plays Mountain
3. Opponent does (?undefined behavior?)
4. Opponent's tries to do the first part of combat, but is it even legal any more? The AI is desynchronized.

The second mountain is not playable. Thus the size of the playable_indicies is smaller. Now in step (3) opponent plays an ability instead, it looks like, assuming it has an ability to play.
https://github.com/hlynurd/open-mtg/blob/master/game.py#L106

Basically, you can't overlap MCTS nodes the way you are doing. The move needs to uniquely define the transition to the next state, if it is overloaded, the results will be nonsense.

Stock MCTS with UCT leaks hidden information (aka cheats)

Hi, it looks like this algorithm performs a MCTS rollout on a game with hidden information. This leaks information back up the tree about the hidden state of the decks and hands. Thus the AI is actually able to play as if there was no hidden information in the game, which is probably not what you intended.

Abstract spell effects

Currently, the few implemented spells are enumerated in "make_move" and "get_legal_moves". Returning legal moves associated with the spell and handling the spell effect should be handled by the card objects rather than long rows of 'player.casting_spell == "Vengeance": [...]'. Consider passing lambda functions as card creation parameters, cf. [lambda self: self.owner.add_mana({"Green": 1})] in current Land card instantiation.

Documentation

The code is hardly documented, decide upon and implement documentation for the functions and classes:

https://www.python.org/dev/peps/pep-0257/
http://sphinxcontrib-napoleon.readthedocs.io/en/latest/example_google.html
https://stackoverflow.com/questions/24555327/how-can-i-produce-a-numpy-like-documentation

[Feature Request] Xmage support

Outside the project scope, but would probably save a lot of time and effort. connect to xmage api's (http://xmage.de/) then do computation off the interface.

Ties do not seem to be accounted for

Ties are something worth looking at in some cases and do not seem to be accounted for.

Implement and benchmark more search algorithms

There's currently only a naive Monte-Carlo Search implemented and benchmarked. A whole zoo of search methods are still to be explored, for example:
http://static.ijcai.org/proceedings-2017/0772.pdf
https://ieeexplore.ieee.org/abstract/document/6218176/
We would benefit from more implementations and evaluations of performance.

Reignite passion?

Hey

I found this project today after watching https://www.youtube.com/watch?v=Xq4T44EvPvo

Hope you reignite the passion for it, would be very cool to have an open source simulator!

MCTS shuffle is wrong

open-mtg/mcts.py

Line 74 in 8ad261f

state.players[k].shuffle_deck()

# the mcts rollouts don't randomize cards that have been seen with Index
        indexed_cards_in_deck = []
        # print("mcts print: %s" % (state.players))

        if len(state.players[k].deck) > 0:
            while len(state.players[k].deck) > 0 and state.players[k].deck[-1].deck_location_known:
                indexed_cards_in_deck.append(state.players[k].deck.pop())
        for indexed_card in indexed_cards_in_deck:
            state.players[k].deck.append(indexed_card)
# and "imagine" a scenario for the opponent - this assumes knowledge of opponent decklist!

state.players[k].shuffle_deck()

This currently looks at my deck, finds the cards that are indexed, puts them in "indexed_cards_in_deck". Then it takes "indexed_cards_in_deck" and puts them BACK into my deck.

Then it shuffles the deck.

This code doesn't do anything.