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

0 Members and 1 Guest are viewing this topic.

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Asymptotic analysis of kingdoms puzzle
« on: March 23, 2019, 08:44:26 pm »
+4

Hi f.ds, sharing a puzzle that a friend and I made (well, mostly my friend) for another friend of ours. You probably won't enjoy the puzzle unless you like both dominion and math, but hopefully everyone here likes at least one of the two. :)

The rules of our puzzle's asymptotic dominion are similar to those in http://forum.dominionstrategy.com/index.php?topic=17378.0, but the main difference is that in our puzzle, you can assume you will have perfect luck, as it asks about the best possible score. Also, this puzzle was made before Renaissance came out, so no Renaissance cards are in any of the kingdoms.

The puzzle is at https://walledvillage.github.io/puzzle.pdf. Each of the 13 bullet points on the left is a separate kingdom to consider. Most of these kingdoms might not have exactly 10 kingdom cards (in fact, one has none), but should be considered as if that were the kingdom anyway. Each of them matches with an answer on the right, and taking the corresponding letters will spell out a message. The eventual goal is to have a final answer, which is a word or phrase.

Feel free to ask for any hints or clarifications here, and I hope you enjoy!

Note: Based off a sample size of 1, this puzzle may take quite a while to complete.
---
Edit: Adding some extra info here.

Some basic kingdoms and their answers, to get the idea across.
  • Market, Chapel. Answer: 1.2^T
  • Market. Answer: 1.2^(T/2) = 1.095^T

A list of sets that I think are easier, since completing the whole puzzle is probably unreasonable.
In approximately increasing difficulty:
  • Potion cost
  • Durations
  • Reactions
  • Artisan, ...
  • Hamlet, Watchtower
  • Debt cost

A kingdom I would say is pretty fun and decently approachable is Artisan, ....
Here's some other kingdoms not included in the puzzle that are fun, and not toooo crazy to analyze:
  • Bishop, Cursed Village, Seaway
  • Bridge, Hunting Grounds, Donate, Canal, Inheritance
« Last Edit: March 28, 2019, 04:59:52 pm by bitwise »
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #1 on: March 25, 2019, 09:45:55 am »
0

Are the values on the right the high scores? If yes, how do they correspond to the different puzzles?
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #2 on: March 25, 2019, 03:31:20 pm »
0

This is a mystery hunt-style puzzle, so not all the instructions are not explicitly given. If you want to just think about the dominion and math, then (minor spoiler)  For each kingdom, find its optimal score under the rules given. Each kingdom's answer is in the list of answers to the right. If you find all the answers in order, the corresponding letters will spell out a message. The eventual goal is to have a final answer (english word or phrase) for the entire puzzle.
Logged

hhelibebcnofnena

  • Minion
  • *****
  • Offline Offline
  • Posts: 529
  • she/her
  • Respect: +409
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #3 on: March 25, 2019, 10:30:06 pm »
0

I think part of what is confusing is that the kingdoms on the right are not all valid 10-card kingdoms that could come up in a normal game (e.g. just Hamlet and Watchtower, or no cards but all the Events, or all cards costing at least ). It therefore isn't clear that those are kingdoms, rather than groups of cards with certain properties related to their effect on the score.
Logged
Hydrogen Helium Lithium Beryllium Boron Carbon Nitrogen Oxygen Fluorine Neon Sodium

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #4 on: March 28, 2019, 05:00:28 pm »
0

Fair enough, I edited the first post to make it more clear.
I also added some practice kingdoms, a list of the ones in the puzzle I think are the most approachable, and some fun bonus kingdoms. :)

Fun kingdoms to try out:
  • Bishop, Cursed Village, Seaway
  • Bridge, Hunting Grounds, Donate, Canal, Inheritance
« Last Edit: March 28, 2019, 05:56:17 pm by bitwise »
Logged

nasmith99

  • Steward
  • ***
  • Offline Offline
  • Posts: 26
  • Shuffle iT Username: nasmith99
  • Respect: +55
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #5 on: March 28, 2019, 11:22:53 pm »
0

What are the challenge's rules concerning possession? Can we assume a cooperative opponent?
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #6 on: March 29, 2019, 12:50:21 am »
0

