Print

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

[tim17]

Suppose you're playing a game of dominion where the kingdom piles are infinite instead of their usual size (and therefore the game never ends). The puzzle is to come up with a strategy that yields the best score as a function (f) of n, the number of turns played so far. Since I believe it's possible to score an unbounded number of points in a single turn on some boards, I want to restrict to only boards where the number of points that can be scored on the nth turn is bounded by a function of n (i.e. no infinite points in a single turn). Ideally, I'd like solutions to work regardless of shuffle luck.

To give a simple example, suppose you opened monument/donate, and then just played monument every turn for the rest of forever. On the nth turn, you would have n-2 points, so in this case f(n) = n-2 = O(n).

To do slightly better, suppose that you trashed down to a golden deck of bishop, silver, silver, gold, province, and trashed the province, buying a new one each turn. This would yield f(n) ~= 5n

It's not too hard to do better than linear in n, but I'm not sure quite how well you can do. I'll add the best that I've come up with so far after not too much thought in spoiler tags below, and leave it up to anyone interested to go crazy with this.

I was thinking about solo games, but feel free to try with 2 players if you think that would help (maybe you can do something with possession).

See also Busy Beaver amount of Coin and How high can you go for similar puzzles.

Function:

f(n) =O(n!)

Strategy: (I don't think this board allows infinite points in a turn, but I haven't thought it through enough to be fully confident.)

Have a vineyard on your island mat, and have a deck containing the following:

2 schemes
2 treasuries
2 scrying pools
potion
k ironworks

turn:

1. start with 2 treasuries, 2 scrying pools, and something else in hand
2. play scrying pools to draw the deck
3. play k ironworks to gain k ironworks
4. play treasuries
5. play schemes
6. play potion
7. buy scrying pool
8. Topdeck 2 pools with schemes, and 2 treasuries

You had roughly k actions at the beginning of the turn, now you have roughly 2k actions, for twice as many vineyard points. Next turn, you'll be able to play the 2k ironworks to gain 2k ironworks, and then play the extra scrying pool to play those 2k ironworks to gain another 2k, giving you roughly 6k ironworks in total (and buying another scrying pool). Doing this for n turns will yield O(n!*k) points, hence the value of f(n).


Perhaps one can do (asymptotically) better on this board, I just wanted to come up with something that did reasonably well. Feel free to come up with something better.

[liopoil]

Claim 1: It's possible to convert x coins into O(x) points.

An easy way to do this is if your deck has one gardens in it and you buy a masterpiece, you get (x - 3)/10 points. I'm sure there are many more efficient and maybe simpler examples.

Claim 2: You can pretty much always get a specific n-card deck within ~n turns.

This is really easy. Just buy the cards you want and trash the rest.

So take ~n turns to get a deck consisting of the ~n cards you need for the royal carriage-city quarter-crossroads solution to the "busy beaver amount of coins" thread. Then on the last turn go crazy for around 2 ↑↑↑ n points.

Not fully fleshed out, but hopefully it's convincing enough that you can believe that triple arrows can be done. With the extra flexibility in this puzzle I wouldn't be totally shocked if a fourth arrow could be added or something, though.

EDIT: The solution to the busy beaver puzzle involved being able to gain arbitrarily many cards costing less than 5, which is no good here. Hmm, this is another good puzzle...

[majiponi]

Kingdom: Chapel, Stonemason, Scrying Pool, Scheme, Fortress, Gardens, Islands, Poacher
Event: Lost Arts

Setup:
put a Garden on your Island Mat
put your +1 Action token on the Stonemason Supply pile
have 2 Scrying Pools in hand
(Your deck has Chapel, Stonemason, 2 Scrying Pools, 2 Schemes, Fortress, 4 Poachers and Potion)

Turn 1
play 2 Schemes, 2 Scrying Pools, 4 Poachers
play 1 Stonemason to trash Fortress to gain 2 Stonemasons
buy Stonemason overpaying $2P to gain 2 Scrying Pools
topdeck 2 Scrying Pools

Turn 2
play 2 Schemes, 2 Scrying Pools, 4 Poachers
play 4 Stonemasons to trash Fortress to gain 8 Stonemasons
play Scrying Pool
play 8 Stonemasons to trash Fortress to gain 16 Stonemasons
play Scrying Pool
play 16 Stonemasons to trash Fortress to gain 32 Stonemasons
buy Stonemason overpaying $2P to gain 2 Scrying Pools
topdeck 2 Scrying Pools
...

On n-th turn, you can multiply (4^n)-1 on your score.

