Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 2 [All]

Author Topic: Busy Beaver amount of Coin  (Read 1040 times)

0 Members and 1 Guest are viewing this topic.

tim17

  • Navigator
  • ****
  • Offline Offline
  • Posts: 70
  • Respect: +104
    • View Profile
Busy Beaver amount of Coin
« on: April 28, 2017, 09:41:30 pm »
+7

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.
Logged

gkrieg13

  • Witch
  • *****
  • Offline Offline
  • Posts: 482
  • Shuffle iT Username: gkrieg
  • Respect: +403
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #1 on: April 28, 2017, 09:46:05 pm »
+2

\Theta(n2) is easy just with banks.
Logged
twitch: www.twitch.tv/gkrieg

"Wherefore, whoso believeth in God might with surety hope for a better world, yea, even a place at the right hand of God, which hope cometh of faith, maketh an anchor to the souls of men, which would make them sure and steadfast, always abounding in good works, being led to glorify God." - Ether 12:4

ThetaSigma12

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1151
  • Respect: +842
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #2 on: April 28, 2017, 11:16:44 pm »
+5

Logged
If you have a fan card you want to be created, just post about it here! I'd love to take a look at it.

tim17

  • Navigator
  • ****
  • Offline Offline
  • Posts: 70
  • Respect: +104
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #3 on: April 28, 2017, 11:47:50 pm »
+3

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.
Logged

singletee

  • Jester
  • *****
  • Offline Offline
  • Posts: 778
  • Shuffle iT Username: singletee
  • Gold, Silver, Copper, Let's Jam!
  • Respect: +1223
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #4 on: April 29, 2017, 02:29:22 pm »
+4

majiponi

  • Explorer
  • *****
  • Offline Offline
  • Posts: 311
  • Respect: +234
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #5 on: April 29, 2017, 08:12:40 pm »
0

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).
Ferry on Villa, the only card you have in your hand is Quarry. n is any positive interger.

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.
Very good. I tried another card, Storyteller, which was unsuccessful. It lets you infinite. Madman is good, since it limits. I haven't checked whole your solution, but this can let me notice a simple solution for N(n^3).

Quote
Hand: m Madmans, m Remakes, m-3 Market Squares, 2 Golds, 1 Necropolis (m=n/3)

play Necropolis
play Remake to trash 2 Golds to gain 2 Banks, reacting all Market Squares
play Madman to draw all
repeat until you have no Madman

Hand: (m^2-5m+2) Golds, 2m Banks
play all Treasures to earn (2m^3-5m^2-10m+6) coins
« Last Edit: April 30, 2017, 06:59:57 am by majiponi »
Logged

singletee

  • Jester
  • *****
  • Offline Offline
  • Posts: 778
  • Shuffle iT Username: singletee
  • Gold, Silver, Copper, Let's Jam!
  • Respect: +1223
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #6 on: April 30, 2017, 04:57:54 am »
+4

I think I can get Θ(2n)

Kingdom:
Scrying Pool
Workshop
Bridge
King's Court
Lost Arts
Training


Setup:
Training on Workshop
Lost Arts on King's Court


Initial hand:
2 KC, 2 Workshop, 1 Bridge, Θ(n) Scrying Pool

Method:
KC-KC-Bridge-Workshop-Workshop, which lowers KC to cost 4, and get 2 KCs and 4 Workshops.
Play Scrying Pool.
Now KC-KC-WS-WS-WS, WS, this time gaining 10 cards. As it turns out, the optimal thing to get is 4 KCs and 6 Workshops.
Play Scrying Pool.
Each iteration, the number of cards you can gain is 2x-2, where x is the number of cards you gained last time.
Continue in this way, until you've exhausted all Scrying Pools.
Since Workshops are Trained, the number of coins you get is the number of total Workshop plays, which is Θ(2n).