What are the challenge's rules concerning possession? Can we assume a cooperative opponent?
The opponent can't buy or play cards, even when possessed, so you can't do much with them. You can assume that they are cooperative and you can assume perfect luck for how they draw cards though, like if you needed to Ambassador them cards so that you could Jester them, or something.

The potion kingdom would be more interesting if you could possess them and actually buy cards; I regret not having it that way.
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #7 on: April 03, 2019, 05:46:23 am »
+1

I worked on quite a few, but often get results that don't fit into the suggested solutions. Now I wonder, if I didn't find the best solution

Cards costing >= 6 vp ~ 9^T
buy King's Court, Grand Market, and Goons
use a small number of banks to get enough coins
limiting factor is the number of buys, 3 cards (KC, GM, G) yield 6 buys so I triple the number of cards every turn
victory points grow quadratic in the number of cards


Cards with potion in cost vp ~ T^2 / 12
alternate between buying Golem and Vineyard
use Golem to discard deck, so that a single potion is sufficient
T/2 Vineyard, T/2 Golem => T^2/12 points


Cards and events with debt in cost vp ~ T^2 / 27
loop over the following three turns
1) buy Engineer
2) buy City Quarter
3) play all City Quarters, Engineers, gaining Estate, buy Triumph
sum(2x/3, x=1..T/3)/3 ~ T^2/27


Reserve cards vp ~ 11.16 T
loop over the following
37x play Wine Merchant, 4 Gold, buy 2 Provinces
4x call 1 Coin of the Realm, play 3 Wine Merchant, 2 CotR, buy Province, 2 Guide
8x call 2 Coin of the Realm, play 5 Wine Merchant, buy Province, 4 Guide
use Guide to cycle through the deck. Occasionally keep 2$ to recover all the Wine Merchant.
vp/turn = (37*12 + 12*6)/43


Treasures vp ~ a^T
General idea: Use idols to gain will-o-wisp, which allows to draw a large hand, get points from castles that are a fraction of the will-o-wisp.
We use crown on the odd idols and the will-o-wisp to improve the speed.
If I calculated correctly, you can gain 0.24 will-o-wisp per Crown + 2 Idol and draw 4/3 cards per Crown/will-o-wisp.
I currently don't know exactly how large of a fraction of the cards should be which, but you will grow exponentially.


Hamlet, Watchtower vp ~ 144/13 T
The limit is that I can have only 6 Gold in play.
Hence, loop over buying 2 Provinces and 1 Hamlet (12x), and 6 Watchtowers (1x)
vp/turn = 12 * 12 / 13


Events vp ~ between 1.06^T and 1.13^T
Fundamentally, this builds on the fact that Travelling Fair + Expedition costs less than the two Gold you can draw with it. Then you can dedicate a fraction of your gains to triumph to score points. I calculated that the optimal fraction is about 3.2%. Your victory points grow with the square of that because you gain points for every card gained. Then you may achieve up to another square by using mission, so you are somewhere between 1.032^2 to 1.032^4.

Travellers vp ~ 2^T
+card on peasant
a small fraction of soldiers for $
This allows you to one more peasant for every peasant in play. So my number of peasants grows like 2^T. Then I dedicate a tiny fraction of my gains to Provinces so that they grow at the same speed and use Fugitive to cycle over them.


Durations vp ~ 3.06^T
The number of cards and coins is irrelevant here, because of Wharf and Bridge Troll. The limiting factor is the number of buys I can get. For every 3 buys, I need to play 1 Fishing Village, so I can grow the number of buys like 1.75^T. Because of Outpost, the actual growth per turn is the square of this number.

Reactions vp ~ 9 T
I can grow my number of Market Squares and Caravan Guards exponentially (1.25^T), but unfortunately there is no way to convert that into exponential gains of points, because I cannot cycle past the provinces. With any of the +2 card reactions, I can cycle past 6 Provinces a turn. Hence, if the number of Provinces grows per shuffle like P(S), I need P(S) / 6 turns to cycle till the next shuffle. For exponential growth per shuffle P(S) = x^S the number of points per turn is 6 (x^(S+1) - x^S) / (x^S / 6) = 36 (x - 1) = 9
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #8 on: April 03, 2019, 02:44:52 pm »
0

