Dominion Strategy Forum
Dominion => Puzzles and Challenges => Topic started by: sudgy on April 24, 2020, 02:13:19 pm
-
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.
-
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.
-
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".
-
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.
-
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.
-
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.
-
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).
-
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.
-
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.)