Dominion Strategy Forum

Please login or register.

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

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

0 Members and 1 Guest are viewing this topic.

tim17

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 134
  • Respect: +280
    • View Profile
Best Asymptotic Point Scoring
« on: July 06, 2017, 01:18:32 am »
+11

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: +2479
    • 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

  • Jester
  • *****
  • Offline Offline
  • Posts: 823
  • Respect: +739
    • 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

  • Jester
  • *****
  • Offline Offline
  • Posts: 763
  • Respect: +500
    • 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: +353
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 134
  • Respect: +280
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 134
  • Respect: +280
    • 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: +353
    • 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: +2479
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 134
  • Respect: +280
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 134
  • Respect: +280
    • 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: +2479
    • 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

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +72
    • 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: +353
    • 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

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +72
    • 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: +2479
    • 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

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +72
    • 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: +353
    • 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: +2479
    • 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: +2479
    • 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: 348
  • Grand Market = cantrip Woodcutter
  • Respect: +397
    • 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: +2479
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • 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: +2479
    • 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

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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.

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).
« Last Edit: January 29, 2021, 05:27:23 pm by pitythefool »
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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: +2479
    • 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

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • 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

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • 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

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 134
  • Respect: +280
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #36 on: November 21, 2018, 01:41:28 am »
+8

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: 22
  • Respect: +37
    • 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

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3438
  • Shuffle iT Username: faust
  • Respect: +5305
    • 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
You say the ocean's rising, like I give a shit
You say the whole world's ending, honey it already did

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • 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: 22
  • Respect: +37
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #42 on: November 21, 2018, 03:36:47 pm »
+1

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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • 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: +2479
    • 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

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #45 on: November 01, 2020, 01:33:36 pm »
0

I believe that the latest Trader change kills the triple up arrow solution. It had a good run.  :'(
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #46 on: November 08, 2020, 11:47:38 am »
0

I believe that the latest Trader change kills the triple up arrow solution. It had a good run.  :'(

I believe it still works exactly as it did.
Fairgrounds does not have any on-gain ability.
The only difference in the new rules for Trader is that you can process the on-gain of the card you buy before exchanging it for a Silver.  Before, you didn't have that option.  I just tested this in a kingdom with Trader and Ducat.  Now buying a Ducat with Trader and Copper in hand allows you to choose whether to react to the Ducat or Trader first.  If you do Ducat, you can trash the Copper from your hand and then still elect to react with Trader, thus returning the Ducat to the kingdom and gaining a Silver.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #47 on: November 08, 2020, 06:48:42 pm »
0

I'm saying this on the basis that exchanging a card that is being gained from the Black Market deck shouldn't work, and you'll be forced to take the card you were originally gaining. So in our case, our Fairgrounds would get removed from the Black Market deck and we'd stop being able to buy it.

Though, I'm remembering that gaining Horse can be exchanged with Changeling, and that's not from a supply pile, so maybe it does work after all. I've yet to test this with the Black Market / Trader situation on the client.
Logged

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1711
  • Respect: +4335
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #48 on: November 11, 2020, 10:10:44 am »
0

I'm saying this on the basis that exchanging a card that is being gained from the Black Market deck shouldn't work, and you'll be forced to take the card you were originally gaining. So in our case, our Fairgrounds would get removed from the Black Market deck and we'd stop being able to buy it.

Though, I'm remembering that gaining Horse can be exchanged with Changeling, and that's not from a supply pile, so maybe it does work after all. I've yet to test this with the Black Market / Trader situation on the client.

Exchanging just requires a pile, it doesn't have to be a Supply pile, so Horses work. Black Market cards do not have a pile, you can't upgrade Page/Peasant from the BM for instance.
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #49 on: November 11, 2020, 05:11:56 pm »
0

I'm saying this on the basis that exchanging a card that is being gained from the Black Market deck shouldn't work, and you'll be forced to take the card you were originally gaining. So in our case, our Fairgrounds would get removed from the Black Market deck and we'd stop being able to buy it.

Though, I'm remembering that gaining Horse can be exchanged with Changeling, and that's not from a supply pile, so maybe it does work after all. I've yet to test this with the Black Market / Trader situation on the client.

Exchanging just requires a pile, it doesn't have to be a Supply pile, so Horses work. Black Market cards do not have a pile, you can't upgrade Page/Peasant from the BM for instance.

The dominionstrategy.com wiki seems to have some contradictions.  The rules given for exchanging are as you have stated, but is the Black Market deck a pile or not?

Their rules clarifications for Black Market include:

"If you buy a card from the Black Market deck and then use Trader to prevent yourself from gaining it, the bought card goes back on top of the Black Market deck."

I wonder what ShuffleIT has implemented?
Logged

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1711
  • Respect: +4335
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #50 on: November 11, 2020, 09:38:05 pm »
0

I'm saying this on the basis that exchanging a card that is being gained from the Black Market deck shouldn't work, and you'll be forced to take the card you were originally gaining. So in our case, our Fairgrounds would get removed from the Black Market deck and we'd stop being able to buy it.

Though, I'm remembering that gaining Horse can be exchanged with Changeling, and that's not from a supply pile, so maybe it does work after all. I've yet to test this with the Black Market / Trader situation on the client.

Exchanging just requires a pile, it doesn't have to be a Supply pile, so Horses work. Black Market cards do not have a pile, you can't upgrade Page/Peasant from the BM for instance.

The dominionstrategy.com wiki seems to have some contradictions.  The rules given for exchanging are as you have stated, but is the Black Market deck a pile or not?

Their rules clarifications for Black Market include:

"If you buy a card from the Black Market deck and then use Trader to prevent yourself from gaining it, the bought card goes back on top of the Black Market deck."

I wonder what ShuffleIT has implemented?