Nice! Thanks for trying the puzzle out. :)

I will say that the strategy is allowed to depend on T, meaning that you know how many turns you have, so you can choose to delay buying points until the very end if that would benefit your strategy. Doing that should improve some of your kingdom's scores.

If you'd like to know, the ones you have correct are: Potion, Reserve, Hamlet/Watchtower, Travellers .
Also, I would say that you have the right strategy for Durations but seem to have analyzed it incorrectly?
Logged

ephesos

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

Durations

Important cards are Outpost, Bridge Troll, Wharf, and Fishing Village. Assume some constant number of Bridge Trolls and Fishing Villages is played, so cost is 0.

Say that we play F(T) Fishing Villages and W(T) Wharfs on turn T.

The number of buys on turn T is W(T-1) + W(T).

On turn T+1, we get back F(T-1) Fishing Villages and W(T-1) Wharfs into our deck, and add W(T-1)+W(T) cards that we bought on turn T.

So F(T+1)+W(T+1) = F(T-1)+W(T-1)+[W(T-1)+W(T)]

Assume that F(T+1) = W(T). Then, W(T+1) = W(T-2)+2*W(T-1). This is recognizable as a result of the Fibonacci sequence, W(T+1)=W(T)+W(T-1).

Thus, W(T) is proportional to the Tth Fibonacci number, which scales as 1.618^T.

Two checks: actions and card draw.
Actions: F(T-1)+F(T) >= W(T). Since F(T-1)+F(T) = F(T+1) = W(T), there are enough actions.
Card draw: 2*W(T-1) + 2*W(T) >= W(T) + F(T), which is easily satisfied since W(T) = F(T+1) > F(T).

Use Outpost to get 2 turns per turn, for 1.618^2T = 2.618^T.
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #10 on: April 08, 2019, 06:04:59 am »
0

Debt
Strategy: Buy X City Quarters, then buy X Engineers, then Triumph for 3X/2 turns, gaining X Estates every time. After a negligible logarithmic number of City Quarters, all Engineers and City Quarters are in hand, so total card draw from the City Quarters is order of (3X^2)/2, so the deck can support (3X^2)/2 Estates.

Since 7X/2 = T, points are (3X^2)/2 from Estates + (3X^2)/2 from Triumph = 3X^2 = 12/49 T^2.


Events
Deck is X Golds. Buy Y Golds with Travelling Fair, and Z Expeditions with Travelling Fair, then Mission.
On Mission turn, buy enough Expeditions to fully draw all Gold bought (X+Y).

So 5 (X+Y)/2 = 3*2*Z and 8*Y+5*Z = 3*X. So we get Y=X/11 and Z=5X/11, for a money growth rate of 1.111^T.

Cashing out is buying lots of Conquests + Travelling Fair. So that's 2*(1.111^T/8)^2 ~ 1.234^T
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #11 on: April 08, 2019, 04:45:36 pm »
0

Thanks for trying the puzzle out.  :)
Comments per kingdom, if you're interested.

Re: Durations
Correct! I like how nice this one turned out. / anti-spoiler dummy text

Re: Debt
These are the right cards to use, but you can do better with a different greening strategy. More spoilers : / Even though getting estates on turns you buy triumph is twice as efficient, you don't actually want to maximize the proportion of turns you do this, just due to the way that it increases the numerator by a linear amount but the denominator by a quadratic amount.

Re: Events
If you have Y=X/11, then shouldn't the base growth rate be 12/11 -> 1.0909^T, not 1.111? Anyway, you can improve this strategy. More spoilers : / You can improve both the building up and the cashing out. I hadn't considered not always drawing all your gold (besides possible endgame shenanigans) but I don't think it is helpful. There's also another card that helps you build up.
Logged

ephesos

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

Okay, improved Events cashout. Don't see a way to buildup faster, maybe something with Quest and Curses? Doesn't seem like you can gain Gold at a rate matching the gain of Curses, so you're chained to the slower one.

Deck is X Golds. Buy Y Golds with Travelling Fair, and Z Expeditions with Travelling Fair, then Mission.
On Mission turn, buy enough Expeditions to fully draw all Gold bought (X+Y).