[Holger]

Kingdom: Chapel, Stonemason, Scrying Pool, Scheme, Fortress, Gardens, Islands, Poacher
Event: Lost Arts

Setup:
put a Garden on your Island Mat
put your +1 Action token on the Stonemason Supply pile
have 2 Scrying Pools in hand
(Your deck has Chapel, Stonemason, 2 Scrying Pools, 2 Schemes, Fortress, 4 Poachers and Potion)

Turn 1
play 2 Schemes, 2 Scrying Pools, 4 Poachers
play 1 Stonemason to trash Fortress to gain 2 Stonemasons
buy Stonemason overpaying $2P to gain 2 Scrying Pools
topdeck 2 Scrying Pools

Turn 2
play 2 Schemes, 2 Scrying Pools, 4 Poachers
play 4 Stonemasons to trash Fortress to gain 8 Stonemasons
play Scrying Pool
play 8 Stonemasons to trash Fortress to gain 16 Stonemasons
play Scrying Pool
play 16 Stonemasons to trash Fortress to gain 32 Stonemasons
buy Stonemason overpaying $2P to gain 2 Scrying Pools
topdeck 2 Scrying Pools
...

On n-th turn, you can multiply (4^n)-1 on your score.

That's great. I think you can even multiply your score by about (2^N)^n each turn for any number N by a modification of your method: Replace Poacher by Market and increase the (initial) number of potions (and thus Scrying Pools necessary to draw your deck), Schemes and Markets sufficiently so that you can gain N more Scrying Pools at the end of each turn by buying N/2 overpaid Stonemasons.

[luser]

I have better f(n)= 2^2^2^(O(n) times) kingdom kc, workshop, city quarter, training, tfair, bridge, gardens.  Deck contains starting cards one gardens, rest are action. Training on workshop

Turn starts by drawing deck with log(d) cq where d is deck size, play kc-bridge. Then you start multiplying workshops/kc. Assume that deck has k kc and k workshops. play k/2 kc on k/2 workshops to gain 3/4k workshops and 3/4k kc then play cq to draw these and repeat by number of cq in deck. If you start with 3 kc and 3 workshops and l cq you will end with 2^l workshops. Coins from training allow you to buy 2^l/10 cq which shows that f(n+1)>=2^f(n) and bound follows.

[tim17]

I have better f(n)= 2^2^2^(O(n) times) kingdom kc, workshop, city quarter, training, tfair, bridge, gardens.  Deck contains starting cards one gardens, rest are action. Training on workshop

Turn starts by drawing deck with log(d) cq where d is deck size, play kc-bridge. Then you start multiplying workshops/kc. Assume that deck has k kc and k workshops. play k/2 kc on k/2 workshops to gain 3/4k workshops and 3/4k kc then play cq to draw these and repeat by number of cq in deck. If you start with 3 kc and 3 workshops and l cq you will end with 2^l workshops. Coins from training allow you to buy 2^l/10 cq which shows that f(n+1)>=2^f(n) and bound follows.

More or less. I guess you want to have k/3 kc and 2k/3 workshops to gain 2k/3 kc and 4k/3 workshops, giving you the factor of 2. But then you'd need more cq's to draw everything each iteration, giving you only sqrt(d) iterations. If you only play half of what you draw each iteration, you're not actually getting an exponential increase. Maybe I'm misunderstanding your suggestion though (or my math could be off).

You could also probably do a bit better with the factor by stonemasoning a fortress into stonemasons/workshops.

In any case, looks like we're into up arrow notation land.

[tim17]

I have better f(n)= 2^2^2^(O(n) times) kingdom kc, workshop, city quarter, training, tfair, bridge, gardens.  Deck contains starting cards one gardens, rest are action. Training on workshop

Turn starts by drawing deck with log(d) cq where d is deck size, play kc-bridge. Then you start multiplying workshops/kc. Assume that deck has k kc and k workshops. play k/2 kc on k/2 workshops to gain 3/4k workshops and 3/4k kc then play cq to draw these and repeat by number of cq in deck. If you start with 3 kc and 3 workshops and l cq you will end with 2^l workshops. Coins from training allow you to buy 2^l/10 cq which shows that f(n+1)>=2^f(n) and bound follows.

More or less. I guess you want to have k/3 kc and 2k/3 workshops to gain 2k/3 kc and 4k/3 workshops, giving you the factor of 2. But then you'd need more cq's to draw everything each iteration, giving you only sqrt(d) iterations. If you only play half of what you draw each iteration, you're not actually getting an exponential increase. Maybe I'm misunderstanding your suggestion though (or my math could be off).

