Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[jonaskoelker]

Preface

Math 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 processes

If 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 Dominion

How 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 pins

I 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 approach

This 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.

[trivialknot]

A few comments on organization...

You should start with the simplest example of an infinite loop in Dominion.  Not everyone follows the Puzzles & Challenges forum.

For the Pokemon card section, I feel like the point gets lost in all the comments about well-ordering, cartesian products, and lexicographical ordering, and I say that as somebody who already knew what those things were to begin with.  I would lead with all the examples (Pokemon, followed by Pokemon+MGT, followed by Pokemon+MGT+YuGiOh), and appeal to intuition as to why these processes are finite.  Then you can introduce the math, which can be a segue to the applications to Dominion.

As for the analysis itself, my question is, why does every infinite loop involve either KC or Crown+Mandarin?  Or at least, I think every loop has that requirement, maybe I am unaware of the exceptions.

[jonaskoelker]

A few comments on organization...

[...]

As for the analysis itself, my question is, why does every infinite loop involve either KC or Crown+Mandarin?  Or at least, I think every loop has that requirement, maybe I am unaware of the exceptions.

Thank you for your feedback. I think I'll write a version 2 soonish, in a new post, and prepend a "Changelog" section to my first post with a link to the updated version.

My article points at a condition that's necessary to satisfy in order to construct an infinite loop—that a particular way of proving it finite always failss—but this condition is certainly not sufficient.

The on-gain effect of Mandarin lets you take cards out of play, which demonstrates my proposed termination function to be invalid. However, that's not enough: to base an infinite loop around taking cards out of play with Mandarin, you most likely will have to take cards out of play infinitely often, meaning you'll have to gain a Mandarin infinitely often.  There are very few treasures which help you do that—I mean, they give you money which you can use to buy a Mandarin, but then you face the problem of putting the Mandarin back into the supply; Ambassador is the only help here, I think.

About the only treasure that can do it in your action phase is Crown—and then only if it's a throned/crowned/KC'd/procession'd Overlord played as a Crown, because you can play the Overlord as something else on the second and later plays.

That is, the use of Overlord and Crown is a clever hack that makes Mandarin effectively topdeck actions rather than just treasures. (I think Band of Misfits would be just as fine as Overlord, provided Crown costs less than BoM, which only Ferry enables, IINM.)

That is: loops with Mandarin involve not just Crown but also either Overlord or Band of Misfits, because the extra parts help get around the limitations of Mandarin.

Why is King's Court used in the other loops? In some hand-wavy sense, "because you get out more than what you put in". When you e.g. Throne Room a Warehouse, you spend two cards to get two times the effect of a Warehouse. It's a 2-for-2. If you KC a Warehouse, you spend two cards but get three times the effect of one card, a 3-for-2.

One loop I have discovered which uses Bonfire to take cards out of play uses KC'd Lurkers to gain cards back from the trash, but otherwise doesn't use KC. If I had a Grand Lurker, "+1 Action. Choose one: Trash two Action cards from the Supply, or gain two Action cards from the trash, I would not need a King's Court in that loop.

So in some sense, the use of KC is a happenstance—it's a consequence of the magnitude of certain other effects (at least in one instance) and not clearly a consequence of some general theory, the way the use of Mandarin or Bonfire is.

We could also consider the other loop I've found—repeatedly KC an Overlord as Mining Village (draw another Overlord; trash for money), Lurker (gain itself from trash), KC (to repeat this sequence). The payload here is Mining Village; if Mining Village said "you may gain an action from the trash" after its other text, you wouldn't need KC here.

Once again, while KC is in some sense fundamentally different from Throne Room in that it gives you 3-for-2 rather than n-for-n, this difference is only necessary due to somewhat incidental reasons

Aside: One thing I haven't emphasized enough in the article is that because the exceptions are rare, very often (i.e. in many random kingdoms) my proposed only-almost termination function is in fact a valid termination function. Knowing about this theory you detect the absence of infinite loops.

[jonaskoelker]

A survey of known infinite loops

I think the first widely popularized loop is the following, by Majiponi in this post:

Code: [Select]

Overlord, Crown, Raze, Lurker, Mandarin, Watchtower

