Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[bitwise]

This puzzle is related to the Best Asymptotic Point Scoring and Asymptotic analysis of kingdoms puzzle.

As in those puzzles, we have a kingdom with unlimited piles, and piles that have differently named cards have their contents repeated. You can choose the repeating order of any of these piles as long as it is a possible legal order in a normal game.

For this puzzle, you can also assume you have perfect luck, and one opponent whose choices you control, but cannot buy or play cards on their turns. For every kingdom, either it is possible to get an unbounded number of points on some turn, or there is a function f(n), where n is the number of turns, that bounds the maximum number of points that you can get by turn n.

For example, with only Bishop in the kingdom, you can trash down to a deck with Gold-Silver-Silver-Bishop-Province, and trash and buy a Province every turn for 5 points. This will give you f(n) = 5n - c, for some constant c that is related to how long it takes to build that deck.

For this puzzle, we are interested in kingdoms whose f(n) is bounded by a polynomial. Out of kingdoms whose f(n) is asymptotically bounded by a polynomial, what is the highest degree polynomial that can be achieved? For example, that Bishop kingdom can achieve O(n). A kingdom of only Gardens can achieve O(n^2). A kingdom of only Gardens and Embargo can achieve O(n^3).

Note that it's pretty easy to have a kingdom that's above polynomial. For example, with only Market in the kingdom, you can play all your markets every other turn (your starting 10 cards are all stop cards), and multiply the number of markets you have by 1.2, giving f(n) ~= 1.2^(n/2) ~= 1.095^n.

I propose two versions of this puzzle:

A) 10 kingdom piles, any number of sideways cards. Black Market is banned.
B) Any number of kingdom piles allowed, any number of sideways cards allowed. Black Market is banned.

[bitwise]

Here's a more substantial kingdom that gives O(n^18) VP:

Artisan, Bank, Cellar, Cobbler, Counting House, Gardens, Ill-Gotten Gains, Masterpiece, Page, Vampire.

There are no +Buys, so we can only buy one card a turn. There's a chain of gainers, Artisan -> Vampire -> Cobbler. In n turns, we can have O(n) Artisans, O(n^2) Vampires, and O(n^3) Cobblers, and at least O(n^4) of any <=4 cost. None of these gainers can gain themselves or anything before them in the chain, so we won't have exponential growth.

With one Page, we can have Champion and so we don't need to worry about Actions. We can gain O(n^4) Pages, so we can also have O(n^4) Heros, letting us have at least O(n^5) of any treasures we desire. Also, using O(n^5) Ill-Gotten Gains, we can have O(n^6) Coppers. Our draw engine can use these Coppers with Counting House and Cellars. We can have O(n^4) Cellars and O(n^3) Counting Houses, so with O(n^3) Counting House/Copper pairs, we will be able to draw O(n^6)*O(n^3) cards in a turn (supposing we had that many cards). With O(n^5) Banks, we can get O(n^10) money, so we can overpay for Masterpiece to have O(n^9) silvers in our deck on our second to last turn. On our last turn, we can draw O(n^9) Silvers and O(n^5) Banks to hit O(n^14) money, overpaying for masterpiece.

Our final deck will have O(n^14) cards (mostly silvers) and O(n^4) Gardens, giving O(n^18) VP. 

[pitythefool]

Here's a more substantial kingdom that gives O(n^18) VP:

Artisan, Bank, Cellar, Cobbler, Counting House, Gardens, Ill-Gotten Gains, Masterpiece, Page, Vampire.

There are no +Buys, so we can only buy one card a turn. There's a chain of gainers, Artisan -> Vampire -> Cobbler. In n turns, we can have O(n) Artisans, O(n^2) Vampires, and O(n^3) Cobblers, and at least O(n^4) of any <=4 cost. None of these gainers can gain themselves or anything before them in the chain, so we won't have exponential growth.

With one Page, we can have Champion and so we don't need to worry about Actions. We can gain O(n^4) Pages, so we can also have O(n^4) Heros, letting us have at least O(n^5) of any treasures we desire. Also, using O(n^5) Ill-Gotten Gains, we can have O(n^6) Coppers. Our draw engine can use these Coppers with Counting House and Cellars. We can have O(n^4) Cellars and O(n^3) Counting Houses, so with O(n^3) Counting House/Copper pairs, we will be able to draw O(n^6)*O(n^3) cards in a turn (supposing we had that many cards). With O(n^5) Banks, we can get O(n^10) money, so we can overpay for Masterpiece to have O(n^9) silvers in our deck on our second to last turn. On our last turn, we can draw O(n^9) Silvers and O(n^5) Banks to hit O(n^14) money, overpaying for masterpiece.

Our final deck will have O(n^14) cards (mostly silvers) and O(n^4) Gardens, giving O(n^18) VP.

It took me some time to digest this.  I would not have expected the exponents to grow as they do by just buying one Artisan per turn.  Quite a stunning result.
One quibble.  Overpaying for Masterpiece with O(n^10) coins yields O(n^10) Silver, so you can bump your result up to O(n^19) VP.

[bitwise]

In that kingdom, our draw is limited to O(n^9) (n^3 counting houses+cellar pairs, n^6 coppers), so even if we gained more silvers beforehand we wouldn't be able to draw more of them. That's why the max money to hit in a turn is limited to n^14. As is, we can only do this megaturn twice before our deck is filled with silvers to draw. If we add a Chancellor effect, then we could do this megaturn a linear number of times to bump up the result to O(n^19).