Dominion Strategy Forum

• July 19, 2018, 12:13:22 am
• Welcome, Guest

News:

DominionStrategy Wiki

Pages: 1 2 [3]  All

AuthorTopic: Dominion 101: What is an engine?  (Read 4936 times)

0 Members and 1 Guest are viewing this topic.

crj

• Jester
• Offline
• Posts: 786
• Respect: +901
Re: Dominion 101: What is an engine?
« Reply #50 on: October 18, 2017, 09:37:13 am »
+4

Not that engine is Dominion-specific language in the first place
Yes, "engine" is Dominion-specific language.
Quote
it is used more generally in virtually all tableau- and deckbuilding games
The term "engine" also has a diversity of other, less specific, meanings. But when talking about Dominion specifically, it has a Dominion-specific meaning.

Why are you finding this so hard to understand or accept? You could, if you really wanted, suggest that the Dominion-specific meaning is unhelpful or misguided in some way, but you seem to be trying to say "Engine" doesn't have a Dominion-specific meaning.

You're wrong; it does.
Logged

werothegreat

• Offline
• Posts: 8016
• Prepare to be boarded!
• Respect: +9239
Re: Dominion 101: What is an engine?
« Reply #51 on: October 18, 2017, 10:04:07 am »
+2

As far as I know, Dominion is unique among deckbuilding games in having a static tableau.  All the other deckbuilders I've seen have a "center row" of sorts where a selection of cards is presented, and once one is taken, another randomly replaces it from a shuffled deck.  It'd be like playing Dominion without a Kingdom, but everyone has a Princed Black Market.

What this means is that it's a lot easier to make a consistent engine in Dominion than, say, Ascension or Legendary.  In the former, you can plan out your strategy from the get-go, whereas in the latter, you have to scrounge from the scraps that get thrown out, hopefully before anyone else grabs them.
« Last Edit: October 18, 2017, 10:05:46 am by werothegreat »
Logged
Contrary to popular belief, I do not run the wiki all on my own.  There are plenty of other people who are actively editing.  Go bother them!

Check out this fantasy epic adventure novel I wrote, the Broken Globe!  http://www.amazon.com/Broken-Globe-Tyr-Chronicles-Book-ebook/dp/B00LR1SZAS/

trivialknot

• Minion
• Offline
• Posts: 578
• Respect: +908
Re: Dominion 101: What is an engine?
« Reply #52 on: October 18, 2017, 10:45:06 am »
+1

I don't even know what it means to say a Dominion engine is "reliable" and "consistent".  Like, are reliability and consistency two different things, or are they just redundant synonyms?  And it seems to me that engines can be less consistent than a plain old Big Money deck.  Engines can dud, which produces a large variance between turns.  Big Money decks, on the other hand, are supposed to be robust to card order.
Logged

josh56

• Thief
• Offline
• Posts: 91
• Respect: +60
Re: Dominion 101: What is an engine?
« Reply #53 on: October 18, 2017, 05:08:22 pm »
+1

Not that engine is Dominion-specific language in the first place
Yes, "engine" is Dominion-specific language.
The term engine is used in other games.
As I already said, it is fine to have a Dominion-is-the-only-game-in-the-world perspective but I prefer a view that focuses on the commonalities among different games.

As far as I know, Dominion is unique among deckbuilding games in having a static tableau.
Nightfall also has draftable cards which are available to everybody without changing throughout the entire game. I am not a fan of the Star Realms like dynamic tableaus in deck-building; as you pointed out they usually lead to less strategic and more random play.
Logged

Awaclus

