Print

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

[DStu]

Any way to pull those out for, say, T > 35, and see if that occurs in more cases?

This was the only thing I outputted, but they don't have such a long runtime (50.000.000 takes about a minute on my single-core 2.0GHz supercomputer), so I can just rerun them tonight.

[Schneau]

Waiting until you have 3 Golds gives you (10x50.000.000)

Code: [Select]

37:  3 4 4 4 5 8 4 6 7 10 5 5 9 6 8 5 5 12 10 6 3 5 7 7 12 5 5 14 7 6 7 6 5 7 7 5 9
37:  5 2 5 4 5 6 5 7 6 6 10 9 1 11 12 4 4 7 5 12 5 5 5 7 10 7 7 7 6 6 7 7 7 8 6 7 12
37:  3 4 5 5 5 4 8 5 5 9 8 5 5 4 11 12 6 9 12 4 5 6 10 9 6 5 7 7 7 6 7 7 13 6 7 4 8
38:  4 3 5 5 5 7 5 5 7 10 9 5 5 6 8 10 6 4 12 5 9 7 6 7 7 10 5 6 7 15 7 4 7 7 7 6 3 10
39:  5 2 5 4 2 6 9 5 2 7 10 8 7 5 5 9 12 2 7 5 10 2 10 3 7 7 4 5 7 7 7 7 7 7 5 7 5 9 11
37:  3 4 2 5 6 5 3 7 8 5 8 9 5 8 12 1 4 5 11 7 5 7 7 3 7 13 6 4 6 7 12 7 7 7 7 6 8
38:  3 4 5 4 5 7 4 5 9 7 6 8 8 10 5 4 13 7 5 4 5 10 3 7 6 7 11 5 7 7 7 6 7 14 7 7 3 14
37:  4 3 4 3 5 5 5 5 7 8 10 5 5 5 12 9 10 8 5 8 5 7 6 6 5 11 5 12 5 7 7 7 7 7 7 7 10
37:  3 4 5 5 3 7 5 8 6 10 8 2 9 9 3 5 7 5 5 7 8 7 4 6 7 11 7 7 7 7 6 7 12 7 6 7 10
38:  5 2 4 4 5 4 5 7 5 9 7 5 3 9 8 10 6 9 5 4 10 8 6 6 7 7 7 7 7 7 7 13 6 6 6 5 7 10
3 early Golds followed by 2 early Provinces.  Overall, they all get 6-7 Provinces quite quickly, followed by long sequences of 7s until you get the last.

Amusingly, only one of those hits the worst-case scenario of not buying Gold until Turn 9.  Any way to pull those out for, say, T > 35, and see if that occurs in more cases?  Any cases where T[gold] < 9 are automatically not worst-case.

(Unless someone could explain why getting the first Gold at 9 is better than getting it at 8.)

Well, not better, but since it appears they are in the same reshuffle, they should be equivalent. It doesn't matter which turn you get a specific card between turns within the same reshuffle (unless some cards miss the reshuffle, but that doesn't appear to be the case here).

[kn1tt3r]

Isn't it possible to at least make sure you have a 5/2 opening?

[DStu]

Isn't it possible to at least make sure you have a 5/2 opening?

If, then we should start further otimized I think.

5/2, next shuffle should also be clear, or? Not? Silver misses the reshuffle, and get a 5/2 again. I would guess. Any doubts so far?

So we are at turn 5, with a guaranteed Silver. This will give at least a Silver, so we could either make this a 5 or a 7.  Probably not totally clear here.

[kn1tt3r]

Isn't it possible to at least make sure you have a 5/2 opening?

If, then we should start further otimized I think.

5/2, next shuffle should also be clear, or? Not? Silver misses the reshuffle, and get a 5/2 again. I would guess. Any doubts so far?

So we are at turn 5, with a guaranteed Silver. This will give at least a Silver, so we could either make this a 5 or a 7.  Probably not totally clear here.

Seems correct.

I would assume that a homogenuous deck is overall more resistant to bad shuffle luck, which maybe makes 7/2 on turns 5 and 6 a bit better (i.e. worse) than 5/5. With 7/2 you can make one of your two Silvers miss the reshuffle, and afterwards you have one Gold to miss reshuffles.

So you have SCCCC on turn 5 and CCEEE on turn 6, with CS missing the reshuffle. Now in turns 7/8 you have basically the same decisions as in the previous turns because you have just one more Gold you don't draw in those turns anyway.

The next thing to achive is to draw most of your high value money in one turn (which might be the one after the next reshuffle), because you don't want a Province yet...

