Dominion Strategy Forum

Please login or register.

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

Author Topic: Best Asymptotic Point Scoring  (Read 6227 times)

0 Members and 1 Guest are viewing this topic.

tim17

  • Bishop
  • ****
  • Offline Offline
  • Posts: 108
  • Respect: +189
    • View Profile
Best Asymptotic Point Scoring
« on: July 06, 2017, 01:18:32 am »
+10

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.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #1 on: July 06, 2017, 02:00:16 am »
0

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...
« Last Edit: July 06, 2017, 02:05:55 am by liopoil »
Logged

majiponi

  • Minion
  • *****
  • Offline Offline
  • Posts: 529
  • Respect: +433
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #2 on: July 06, 2017, 03:54:19 am »
+2

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.
« Last Edit: July 06, 2017, 04:01:54 am by majiponi »
Logged

Holger

  • Tactician
  • *****
  • Offline Offline
  • Posts: 448
  • Respect: +212
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #3 on: July 06, 2017, 01:34:22 pm »
0

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.
Logged

luser

  • Tactician
  • *****
  • Offline Offline
  • Posts: 447
  • Respect: +352
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #4 on: July 06, 2017, 04:52:31 pm »
+1

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.

Logged

tim17

  • Bishop
  • ****
  • Offline Offline
  • Posts: 108
  • Respect: +189
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #5 on: July 07, 2017, 02:21:28 am »
0

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.
Logged

tim17

  • Bishop
  • ****
  • Offline Offline
  • Posts: 108
  • Respect: +189
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #6 on: July 07, 2017, 02:26:43 am »
0

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.
Logged

luser

  • Tactician
  • *****
  • Offline Offline
  • Posts: 447
  • Respect: +352
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #7 on: July 07, 2017, 04:47:00 am »
0

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.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #8 on: July 07, 2017, 02:29:25 pm »
+1

