PrefaceMath ahead! In this article I try to explain some mathematical concepts and how they relate to Dominion, in particular with respect to infinite loops. With this mathematical toolkit you should be able to understand why infinite loops take the shape they do, and be better able to predict which cards do and do not enable new loops. The strategic relevance of the presented concepts in your day-to-day play is... unclear. If this article belongs in some other (sub)forum, let Theory know.
Edit: If you are unfamiliar with the infinite loops, I wrote a survey of them in
a post in this thread, based on
trivialknot's suggestion. You may want to read this first.
I'm interested in feedback: could I organize it better, is it too mathy, have I expressed the math clearly enough, is there anything you think could be improved? Was it useful to you? Can you think of applications of this approach I haven't mentioned?
A theory of finite processesIf I sell all my Pokemon cards and don't buy any new ones, I will eventually have none left, i.e. this is a finite process. The number of cards I own is an upper bound on how many more sales I have to make; observe that this number always decreases, but never below 0.
A set of numbers A is called well-ordered if, for any set non-empty set B which is a subset of A, there is an element of B which is smaller than all the others. The natural numbers is an example of a well-ordered set. The set of integers is not: the set of negative numbers is non-empty, but there is no smallest negative number, since -1 > -2 > -3 > ... and so on, infinitely.
In a well-ordered set, there cannot be an infinite decrease sequence: the set of all numbers in the sequence is a non-empty set and by well-ordering must have a smallest element, let's say the nth in the sequence. But since the sequence is decreasing, the (n+1)th element is less than the nth, violating the assumption that the nth element was the smallest.
So, if we can map some process onto a decreasing sequence of natural numbers, or of elements of some other well-ordered set, we can conclude that the process cannot be infinite.
This works great in the case of selling pokemon cards: the number of cards I own is a decreasing sequence. To apply this to Dominion, we will need something more than a single number.
If A and B are two well-ordered set, their cartesian product—the set of pairs (x, y) with x in A and y in B—is also a well-ordered set, if we use the lexicographic ordering; that is, we take (x1, y1) < (x2, y2) to be true iff either x1 < x2 or x1 = x2 and y1 < y2. To see that A×B is well-ordered, note that since A is well-ordered, in any non-empty set {(x1, y1), (x2, y2), ...} there is some smallest x-value, x*. Among the pairs {(x*, y_a), (x*, y_b), ...} there is some smallest y-value, y*. The pair (x*, y*) is smaller than all the other pairs. To see this, take some other pair (x', y'). Either x* < x', and so (x*, y*) < (x', y') by the lexicographic ordering, or else x* = x' and y* < y'.
In particular, pairs of natural numbers form a well-ordered set. If I repeatedly sell some Pokemon cards, sell some Magic cards and/or trade some of my Pokemon cards for some Magic cards, I will eventually have neither Pokemon nor Magic cards left. The pair (p, m) always goes down whenever I complete a transaction, where p is the number of pokemon cards I own and p:Pokemon::m:Magic. Note that the number of Magic cards I own may increase, but only if p simultaneously decreases. The (p, m) pairs form a decreasing sequence (p1, m1) > (p2, m2) > ..., so the process is finite. (It may help to observe that if p stays constant, m eventually decreases to 0, at which point p must decrease by at least 1—so p also eventually reaches 0.)
If we have three well-ordered sets, A, B and C, then B×C is well-ordered, and so is A×(B×C). In general, a cartesian product A1×(A2×(A3×...)) of any finite number of well-ordered sets is itself well-ordered. If I make a list of card games, e.g. Pokemon, Magic, Yu-Gi-Oh, etc., such that I will sell cards from any game, or exchange cards from games earlier in the list for cards from games later in the list (but not the other direction), eventually I get rid of all my cards. So long as the number of cards from the first n-1 games remains constant, the number of cards from the last game must decrease to 0, so the number of cards from game n-2 must decrease by at least one; repeat this, and so eventualy the number of cards from n-3, n-4, ..., 1 must all decrease to 0.
For convenience, let's use (x1, x2, ..., xn) as a shorthand for (x1, (x2, (..., (x_(n-1), xn))).
Note that in the triple (p, m, y) where ...::y:YuGiOh, I can trade some Pokemon cards for Yu-Gi-Oh cards while keeping the number of Magic cards constant. In general, the tuple can contain numbers which either decrease or stay the same at each step of the process, provided the tuple-as-a-whole decrease.
The last theorem: if some sequence of tuples (x1, x2, ..., xn) > (y1, y2, ..., yn) > ... forms a decreasing sequence, you can append anything after the tuples, and you can prepend anything that never increases (but maybe sometimes doesn't decrease, i.e. stays the same for one or more steps) and the sequence will still be decreasing. Consider (x0, x1, ..., xn, x_(n+1), ..., xm) and (y0, y1, ..., yn, y_(n+1), ..., ym) with x0 >= y0. If x0 > y0, then (x0, ..., xm) > (y0, ..., ym). Otherwise, (x0, ..., xm) > (y0, ..., xm) iff (x1, ..., xm) > (y1, ..., ym) by definition of the lexicographic comparison. Repeat this argument for x1, x2, etc., until either we conclude that (x0, ..., xm) > (y0, ..., xm) or we get to xn and yn. By assumption, (x1, ..., xn) > (y1, ..., yn); given that xi=yi for i=1...n-1, it must be the case that xn > yn (by definition of the lexicographic comparison).
These decreasing sequences in well-ordered sets are sometimes called
termination functions. (Or rather, the functions f that map from states of the process to some well-ordered set, such that f(x) > f(y) if state y can occur after state x, are called termination functions.)
Applications to DominionHow does this relate to Dominion? Given that there are infinite loops in Dominion, it's impossible to prove that there aren't any. In particular, we can't use the above methodology to make such a proof. Or rather, if we do the proof will be incorrect. That's what I will do. The point of doing this is that it's instructive to try and fail: when trying to do so, you will think of the quantitative aspects of Dominion which but for a few exceptions are always decreasing. Knowing the almost-monotone subprocesses will make the exceptions stand out, and being aware of the currently known exceptions will help you fiddle with loops.
Throning a Warehouse sets up four effects to be resolved: draw 3, discard 3, draw 3, discard 3. I assume without proof that no matter what sequence of plays you make, the not-yet-resolved effects will eventually resolve, no matter how many reactions you play. I think the rules are such that if you may reveal Moat, you may reveal it any number of times. Given that almost all reactions can either do something a finite number of times or are idempotent and thus have trivial fixpoint/limit behavior, one could make some rules which forbid degenerate infinite plays, and under those rules my assumption would actually be true. But the way everyone actually plays (except maybe a few jerks who run out of willing opponents?), I think that it
is true.
Of course, the number of not-yet-resolved effects is not a termination function on its own: it's 0 at the start of your action phase and goes to 4 if you Throne a Warehouse. But this requires you to put a card into play. So let's try that as a termination function: (number of cards not currently in play, number of yet unresolved effects).
Playing a reserve card puts it on your tavern mat rather than in play, so this doesn't decrease the termination function. Also, calling a reserve card puts it in play, which increases the termination function. To remedy this, let's try the following: (number of cards neither in play nor on your tavern mat, cards not in play, pending effects). This works for both non-reserve actions, playing a reserve and calling a reserve.
This is the core termination function which "proves" that you can only play a finite number of actions each turn. Except: if you play a self-trasher, such a Mining Village or Pixie, the number of cards not in play increases when you trash it, proving that it is in fact not a termination function. Likewise, if you gain a Mandarin or buy a Bonfire you can take cards out of play.
With Bonfire you face the challenge of having to get cards out of the trash, so we could use (cards not in the trash, not in play/tavern, not in play, pending effects) as a termination function, except (a) we already know that Bonfire violates this, and more importantly (b) the number of cards not in the trash can increase, if we play Lurker, Rogue or Graverobber.
Likewise, any quantitative feature of Dominion game states that (almost) always stay the same or decrease could be prepended. The interesting ones I know are the following:
- If we split the buy phase in two, the turn structure is (Action, Treasures, Purchase, Night, Clean-up); the number of steps to do is decreasing, but for Villa. Note that Horn of Plenty can gain Villa during the treasures sub-phase.
- Card only leave the supply, never enter it. Exceptions are Ambassador (it only returns cards on net in 2-player games), and a few self-returners such as Spoils, Madman and Wish.
- Cards never leave the trash, except for Lurker, Rogue and Graverobber.
- Cards never leave your opponents' decks, but for Masquerade, Thief, Noble Brigand and trashing attacks.
- Buying a card except with Black Market on net costs you a buy, except for Forum
- When you buy a card, a card leaves the supply, except if you have Trader and the Silvers are out.
- When you turn a card in the trash face down with Necromancer, it isn't turned face up again until the turn ends or the card leaves the trash.
Note in particular that Necromancer isn't on any list of exceptions. When Nocturne came out, some people speculated that Necromancer might be useful for constructing infinite loops. I think it won't: to play some card an arbitrary number of times, you must already be able to take it out of the trash and put it back the same number of times; so Necromancer can perhaps feed off an already existing loop (and maybe improve their capabilities), but not create any new ones. To find new loops or evaluate whether a new card might enable a new loop, find some almost weakly decreasing quantity which the new card increases.
How loops relates to pinsI have skipped over the fact that the clean-up phase takes cards out of play. If you can set up a pin such that your opponent(s) can't do anything on their turn(s), or can only do things which won't prevent you from doing what you want, you can set up an infinite process which spans multiple turns and uses the clean-up step to take cards out of play.
For example, with the kingdom {Scrying Pool, Scheme, Miser, Monument, Pirate Ship, Minion, Rabble, Relic, Storyteller, King's Court}, you can use multiple KC'd Rabbles to make your opponents topdeck three blanks, then play Monument for 1 VP, play Relic with Storyteller then play Minion to make them discard their hand and draw a hand of 3 blanks. Miser, Scheme and Scrying Pool are there to ensure perfect reliability: use 5 Scrying Pools to draw your deck (which has no Copper in it thanks to Miser), play 5 Schemes, do the above, then topdeck 5 Scrying Pools for next turn. Pirate Ship prevents your opponents' decks from growing too big for your Rabbles to topdeck three blanks. All they can do is buy Copper or Curse so they can't end the game, as you need no more than 9 copies of any card and can probably make do with less. (But not in practice, most likely, since it takes too long to set up.)
The limits of this approachThis approach doesn't say much about what I call finite loops. There may be some set of k cards such that playing one of each in the right order will gain and draw one more copy of each plus a victory card of your choice. Such a process is finite since it runs out of copies to gain (assuming you don't put any back), but by assumption it empties the Province or Colony pile into your deck, which is often a strong move.
Is there something special about Dominion? Could we also apply this type of analysis to e.g. M:tG? Yes and no. In M:tG, within the span of a single turn it's more common for permanents to tap than untap, for cards to leave than enter your deck and for cards to enter than leave your graveyard, but the exceptions to these are all very numerous; I attribute this in part to M:tG having many more cards and in part to a difference in design philosophy. What distinguishes Dominion is that the main almost-correct termination function is very restrictive and has very few exceptions, and the other almost-never-increasing quantities likewise have very few exceptions. You get more mileage out of this approach in Dominion than in e.g. M:tG.
Appendix: the example pin kingdom, in pictures
Edit: Actually, you might need to add Young Witch (with Scheme as the Bane) to make sure your opponents have enough junk in their deck; otherwise your Minion might make them discard some of their junk, and your Rabbles will fail to topdeck enough junk to lock them down.
, and 2 buys instead of 1.
.
