Dominion Strategy Forum

Please login or register.

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

Author Topic: Asymptotic Dominion: Asking all Nth turn puzzles at once  (Read 8839 times)

0 Members and 1 Guest are viewing this topic.

wuthefwasthat

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 48
  • Respect: +151
    • View Profile
    • The Dominion section of my blog
Asymptotic Dominion: Asking all Nth turn puzzles at once
« on: August 19, 2012, 08:19:08 pm »
+5

We often ask, "What is possible in N turns?"  But we restrict ourselves to small N, because it's no fun to reason the details out about larger N.  Even at N=5, while solutions are full of ideas, details become tedious to work out.  But we can make large N interesting too.  In fact, this puzzle is about N approaching infinity.

Let's consider the function f where f(N) is the maximum number of points it's possible to have at the end of turn N, in a game of Solitaire Dominion.  A few tweaks are required to make this interesting:
  • We care about asymptotic lower bounds, rather than exact ones.  After all, it's no fun to reason about exact details for large N, and this makes different bounds more comparable.  (Although in theory we can still get incomparable solutions, in practice we won't.)  You may want to know a bit of math:  http://en.wikipedia.org/wiki/Big_O_notation.  But the intuition is just that solution A is better than solution B if it eventually gets more points than solution B, i.e. it outgrows it in the long run.
  • It's no fun to play an unbounded number of turns with bounded piles.  (Otherwise, the best solution obviously uses some combination of Monument, Goons/Ambassador, and Bishop/Graverobber/Rogue, and the function is linear and annoying to work out details for.)  Thus let's say each Kingdom pile has infinitely many copies of each card.  (Unfortunately, the Black Market deck only makes sense being finite.)  I'll call this game Asymptotic Dominion. 
  • Lastly, while we're breaking the rules of the game, why limit to 10 piles?  This is a constraint which often gets in the way of interesting ideas.  Let's instead consider the puzzle for entire sets of expansions.
Thus, in Asymptotic Dominion, what is the best lower bound you can prove for f(N), where the set of cards is:
  • Base set
  • Base set + Intrigue + Seaside
  • Base set + Intrigue + Seaside + Alchemy, no Possession
  • Base set + Intrigue + Seaside + Alchemy + Prosperity, no Possession
  • All cards, no Possession or King's Court (Possession isn't in the Black Market deck either.)
Hints: 
  • Even with base set only, it's possible to do far better than Omega(N^2), or even Omega(N^1000).  Some intuition, for all the non-mathematicians:  A "Golden deck" gets only Omega(N), since it gets a fixed number of points per turn.  A deck that Islands a Gardens every few turns gets Omega(N^2) points, since you'll have Omega(N) Gardens and Omega(N) cards. 
  • Numbers 4 and 5 are the easiest puzzles, especially number 4.  An optimal solution for number 5 has essentially been discussed already elsewhere on the boards!
  • Average case is equivalent to worst case, for all of these, except for Base set only.
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #1 on: August 19, 2012, 08:24:03 pm »
0

Logged

theory

  • Administrator
  • *****
  • Offline Offline
  • Posts: 3603
  • Respect: +6121
    • View Profile
    • Dominion Strategy
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #3 on: August 19, 2012, 08:30:58 pm »
0

Some methods for 4/5 can be derived from the "infinitely-many" cards thread: just put a Gardens in your deck, then gain as many cards as you like on a turn to gain an unbounded number of points. In the first post, I gave a solution with KC and one without KC.
Logged

wuthefwasthat

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 48
  • Respect: +151
    • View Profile
    • The Dominion section of my blog
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #4 on: August 19, 2012, 08:39:53 pm »
+2

This guy was writing about these things: http://globofthoughts.wordpress.com/2012/07/08/asymptotics-of-resource-unbounded-dominion-solutions/

That guy is me.  I originally posted this on boardgamegeek forums, before I knew about this forum.  Of course, you guys are way more awesome (with an explicit puzzle sub-forum and all), so I was hoping people here would find this more interesting!

But... now you all know where to find solutions.  Should I take them down?  It is instructive to look at the solution for Base set only though, to get a handle of what is going on.

Cool puzzle. This thread is somewhat related.

Some methods for 4/5 can be derived from the "infinitely-many" cards thread: just put a Gardens in your deck, then gain as many cards as you like on a turn to gain an unbounded number of points. In the first post, I gave a solution with KC and one without KC.

Ah, I hadn't seen those threads before.  Definitely relevant, and indeed that works for #4.  And the thread has hints at how to solve #5. 