Once the setup is done, you play 5xOverlord first as 4xCrown then a self-trasher (Raze), then Lurker to gain a Mandarin from the trash, reveal Watchtower to put Mandarin back in the trash. Since Mandarin has taken your Overlords out of play, you can play them as something other than Crown on the second play; play them as Lurker to gain back the trashed Overlord, a payload card of your choice, then Watchtower to draw back your Overlords. (Mandarin is a fine payload if all you want is money. Farmers' Market gives you money, buys and VP for just one kingdom slot.)

Qvist has shown how you can set this combo off in turn 5, with the right support, in the following video:



The second loop I want to highlight is by me:

Code: [Select]

Lurker, Scrying Pool, Ambassador, Masquerade, Cutpurse, Thief, Pirate Ship, Villa, King's Court, Bonfire, Travelling Fair

Bonfire takes your cards out of play, Villa gets you back to your action phase, Ambassador puts Villa back in the supply, Cutpurse/Masquerade/Thief takes Villa back from your opponent, King's Court on Lurker gains your cards back from the trash, Scrying Pool draws the cards you have gained and Pirate Ship (or Miser if you prefer) pays for it all. The details are all in the post where I first presented the loop, in the same thread as Majiponi's loop.

There are several other loops which exploit Villa in that thread; some of them only work in solo mode or with cooperative opponents. I'm not aware of anything of them being on video.

The third infinite loop I want to present is also by me, posted about in its own thread.

Code: [Select]

King's Court, Overlord, Mining Village, Lurker

You play a KC'd Overlord as (1) a self-trasher (Mining Village) which draws a second Overlord; (2) Lurker to gain itself back; and (3) a King's Court, cost-reduced somehow, to begin repeating the next iteration of the loop.

Qvist has illustrated how to set this off in turn 1(!) and empty the supply in the following video, which uses Pixie instead of Mining Village as the self-trasher.



This is based on the work of Mith.

The last infinite combo I want to highlight is this:

Code: [Select]

Goons, Forum, Trader

Reduce the cost of Forum to $0 (3xQuarry, 5xHighway, ...), then repeatedly buy a Forum and reveal Trader to leave the Forum in the supply, while still gaining 1 VP. If you have Merchant Guild you can get any amount of coin tokens; with Villa you can spend them the same turn and with Travelling Fair you can turn them into buys.

The loop has been described in the Infinite Combos thread.


A short mini-survey of known finite loops

Beyond infinite loops, there are also what I call finite loops (or sometimes bounded loops), which can be quite powerful. I have not thought super-carefully about it, but I'm fairly confident that in the following videos you can find one or more sequences of moves which you can repeat up to k times, where k is the number of cards left in some pile.

The first is a turn 6 win by Dan Brooks:



The second is a turn 1 win by Qvist:



These are not infinite loops, but they illustrate very well that loops do not need to be infinite to be extremely powerful. I notice that Procession is featured in both videos. Both throning and taking cards out of play are useful effects, and Procession does both.

[Qvist]

Infinite if the piles are infinite:

Develop Lost City Fortress

Hand: Fortress, Fortress, Lost City, Develop
Play Fortress,
Play Develop on Fortress, gaining Develop and Lost City topdecked, play Lost City to draw those
Play Develop on Fortress, gaining Develop and Lost City topdecked, play Lost City to draw those
Play Develop on Fortress, gaining Develop and Lost City topdecked, play Lost City to draw those
...

[jonaskoelker]

Also, you can empty the supply with a finite loop doing most but not all of the work, provided you are either an extraterrestrial supercomputer or Celestial Chameleon:

Beyond the Impossible - Empty the Supply by Turn 5.

Empty the Supply in 4 Turns.

Check the dates, and contemplate how the cards available were merely moderately b0rken...

[mith]

The earlier unbounded loops in the linked thread are instructive; the Crown/Mandarin trick in majiponi's loop was found by ephesos, for example, and the core of the Bonfire/Ambassador loop was the first solution given to the original challenge, provided by florrat.

I think in some sense the PSA solution of KC/Overlord/Trasher/Lurker melds parts of both into a very efficient and usable beast - Crown/Mandarin is built on removing the Overlord/BoM from play in order to reuse it (which self-trashing also does), while Bonfire/Ambassador is built on regaining all your played cards from the trash.

[jonaskoelker]

Infinite if the piles are infinite: [...]

I think this is a good definition of "bounded loop"—the one inherently finite quantity I can think of in Dominion is the number of cards. The vanilla bonuses and tokens can all be had in infinite quantity (though it's hard to rack up debt), and I'm hard pressed to find another quantitative aspect of a game state. (Maybe number of actions played for Conspirator and Peddler, and number of Crossroads played for Crossroads, but meh, they're dull and have nice limiting behavior.)

Also, this highlights very clearly why termination functions don't help us analyze bounded loops, or at least not the function I proposed: the number of cards neither in play nor on the tavern mat starts out infinite and stays infinite after each play.

My best idea for an almost-correct termination function in the case of infinite piles would be something that counts cards in your hand, draw pile and discard pile, perhaps with actions thrown in somewhere. The obvious thing that strikes me is that some cards draw more cards, so maybe you divide cards-in-hand into draw-in-hand and other cards in hand, and hope that relatively few cards can gain draw to convenient places.

But... well, here's an exercise: find a loop that's infinite if piles are infinite. Measure how much time you took. Spend an equal amount of time trying to find a loop that's infinite if piles are finite. Here's my solution to the first part:

Cost-reduce King's Court enough (with e.g. Highway), then KC a KC, KC'ing an Ironworks to gain KC, Ironworks and Lurker to your deck (thanks to Watchtower or Travelling Fair), then KC a Lurker trashing 3xCultist to draw 9 cards, then KC the newly drawn KC and repeat the loop.

If some of the cards drawn after the gained 3 were KC and Ironworks, you could also sneak in a KC'd Ironworks to gain KC, Ironworks and something else, so with a bit more setup this loop not only draws infinitely but gains infinitely. (For example, more Highways to cost-reduce everything into Ironworks range, more Lurkers to gain potion- or debt-costing actions and Stonemason to gain Philosopher's Stone and Vineyard off of e.g. Possession.)

I thought this up almost as fast as I could type it. I have found two infinite loops (with finite piles), and both took a lot longer to find. One was a variation on work done by others, so I had a lot of ideas given to me.

Based on this, I think it might be difficult to find a termination function that only has very few exceptions.

[luser]

if piles are infinite the best combo is bot's main strategy. other strategies are ironworks-ironworks-ironworks... with card token or inheritance