That particular rule clarification predates the recent Trader errata (note that the current Trader doesn't "prevent yourself from gaining"). You can't Exchange things from the Black Market (see here: http://forum.dominionstrategy.com/index.php?topic=13044.msg483985#msg483985 and some messages below it).
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #51 on: December 22, 2020, 07:10:49 pm »
+2

I believe that the latest Trader change kills the triple up arrow solution. It had a good run.  :'(
I tried to make a replacement for bitwise & paulfc's brilliant 3 up-arrow solution, which now seems invalid due to recent rule changes.  I am using Livery & Falconer in place of Black Market & Haggler.  But even with Mandarin thrown in, it does not achieve 3 up-arrow growth.  It is superior to the other 2 up-arrow solutions in this thread, but it does not lend itself to easy analysis.  I am hoping that working together, we may improve upon it.

Kingdom:  Squire, Changeling, Black Market, Scavenger, Patron, Falconer, Livery, Scrying Pool, Golem
Black Market:  Mandarin, Rogue, Vault, Count, City Quarter, Herbalist
Events:  Travelling Fair, Donate
Landmark:  Obelisk on Livery
Projects:  Capitalism, Academy
Ways:  Way of the Seal, Way of the Turtle, Way of the Mouse -> Hermit

Victory points are generated by Obelisk.

Getting started: (in no particular order):
    buy 2 Black Markets and then buy all the cards from the Black Market
    buy the projects Capitalism and Academy
    buy Seaway (using Quarry) and Training for Livery
    buy 2 Scavengers
    buy lots of Scrying Pools (or alternately Squires and trash them with Donate, gain Scrying Pools)
    buy lots of Liveries, Falconers, and Golems
    buy Donate to trash unwanted cards

Starting deck

     1 Mandarin
     1 Herbalist
     1 Vault
     1 Count
     1 Rogue
     1 City Quarter
     2 Black Markets
     2 Scavengers
     S Scrying Pools
     L Liveries
     F Falconers
     G Golems

I have denoted the start and end of the Black Market treasure phases, to indicate where I play action/treasures as treasures.

Turn start:  (Quarry is in hand, Scrying pool has been set aside as the result of the previous turn)

    play Scrying Pool (from Way of the Turtle), draw entire deck (+action)
    play Herbalist as Way of the Seal

<begin outer loop>
    play Black Market
    <begin Black Market treasure phase>
        play all Liveries
    <end Black Market treasure phase>
    <begin Horse gaining loop>
        play Falconer, gain Patron
            Patron is a four coin card so we gain one Horse for every Livery played this turn (not just those currently in play).
            Patron is a card of three types and thus we can react to gaining it by playing another Falconer from our hand.
        repeat this sequence for all Falconers thus playing them all with just one action.
        (each gained action card comes with +action from Academy.  It should be pretty clear by now that we will never run out of actions.)
    <end Horse gaining loop>
    play Black Market
    <begin Black Market treasure phase>
        play Quarry
    <end Black Market treasure phase>
    For all Horses and Patrons we also have in hand,
        play <action> as Way of the Mouse (Hermit), gain Livery
    (Quarry made 5 coin cards affordable to Hermit, but they do not trigger Liveries to produce Horses.)
    (each gained action card comes with +action from Academy.)
    play Scrying Pool, draw Horses, Patrons, and Liveries
    For all Patrons and all Liveries and all-but-one Horse,
        play <action> as Way of the Mouse (Hermit), gain Livery
    play Scrying Pool, draw Liveries
    <begin main Hermit loop>
        For all Liveries,
            play Livery as Way of the Mouse (Hermit), gain Livery
        play Scrying Pool, draw Liveries
        {Exit loop when only 4 Scrying Pools remain, or 5 Scrying Pools if there is only 1 Golem}
    <end main Hermit loop>
    For all Liveries (one final time),
        play Livery as Way of the Mouse (Hermit), gain Falconer
        play Livery as Way of the Mouse (Hermit), gain Squire
    play Scrying Pool, draw Falconers and Squires
    play Vault, draw <two cards>, discard all but Squires, Scavengers, Golem, Mandarin, and <two cards>
    play Scavenger, topdeck Scrying Pool
    play Scavenger, topdeck Count
    play Golem, reveal Count and Scrying Pool
        play Count, discard <two cards>, trash hand which is just Mandarin and a lot of Squires, gain Scrying Pools for trashing Squires
        play Scrying Pool, draw entire deck (only non-action is Quarry which is in play)
    play Rogue, gain Mandarin from trash,
        topdeck treasures (Quarry, Black Markets, Liveries, Patrons, Count, Rogue, Vault, Scavengers, Herbalist)
        put Quarry and a Black Market on top
    play Horse, draw Quarry and a Black Market
    play Scrying Pool, draw entire deck (Quarry already in hand)
    {Exit outer loop when no Golems remain}
<end outer loop>

    play Black Market
        play all Liveries
    For half of your Falconers,
        play Falconer, gain Patron and Horses, convert all to Changelings and discard.
    For the remaining Falconers,
        play Falconer, gain Patron and Horses, topdeck all
    play Scrying Pool.  Draws all of the topdecked Patrons and Horses up to the first Changeling
    play City Quarter.  Draws all of the Changelings.
    play last Scrying Pool as Way of the Turtle.

Buy Phase:

    play all Patrons
    play Herbalist
    DO NOT play Quarry

    buy Travelling Fair for extra buys as needed
    then spend everything on Liveries, gaining a lot of Horses in the process

Night Phase:
    exchange the Changelings for Golems

Cleanup:
    topdeck the Quarry (by way of Herbalist)
    one Scrying Pool has been set aside (by Way of the Turtle)

Proof of finiteness

Liveries in large number are a powerful force.  If Horses are allowed to gain more cards that produce Horses unimpeded, unbounded loops are easy to create even without the presence of Mandarin.  Add Mandarin and Capitalism and now you have a lot of exploits to plug.  The kingdom ended up being very complicated because of it, due to the addition of necessary interlocks.  Here's the reasoning why play is bounded.

The case of not purchasing Capitalism.

We have only one Mandarin and one Rogue.  To gain the Mandarin, we first have to trash it and then gain it back from the trash with the Rogue.  We can trash it easily with Hermit.  When we gain the Mandarin back, the only thing going back onto the deck will be the Quarry, so the Rogue cannot be played again and we cannot gain the Mandarin back again.  After that, the playing of all cards will be final.  Unbounded play must therefore be predicated on gaining more cards during play.
The only gainers are Hermit and Falconer.
Without the Quarry in play, the Hermit is limited to gaining three coin cards and Falconers are limited to gaining four coin cards.  The Falconers can therefore produce more Horses.  But the number of Falconers in our deck is finite and will run out.  After which we can play actions as a Hermit and only gain cards that cost up to three coins which will not produce any more Horses.
With the Quarry in play, five coin actions are reduced to a cost of three coins and can be gained with Hermit, but they will not produce more Horses.  We can gain more Falconers, but they are limited to gaining cards which cost less than themselves, and their cost has been reduced to three coins.  Eventually we will not be able to gain any more cards.
There is one final way to gain a card; trashing a Squire.  The Rogue is an attack card, but it is not in the supply, so we can only gain Scrying Pools.
Any action played as a Hermit can gain a Squire and trash a Squire and gain a Scrying Pool.  That seems like a gain, but it isn't.  You are losing two cards and  gaining two cards.  It just makes waiting for the end take a lot longer.

The case of purchasing Capitalism.

Hermit can no longer trash the Mandarin, nor the Squires.  The gaining situation is the same as above.  We can gain Horses only when the Quarry is not in play, but we cannot gain any really useful cards unless the Quarry is in play.  Gaining the Mandarin from the trash will return the Rogue and a lot of other useful action/treasures to the stack to be played again but most importantly, it removes the Quarry from play.  The only card that can trash the Mandarin is the Count and only by trashing the entire hand.  That obviously ends play unless triggered by a Golem.  This is limited because Golems are not treasures and they cannot be returned from play and they cannot be gained, only acquired in the Night phase or bought in the final Buy phase.

Analysis

If we play L Liveries and then F Falconers gaining F Patrons, we will gain L*F Horses.
We then turn those L*F Horses and F Patrons into (L+1)*F more Liveries,
and then turn those Liveries into more Liveries, S-4 more times for O(L*F*S) Liveries.
The final Hermit loop converts O(L*F) Liveries into O(L*F*r) Falconers and O(L*F*(1-r)) Squires.  The Squires are converted to Scrying Pools by the Count.
For the next playing of Falconers, L' = O(L*F*S), F' = O(L*F*r), and S' = O(L*F*(1-r)).
To maximize Liveries gained next iteration, we need to maximize L'*F'*S'= O(L*F*S) * O(L*F*r) * O(L*F*(1-r)) = O(L^3*F^3*S*(1-r)*r).
That at least tells us that we should gain Falconers and Squires in equal number so F = S, and that equates to O(L^3*F^4).
The number of Liveries appears to cube itself each time we play a Golem, but not really since the other components do not grow nearly as fast.
Empirical data suggests that the actual exponent of growth for Liveries is ~2.4 (though my spreadsheet could only do 7 iterations before blowing up).

This is repeated for each Golem, with the number of Golems for the next turn equal to half the number of Horses gnerated in the last iteration.
Empirically, G' = ~(L^(2.4*G)^1.7.  That means that overall growth per turn = L^(2.4*[(L^(2.4*G)^1.7]) or thereabouts not even counting the Liveries we end up buying.
The problem is that the exponents aren't in a favorable place.  I believe, overall, it surpasses 2 up-arrows.

For those that are new to up-arrow notation:

If f(x) = x*2, then f(f(f(2)))) = 2*2*2*2 = 2^4 = 2↑4 = 16  "exponentiation"
If f(x) = x^2, then f(f(f(2)))) = ((2^2)^2)^2 = 2^8 = 256
If f(x) = 2^x, then f(f(f(2)))) = 2^(2^(2^2)) = 2↑↑4 = 65536  "tetration"
If f(x) = 2↑↑x, then f(f(f(2)))) = 2↑↑(2↑↑(2↑↑2) = 2↑↑↑4 = ?  "pentation"

Mathematicians have not blessed that second row with a name that I could find.  Bankers would call it "compounding", and if applied to finance, "amortization".

EDIT:  Forget what I said about amortization.  It's just another form of exponentiation.  I don't have any label for that second row.
« Last Edit: January 27, 2021, 08:19:47 pm by pitythefool »
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #52 on: December 29, 2020, 05:17:31 pm »
0

Exciting stuff :D I'll try to take a closer look at the effect on liveries per golem played since that seems a little bit sketchy to me.

If I'm not mistaken, I believe the second row can be referred to as a double exponential function?
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #53 on: January 11, 2021, 07:06:38 pm »
0

... seems a little bit sketchy to me.

I've had a chance to reexamine the analysis.  It was indeed a bit sketchy.
I was maximizing the right expression to find the best ratio of Falconers to Squires, but it was looking an iteration further ahead.  For growth, we should simply look at L' relative to L.  L' was correctly stated as O(L*F*S).
Regardless of the starting values, a couple of Golem iterations leaves the cards in very specific ratios;  F = S = H;  L = F^(sqrt(2))
I wrote a program that reimplemented and verified my spreadsheet.  I took it to 23 Golems.  It verified the exponential growth of Liveries to be 1+sqrt(2), which can be calculated from the relationships above, to eight decimal places: 2.41421356.

Liveries after G Golem iterations is L^(2.414*G).  In the final iteration we do not produce more Liveries but convert half the Horses to Golems for the next turn, so we end a turn with G = L^1.707, so growth can be expressed as L^(2.414*L^1.707)) per turn.