You could also probably do a bit better with the factor by stonemasoning a fortress into stonemasons/workshops.

In any case, looks like we're into up arrow notation land.

I guess you could play like slightly fewer kc's and workshops each iteration so that you only need a constant number of cqs to redraw the deck, giving you f(n+1) ~= (2-c)^f(n) for some small constant c.

[luser]

With what I wrote its exponential as for each kc-cq play number of played kc-workshops increases by some constant. By optimizing gains you would only improve that constant.

[liopoil]

Alright, so mojiponi's solution (and Holger's addition) ends up on the rough order of 2^kn2 for any k.

I think what luser originally wrote works but tim's suggestion is more clear and is technically better (improves the base of the exponent, pretty much). A more explicit (but still not totally optimized) description of luser's solution with additions (it took me a bit of work to decipher exactly what was happening):

Kingdom:  KC, stonemason, city quarter, fortress, gardens, training, travelling fair, inheritance (3 events, oh well). Training on stonemason, inheritance on KC (okay add a cost-reducer to the kingdom). When our deck has size d: Deck has 1 gardens, 1 fortress, ~7d/22 estates, ~14d/22 Stonemasons, ~d/22 City Quarters where x = o(d).

Turn:
Play ~log₂(d) City Quarters to draw the deck
Play the estates as d/4 KC on d/2 stonemasons for 3d gains, make them d estates and 2d stonemasons.
We have d/4 cards left in hand, so play 4 city quarters to draw everything again.
Play 3d/4 estates on 3d/2 stonemasons for 9d gains, which are 3d estates and 6d stonemasons...
Repeat like before until we run out of city quarters. We now have over d' = 3^d/88d cards in our deck, and the number of stonemason plays a bit over half of that. From training we could buy d'/20 city quarters, but just buy d'/22 instead (using travelling fair for buys).

Each turn d' = (3^1/88)^d, so we end up with around 3^1/88 ↑↑ n points.

See, that wasn't optimal at all (the base is around 1.01), but I think it would take quite a bit of work to get it much higher than that. I rounded down numbers in several places which could let us improve a little, but I don't see the base getting close to 2 very easily, mostly because we don't have enough coins!

I wouldn't be surprised at all if three arrows is possible though... I'll think about it...

[tim17]

Alright, so mojiponi's solution (and Holger's addition) ends up on the rough order of 2^kn2 for any k.

I think what luser originally wrote works but tim's suggestion is more clear and is technically better (improves the base of the exponent, pretty much). A more explicit (but still not totally optimized) description of luser's solution with additions (it took me a bit of work to decipher exactly what was happening):

Kingdom:  KC, stonemason, city quarter, fortress, gardens, training, travelling fair, inheritance (3 events, oh well). Training on stonemason, inheritance on KC (okay add a cost-reducer to the kingdom). When our deck has size d: Deck has 1 gardens, 1 fortress, ~7d/22 estates, ~14d/22 Stonemasons, ~d/22 City Quarters where x = o(d).

Turn:
Play ~log₂(d) City Quarters to draw the deck
Play the estates as d/4 KC on d/2 stonemasons for 3d gains, make them d estates and 2d stonemasons.
We have d/4 cards left in hand, so play 4 city quarters to draw everything again.
Play 3d/4 estates on 3d/2 stonemasons for 9d gains, which are 3d estates and 6d stonemasons...
Repeat like before until we run out of city quarters. We now have over d' = 3^d/88d cards in our deck, and the number of stonemason plays a bit over half of that. From training we could buy d'/20 city quarters, but just buy d'/22 instead (using travelling fair for buys).

Each turn d' = (3^1/88)^d, so we end up with around 3^1/88 ↑↑ n points.

See, that wasn't optimal at all (the base is around 1.01), but I think it would take quite a bit of work to get it much higher than that. I rounded down numbers in several places which could let us improve a little, but I don't see the base getting close to 2 very easily, mostly because we don't have enough coins!

I wouldn't be surprised at all if three arrows is possible though... I'll think about it...

So if we only play a p fraction of the kc's and stonemasons each iteration, we'll get a 2p size increase instead of a 2 factor increase each iteration. However, this means that we have a (1-p) fraction of those cards remaining in our hand. As a result, playing k=1-log₂(1-p) cq's should be sufficient to draw the deck each time.

This yields a total increase of (2p)^d/k-O(1) to the deck size. WolframAlpha says that the optimal value for p is about .829464, which yields about 1.153^d for d', which is somewhat better than 3^1/88, though still not very close to 2.