So 5 (X+Y)/2 = 3*2*Z and 8*Y+5*Z = 3*X. So we get Y=X/11 and Z=5X/11, for a money growth rate of 1.0909^T.

Cashing out: Get X Silvers, play X Gold and X Silvers, then Raid L times, then Conquest M times.

Getting X Silvers can be done in constant time; 18 Gold can buy 10 Expeditions and 2 Delves, so X Gold buys X/9 Silvers and draws everything. Then just Raid 8 times on the next turn.
Next, we have to get enough Expeditions to draw everything.
X Golds and Y Silvers can buy (3X+2Y)/5 Expedition/Travelling Fairs, which draws X + (X+4Y)/5 cards. If Y = p(k)X, then p(k+1) = [1+4p(k)]/5. Defining q(k) = 1-p(k), q(k+1) = 4/5 q(k), which goes to 0 exponentially. Thus, p(k) -> 1 exponentially quickly, and though we cannot reach exactly X Silvers, we can get close enough that the difference is negligible, in a negligible amount of time.

So we cash out with X Gold and X Silver, gaining 5X = spending (7L+8M). Total VP is 2M^2 + M*L*X = 2M^2 + M*X*(5X-8M)/7. Second term is cubic in X, so the first is negligible. Optimizing for M, we get (5X^2-16MX)/7 = 0, or M = 5/16 X, L = 5/14 X. So the total VP scales as M*L*X = 25/224 X^3 ~ X^3. X ~ 1.0909^T, so the overall VP is proportional to 1.298^T.

Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #13 on: April 09, 2019, 08:49:20 am »
0

You can buy Wedding on your mission turns, but that seems to be only slightly better

Normal turn: TF+Ex = 5, TF+G = 8
5 A + 8 B = 3
2 A = (1 + B)
Mission turn: TF+Ex = 5, TF+W = 9
5 C + 9 D = 3 (1 + B)
2 C = 1 + B + D
Solution A = 0.524, B = 0.048, C = 0.547, D = 0.046 => grow rate (1 + B + D)^T = 1.093^T

I agree with the cubic cashing out using Delve, Raid, and Conquest (you could use Triumph, but that would only change the prefactor): 1.093^(3T) = 1.306^T
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #14 on: April 09, 2019, 11:00:47 pm »
0

Better Events buildup with Quest and Curses

Suppose the deck has 19A+9B Gold and 2A Curses. With these, we buy A Quests, B Curses, 11A+5B Expeditions, and 12A+6B Travelling Fairs.
Check the money total: 57A + 27B = 3(11A+5B) + 2(12A+6B).
Also check card draw: 11A+5B Expeditions draws 22A+10B, and on the next turn, we have 19A+9B+2A+A+B cards = 22A+10B

At the next step, we have 20A+9B Gold and 2A+B Curses. Suppose that at each step we multiply both Gold and Curse amounts by k.
Then, k(19A+9B) = 20A+9B and k(2A) = 2A+B. Solving for k, we get k ~ 1.05 and A ~ 9.952 B, with an overall Gold to Curse ratio of about 9.952 to 1.

With Mission, this scales money as 1.05^2T = 1.10^T. With the previous cubic cashout, this leads to an overall VP of 1.34^T.

Obviously, before cashing out, trash all the Curses with Donate so they don't give you a negative score :P

EDIT: Oops, realized this buys Curses on the Mission turn. There's probably a way to do it that buys all the Curses on the normal turn, then gains Gold on the Mission turn.
EDIT2: It turns out the analysis is pretty much the same.
Buying A + 0.5B Quests and a lot of Expeditions on Mission turn, we get the equations:
k(19A+9B) = 21A + 9.5B
k(2A)  =    2A + B
Which gives k=1.10, so the overall rate is pretty much the same. The Gold to Curse ratio changes slightly to 10.41 to 1.
I think you could optimize this further by buying Weddings with the extra money, since you have more than enough Expeditions. But the rate will be pretty similar.
« Last Edit: April 09, 2019, 11:28:07 pm by ephesos »
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #15 on: April 10, 2019, 03:29:34 am »
0

I verified your solution and checked whether adding Weddings would bring a benefit
Normal turn: A * TF + Ex, B * TF + Qu, C * TF + Cu
Mission turn: X * TF + Ex, Y * TF + Qu, Z * TF + We
A ratio R of my total cards are Gold the rest are Curses