Edit: This can be improved by swapping out Workshop for Artisan, resulting in being able to put back Scrying Pools to gain things in hand, allowing us to start the first round with Θ(n) gains and thus Θ(n*2n) growth overall.
« Last Edit: May 05, 2017, 03:37:38 pm by singletee »
Logged

Deadlock39

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1645
  • Respect: +1607
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #7 on: May 04, 2017, 09:10:36 pm »
0

I'm a bit confused. Is there a difference between this and the "how high can you go" Stef posted? Wouldn't the answer be whatever the big-O of the answer found there?

singletee

  • Jester
  • *****
  • Offline Offline
  • Posts: 778
  • Shuffle iT Username: singletee
  • Gold, Silver, Copper, Let's Jam!
  • Respect: +1223
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #8 on: May 05, 2017, 03:36:02 pm »
+1

I'm a bit confused. Is there a difference between this and the "how high can you go" Stef posted? Wouldn't the answer be whatever the big-O of the answer found there?

No; the answer to Stef's question is a number. Here we need a function (of number of cards in starting hand). Also here's we're looking to produce lots of coins, not necessarily gain lots of cards. But I think any answer here is going to also involve gaining lots of cards.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #9 on: May 05, 2017, 05:06:14 pm »
0

If we use some form of remake/fortress or something I assume that we could get \Theta(4^n) fairly easily. In fact I bet the base of the exponent can be even higher than that. Can we do better than just a constant raised to the n?
Logged

Deadlock39

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1645
  • Respect: +1607
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #10 on: May 05, 2017, 06:49:07 pm »
0

I'm a bit confused. Is there a difference between this and the "how high can you go" Stef posted? Wouldn't the answer be whatever the big-O of the answer found there?

No; the answer to Stef's question is a number. Here we need a function (of number of cards in starting hand). Also here's we're looking to produce lots of coins, not necessarily gain lots of cards. But I think any answer here is going to also involve gaining lots of cards.

I guess I forgot that that was gains, but they produced most of those gains by using coins to buy Travelling Fair. You'd need to work it out again to optimize coins instead of gains, but they got up in the territory of 10^600 coins out of a standard 5 card starting hand right, so that would translate pretty directly to this. 

I'm mostly just saying, surely the solution that problem ended up with is also the best approach to this one?

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #11 on: May 05, 2017, 09:23:02 pm »
+2

That problem started with a 5-card starting hand but an arbitrarily large deck. This one starts with a limited handsize of n and no deck at all. The only applicable part would be when we cash in for stef's problem, which isn't all that great really. Almost all of the work for that problem was in drawing as many cards as possible

I actually really like this problem. What we've done so far is show that for each card (scrying pool) in our hand we can double (or quadruple if we use remake I think) our handsize. I'd be very interested to see if it's possible to get some more powerful operation.
« Last Edit: May 05, 2017, 09:27:58 pm by liopoil »
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #12 on: May 05, 2017, 09:31:39 pm »
0

Stonemasoning golems into scrying pools would probably let us bring the base of the exponent up to 8
Logged

Deadlock39

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1645
  • Respect: +1607
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #13 on: May 05, 2017, 11:12:17 pm »
0

Okay, got it. I missed the no deck part.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #14 on: May 07, 2017, 03:11:33 pm »
+3

Ok, here's the highest exponent base I can get so far: O(168151n)

EDIT: Lurker allows infinite coins, but if I take lurker and hunting grounds out of the kingdom and just use stonemason, I get O(65536n)

Kingdom: Bridge, Fortress, Possession, Golem, Alchemist, Scrying Pool, Stonemason, King's Court, Hunting Grounds, Lurker
Events: Inheritance, Training

Setup: Inherit King's Court, train King's Court.

Hand: Fortress, Scrying Pool, 2x King's Court, Lurker, 2x Stonemason, n - 7 Possessions