Edit:  The thread says how to solve #5 as well.  In fact, it doesn't even need Dark Ages. 
« Last Edit: August 19, 2012, 11:27:29 pm by wuthefwasthat »
Logged

razorborne

  • Bishop
  • ****
  • Offline Offline
  • Posts: 100
  • Respect: +8
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #5 on: August 19, 2012, 09:09:33 pm »
+1

Ah, I hadn't seen those threads before.  Definitely relevant, and indeed that works for #4.  And the thread has hints at how to solve #5.
I'd say it more than gives hints on #5. if the 8 green cards the non-KC solution calls for are all gardens, then #5 is solved as "infinite points per turn". and if you assume perfect shuffle luck, then I can just get right back up to that set-up next turn with my infinite crossroads. and, with a slight adjustment, it can get infinite gardens too. just add in a throne room, a procession, an ironworks, and a workshop. throne room the procession, use the first procession to play the ironworks, gaining throne room and procession, trashing it to gain who cares. then use the second procession to play workshop, gaining workshop and gardens, trashing it to gain an ironworks. if you increase the number of starting green cards in your hand to 13, you can then still draw up all the cards you got and end the turn with infinite gardens, each worth infinite points. you can also replace the gardens with silk roads for the same result. this even nets you an action each iteration.
Logged

RiemannZetaJones

  • Thief
  • ****
  • Offline Offline
  • Posts: 90
  • Respect: +62
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #6 on: August 19, 2012, 09:18:21 pm »
+2

Some methods for 4/5 can be derived from the "infinitely-many" cards thread: just put a Gardens in your deck, then gain as many cards as you like on a turn to gain an unbounded number of points. In the first post, I gave a solution with KC and one without KC.

There is now the much simpler approach of Rats.
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #7 on: August 19, 2012, 09:21:16 pm »
0

Some methods for 4/5 can be derived from the "infinitely-many" cards thread: just put a Gardens in your deck, then gain as many cards as you like on a turn to gain an unbounded number of points. In the first post, I gave a solution with KC and one without KC.

There is now the much simpler approach of Rats.
True! Provided your Gardens is on an Island. :)
Logged

ycz6

  • Minion
  • *****
  • Offline Offline
  • Posts: 676
  • Respect: +412
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #8 on: August 19, 2012, 10:11:41 pm »
0

Some methods for 4/5 can be derived from the "infinitely-many" cards thread: just put a Gardens in your deck, then gain as many cards as you like on a turn to gain an unbounded number of points. In the first post, I gave a solution with KC and one without KC.

There is now the much simpler approach of Rats.
True! Provided your Gardens is on an Island. :)
Rats/Fortress will also do the job.
Logged

wuthefwasthat

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 48
  • Respect: +151
    • View Profile
    • The Dominion section of my blog
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #9 on: August 19, 2012, 11:18:33 pm »
0

So it looks like infinite is possible using everything up to Hinterlands* (including Promo), with Black Market, Horn of Plenty, Mandarin, and Crossroads being key cards.  Very amusing combo.  I'm guessing it's still an interesting question to go up to only Cornucopia*?  And wow, it sure does become super easy with Dark Ages... You can tell I hadn't thought much about the newer cards.  The origin of this puzzle goes back to pre-Cornucopia days...

*Excluding King's Court and Possession
Logged

ycz6

  • Minion
  • *****
  • Offline Offline
  • Posts: 676
  • Respect: +412
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #10 on: August 21, 2012, 01:10:03 am »
0

This guy was writing about these things: http://globofthoughts.wordpress.com/2012/07/08/asymptotics-of-resource-unbounded-dominion-solutions/
"This guy" and wuthefwasthat are the same person. Just thought I'd mention.
Logged

pst

  • Minion
  • *****
  • Offline Offline
  • Posts: 584
  • Respect: +906
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #12 on: August 21, 2012, 04:58:41 am »
0

5. All cards, no Possession or King's Court (Possession isn't in the Black Market deck either.)[/li][/list]

Easier to just say that BM also is excluded, because what would be in the BM deck when all cards are in play anyway? :-)
Logged

pst

  • Minion
  • *****
  • Offline Offline
  • Posts: 584
  • Respect: +906
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #13 on: August 21, 2012, 04:59:52 am »
0

Easier to just say that BM also is excluded, because what would be in the BM deck when all cards are in play anyway? :-)

Unless of course you just need it for the play-treasures-before-your-buy-phase function. Hm.
Logged

Qvist

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2400
  • Shuffle iT Username: Qvist
  • Respect: +4085
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #14 on: August 21, 2012, 05:10:27 am »
0