I find the optimal values A = 0.526, B = 0.044, C = 0.009, X = 0.551, Y = 0.048, Z = 0.002, R = 0.912. This leads to a growth rate of (1 + C/(1-R))^T = 1.103^T. Including the cubic cashing-out, we get 1.341^T.

Here are the equations
Code: [Select]
5 A + 2 B + 2 C = 3 R
2 B = (1 - R)
2 A = 1 + B + C
5 X + 2 Y + 9 Z = 3 (R + B)
2 Y = (1 - R) + C
2 X = 1 + B + C + Y + Z
(1 - R) * (B + Y + Z) = R * C
Logged

bitwise

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

I verified your solution and checked whether adding Weddings would bring a benefit
Normal turn: A * TF + Ex, B * TF + Qu, C * TF + Cu
Mission turn: X * TF + Ex, Y * TF + Qu, Z * TF + We
A ratio R of my total cards are Gold the rest are Curses

I find the optimal values A = 0.526, B = 0.044, C = 0.009, X = 0.551, Y = 0.048, Z = 0.002, R = 0.912. This leads to a growth rate of (1 + C/(1-R))^T = 1.103^T. Including the cubic cashing-out, we get 1.341^T.

Here are the equations
Code: [Select]
5 A + 2 B + 2 C = 3 R
2 B = (1 - R)
2 A = 1 + B + C
5 X + 2 Y + 9 Z = 3 (R + B)
2 Y = (1 - R) + C
2 X = 1 + B + C + Y + Z
(1 - R) * (B + Y + Z) = R * C

Yup, that's right! I would put a smiley here but it shows through the spoiler tags, heh.
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #17 on: April 11, 2019, 02:20:03 am »
0

In the meantime, I worked also on the 6+ cards. I found that using Hunting Grounds and Expand, you can improve on my previous solution, because you can gain more cards that you can play on your current turn. The general idea is to Expand Hunting Grounds into more King's Courts and Expands gaining the Duchies in the process required to Expand into more Hunting Grounds
A * KC Ex(3HG) Ex(3D) -> 3KC, 3HG, 3D
B * KC Ex(3HG) Ex(3D) -> 3Ex, 3HG, 3D
C * KC Ex(3HG) Ex(3D) -> 6HG, 3D
D * KC HG HG -> draw 24
In every loop you will play a few less of each card (X KC, Y Ex, Z HG) leading to
24 D = 9 (A + B + C)
3 A = A + B + C + D - X
3 B = 2 (A + B + C) - Y
3 C = 2 D - Z
The optimal solution to this is for A = 88, B = 128, C = 48, D = 99, X = 99, Y = 144, Z = 54. Per loop this leads to gain of 3A / (3A + X) = 8/11 of the cards I already have. The geometric series converges to 11/3.

In the cashing out phase I add Goons to square the number of points ~13.444^T. There maybe a chance to optimize this further, because you have some excess draw from the previous turn (the number of HG is optimized to draw the action cards and the Duchies, but the Duchies don't remain in the deck). However, I didn't find a way to put this in an equation.
Logged

ghostofmars

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

And here is my solution for the Artisan, ... puzzle

Card draw and actions are not an issue, because of Champion and Counting House/Cellar. If I have N Copper, I just need log_N(deck size) CH/C to draw my entire deck.

Strategy:
-buy Artisan every other turn ~T^2
-gain Vampire for every Artisan ~T^3 (gain a few Ill gotten gains with vampire to provide trashing fodder for the Bats)
-gain Cobbler for every Vampire ~T^4
-gain Page/Gardens with the Cobbler ~T^5
-exchange Page to Heros ~T^5
-gain Bank with every Hero ~T^6
-coin grows quadratic in the number of banks ~T^12
-buy Masterpiece - gain silver with overpay ~T^13
total points #garden * #silver ~T^18
Logged

bitwise

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

6+:
As you can probably tell from the possible answers, this is valid but you can do better. KC Hunting Grounds Expand is good, but you need to do give it some help to make it even better.

Artisan, ...
Yup, that's right. I was thinking of posting a challenge for the best polynomial possible, either with a valid kingdom (10 cards + some number of sideways cards). It turns out you can get a lot higher with Renaissance.

You have probably solved enough to start guessing at the message. :)
« Last Edit: April 11, 2019, 04:47:14 pm by bitwise »
Logged

