1

**Puzzles and Challenges / Best polynomial asymptotic point scoring**

« **on:**January 24, 2020, 01:29:25 am »

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.

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.