Also, a couple tweaks to the procedure.  For the main Hermit loop, I stated "Exit loop when only 4 Scrying Pools remain, or 5 Scrying Pools if there is only 1 Golem".  However, you can stay in this loop until you are down to 2 Scrying Pools.  The 2nd Scrying Pool will draw the entire deck which includes more Scrying Pools created by the Count when it trashed Squires.
Also, it left a very large number of Horses in our hand at the beginning of the buy phase.  I did not want to play the Quarry since I wanted to gain Horses in the buy phase.  But I could have played the Quarry, played the Horses as Hermits and gained Liveries.  We would not gain Horses for our purchases, but I think having more Liveries for the first iteration is a win.
But I thought of an even better strategy.  Do not play Quarry, but still play the Horses as Hermits and gain Squires.  Then in the buy phase, Donate and trash the Squires to gain Scrying Pools.  While at it, pre-trash the Mandarin as well.  Just a slight catch:  the Quarry which we topdecked gets shuffled again.  We can work around that by setting two Scrying Pools aside with Way of the Turtle and simply take Herbalist out of the kingdom.
This is all insignificant but fun to think about.

EDIT:  Corrected the number of Horses and Golems again.
« Last Edit: January 16, 2021, 08:31:28 am by pitythefool »
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #54 on: January 15, 2021, 06:43:41 pm »
0

This is all insignificant but fun to think about.
Another thing my model has let me discover is the optimum ratio of Falconers-to-Squires to gain.  Earlier analysis had pegged it at 0.5 (equal amounts of each).  This seemed reasonable since they contributed to the increase of Liveries nearly equally and neither Falconers nor Scrying Pools could be returned from play.  It turns out that the algorithm is not sensitive to this value at all.  If you place the ratio at the extremes (close to 0.0 or 1.0), the exponential growth drops off  to about 2.0, but anywhere in between and the growth tends towards 2.414.  But a ratio of 0.689655 gets there just a bit quicker.  It's because Falconers also produce Patrons and Patrons do get returned from play by gaining a Mandarin, hence they repeatedly contribute to gaining more Liveries.

If you start with just 5 Liveries, 5 Falconers, 5 Scrying Pools, and 7 Golems, along with the minimum number of other components, and acquire Falconers/Squires at the 0.5 ratio, you will end up with 3.967*10^310 Liveries.  At a ratio of 0.689655, you end up with 5.742*10^317 Liveries; more than 10 million times as many.  The fact that this isn't really significant is a testimony to how large these numbers are.

If you continue both for a total of 23 Golems the difference in Liveries is 10^(4.132*10^8) versus 10^(4.229*10^8).
Logged

majiponi

  • Jester
  • *****
  • Offline Offline
  • Posts: 823
  • Respect: +739
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #55 on: January 26, 2021, 10:49:35 am »
0

How about this? infinite?

Kingdom: Page, Stonemason, Scrying Pool, Scheme, Watchtower, Philosopher's Stone, Fortress
Landmark: Tomb

Turn:
play Schemed Scrying Pool to draw all
play n Stonemasons to gain 2n Stonemasons (topdeck)
play Hero to gain Philosopher's Stone (topdeck)
play Scrying Pool to discard Philosopher's Stone to draw all
play Stonemason to gain 2 Scrying Pool
play 2n-1 Stonemasons to gain 4n-2 Stonemasons
repeat this until you have no Hero in hand
play all Pages, Treasure Hunters, Warriors to draw all
play Stonemasons to gain Pages
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #56 on: January 27, 2021, 08:21:22 pm »
0

play Hero to gain Philosopher's Stone (topdeck)

There have been a lot of Scrying Pool/Stonemason engines posted here.  I really like the usage of Hero, though.  That's novel.  It takes 3 turns for gained Pages to be used as Heroes though.  That really dampens the growth.  Imagine that you could buy Heroes directly and use them the very next turn.  And also, imagine that they generate 3.5 Scrying Pools instead of just two.  Then the growth would be on par with an engine I posted in this thread earlier [Reply #24 on: November 10, 2018, 11:12:10 pm].

But having said that, I like when people post new ideas and yours has potential.  It has two things going for it that I see.
One:  Warriors produce a lot of coin.  Try calculating how much (and remember that Scrying Pools are also attack cards).  Once again, though, you would be looking at a two turn delay in Warrior growth;  training on Stonemason may generate more.
(EDIT:  I confused Warrior with Soldier)
Two:  With Capitalism purchased, Hero is considered a treasure and may be returned to your deck by gaining a Mandarin.  Unfortumately, I can not come up with any way to limit Mandarin gains, in this kingdom, off the top of my head.
« Last Edit: January 28, 2021, 12:28:45 pm by pitythefool »
Logged

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1711
  • Respect: +4335
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #57 on: January 27, 2021, 08:31:38 pm »
0

play Hero to gain Philosopher's Stone (topdeck)

There have been a lot of Scrying Pool/Stonemason engines posted here.  I really like the usage of Hero, though.  That's novel.  It takes 3 turns for gained Pages to be used as Heroes though.  That really dampens the growth.  Imagine that you could buy Heroes directly and use them the very next turn.  And also, imagine that they generate 3.5 Scrying Pools instead of just two.  Then the growth would be on par with an engine I posted in this thread earlier [Reply #24 on: November 10, 2018, 11:12:10 pm].

But having said that, I like when people post new ideas and yours has potential.  It has two things going for it that I see.
One:  Warriors produce a lot of coin.  Try calculating how much (and remember that Scrying Pools are also attack cards).  Once again, though, you would be looking at a two turn delay in Warrior growth;  training on Stonemason may generate more.
Two:  With Capitalism purchased, Hero is considered a treasure and may be returned to your deck by gaining a Mandarin.  Unfortumately, I can not come up with any way to limit Mandarin gains, in this kingdom, off the top of my head.