I want to say we can get rid of tfair and training by just adding candlestick maker and scheme to the kingdom and having the last iteration of gains be a bunch of candlestick makers and a few schemes to topdeck cq's. In any case, I think we need scheme to guarantee firing each turn.

I agree though that I don't care so much about the base and think that maybe it's possible to add another arrow (especially if we go to 2 player).

[tim17]

So if we only play a p fraction of the kc's and stonemasons each iteration, we'll get a 2p size increase instead of a 2 factor increase each iteration. However, this means that we have a (1-p) fraction of those cards remaining in our hand. As a result, playing k=1-log₂(1-p) cq's should be sufficient to draw the deck each time.

This yields a total increase of (2p)^d/k-O(1) to the deck size. WolframAlpha says that the optimal value for p is about .829464, which yields about 1.153^d for d', which is somewhat better than 3^1/88, though still not very close to 2.

I want to say we can get rid of tfair and training by just adding candlestick maker and scheme to the kingdom and having the last iteration of gains be a bunch of candlestick makers and a few schemes to topdeck cq's. In any case, I think we need scheme to guarantee firing each turn.

I agree though that I don't care so much about the base and think that maybe it's possible to add another arrow (especially if we go to 2 player).

Okay a bunch of things with what I said are wrong:

1. Scheme is bad, pretend I didn't say that. We can have royal seal to topdeck the cq buys if we don't want tfair.
2. What I said doesn't give enough cq's. Instead of candlestick maker, we use forager and have lots of treasures in the trash (some from the black market deck).
3. I forgot that stonemason gives a factor of 4, not 2.  This means we want to optimize (4p)^d/k-O(1), where k=2-log₂(1-p). Optimizing now yields p ~= .715408, so 1.3175^d.

As an aside, (I believe) we don't have infinite vp in a turn because the only draw is cq and kc/fortress and we can't gain those mid turn (we would need to gain both kc and fortress mid turn to get draw out of it). On the other puzzle, we ensured bounded +actions, maybe we can try the same here, though then we can't have forager I guess.

[liopoil]

I was kinda assuming perfect shuffle luck, so we draw the city quarters at the start of every turn. I forgot that tfair topdecks and was just using it for buys. But sure, get a royal seal. I like the idea of forager but not totally sure how it works? We would have to gain a lot of them, like O(d) of them - then we have fewer stonemasons and estates. Also I guess it's just a constant factor.

If p is the fraction of the cards we play each iteration, then we end up with (1 - p) of the cards in hand and 4p cards to draw. In order to end up with them all (1 + 3p) in hand we need to play ceil(log₂(1 + 3p/(1-p))) = k city quarters. If the fraction of the deck that is city quarters is x, then the final deck size will be multiplied by (1 + 3p)^xd/k. Then we want to maximize (1 + 3p)^{1/ceil(log₂((1 + 3p)/(1-p)))}. Wolfram says the optimal value for p is actually 3/7 here, which is kind of surprisingly low. That makes the final base of our tetration (16/7)^x/2. If x = 1/22 like it did before this is less than 1.02, but maybe we can do better with forager...

We would actually be thrilled if 99% of our starting cards each turn were city quarter or something; the deck size reached at the end of the turn would only be decreased a constant amount compared to several more iterations. So I think you are right; we can make all of our gains in the final iteration forager. Each forager will give at least 18 coins easily, which is enough for two city quarters. Since k = 2 this is enough for another iteration (multiply by 16/7), so definitely will always be better than taking a stonemason or something. We'll still want to keep travelling fair around for the buys, since each forager play only gives 1 buy but enough coins for two city quarters. In any case we'll be losing a constant factor every turn, possibly a lot, but x will be pretty darn close to 1. If we use the final 4p cards for just KC-forager then we get 8p forager plays for 16p city quarters, and the rest of the deck is just 1-p other stuff. Then x = 16p/(1 + 15p) = 0.923... we could include this in the optimization of p but I have a hunch that we could actually make x arbitrarily close to 1. Anyway, we now have 1.464544...  ↑↑ n points.

If we let x = 1 we get 1.51... instead, so slightly better. Anyway, not sure I feel like trying to optimize this technique further... I made enough mistakes while writing this post.

[ghostofmars]

Wouldn't it be possible to use native village to set aside additional point cards? If you can afford to use a small fraction of your gains towards additional gardens, then play NVs to set the gained cards aside that should increase the order.

[luser]

Native village with kc would cause infinite draw. I doubt that you could get triple arrow because of deck composition where you use limited number of one action as counter.

