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

0 Members and 1 Guest are viewing this topic.

bitwise

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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

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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 168
  • Respect: +83
    • 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

bitwise

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 23
  • Shuffle iT Username: nasmith99
  • Respect: +48
    • 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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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

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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

  • Young Witch
  • ****
  • Offline Offline
  • Posts: 141
  • Respect: +67
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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

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

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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

bitwise

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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: 323
  • Shuffle iT Username: Ephesos
  • Respect: +266
    • 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

  • Scout
  • ****
  • Online Online
  • Posts: 42
  • Respect: +31
    • 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.112 seconds with 20 queries.