ephesos

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

Not really sure what to do about Debt.

Even if I let the amount of turns you Triumph for vary, I get that the points are maximized when it's 3T/7, because you can't support a deck with more than 3X^2/2 Estates.
We can Donate occasionally to prevent having more Estates than we can draw past, but that just loses points, as does alternating Annexes.

Turns: 2X + Y = T
Points: min(3X^2/2, XY) Estates + XY from Triumph.
If Y<=3X/2, T <= 7X/2, points = 2XY which is maximized at X=2T/7, Y=3T/7 subject to the initial constraint.
If Y > 3X/2, T > 7X/2, points = 3X^2/2 + XY which is maximized again at X=2T/7, Y=3T/7.
So points = 12/49 T^2 is the best I have so far.
Logged

ghostofmars

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 162
  • Respect: +71
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #21 on: April 12, 2019, 08:40:37 am »
0

I figured the Debt cards out. The key is to gain estates while you are building up the Engineer and City Quarters.

In build-up phase: Gain X En, X CQ, and X^2 Es. Then cash-out by gaining Estate + Triumph for several turns. For X = R T the total victory points are
VP = (R T)^2 + 2 * (1 - 2 R)T * R T = (2R - 3R^2) T^2
This is optimal for R = 1/3
leading to VP = 1/3 T^2.
Logged

bitwise

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 133
  • Respect: +142
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #22 on: April 12, 2019, 12:37:16 pm »
0

Debt:
ghostofmars is almost right, but keep in mind that that deck can only support 3R^2/2 * T^2 estates.
Logged

ephesos

  • Explorer
  • *****
  • Offline Offline
  • Posts: 347
  • Shuffle iT Username: Ephesos
  • Respect: +290
    • View Profile
Re: Asymptotic analysis of kingdoms puzzle
« Reply #23 on: April 17, 2019, 10:44:24 pm »
0

Okay, so putting the two together:

Strategy: Gain X Engineers and X City Quarters, alternating between the two. As you do, gain some number of Estates, up to at most X^2. Then Triumph Y times.

Turns: 2X + Y = T
Points: X^2 + min(X^2/2, XY) Estates + XY from Triumph.
If Y >= X/2, 5X/2 <= T, X <= 2T/5. Points = 3X^2/2 + X(T-2X) = TX - X^2/2, optimizing over the interval [0,2T/5] gives X=2T/5, Y=T/5, points = 8T^2/25
If Y <= X/2, X >= 2T/5. Y >=0, so X <= T/2. Points = X^2 + 2XY = 2TX - 3X^2. Optimizing over the interval [2T/5, T/2] gives X=2T/5 as before.

So the answer is 8/25 T^2 = .32 T^2.
Logged

ephesos

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

Inheritance, Procession, Scrying Pool, Stonemason, Worker's Village

Deck is 2X Gold, X Worker's Village, X Stonemasons, 2X Estates, X/2 Provinces, and 2 Scrying Pools. I couldn't figure out how to use Procession, so I ignored it.
Scrying Pool for all actions in hand
Play X/2 Worker's Villages and 2X Estates drawing X/2 Provinces and 2X Gold
Play X/2 Stonemasons trashing X/2 Worker's Villages and gaining X Estates
Scrying Pool to draw X Estates
Play X/2 Stonemasons trashing X/2 Provinces to gain X Gold
Play X Estates to draw X Gold

Play 3X Gold. Have 7X/2 Buys from X/2 Worker's Villages and 3X Estates.
Spend $3X to buy X/2 Stonemasons, overpaying by 4 each time to gain X Worker's Villages
Spend $6X to buy 3X/4 Provinces

On the next turn, we have 3X Gold, 3X/2 Worker's Villages, 3X/2 Stonemasons, 3X Estates, and 3X/4 Provinces.
Thus, total deck value has multiplied by a factor of 1.5, so points are 1.5^T
Logged
Pages: [1] 2  All
 

Page created in 0.059 seconds with 21 queries.