Second problem is that you didn't use kc-cq which increases draw to 8x instead to 2x.

Dependence of function on tfair/cq cost is just wrong from the first glance. It couldn't change asymptotic behaviour. Having constant number of cq more increases coins by bigger constant factor and initial log (d) cq plays exceed any constant factor.

But now I realized how to use scrying pool which I couldn't before as I didn't know how to deal with potions. Its again with city quarter.

Kingdom with cq, kc, bridge, workshop, spool, watchtower.

At start of turn use topdecked pool to draw all actions bought last turn and with one kc-cq draw rest of deck. Play kc-bridge. Now repeat playing kc-workshops gaining more kc and workshops and redrawing with scrying pool while you have pools.

At last iteration use half of kc and workshops that you have to gain potions, kc and bridges and use kc-cq to draw them. Buy and topdeck kc, cq and as many scrying pools as potions.

[ghostofmars]

Native village with kc would cause infinite draw.

How would that work? If I have a finite number of KC and NV, I can set aside a finite number of cards each turn.

[liopoil]

Native village with kc would cause infinite draw. I doubt that you could get triple arrow because of deck composition where you use limited number of one action as counter.

Second problem is that you didn't use kc-cq which increases draw to 8x instead to 2x.

Dependence of function on tfair/cq cost is just wrong from the first glance. It couldn't change asymptotic behaviour. Having constant number of cq more increases coins by bigger constant factor and initial log (d) cq plays exceed any constant factor.

But now I realized how to use scrying pool which I couldn't before as I didn't know how to deal with potions. Its again with city quarter.

Kingdom with cq, kc, bridge, workshop, spool, watchtower.

At start of turn use topdecked pool to draw all actions bought last turn and with one kc-cq draw rest of deck. Play kc-bridge. Now repeat playing kc-workshops gaining more kc and workshops and redrawing with scrying pool while you have pools.

At last iteration use half of kc and workshops that you have to gain potions, kc and bridges and use kc-cq to draw them. Buy and topdeck kc, cq and as many scrying pools as potions.

If we wanted more gardens, we wouldn't even need to set them aside; it would be no trouble to keep drawing them. But that really wouldn't even increase the base of the tetration. Also I think ghost is right - it doesn't seem to cause infinite draw?

You are right, Kc-cq cubes the base of the tetration. So now if we get almost all of our starting cards to be city quarter, then we have 3.455675... ↑↑ n points. EDIT: Somewhat wrong.

We don't want a constant number of cq though; we want almost all of our cards to be cq because the number of iterations is what limits our growth. The initial log_2 (d) plays of cq become meaningless. I think you may be right, there is a slight error in my analysis though... that I don't feel like looking into.

Your new solution also results in double-arrow points... the base of the tetration might be better when optimized but I also don't feel like calculating it.

I'm working on another idea right now, possibly involving hermit...

[ghostofmars]

If we wanted more gardens, we wouldn't even need to set them aside; it would be no trouble to keep drawing them. But that really wouldn't even increase the base of the tetration.

Perhaps there is something I misunderstand, but here is how I understand what you are doing:
In turn n you can increase the deck size of your deck by a factor f^n, so that the total deck size in turn n is f^n^n. Now if we would just replace some gains to double the number of gardens each iteration, your factor f gets replaced by g with g < f. On the other hand you have now g^(2n) points. So if there is a spot where g^2 > f, you would improve the result.

[luser]

Deck size is much bigger than f^n^n, its f^f^f^f...t times ^f

If we wanted more gardens, we wouldn't even need to set them aside; it would be no trouble to keep drawing them. But that really wouldn't even increase the base of the tetration. Also I think ghost is right - it doesn't seem to cause infinite draw?

You shouldn't think, you should know. With stonemason example its 2kc, 2nv, stonemason loop

You are right, Kc-cq cubes the base of the tetration. So now if we get almost all of our starting cards to be city quarter, then we have 3.455675... ↑↑ n points.

We don't want a constant number of cq though; we want almost all of our cards to be cq because the number of iterations is what limits our growth. The initial log_2 (d) plays of cq become meaningless. I think you may be right, there is a slight error in my analysis though... that I don't feel like looking into.

No, problem that makes analysis worthless is that result would depend on having constant number of cq more or less. By first getting 20 cq and playing them for 20 fifty more iterations you would get thousand times more coins and if you plug it into calculation you would get bigger exponent. And log d cq factor where you have cards from previous iteration would outgrow any constant.