Warrior doesn't make money, that's Soldier.
Logged

majiponi

  • Jester
  • *****
  • Offline Offline
  • Posts: 823
  • Respect: +739
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #58 on: January 28, 2021, 11:21:37 am »
0

play Hero to gain Philosopher's Stone (topdeck)

There have been a lot of Scrying Pool/Stonemason engines posted here.  I really like the usage of Hero, though.  That's novel.  It takes 3 turns for gained Pages to be used as Heroes though.  That really dampens the growth.  Imagine that you could buy Heroes directly and use them the very next turn.  And also, imagine that they generate 3.5 Scrying Pools instead of just two.  Then the growth would be on par with an engine I posted in this thread earlier [Reply #24 on: November 10, 2018, 11:12:10 pm].

But having said that, I like when people post new ideas and yours has potential.  It has two things going for it that I see.
One:  Warriors produce a lot of coin.  Try calculating how much (and remember that Scrying Pools are also attack cards).  Once again, though, you would be looking at a two turn delay in Warrior growth;  training on Stonemason may generate more.
Two:  With Capitalism purchased, Hero is considered a treasure and may be returned to your deck by gaining a Mandarin.  Unfortumately, I can not come up with any way to limit Mandarin gains, in this kingdom, off the top of my head.

The idea is non-Kingdom cards avoids infinity.  Your Expanding post is nice, but using Platinum/Colony will spoil it (Stonemason Expand to Gold, Expand Gold to Platinum, Stonemason Platinum to 2 Provinces, Stonemason them to 4 Expands). I first tried Tragic Hero, went inf. Next Treasurer, inf. Then, Mint, inf. Then I realized that depending Kingdom cards creates infinite loops too often. That's why I posted Heroes idea.
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #59 on: January 28, 2021, 12:27:13 pm »
0

play Hero to gain Philosopher's Stone (topdeck)

There have been a lot of Scrying Pool/Stonemason engines posted here.  I really like the usage of Hero, though.  That's novel.  It takes 3 turns for gained Pages to be used as Heroes though.  That really dampens the growth.  Imagine that you could buy Heroes directly and use them the very next turn.  And also, imagine that they generate 3.5 Scrying Pools instead of just two.  Then the growth would be on par with an engine I posted in this thread earlier [Reply #24 on: November 10, 2018, 11:12:10 pm].

But having said that, I like when people post new ideas and yours has potential.  It has two things going for it that I see.
One:  Warriors produce a lot of coin.  Try calculating how much (and remember that Scrying Pools are also attack cards).  Once again, though, you would be looking at a two turn delay in Warrior growth;  training on Stonemason may generate more.
Two:  With Capitalism purchased, Hero is considered a treasure and may be returned to your deck by gaining a Mandarin.  Unfortumately, I can not come up with any way to limit Mandarin gains, in this kingdom, off the top of my head.

The idea is non-Kingdom cards avoids infinity.  Your Expanding post is nice, but using Platinum/Colony will spoil it (Stonemason Expand to Gold, Expand Gold to Platinum, Stonemason Platinum to 2 Provinces, Stonemason them to 4 Expands). I first tried Tragic Hero, went inf. Next Treasurer, inf. Then, Mint, inf. Then I realized that depending Kingdom cards creates infinite loops too often. That's why I posted Heroes idea.

Yes, I do like the Hero.  It does plug a lot of loopholes not being in the Kingdom.
It turns out that the Expand approach is flawed, and you don't even need Platinum/Colony.  Province will suffice as I pointed out way back here in a post about an improved kingdom.
  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.

And yes, I was totally wrong about Warriors.  (Thanks Mic Qsenoch)  There's so many cards now I have trouble remembering them all.  Shame on me for not double checking.

Logged

majiponi

  • Jester
  • *****
  • Offline Offline
  • Posts: 823
  • Respect: +739
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #60 on: January 28, 2021, 09:38:02 pm »
0

It turns out that the Expand approach is flawed, and you don't even need Platinum/Colony.  Province will suffice as I pointed out way back here in a post about an improved kingdom.
  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.

Stonemason Golds to Expands?
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #61 on: January 29, 2021, 07:14:34 am »
0

It turns out that the Expand approach is flawed, and you don't even need Platinum/Colony.  Province will suffice as I pointed out way back here in a post about an improved kingdom.
  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.

Stonemason Golds to Expands?
Some days, I can't seem to get my foot out of my mouth.  The quote was from a kingdom that considered using Ferry.  Without the price reduction, it would be Expand Fortress to Gold, Expand Gold to Province, Stonemason Province to 2 Expands.  And that would yield no gain.  So the kingdom in the original thread was valid after all, since it did not contain Platinum/Colony.  Now I have to go edit it again.
Logged

majiponi

  • Jester
  • *****
  • Offline Offline
  • Posts: 823
  • Respect: +739
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #62 on: January 29, 2021, 09:53:18 am »
0

It turns out that the Expand approach is flawed, and you don't even need Platinum/Colony.  Province will suffice as I pointed out way back here in a post about an improved kingdom.
  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.

Stonemason Golds to Expands?
Some days, I can't seem to get my foot out of my mouth.  The quote was from a kingdom that considered using Ferry.  Without the price reduction, it would be Expand Fortress to Gold, Expand Gold to Province, Stonemason Province to 2 Expands.  And that would yield no gain.  So the kingdom in the original thread was valid after all, since it did not contain Platinum/Colony.  Now I have to go edit it again.

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

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #63 on: January 29, 2021, 05:24:30 pm »
0

It turns out that the Expand approach is flawed, and you don't even need Platinum/Colony.  Province will suffice as I pointed out way back here in a post about an improved kingdom.
  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.

Stonemason Golds to Expands?
Some days, I can't seem to get my foot out of my mouth.  The quote was from a kingdom that considered using Ferry.  Without the price reduction, it would be Expand Fortress to Gold, Expand Gold to Province, Stonemason Province to 2 Expands.  And that would yield no gain.  So the kingdom in the original thread was valid after all, since it did not contain Platinum/Colony.  Now I have to go edit it again.

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.

You're absolutely right.  That kingdom is busted.  I'll go edit it for a third time.
I clearly had that problem in mind while working on the followup kingdom, but I somehow didn't connect it to the earlier kingdom.

Hero is looking better all of the time!
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #64 on: February 22, 2021, 08:14:24 pm »
0

TLDR:  A simpler Mandarin/Scrying Pool engine that overpays for Masterpieces to make Conquest points with increases of N^(4*N^2) per turn.


Kingdom:  Black Market, Forager, Masterpiece, Priest, Changeling, University, Scrying Pool, Cultist, Mandarin
Black Market:  Scheme, Fortress, Watchtower
Events:  Seaway, Conquest
Projects:  Capitalism

Victory points are generated by Conquest.

Getting started: (in no particular order):
    buy 1 Black Market and all the cards from the Black Market
    buy the project Capitalism
    buy Seaway for Forager
    trash all Copper and Estates and Potions

Starting deck

     1   Black Market, Cultist, Scheme, Fortress, and Watchtower
     N   Foragers
     N   Priests
     N   Universities
     N+1 Scrying Pools

loop start
    play Scrying Pool, draw entire deck (nothing but actions)
    play Black Market (so we can play Priests and Foragers without requiring actions)
    play all Priests, trashing the Fortress
    play all Foragers, trashing the Fortress
    play University, gain Mandarin (the Black Market and all Priests and Foragers are returned from play)
repeat until one University remaining
    do the loop a final time, but exchange one Silver the Mandarin for a Changeling
    play the last Scrying Pool, drawing all the cards on the stack and then the Changeling
    play Black Market and all Priests and Foragers as before
    play Scheme (drawing nothing)
    play Cultist (drawing nothing)