[-Stef-]

I really like this puzzle.
It seems quite complex, with two strategies trying to optimize against each other.
One of them playing, with the most interesting decision "when to buy a province over a gold" (My intuition says it's very late, surely after 10+ gold)
The other one trying to give as many $2, $5 or $max hands as possible. $7 only becomes the magic number very late.

The start I think I can solve by hand, but after this it's really time to write something:

1:  ccccc -> silver
2:  cceee -> -
(-)
3:  ccccc -> silver
4:  cceee -> -
(s)
5:  sccce -> silver
6:  sccce -> silver
(ce)
7:  cceee -> -
8:  ccccc -> silver
(ssss)
9:  sssss -> gold
10: cceee -> -
11: ccccc -> silver
(c)


The first gold can be postponed until turn 11, but then turns 9-10-11 bring silver/silver/gold so this is worse.

[DStu]

So here, if you want, play with it yourself.

Is pretty basic maipulation of vectors of integers, cards are represented by integers. Sourcecode is partly German because it's some old stuff before I joined this forum. Anyway, should not be hard to understand.
1,2,3=Copper,Silver,Gold
4,5,6=Estate,Duchy,Province

make needs g++ to be in the $PATH, otherwise you must change the makefile or compile from hand.

Edit: All you need to change is in worstcase.cpp, in dominion.cpp is just basic game-mechanics.

[Davio]

I guess it can be optimized with pruning non-promising branches?

If you get a Gold on the first or second reshuffle, it's probably not going to be the 40 turn game we're looking for...

[NoMoreFun]

An interesting variant would be one involving other players' attacks.

It'd be interesting to find the dominion number for when you get militia'd every turn after 2, get sea hag'd every turn after 2 (for 10 turns) and other attacks.

The dominion number for being fortune teller'd every turn would be infinity, as once you've bought 7 provinces, you could draw a hand of 5 victory cards, and your deck composed of treasure cards with the other 5 green cards on the bottom. Fortune teller would then discard the treasures, and your next hand would be all green. This can be repeated indefinitely.

Thief/Noble Brigand/Pirate ship/Saboteur/Knight would be able to destroy your silvers before you can amass any.

Of course one thing to take into account is the presence of the attack card in the kingdom, which may change the minimum number (wouldn't happen for militia and sea hag though).

[ehunt]

I'm willing to wager that simulators are not able to find the Dominion number. After turn twenty you have thirty cards in your deck, and 30! is more than the number of drops of water on earth. I don't think you will see the "worst possible shuffles" in 100000 simulations.

[Kirian]

I'm willing to wager that simulators are not able to find the Dominion number. After turn twenty you have thirty cards in your deck, and 30! is more than the number of drops of water on earth. I don't think you will see the "worst possible shuffles" in 100000 simulations.

Yeah.  At best they're going to give us a lower bound, but they might find some ideas for how to do poorly that we hadn't thought of before.  It looks to me like our best lower bound is currently 38 (DStu's last run).  And of course DStu is running 500M simulations, not 100K, though that's obviously not close to 30!.

[Kirian]

I really like this puzzle.
It seems quite complex, with two strategies trying to optimize against each other.
One of them playing, with the most interesting decision "when to buy a province over a gold" (My intuition says it's very late, surely after 10+ gold)
The other one trying to give as many $2, $5 or $max hands as possible. $7 only becomes the magic number very late.

The start I think I can solve by hand, but after this it's really time to write something:

1:  ccccc -> silver
2:  cceee -> -
(-)
3:  ccccc -> silver
4:  cceee -> -
(s)
5:  sccce -> silver
6:  sccce -> silver
(ce)
7:  cceee -> -
8:  ccccc -> silver
(ssss)
9:  sssss -> gold
10: cceee -> -
11: ccccc -> silver
(c)


The first gold can be postponed until turn 11, but then turns 9-10-11 bring silver/silver/gold so this is worse.

So taking from this, I'm seeing at least some rules taking shape for "worst-case scenario":

1:  Within one shuffle, it doesn't matter what order you buy things.
2:  Within one shuffle, cards should be arranged so as to minimize total useful buys that shuffle.
3:  Within each shuffle, one hand's value should be maximized (if we're still buying Golds)

Interesting to note:  3 Golds is the absolute minimum that must be purchased during the game.  With 2G, 40S, 7C, 7E, 7P, the average card value is < 1.6, and you can't guarantee buying a Province on any turn.  We probably want at least 6-9 though before buying Provinces, in reality.

[Jimmmmm]

Of course, your 4th and 5th Golds are dead cards because they will always show up with the other 3 (whenever you're guaranteed to hit 8 in that particular shuffle).

So increasing your Gold count from 3 to 8 effectively adds only $9 to you deck, which spread over 5 cards is very slow progress towards buying Provinces.

[eHalcyon]

Interesting to note:  3 Golds is the absolute minimum that must be purchased during the game.  With 2G, 40S, 7C, 7E, 7P, the average card value is < 1.6, and you can't guarantee buying a Province on any turn.  We probably want at least 6-9 though before buying Provinces, in reality.

Why do you have 7E?

[DStu]

I'm willing to wager that simulators are not able to find the Dominion number. After turn twenty you have thirty cards in your deck, and 30! is more than the number of drops of water on earth. I don't think you will see the "worst possible shuffles" in 100000 simulations.

Yeah.  At best they're going to give us a lower bound, but they might find some ideas for how to do poorly that we hadn't thought of before.  It looks to me like our best lower bound is currently 38 (DStu's last run).  And of course DStu is running 500M simulations, not 100K, though that's obviously not close to 30!.

... and, you don't care about the 30!, but you can strip out internal permutations of coppers (/7!), of Silvers, Golds and Victories. So it's some "30 choose a,b,c and d", which is I think maximized at "30 chooses 7,7,8 and 8" which is 6.423296287122×10^15.
You also don't care in which hand of the shuffle something happens (you only care what misses the reshuffle), so you can also swap hand, but I think that's partly redundant, so you can't just divide by 6!.  But it will bring the number down.

Of course, you also have the search space of the first 20 turns, and that will bring you up a lot again. And 10^15 is still much bigger than 10^8, but I think that explains why the results seems a lot more reasonable that I expected in the begging, like having really long sequences of 7s in the end. You might not find the minimum, but I don't think you can expect to be far away from it in terms of turns. Would be surprised if you could get to 5 more turns.

[Davio]

I'm willing to wager that simulators are not able to find the Dominion number. After turn twenty you have thirty cards in your deck, and 30! is more than the number of drops of water on earth. I don't think you will see the "worst possible shuffles" in 100000 simulations.

Yeah.  At best they're going to give us a lower bound, but they might find some ideas for how to do poorly that we hadn't thought of before.  It looks to me like our best lower bound is currently 38 (DStu's last run).  And of course DStu is running 500M simulations, not 100K, though that's obviously not close to 30!.

But a lot of those shuffles are the same, it doesn't matter which Copper you have in your hand, all that matters is that it is a Copper.

[kn1tt3r]

I really like this puzzle.
It seems quite complex, with two strategies trying to optimize against each other.
One of them playing, with the most interesting decision "when to buy a province over a gold" (My intuition says it's very late, surely after 10+ gold)
The other one trying to give as many $2, $5 or $max hands as possible. $7 only becomes the magic number very late.

The start I think I can solve by hand, but after this it's really time to write something:

1:  ccccc -> silver
2:  cceee -> -
(-)
3:  ccccc -> silver
4:  cceee -> -
(s)
5:  sccce -> silver
6:  sccce -> silver
(ce)
7:  cceee -> -
8:  ccccc -> silver
(ssss)
9:  sssss -> gold
10: cceee -> -
11: ccccc -> silver
(c)


The first gold can be postponed until turn 11, but then turns 9-10-11 bring silver/silver/gold so this is worse.

So taking from this, I'm seeing at least some rules taking shape for "worst-case scenario":

1:  Within one shuffle, it doesn't matter what order you buy things.
2:  Within one shuffle, cards should be arranged so as to minimize total useful buys that shuffle.
3:  Within each shuffle, one hand's value should be maximized (if we're still buying Golds)

Probably one hand's value should also be maximized if a Province buy is inevitable within a shuffle.

[blueblimp]

Getting an exact answer is maybe feasible if you define the bot that's playing. (I mean, if you know the buy rules for the bot.) There aren't that many states your deck can be in with the basic money bot: 0-30 Golds, 0-40 Silvers, 0-7 Provinces, exactly 3 Estates, exactly 7 Coppers. That's only 31*41*8 = 10,168 different possible deck contents, not that many really.

Now, it gets more complicated because of tracking not just deck contents but discard pile (or alternatively draw pile, you only need one) contents too, which brings the number of states to 15,374,016 (calculated by script). But that's still not that many states, for a computer.

[Tables]

Of course, your 4th and 5th Golds are dead cards because they will always show up with the other 3 (whenever you're guaranteed to hit 8 in that particular shuffle).

So increasing your Gold count from 3 to 8 effectively adds only $9 to you deck, which spread over 5 cards is very slow progress towards buying Provinces.

Not true, each Gold beyond the 3rd actually add $2 in value to your deck.

What else would you have been drawing with your three Golds? Two Silver, maybe?

[DStu]

Getting an exact answer is maybe feasible if you define the bot that's playing. (I mean, if you know the buy rules for the bot.) There aren't that many states your deck can be in with the basic money bot: 0-30 Golds, 0-40 Silvers, 0-7 Provinces, exactly 3 Estates, exactly 7 Coppers. That's only 31*41*8 = 10,168 different possible deck contents, not that many really.

Now, it gets more complicated because of tracking not just deck contents but discard pile (or alternatively draw pile, you only need one) contents too, which brings the number of states to 15,374,016 (calculated by script). But that's still not that many states, for a computer.

Problem is that you not only have this 10,000 states, but you also want to know the way to it, so you get something like 10,000^40.

[Jimmmmm]

Of course, your 4th and 5th Golds are dead cards because they will always show up with the other 3 (whenever you're guaranteed to hit 8 in that particular shuffle).

So increasing your Gold count from 3 to 8 effectively adds only $9 to you deck, which spread over 5 cards is very slow progress towards buying Provinces.

Not true, each Gold beyond the 3rd actually add $2 in value to your deck.

What else would you have been drawing with your three Golds? Two Silver, maybe?

You're right of course. Carry on.

[Kirian]

Interesting to note:  3 Golds is the absolute minimum that must be purchased during the game.  With 2G, 40S, 7C, 7E, 7P, the average card value is < 1.6, and you can't guarantee buying a Province on any turn.  We probably want at least 6-9 though before buying Provinces, in reality.

Why do you have 7E?

The 3 key is totally right next to the 7 key.

[blueblimp]

Getting an exact answer is maybe feasible if you define the bot that's playing. (I mean, if you know the buy rules for the bot.) There aren't that many states your deck can be in with the basic money bot: 0-30 Golds, 0-40 Silvers, 0-7 Provinces, exactly 3 Estates, exactly 7 Coppers. That's only 31*41*8 = 10,168 different possible deck contents, not that many really.

Now, it gets more complicated because of tracking not just deck contents but discard pile (or alternatively draw pile, you only need one) contents too, which brings the number of states to 15,374,016 (calculated by script). But that's still not that many states, for a computer.

Problem is that you not only have this 10,000 states, but you also want to know the way to it, so you get something like 10,000^40.

Memoize it.

[blueblimp]

OK, unless I screwed up, this should be the longest it can take a Basic Big Money bot to buy all 8 Provinces: 69 turns. "V" stands for any victory card, since whether it's a Province or Estate doesn't really matter.

(Edit: The printing of cards that missed the reshuffle was broken, so I fixed that.)

Code: [Select]

result = 69

Path:
CCVVV CCCCC
CCVVV SCCCC C
CCVVV GSCCC CC
CCVVV GSCCC CCV
CCVVV GSCCC CCVV
CCVVV CCVVV GSCCC
CVVVV CCVVV GSCCC C
CVVVV CVVVV GSCCC CC
CCVVV CCVVV CCVVV GSC
GSCVV CCVVV CCVVV CCV
CCVVV CCVVV CCVVV GGSC
GGSCV VVVVV CCVVV CCCC
CCCCV CCVVV SVVVV GGCVV
CCVVV CCVVV SCCCV GSVVV GG
GGCVV CCVVV SCCCV SSCVV GSVV
GSVVV CCCCC SSCVV SSCVV GSVVV GG
GGVVV SCCCV SSCVV SSCVV SSSCV SSSCV GG
GGCVV SSCCC SSCCC GSSVV GSSVV GSSVV GSSVV GSS
GSSVV CCCCC SSSCV SSSCV GSSVV GSSVV GSSVV GGGGG

Edit: Here are the per-turn hand cash amounts:

Code: [Select]

2  5  2  6  2  8  2  8  2  8  2  2  8  1  2  8  1  1  8  2
2  2  6  2  2  2  2  2  9  0  2  4  2  2  7  2  2  5  5  7
2  5  5  5  5  5  5  5  6  5  5  5  7  7  7  7  7  7  7  7
7  7  5  7  7  7  7  7 15


[DStu]

Wow, seems like I'm a bit of.

So, waiting a bit until we get the Provinces seems to get this down to 55 turns if you get 6 Golds before you start buying Provinces.