Turn: Kc-Kc-Lurker-SM-SM, trashing 3 hunting grounds for 9 estates, 5 fortresses for 2 lurkers and 8 stonemasons, and one Possession for a golem and a scrying pool. Play scrying pool, draw it all.
7x Kc on: 2 lurkers to get 18 more Kc, 8 stonemasons for 33 more stonemasons, and 13 more lurkers, and a pool and an alchemist from the golem, then draw them all with pool. Now I have ~40 spare KC plays...

...and so on. The general plan is:

Have n KC plays, ~3n/4 stonemasons, ~n/4 lurkers. Get ~9n/4 KCs from the lurkers. The stonemasons give 9n/2 gains, which I use for ~27n/8 stonemasons and ~9n/8 lurkers. If I have one scrying pool in hand, trash an alchemist for two scrying pools. If I have two scrying pools in hand and no alchemists, trash a golem for two alchemists. If I have two scrying pools and an alchemist but no golem, then trash a possession for two golems. Otherwise, don't bother. Then play a scrying pool.

I now have ~9n/2 KC plays and the correct proportion of stonemasons and lurkers. Repeat. In the end, I get to play 8n - 60 scrying pools (After the first few rounds, I will be getting the full 8 pools from each possession), and each time the number of King's Courts multiplies by 4.5 . I lose a little bit by forced inefficiencies and having to stonemason for pools sometimes, but that won't effect much. So I can get at least O(4.58n - 60) ~ O(168151n) KC plays and so that many coins too.

My original plan was more complicated than this and involved develop lots of other crazy stuff, but I doubt it would have done much better. I bet this can still be very significantly improved though. I like how this just mainly uses lurkers, stonemasons, and estates, which all cost . Also, is the number of different cards in the kingdom a limitation? I was at one point considering setting up a ridiculous number of cards in the trash that would be an exponential function of n before starting for lurker to get... would this be allowed?

The base of the exponent here is 4.58, because I can get ~8n pools and 4.5 gains/card. In particular, 12 cards (4 KCs, 6 SMs, and 2 lurkers) can gain 54 cards (18 KCs, 27 SMs, and 9 lurkers)... is it possible to improve this ratio or the number of pools? I guess we just need a card costing

The title of this thread is interesting... I don't think busy beaver will be exactly attainable here...
« Last Edit: May 07, 2017, 03:59:40 pm by liopoil »
Logged

singletee

  • Jester
  • *****
  • Offline Offline
  • Posts: 778
  • Shuffle iT Username: singletee
  • Gold, Silver, Copper, Let's Jam!
  • Respect: +1223
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #15 on: May 07, 2017, 03:41:53 pm »
+1

Ok, here's the highest exponent base I can get so far: O(168151n)

Kingdom: Bridge, Fortress, Possession, Golem, Alchemist, Scrying Pool, Stonemason, King's Court, Hunting Grounds, Lurker
Events: Inheritance, Training

Setup: Inherit King's Court, train King's Court.

Hand: Fortress, Scrying Pool, 2x King's Court, Lurker, 2x Stonemason, n - 7 Possessions

Turn: Kc-Kc-Lurker-SM-SM, trashing 3 hunting grounds for 9 estates, 5 fortresses for 2 lurkers and 8 stonemasons, and one Possession for a golem and a scrying pool. Play scrying pool, draw it all.
7x Kc on: 2 lurkers to get 18 more Kc, 8 stonemasons for 33 more stonemasons, and 13 more lurkers, and a pool and an alchemist from the golem, then draw them all with pool. Now I have ~40 spare KC plays...

...and so on. The general plan is:

Have n KC plays, ~3n/4 stonemasons, ~n/4 lurkers. Get ~9n/4 KCs from the lurkers. The stonemasons give 9n/2 gains, which I use for ~27n/8 stonemasons and ~9n/8 lurkers. If I have one scrying pool in hand, trash an alchemist for two scrying pools. If I have two scrying pools in hand and no alchemists, trash a golem for two alchemists. If I have two scrying pools and an alchemist but no golem, then trash a possession for two golems. Otherwise, don't bother. Then play a scrying pool.

