Dominion Strategy Forum

Please login or register.

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

Author Topic: Asymptotic analysis of kingdoms puzzle  (Read 8232 times)

0 Members and 1 Guest are viewing this topic.

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #25 on: April 18, 2019, 01:03:54 am »
0

Debt:
Yup, nice!

Inheritance, ...
Procession is indeed useless here, sorry about that. You can do better than that solution. Hint: / You don't need to buy any stonemasons or worker's villages. (Well, besides at the beginning.
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #26 on: April 18, 2019, 01:16:03 am »
0

Reactions

Similar to ghostofmars solution, we only use Caravan Guards and Market Squares, but we hold off on greening until the end and take into account duration.

Assume the solution is of the form k^T.
This turn, we play X Caravan Guards and X/3k Market Squares.
Last turn, we played X/k Caravan Guards, so we have $X/k this turn, and can buy X/3k cards costing $3.
Next turn, we want to play kX Caravan Guards, so we need to buy kX - X/k of them as we get X/k back from last turn. Similarly, we want to play X/3 Market Squares, so we need to buy X/3-X/3k.
We buy (k-1/k)X Caravan Guards, and (1-1/k)X/3 Market Squares, so k - 1/k + 1/3 - 1/3k = 1/3k, k+1/3 - 5/3k = 0, 3k^2 + k - 5 = 0, k = -1/6 + sqrt(61)/6 ~ 1.135
So total money and buys scale as 1.135^T. VP is proportional to both, so it scales the same.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #27 on: April 18, 2019, 01:46:33 am »
0

Reactions:
That's right too, nice!

You have a lot of the kingdoms solved now (9/13 I think) and I would strongly encourage looking at the letters you have and guessing at what it says. Hint hint. :P
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #28 on: April 18, 2019, 12:06:34 pm »
+1

Oh yeah, I've taken a look at the answers: _DDKI_G_C_URT oh god whyyyyyy
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #29 on: April 18, 2019, 01:06:16 pm »
0

Improved Inheritance

Instead of using Gold to buy Province, use Silver. Stonemason Worker's Village to gain Silver, and Stonemason Silver to gain Estates and Stonemasons. Also don't buy Stonemason.

Let the deck start with Z Stonemasons, W Estates, V Provinces, and U Silvers.
We trash V Provinces to gain 2V Gold, trash 2V Gold to gain 4V Worker's Villages, trash 4V Worker's Villages to gain 8V Silvers, and then trash F Silvers to gain T Estates and (2F-T) Stonemasons.
We then play U+8V-F Silvers and buy kV Provinces

As we gain Estates and Stonemasons, we can draw and play them, as long as we can draw the entire deck at the start: W >= V+U
Total Stonemason plays: Z + (2F-T) >= V+2V+4V+F
Total actions: W+T >= Z + (2F-T)
Province money: kV <= (U+8V-F)/4
Total buys: W+T >= kV
Silver gains: kU = U+8V-F
Stonemason gains: kZ = Z+(2F-T)
Estate gains: kW = W+T

Shoving it all into Wolfram Alpha, we get an optimal value of k=1.82405, with Z=6.41641V, T=4.12023V, F=4.70382V, U=4V, W=5V.
So total VP is proportional to 1.82405^T

« Last Edit: April 18, 2019, 01:07:30 pm by ephesos »
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #30 on: April 18, 2019, 09:02:54 pm »
0

Oh yeah, I've taken a look at the answers: _DDKI_G_C_URT oh god whyyyyyy
https://giphy.com/gifs/2zelCiUo5KJyN8MgMr/html5

Inheritance
I wasn't able to get wolfram alpha to take in all those inequalities, so I couldn't check super well. The total actions constraint seems like it's supposed to be W+T >= V+2V+4V+F instead of the current right hand side, but that shouldn't change the answer.
I think you need an additional draw constraint as well-- maybe you can draw WVs, Estates, and SMs for free with a small number of Scrying Pools, but the non-actions have to be drawn with your WVs/Estates. Need something like W + T >= U+V+2V+8V. At a glance, it looks like the values you have wouldn't meet this bound.

As for the actual strategy, it's getting closer but you can do something a bit better.
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #31 on: April 19, 2019, 12:57:00 am »
0

Oh yeah, oops, forgot to edit that constraint. It was in the equations, just I left out a term or two. I also reduced them a lot when I wrote them in the post, to ignore some of the zeros for strategies not being used (buying Gold, trashing Worker's Village directly into Estates/Stonemasons, etc.).

Yeah, the total draw should be W+T >= 11V+U, since you start with V Provinces and U Silvers to draw, and you gain 2V Golds and 8V Silvers.
I redid the equations and got k=1.70156, Z=7.16621V, W=7.64004V, T=5.35996V, F=5.19375V.

I also tried adding buying Duchies into the mix, but the equations come out the same.

Also, I put them into the online Mathematica console to get them to fit.
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #32 on: April 19, 2019, 09:52:11 am »
0

Treasures solution(?) 1.17^T

Cards used:
* Will-o-Wisp (WoW) - source of card draw
* Idol (Id) - source of WoW via Boons
* Contraband (CB) - source of Buys
* Crown (Cr) - double Id, CB and WoW
* Bank - source of Coin
* Loan - trash Silver from Boon
* Royal Seal - put the Silver on top of the deck, so Loan finds them
* Copper - source of discard for Boon
* Quarry - reduce cost of Crown
* Talisman - enhance the number of gains
* Castles - for cash-out
The limiting factors are WoW, Id, CB. Because the coins grow quadratically in the number of Banks, Banks are not limiting. All other cards used in the build-up phase can be gained via Talisman so that again only a square-root of buys needs to be spend on those cards and Talisman.

Action phase: Play Cr + WoW, draw Cr, Id, Loan, or CB and WoW or Copper. The net draw is the same as the number of WoW + a sufficient amount of copper.
Buy phase: Consider the Boons first: 9 of them can be played more than once; 3 of them are helpful (+1 card, +2 card/discard 2, gain WoW), 1 is harmful (+1 silver), 5 do nothing. So for every 9 boons I get 3 cards, 1 WoW, and need to trash 1 silver. I play Cr for every odd Id (gaining boons) and only Id for every even one (distributing curse).
For a set of 9 Cr, 18 Id, 2 Loan, I play 18 boons gaining 2 WoW, drawing 6 cards, and gaining/trashing 2 Silver. The 6 cards are of course more of these sets; the geometric series converges to sum_n (6/(9+18+2))^n = 29/23.

Assuming, I use my WoW to draw A of these sets and B CB. I use the buys for a ratio R of Id and (1 - R) CB. Because I can use Cr on the CB, I need to buy only half of the buys. I require then that all three limiting cards grow at the same rate
1 = 29 A + B
1 + 29/23 * 2A = [29/23 * 18 A + R B] / [29/23 * 18 A] = [B + 2(1-R) B] / B
Solving this leads to
A = 0.0323, B = 0.0624, R = 0.959
and a growth rate of 1 + 29/23 * 2A = 1.082. By using castles, I can increase the growth rate to the square of this.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #33 on: April 19, 2019, 02:15:09 pm »
0

Hint for Inheritance + ...
Silver seems to be better than Gold... maybe Copper is somehow better than Silver? ???

Treasures looks like roughly the right engine, but with several things that can be improved upon.
  • Idols - You can get a lot more bang for your buck from your idols.
  • Buys - You can improve this too. It's important here that Crowns are "free" to buy.
  • Boons - Two other Boons are useful, and they will help reduce the need to trash.
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #34 on: April 20, 2019, 07:37:59 pm »
0

Okay, I think I've got Inheritance now, rate is 1.86646^T

Basic strategy: buy Provinces, trash them to Gold, trash Gold to Duchy, Duchy to Worker's Village, Worker's Village to Silver, and Silver to Estate.
Use extra buys to buy Copper, spend Copper to buy Provinces.

Deck is V Provinces, Z Stonemasons, W Estates, R Coppers, where Z=16.6089V, W=20.3227V, R=14.9317V, and a constant number of Scrying Pools.
Draw all cards with V+R=15.9317V Estates

Play V Stonemasons, trashing V Provinces gaining 2V Gold. Draw with 2V Estates.
Play 2V Stonemasons, trashing 2V Gold gaining 4V Duchies. Draw with 4V Estates.
Play 4V Stonemasons, trashing 4V Duchies gaining 8V Worker's Villages. Draw with 1 Scrying Pool.
Play 8V Stonemasons, trashing 8V Worker's Villages gaining 16V Silvers. Draw with 16V Estates.
Play 16V Stonemasons, trashing 16V Silvers to gain 17.6089V Estates and 14.3911 Stonemasons. Draw with 1 Scrying Pool.

Buy 1.86646V Provinces and 27.86942V Coppers, 29.73588 cards total.
k=1.86646 is the multiplier, so total money/VP scales as 1.86646^T

Note that if you do the Stonemasons in the order stated, you run out of actions, Estates, and Stonemasons in the middle. However, all you have to do is run the supply chain in multiple parts: take 0.125V Provinces, trash those to Gold to Duchy to WV to Silver to Estate/Stonemasons, and then do the next set of 0.125V.

Here's the Mathematica code I used:
Code: [Select]
NMaximize[k, V+B+C+D+F+Q+3G <= Z+(2C+2F-T)  && k*U == U+2D-F && 8*k*V + 5*k*Q <= (3(X+2V-B-G)+2(U+2D-F)+R) && k*V+k*Q+(k-1)*R<=Y+W+2Q+2B-C-D+T && k*X == X+2V-B-G && k*Y == Y+2B-C-D+2Q+4G && k*W == W+T && k*Z == Z + (2C+2F-T) && Y+2B+2Q+4G-C-D+W+T >= V+B+C+D+F+Q+3G&&Y+2B+2Q+4G-C-D+W+T >= X+3V+U+2D+2G+Q+R &&Y+W >= X+V+U+Q+R&&V>=0&&X>=0&&Y>=0&&Z>=0&&C>=0&&B>=0&&T>=0 && Q>=0 &&R>=0&&U>=0&&D>=0&& T<=2C+2F && V==1, {k,V,B,C,Z,W,X,Y,T,U,D,F,Q,R,G}]
where {X:Gold, Y:WV's,Z:Stonemasons,W:Estates,V:Provinces,U:Silvers,Q:Duchies,R:Coppers} are in deck at start of turn, and {B:Gold to WV,C:WV to 2-cost,D:WV to Silver,F:Silver to 2-cost,G:Gold to Duchy} are trashing with Stonemason. Assumed all Provinces/Duchies get trashed each turn, Province to Gold and Duchy to WV.
« Last Edit: April 20, 2019, 07:39:07 pm by ephesos »
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #35 on: April 20, 2019, 08:51:36 pm »
0

Cards costing <= 3:

2^2^T. Analysis is a bit loose here, since the coefficients don't matter. Here, X is used whenever something is proportional to X, ignoring any coefficient.

First, get X Victory cards and draw them with log(X) Crossroads and log(X) Villages

To gain non-Victory cards, we can use Changeling and Tunnel. With X Tunnels, we can gain X Gold by playing 1 Storeroom. Having X Storerooms means we can gain X^2 Gold, which turns into X^2 Changelings.
We then need to draw the Changelings we gain, which can be done with X Crossroads/Villages while having X victory cards in hand.
Thus, at the end of the turn we gain X^2 of all action cards used. The only thing left is to gain X^2 Tunnels. This can be done on the next turn using e.g. X^2 Workshops and X^2 Villages.

So, we start each turn with X Tunnels and X^2 Crossroads, Villages, Workshops, and Storerooms.
Using log(X) Crossroads and Villages, we draw X Tunnels.
Using X Crossroads and Villages, we draw all the cards.
Using X^2 Workshops and Villages, we gain X^2 Tunnels.
Using X Crossroads, we draw X^2 Tunnels.
Using X^2 Storerooms, Crossroads, and Villages, we gain and draw X^4 Changelings.
We then gain X^4 Crossroads, Villages, Workshops, and Storerooms in the Night phase.

Each turn, we square the number of cards we have. So the points scale as X^2^T, which is 2^(k*2^T) for some coefficient k.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #36 on: April 20, 2019, 10:21:15 pm »
0

Inheritance(...): Looks good, yay!
<= 3$: Looks good, yay!
Logged
Pages: 1 [2]  All
 

Page created in 0.122 seconds with 21 queries.