Magic: the Simulator

A simulator for the trading card game "Magic: the Gathering".

Technical Challenges

"Magic: the Gathering" is a strategic trading card game. Its rules are extremely complex - the Comprehensive Rules span over 300 pages! The goal of this project is to write a simulator for some of these rules - enough to play a game.

A significant technical challenge arises from the fact that many game effects "look back in time" to check whether certain things should happen. For example:

113.7a. Once activated or triggered, an ability exists on the stack independently of its source [...] if the source is no longer in the zone it's expected to be in at that time, its last known information is used. The source can still perform the action even though it no longer exists.

302.6. [...] A creature can't attack unless it has been under its controller's control continuously since their most recent turn began.

603.10. [...] the game "looks back in time" to determine if those abilities trigger, using the existence of those abilities and the appearance of objects immediately prior to the event.

It turns out that quite a lot of Magic's rules refer to the past, in arbitrarily complex ways. To handle looking back in time, and doing so efficiently, the entire game state is tracked temporally.

Temporal Maps

We use a novel "temporal entity-component-system" architecture. In traditional ECS architectures, each entity is associated with at most one component of a given type. However, in a temporal ECS, the components associated with each entity are tagged with timestamps of when they were added and removed. This allows us to store the entire past game state to be queried at will.

Implemented naively, this would be quite inefficient because we often need to query components both across space and across time. To solve this problem, we use a novel data structure called a "temporal map" which combines an interval tree (to query across time) with a B-tree indexed by entity IDs (to query across space).

The Magic rules also occasionally call for "undoing" past events and returning to a previous game state. This would be challenging and inefficient in a traditional setting, but fortunately, this is straightforward in a temporal ECS: we can simply query across time for all events that happened after a given checkpoint and remove them.

Secrets

Magic is a game where each of the players have cards in their hand that they don't show to others. To simulate this, we render secret information to special log files attached to auxiliary terminals. That way, each player can just view the terminal corresponding to their hand, and they won't see the others'. The state of the battlefield is rendered to an additional terminal for ease of use.

Continuation-Passing Style

The main loop of the simulator is written in continuation-passing style. Each event produces a "continuation", which is the event that should be executed immediately afterwards. By unrolling the call stack in this way, we can perform useful tasks such as regularly printing the battlefield state in between continuation calls.