Dominion > Puzzles and Challenges

Best Asymptotic Point Scoring

(1/15) > >>

tim17:
Suppose you're playing a game of dominion where the kingdom piles are infinite instead of their usual size (and therefore the game never ends). The puzzle is to come up with a strategy that yields the best score as a function (f) of n, the number of turns played so far. Since I believe it's possible to score an unbounded number of points in a single turn on some boards, I want to restrict to only boards where the number of points that can be scored on the nth turn is bounded by a function of n (i.e. no infinite points in a single turn). Ideally, I'd like solutions to work regardless of shuffle luck.

To give a simple example, suppose you opened monument/donate, and then just played monument every turn for the rest of forever. On the nth turn, you would have n-2 points, so in this case f(n) = n-2 = O(n).

To do slightly better, suppose that you trashed down to a golden deck of bishop, silver, silver, gold, province, and trashed the province, buying a new one each turn. This would yield f(n) ~= 5n

It's not too hard to do better than linear in n, but I'm not sure quite how well you can do. I'll add the best that I've come up with so far after not too much thought in spoiler tags below, and leave it up to anyone interested to go crazy with this.

I was thinking about solo games, but feel free to try with 2 players if you think that would help (maybe you can do something with possession).

See also Busy Beaver amount of Coin and How high can you go for similar puzzles.

Function:

f(n) =O(n!)

Strategy: (I don't think this board allows infinite points in a turn, but I haven't thought it through enough to be fully confident.)

Have a vineyard on your island mat, and have a deck containing the following:

2 schemes
2 treasuries
2 scrying pools
potion
k ironworks

turn:

1. start with 2 treasuries, 2 scrying pools, and something else in hand
2. play scrying pools to draw the deck
3. play k ironworks to gain k ironworks
4. play treasuries
5. play schemes
6. play potion
8. Topdeck 2 pools with schemes, and 2 treasuries

You had roughly k actions at the beginning of the turn, now you have roughly 2k actions, for twice as many vineyard points. Next turn, you'll be able to play the 2k ironworks to gain 2k ironworks, and then play the extra scrying pool to play those 2k ironworks to gain another 2k, giving you roughly 6k ironworks in total (and buying another scrying pool). Doing this for n turns will yield O(n!*k) points, hence the value of f(n).

Perhaps one can do (asymptotically) better on this board, I just wanted to come up with something that did reasonably well. Feel free to come up with something better.

liopoil:
Claim 1: It's possible to convert x coins into O(x) points.

An easy way to do this is if your deck has one gardens in it and you buy a masterpiece, you get (x - 3)/10 points. I'm sure there are many more efficient and maybe simpler examples.

Claim 2: You can pretty much always get a specific n-card deck within ~n turns.

This is really easy. Just buy the cards you want and trash the rest.

So take ~n turns to get a deck consisting of the ~n cards you need for the royal carriage-city quarter-crossroads solution to the "busy beaver amount of coins" thread. Then on the last turn go crazy for around 2 ↑↑↑ n points.

Not fully fleshed out, but hopefully it's convincing enough that you can believe that triple arrows can be done. With the extra flexibility in this puzzle I wouldn't be totally shocked if a fourth arrow could be added or something, though.

EDIT: The solution to the busy beaver puzzle involved being able to gain arbitrarily many cards costing less than 5, which is no good here. Hmm, this is another good puzzle...

majiponi:
Kingdom: Chapel, Stonemason, Scrying Pool, Scheme, Fortress, Gardens, Islands, Poacher
Event: Lost Arts

Setup:
put a Garden on your Island Mat
put your +1 Action token on the Stonemason Supply pile
have 2 Scrying Pools in hand
(Your deck has Chapel, Stonemason, 2 Scrying Pools, 2 Schemes, Fortress, 4 Poachers and Potion)

Turn 1
play 2 Schemes, 2 Scrying Pools, 4 Poachers
play 1 Stonemason to trash Fortress to gain 2 Stonemasons
buy Stonemason overpaying \$2P to gain 2 Scrying Pools
topdeck 2 Scrying Pools

Turn 2
play 2 Schemes, 2 Scrying Pools, 4 Poachers
play 4 Stonemasons to trash Fortress to gain 8 Stonemasons
play Scrying Pool
play 8 Stonemasons to trash Fortress to gain 16 Stonemasons
play Scrying Pool
play 16 Stonemasons to trash Fortress to gain 32 Stonemasons
buy Stonemason overpaying \$2P to gain 2 Scrying Pools
topdeck 2 Scrying Pools
...

On n-th turn, you can multiply (4^n)-1 on your score.

Holger:

--- Quote from: majiponi on July 06, 2017, 03:54:19 am ---Kingdom: Chapel, Stonemason, Scrying Pool, Scheme, Fortress, Gardens, Islands, Poacher
Event: Lost Arts

Setup:
put a Garden on your Island Mat
put your +1 Action token on the Stonemason Supply pile
have 2 Scrying Pools in hand
(Your deck has Chapel, Stonemason, 2 Scrying Pools, 2 Schemes, Fortress, 4 Poachers and Potion)

Turn 1
play 2 Schemes, 2 Scrying Pools, 4 Poachers
play 1 Stonemason to trash Fortress to gain 2 Stonemasons
buy Stonemason overpaying \$2P to gain 2 Scrying Pools
topdeck 2 Scrying Pools

Turn 2
play 2 Schemes, 2 Scrying Pools, 4 Poachers
play 4 Stonemasons to trash Fortress to gain 8 Stonemasons
play Scrying Pool
play 8 Stonemasons to trash Fortress to gain 16 Stonemasons
play Scrying Pool
play 16 Stonemasons to trash Fortress to gain 32 Stonemasons
buy Stonemason overpaying \$2P to gain 2 Scrying Pools
topdeck 2 Scrying Pools
...

On n-th turn, you can multiply (4^n)-1 on your score.

--- End quote ---

That's great. I think you can even multiply your score by about (2^N)^n each turn for any number N by a modification of your method: Replace Poacher by Market and increase the (initial) number of potions (and thus Scrying Pools necessary to draw your deck), Schemes and Markets sufficiently so that you can gain N more Scrying Pools at the end of each turn by buying N/2 overpaid Stonemasons.

luser:
I have better f(n)= 2^2^2^(O(n) times) kingdom kc, workshop, city quarter, training, tfair, bridge, gardens.  Deck contains starting cards one gardens, rest are action. Training on workshop

Turn starts by drawing deck with log(d) cq where d is deck size, play kc-bridge. Then you start multiplying workshops/kc. Assume that deck has k kc and k workshops. play k/2 kc on k/2 workshops to gain 3/4k workshops and 3/4k kc then play cq to draw these and repeat by number of cq in deck. If you start with 3 kc and 3 workshops and l cq you will end with 2^l workshops. Coins from training allow you to buy 2^l/10 cq which shows that f(n+1)>=2^f(n) and bound follows.