I now have ~9n/2 KC plays and the correct proportion of stonemasons and lurkers. Repeat. In the end, I get to play 8n - 60 scrying pools (After the first few rounds, I will be getting the full 8 pools from each possession), and each time the number of King's Courts multiplies by 4.5 . I lose a little bit by forced inefficiencies and having to stonemason for pools sometimes, but that won't effect much. So I can get at least O(4.58n - 60) ~ O(168151n) KC plays and so that many coins too.

My original plan was more complicated than this and involved develop lots of other crazy stuff, but I doubt it would have done much better. I bet this can still be very significantly improved though. I like how this just mainly uses lurkers, stonemasons, and estates, which all cost . Also, is the number of different cards in the kingdom a limitation? I was at one point considering setting up a ridiculous number of cards in the trash that would be an exponential function of n before starting for lurker to get... would this be allowed?

The base of the exponent here is 4.58, because I can get ~8n pools and 4.5 gains/card. In particular, 12 cards (4 KCs, 6 SMs, and 2 lurkers) can gain 54 cards (18 KCs, 27 SMs, and 9 lurkers)... is it possible to improve this ratio or the number of pools? I guess we just need a card costing

The title of this thread is interesting... I don't think busy beaver will be exactly attainable here...

This kingdom can go infinite (particularly, the combination of Training, Inherited King's Courts, Hunting Grounds, and Lurker):

Estate1
   Estate2
      Lurker1 trashing HG, gaining 3 Estates
      Lurker1 gaining HG
      Lurker1 trashing Lurker
   Estate2
      Lurker2 gaining Lurker
      Lurker2 trashing Lurker
      Lurker2 gaining Lurker
   Estate2
      HG1 drawing 4 cards
      HG1 drawing 2 cards
      HG1 drawing nothing
(Repeat)

Scrying Pools are also Lurkable, so that could go infinite as well.

Stonemasoning Possession->Golem->Scrying Pool is great, but I think including Lurker will inevitably enable unlimited gaining of cards that you want to limit.
« Last Edit: May 07, 2017, 03:50:51 pm by singletee »
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #16 on: May 07, 2017, 03:57:58 pm »
0

Ah! Darn, lurker is too powerful. What if I just use stonemason to gain two estates at a time? Then I have 1 KC and 2 Stonemasons gain 4 KC and 8 Stonemasons, so I think that I can get 48n = 65536n.
Logged

JacquesTheBard

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 231
  • Respect: +227
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #17 on: May 08, 2017, 12:49:21 am »
0

Does the +$ token from Training apply to Inherited Estates? I thought they didn't.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #18 on: May 08, 2017, 09:15:39 am »
0

Does the +$ token from Training apply to Inherited Estates? I thought they didn't.
Ok, then just train stonemason instead, doesn't change anything
Logged

trivialknot

  • Apprentice
  • *****
  • Online Online
  • Posts: 299
  • Respect: +357
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #19 on: May 11, 2017, 06:15:03 pm »
0

This isn't quite a solution, but does better than exponential:

Use n cards to generate O(n^2) coins.  Play Storyteller, draw O(n^2) new cards.  Now you use those cards to generate O(n^4) coins.  So on and so forth.  The idea is that you're limited by the number of storytellers in your starting hand, so you can only generate O(n^(2^n)) coins.

Generating O(n^2) coins is easy.  Say Beggar + Miser.  And Throne Room for actions.

The problem is you need unlimited gains, but somehow be blocked from gaining Storytellers.  There's gotta be a way, right?


BTW, is the idea that it's impossible to generate infinite money given the kingdom, or impossible to generate infinite money given the game-state at the start of the turn?
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #20 on: May 11, 2017, 08:51:12 pm »
0

Generating the coins should be easy, but you also have to gain n^2 non-storyteller cards with just n cards. I have no idea how that could be done.

I think the idea is that given the kingdom you can't set up a turn that gets an unbounded number of coins.
« Last Edit: May 11, 2017, 08:52:40 pm by liopoil »
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #21 on: May 12, 2017, 05:29:02 am »
0

A way to not be able to gain Storytellers:

Storyteller is a Black Market card (not sure what the rules are for these here). You only have one and canot buy more. In order to play > 1 Storyteller, you have to call Royal Carriages, which you can only do directly after playing Storyteller, so unless there's Crown, you cannot use additional gained RCs to play Storyteller more often.

The problem with this approach is that you have to do all your gaining and money-producing with Treasure cards, which is probably not powerful enough.
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

luser

  • Tactician
  • *****
  • Offline Offline
  • Posts: 402
  • Respect: +287
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #22 on: May 12, 2017, 07:19:00 am »
0

You could relatively easily get something like 2^2^n I am not sure what exactly.

You need tfair, chapel, peasant, page, scrying pool, watchtower. As optimal coins is hard lets do easy estimate.

Drawing deck is easy as its only actions and you topdeck last discipled poll to draw it.

At i-th round you start with x coins. With tfair you could buy x/4 peasants. Next turn just turn them into x/4 soldiers. They give x^2 coins next turn and bound 2^2^n follows.
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #23 on: May 12, 2017, 07:37:54 am »
+2

Here's a strategy to gain an arbitrarily large amount of actions costing $5 or less. This would make the upper limit depend only on how much you can draw:


Ferry on Hunting Grounds, inherited Catacombs.

Put 2 Quarries in play (Black Market). Play Baron with Watchtower in Hand. You can now do the following:

Trash the gained Estate.
  trigger Catacombs on trash - gain card costing less than Estate (which is now in the trash and thus no longer an action, i.e. it costs $2)
  gain Hunting Grounds (which costs $0)
  trash Hunting Grounds, gaining 3 Estates.
  trash Estate 1 & 2, gaining any actions costing $5 or less
 trash Estate 3, gain Hunting Grounds, repeat.


An issue is that you have to limit actions. A Village added to this would allow you to draw an arbitrarily large amount of cards.
« Last Edit: May 12, 2017, 07:40:00 am by faust »
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #24 on: May 12, 2017, 07:38:48 am »
+1

You could relatively easily get something like 2^2^n I am not sure what exactly.

You need tfair, chapel, peasant, page, scrying pool, watchtower. As optimal coins is hard lets do easy estimate.

Drawing deck is easy as its only actions and you topdeck last discipled poll to draw it.

At i-th round you start with x coins. With tfair you could buy x/4 peasants. Next turn just turn them into x/4 soldiers. They give x^2 coins next turn and bound 2^2^n follows.
I believe we are looking for a solution that only uses a single turn.
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #25 on: May 12, 2017, 10:50:13 am »
0

Here's a strategy to gain an arbitrarily large amount of actions costing $5 or less. This would make the upper limit depend only on how much you can draw:


Ferry on Hunting Grounds, inherited Catacombs.

Put 2 Quarries in play (Black Market). Play Baron with Watchtower in Hand. You can now do the following:

Trash the gained Estate.
  trigger Catacombs on trash - gain card costing less than Estate (which is now in the trash and thus no longer an action, i.e. it costs $2)
  gain Hunting Grounds (which costs $0)
  trash Hunting Grounds, gaining 3 Estates.
  trash Estate 1 & 2, gaining any actions costing $5 or less
 trash Estate 3, gain Hunting Grounds, repeat.


An issue is that you have to limit actions. A Village added to this would allow you to draw an arbitrarily large amount of cards.
Now this idea seems like it has potential... if we use ~n madmen for our draw then we can have O(n2^n) cards and ~n actions left. Not sure what we would do then though... If there was a way to make this only able to gain unlimited cards costing 4 or less then we could use storyteller.
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #26 on: May 12, 2017, 01:18:03 pm »
+2

Some ponderings on this.

1) We can include Royal Carriage; it doesn't break anything unless we also include non-terminals costing $5 or less. Royal Carriage means that all our gains can be actions we use. That was my first intiution, but actually:

2) We can substitute Madmen for City Quarter in order to vastly improve our drawing potential:
- play CQ1, drawing ~n Royal carriages.
- play all Royal Carriages
- play CQ2, call n Royal Carriages. This draws O(n2^n) cards.
- repeat. Calling ~n2^n RCs on the second CQ draws O(n2^(n^2n)) overall we should get something like Ω(n*(2↑↑n)^n) cards drawn (this is a lower bound; the computation seems hard).

3) Once the final card is drawn with the final call on the final RC, we can cash in using e.g. Beggar/Miser for that number squared.

This is pretty crazy stuff... can somebody convince me that Royal Carriage doesn't actually allow arbitrary amounts of draw?
« Last Edit: May 12, 2017, 01:22:45 pm by faust »
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #27 on: May 12, 2017, 01:19:40 pm »
0

(2↑↑n = 2^2^...^2 [n times] for anyone who hasn't seen this yet)
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #28 on: May 12, 2017, 01:32:46 pm »
0

That's pretty insane... I'm concerned that we might be able to get too many actions though. We have to do the baron-watchtower-hunting grounds-catacombs thing for unlimited gains first, right? Yes, it looks like we can only have ~n city quarters total, but I think we might be able to get unlimited +actions and therefore unlimited +cards with hunting grounds. Actually, if we have x royal carriages and hunting grounds then we can call the royal carriages on the last royal carriage for +x actions, then play the hunting grounds and now have 2x royal carriages and hunting grounds. Since we can get unlimited RCs and HGs I think we're stuck.

EDIT: The issue is exactly the "unless we also include non-terminals costing $5 or less". Royal carriage is a non-terminal costing $5 or less.

I totally missed city quarter though when I was looking through cards... I hope we can do something with that.
« Last Edit: May 12, 2017, 01:34:20 pm by liopoil »
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #29 on: May 12, 2017, 01:36:43 pm »
+1

That's pretty insane... I'm concerned that we might be able to get too many actions though. We have to do the baron-watchtower-hunting grounds-catacombs thing for unlimited gains first, right? Yes, it looks like we can only have ~n city quarters total, but I think we might be able to get unlimited +actions and therefore unlimited +cards with hunting grounds. Actually, if we have x royal carriages and hunting grounds then we can call the royal carriages on the last royal carriage for +x actions, then play the hunting grounds and now have 2x royal carriages and hunting grounds. Since we can get unlimited RCs and HGs I think we're stuck.

EDIT: The issue is exactly the "unless we also include non-terminals costing $5 or less". Royal carriage is a non-terminal costing $5 or less.

I totally missed city quarter though when I was looking through cards... I hope we can do something with that.
You cannot call RC on RC since the played RC is no longer in play when you would call the RC from the tavern mat. That is the beauty of why we can include it in this.
« Last Edit: May 12, 2017, 01:42:04 pm by faust »
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #30 on: May 12, 2017, 01:58:30 pm »
0

Oh wow! Ok, it might work...

The kingdom has to be bounded no matter how you play it. So it still has to work if you played 4 quarries... but since city quarter costs I think we still can't gain it from the watchtower trick?

I think everything still works even if we play hunting grounds in between the city quarters... for example, after CQ2 we have n2^n royal carriages... and a hunting grounds, and n actions. That means we can play a hunting grounds n2^n times to draw 4n2^n cards, and repeat that n times for 4nn2^n cards. Hmm, this might just change it to 8↑↑n or something? But yeah, it does seem that actions are limited. I'm impressed
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #31 on: May 12, 2017, 02:11:41 pm »
0

We can also take advantage of the oodles of actions were getting:

After fully resolving 1 City Quarter and call RCs, let's draw a hand of RCs and a single Hunting Grounds. We can use that to quadruple our handsize. Then repeat until there is only 1 actions left. This gives us a factor of 4^x for each step, where x is the number of actions (which is double the number of Royal Carriages called on the City Quarter).

This means that directly before playing Qity Quarter 3, we would have O(8^n*n*2^n)=O(n*16^n) cards in hand.

Iterating (and finally squaring, this would yield


PPE: 1
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #32 on: May 12, 2017, 02:17:47 pm »
0

You can also probably Disciple every City Quarter that you have.

EDIT: Nah, Teacher must not be available.   :(
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #33 on: May 12, 2017, 02:26:23 pm »
+1

I'm thinking that since we can quadruple ~2n times before each city quarter we'll end up with something like 32 ↑↑ n actually. I had the same thought with disciple, but nope.

I'm assuming you meant to use big-O notation there instead of a 0... but that's not really appropriate anymore either. Big-O just swallows up constant factors, and the fact that we have more like n - 5 city quarters rather than n city quarters already decreases the answer by a quintuply-exponential factor.

There's also really no reason to square it at the end. Just draw coppers the last time that we draw.
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #34 on: May 12, 2017, 02:40:00 pm »
0

That's true. We need better notation!

I'm thinking of how to improve performance further. Patrol can draw 7 cards per play, but then only 3 of those are usable.

Actually, what about Patrol + Crossroads? Patrol draws 3 good cards and 4 green cards, Crossroads draws for all the green cards in our hand.
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #35 on: May 12, 2017, 02:44:22 pm »
0

Of course kingdom space might run out. We have:

City Quarter, Hunting Grounds, Catacombs, Royal Carriage, Quarry, Black Market, Watchtower.

We can trigger the trashing stuff by buying a Sprawling Castle off of Black Market, so no Baron needed.

Thus we can handily include Patrol+Crossroads+Island.

EDIT: Patrol is pretty unnecessary as soon as we have > 7 green cards in hand.
« Last Edit: May 12, 2017, 02:50:42 pm by faust »
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #36 on: May 12, 2017, 02:52:38 pm »
0

That's true. We need better notation!

I'm thinking of how to improve performance further. Patrol can draw 7 cards per play, but then only 3 of those are usable.

Actually, what about Patrol + Crossroads? Patrol draws 3 good cards and 4 green cards, Crossroads draws for all the green cards in our hand.
I was just to post about crossroads... but rather than use patrol, I was thinking that we should use crossroads + island in-between city quarters instead of hunting grounds. That should make a huge difference. At this point city quarter is actually mainly serving to give us a large bounded number of actions, and I think it is actually the only card that can do that for us. I thought about trying to incorporate golem but I think it goes unbounded with royal carriage.

Anyway, what we do now is:

CQ1, draw ~n royal carriages, crossroads, and an island.
Crossroads, call the royal carriages, draw O(2^n) islands and O(2^n) royal carriages.
CQ2, call the royal carriages, draw on the order of (2^n)*2^(2^n) royal carriages and a crossroads
Crossroads, call the royal carriages, draw on the order of 2^2^2^n islands and royal carriages, also a crossroads. That only took one action, and we still have 2^n actions left. So do it again and again, and draw 2 ↑↑ (2^n) cards total by my count.
CQ3, call 2 ↑↑ (2^n) royal carriages, ...

I'm not sure how many up-arrows this is anymore. It's at least 3.

EDIT: In case it isn't clear what's happening with the crossroads, each call of crossroads draws only more islands, except for the last one which draws royal carriages. Therefore it always gets just as many royal carriages as it does islands.
« Last Edit: May 12, 2017, 03:19:02 pm by liopoil »
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #37 on: May 12, 2017, 02:55:27 pm »
+1

Island is actually unnecessary since we can always gain Estates from trashing as many Hunting Grounds as we like, so we'd still have 2 free spaces in our kingdom. Feels like there should be still something we can use them for.
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #38 on: May 12, 2017, 03:05:52 pm »
0

Island is actually unnecessary since we can always gain Estates from trashing as many Hunting Grounds as we like, so we'd still have 2 free spaces in our kingdom. Feels like there should be still something we can use them for.
Ah, I forgot that estate counts as an action card. We have three spaces if we put young witch in the black market deck. I think we're at three up-arrows now, but I'm not totally sure. I don't totally remember how debt costs work... are we allowed to stonemason fortunes into city quarters?

EDIT: I think we are. So if we include both then we are down to one spot left, and I think we can use ~2n city quarters. Oh, but I forgot that it's a split pile.
« Last Edit: May 12, 2017, 03:10:58 pm by liopoil »
Logged

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1521
  • Shuffle iT Username: faust
  • Respect: +1908
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #39 on: May 12, 2017, 03:07:45 pm »
0

Island is actually unnecessary since we can always gain Estates from trashing as many Hunting Grounds as we like, so we'd still have 2 free spaces in our kingdom. Feels like there should be still something we can use them for.
Ah, I forgot that estate counts as an action card. We have three spaces if we put young witch in the black market deck. I think we're at three up-arrows now, but I'm not totally sure. I don't totally remember how debt costs work... are we allowed to stonemason fortunes into city quarters?
Yes, but it's not very clear how split piles work with infinite pile sizes. Maybe the first Fortune only waits at position omega+1, then we're out of luck.
Logged
Wins: M30, M36, M41, M53, M55, M63, M66, M71, M74, M75, M77, RMM11, RMM12, RMM14, RMM16, RMM18, RMM23, NMV, M31, M42, M56, M65, RMM20, RMM24, RMM28, M61, RMM22
Losses: NM4, M33, M35, M37, M38, M45, M46, M60, M68, M69, M82, RMM13, RMM21, RMM26, M43, M51, M58, M72, M83, RMM15, RMM33

MVPs: M41, M53, M63, M65, M66, RMM20, RMM24, RMM28
Win percentage: 56.3 (27/48)
Modded games: M40, M50, M59, M69, M79, RMM19, RMM25, RMM30

Most people are complete idiots.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2551
  • Respect: +2437
    • View Profile
Re: Busy Beaver amount of Coin
« Reply #40 on: May 12, 2017, 03:36:49 pm »
+1

A lower bound on the end-result, just to check that it really is three arrows:

Let's assume that every time we play city quarter or crossroads called as many times as we have royal carriages that our hand has just one estate in it to start, even though it will actually be huge. Then if we have x royal carriages, we draw about 2^x royal carriages each time we play crossroads or city quarter. Each time we play a city quarter we get +2x actions (O(x)), and each time we play a crossroads we get -1 action.

CQ1: 1 action, ~n RCs
Crossroads (O(1) times): 2^n RCs, 1 action
CQ2: O(2^n) actions, 2↑(2↑n) RCs
Crossroads (O(2^n) times): 2 ↑↑ (2 ↑ n) RCs
CQ3: 2 ↑↑ (2 ↑ n) actions and RCs
Crossroads (2 ↑↑ (2 ↑ n) times): 2 ↑↑ (2 ↑↑ (2 ↑ n)) RCs

And so on. We end up with ~n layers of "2 ↑↑ (". That's the definition of 2 ↑↑↑ n. In the end just draw coppers and we get 2 ↑↑↑ n coins. I don't think there's much point in trying to be more precise than that. Maybe we should say it's more like 2 ↑↑↑ (n - 5), or if we are allowed to start with fortunes and stonemason them, then maybe 2 ↑↑↑ (2n - 11) or something. If we want to do better than that we need to use the last few kingdom spots to put a whole new layer into the strategy.

From the "How high can you go?" thread:
I'm just watching this thread to see when you guys start using up-arrows.
Also, lol:
A number with more digits than atoms in the universe would require a tetration sort of operation, which I have not seen in dominion.
« Last Edit: May 12, 2017, 03:51:11 pm by liopoil »
Logged
Pages: 1 2 [All]
 

Page created in 0.136 seconds with 21 queries.