Also its easy to see that you want to play only 1 cq per iteration if you use more you made mistake. For contradiction find last cq play where you didn't draw whole deck. You could instead of playing  on previous turn play them this turn to gain same cards for undrawn portion and have better drawing capabilities in previous turn.

[liopoil]

If we wanted more gardens, we wouldn't even need to set them aside; it would be no trouble to keep drawing them. But that really wouldn't even increase the base of the tetration.

Perhaps there is something I misunderstand, but here is how I understand what you are doing:
In turn n you can increase the deck size of your deck by a factor f^n, so that the total deck size in turn n is f^n^n. Now if we would just replace some gains to double the number of gardens each iteration, your factor f gets replaced by g with g < f. On the other hand you have now g^(2n) points. So if there is a spot where g^2 > f, you would improve the result.

luser is right... if the deck size is d on turn n, then the deck size at the end of the turn will be f^d for some constant f. Then after n turns the deck size is f^f^f^...^f, or f ↑↑ n.

If we wanted more gardens, we wouldn't even need to set them aside; it would be no trouble to keep drawing them. But that really wouldn't even increase the base of the tetration. Also I think ghost is right - it doesn't seem to cause infinite draw?

You shouldn't think, you should know. With stonemason example its 2kc, 2nv, stonemason loop

Oh, right - we can't have any gainable draw at all. Then we also can't have KC-workshop-watchtower, which would break your second method but it looks like you can just replace watchtower with royal seal.

You are right, Kc-cq cubes the base of the tetration. So now if we get almost all of our starting cards to be city quarter, then we have 3.455675... ↑↑ n points.

We don't want a constant number of cq though; we want almost all of our cards to be cq because the number of iterations is what limits our growth. The initial log_2 (d) plays of cq become meaningless. I think you may be right, there is a slight error in my analysis though... that I don't feel like looking into.

No, problem that makes analysis worthless is that result would depend on having constant number of cq more or less. By first getting 20 cq and playing them for 20 fifty more iterations you would get thousand times more coins and if you plug it into calculation you would get bigger exponent. And log d cq factor where you have cards from previous iteration would outgrow any constant.

Also its easy to see that you want to play only 1 cq per iteration if you use more you made mistake. For contradiction find last cq play where you didn't draw whole deck. You could instead of playing  on previous turn play them this turn to gain same cards for undrawn portion and have better drawing capabilities in previous turn.

I still don't see what you are saying at all. The number of iterations is O(d) >> log d, so the vast majority of the cq will be spent re-drawing cards mid-turn. Multiplying the number of cq by a constant multiplies the exponent by a constant. The log d just subtracts from the exponent, which gets dominated.

Since we're using KC-cq anyway, we'll want to play 7/11ths of our cards each time so that 3 plays of cq take us from 4/11 to 32/11. That means we're really getting (almost) 32/11 ↑↑ n VP.

[liopoil]

OK, I think I now see what you were saying before, so the below version doesn't bother with foragers. Hopefully I've re-phrased it well enough that it's now more clear why it doesn't matter what fraction of the deck is city quarters. I believe we can add ferry and royal carriage to the kingdom without allowing unbounded gain. The kingdom is now:

KC, stonemason, city quarter, fortress, royal carriage, bridge, travelling fair, training, ferry, inheritance.

The only draw is city quarter and fortress, and it's still not possible to gain either mid-turn. Ferry on royal carriage, inheritance on KC so that we can gain them from stonemasoning fortress. Training on stonemason. The bridge is just so that we can inherit KC in the first place. Choose some large constant C, and say that we have d stonemasons/estates. Every iteration, gain C royal carriages on the side, and only keep d/2^C-1 KC/stonemasons in hand. This gains 4d(1 - 1/2^C-1) estates/stonemasons. Then play C royal carriages, and use them to play a city quarter C+1 times to draw everything again. Repeat for as many iterations as city quarters. Now if there were x city quarters going into this turn, then now we have O(d(4 - 1/2^C-3)^{x - log(x + d)}) coins which we use to buy city quarters. The new number of estates/stonemasons in our deck is also on the order of this quantity, so we can say d = O(x) and x = O(d). Therefore the new number of city quarters is:

O(d(4 - 1/2^C-3)^{x - log(x + d)})
= O(x(4 - 1/2^C-3)^{x - log(x)})
= O((4 - 1/2^C-3)^x)
~O(4^x)

Since the number of points is within a constant factor of the number of city quarters, in the long run we can get (4 - ε) ↑↑ n points in n turns for any ε > 0.

[jonaskoelker]

