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 13944 times)

0 Members and 1 Guest are viewing this topic.

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1688
  • Respect: +4302
    • 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

  • Spy
  • ****
  • Offline Offline
  • Posts: 80
  • Respect: +74
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #51 on: December 22, 2020, 07:10:49 pm »
+1

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

bitwise

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

  • Spy
  • ****
  • Offline Offline
  • Posts: 80
  • Respect: +74
    • 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 = G;  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), so growth can be expressed as L^(2.414*L^0.707)) per turn (not including the buy phase).

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 to be less.
« Last Edit: Today at 06:41:05 pm by pitythefool »
Logged

pitythefool

  • Spy
  • ****
  • Offline Offline
  • Posts: 80
  • Respect: +74
    • View Profile
Re: Best Asymptotic Point Scoring
« Reply #54 on: Today at 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
Pages: 1 2 [3]  All
 

Page created in 0.075 seconds with 22 queries.