buy phase
    buy Masterpiece, overpaying by all of the coins you have
        reveal Watchtower, trash Masterpiece and all Silvers for coin benefit.
    repeat until only two buys left
    buy Masterpiece, overpaying by all of the coins you have except six, exchange Masterpiece and all Silvers for Changelings
    buy Conquest, exchange Silvers for Changelings

night phase
    trash the Changeling in hand, gain a Cultist, reveal Watchtower and trash, draw 3 Changelings
    repeat, thus trashing a third of the Changelings, but drawing the other two thirds to the hand
    trash all Changelings, gaining equal numbers of Universities, Scrying Pools, Priests, and Foragers.*

*(Gaining equal numbers is not best but it exhibits uniform growth and simplifies the math. More Foragers are preferred but the optimal ratio is not a constant.)

cleanup
    put a Scrying Pool on top of your deck (due to Scheme)

Proof of finiteness.

    All phases are limited.
    Action phase:  The only gainer is University which cannot gain itself and cannot be returned from play.  When the last one is played, all other cards can only be played one more time.
    Buy phase:  Additional buys cannot be bought in the buy phase.
    Night phase:  Changelings cannot gain any card that yields more than one card costing more than three coins, when gained or trashed.

Analysis:

    N Priests are played N times each generating O(N^4) coins.  The benefit for trashing a card reaches 2*N^2 coins.  The last play of the Foragers thus adds O(N^3) coins, but this is not significant.  Spending all of it on a Masterpiece and then trashing all gained cards effectively multiplies the wealth by 2*N^2.  That is repeated for every buy up until the last.
    N Foragers played N times each yields 2*N^2 buys.  All Silvers trashed or exchanged for Changelings are still considered "gained".
So the purchase of Conquest yields O[(N^4)*(2*N^2)^(2*N^2)] = O(N^(4*N^2)).  Universities, Scrying Pools, Priests, and Foragers increase by the same order.

« Last Edit: February 27, 2021, 07:29:20 am by pitythefool »
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #65 on: February 26, 2021, 08:08:36 pm »
0

TL;DR: +Ironworks -Forager +Squire should still be finite and boost it up to N -> (2^(2^(2^N))).

Looks neat! I'm a little confused at the end of the Buy phase since Conquest should only give 2 silvers, which of course can be remedied by exchanging instead of trashing on the second-to-last buy and leaving 6 money to buy the Conquest last. (Also, you only need to do this on the last turn anyway.) This shouldn't affect any of the calculations, of course.

I think we can improve this by removing Forager and adding Ironworks (which gets Seawayed), which is a gainer that works with Capitalism but can't gain Mandarins (or Scrying Pools or Universities). Since Ironworks can gain a copy of itself, we have to be careful that this doesn't introduce any infinite loops. I believe this is okay because

1. You cannot gain Scrying Pools or Universities mid-turn (or take them out of play).
2. Without using a University, you cannot gain a Cultist or Mandarin midturn, and cards stay in play.
3. Without playing Scrying Pool or University, the only plays that don't decrease handsize are playing our single Scheme/Fortress/Watchtower, trashing a Cultist, or playing a Cultist, or playing an Ironworks on Estate. We have a finite bound on all these actions besides the Ironworks play. The Ironworks play strictly decreases the number of "available" (in hand + deck + discard) Ironworks. No other play (besides playing University) can increase the number of available Ironworks.

With this, the action phase loop looks like:

play Scrying Pool, drawing entire deck
play Black Market
  play all Priests, trashing the Fortress
  play all Ironworks, gaining either Priest or Ironworks (I think the best thing is all Ironworks until the second-to-last loop where you get some ratio of Priests)

