Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: [1]

Author Topic: The Physics of Dominion  (Read 754 times)

0 Members and 1 Guest are viewing this topic.

trivialknot

  • Minion
  • *****
  • Offline Offline
  • Posts: 645
  • Respect: +978
    • View Profile
The Physics of Dominion
« on: February 25, 2018, 05:36:09 pm »
+23

Preface: I wrote an earlier article about this, but from the outset I wanted to run some simulations and return with a cleaner article.  Here it is!  I have an associated GitHub repository but it's attached to my real name so I'll only share over pm.

Despite the great variation between different games of Dominion, there is one strategy concept that is particularly enduring: the dichotomy between decks that draw (here called "Engines"), and decks that do not (here called "Big Money").  In this article, I will not give strategy advice, but instead try to understand the dichotomy through the lens of physics.  I will show that the line between engines and big money is a phase transition, much like the transitions between water, liquid and gas.

Understanding phase transitions

Most people are familiar with the phase transitions of water. At a certain temperature, water will freeze; at another temperature, water will boil. The phase of water also depends on pressure.  We can draw a phase diagram which shows the state of water as a function of temperature and pressure.


Although water is the most familiar example, phase transitions occur everywhere in physics, and in pure math as well. 

It is particularly informative to consider the bond percolation model.  Suppose that we have a network of pipes, with hubs arranged in a 2-dimension grid. Some adjacent hubs are connected by pipe, and others are not. If the pipes are arranged randomly, what is the probability that water will be able to flow from point A to point B, in the limit as A and B are infinitely far apart?


The black lines represent pipes. Image credit: Wikipedia

We have two possible scenarios:
  • The hubs are broken up into a series of islands, each inaccessible from the others. Some islands might be very large, but they are still finite in size. As the distance between A and B goes to infinity, there is zero probability that they are connected on the same island.
  • There is at least one infinitely large network of hubs. Although there will still be some disconnected islands, there is now a nonzero probability that neither A nor B is on an island, and they are connected to each other.
If you increase the density of pipes, there will be a sudden transition from case 1 to case 2.  This is a phase transition.  Although the model is based on an infinite grid of pipes, a phase transition still occurs even in a finite grid--it just won't be quite as sudden.

Phase transitions in Dominion

In Dominion, we are not trying to traverse a network of pipes, we are trying to traverse our deck by drawing cards.  As with the network of pipes, we will consider the limit as the deck is infinitely large.


The simplest deck that we can consider is a deck with just Coppers and Labs.  In this deck, we can tune one parameter, the fraction of Labs (L). As a function of L, what is the expected payoff of a single turn?

Here's what the simulations show. For L < 1/2, the expected payoff is finite. For L > 1/2, the payoff is infinite (i.e. it gets larger and larger the longer the simulation runs). L = 1/2 is the phase transition.


At first, it would seem you can't do any better than infinity. However, what you can do is increase the probability of drawing infinitely on any given turn. I refer to this probability as Reliability.

Interestingly, at exactly L = 1/2, the expected payoff is infinite, but the reliability is zero. However, this only applies to an infinite deck. In a finite deck, the phase transition is not as sharp, and the payoff is capped by the total payoff in our deck. The phase transition also occurs slightly earlier because we draw 5 cards for free.


The Village/Smithy Phase Diagram


Now we'll consider an infinite deck with Villages, Smithies, and Copper.  Now we have two tuning parameters, the fraction of Villages (V) and fraction of Smithies (S)--and the fraction of Copper is just 1-S-V.  With two parameters, we can draw a two-dimensional phase diagram, just like the phase diagram of water.


For some values of S and V, the expected payoff is finite, which is shown with one color scale. For other values of S and V, there is a probability of infinite payoff; in these cases I show the reliability with a different color scale. The diagram is shaped like a triangle because the total number of Villages and Smithies must be less than the number of cards in the deck.

The diagram also shows that if you add a few Smithies, you can improve your deck, even in absence of any Villages.  This is the "Big Money plus terminal draw" strategy.  However, this strategy is not associated with any phase transition, and is fundamentally distinct from the Village/Smithy engine.

Conclusions

This analysis shows how Engine and Big Money strategies are fundamentally different.  It also shows why, if you go for an engine, you usually want to go all the way.  Moving towards the engine phase transition has some opportunity cost, and sometimes, the opportunity cost is worth it to see that big increase in payoff that occurs at the phase transition.  Sometimes, the opportunity cost is not worth it.  Rarely is it best to move towards the phase transition, only to stop short.

This analysis applies to a wide variety of Engines in Dominion, but it is also interesting to consider exceptions.  In sufficiently small decks, phase transitions become meaningless.  There is no phase transition in draw-to-X decks, such as the one enabled by Minion, and City Quarter evades analysis as well.  Some sifters actually generate multiple phase transitions, the first phase transition allowing you to draw through your deck, and the second allowing you to draw the cards you discarded.

Although a simple physics-based analysis cannot teach you how to play Dominion well, I hope that it has helped you appreciate some of its contours.
Logged

JW

  • Minion
  • *****
  • Offline Offline
  • Posts: 720
  • Shuffle iT Username: JW
  • Respect: +1312
    • View Profile
Re: The Physics of Dominion
« Reply #1 on: February 25, 2018, 05:55:06 pm »
0


Does the shading represent particular points on the distribution? If so, there's something strange going on because the shades curve declines when the percentage of labs gets higher, even though the chance of drawing all 15 copper should be going up.
Logged

trivialknot

  • Minion
  • *****
  • Offline Offline
  • Posts: 645
  • Respect: +978
    • View Profile
Re: The Physics of Dominion
« Reply #2 on: February 25, 2018, 06:14:11 pm »
0