This guy was writing about these things: http://globofthoughts.wordpress.com/2012/07/08/asymptotics-of-resource-unbounded-dominion-solutions/

Hm, am I missing something, but he assumes 6 card hands (with Base) and 7 card hands (with Base+Intrigue)? So I'm not sure how this is possible.

wuthefwasthat

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 48
  • Respect: +151
    • View Profile
    • The Dominion section of my blog
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #15 on: August 21, 2012, 05:26:33 am »
+2

Unless of course you just need it for the play-treasures-before-your-buy-phase function. Hm.
Yup, that's why I worded it that way.

Hm, am I missing something, but he assumes 6 card hands (with Base) and 7 card hands (with Base+Intrigue)? So I'm not sure how this is possible.
You're not sure how it's possible to get 6 and 7 card hands?   Laboratory  :P

Nobody said you had to start the turn with those hands.
Logged

Ozle

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3625
  • Sorry, this text is personal.
  • Respect: +3360
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #16 on: August 21, 2012, 06:13:24 am »
0

I don't even understand the question!

However, I'm worried that if you give CC infinite turns he may actually break some laws of physics or something using just Dominion cards!
Logged
Try the Ozle Google Map Challenge!
http://forum.dominionstrategy.com/index.php?topic=7466.0

Sullying players Enjoyment of Innovation since 2013 Apparently!

Qvist

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2400
  • Shuffle iT Username: Qvist
  • Respect: +4085
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #17 on: August 21, 2012, 06:54:14 am »
0

Ok, but with a hand of TR+TR+TR+TR+WS+WS+WS+CR you get 4 cards per turn: 1+3/4+(3/4)^2 ... = 4
So, this is 16^n points, isn't it?

wuthefwasthat

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 48
  • Respect: +151
    • View Profile
    • The Dominion section of my blog
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #18 on: August 21, 2012, 02:24:21 pm »
+1

Ok, but with a hand of TR+TR+TR+TR+WS+WS+WS+CR you get 4 cards per turn: 1+3/4+(3/4)^2 ... = 4
So, this is 16^n points, isn't it?

(It gets you 6, of 8, yes.)  The problem is you can't Workshop for Council Room, so you'd need to fit in Remodel or something like that.  So then we need Bridge... but Intrigue can do better anyways, with a 6/7 ratio!
Logged

Qvist

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2400
  • Shuffle iT Username: Qvist
  • Respect: +4085
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #19 on: August 21, 2012, 03:56:03 pm »
0

Ok, but with a hand of TR+TR+TR+TR+WS+WS+WS+CR you get 4 cards per turn: 1+3/4+(3/4)^2 ... = 4
So, this is 16^n points, isn't it?

(It gets you 6, of 8, yes.)  The problem is you can't Workshop for Council Room, so you'd need to fit in Remodel or something like that.  So then we need Bridge... but Intrigue can do better anyways, with a 6/7 ratio!

Ah, right. Council Room costs $5. Ok, that makes sense. I will still see if I can beat any of these.

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #20 on: August 21, 2012, 04:20:27 pm »
0

Crossroads can maybe be subbed for Scrying Pool in the solution on the blog. The analysis becomes annoying though (because you need O(log x) Crossroads to draw your deck, then one Crossroads per batch of new cards, and then you need some amount of new ones). So there might be some loss in the goodness of the solution.

Crossroads and Scrying Pool are AFAIK the only way to draw a non-constant amount of cards.
« Last Edit: August 21, 2012, 04:22:00 pm by blueblimp »
Logged

eHalcyon

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 8689
  • Respect: +9187
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #21 on: August 21, 2012, 04:22:50 pm »
0

Crossroads can maybe be subbed for Scrying Pool in the solution on the blog. The analysis becomes annoying though (because you need O(log x) Crossroads to draw your deck, then one Crossroads per batch of new cards, and then you need some amount of new ones). So there might be some loss in the goodness of the solution.

Crossroads and Scrying Pool are AFAIK the only way to draw a non-constant amount of cards.

Scout and Apothecary are non-constant, but bounded.
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #22 on: August 21, 2012, 04:29:11 pm »
0

Crossroads can maybe be subbed for Scrying Pool in the solution on the blog. The analysis becomes annoying though (because you need O(log x) Crossroads to draw your deck, then one Crossroads per batch of new cards, and then you need some amount of new ones). So there might be some loss in the goodness of the solution.

Crossroads and Scrying Pool are AFAIK the only way to draw a non-constant amount of cards.

Scout and Apothecary are non-constant, but bounded.
Yeah sorry, I was using "non-constant" is the sense of "not O(1)".
Logged