Alright, so mojiponi's solution (and Holger's addition) ends up on the rough order of 2kn2 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 ~log2(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' = 3d/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' = (31/88)d, so we end up with around 31/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...
« Last Edit: July 07, 2017, 02:31:53 pm by liopoil »
Logged

tim17

  • Bishop
  • ****
  • Offline Offline
  • Posts: 108
  • Respect: +189
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #9 on: July 07, 2017, 10:20:11 pm »
+1

Alright, so mojiponi's solution (and Holger's addition) ends up on the rough order of 2kn2 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 ~log2(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' = 3d/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' = (31/88)d, so we end up with around 31/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-log2(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.153d for d', which is somewhat better than 31/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).
Logged

tim17

  • Bishop
  • ****
  • Offline Offline
  • Posts: 108
  • Respect: +189
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #10 on: July 07, 2017, 11:12:28 pm »
+1

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-log2(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.153d for d', which is somewhat better than 31/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-log2(1-p). Optimizing now yields p ~= .715408, so 1.3175d.

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.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #11 on: July 08, 2017, 01:38:40 am »
+1

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(log2(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(log2((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.
Logged

ghostofmars

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 141
  • Respect: +67
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #12 on: July 09, 2017, 09:10:58 am »
0

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.
Logged

luser

  • Tactician
  • *****
  • Offline Offline
  • Posts: 447
  • Respect: +352
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #13 on: July 09, 2017, 11:31:21 am »
0

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.

Logged

ghostofmars

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 141
  • Respect: +67
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #14 on: July 09, 2017, 03:55:04 pm »
0

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.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #15 on: July 09, 2017, 05:16:24 pm »
0

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...
« Last Edit: July 10, 2017, 02:03:44 pm by liopoil »
Logged

ghostofmars

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 141
  • Respect: +67
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #16 on: July 10, 2017, 04:48:14 am »
0

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.
Logged

luser

  • Tactician
  • *****
  • Offline Offline
  • Posts: 447
  • Respect: +352
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #17 on: July 10, 2017, 06:41:06 am »
0

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


Quote
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.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #18 on: July 10, 2017, 01:52:20 pm »
0

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.

Quote
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.
« Last Edit: July 10, 2017, 01:59:15 pm by liopoil »
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #19 on: July 10, 2017, 02:45:23 pm »
+3

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/2C-1 KC/stonemasons in hand. This gains 4d(1 - 1/2C-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/2C-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/2C-3)x - log(x + d))
= O(x(4 - 1/2C-3)x - log(x))
= O((4 - 1/2C-3)x)
~O(4x)

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.
« Last Edit: July 10, 2017, 02:46:34 pm by liopoil »
Logged

jonaskoelker

  • Explorer
  • *****
  • Offline Offline
  • Posts: 326
  • Grand Market = cantrip Woodcutter
  • Respect: +382
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #20 on: October 01, 2017, 01:06:07 pm »
0

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.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #21 on: October 01, 2017, 05:52:22 pm »
0

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".
Logged

bitwise

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +55
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #22 on: October 27, 2018, 01:00:46 pm »
+1

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.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #23 on: October 29, 2018, 04:18:00 am »
0

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.
Logged

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #24 on: November 10, 2018, 11:12:10 pm »
0

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

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).
Logged

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #25 on: November 12, 2018, 05:33:29 pm »
0

Here's my second take.  It's an extreme kingdom. I had to add Black Market to accommodate cards I only needed 1 copy of.  There's a lot of events and a Renaissance project.  It will also be difficult to get the engine started, but it's all legal.

Kingdom:  Black Market, Stonemason, Village, Fishing Village, Haggler, Mine, Scrying Pool, Alchemist, Golem, Possession
Black Market:  Scheme, Fortress, City Quarter
Events: Travelling Fair, Seaway, Training, Lost Arts, Donate, Ferry, Inheritance, Obelisk on Stonemason
Project:  Capitalism

Getting started:
  buy 1 Black Market, gain Scheme, Fortress, and City Quarter from the Black Market
  buy Seaway, Training, and Lost Arts for Stonemason (so it gets +1 action, +1 coin, and +1 buy)
  buy Ferry for Mine and then Inheritance on Mine, then buy Ferry for Haggler
  buy the project Capitalism
  buy Donate to trash unwanted cards

Victory points are simply generated by Obelisk.

Starting Deck:
  1 Scheme
  1 Fortress
  1 City Quarter
  1 Black Market
  N Stonemasons
  N Golems
  4 Scrying Pools

We are starting with 3 Fishing Villages set aside from last turn (allows us to play a City Quarter and a Black Market and one Mine without requiring more actions)

Start of turn (This will make more sense after seeing the buy phase)
  hand consists of 4 Scrying Pools and a City Quarter
  play 1 Scrying Pool, drawing all the recently bought actions that were topdecked.
  play the the City Quarter to draw the remainder of the deck.
  play the Scheme (to allow us to topdeck our City Quarter for next turn)

As before we are going to play all of our Stonemasons on Fortress, gaining more Stonemasons, then playing a Scrying Pool to draw them all into our hand.  To prevent running out of Scrying Pools, divert a Stonemason as needed to downgrade a potion card (Possession -> 2 Golems -> 4 Alchemists -> 8 Scrying Pools).  We will do this repeatedly until we only have one Scrying Pool left.

Now use all of the Stonemasons to generate the following cards in these ratios:
  2 Estates
  2 Hagglers
  2 Villages
  3 Fishing Villages

  play the final Scrying Pool to draw these all into our hand (our discard pile is now empty)
  play the Black Market, allowing us to play Fishing Villages. play 1/3 of them (enough actions to play all of the Hagglers)
  play an Estate, trashing a Fishing Village and gaining a Potion
  play a Village to draw the Potion
  repeat that sequence for all Estates
  play all of the Hagglers

Begin buy phase

  play all of the Potions
  buy Travelling Fair (for topdecking)
  buy a lot of Possessions, gaining a lot of Golems (topdeck them all)
  buy 1 Alchemist, gaining a lot of Scrying Pools (topdeck them all)
  put the City Quarter on the top of our deck (because of Scheme)

Each Golem is worth 4 Scrying Pools, so we've played ~N*2^(4*N) Stonemasons for 1 buy and 1 coin each.  We've also played ~(N/2)*(2/9)*2^(4*N) Hagglers for 2 coins each and ~(N/2)*(1/9)*2^(4*N) Fishing Villages for 1 coin each.  We mined ~(N/2)*(2/9)*2^(4*N) Potions.  I'm not even going to work out exacly how many Possessions we can buy since the only significant part is the O(N*2^(4*N)).  So we buy O(N*2^(4*N)) Possessions and that allows us to gain O(N*2^(4*N))*O(N*2^(4*N)) Golems due to the Hagglers.  That is an increase in Golems of O(N*2^(8*N)) = O(256^N).  Stonemasons did not increase by nearly that much, only O(16^N).  We have to run quite a few Scrying Pool passes in the next turn, doubling the number of Stonemasons each time in order for them to achieve an equivalent growth.  It would take O(240^N) Scrying Pools to do that, or O(0.25*240^N) Golems.  The true growth rate is therefore O(256^N) - O(240^N) which is still O(256^N).

I struggled real hard to put Hagglers into my last solution.  That solution started out with Upgrade instead of Expand.  I needed Ferry on Hagglers to gain them using Stonemason.  But that would allow someone to put Ferry on Upgrade and gain them which would lead to an unbounded engine.  I then picked Expand instead, reasoning that Ferry on Expand would not make them gainable as the cost would be 5 coins.  Alas, Expand Fortress to Gold, Expand Gold to Province, Stonemason Province to 2 Golds, Stonemason 2 Golds to 4 Expands yields a gain of 2 Expands, hence another unbounded engine.  This kingdom uses Mine as a selective Expand.  It can't be used on anything put treasure cards.  The original goal was to mine an action card to gain a Haggler.  I needed an action card costing 3 coins or less, that had at least +1 coin (to make it a treasure), that also provided additional actions, and that didn't draw cards.  Squire was my first choice, but it was too good.  I could Mine a Squire and gain a Haggler, but trashing the Squire allows gaining an attack card.  Scrying Pool is an attack card.  Enough said.

That's the hardest part of this puzzle.  You have to put together a pretty good kingdom, but not a great kingdom, and hope you didn't miss an exploit.

EDIT: Corrected the growth calculation.  It's actually bigger than I first reported.

EDIT: I was thinking of Mine as a replacement for Expand so much, I forgot that the Potion would be gained into my hand.  D'oh.  No need for those Villages.  You could use half as many Fishing Villages instead (for actions) and play them along with the others by Black Market.  It wouldn't improve things in any significant way, but I thought I'd point that out.
« Last Edit: November 13, 2018, 10:12:46 pm by pitythefool »
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #26 on: November 14, 2018, 06:42:09 pm »
0

The growth rate to beat is currently double-up-arrow, first introduced here:

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.

and explained in more detail here:
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 ~log2(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' = 3d/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' = (31/88)d, so we end up with around 31/88 ↑↑ n points.

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

the rest of the thread just improves the number of set up turns by a constant, as bitwise pointed out. So the next step requires a new level of method, and it would surely involve these newfangled expansions I'm hearing about...
Logged

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #27 on: November 14, 2018, 08:06:02 pm »
0

The growth rate to beat is currently double-up-arrow, first introduced here:

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.

and explained in more detail here:
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 ~log2(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' = 3d/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' = (31/88)d, so we end up with around 31/88 ↑↑ n points.

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

the rest of the thread just improves the number of set up turns by a constant, as bitwise pointed out. So the next step requires a new level of method, and it would surely involve these newfangled expansions I'm hearing about...

"Each turn d' = (31/88)d, so we end up with around 31/88 ↑↑ n points.".    I'm claiming d' = 256^d, so I think it's a lot better.
« Last Edit: November 14, 2018, 08:10:45 pm by pitythefool »
Logged

bitwise

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +55
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #28 on: November 14, 2018, 08:10:05 pm »
0

"Each turn d' = (31/88)d, so we end up with around 31/88 ↑↑ n points."  I'm claiming d' = 256^d.
Your post looks right to me (though I didn't check super carefully), but since 4↑↑(n+2) > 256↑↑(n), it's only 2 turns better than the 4↑↑n kingdom (supposing the setup took the same amount of time) despite seeming way better.
Logged

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #29 on: November 14, 2018, 08:24:23 pm »
+1

"Each turn d' = (31/88)d, so we end up with around 31/88 ↑↑ n points."  I'm claiming d' = 256^d.
Your post looks right to me (though I didn't check super carefully), but since 4↑↑(n+2) > 256↑↑(n), it's only 2 turns better than the 4↑↑n kingdom (supposing the setup took the same amount of time) despite seeming way better.
Ha.  My setup would definitely take a lot longer.  I wanted to show the usefulness of Hagglers though.  When used to best advantage, they can square your tetration base.  Unfortunately, City Quarters cannot be haggled.  I am also thinking that using Mines to gain actions directly into your hand may be very useful.  But I guess it's three arrows now or bust, eh?
« Last Edit: November 14, 2018, 08:52:19 pm by pitythefool »
Logged

bitwise

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +55
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #30 on: November 14, 2018, 08:50:19 pm »
0

"Each turn d' = (31/88)d, so we end up with around 31/88 ↑↑ n points."  I'm claiming d' = 256^d.
Your post looks right to me (though I didn't check super carefully), but since 4↑↑(n+2) > 256↑↑(n), it's only 2 turns better than the 4↑↑n kingdom (supposing the setup took the same amount of time) despite seeming way better.
Ha.  My setup would definitely take a lot longer.  I wanted to show the usefulness of Hagglers though.  When used to best advantage, they can double your tetration base.  Unfortunately, City Quarters cannot be haggled.  I am also thinking that using Mines to gain actions directly into your hand may be very useful.  But I guess it's three arrows now or bust, eh?
If you put City Quarter in the kingdom and Gladiator/Fortune, you could Haggle for City Quarter that way, but since you can't gain them mid-turn it doesn't seem like that would really help.

One other little thing, you should be able to play your Hagglers when you Black Market, so you don't need quite as many Fishing Villages.
Logged

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #31 on: November 14, 2018, 08:55:10 pm »
0

"Each turn d' = (31/88)d, so we end up with around 31/88 ↑↑ n points."  I'm claiming d' = 256^d.
Your post looks right to me (though I didn't check super carefully), but since 4↑↑(n+2) > 256↑↑(n), it's only 2 turns better than the 4↑↑n kingdom (supposing the setup took the same amount of time) despite seeming way better.
Ha.  My setup would definitely take a lot longer.  I wanted to show the usefulness of Hagglers though.  When used to best advantage, they can double your tetration base.  Unfortunately, City Quarters cannot be haggled.  I am also thinking that using Mines to gain actions directly into your hand may be very useful.  But I guess it's three arrows now or bust, eh?
If you put City Quarter in the kingdom and Gladiator/Fortune, you could Haggle for City Quarter that way, but since you can't gain them mid-turn it doesn't seem like that would really help.

One other little thing, you should be able to play your Hagglers when you Black Market, so you don't need quite as many Fishing Villages.
Wow.  You're right.  I didn't think of Fortune.  And I missed playing the Hagglers with Black Market.  Come to think of it, I could have also just played them in my buy phase.  That's great.
« Last Edit: November 14, 2018, 09:02:33 pm by pitythefool »
Logged

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #32 on: November 14, 2018, 09:10:21 pm »
+1

A question for tim17.  I'd like a ruling on how split piles work in an infinite kingdom.  Would it be possible to gain a Fortune or would they be buried under an infinity of Gladiators?  Or is it 5 Gladiators, 5 Fortunes, 5 Gladiators, 5 Fortunes, ....   While we're on the subject, how about Knights and Ruins and other mixed supply piles?
Logged

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #33 on: November 20, 2018, 04:02:22 pm »
+2

The title of this thread is "Best Asymptotic Point Scoring".  This led me to generate some complicated engines to achieve high asymptotic ratios of point growth.  Now I'm not sure if that was the intended goal or not.  It seems discussion here has gone in a direction that looks at growth over time where the number of turns for setup is a factor.  So I'm trying a different approach.

Kingdom:  Stonemason, Scheme, Scrying Pool, Fortress, Storyteller, Priest
Events: Advance, Seaway, Obelisk on Stonemason
Project:  Academy

Setup:  buy Seaway for Stonemason, buy the project Academy.

Starting Deck

  1 Scrying Pool
  1 Scheme
  1 Fortress
  1 Priest
  N Stonemasons
  M Storytellers

  We will always play Stonemason with Fortress as the card to be trashed and we will always gain two Stonemasons, so I'll just refer to this as "play Stonemason".  This also gains two villagers (via Academy), so we will always assume to use a villager when we need another action.  Similarly, Priest will also always trash Fortress.

Play
  play Scrying Pool, draw entire deck
  play 1 Stonemason
  play Priest
  play Scheme (draw 1 Stonemason)
  play N Stonemasons
  play Storyteller (draws 2N+1 Stonemasons)

iterate next two lines as long as we have Storytellers
  play all Stonemasons
  play Storyteller (draw twice as many Stonemasons)
then
  play (N+1)*2^M Stonemasons
  buy stuff
  topdeck Scrying Pool

We have played a total of (N+1)*2^(M+1)-1 Stonemasons.  Only the ones we played after the last Storyteller have coins generated from Priest, but that doesn't matter, they all generated a +buy.  Buy Advance as many times as we can (zero cost).  Repeatedly trash the Fortress and gain Storytellers.
(Interesting note, each time you trash the Fortress, Priest generates another 2 coins which is available immediately for spending.  I had to remove Travelling Fair from the kingdom because of this.  It also means that at some point we can switch over to buying Stonemasons and overpaying by five to gain double Storytellers, but I'll leave this tweak out.)
So N'=(N+1)*2^(M+1)-1 and M'=M+(N+1)*2^(M+1).  Since the growth of Stonemasons is controlled by the growth of Storytellers, and vice versa, we can just say N'>2^N.  This is weak compared to other schemes already posted.  But it is simple and quick to set up.  So the next chore is to determine how quickly we can set it up.  I've added some additional items to my kingdom solely for that purpose.

Additional Kingdom cards:  Baker, Market Square, Pixie, Ironworks
Shelters.
Additional Events:  Donate, Alms

Starting deck is Necropolis, Overgrown Estate, Hovel, Pouch, Goat, and five Copper.

This is by no means optimized.  I concentrated on the worst case scenarios and took a guess on the correct order to buy.  This is tedious, I suggest skipping to the end.

The hand with Necropolis will buy Advance, trash Necropolis and gain an Ironworks.  The other hand may only have 1 coin.  Alms for Market Square.
If Goat collides with Hovel, trash Hovel.  Don't trash Overgrown Estate.
Turn 3:  Buy Donate, trash down to Ironworks, Market Square, Goat, and Overgrown Estate.  Discard Market Square, gain a Gold.  Worst case, we could only pay off 1 debt.
deck={ Ironworks, Market Square, Goat, Overgrown Estate, Gold }
Turn 4:  Ironworks a Potion.  Play Goat, trash Overgrown Estate, draw Potion.  Do not discard Market Square.  Play Gold.  Pay off 5 debt.
deck={ Ironworks, Market Square, Goat, Gold, Potion }
Turn 5:  Ironworks a Fortress.  Play Market Square and draw Fortress.  Play Goat, Gold, and Potion.  Pay off remaining 2 debt.  Buy Advance, trash Fortress, gain Priest.  Buy a Scrying Pool.
deck={ Ironworks, Market Square, Goat, Gold, Potion, Fortress, Priest, Scrying Pool }
Turn 6:  Play Market Square, Fortress, and Scrying Pool (if any in hand).  This puts the remaining five cards in hand.  Play Priest, trash Potion.  Play Goat, trash Gold.  Buy a Scheme.
deck={ Ironworks, Market Square, Goat, Fortress, Priest, Scrying Pool, Scheme }
Turn 7:  Play Scrying Pool, Scheme, and Market Square as them come into our hand.  Play Priest, trash Ironworks.  Play Goat, trash Fortress.  Buy Seaway, Gain Stonemason.  Topdeck Scrying Pool.
deck={ Market Square, Goat, Fortress, Priest, Scrying Pool, Scheme, Stonemason }
Turn 8:  Play Scrying Pool.  Even in the worst case (Goat is second card), we draw the remainder of the deck.  Play Scheme.  Play Fortress.  Play Priest, trash Goat.  Play Stonemason, trash Market Square, gain 2 Stonemasons.  Use coin token from Baker.  Buy the project Academy.  Alms for a Stonemason.
deck={ Fortress, Priest, Scrying Pool, Scheme, Stonemason x 4 }
The engine has been started.  We will increase the number of Stonemasons to 12 and buy 5 Storytellers this turn.

This allows us to conclude that the engine has the growth function f(n)=2↑↑(n-8).  I think this means it will beat luser, tim17, and liopoil's engine that employs City Quarter unless that engine can be setup in 6 turns or less.  I'm not knocking that engine!  The use of City Quarters and Royal Carriages was very clever and it was done before Renaissance.  I'm just establishing a complete declaration of point growth as a target.
Logged

tim17

  • Bishop
  • ****
  • Offline Offline
  • Posts: 108
  • Respect: +189
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #34 on: November 20, 2018, 09:08:51 pm »
0

Glad that this thread has continued to generate interest :)

A question for tim17.  I'd like a ruling on how split piles work in an infinite kingdom.  Would it be possible to gain a Fortune or would they be buried under an infinity of Gladiators?  Or is it 5 Gladiators, 5 Fortunes, 5 Gladiators, 5 Fortunes, ....   While we're on the subject, how about Knights and Ruins and other mixed supply piles?


I forget if I had thought about this when I had initially posed the question. I don't have strong feelings one way or another; I tend to prefer to let people assume whatever they want and then see what they can come up with. Accordingly, let's say that any pile with more than one card name has infinitely many of each, and you get to choose the order of the pile during setup. If for some reason this causes problems, we can try some other interpretation, but let's go with this for now.
Logged

bitwise

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +55
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #35 on: November 20, 2018, 09:17:50 pm »
0

Glad that this thread has continued to generate interest :)

A question for tim17.  I'd like a ruling on how split piles work in an infinite kingdom.  Would it be possible to gain a Fortune or would they be buried under an infinity of Gladiators?  Or is it 5 Gladiators, 5 Fortunes, 5 Gladiators, 5 Fortunes, ....   While we're on the subject, how about Knights and Ruins and other mixed supply piles?


I forget if I had thought about this when I had initially posed the question. I don't have strong feelings one way or another; I tend to prefer to let people assume whatever they want and then see what they can come up with. Accordingly, let's say that any pile with more than one card name has infinitely many of each, and you get to choose the order of the pile during setup. If for some reason this causes problems, we can try some other interpretation, but let's go with this for now.
I propose the following interpretation: instead of infinite piles, have the following rule: whenever a pile would be emptied, replenish the pile with cards in the original state. (And if you were somehow gaining 1000 cards at the same time, you replenish the pile multiple times in between gains as necessary.) This lets us include knights and split piles without too much confusion. For example, the Gladiator/Fortune pile would effectively keep being 5 Gladiators then 5 Fortunes alternating.
Logged

bitwise

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +55
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #36 on: November 21, 2018, 01:41:28 am »
+7

With the help of paulfc, I think we were able to get to 3 up arrows!

EDIT: The original analysis was slightly wrong (2 ↑↑↑ n instead of 2 ↑↑↑ 2n). I also forgot to add a way to score.

The core kingdom cards we need are:
Black Market (BM), Haggler (H), Scrying Pool (SP), Squire (S), Golem (G), Count.
We also need a single Trader from the Black Market deck, and Trader cannot be a Kingdom pile.
We also need enough +Actions (Page ->Champion is fine). We also need (just one) Royal Seal for topdecking.
We also need a source of buying Golems at the end of our turn. I'll use Changeling for that.
Finally, we need some source of points, since Haggler and Changeling are not very good at getting points. Obelisk on any pile, say BM, works.

The Black Market deck will contain only Fairgrounds, Trader, Royal Seal. To set up our deck, we buy the Trader and Royal Seal, and also obtain and play Champion.

At the beginning of our turn, our deck will have 1 Trader, 1 Royal Seal, X BMs, X Hs, X SPs, and X Gs. (We don't need exactly the same number of each, just within some constant factor is good enough.) We may also have some number of Counts but don't particularly care how many. We can guarantee that 2 Scrying Pools will be in our starting hand, letting us draw all the actions in our deck.

The sequence of our turn will basically be a nested loop.

The basic step of first loop is to play all the Hagglers in our hand, then all the Black Markets in our hand. (The first time we do this loop, we also play the Royal Seal with Black Market.) With each Black Market, we buy the Fairgrounds, but use Trader to gain a Silver instead of instead of the Fairgrounds. If we have A Hagglers out, then each time we buy Fairgrounds, we gain A cards costing less than 6. We can topdeck all actions gained this way, but none of the Silvers. After playing all the Hagglers and Black Markets in our hand, we play a Scrying Pool to get all the actions gained this way (and a single Silver).

If we started with 2A BMs and 2A Hs, doing one step of this loop gains us (2A)^2=4A^2 cards. We can choose this to be 2A^2 BMs and 2A^2 Hs. We can repeat the loop by playing all the Hs then all the BMs again. Even ignoring the Hagglers played in previous steps, one step of this loop changes A to A^2 (i.e. A -> A^2 -> A^4 -> A^8 -> ... ), so with B SPs, we can end up with 4*A^(2^B) actions in our hand costing less than 6.

We will repeat this loop for every SP in our hand, except leaving one extra in our hand. On the last step of the loop, we will gain some constant fraction each of BM, H, Squire. We will also divert some of these gains to be Count, and we need one Count per Golem in our hand, plus 3 extra Counts. This number will always be way way smaller than the number of cards we can gain (at least X^(2^X) cards we can gain, and at most X Golems in our hand), so we can basically ignore the number in our analysis.

With all the actions in our hand, we can play the BMs and Hs to gain some amount of BMs and Hs on the top of our deck. Then, we play Count for topdeck and money to topdeck all of our Golems except for one. With our remaining 4 Counts, we use 3 of them for topdeck and money, topdecking Trader, SP, and our last Count. Now our hand is a bunch of Squires and one Golem. The top of our deck is Count, SP, Trader, the rest of our Golems, and a bunch of BMs and Hs, then some Silvers. We can now use Golem, which will hit Count and SP. We pick Count then SP as our order. With Count, we pick topdeck and trash, topdecking a Squire, then trashing our hand full of Squires. With each Squire, we gain a SP and topdeck it. Then, our Golem plays the SP, letting us draw all the actions we have left (a bunch of SPs, the Trader, the Golems, a bunch of BMs and Hs (and 1 Squire that we don't really care about)).

Doing this is a single step of our second loop. We perform the first loop for all the SPs in our hand, then expend one Golem to gain a bunch more SPs. If we end the steps of the first loop with C BMs+Hs and D Ss, we will have O(C^2) BMs, O(C^2) Hs, and O(D) SPs after all these operations. If we started with A each of BM, H, SP, we will have 4*A^(2^A) actions to allocate between C and D. We can allocate a square root amount to C and the rest to D and end up with D = O(A^(2^A)), which is at least 2^(2^A). So, one step of this loop turns A into 2^(2^A).

Now, we can repeat this second loop for every Golem we started with. Since we started with X BM, H, SP, and got to repeat this loop X times, we went from A to 2^(2^A) X times, starting at X, which is (2↑↑(2X))^X > 8 * 2↑↑(2X). Letting Y = 2↑↑(2X), we can let this be 4Y SPs in hand and 4Y changelings on the top of our deck, and play all the SPs, drawing the 4Y changelings. Then, in our Night phase, we use the Changelings to gain Y each of BM, H, SP, G, topdecking them (putting the scrying pools on top for next turn).

Since every turn changes X from 2↑↑(2X), this kingdom has growth rate f(n) > 2↑↑↑(2n-c) for some constant c f(n) > 2↑↑↑n. The actual amount is bigger than c↑↑↑n for any constant c, but I'm not sure how to express it. At the very least, we can correctly remove the -c from n and still have a correct lower bound, so there's that.

This kingdom is not an infinite kingdom because:
  • Golems cannot be gained midturn, and there is only one Trader.
  • The only draw that can be gained midturn is Scrying Pool, and no cards are gained to hand.
  • To gain Scrying Pools midturn that can still be played on the same turn, a Golem or Trader must be used.

In summary:
  • Kingdom: Black Market, Haggler, Scrying Pool, Squire, Golem, Count, Changeling, Page. Sideways cards: Obelisk on BM.
    (BM deck: Fairgrounds, Trader, Royal Seal).
  • Growth rate: f(n) = 2↑↑↑n
  • No Renaissance cards needed!
« Last Edit: November 21, 2018, 12:04:48 pm by bitwise »
Logged

boris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 21
  • Respect: +30
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #37 on: November 21, 2018, 03:30:30 am »
0

In summary:
  • Kingdom: Black Market, Haggler, Scrying Pool, Squire, Golem, Count, Changeling, Page.
    (BM deck: Fairgrounds, Trader, Royal Seal).
  • Growth rate: f(n) = 2↑↑↑(2n-c)
  • No Renaissance cards needed!

Wow!
I need to carefully go through this again, but I guess, there should also be a gardens to gain some VP. Or am I missing something?
Logged

faust

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2567
  • Shuffle iT Username: faust
  • Respect: +3542
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #38 on: November 21, 2018, 04:48:00 am »
0

If we started with 2A BMs and 2A Hs, doing one step of this loop gains us (2A)^2=4A^2 cards. We can choose this to be 2A^2 BMs and 2A^2 Hs. We can repeat the loop by playing all the Hs then all the BMs again. Even ignoring the Hagglers played in previous steps, one step of this loop changes A to A^2 (i.e. A -> A^2 -> A^4 -> A^8 -> ... ), so with B SPs, we can end up with 4*A^(2^B) actions in our hand costing less than 6.
If we were to add Capitalism and Mandarin to the kingdom, we could gain a Mandarin here and then not only get the 2A^2 BM plays, but instead could play all BMs we had already again. I am too lazy right now to work out whether this significantly increases the overall growth rate.
Logged
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.

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #39 on: November 21, 2018, 07:55:34 am »
0

If we started with 2A BMs and 2A Hs, doing one step of this loop gains us (2A)^2=4A^2 cards. We can choose this to be 2A^2 BMs and 2A^2 Hs. We can repeat the loop by playing all the Hs then all the BMs again. Even ignoring the Hagglers played in previous steps, one step of this loop changes A to A^2 (i.e. A -> A^2 -> A^4 -> A^8 -> ... ), so with B SPs, we can end up with 4*A^(2^B) actions in our hand costing less than 6.
If we were to add Capitalism and Mandarin to the kingdom, we could gain a Mandarin here and then not only get the 2A^2 BM plays, but instead could play all BMs we had already again. I am too lazy right now to work out whether this significantly increases the overall growth rate.
I was up most of the night figuring out how to do just this to my last posted engine.  Adding Upgrade would allow me to trash a Fortress and gain a Mandarin after having played all my Storytellers and they would go back onto my deck.  Adding Alchemist would allow me to generate an unending supply of Scrying Pools to redraw everything.  Oh, well.  No point in that now.
Logged

pitythefool

  • Baron
  • ****
  • Offline Offline
  • Posts: 52
  • Respect: +54
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #40 on: November 21, 2018, 07:57:34 am »
0

With the help of paulfc, I think we were able to get to 3 up arrows!

That was some truly inspired sh*t!  Congrats.
Logged

bitwise

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +55
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #41 on: November 21, 2018, 12:00:27 pm »
0

Wow!
I need to carefully go through this again, but I guess, there should also be a gardens to gain some VP. Or am I missing something?

Yes, normally you can convert your engine to points on the last 1 or 2 turns easily but since all the gains are from Haggler and Changeling, this isn't actually possible as is. We can just add one Gardens or Obelisk on any pile.

If we were to add Capitalism and Mandarin to the kingdom, we could gain a Mandarin here and then not only get the 2A^2 BM plays, but instead could play all BMs we had already again. I am too lazy right now to work out whether this significantly increases the overall growth rate.
I don't think it really helps, since you can do this only once per loop, and on every step of a loop you square the number of BMs + Hs you have, which is a lot more than the sum all of your previous steps. Example: If you've done X, X^2, X^4, X^8, your next step would be X^16 things, and the Mandarin trick would let you get X+X^2+X^4+X^8 extra BM plays, which is a lot less than X^16.

I thought about my analysis some more and realized that applying X -> 2↑↑(2X) n times doesn't give 2↑↑↑2n. You would need to apply X -> 2↑↑(2↑↑X) n times to do that. The actual value is hard to reason about, but it is definitely greater than 2↑↑↑n (and is also greater than c↑↑↑n for any constant c > 0). However, I don't think it's bigger than any 2↑↑↑(1+c)n, for any c is a constant > 0.

I will edit my post with these fixes.

With the help of paulfc, I think we were able to get to 3 up arrows!

That was some truly inspired sh*t!  Congrats.
Thanks! Actually, it was your latest post that gave me the idea.  :D
« Last Edit: November 21, 2018, 12:06:22 pm by bitwise »
Logged

boris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 21
  • Respect: +30
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #42 on: November 21, 2018, 03:36:47 pm »
0

Really great work. As far as I understand the growth analysis, it seems fine, but I cannot follow two steps, which are more related to Dominion rules.
If we started with 2A BMs and 2A Hs, doing one step of this loop gains us (2A)^2=4A^2 cards. We can choose this to be 2A^2 BMs and 2A^2 Hs. We can repeat the loop by playing all the Hs then all the BMs again. Even ignoring the Hagglers played in previous steps, one step of this loop changes A to A^2 (i.e. A -> A^2 -> A^4 -> A^8 -> ... ), so with B SPs, we can end up with 4*A^(2^B) actions in our hand costing less than 6.

It seems to me that this needs additional support, because every pair of BM and Haggler gives you 4 coins, but 6 are necessary for Fairgrounds. Asymptotically, this would not change a lot I guess, since two-thirds of the cards could still be gained.

Now, we can repeat this second loop for every Golem we started with. Since we started with X BM, H, SP, and got to repeat this loop X times, we went from A to 2^(2^A) X times, starting at X, which is (2↑↑(2X))^X > 8 * 2↑↑(2X). Letting Y = 2↑↑(2X), we can let this be 4Y SPs in hand and 4Y changelings on the top of our deck, and play all the SPs, drawing the 4Y changelings. Then, in our Night phase, we use the Changelings to gain Y each of BM, H, SP, G, topdecking them (putting the scrying pools on top for next turn).

Where do the changelings come from? I could imagine that these could be exchanged tradered silvers, but you mention drawing some silvers and trashing them with Count. 

Logged

bitwise

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +55
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #43 on: November 21, 2018, 04:03:59 pm »
0

Really great work. As far as I understand the growth analysis, it seems fine, but I cannot follow two steps, which are more related to Dominion rules.
If we started with 2A BMs and 2A Hs, doing one step of this loop gains us (2A)^2=4A^2 cards. We can choose this to be 2A^2 BMs and 2A^2 Hs. We can repeat the loop by playing all the Hs then all the BMs again. Even ignoring the Hagglers played in previous steps, one step of this loop changes A to A^2 (i.e. A -> A^2 -> A^4 -> A^8 -> ... ), so with B SPs, we can end up with 4*A^(2^B) actions in our hand costing less than 6.

It seems to me that this needs additional support, because every pair of BM and Haggler gives you 4 coins, but 6 are necessary for Fairgrounds. Asymptotically, this would not change a lot I guess, since two-thirds of the cards could still be gained.
Good catch. It doesn't really matter though, we can do 1 BM per 2 Hagglers for example. Now if we start with 1/3 A BM and 2/3 A H, we get (2/3)*(1/3) A^2 cards to work with. My original solution starts with A and gets 1/4 A^2; this starts with A and gets 2/9 A^2. As you suggested, it could also work to do half BM and half H, but only buy with 2/3 of the BM that we gain, which would end up as 1/6 A^2. Any constant factor for the A^2 is fine and will lead to a A^(c*2^A) after all A steps of the inner loop, for some constant c. We only need the inner loop to be 2^A, so there is a lot of room to work with.

In fact, this loop would work even if we couldn't gain Hagglers midturn-- with something like 12 Hagglers, we can gain BMs only, even with only being able to use one in three of them to buy something. That would reduce one outer loop from X -> 2 ↑↑ 2X to x -> O(1) ↑↑ X, but that would be fine.
 
Now, we can repeat this second loop for every Golem we started with. Since we started with X BM, H, SP, and got to repeat this loop X times, we went from A to 2^(2^A) X times, starting at X, which is (2↑↑(2X))^X > 8 * 2↑↑(2X). Letting Y = 2↑↑(2X), we can let this be 4Y SPs in hand and 4Y changelings on the top of our deck, and play all the SPs, drawing the 4Y changelings. Then, in our Night phase, we use the Changelings to gain Y each of BM, H, SP, G, topdecking them (putting the scrying pools on top for next turn).

Where do the changelings come from? I could imagine that these could be exchanged tradered silvers, but you mention drawing some silvers and trashing them with Count.
In the last step of the outer loop, we don't have to gain BMs and Hs--we can gain any non-victory card costing less than 6 that we want. Just pick some of those to be Changelings.
« Last Edit: November 21, 2018, 04:11:23 pm by bitwise »
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #44 on: November 23, 2018, 02:15:19 am »
0

Very nice! This is some good progress. It got me thinking about the Busy Beaver amount of Coin thread again, where we also achieved triple-up-arrow. The question there is, how many coins can be generated by an n-card deck which can't generate arbitrarily many coins? Coins and VP are mostly synonymous, and with f(n) coins you can pretty much get whatever f(n)-size deck you want. This suggests that if there is a solution for the coin problem achieving the growth rate, then there should be a solution to this VP problem which achieves a fn(2) growth rate, where fn() is f() iterated n times and 2 is a constant.

This suggests that there should be a quadruple-up-arrow solution to the VP problem, arising from the triple-up-arrow solution to the coin problem. However, we don't quite yet have this: the current triple-up-arrow solution for the coin problem involves gaining arbitrarily many cards costing <6, which isn't an issue for that problem because the number of actions (and so the amount of draw) is bounded. But for this problem, we could gain arbitrarily many estates for unbounded VP. The converse seems to be true in this case, though: bitwise's triple-up-arrow solution does give a double-up-arrow solution for the coin problem too.

That said, maybe we can still use this. Suppose we add the landmark wall to the kingdom, so that the estates aren't worth a point anymore. Then as long as we have another way of getting points (I think obelisk on an expensive card or palace both work), it may be possible to use that solution. I'll go see how well that works...

EDIT: the way we gained arbitrarily many cards in the coin solution was to inherit estate as catacombs, trash them with watchtower gaining hunting grounds (reduced cost to zero), trash the hunting grounds for 3x estate, repeat. However, we could gain arbitrarily many duchies in this way, so wall doesn't fix that. Still, maybe we can find another way to gain arbitrarily many cards in a way that excludes duchy and province (and at least one of gold, a potion-cost, or a debt-cost)
« Last Edit: November 23, 2018, 02:54:46 am by liopoil »
Logged
Pages: 1 2 [All]
 

Page created in 0.156 seconds with 20 queries.