(The last loop is analogous to pitythefool's solution, as are the remaining phases.)

Analysis:
At the start of the turn, say we have:
  N       Ironworks
  <= N Priests (exact amount doesn't really matter)
  U       Universities
  U+1   Scrying Pools
Every time we play a Pool and University, we double the amount of Ironworks, and on the last step we can give ourselves an equal number of Ironworks and Priests, giving 2^U * N Ironworks and 2^U * N Priests. Let's just set U=N to simplify, so that we have N * 2^N Priest plays then N * 2^N Ironworks plays, giving us on the order of $(N^2 * 4^N) and (N * 2^N) buys.
Every Masterpiece buy/trash multiplies the wealth by N * 2^N, so our total wealth before the end of the buy phase is on the order of
  (N^2 * 4^N) * (N * 2^N)^(N* 2^N) ~ (N*2^N)^(N*2^N) < (2^N)^(2^N) < 2^(2^N).
So we can grow from N -> 2^(2^N) every turn. I'm a little confused where this puts us in growth rate at the moment.

---

So another thing I think we can do is add Squire and trash it for midturn Scrying Pool gains. Then our finiteness argument should be like

1. You cannot gain Universities mid-turn (or take them out of play).
2. Supposing you do not play any Universities, every card you play does not increase the number of available (Scrying Pool + Cultist + Squire + Priest + Ironworks) that you have.
3. Increasing your handsize strictly decreases this availability count.
4. Besides playing your single Scheme, Fortress, or Watchtower, every action you can do either strictly decreases your hand size or your total availability count (or both).

In this proposed loop, I'm going to ignore +Actions since we aren't using it as a limiting resource and could fix it with Academy or maybe Lost Arts on Ironworks. The loop should look like

Draw deck (with scrying pool)
inner loop start
  Requirement: Hand has at least 1 Scrying Pool. If not the last loop before a University, hand has at least 2 Scrying Pools or 1 Scrying Pool, 1 Priest, 1 Squire.
  Play all Ironworks, gaining either Ironworks, Priest, or Squire. (In most loops, almost every gain is for Ironworks. Replace with a Priest/Squire gain if needed to make the above condition satisfied.)
  If not the last loop before a University:
    If there is only 1 Scrying Pool in hand, first Priest to trash a Squire, gaining Scrying Pool. Either way, play a Scrying Pool.
  If the last loop before a University (only 1 Scrying Pool in hand, and don't have Priest + Squire):
    end inner loop

Outer loop
  Do inner loop until it ends (note: in the inner loop for the last iteration of the outer loop (no Universities left), be sure to gain lots of Priests and play them too.)
  Play University

Analysis for this:
To simplify, let's just say we have N each of Ironworks and Universities to start, and some negligible amount of Scrying Pools, Priests, and Squires. Once we have 1 Scrying Pool, 1 Priest, 1 Squire left, each inner loop will have to spend two gains on Squire and Priest, and the rest on Ironworks. So if we have X Ironworks to start, we'll end up with X-2 Ironworks on the next iteration. Iterating until the resources are exhausted, we'll have gained/played around X^2/2 Ironworks total. So every full outer loop takes our Ironworks from X->X^2/2. We will do this N times, once for each University.
N iterations of this starting from 1 gives us O(2^(2^N))) at the final iteration. Of course, we're starting at N, not 1, but this will not increase the asymptotics very much.
With 2^(2^N) Priest plays and 2^(2^N) buys, we will wind up with a N -> (2^(2^N))^(2^(2^N)) < 2^(2^(2^N)) growth per turn.
« Last Edit: February 26, 2021, 09:28:03 pm by bitwise »
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #66 on: February 27, 2021, 07:42:17 am »
0

TL;DR: +Ironworks -Forager +Squire should still be finite and boost it up to N -> (2^(2^(2^N))).

Looks neat! I'm a little confused at the end of the Buy phase since Conquest should only give 2 silvers, which of course can be remedied by exchanging instead of trashing on the second-to-last buy and leaving 6 money to buy the Conquest last. (Also, you only need to do this on the last turn anyway.) This shouldn't affect any of the calculations, of course.
Yes, that was written poorly by me.  But you managed to interpret it correctly.  I have edited the post to correct that and one other mistaken remnant from an earlier version.

Quote
I think we can improve this by removing Forager and adding Ironworks (which gets Seawayed), which is a gainer that works with Capitalism but can't gain Mandarins (or Scrying Pools or Universities).
I had considered Squire, but not in combination with another gainer.  Awesome work.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +143
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #67 on: February 27, 2021, 02:29:20 pm »
0

A N -> (2^(2^(2^N))) growth should amount to f(n) = 2 ↑↑ 3n growth, which seems like the best so far if I'm understanding correctly. The triple up arrow seems elusive again though :(

Great work on your part as well! I think it's a lot harder to build out the solution from nothing than to try to improve it. :P
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #68 on: May 16, 2021, 10:37:56 am »
0

This is not like my usual posts.  I will be posting a new engine next, but it will use some extreme mechanisms that many of you may be unaware of and I thought it would be best to explain them and other findings first.


Ways and means

I am fond of Capitalism.  It transforms a lot of useful actions into action/treasures which allows you to play them in treasure phases.  Many people misunderstand how this interacts with Ways.  If I play an action/treasure as a treasure, I am still playing a card that is an action.  As such, I can elect to play it as a Way.  The Way does not change the type of the card, it only changes the action taken when playing it.  A discussion of this can be found here; https://www.reddit.com/r/dominion/comments/g16wdr/capitalism_with_ways, where Donald X. himself weighs in with: "Ways do not change card text; they do not affect what cards Capitalism applies to."


There's a fine line dividing an action and its effect

Playing an action as a Way does not change any special effect listed on the card below a dividing line, only the action above it.  If I play an Herbalist as Way of the Ox, I can still topdeck a treasure when I discard the Herbalist.  With Capitalism in effect, I can even elect to topdeck the Herbalist itself.  On the other hand, if I play a Scheme as Way of the Ox, I lose the ability to topdeck an action card from play at cleanup since that is granted by the action of the card, not as an effect (e.g above the line versus below the line).


A dog is a man's best friend

Specifically a Sheepdog.  Whenever you gain a card, you can elect to play a Sheepdog from your hand.  Drawing two cards can sometimes be useful in an engine, but why is it so great?  It isn't so much the effect of the card, but the fact that you can play it whenever you gain another card.  There are probably a lot more useful action cards that you wish had the ability to be played like this.  Well, you can achieve it if the kingdom has Way of the Mouse with Vassal as the action card set aside.  Now when you gain, say, a Scrying Pool, topdeck it, reveal Sheepdog from your hand, elect to play it, play it as Way of the Mouse, Vassal then discards the Scrying Pool, and you can elect to play it.  Sheepdog partnered with Way of the Mouse/Vassal can thus enable practically any engine in any turn phase.


Temporal association of Buy & Haggle

Capitalism is strongest in combination with Mandarin.  I like to use a lot of Hagglers to gain a lot of action/treasure cards including a Mandarin and watch a lot of cards get returned to the top of my draw pile.  I used to think that the Mandarin had to be gained last, since it would remove the Hagglers from play and the Haggle effect is while-in-play, and then I wouldn't be able to gain more cards, but this is not so.  As soon as a buy is made, all Hagglers in play are activated to gain a card and you can choose the cards to be gained in any order.
Even more surprising is that the Hagglers do not even need to be played before a card is bought.  If you can manage to play a Haggler while the when-buy is still being processed, you can haggle a card after the buy.  This is similar to being attacked and reacting with a Caravan Guard.  If you draw another Caravan Guard, you can play that too even though it was not in your hand when the attack card was played.
I've already revealed Way of the Mouse (Vassal) and this is the easiest way to achieve the effect.

With a hand of four Hagglers and four Sheepdogs:

    play all Hagglers
    buy Travelling Fair (for topdecking)
    buy a Gold
        from Hagglers
            gain a Haggler and topdeck it
                reveal Sheepdog and play it as Way of the Mouse (Vassal)
                    Vassal plays Haggler
            gain a Haggler and topdeck it
                reveal Sheepdog and play it as Way of the Mouse (Vassal)
                    Vassal plays Haggler
            gain a Haggler and topdeck it
                reveal Sheepdog and play it as Way of the Mouse (Vassal)
                    Vassal plays Haggler
            gain a Haggler and topdeck it
                reveal Sheepdog and play it as Way of the Mouse (Vassal)
                    Vassal plays Haggler
            gain a Haggler and topdeck it
            gain a Haggler and topdeck it
            gain a Haggler and topdeck it
            gain a Haggler and topdeck it
        gain the Gold

From four Hagglers, we have gained eight more.  Could we have done better?  Yes, quite a bit if Capitalism and Mandarin are in the kingdom.  The Haggle effect of Haggler is "below the line".  We could play the Haggler as a Way and the Haggle effect would still happen.

    play all Hagglers
    buy Travelling Fair (for topdecking)
    buy a Gold
        from Hagglers
            gain a Haggler and topdeck it
            gain a Haggler and topdeck it
            gain a Haggler and topdeck it
            gain a Haggler and topdeck it
                reveal Sheepdog and play it as Way of the Mouse (Vassal)
                    Vassal plays Haggler
                        play Haggler as Way of the Mouse (Vassal)
                            Vassal plays Haggler
                                play Haggler as Way of the Mouse (Vassal)
                                    Vassal plays Haggler
                                        play Haggler as Way of the Mouse (Vassal)
                                            Vassal plays Haggler
                                                play Haggler as an actual Haggler
                                                4th Haggler finished
                                        3rd Haggler finished
                                2nd Haggler finished
                        1st Haggler finished
                This concludes the Sheepdog-Vassal chain.
        <return to when-buy processing>
            from Hagglers just played
                gain a Mandarin
                    all Hagglers are returned to the top of the deck
                gain a Haggler and topdeck it
                gain a Haggler and topdeck it
                gain a Haggler and topdeck it

    We now have 7 Hagglers on our deck.  Reveal another Sheepdog and do it again, this time ending with 13 Hagglers.
    The 3rd Sheepdog ends with 25 Hagglers and the 4th with 49.

    Surprisingly, most of the cards were gained with Hagglers that were still in the supply when the purchase was made and some were not even in play when the haggles were exercised.  This scenario has been verified on ShuffleIT (as with everything mentioned here) and can be achieved, or at least could be if the kingdom contained more than 10 Hagglers.

    Can we do better yet?  Yes.  It is possible to gain an unbounded number of Hagglers.  I leave it for you to ponder.  Hint: gain more Sheepdogs.


Other ways to trigger actions

    Falconer can also be played when a card is gained.  But the card must be of at least two types, so it is more restrictive.  Though both Sheepdog and Falconer can be triggered by gaining themselves.
    A Noble Brigand does not get played when gained.  The new wording is simply "When you buy this, do its attack".
    Village Green may be played, not when gained, but when discarded other than at clean up.  Doctor overpay and Exile mechanics are a good way to limit that.


Delayed gratification

    Why didn't the Hagglers played above immediately grant the gaining of a card?  When a when-buy effect is being processed, no other when-buy effects can be processed until the first one is completed.  The Hagglers are registered as being played during the buy, but do not take effect until when-buy processing is resumed.  This is especially disheartening for Doctor overpay.  Overpaying for a Doctor is considered a when-buy effect.  If you have other when-buy effects to process (such as Hagglers in play), you will be granted the option of choosing the order in which to process them.  When you choose overpay, you must use up all of the overpay credit before processing any other when-buy effects.


No two-for-one specials

    If you Throne Room a Haggler after the buy, you do not get two cards, only one.  It is the act of putting the Haggler in play, not playing it, that causes the effect.


The art of the deal

    Where does the art of haggling come in?  It seems you have no say in determining the price of a haggled card.  Or do you?  When you play a Haggler during a when-buy period, the price point of the gained card is set at the time the Haggler is processed.  This is not necessarily the cost of the card at the time the original buy was made, nor the price of the card when the Haggler was put in play.  For example, if I buy a Farmland (which has its own when-buy effect), then manage to play a Bridge, then a Haggler, and then another Bridge, and then return to when-buy processing, I'll be asked to gain a card cheaper than four coins.  Not the six coins I paid for Farmland, nor the five coins it would have cost when I played the Haggler.
    The price adjustments are applied to the card we bought and the card we can gain equally.  So it appears we do not gain any advantage for all of our effort.
You can also go the other way and it behaves the same; play a Quarry and two Hagglers, then buy a Grand Market for four coins.  For the first Haggler, we can gain a card cheaper than four coins.  Choose a Mandarin and the Quarry is removed from play.  For the second Haggler, we are asked to gain a card cheaper than six coins.  It does not change our selection of action cards that can be gained.  But maybe you wanted a Venture, in which case you at least saved two coins when buying the Grand Market.
    There are four cards whose price CAN be manipulated when using Hagglers.  See http://forum.dominionstrategy.com/index.php?topic=7339.msg866270#msg866270 for a fun puzzle.


Curses, foiled again

    One when-buy event that cannot be triggered after the buy is Embargo.  If you buy a card then manage to play an Embargo on its supply pile during the when-buy processing, you do not gain a curse.  This seems inconsistent with other when-buy processes but it relates to Embargo's wording "For the rest of the game, when a player buys a card, ..."


Doctor, Doctor, give me the news

    While playing with Doctor, I came to realize that the overpay effects are greatly underrated.  An example is a deck that contains a single Tunnel.  Buy a Doctor and overpay by 1000 coins.  Discard the Tunnel, reveal it, gain a Gold.  Next we will reshuffle and encounter either the Tunnel again or the Gold.  Keep trashing Gold and discarding the Tunnel and this sequence can continue until the overpay runs out.
   With topdecking and good strategy, you can prepare a sequence of cards for the Doctor to encounter before buying it.  Squire, Cultist, Catacombs, and Hunting Grounds all have useful effects when trashed and there are others.  Another powerful card to consider here is Village Green.  When discarded, you can elect to play it.  And of course, that invites playing it as a Way.  There are also over two dozen cards that have a side effect when gained and other while-in-play effects you can establish beforehand.
    It is possible to create an engine that runs during a Doctor buy.  It has have the advantage of being bounded by its nature.  You must overpay by a finite amount up front and cannot extend it while the engine is running.  If you play Hagglers in the engine, you are restricted to gaining cards that cost less than a Doctor.  These are very handy restrictions when trying to prevent an engine from running unbounded.


Vassal and Village Green; a powerful combo

    When a Village Green is discarded, you can elect to play it.  When you play a Vassal, it first discards the card on top or your deck, and then if it is an action, you can play it.  So when a Vassal discards a Village Green, you can play the Village Green twice.
    When you pair this effect with Way of the Mouse/Vassal, powerful sequences can be built up.  If you have N Village Greens on your deck and you discard the first one with a Vassal and elect to play it also as a Vassal, then you get to play the second Village Green twice before playing the first one a second time.  If you thus chain through all N Village Greens, you will have N+1 Village Green actions to resolve.  Let's call them VG credits.  And for each VG credit you can either play the Village Green as normal to draw the top card of your deck into your hand and gain two actions, or play the Village Green as a Vassal to either discard the top card of your deck or play it if it is an action.  If you can somehow gain and topdeck more Village Greens, you can increase your Village Green credits and keep the engine running.
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #69 on: May 16, 2021, 04:51:26 pm »
0

If you are having trouble following some of the play, it may help to read my earlier post.

Kingdom:  Black Market, Village Green, Mandarin, Forum, Royal Carriage, Haggler, Border Village
Black Market:  Druid, Watchtower, Scheme, Treasurer
Boons for Druid are Forest's Gift (+coin, +buy), Flame's Gift (trash a card), and Field's Gift (+action, +coin)

Event:  Training
Landmark:  Obelisk on Haggler (for Victory points)
Project:  Capitalism
Way of the Mouse: Vassal

getting started

    buy all Black Market cards
    buy the project Capitalism
    buy Training for Haggler
    trash all unwanted cards and the Mandarin with Flame's Gift

starting deck

    1 Druid, Watchtower, Scheme, Scrying Pool, Treasurer.  (Mandarin in trash)
    many Hagglers
    many Royal Carriages

action phase

    play Scrying Pool, draw deck
    play Scheme, draw nothing
    play all Royal Carriages
    play Druid, select Forest's Gift (always)
        call all Royal Carriages, replaying Druid

treasure phase

    play Treasurer, gain Copper from trash, reveal Watchtower, trash Copper
    play all Hagglers

buy phase

    buy Transport
        exile a Village Green

    buy Border Village
        from N Hagglers,
            gain Mandarin,
                topdeck Treasurer and all Hagglers
            gain N-1 Village Greens (topdeck)
                after gaining the last Village Green, discard the Village Green from exile
                    play discarded Village Green as Way of the Mouse: Vassal
                        play topdecked Village Green as Way of the Mouse: Vassal
                            repeat for all topdecked Village Greens
                                ...
<start of Haggler chain>
                                play Haggler as Way of the Mouse: Vassal
                                    play Haggler as Way of the Mouse: Vassal
                                        repeat for all topdecked Hagglers
                                            ...

                                            play Treasurer, gain Mandarin from trash and trash it again
                                                topdeck Treasurer and all Hagglers
<repeat Haggler chain N times>
    The Nth time through the loop, we play the Haggler chain up to the Treasurer, then discard the Treasurer without playing it.
    The Village Green chain is thus completed, returning us to when-buy processing.
    Post-buy Hagglers now kick in.
        We have played N Hagglers N times each, so we stand to gain N^2 cards.
            gain N^2 Hagglers and topdeck them
        gain the Border Village
            gain a Haggler (topdeck)

    buy Transport
        exile a Village Green

    buy Forum
        from Hagglers,
            gain all Village Greens and topdeck them

Forums grant an extra buy when buying them, so we can keep buying them.  Reserve 6 coins, but keep buying Forums and loading the deck with Village Greens till the money runs out.

    buy Border Village
        from M Hagglers,
            gain M-2 Hagglers (topdeck)
            gain 1 Mandarin,
                topdeck all Hagglers
            gain 1 Village Green (topdeck)
                after gaining the Village Green, discard the Village Green from exile
                    play discarded Village Green as Way of the Mouse: Vassal
                        play topdecked Village Green as Way of the Mouse: Vassal
                            play Haggler as Way of the Mouse: Vassal
                                play Haggler as Way of the Mouse: Vassal
                                    repeat for all topdecked Hagglers
                                        ...
                            We will eventually run into all of the Village Greens, play them as Vassals too, continuing the chain.
                            If we encounter Forums or Border Villages, play them as Vassals to continue the chain.
                            The last Vassal will draw the Treasurer from the discard pile, play it and gain and trash the Mandarin.
                            Then all the treasures in play get restacked onto the deck and we do it all again.
                            Keep repeating this sequence, discarding the Treasurer with the last Village Green credit.

        with post-buy Hagglers,
            gain Hagglers and topdeck them
        gain the Border Village
            gain a Haggler (topdeck)

    buy another Transport, more Forums, and then repeat by buying another Border Village

We eventually run out of buys.
When the last Border Village is bought, use the post-buy Hagglers to gain Royal Carriages instead of Hagglers.
At cleanup, topdeck the Scrying Pool (from playing Scheme)

Proof of finiteness

    The two possibilities for unbounded play are gaining an unbounded number of cards or repeatedly playing the same cards an unbounded number of times.
The only gainers are a single Treasurer which can only regain a card from the trash, Black Markets, and Hagglers.  Black Markets can only gain cards from the Black Market deck which is finite, so gaining from there cannot be sustained.  Hagglers can only gain cards when you buy something, so they cannot contribute to unbounded play in the action phase.  If the Treasurer is played and does not gain the Mandarin from the trash, it cannot be replayed in the action phase, so that also does not help.  There are other ways to gain Mandarins in the buy phase, but not in the action phase.  It is possible to gain multiple treasure cards from the trash by combining the play of the Treasurer with replays via Royal Carriages.  But it only gains treasures from the trash, so it is limited to what you can put into the trash.  Also, the Royal Carriages cannot be replayed, hence this is also not sustainable.
    The only cards that can draw cards are Border Village, Forum, Village Greens, the single Scheme, and even Watchtower.  None of these are considered treasures under Capitalism and hence cannot be replayed.  But we have introduced the Way of the Mouse: Vassal as a way of playing cards without drawing them.  Indeed, it is now more convenient to play the cards right off our stack.  Doing so in the action phase is of no benefit, since we could play them normally.  Doing so in the buy phase requires discarding a Village Green.  There are only two ways to do this; playing a Forum or discarding one from exile.  Playing a Forum doesn't help since we need to first discard a Village Green to allow us to play a Forum so we can discard a Village Green.  Simple chicken and egg problem.  That only leaves discarding a Village Green from exile.  You must first exile a Village Green and every time you do that requires buying a Transport.
    The buy phase is limited in part because the number of buys are limited.  The single Druid is the only way to obtain buys.  We can gain more Royal Carriages but  cannot play them on the Druid except immediately after.  There is one exception to the limited buys and that is buying Forums.  We can buy as many Forums as we can afford and that is the clincher.  We always run out of money.  There is no way to gain coin in the buy phase without playing actions (which would require buying another Transport).
    A Forum is five coins.  A Haggler is five coins.  We cannot gain more Hagglers when buying Forums.  We can gain more Village Greens, which is mainly the point.  These can trigger the playing of actions, including the replaying of Hagglers.  But the action chain must stop before the Hagglers take effect.  In other words, you can only gain more cards after the ability to play them is gone.  To start another action chain requires buying another Transport.  Or we could trigger actions just to play them as Vassals and earn more coins.  More coins allows us to buy more Forums, but to repeat such a sequence for another Forum buy would require another Transport buy first.  So no engine can be sustained indefinitely.


Analysis

    We start a turn with N number of Hagglers and N^3 number of Royal Carriages.  Each Royal Carriage earns us 2 buys; a Transport and a Border Village (Forums don't count), so we will increase our Haggler count N^3 times.
    Whether we play Hagglers as Hagglers or Vassals, we get the +1 coin token from Training for 3 coins per Haggler.  To simplify the math, I'm reducing that to half the price of a Forum.
When we buy a Border Village (after the first), the pre-buy Hagglers first double the number of Hagglers and then all Hagglers are played multiple times for massive post-buy gains.

The first Border Village increases Hagglers from N to O(N^2).
Then we will buy O(1/2*N^2) Forums, gaining O(1/2*N^4) Village Greens, allowing us to play O(2*N^2) Hagglers O(1/2*N^4) times for O(N^6) Hagglers.
Then we will buy O(1/2*N^6) Forums, gaining O(1/2*N^12) Village Greens, allowing us to play O(2*N^6) Hagglers O(1/2*N^12) times for O(N^18) Hagglers.
Then we will buy O(1/2*N^18) Forums, gaining O(1/2*N^36) Village Greens, allowing us to play O(2*N^18) Hagglers O(1/2*N^36) times for O(N^54) Hagglers.
... and we repeat this N^3 in a turn, yielding O(N^(3^(N^3))) Hagglers.

Sometimes the strength of an engine is stated as growth-per-turn.  Here we turn N Hagglers into N^(3^(N^3)) which can be stated as g(N) = N^(3^(N^3)).  Obelisk grants us two victory points per Haggler, so we actually multiply this two to get VP.  The factor of two is insignificant so I'll just drop it.

It is often gratifying to talk about the Victory points at some turn n as a function of n, usually after a small constant number of turns required to get the engine up and running.  For reasons that will become clear later, I'll drop the constant and assume we start the first turn with 3 Hagglers.

f(0) = 3
f(1) = g(3) = 3^(3^(3^3)) = 3↑↑4 = 37,625,597,484,987
f(2) = g(g(3)) = [3^(3^(3^3))]^3^(3^([3^(3^(3^3))]^3)) which is much greater than 3^(3^(3^(3^(3^(3^3))))) = 3↑↑7 = ??!
f(n) = gn(3) >> 3↑↑(3*n+1)

The actual value of f(n) will far outpace the double up-arrow expression given.  For the evaluation of f(2), we replaced [3^(3^(3^3))] with just 3 at the base of the exponents.  This was necessary since those exponents were being evaluated bottom-up and we can only consider evaluating top-down to continue the chain.  Consider for a moment how much larger the value really would be without that substitution.  The increased value would be inserted into f(3) at the base and also at the exponent 2nd from the top and that's where things really start to get larger.  It would easily outpace the double up-arrow expression even if we were to assume a larger number of Hagglers at the start.  And that's where things get interesting.  What if we started with 27 Hagglers?  27 = 3^3.  That does not work out very well.  But if we started with 3^(3^3), that clearly allows us to add more exponents of 3 to our chain.  Leading me to conclude that
for sufficiently large n, f(n) = 3↑↑(k*n) for arbitrary values of k.
Okay, maybe that's a bit of a stretch, but this math is so strange who can tell.  I think the analysis of the engine is more of an art than creating the engine.

Logged

silverspawn

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5378
  • Shuffle iT Username: sty.silver
  • Respect: +3332
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #70 on: January 08, 2022, 07:31:50 am »
0

I don't know if you would be interested in this but it seems similar to the solutions in this thread (which I haven't read in detail).

IlstrawberrySeed

  • Baron
  • ****
  • Offline Offline
  • Posts: 54
  • Respect: +26
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #71 on: October 08, 2022, 10:43:56 pm »
0

Don’t know if anyone still reads this, but I’m working on a castles/displace deck using scepter->hunter for draw and finiteness, and capitalism -> rogue/treasurer + watchtower for the top decking and infinite coins and non-treasure draw. Buys are restricted through market square, and border village increases the rate at which our effective Scepters increase. Remodel + Lich -> Sycophant (watchtower) take care of the favor for Island folk to take extra turns.

Question, is an amount of points bounded by f(n,s), where n is turns taken, and s is turns skipped, and f(n, s) increases faster with each increase of n than each increase of s, OK for this challenge, concidering that s can be infinite, and therefore points scored in a turn is infinite?
Logged

tim17

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 134
  • Respect: +280
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #72 on: October 26, 2022, 09:46:15 am »
0

Question, is an amount of points bounded by f(n,s), where n is turns taken, and s is turns skipped, and f(n, s) increases faster with each increase of n than each increase of s, OK for this challenge, concidering that s can be infinite, and therefore points scored in a turn is infinite?

Correct me if it seems I'm misunderstanding your question, but here is what I will say. Let g(n) be the number of points you have right at the end of your nth non-skipped turn. For any board, if there exists a strategy in which for some n, g(n) - g(n-1) is infinite, then that board is disallowed.

However, if somehow this ruling prevents you from doing something interesting, you are welcome to post that interesting thing anyway.
Logged
Pages: 1 2 3 [All]
 

Page created in 0.14 seconds with 20 queries.