Claim 2: You can pretty much always get a specific n-card deck within ~n turns.

This is really easy. Just buy the cards you want and trash the rest.

Your suggested method is incomplete: If I want 7xCopper, 3xEstate and a single 5-cost card, I might get 3/4 on an arbitrary number of shuffles before I hit $5. If I want a $6+ card I also have to buy treasures which (let's stipulate) I don't want.

Here's a fool-proof way: open 2xLurker, then Donate. Gain 2 more Lurkers and 1 Hireling, then repeatedly play the following turn: play 4xLurker, gaining a desired action card and a Hireling, then play 1 Hireling. (That way you keep drawing your deck, making that turn golden.)

If you want any non-action cards, buy enough treasures to buy them, while gaining and playing enough Hireling that you keep drawing your deck.

Once you have all the cards in your deck that you want, plus at least one Copper and one Silver, buy Bonfire to trash the Hirelings you've played if you don't want them in your deck at the end of the game. Donate to get rid of any other excess cards (e.g. Lurker), except for the Copper/Silver pair. Use those to pay off your debt. Then Bonfire them.

Now you have exactly the deck you want, and no debt, with some number of Hirelings having been played.

This takes one turn per action card you want to gain plus one turn per non-action card you want to gain, plus a constant number of turns for setup and cleanup (and optionally a constant number of turns buying treasures).

I'm pretty sure you can gain cards at a higher rate, and you can increase that rate proportionally to how many Lurkers you already have, so I would guess you can obtain any n-card deck you want in O(log n) turns. (idea: as fast as you can, gain enough Lurkers that you can gain your desired n action cards in a single turn, buying non-action cards one per turn while you ramp up.)

If you object to Hireling'ing yourself, then here's an observation: 2xGold is enough to afford Travelling Fair plus Expedition (enough to draw those 2xGold) with one coin to spare.  Plan: get enough Gold that you can keep drawing your deck while adding one desired card per turn in a sustainable way. Once you have assembled your desired deck (plus a ****ton of Gold), Donate all the undesired Gold except one, pay off your debt, then Bonfire that Gold.

[liopoil]

Yeah, there are lots of foolproof ways to set your starting deck up, especially because of donate. I didn't really feel the need to flesh that part of it out because that's not really the hard. I suppose the true statement of the final result here is:

For any ε > 0, there exists a positive constant integer c, such that for any positive integer n we can get (4 - ε) ↑↑ (n - c) points within n turns.

Again it doesn't make much sense to use big-O notation when the rate of growth is hyper-exponential like this. Really the answer is "we can pretty much make our score grow at the same general rate as 4 ↑↑ n does".

[bitwise]

Sorry for the necro.

Note that if we're already willing to subtract a constant number of turns from n (e.g. to set up the deck), it doesn't really matter what number you have as the base of the tetration. Here's a proof that 2 ↑↑ (n+2) >= 4 ↑↑ n.

Lemma 1: If x >= 4y and y >= 1, then 2^x >= 4*4^y.
Proof: x => 4y implies 2^x >= 2^(4y) = 4^(2y) = (4^y)*(4^y) >= 4*(4^y).

Now we can show that 2 ↑↑ (n+2) >= 4 * (4 ↑↑ n) for all n with induction. For n=1, both sides equal 16. If 2 ↑↑ (k+2) >= 4 * (4 ↑↑ k), then by Lemma 1, 2^(2 ↑↑ (k+2)) >= 4 * 4 ^ (4 ↑↑ k), or 2 ↑↑ (k+3) >= 4 * (4 ↑↑ (k+1)).

The same idea can be extended to show that for any A,B, there's a constant c such that A ↑↑ (n+c) >= B ↑↑ n for all n.

In summary, all of the c ↑↑ n solutions are about as good as each other for this question.

[liopoil]

Sorry for the necro.

Note that if we're already willing to subtract a constant number of turns from n (e.g. to set up the deck), it doesn't really matter what number you have as the base of the tetration. Here's a proof that 2 ↑↑ (n+2) >= 4 ↑↑ n.

Lemma 1: If x >= 4y and y >= 1, then 2^x >= 4*4^y.
Proof: x => 4y implies 2^x >= 2^(4y) = 4^(2y) = (4^y)*(4^y) >= 4*(4^y).

Now we can show that 2 ↑↑ (n+2) >= 4 * (4 ↑↑ n) for all n with induction. For n=1, both sides equal 16. If 2 ↑↑ (k+2) >= 4 * (4 ↑↑ k), then by Lemma 1, 2^(2 ↑↑ (k+2)) >= 4 * 4 ^ (4 ↑↑ k), or 2 ↑↑ (k+3) >= 4 * (4 ↑↑ (k+1)).

The same idea can be extended to show that for any A,B, there's a constant c such that A ↑↑ (n+c) >= B ↑↑ n for all n.

In summary, all of the c ↑↑ n solutions are about as good as each other for this question.

Oh, yes, you are right. Wow, it's been a while.

I'm kinda surprised that this and the busy beaver question (maximize coins in single turn, iirc) have different answers (two up arrows v. three up arrows). Also a couple expansions have come out since I last thought about this, and I don't know all the cards anymore. Still, would be interesting to see if it's possible to do better now.

[pitythefool]

First off, I'd like to thank tim17 for this excellent puzzle.  Here's my first take.

EDIT:  majiponi  found an exploit that leads to unbounded play thus disqualifying this kingdom.

Sorry, but I've noticed that your Kingdom goes infinite even without Ferry.

Expand Alchemist to Possession
Stonemason Possession to Golem and Gold
Stonemason Golem to 2 Alchemists
Expand Gold to Province
Stonemason Province to 2 Expands

Removing Alchemist, no infinity, but no interest either.

Kingdom: Stonemason, Village, Scrying Pool, Alchemist, Golem, Possession, Expand, Scheme, Fortress
Events: Seaway, Training, Lost Arts, Donate, Obelisk on Stonemason

Setup:  Seaway, Training, and Lost Arts on Stonemason (so it gets +1 action, +1 coin, and +1 buy)

Victory points are simply generated by Obelisk.

Starting deck:
  9 Scrying Pools
  1 Scheme
  1 Fortress
  N Expands
  N Stonemasons

At start of turn
  play Scrying Pool, draw entire deck
  play a Stonemason on the Fortress, gaining 2 Stonemasons
  play Scheme to draw one Stonemason (and to allow us to topdeck a Scrying Pool for next turn)

Start of iteration

  play all Stonemasons on Fortress, gaining 2 Stonemasons each time
  play a Scrying Pool, drawing a lot of Stonemasons

  play a Stonemason on Fortress, gain 2 Villages
  play remaining Stonemasons on Fortress, gaining 2 Stonemasons each time
  play a Scrying Pool, drawing a lot of Stonemasons and 2 Villages

  play a Stonemason on Fortress, gain 2 Stonemasons
  play 2 Villages, draw the two stonemasons
  play Expand on a Scrying Pool, gain a Golem
  play remaining Stonemasons on Fortress, gaining 2 Stonemasons each time
  play a Scrying Pool, drawing a lot of Stonemasons and 1 Golem

  play Expand on Golem, gain a Possession
  play remaining Stonemasons on Fortress, gaining 2 Stonemasons each time
  play a Scrying Pool, drawing a lot of Stonemasons and 1 Possession

  play Stonemason on Possession, gain two Golems
  play remaining Stonemasons on Fortress, gaining 2 Stonemasons each time
  play a Scrying Pool, drawing a lot of Stonemasons and 2 Golems

  play Stonemason on Golem, gain two Alchemists
  play Stonemason on Golem, gain two Alchemists
  play remaining Stonemasons on Fortress, gaining 2 Stonemasons each time
  play a Scrying Pool, drawing a lot of Stonemasons and 4 Alchemists

  play 4 Stonemasons on Alchemists, gain 8 Scrying Pools
  play remaining Stonemasons on Fortress, gaining 2 Stonemasons each time
  play a Scrying Pool, drawing a lot of Stonemasons and 8 Scrying Pools

End of iteration.  This state matches the start of iteration state except we have about 128 times as many Stonemasons and 2 less Expands.

It may seem like an endless loop, but eventually we run out of Expands.  Since neither Expands nor potion cards can be gained during a turn, the turn must eventually end.  When the Expands run out, we keep performing the iterations just gaining and drawing Stonemasons until we are out of Scrying Pools and the action phase ends.

Buy phase

  buy all of the Expands we can for next turn
  topdeck a Scrying Pool (from playing Scheme)

Two Expands gives us 7 Scrying Pools, so if we start with N Expands, we do O(3.5*N) Scrying Pool passes that double the number of Stonemasons each time.  That means we played O(N*2^(3.5*N)) Stonemasons for 1 buy each and 1 coin each. We can therefore buy O(N/7*2^(3.5*N)) Expands for the next turn.  Our Stonemasons have increased by the same order.  Therefore our growth rate is O(2^(3.5*N)) = O(11.31^N).