Dominion Strategy Forum

Please login or register.

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

Author Topic: Best asymptotic point scoring per "action"  (Read 2335 times)

0 Members and 1 Guest are viewing this topic.

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Best asymptotic point scoring per "action"
« on: April 24, 2020, 02:13:19 pm »
+1

Maybe this is just linear in the end, but I was wondering: what is the best asymptotic point scoring per "things you do"?  By "things you do", I'm talking about things like playing a card, buying a card, etc.  If we need a hard list, for now let's go with
  • Cards played
  • Cards bought
  • Reactions used
as the things that count as things you do (I might add more things if people think of more).  So, what is the best asymptotic point scoring, as a function of the number of these "actions"?  Like I said before, I can only think of O(n) (I can think of something better that works temporarily, but they're not sustainable).  Another mode that might be more interesting if this turns out to be no good is to consider infinite piles.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Best asymptotic point scoring per "action"
« Reply #1 on: April 24, 2020, 02:34:17 pm »
0

You can get O(n^2) at least. In the max VP against bots thread, my solution (https://cdn.discordapp.com/attachments/643886239233081366/702629645656391720/Screen_Shot_2020-04-22_at_2.18.44_PM.png) should be O(n^2), since it is infinitely gaining and replaying cards (O(n) cards gained for n actions), and buying Triumph and returning the estates at a constant rate.
I feel like with finite piles, this is probably the max, since you can only gain a constant number of cards per action. Every other VP source is limited to a constant per action, besides Conquest. And if there isn't a way to gain more than O(1) cards per action, there certainly isn't a way to gain more than O(1) silvers per action either.

With infinite piles, there's definitely more amusing things to do. I'll think about that and see what I can come up with.
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best asymptotic point scoring per "action"
« Reply #2 on: March 02, 2021, 08:06:25 pm »
+1

I'll present an engine for the infinite pile version.  It's fun to not have to worry about unbounded play for a change.

Projects:  Capitalism, Guildhall

play Royal Seal (for topdecking)
play 2 Liveries
play 2 Hagglers

<buy phase>
    remove 2 tokens from Coffers for coins
    play Haggler
    play Livery
    buy a Bank
        from N Hagglers, gain N Border Villages
            from N Border Villages
                gain 1 Livery (topdeck)
                gain 1 Haggler (topdeck)
                gain N-3 Gardens
                gain 1 Cavalry, draw Livery and Haggler, return to action phase
        from N Liveries
            gain (2*N+1)*N Horses
        from gaining Bank, Livery, and Haggler
            +3 Coffers
<action phase>
    do nothing, restart buy phase


This turn never ends.
We don't use any actions since we are only playing treasures in the buy phase.
We use one buy which is replenished by gaining Cavalry.

The loop has two cards played and one card bought so I believe it scores only three from your "things you do" list.
There is of course a lot of gaining and other activity going on, but I believe it all escapes being counted.

We are gaining cards at O(N^3) rate and gaining Gardens at O(N^2) rate, so overall growth is O(N^5) per "thing".

Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best asymptotic point scoring per "action"
« Reply #3 on: March 04, 2021, 07:03:38 pm »
0

Another infinite pile engine.

Kingdom:  Black Market, Squire, Scrying Pool, Masterpiece, Feodum, Cavalry, Priest, Livery, Border Village, Forge
Black Market:  Royal Seal, Fortress
Event:  Travelling Fair
Project:  Academy

buy Academy (for actions, may require some Border Villages initially)
play Royal Seal (for topdecking)
play 5 Hagglers

<action phase>
    play Scrying Pool, draw all topdecked actions
    play Priest, trash Fortress
    play Haggler
    play Livery
    play Forge, trash all Squires, all Horses, all Border Villages, all but 1 Scrying Pool, 2 Cavalry, and Fortress
       gain nothing from Forge
       gain Scrying Pools from trashing Squires (topdeck)
<buy phase>
    buy Masterpiece, overpay by all coins except 7
        from overpay, gain many Silver
        from N Hagglers, gain N Squires (topdeck)
    buy Forge (topdeck)
        from N Hagglers, gain N Border Villages (topdeck)
            from N Border Villages
                gain Priest (topdeck)
                gain Haggler (topdeck)
                gain Livery (topdeck)
                gain N-5 Feoda
                gain 2 Cavalry (topdeck), draw 4 cards and return to action phase
        from M Liveries
            gain (2*N+1)*M Horses (topdeck)

We are now up to 5 cards played and 2 cards bought per iteration.
VP is granted by the Feoda and VP growth is now O(N^6) per activity.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Best asymptotic point scoring per "action"
« Reply #4 on: March 05, 2021, 04:38:21 pm »
0

Here's something silly that uses multiple turns.

Kingdom: Page, Hireling
Landmarks: Donate, Tomb

Setup: Pick an integer K >= 9. Over many turns, obtain K Treasure Hunters and K-5 Hirelings, and play all the Hirelings (so that starting hand size will be K every turn). Set up your deck so that you gain at least one card on a turn and are guaranteed to draw at least 8 Treasure Hunters next turn. (e.g., Donate down to only K Treasure Hunters, then buy anything. Next turn you will draw at least K-1 Treasure Hunters).

Every turn:
Play K Treasure Hunters. (or K-1 the first time)
Buy Donate, paying off all debt.
Donate down to K Treasure Hunters.

On the first turn you start this, you'll gain at least 1 Silver, then on every subsequent turn, you'll gain K times more Silvers than the previous turn, and trash them all.

After n turns, this gives O(K^N) points and takes O(K) actions, giving an O(K^N) points per action performance for any K of our choosing.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Best asymptotic point scoring per "action"
« Reply #5 on: March 05, 2021, 04:55:49 pm »
0

I don't know if cards set aside by Prince should count as plays every time or not. Either way, it should be possible to keep growing the number of Treasure Hunters every turn to increase our performance.

For example, we could put a +Buy token on Page, then once we can hit $18 every turn:

(All Treasure Hunters that have been set aside by Prince get played.)
Play two Pages.
Play Prince, setting aside a Treasure Hunter.
Buy Page, Prince, and Donate, paying all debt.
Clean-up: exchange a single Page for Treasure Hunter.
Donate: Trash all Silvers.

This can be accomplished with the kingdom Page, Peasant, Prince, Donate, Tomb.
After N turns of this, we do O(N) playing/buying steps, or O(N^2) if we count the start of turn Prince effects. We will score O(N!) points though, and no matter which denominator we pick, we will have an (N-O(1))! points/actions ratio.
« Last Edit: March 05, 2021, 04:57:45 pm by bitwise »
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best asymptotic point scoring per "action"
« Reply #6 on: March 06, 2021, 11:47:53 am »
0

Landmark:  Tomb
Projects:  Academy, Guildhall

Part 1

play Quarry (actions are cheaper, Masterpiece still costs 3 coins)
play Royal Seal (for topdecking)
play 3 Hagglers
buy Seaway for Priest

<action phase>
    play Priest, trash Fortress
    play Priest, trash Fortress
<buy phase>
    remove all tokens from Coffers
    buy Doctor, overpay with as many coins as cards in deck and discard pile.  Trash all for coin benefit and VP.
    buy Masterpiece, overpay with all your coins
       +coffers for Masterpiece and all Silver gained
       from Hagglers,
          gain Priest (topdeck)
          gain Priest (topdeck)
          gain Cavalry, draw both Priests, return to action phase

If we overpay for Masterpiece with N coins, we gain N+1 cofffers.
Two priests yields more coins and increases trash benefit by 4.
Overpaying for Doctor allows us to trash N+2 cards (Masterpiece, Silver, Cavalry), gaining (N+2)*(trash benefit) coins.
Simplifying, we gain ~4 VP first iteration, then on subsequent iterations:
   4 * 8,
   4 * 8 * 12,
   4 * 8 * 12 * 16, ...

VP per activity is O(4^N * N!).


Part 2

Play an extra Quarry and two Hagglers at the start.  Now when buying Masterpiece, gain Squire, Haggler, Cavalry, and an increasing number of Priests.  Use a Scrying Pool to draw all actions.  Academy provides the actions required to play the Haggler and all Priests.  One Priest trashes the Squire to replensish Scrying Pool for next iteration.

Now we have (starting with just one Priest and adding one per iteration),
   2,
   2 * 6,
   2 * 6 * 12,
   2 * 6 * 12 * 20,
   2 * 6 * 12 * 20 * 30, ...
   N! * (N+1)!

Our activities per iteration are increasing linearly as N+3.  We recognize that (N+1)! / (N+3) = (N+1)/(N+3) * N! ~= N!, hence VP per activity is O((N!)^2).

« Last Edit: March 06, 2021, 11:49:16 am by pitythefool »
Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best asymptotic point scoring per "action"
« Reply #7 on: March 09, 2021, 08:45:35 pm »
0

I get a lot of ideas when I think about these problems.  Most of them never pan out and I don't get to talk about them.  This mechanism is probably not going to help the infinite version of this challenge, but it helps make a tighter loop for the finite version.

It's still O(n^2).  bitwise is correct that with the current state of Dominion, that limit can't be beat.  So this is no great leap, but I get to display Academy+Diadem.  Acadamy+Diadem is to actions what Guildhall is for treasures, almost.  But whereas Guildhall is mostly a passive effect, Diadem has to be played to collect coins from unused actions.  And there is only one.  On the other hand, when you convert Guildhall coin tokens to coins, they are gone and you have to accumulate more.  Diadem does not remove the unused actions you have accrued.  If you Crown a Diadem, you get twice as much.  I left Academy out of this, since I'm already loaded on Landscapes and it is not strictly needed with a Champion in play, but it would accelerate the progression a lot.

Kingdom:  Page, Tournament, Cavalry, Mandarin, Grand Market
Events:  Inheritance, Triumph, Seaway
Ways:  Way of the Horse, Way of the Butterfly

Setup (in no particular order)
    put a Champion in play
    buy Inheritance for Cavalry
    buy Seaway for Estate and later return all Estates as Way of the Horse
    buy a Tournament and a Province, use them to obtain Diadem
    trash everything except
            9 x Grand Markets, Mandarin, Diadem

<start of hand>
    draw and play all Grand Markets (gains unused actions and +buys)

<buy phase>
    play Diadem
    buy Triumph, gain Estate
    buy Triumph, gain Estate ...
    buy Cavalry, draw 2 Estates
<action phase>
    play Estate as Way of the Horse, draw Estates ...
    play Estate as Way of the Horse, draw Calvary and Mandarin
    play Cavalry as Way of the Butterfly, gain Mandarin, Diadem is topdecked
    play Mandarin as Way of the Horse, draw Diadem and other Mandarin
    return to buy phase

Playing the Estates replenish the buys for buying Triumph.  Gaining the Cavalry replenishes the buy for that.  Way of the Horse provides more card drawing power than is required so there is no need for topdecking.  We just add an extra Mandarin in and ping-pong between them so we will always have one when needed.

You start out purchasing just a couple of Triumphs, but each time you play Diadem, it is worth more.  Eventually, you can empty the Estate pile and return them all in the same iteration.

Logged

pitythefool

  • Thief
  • ****
  • Offline Offline
  • Posts: 98
  • Respect: +85
    • View Profile
Re: Best asymptotic point scoring per "action"
« Reply #8 on: March 16, 2021, 10:29:35 pm »
0

Another insignificant improvement on the finite version.  I don't know why, but I tend to sometimes get fixated on these puzzles.
Still only O(n^2).


Kingdom:  Scrying Pool, Priest, Fortress, Cavalry, King's Court
Events:  Advance, Inheritance, Triumph, Seaway
Ways:  Way of the Horse

Setup (in no particular order)
    buy Inheritance for Priest
    buy Seaway for Estate
    trash everything except
            3 x Estate, 6 x King's Court, 7 x Priest, Fortress

<start of hand>
    use Scrying Pool to draw entire hand
    play 6 King's Courts
        play 7 Priests, 3 times each, trashing Fortress (trashing a card now earns 42 coins)
        play the 3 starting Estates, 3 times each as Way of the Horse, returning them and earning 9 buys
       
<buy phase>
    buy 8 x Triumph, gain 8 Estates
    buy Advance, trash Fortress, gain Cavalry, draw 2 cards
<action phase>
    play Estates as Way of the Horse, draw cards ...
    play Cavalry as Way of the Horse
    return to buy phase

That comes out to 0.444 purchases of Triumph per activity.


Just for fun, here's a more contrived version using Conquest in place of Triumph.

Buy Capitalism
Seaway on Squire
Play a City Quarter, Priest, and an Ambassador so Scepter can replay them.

initial loop
<buy phase>
    play Scepter, replaying City Quarter, draw cards
    play available Crowns and Squires for +coins, +buys
    play available Crowns and Scepters, replaying Priest, trashing Fortress
    with available coins and buys,
        buy mostly action cards at first, any action cards, for large City Quarter draw
        also buy additional Scepters, Crowns, and Squires if still needed
    buy Cavalry, draw 2 cards, go to action phase
<action phase>
    play Cavalry as Way of the Butterfly, gain Mandarin, return Crowns, Scepters, and Squires from play, put Scepters on top
    play Mandarin as Way of the Horse, draw 2 Scepters

After we get the trash benefit up to 102 coins and have 59 spare actions cards in our hand, we can fall into the VP gaining loop.

<buy phase>
    play Scepter, replaying City Quarter, draw deck
    play 6 Squires for +18 buys
    play 9 x Crowns on 9 x Scepters, each replaying Ambassador, returning 36 Silver
    buy 18 x Conquest, gain 36 Silver
    buy Advance, trash Fortress, gain Cavalry, draw 2 Silver, go to action phase
<action phase>
    play Cavalry as Way of the Butterfly, gain Mandarin, return Crowns, Scepters, and Squires from play, put Scepters on top
    play Mandarin as Way of the Horse, draw 2 Scepters

Sadly, at 74 counted activities per iteration, that's only 0.243 purchases of Conquest per activity.  Not nearly as efficient.

EDIT:  The value of Triumph increases by an average of 1.125 VP per purchase, whereas Conquest's value increases by 2 VP.  I am no longer entirely sure which is better, though I still think it's the Triumph.  I think a more efficient Conquest loop could conquer it though.  (lol, I wasn't intending to make a play on the names.)

« Last Edit: March 17, 2021, 05:39:48 pm by pitythefool »
Logged
Pages: [1]
 

Page created in 0.044 seconds with 20 queries.