Dominion > Puzzles and Challenges

Busy Beaver amount of Coin

(1/9) > >>

tim17:
Consider a modification of (1 player) dominion, where supply piles are infinite (or if you don't believe in infinity, arbitrarily large). Suppose also that you start your turn with an n card deck, and all of those n cards are in your hand.

On certain boards, it is possible to construct such a scenario where you are able to generate arbitrarily many coins on your turn (e.g. a board with highway and villa (and n >=4), since you can play 4 highways and then buy and play arbitrarily many villas).

I want to only consider boards on which, for any positive n, the number of coins you can generate is bounded by some (finite) function of n (call it f(n)).

What's the largest achievable f(n)? Clearly you can get at least f(n)=5n (just have a hand with n platinums). However, you can certainly do much better than this. I'll break this up into 2 parts:

1. What's the best O() complexity achievable? Is it O(n^2), O(2^n), O(2^2^n)?

2. Can we also figure out the optimal constant?

I have some thoughts on 1, but probably one can do better than the best I've come up with. Feel free to let me know if you find any issues with my formulation.

gkrieg13:
\Theta(n2) is easy just with banks.

ThetaSigma12:

--- Quote from: gkrieg13 on April 28, 2017, 09:46:05 pm ---\Theta

--- End quote ---
You called?

tim17:
For those interested, I'll outline my best idea with spoiler tags. The first tag contains the board. The second tag contains my approach and result.

Board contains:

Hermit
Bank
Villa
Counterfeit (or whatever nonterminal that gives at least 1 coin and +buy that you want)
Raid



Start your turn with a hand of \Theta(n) madmen, n/4 banks, n/2 silvers, and \Theta(n) counterfeits in hand.

1. Play silvers and counterfeits to get \Theta(n) buys and coins
2. Buy raid to gain n/2 silvers
3. Buy and play villa
4. Play 2 madmen to draw n/2 silvers
5. Play n/2 silvers
6. Buy raid to gain n silvers
7. Buy and play villa
8. Play 3 madmen to draw n silvers
9. Play n silvers
10. Buy raid to gain 2n silvers
11. Buy and play villa
12. Play 4 madmen to draw 2n silvers
...
Keep doing this until you run out of madmen, which will happen after \Theta(\sqrt(n)) iterations.  In total, your madmen
drew \Theta(n*2^(\sqrt(n))) silvers.

After playing all the silvers, play your n/4 banks, each worth \Theta(n*2^(\sqrt(n))) coins apiece.

This yields \Theta(n^2 * 2^(\sqrt(n))) coins overall.

I believe my analysis is correct. If you spot any mistakes, or think there's a way to generate an unbounded amount of coin on this board, feel free to comment. Also, of course feel free to expand on my idea to do better.

singletee:
See also How high can you go

Navigation

[0] Message Index

[#] Next page