Dominion Strategy Forum

Please login or register.

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

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

0 Members and 1 Guest are viewing this topic.

pitythefool

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

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

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

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

Victory points are simply generated by Obelisk.

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

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

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

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

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

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

Begin buy phase

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

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

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

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

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

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

liopoil

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

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

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

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

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

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

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

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

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

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

pitythefool

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 46
  • Respect: +52
    • 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

  • Scout
  • ****
  • Offline Offline
  • Posts: 44
  • Respect: +36
    • 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

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 46
  • Respect: +52
    • 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

  • Scout
  • ****
  • Offline Offline
  • Posts: 44
  • Respect: +36
    • 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

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 46
  • Respect: +52
    • 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

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 46
  • Respect: +52
    • 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

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

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

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

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

Starting Deck

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

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

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

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

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

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

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

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

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

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

tim17

  • Bishop
  • ****
  • Offline Offline
  • Posts: 104
  • Respect: +171
    • 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

  • Scout
  • ****
  • Offline Offline
  • Posts: 44
  • Respect: +36
    • 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

boris

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 20
  • Respect: +26
    • 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

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

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

pitythefool

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 46
  • Respect: +52
    • 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

  • Coppersmith
  • ****
  • Offline Offline
  • Posts: 46
  • Respect: +52
    • 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

  • Scout
  • ****
  • Offline Offline
  • Posts: 44
  • Respect: +36
    • 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: 20
  • Respect: +26
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #42 on: November 21, 2018, 03:36:47 pm »
0

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

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

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

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

Logged

bitwise

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

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

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

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

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

liopoil

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

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

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

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

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

Page created in 0.167 seconds with 21 queries.