[FOM] Large Finite Numbers in a Casual Game

[Annatala Wolf]

Some of you may be familiar with the game "Magic: the Gathering", which was
the first and is the most popular collectible card game. I used to play the
game, and my fiance was once a Pro Tour player (he received funds to play
in other countries once or twice). Recently, he found something
mathematically interesting about Magic posted online.

(You don't need to understand the mechanics to appreciate the link I'm
providing, but you might appreciate it on a deeper level if you do, so I
provide a large summary of relevant game rules below the link.)

The rules of Magic are extremely intricate, and this is not entirely
artificial. The designer of the card game took great pains to ensure that
the game could be modified by the cards themselves in as many ways as
possible while preserving a complex set of underlying algorithms for
determining the order in which things happen, and precisely what happens as
a result. This has led to some very interesting and sometimes bizarre play
situations which rely on recursion in one form or another. For a less
interesting example, it's possible to produce an infinite cascade of
effects, although most are very hard to pull off in practice. If an
infinite loop can't be stopped by either player, the game is a draw.
Usually, however, the active player has control over when the effects
cease. In this case, the rule is that the player must name a finite number
of cycles, which implies the number must be something they could write down
on paper. (I think it would be more interesting structured with ordinals,
but that's a different topic.)

Infinite loops in a game aren't particularly novel or interesting. However,
one Magic player came up with a clever challenge: how much damage could you
possibly do to the opposing player on the very first turn with an
unrestricted deck that is guaranteed NOT to be capable of producing
infinite loops?

A lower bound for the current record is 2 -> 20 -> 408. (Conway notation.
I'm still checking the math on the analysis, though.) I'm mildly curious if
a significantly better strategy exists for producing large numbers
recursively by using the same general kinds of effects.

The link below describes the process in detail. The process and analysis
are both nontrivial.


http://www.soniccenter.org/sm/mtg/megacombo.html


**************************************

(Below, I provide some general facts about how the game works that might
make it easier to follow the discussion, but you can follow the algorithm
perfectly well without the following information. It's only here in case
you'd like the satisfaction of understanding why exactly things are
happening the way they are in the game.)

**************************************

The entire combo takes place in the pre-combat main phase of play, so you
don't need to know anything about the complexity of turn order or combat
order (for one issue, spells and effects referring to Untap or Upkeep
phases will not do anything). However, it helps to know a little about the
main phase itself and the way cards are played.

Cards in your hand ("hand") and deck ("library") are called "lands" if they
have the Land type. Otherwise, they are called "spells" when in those
zones. A constructed-format deck must have 60 cards. Your discard is called
the "graveyard". "Exile" means temporarily removed from the game. The play
area is called the "battlefield" (formerly "in play"). There is also an
imaginary "stack" of spells and effects which may interrupt one another
while the bottom-most spell or effect is trying to resolve. There are lots
of ways to move cards between each of these zones. All zones are public
except the hand is private to its player and the library is private to all
players. The graveyard and library maintain a sequential order.

The card images in the discussion show give the full text of the card, but
some cards have errata, especially old cards. For example, anything labeled
"Enchant (type)" should now be "Enchantment - Aura", with text in the
description that names the type that specific Aura enchants. So if
something seems a little off, it's probably an old card you're looking at.

The upper-left corner of a card is its name. Text referring to the name of
the card means the card itself, while text that refers to "cards called
(name)" refers to all copies of the card.

The upper-right corner of a card contains the "casting cost" of the card,
which is how much "mana" it takes to "play" it from your hand to the
battlefield. Text that refers to "playing" only counts if the card is
played from your hand by paying the casting cost. Lands have no casting
cost and are the primary source of mana. Costs come in five different
colors of mana, plus a gray circle with a number in it that means "...plus
this much more mana, of any types".

The middle line under the art gives the card's type. If the card has any
supertypes (not common), these are listed first, followed by all the card's
types. (The only relevant supertype here is Legendary, and the discussion
already explains it.) The types may be followed by a dash and a list of
subtypes (usually only one). The subtypes are merely identifiers, except
for Aura (below). The symbol to the right has no function.

Types include Artifact, Creature (formerly "summon"), Enchantment, Instant,
Land, and Sorcery. There's nothing special about Artifacts, and I'll cover
the other types soon.

The text box at the bottom includes rules text (which describe what the
card does) and flavor text (in italics, which has no game effect). What
these rules mean depends on the card type. Some cards describe what happens
when the card is played. Some cards have permanent abilities, which affect
the game whenever the card is on the battlefield (when cards conflict, the
newest copy takes precedence). Some cards have triggered abilities, which
trigger when a certain condition arises while the card is on the
battlefield. And some cards have activated abilities, which are mana costs
printed directly in the text box. Paying the cost activates the effect.

Some cards refer to "tapping", or have the "tap" symbol as a cost in the
text box. Unless a card says otherwise, cards come into play untapped, and
if a card becomes tapped you can't pay any "tap" cost with that card until
next turn. Unless, of course, some other effect can "untap" the card.

On the lower right of creature cards you'll see two numbers. The number
before the slash is power: how much damage the card deals when attacking.
The number after the slash is defense: how much damage the card can take in
one turn before it is destroyed and moves to the graveyard. Creatures
cannot use any abilities requiring the "tap" symbol on the turn they come
into play unless they have "Haste". They also can't attack (which is our
source of damage to the opponent) without haste, even if they have a way to
avoid tapping.

Enchantments are like artifacts and creatures, except they never have tap
symbols in activation costs. Also, "Aura" is a subtype of enchantments that
must target something in order to come into play. In general, anything with
the word "target" means you can't place it on the stack unless a legal
target exists on the battlefield.

Lands have no casting cost, but you can only play one land drop per turn.
Lands don't go on the stack, so they can't be responded to with fast
effects.

Sorcery cards are played, the text happens, and then they resolve and go to
the graveyard. They don't become permanents like the other card types.
Instants are just like sorceries, except that they are "fast", which I'm
about to explain.

Most cards in Magic are "slow". You can only play them on your main phase,
and you can only play them when the stack of effects is empty. So the stack
of effects may contain at most one "slow" effect, and it must be on the
bottom of the stack. Instants, triggered abilities, and activated abilities
may be played at any time (for the most part), including being added to the
stack in response to other spells and abilities. The stack is, as the name
suggests, a stack. When both players pass priority, the top effect
resolves. Although the stack is imaginary, an effect in the stack can be
modified or cancelled by another effect higher up. If multiple effects
happen at the same time, the controller of whatever produced those effects
decides the order in which they go on the stack.

Last thing: counters and tokens. Most of the engine uses counters, tokens,
and triggered abilities to go super-exponential. Counters are imaginary
markers tied to a card on the battlefield that may modify the card in some
way. Different counters do different things, and there is no limit to how
many counters (or how many types of counters) can be on a card. Tokens are
permanents that aren't cards (usually these are creatures generated by
abilities). If anything would move a token from one zone to another, it
ceases to exist. Also, unless a card says "may", you don't get to choose
whether something happens. This is notable with triggered abilities.
-- 

/* Annatala Wolf, Lecturer
 * Department of Computer Science and Engineering
 * The Ohio State University
 */
enum E{A;System s;String t="/* Annatala Wolf, Lecturer%n * Department of
Computer Science and Engineering%n * The Ohio State University%n */%nenum
E{A;System s;String
t=%c%s%1$c;{s.out.printf(t,34,t);s.exit(0);}}";{s.out.printf(t,34,t);s.exit(0);}}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170504/2a46f402/attachment-0001.html>