@JW,
The shading represents the standard deviation, which was calculated by the simulation.  Of course you can't get more than 15 copper, and the distribution would be skewed, but I didn't record that part of the results.
Logged

timchen

  • Minion
  • *****
  • Offline Offline
  • Posts: 704
  • Shuffle iT Username: allfail
  • Respect: +233
    • View Profile
Re: The Physics of Dominion
« Reply #3 on: March 02, 2018, 03:48:53 am »
+1

Why does this show that if you want to go engine you want to go all the way? Also what does going all the way mean? If you mean just over the transition then it is probably too conservative when the deck size is large enough since you would have no reliability; if you go all the way toward a deck full of lab or village/smithy it is certainly not optimal.
Logged

trivialknot

  • Minion
  • *****
  • Offline Offline
  • Posts: 645
  • Respect: +978
    • View Profile
Re: The Physics of Dominion
« Reply #4 on: March 02, 2018, 11:57:34 am »
0

Why does this show that if you want to go engine you want to go all the way? Also what does going all the way mean? If you mean just over the transition then it is probably too conservative when the deck size is large enough since you would have no reliability; if you go all the way toward a deck full of lab or village/smithy it is certainly not optimal.
You seem to have figured it out for yourself, that "all the way" means going somewhat past the phase transition.

But the purpose isn't really to give strategy advice.  "Go somewhat past the phase transition" is at best a rule of thumb.  You can poke at it with questions like "what if opportunity cost is nonlinear?" or "what if payoff is nonlinear?"  A more direct discussion, such as Titandrake's article on overdrawing would be more on point.

I see your topological insulator, btw.
Logged

xer

  • Herbalist
  • **
  • Offline Offline
  • Posts: 7
  • Shuffle iT Username: xer
  • Respect: +24
    • View Profile
Re: The Physics of Dominion
« Reply #5 on: March 08, 2018, 10:50:27 am »
+3

Regarding the Lab Engine:
When I read the articles I was really confused what 'payoff' and 'reliability' are supposed to be and doubted it could be as simple as
Let x be the average value of a card.  The average value of a turn is simply 5*x.
x = 1-D + D*2*x
x = 1+D/(1-2D)
so i took the time to think about it myself. I said that you draw 5 cards, play all labs at once, draw all the cards, play all the Labs from those cards etc until you only draw Copper. To end up with M money you need to play exactly M-5 Labs. The probability that you're able to draw and play exactly l Labs is given by L(l,5), where L is

l is the number of Labs you still need to play, c is the number of cards you're drawing and pLab is the probability of drawing a Lab.
If you already played all (M-5) Labs, you need all cards that you draw to be Coppers, otherwise you can draw any number (k) of Labs, but not more than (M-5) and not more than you draw cards. You then play those k Labs, draw your 2k cards and reduce the amount of needed Labs by k.
Prob gives you the probability that the c cards you draw contain exactly k Labs.

I wrote a script to evaluate that formula for me and it gave me this plot:


To my surprise that showed quite nicely what 'reliability' is: The probability to draw an infinite amount of cards or "The white space in my plot (as x approaches ∞)". It's non-trivial that such a probability exists, but it actually makes a lot of sense: For a high density of Labs you almost double the amount of cards you draw each cycle of playing and drawing, so the probability to draw enough Coppers to end it vanishes so quickly that it converges against a value < 1.

I assume with 'payoff' you mean the average amount of money made each turn. In that case it's really confusing to say that payoff is infinite, since the reliability to get infinite money is 0%. I'm not sure how to determine what actually happens at pLab =.5

I think it's possible to do a similiar calculation for a Herald engine, but that's probably too difficult for me already. Not sure what you'd gain from it anyway.
« Last Edit: March 08, 2018, 10:53:14 am by xer »
Logged

trivialknot

  • Minion
  • *****
  • Offline Offline
  • Posts: 645
  • Respect: +978
    • View Profile
Re: The Physics of Dominion
« Reply #6 on: March 08, 2018, 12:51:08 pm »
+2

When I read the articles I was really confused what 'payoff' and 'reliability' are supposed to be and doubted it could be as simple as[...]
If you have any ideas on how to make the article more clear, let me know.  I may revise it later.  I want it to be accessible to people even without a math or physics background.

To my surprise that showed quite nicely what 'reliability' is: The probability to draw an infinite amount of cards or "The white space in my plot (as x approaches ∞)". It's non-trivial that such a probability exists, but it actually makes a lot of sense: For a high density of Labs you almost double the amount of cards you draw each cycle of playing and drawing, so the probability to draw enough Coppers to end it vanishes so quickly that it converges against a value < 1.
That sounds right.  The concept of reliability can be initially surprising, because you might think, infinity is a really long time, surely at some point you will encounter a long string of copper and stop drawing.  But the more you draw, the longer the string of bad luck required in order to stop drawing.

I already had an expectation that you could draw infinitely, because most phase transitions have something analogous.  But maybe this expectation leads me to downplay how surprising it is, and explain it poorly.

I assume with 'payoff' you mean the average amount of money made each turn. In that case it's really confusing to say that payoff is infinite, since the reliability to get infinite money is 0%. I'm not sure how to determine what actually happens at pLab =.5
Right, the L=0.5 case is very difficult.  And you can't even use a simulation, because a simulation is always finite.  But we were discussing this in another thread, and someone managed to prove it.  Basically, drawing will eventually halt, but it takes so long to halt that the expected payoff doesn't converge.  But the proof is kind of hard to explain--this would be a very difficult homework problem in a college course on probability.
Logged
Pages: [1]
 

Page created in 0.096 seconds with 20 queries.