Print

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

[tim17]

Consider a modification of (1 player) dominion, where supply piles are infinite (or if you don't believe in infinity, arbitrarily large). Suppose also that you start your turn with an n card deck, and all of those n cards are in your hand.

On certain boards, it is possible to construct such a scenario where you are able to generate arbitrarily many coins on your turn (e.g. a board with highway and villa (and n >=4), since you can play 4 highways and then buy and play arbitrarily many villas).

I want to only consider boards on which, for any positive n, the number of coins you can generate is bounded by some (finite) function of n (call it f(n)).

What's the largest achievable f(n)? Clearly you can get at least f(n)=5n (just have a hand with n platinums). However, you can certainly do much better than this. I'll break this up into 2 parts:

1. What's the best O() complexity achievable? Is it O(n^2), O(2^n), O(2^2^n)?

2. Can we also figure out the optimal constant?

I have some thoughts on 1, but probably one can do better than the best I've come up with. Feel free to let me know if you find any issues with my formulation.

[gkrieg13]

\Theta(n²) is easy just with banks.

[ThetaSigma12]

\Theta

You called?

[tim17]

For those interested, I'll outline my best idea with spoiler tags. The first tag contains the board. The second tag contains my approach and result.

Board contains:

Hermit
Bank
Villa
Counterfeit (or whatever nonterminal that gives at least 1 coin and +buy that you want)
Raid



Start your turn with a hand of \Theta(n) madmen, n/4 banks, n/2 silvers, and \Theta(n) counterfeits in hand.

1. Play silvers and counterfeits to get \Theta(n) buys and coins
2. Buy raid to gain n/2 silvers
3. Buy and play villa
4. Play 2 madmen to draw n/2 silvers
5. Play n/2 silvers
6. Buy raid to gain n silvers
7. Buy and play villa
8. Play 3 madmen to draw n silvers
9. Play n silvers
10. Buy raid to gain 2n silvers
11. Buy and play villa
12. Play 4 madmen to draw 2n silvers
...
Keep doing this until you run out of madmen, which will happen after \Theta(\sqrt(n)) iterations.  In total, your madmen
drew \Theta(n*2^(\sqrt(n))) silvers.

After playing all the silvers, play your n/4 banks, each worth \Theta(n*2^(\sqrt(n))) coins apiece.

This yields \Theta(n^2 * 2^(\sqrt(n))) coins overall.

I believe my analysis is correct. If you spot any mistakes, or think there's a way to generate an unbounded amount of coin on this board, feel free to comment. Also, of course feel free to expand on my idea to do better.

[singletee]

See also How high can you go

[majiponi]

On certain boards, it is possible to construct such a scenario where you are able to generate arbitrarily many coins on your turn (e.g. a board with highway and villa (and n >=4), since you can play 4 highways and then buy and play arbitrarily many villas).

Ferry on Villa, the only card you have in your hand is Quarry. n is any positive interger.

For those interested, I'll outline my best idea with spoiler tags. The first tag contains the board. The second tag contains my approach and result.

Very good. I tried another card, Storyteller, which was unsuccessful. It lets you infinite. Madman is good, since it limits. I haven't checked whole your solution, but this can let me notice a simple solution for N(n^3).

Hand: m Madmans, m Remakes, m-3 Market Squares, 2 Golds, 1 Necropolis (m=n/3)

play Necropolis
play Remake to trash 2 Golds to gain 2 Banks, reacting all Market Squares
play Madman to draw all
repeat until you have no Madman

Hand: (m^2-5m+2) Golds, 2m Banks
play all Treasures to earn (2m^3-5m^2-10m+6) coins

[singletee]

I think I can get Θ(2ⁿ)

Kingdom:
Scrying Pool
Workshop
Bridge
King's Court
Lost Arts
Training

Setup:
Training on Workshop
Lost Arts on King's Court

Initial hand:
2 KC, 2 Workshop, 1 Bridge, Θ(n) Scrying Pool

Method:
KC-KC-Bridge-Workshop-Workshop, which lowers KC to cost 4, and get 2 KCs and 4 Workshops.
Play Scrying Pool.
Now KC-KC-WS-WS-WS, WS, this time gaining 10 cards. As it turns out, the optimal thing to get is 4 KCs and 6 Workshops.
Play Scrying Pool.
Each iteration, the number of cards you can gain is 2x-2, where x is the number of cards you gained last time.
Continue in this way, until you've exhausted all Scrying Pools.
Since Workshops are Trained, the number of coins you get is the number of total Workshop plays, which is Θ(2ⁿ).

Edit: This can be improved by swapping out Workshop for Artisan, resulting in being able to put back Scrying Pools to gain things in hand, allowing us to start the first round with Θ(n) gains and thus Θ(n*2ⁿ) growth overall.

[Deadlock39]

I'm a bit confused. Is there a difference between this and the "how high can you go" Stef posted? Wouldn't the answer be whatever the big-O of the answer found there?

[singletee]

I'm a bit confused. Is there a difference between this and the "how high can you go" Stef posted? Wouldn't the answer be whatever the big-O of the answer found there?

No; the answer to Stef's question is a number. Here we need a function (of number of cards in starting hand). Also here's we're looking to produce lots of coins, not necessarily gain lots of cards. But I think any answer here is going to also involve gaining lots of cards.

[liopoil]

If we use some form of remake/fortress or something I assume that we could get \Theta(4^n) fairly easily. In fact I bet the base of the exponent can be even higher than that. Can we do better than just a constant raised to the n?

[Deadlock39]

I'm a bit confused. Is there a difference between this and the "how high can you go" Stef posted? Wouldn't the answer be whatever the big-O of the answer found there?

No; the answer to Stef's question is a number. Here we need a function (of number of cards in starting hand). Also here's we're looking to produce lots of coins, not necessarily gain lots of cards. But I think any answer here is going to also involve gaining lots of cards.

I guess I forgot that that was gains, but they produced most of those gains by using coins to buy Travelling Fair. You'd need to work it out again to optimize coins instead of gains, but they got up in the territory of 10^600 coins out of a standard 5 card starting hand right, so that would translate pretty directly to this. 

I'm mostly just saying, surely the solution that problem ended up with is also the best approach to this one?

[liopoil]

That problem started with a 5-card starting hand but an arbitrarily large deck. This one starts with a limited handsize of n and no deck at all. The only applicable part would be when we cash in for stef's problem, which isn't all that great really. Almost all of the work for that problem was in drawing as many cards as possible

I actually really like this problem. What we've done so far is show that for each card (scrying pool) in our hand we can double (or quadruple if we use remake I think) our handsize. I'd be very interested to see if it's possible to get some more powerful operation.

[liopoil]

Stonemasoning golems into scrying pools would probably let us bring the base of the exponent up to 8

[Deadlock39]

Okay, got it. I missed the no deck part.

[liopoil]

Ok, here's the highest exponent base I can get so far: O(168151ⁿ)

EDIT: Lurker allows infinite coins, but if I take lurker and hunting grounds out of the kingdom and just use stonemason, I get O(65536ⁿ)

Kingdom: Bridge, Fortress, Possession, Golem, Alchemist, Scrying Pool, Stonemason, King's Court, Hunting Grounds, Lurker
Events: Inheritance, Training

Setup: Inherit King's Court, train King's Court.

Hand: Fortress, Scrying Pool, 2x King's Court, Lurker, 2x Stonemason, n - 7 Possessions

Turn: Kc-Kc-Lurker-SM-SM, trashing 3 hunting grounds for 9 estates, 5 fortresses for 2 lurkers and 8 stonemasons, and one Possession for a golem and a scrying pool. Play scrying pool, draw it all.
7x Kc on: 2 lurkers to get 18 more Kc, 8 stonemasons for 33 more stonemasons, and 13 more lurkers, and a pool and an alchemist from the golem, then draw them all with pool. Now I have ~40 spare KC plays...

...and so on. The general plan is:

Have n KC plays, ~3n/4 stonemasons, ~n/4 lurkers. Get ~9n/4 KCs from the lurkers. The stonemasons give 9n/2 gains, which I use for ~27n/8 stonemasons and ~9n/8 lurkers. If I have one scrying pool in hand, trash an alchemist for two scrying pools. If I have two scrying pools in hand and no alchemists, trash a golem for two alchemists. If I have two scrying pools and an alchemist but no golem, then trash a possession for two golems. Otherwise, don't bother. Then play a scrying pool.

I now have ~9n/2 KC plays and the correct proportion of stonemasons and lurkers. Repeat. In the end, I get to play 8n - 60 scrying pools (After the first few rounds, I will be getting the full 8 pools from each possession), and each time the number of King's Courts multiplies by 4.5 . I lose a little bit by forced inefficiencies and having to stonemason for pools sometimes, but that won't effect much. So I can get at least O(4.5^{8n - 60}) ~ O(168151ⁿ) KC plays and so that many coins too.

My original plan was more complicated than this and involved develop lots of other crazy stuff, but I doubt it would have done much better. I bet this can still be very significantly improved though. I like how this just mainly uses lurkers, stonemasons, and estates, which all cost . Also, is the number of different cards in the kingdom a limitation? I was at one point considering setting up a ridiculous number of cards in the trash that would be an exponential function of n before starting for lurker to get... would this be allowed?

The base of the exponent here is 4.5⁸, because I can get ~8n pools and 4.5 gains/card. In particular, 12 cards (4 KCs, 6 SMs, and 2 lurkers) can gain 54 cards (18 KCs, 27 SMs, and 9 lurkers)... is it possible to improve this ratio or the number of pools? I guess we just need a card costing

The title of this thread is interesting... I don't think busy beaver will be exactly attainable here...

[singletee]

Ok, here's the highest exponent base I can get so far: O(168151ⁿ)

Kingdom: Bridge, Fortress, Possession, Golem, Alchemist, Scrying Pool, Stonemason, King's Court, Hunting Grounds, Lurker
Events: Inheritance, Training

Setup: Inherit King's Court, train King's Court.

Hand: Fortress, Scrying Pool, 2x King's Court, Lurker, 2x Stonemason, n - 7 Possessions

Turn: Kc-Kc-Lurker-SM-SM, trashing 3 hunting grounds for 9 estates, 5 fortresses for 2 lurkers and 8 stonemasons, and one Possession for a golem and a scrying pool. Play scrying pool, draw it all.
7x Kc on: 2 lurkers to get 18 more Kc, 8 stonemasons for 33 more stonemasons, and 13 more lurkers, and a pool and an alchemist from the golem, then draw them all with pool. Now I have ~40 spare KC plays...

...and so on. The general plan is:

Have n KC plays, ~3n/4 stonemasons, ~n/4 lurkers. Get ~9n/4 KCs from the lurkers. The stonemasons give 9n/2 gains, which I use for ~27n/8 stonemasons and ~9n/8 lurkers. If I have one scrying pool in hand, trash an alchemist for two scrying pools. If I have two scrying pools in hand and no alchemists, trash a golem for two alchemists. If I have two scrying pools and an alchemist but no golem, then trash a possession for two golems. Otherwise, don't bother. Then play a scrying pool.

I now have ~9n/2 KC plays and the correct proportion of stonemasons and lurkers. Repeat. In the end, I get to play 8n - 60 scrying pools (After the first few rounds, I will be getting the full 8 pools from each possession), and each time the number of King's Courts multiplies by 4.5 . I lose a little bit by forced inefficiencies and having to stonemason for pools sometimes, but that won't effect much. So I can get at least O(4.5^{8n - 60}) ~ O(168151ⁿ) KC plays and so that many coins too.

My original plan was more complicated than this and involved develop lots of other crazy stuff, but I doubt it would have done much better. I bet this can still be very significantly improved though. I like how this just mainly uses lurkers, stonemasons, and estates, which all cost . Also, is the number of different cards in the kingdom a limitation? I was at one point considering setting up a ridiculous number of cards in the trash that would be an exponential function of n before starting for lurker to get... would this be allowed?

The base of the exponent here is 4.5⁸, because I can get ~8n pools and 4.5 gains/card. In particular, 12 cards (4 KCs, 6 SMs, and 2 lurkers) can gain 54 cards (18 KCs, 27 SMs, and 9 lurkers)... is it possible to improve this ratio or the number of pools? I guess we just need a card costing

The title of this thread is interesting... I don't think busy beaver will be exactly attainable here...

This kingdom can go infinite (particularly, the combination of Training, Inherited King's Courts, Hunting Grounds, and Lurker):

Estate1
   Estate2
      Lurker1 trashing HG, gaining 3 Estates
      Lurker1 gaining HG
      Lurker1 trashing Lurker
   Estate2
      Lurker2 gaining Lurker
      Lurker2 trashing Lurker
      Lurker2 gaining Lurker
   Estate2
      HG1 drawing 4 cards
      HG1 drawing 2 cards
      HG1 drawing nothing
(Repeat)

Scrying Pools are also Lurkable, so that could go infinite as well.

Stonemasoning Possession->Golem->Scrying Pool is great, but I think including Lurker will inevitably enable unlimited gaining of cards that you want to limit.

[liopoil]

Ah! Darn, lurker is too powerful. What if I just use stonemason to gain two estates at a time? Then I have 1 KC and 2 Stonemasons gain 4 KC and 8 Stonemasons, so I think that I can get 4⁸ⁿ = 65536ⁿ.

[JacquesTheBard]

Does the +$ token from Training apply to Inherited Estates? I thought they didn't.

[liopoil]

Does the +$ token from Training apply to Inherited Estates? I thought they didn't.

Ok, then just train stonemason instead, doesn't change anything

[trivialknot]

This isn't quite a solution, but does better than exponential:

Use n cards to generate O(n^2) coins.  Play Storyteller, draw O(n^2) new cards.  Now you use those cards to generate O(n^4) coins.  So on and so forth.  The idea is that you're limited by the number of storytellers in your starting hand, so you can only generate O(n^(2^n)) coins.

Generating O(n^2) coins is easy.  Say Beggar + Miser.  And Throne Room for actions.

The problem is you need unlimited gains, but somehow be blocked from gaining Storytellers.  There's gotta be a way, right?

BTW, is the idea that it's impossible to generate infinite money given the kingdom, or impossible to generate infinite money given the game-state at the start of the turn?

[liopoil]

Generating the coins should be easy, but you also have to gain n^2 non-storyteller cards with just n cards. I have no idea how that could be done.

I think the idea is that given the kingdom you can't set up a turn that gets an unbounded number of coins.

[faust]

A way to not be able to gain Storytellers:

Storyteller is a Black Market card (not sure what the rules are for these here). You only have one and canot buy more. In order to play > 1 Storyteller, you have to call Royal Carriages, which you can only do directly after playing Storyteller, so unless there's Crown, you cannot use additional gained RCs to play Storyteller more often.

The problem with this approach is that you have to do all your gaining and money-producing with Treasure cards, which is probably not powerful enough.

[luser]

You could relatively easily get something like 2^2^n I am not sure what exactly.

You need tfair, chapel, peasant, page, scrying pool, watchtower. As optimal coins is hard lets do easy estimate.

Drawing deck is easy as its only actions and you topdeck last discipled poll to draw it.

At i-th round you start with x coins. With tfair you could buy x/4 peasants. Next turn just turn them into x/4 soldiers. They give x^2 coins next turn and bound 2^2^n follows.

[faust]

Here's a strategy to gain an arbitrarily large amount of actions costing $5 or less. This would make the upper limit depend only on how much you can draw:


Ferry on Hunting Grounds, inherited Catacombs.

Put 2 Quarries in play (Black Market). Play Baron with Watchtower in Hand. You can now do the following:

Trash the gained Estate.
  trigger Catacombs on trash - gain card costing less than Estate (which is now in the trash and thus no longer an action, i.e. it costs $2)
  gain Hunting Grounds (which costs $0)
  trash Hunting Grounds, gaining 3 Estates.
  trash Estate 1 & 2, gaining any actions costing $5 or less
 trash Estate 3, gain Hunting Grounds, repeat.


An issue is that you have to limit actions. A Village added to this would allow you to draw an arbitrarily large amount of cards.

[faust]

You could relatively easily get something like 2^2^n I am not sure what exactly.

You need tfair, chapel, peasant, page, scrying pool, watchtower. As optimal coins is hard lets do easy estimate.

Drawing deck is easy as its only actions and you topdeck last discipled poll to draw it.

At i-th round you start with x coins. With tfair you could buy x/4 peasants. Next turn just turn them into x/4 soldiers. They give x^2 coins next turn and bound 2^2^n follows.

I believe we are looking for a solution that only uses a single turn.