• Offline
• Posts: 10626
• (´｡• ω •｡`)
• Respect: +11072
Re: Dominion 101: What is an engine?
« Reply #54 on: October 18, 2017, 05:23:33 pm »
+1

The term engine is used in other games.
As I already said, it is fine to have a Dominion-is-the-only-game-in-the-world perspective but I prefer a view that focuses on the commonalities among different games.

Why do you think that it needs to mean the same thing in all games?
Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

• Explorer
• Offline
• Posts: 316
• Grand Market = cantrip Woodcutter
• Respect: +366
Re: Dominion 101: What is an engine?
« Reply #55 on: October 19, 2017, 07:34:41 am »
+2

Unfortunately, this [definition of an engine] doesn't work out in practice.  [Counterexample: Village/Smithy/Woodcutter/3xTreasure, times 1, 2 and 3]

This just goes to show that a deck with 50% basic treasures is probably not an engine. Your suggested deck is not an engine.

To me, this example shows that a very thin deck is easier to draw all of than a multiplied version of that deck, because you need to draw fewer additional cards above your 5 starting cards to draw the whole deck.

The percentage of basic treasure in your deck that you can have while still having a high chance to draw your deck depends on the size of the deck and the strength of the draw available. 50% or higher basic treasure is consistent with having a high chance to draw the deck if the draw is good enough. For example, decks like 2 Margrave (with +Action token), 4 Gold, or 4 Margrave (with + Action token), 8 Gold draw themselves reliably.

Even this deck falls victim to the same principle.  The 2 Margrave (with +action) and 4 gold deck is 100% reliable.  Double it and it drops to 89%.  Triple it and you're at 76%.

In terms of combinatorics, as you increase the size of the deck (keeping the proportions the same), a smaller and smaller proportion of the possible starting hands has the cards that you need to kick off.  I've not yet quite wrapped my mind around why this should be the case in general.  I'm not sure if it's only due to having a fixed-size starting hand or if there are other combinatorics principles in play also.

The larger the deck you have, the more it becomes like a random walk.  Suppose that all the draw is from labs.  Draw a lab, that's one step forward; draw anything else, and it's one step back.  If the random walk ever reaches zero, then you dud.

So we have the question "What is the probability that a random walk will reach zero within a given number of steps?"  If your deck can exactly draw itself (not including the starting 5 cards), then the probability of dudding approaches 100%.  However, if you have a little bit of overdraw, the probability approaches something less than 100%.  (See this stack exchange question)

I'm happy to see that my comment inspired a bit of discussion (of the civil kind to boot, woop!). I had overlooked the effect of the starting hand. I had a gut sense that a random walk might be a useful way of modelling deck draw. I think I phrased my criterion in terms of number of cards drawn, not probability of drawing all the cards, which is different, but hey, it's still interesting that overdraw is necessary to get the dud probability below 100% in this model.
Logged

crj

• Jester
• Offline
• Posts: 786
• Respect: +901
Re: Dominion 101: What is an engine?
« Reply #56 on: October 19, 2017, 07:28:14 pm »
0

Yes, "engine" is Dominion-specific language.
The term engine is used in other games.
That's irrelevant.
Logged

JW

• Minion
• Offline
• Posts: 694
• Respect: +1229
Re: Dominion 101: What is an engine?
« Reply #57 on: October 19, 2017, 07:38:54 pm »
0

The larger the deck you have, the more it becomes like a random walk.  Suppose that all the draw is from labs.  Draw a lab, that's one step forward; draw anything else, and it's one step back.  If the random walk ever reaches zero, then you dud.

So we have the question "What is the probability that a random walk will reach zero within a given number of steps?"  If your deck can exactly draw itself (not including the starting 5 cards), then the probability of dudding approaches 100%.  However, if you have a little bit of overdraw, the probability approaches something less than 100%.  (See this stack exchange question)

I'm happy to see that my comment inspired a bit of discussion (of the civil kind to boot, woop!). I had overlooked the effect of the starting hand. I had a gut sense that a random walk might be a useful way of modelling deck draw. I think I phrased my criterion in terms of number of cards drawn, not probability of drawing all the cards, which is different, but hey, it's still interesting that overdraw is necessary to get the dud probability below 100% in this model.

If you can only draw the deck exactly, as it gets bigger and bigger your chance to draw the whole deck decreases towards zero. But a "dud" usually is used to mean a bad turn. Referring to any hand that does not draw the entire deck as a "dud" implies that a turn that doesn't draw the deck is bad. If you have a large deck and you draw almost all of it, that is probably a great turn. So the average number of (non-drawing) cards in hand in line with what you had initially proposed may be a better way to conceptualize the strength of deck.
Logged

trivialknot

• Minion
• Offline
• Posts: 578
• Respect: +908
Re: Dominion 101: What is an engine?
« Reply #58 on: October 19, 2017, 09:07:22 pm »
+1

The larger the deck you have, the more it becomes like a random walk.  Suppose that all the draw is from labs.  Draw a lab, that's one step forward; draw anything else, and it's one step back.  If the random walk ever reaches zero, then you dud.

So we have the question "What is the probability that a random walk will reach zero within a given number of steps?"  If your deck can exactly draw itself (not including the starting 5 cards), then the probability of dudding approaches 100%.  However, if you have a little bit of overdraw, the probability approaches something less than 100%.  (See this stack exchange question)

I'm happy to see that my comment inspired a bit of discussion (of the civil kind to boot, woop!). I had overlooked the effect of the starting hand. I had a gut sense that a random walk might be a useful way of modelling deck draw. I think I phrased my criterion in terms of number of cards drawn, not probability of drawing all the cards, which is different, but hey, it's still interesting that overdraw is necessary to get the dud probability below 100% in this model.

If you can only draw the deck exactly, as it gets bigger and bigger your chance to draw the whole deck decreases towards zero. But a "dud" usually is used to mean a bad turn. Referring to any hand that does not draw the entire deck as a "dud" implies that a turn that doesn't draw the deck is bad. If you have a large deck and you draw almost all of it, that is probably a great turn. So the average number of (non-drawing) cards in hand in line with what you had initially proposed may be a better way to conceptualize the strength of deck.
Yeah, that's a good point.  If you draw like a hundred cards out of two hundred, it's hard to see that as a dud.  Uh let's just call it an early termination.

By my reckoning, if you're overdrawing slightly, then the average number of cards you draw increases as O(N).  This is easy to prove, because as I already argued, there's a nonzero probability p of drawing everything.  So the average number of cards you draw is at least p*N.

On the other hand, if you have no overdraw, then the math is difficult.  After playing around with it for a while, I think it's still O(N).  Even if the probability of early termination approaches 1, it approaches 1 really really slowly.
Logged

Beyond Awesome

• Global Moderator
• Offline
• Posts: 2906
• Shuffle iT Username: Beyond Awesome
• Respect: +2404
Re: Dominion 101: What is an engine?
« Reply #59 on: November 06, 2017, 11:45:18 pm »
+2

Logged

JW

• Minion
• Offline
• Posts: 694
• Respect: +1229
Re: Dominion 101: What is an engine?
« Reply #60 on: November 07, 2017, 12:02:20 am »
+1

It would be great if when the article says "Cellar, Moat, Merchant, Village, Workshop, Militia, Remodel, Smithy, Market, Mine", you link to the pages for these cards on the Wiki so that the reader can easily find what these cards do.
Logged

Beyond Awesome

• Global Moderator
• Offline
• Posts: 2906
• Shuffle iT Username: Beyond Awesome
• Respect: +2404
Re: Dominion 101: What is an engine?
« Reply #61 on: November 07, 2017, 01:52:28 pm »
+4

It would be great if when the article says "Cellar, Moat, Merchant, Village, Workshop, Militia, Remodel, Smithy, Market, Mine", you link to the pages for these cards on the Wiki so that the reader can easily find what these cards do.

I will do that. I meant to add the hyperlinks but forgot.
Logged

• Explorer
• Offline
• Posts: 316
• Grand Market = cantrip Woodcutter
• Respect: +366
Re: Dominion 101: What is an engine?
« Reply #62 on: November 11, 2017, 05:02:33 pm »
0

If you have no overdraw, then the math is difficult.  After playing around with it for a while, I think it's still O(N).  Even if the probability of early termination approaches 1, it approaches 1 really really slowly.
Care to share the math? I would love to see it.

Related, is the following an engine board? At the end of the game, off of 5xLab, 6xWarehouse and 3xStables, Qvist can draw 37 cards (plus the starting 5) out of 49 total. This requires discarding 3xCopper and 18 cards of his choice (he has 5xColony, 3xEstate, 3xTunnel and 5 ruins, so that's 16 blanks). Adam's deck is similar. I lean towards saying yes, this is an engine, although a somewhat peculiar one.

Logged

trivialknot

• Minion
• Offline
• Posts: 578
• Respect: +908
Re: Dominion 101: What is an engine?
« Reply #63 on: November 11, 2017, 06:27:02 pm »
0

If you have no overdraw, then the math is difficult.  After playing around with it for a while, I think it's still O(N).  Even if the probability of early termination approaches 1, it approaches 1 really really slowly.
Care to share the math? I would love to see it.
Okay, here’s how I did it.  Suppose we have a balanced random walk starting from origin.  It will eventually either reach +n or -n, each with probability 1/2.  The expected number of steps required is O(n^2).

So let’s say that the random walk starts from position 5, and it terminates if it ever reaches 0.  Well there’s a 1/2 probability it will reach 10 first, and 1/2 probability it will reach 0 first, and this takes O(5^2) steps.  If it reaches 10 first, then after O(10^2) steps, it will either reach 0 or 20 first.  And if it reaches 20 first then we wait another O(20^2) steps, and so on.

So if we continue this process, the expected time before terminating is O(5^2) + O(10^2)/2 + O(20^2)/4 + ...  This series diverges..  So even though an engine without overdraw will eventually terminate in an infinite deck, the expected time to terminate is infinite.
Logged

• Explorer
• Offline
• Posts: 316
• Grand Market = cantrip Woodcutter
• Respect: +366
Re: Dominion 101: What is an engine?
« Reply #64 on: November 14, 2017, 02:49:00 pm »
0

Okay, here’s how I did [the math].
Nice, thanks

O(10^2) = O(1) but I know what you mean. Open questions, at least in my head: is the constant hidden by O(⋅) the same for all terms? Does it matter?
Logged

trivialknot

• Minion
• Offline
• Posts: 578
• Respect: +908
Re: Dominion 101: What is an engine?
« Reply #65 on: November 14, 2017, 03:31:52 pm »
0

O(10^2) = O(1) but I know what you mean. Open questions, at least in my head: is the constant hidden by O(⋅) the same for all terms? Does it matter?
Yeah that math notation is not really accurate.  I was on a mobile device at the time and trying to be brief.  My assertion that it takes O(n^2) implies that the constant hidden by O(⋅) converges to a constant for large n.  Although, I don't actually know how to prove the O(n^2) assertion.  I was just thinking in terms of a diffusive process, and thinking back to my statistical mechanics classes.

I think this is a fairly interesting problem that could probably be understood within the theory of phase transitions.  I just don't have the time to think it through.  Also, I'm skeptical of the relevance to Dominion anyway.  Real decks aren't infinite in size.
Logged

• Explorer
• Offline
• Posts: 316
• Grand Market = cantrip Woodcutter
• Respect: +366
Re: Dominion 101: What is an engine?
« Reply #66 on: November 14, 2017, 04:27:18 pm »
0

My assertion that it takes O(n^2) implies that the constant hidden by O(⋅) converges to a constant for large n.
I think you need Θ(⋯) for that.

Consider 1/(2^n): that's O(1), but sum(c for k ∈ ℕ) is divergent while sum(1/(2^k) for k ∈ ℕ) is not, where c is any non-zero constant.

Also, I'm skeptical of the relevance to Dominion anyway.  Real decks aren't infinite in size.
Sure. The context of this is me proposing that we use "draws O(1) cards" vs. "draws Θ(n) cards" to distinguish engines and non-engines. Just like money density math and computer simulations give very precise answers to somewhat wrong questions, my criterion would give a well-defined, rigorous and very precise criterion which would divide decks more-or-less-approximately between engines and non-engines.

The fact that the only infinite decks occur in thought experiments and the calculations in my math wouldn't make it bad at distinguishing between engines and non-engines. (Maybe something else, such as its low resolution, would.)

So, just because there are no infinite nails doesn't mean you can't hammer in the finite ones with the handle of my high-precision screwdriver
Logged

trivialknot

• Minion
• Offline
• Posts: 578
• Respect: +908
Re: Dominion 101: What is an engine?
« Reply #67 on: November 14, 2017, 08:44:49 pm »
0

I work in condensed matter physics, not math, so I'm not familiar with the distinction between O() and Θ().

Incidentally, the theory of phase transitions also assumes a system of infinite size.  Well say I have a cup of water, that's about 10^23 molecules, it's practically infinite, right?  And if you had a deck of 10^23 cards I think phase transition theory would apply there too.  I'm more skeptical about applying it to a deck of 20 cards.  But hey, 20 is still >> 1, so I maybe I'm being overly cautious.  I definitely don't think it applies to the 5-card golden deck though.
Logged

• Explorer
• Offline
• Posts: 316
• Grand Market = cantrip Woodcutter
• Respect: +366
Re: Dominion 101: What is an engine?
« Reply #68 on: November 15, 2017, 12:38:44 pm »
+1

I work in condensed matter physics, not math, so I'm not familiar with the distinction between O() and Θ().
I don't know that's it's taught in math curricula, but it's a staple of computer science.

O(⋅) is a set of functions (typically from ℕ to ℝ). f is in O(g) if there exists a c and an N such that for all n > N, f(n) ≤ c*g(n). Loosely speaking, g (eventually) grows faster than f.

Θ(⋅) is a set of functions. f is in Θ(g) if f is in O(g) and g is in O(f). They grow equally quickly.

Examples: n^k is O(n^(k+d)) for constant k and any d > 0. In particular, sqrt(n) is O(n) and n is O(n^2).

O(⋅) induces a weak partial ordering. Θ(⋅) is the corresponding equivalence relation ("both x ≤ y and y ≤ x").

It's useful for analyzing the time and space usage of algorithms in the abstract. If one e.g. sorting algorithm takes O(n log n) time and another takes O(n^2) time to sort n things, the latter might run faster on your computer than the former runs on mine, if your computer is a constant factor faster than mine and n is small enough, but this doesn't really show that the former isn't preferable. Ignoring that constant factor (in cases where it isn't relevant) is one motivation for using this concept.

(OTOH, constants matter. While Fibonacci heaps are useful for Dijkstra's shortest path—in theory, using O() analysis—in practice a bog standard left-packed-tree-in-an-array heap is faster, at least for data that all fits in memory simultaneously.)
Logged

• Herbalist
• Offline
• Posts: 9
• Respect: +21
Re: Dominion 101: What is an engine?
« Reply #69 on: November 16, 2017, 06:36:51 pm »
+3

So the math about a deck of exactly $n$ labs and $n$ coppers is wrong.  After playing around with this for awhile, it is $\Theta(\sqrt{n})$. Your argument that it is infinite in an infinite deck only implies that it is greater than $O(1)$, but not that it is necessarily $\Theta(n)$.

Here's a rough proof:
We can think of the ordering of the deck as a dyck path from $(0,0)$ to $(n,n)$, where going up represents drawing a lab, and going right represents drawing a copper. Falling below the diagonal is equivalent to terminating. Since there are ${2n \choose n}$ ways to shuffle the deck, and $C_n={2n \choose n}/(n+1)$ such paths that stay above the diagonal, so the propability of drawing the whole deck is $1/(n+1)$.

Now consider the probability of drawing any particular number of cards $2k$. First, there must have been exactly $k$ labs and $k$ coppers before that point, and they must be in an order that lets you draw all of them. The probability of there being exactly $k$ of each is $\Theta(1/k)$. This is because as long as $k$ is a little less than $n$, the draws are mostly independent, and thus look like a binomial distribution, which has standard deviation $\Theta(k)$. From the argument before about the whole deck, the probability that this intital segment is in the right order to draw all of it is $\Theta(1/k)$, which means the probability of drawing exactly $2k$ cards is $\Theta(1/k^{3/2)})$.

To find the EV, we thus sum up $\Theta(k/(k^{3/2}))$ for $k$ from 1 to $n$, to get $\Theta(\sqrt(n))$

I have also found explicit values up to $n=5000$ and they are definitely growing with $\sqrt{n}$
Logged

trivialknot

• Minion
• Offline
• Posts: 578
• Respect: +908
Re: Dominion 101: What is an engine?
« Reply #70 on: November 16, 2017, 07:17:40 pm »
+1

Since there are ${2n \choose n}$ ways to shuffle the deck, and $C_n={2n \choose n}/(n+1)$ such paths that stay above the diagonal, so the propability of drawing the whole deck is $1/(n+1)$.
Oh, sweet, you found an explicit formula.  I'm not sure how you found C_n, but I guess once you have it you can just prove it by induction.

Now consider the probability of drawing any particular number of cards $2k$. First, there must have been exactly $k$ labs and $k$ coppers before that point, and they must be in an order that lets you draw all of them. The probability of there being exactly $k$ of each is $\Theta(1/k)$.
Was this a typo where you meant $\Theta(1/\sqrt{k})$?  With this correction, I follow and agree with the rest of the argument.

So it appears that I was correct to say that the number of cards you draw diverges, but I was incorrect to say it was O(n).  That's funny, because earlier in the thread, people were wondering if there exists a "hybrid" deck where the number of cards you draw is more than Θ(1) but less than Θ(n).  The hybrid deck was right in front of us all along, in the form of an engine without overdraw.
Logged

• Herbalist
• Offline
• Posts: 9
• Respect: +21
Re: Dominion 101: What is an engine?
« Reply #71 on: November 21, 2017, 04:21:15 pm »
+1

Yes that was supposed to be $\Theta(1/\sqrt{k})$. C_n is just the catalan numbers.
Logged

• Torturer
• Offline
• Posts: 1520