jomini

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1060
  • Respect: +766
    • View Profile
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #23 on: August 22, 2012, 12:20:37 am »
+2

BB:
Quote
Crossroads and Scrying Pool are AFAIK the only way to draw a non-constant amount of cards.

No, there are several others. Counting house lets you draw any number of coppers. This isn't so hot, but when coupled with another non-constant drawer, cellar, it can make Chou an extremely powerful draw card.

Chou (draw 12 coppers from discard) -> cellar (discard 12 coppers & draw 12 cards)

You can go arbitrarily high. A fun way to cycle madly is to discard your deck, play counting house, and then cellar.

Madman now also allows you to draw a variable number of cards.

None of these should be bounded.
Logged

wuthefwasthat

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 48
  • Respect: +151
    • View Profile
    • The Dominion section of my blog
Re: Asymptotic Dominion: Asking all Nth turn puzzles at once
« Reply #24 on: August 22, 2012, 01:40:08 am »
0

Crossroads can maybe be subbed for Scrying Pool in the solution on the blog. The analysis becomes annoying though (because you need O(log x) Crossroads to draw your deck, then one Crossroads per batch of new cards, and then you need some amount of new ones). So there might be some loss in the goodness of the solution.

Crossroads doesn't make the solution any worse, but indeed the analysis is a bit annoying, which is why I don't mention it.  Let me sketch a proof (feel free to PM me about details):

Suppose with a hand of x, we can gain c*x cards, where c < 1.  We're aiming for a multiplicative factor of k=1/(1-c) each turn. 

First, we prove that instead of going from x to kx, we go to kx - O(log^3(x)).  In fact, kx - O(log^2(x)) if you're careful on the analysis. 
To do this, let S_i be the number of cards we have at iteration i.  So S_0 = x, and S_(i+1) = c S_i - log(S_i).  We want to lower bound sum_i=0...log(x) S_i.  Show by induction that S_i >= c^i x - i log(x).  The result follows from that.  You'll have to use the fact that the S_i are decreasing, so S_i <= x. 

So does x still grow as k^n?  We're now interested in the recurrence for number of cards per turn, T_i = k T_(i-1) - log^2(T_(i-1)).  Similar recurrence, but slightly harder since the terms are growing.  Prove by induction that T_i >= k^i - (i-1)^3 * (k^(i-1) + k^(i-2) ... + 1) * log^3(k).  The proof is just a bunch of algebra.  For k > 2 (actually, it's sufficient to have k-1>log^3(k)), this is dominated by the k^i term for large i, so we have that T_i = Omega(k^i), as desired.

Okay, so this basically proves it, except that there's a Crossroads specific detail we're ignoring.  In order for O(log x) Crossroads to draw the deck, a constant fraction of our deck has to be Victory cards!  Luckily, this analysis doesn't care what the base of the log is.  This means it doesn't matter what the density of the Victory cards are: as long as it's any constant fraction, Crossroads is good enough to get the exact same result.  So we've in fact proven that Crossroads can get (k - epsilon)^i, for any epsilon. 

But truly getting k^i is not any harder.  Just have O(sqrt(n)) Victory cards and O(sqrt(n)) Crossroads, or something like that.  The analysis is no harder than what I just did.


Similar analysis, by the way, shows that when you have Seaside, you can use Caravans/Wharves to smooth out variance and get probability 1.  But it's easier and nicer to describe using Haven, put-back cards (e.g. Courtyard, Mandarin), or discard-and-draw-tricks. 

Crossroads and Scrying Pool are AFAIK the only way to draw a non-constant amount of cards.

I realize Jomini has noted some of these things, but, just to be exhaustive:  Scrying Pool, Crossroads, and Madman all draw unboundedly many cards.  Technically, Cellar, Storeroom, and Library can also draw arbitrarily many cards, although they don't increase your hand size arbitrarily.  I suspect arbitrary hand-size increase is closer to what we care about, in which case Native Village and Counting House work.  Lastly, Apprentice deserves honorable mention because its text doesn't preclude it from drawing arbitrarily many cards, and it's possible for this to happen with introduction of new cards. 

*Technically, a single play of Forge or Count could cause an unbounded hand-size increase, with Cultists in hand, but this is less interesting since it ultimately requires a linear number of cards to draw.  With infinite players, a Jester+Watchtower can also gain us infinitely many Fortresses in hand...
« Last Edit: August 22, 2012, 02:00:27 am by wuthefwasthat »
Logged
Pages: [1] 2  All
 

Page created in 0.142 seconds with 20 queries.