Print

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

[Asubfive]

We often ask challenges like this: Maximize/minimize n such that there is a kingdom k such that P(k,n).

This is a question of the form: Maximize/minimize n such that for all kingdoms k we have P(k,n).

As remarked by Donald, one of the most obvious choice for P is "A solo player in kingdom k can gain all Provinces in n turns."

Therefore, I ask: What is the minimal n such that a solo player can guarantee gaining all Provinces in n turns no matter what the kingdom?

This minimal n could be called "The Dominion Number" akin to God's Number for Rubik's Cube.

Clarifications:

• The shuffling is random.
• Extra turns like Outpost and Possession turns do not count (but I doubt it matters for the solution).
• Any Black Market deck is allowed (but I also doubt it matters).

[DStu]

Random shuffling means worst case shuffling, as otherwise you can't guarantee that you don't have worse case shuffle luck. And for all kingdoms means without kingdom cards, as we already have a kingdom where bm is optimal.
So the question is how many turns it takes bm to get all provinces with worst shuffle luck
Edit. The proof is even easier here, as we only want Provinces, you could fill the kingdom with altenate Victories, which obviously don't help.
Gardens, Duke, Great Hall, Harem, Vineyard, Silk Road, Feodum, Fairground will all not help. Add Sea Hag and Saboteur, and you have a Kingdom with no cards that will help your BM to get Provinces

[Davio]

Yeah, random shuffling means we're looking for a big Oh kind of thing.

[blueblimp]

Getting all Provinces with pure BM with worst-case shuffling luck sounds very unpleasant. So many 5's and 7's.

[Kirian]

Getting all Provinces with pure BM with worst-case shuffling luck sounds very unpleasant. So many 5's and 7's.

Indeed, just determining worst-case shuffling is going to be a PITA.  With worst-case shuffling I would guess we can put off the first Gold by until at least T8 or T9, and delay the first $8 until probably T16 or later.  Let's see:

Open 2/5 for Silver/-
T3: SCCCE, buy Silver
T4: CCCCE, buy Silver
T5: E|SCCE, buy Silver (Deck is 2S, 5C, E)
T6: SCCCE, buy Silver
T7: SCCE|C, buy Silver (Deck is 4S, 4C, 2E)
T8: SCCCE, buy Silver
T9: SSSCE, buy Gold

Can anyone do worse?

[Schneau]

This probably requires you to get the average worth of cards in your deck over the magical 5/8 = 1.6, since otherwise you can probably go through a shuffle with all $7 hands. Once you are over 1.6, you are guaranteed at least one Province during one time through your deck. Of course, with worst shuffle luck your hand might be 5 Golds, and the rest of your hands being awful. So, it might end up being only one Province per shuffle with worst shuffle luck.

[Kirian]

This probably requires you to get the average worth of cards in your deck over the magical 5/8 = 1.6, since otherwise you can probably go through a shuffle with all $7 hands. Once you are over 1.6, you are guaranteed at least one Province during one time through your deck. Of course, with worst shuffle luck your hand might be 5 Golds, and the rest of your hands being awful. So, it might end up being only one Province per shuffle with worst shuffle luck.

In addition, every Province buy decreases the average card strength.  The question becomes:  is it going to be faster to exceed that average, or to hit that average, buy a Province, buy a Gold, etc.?

[eHalcyon]

This probably requires you to get the average worth of cards in your deck over the magical 5/8 = 1.6, since otherwise you can probably go through a shuffle with all $7 hands. Once you are over 1.6, you are guaranteed at least one Province during one time through your deck. Of course, with worst shuffle luck your hand might be 5 Golds, and the rest of your hands being awful. So, it might end up being only one Province per shuffle with worst shuffle luck.

In addition, every Province buy decreases the average card strength.  The question becomes:  is it going to be faster to exceed that average, or to hit that average, buy a Province, buy a Gold, etc.?

The Province will decrease average value, but all your subpar hands during that shuffle will probably be used to buy more Silver, which should balance out or even push it in your favour when you reshuffle... right?

[Kirian]

This probably requires you to get the average worth of cards in your deck over the magical 5/8 = 1.6, since otherwise you can probably go through a shuffle with all $7 hands. Once you are over 1.6, you are guaranteed at least one Province during one time through your deck. Of course, with worst shuffle luck your hand might be 5 Golds, and the rest of your hands being awful. So, it might end up being only one Province per shuffle with worst shuffle luck.

In addition, every Province buy decreases the average card strength.  The question becomes:  is it going to be faster to exceed that average, or to hit that average, buy a Province, buy a Gold, etc.?

The Province will decrease average value, but all your subpar hands during that shuffle will probably be used to buy more Silver, which should balance out or even push it in your favour when you reshuffle... right?

Actually, you would only want to buy just enough Silver/Gold to bring you back across that threshold, lest you increase the number of turns between shuffles unnecessarily.

I'm thinking that we're looking at N = 40 at least here.

[Tables]

I've worked this one out before. Well, almost. I'll spoiler anyway even though I answer a slightly different question (worst case time for the standard BMU bot ignoring Duchies to get to 4 Provinces)
If I remember correctly, it's 35 to get to 4 Provinces, assuming we follow the standard procedure of buying a Province iff total coin in deck >=17. Obviously, the idea is we hit 5 as often as possible, wasting as much money as possible. However, once we get 5 Silver we can do even better, massively overkilling on some Provinces and getting three Provinces ASAP.

However, there are two problems here. Firstly, if we're going for worst case time, we WON'T pick up those early Provinces, because we know they'll clog our deck up too much. So we make our deck better instead, which means Golds over Provinces and generally setting a higher bar before we start greening. Secondly, we're aiming for 8 Provinces not 4, but again, that just means we set a higher bar before starting.

Actually doing the maths and working out the exact optimum point to switch from Golds to Provinces will be tricky, as we have to bear in mind all kinds of annoying 'worst case' tricks (like, having to buy Golds for $13 switches into missing Provinces and buying Golds with $7)

And considering this, I think Kirian is right. It's almost certainly at least 40 turns, probably even more than that.

[Powerman]

I think a good starting point would be to run a bot with simple buy rules for a ton of simulations and go from there.

[DG]

It's reassuring to know that in a four player game, the players cannot get stuck indefinitely with repeated bad draws that cannot muster 8 coins for a province. If the gold and silver piles are exhausted then someone will eventually get a province buying hand.

[jomini]

It's reassuring to know that in a four player game, the players cannot get stuck indefinitely with repeated bad draws that cannot muster 8 coins for a province. If the gold and silver piles are exhausted then someone will eventually get a province buying hand.

That is true only for simple BM games. Something simple, like adding in minion, can make folks miss their cards and have to make 8 coin in only 4 cards (worst case scenario with militia could be even worse with hands like militia/silver x3/gold cropping up again and again). Likewise swindler may be able to trash all the silver/gold without replacement nor allow any player to hit 8 coin again. Worst case luck with something like apprentice could also deplete the treasures in deck without allowing for game ending.

The bigger thing is that if you deplete two treasure piles you are going to have to have a LOT of 5 hands and the duchy pile will go away long before worst case luck will let the provinces linger (even if the the 3 guys in losing positions refuse to buy duchies). You'd have to really try to force people to get stuck without options for emptying the duchy pile.

[Kirian]

I think a good starting point would be to run a bot with simple buy rules for a ton of simulations and go from there.

The thing is, a bot won't find the worst-case scenario here.  You have to apply the worst possible shuffle luck in order to delay the first Province buy, but a bot can't be programmed to create "worst possible shuffle luck."  And as long as the average card value is under 7/5, you should be able to get through an entire shuffle without hitting $8.

[greatexpectations]

The thing is, a bot won't find the worst-case scenario here.  You have to apply the worst possible shuffle luck in order to delay the first Province buy, but a bot can't be programmed to create "worst possible shuffle luck."  And as long as the average card value is under 7/5, you should be able to get through an entire shuffle without hitting $8.

i think powerman was suggesting something different. more along the lines of running a ton of simulations, isolating the worst few performances, and working from there.

[Sakako]

You could run a bot for, say, a thousand simulations or so on every possible kingdom, and take the upper bound of solo performances. But of course, who wants to do that? And what about in games which use solely cards from Prosperity? They must, by the rules, be Colony games, so Platinums will also be involved, perhaps making for a shorter game.

Of course, it's true that on many kingdoms, Big Money is the worst strategy, so you could work out the worst-shuffle timing for someone to get a province using solely Big Money for a good approximation.

[Powerman]

The thing is, a bot won't find the worst-case scenario here.  You have to apply the worst possible shuffle luck in order to delay the first Province buy, but a bot can't be programmed to create "worst possible shuffle luck."  And as long as the average card value is under 7/5, you should be able to get through an entire shuffle without hitting $8.

i think powerman was suggesting something different. more along the lines of running a ton of simulations, isolating the worst few performances, and working from there.

Exactly.  Have a bot with buy rules of:
8+: Province
6,7: Gold
3,4,5: Silver

And run (say) 100,000 simulations to see how long it takes for the bot to buy 8 provinces.  Then the worst results can be modified to make it entirely "bad luck".  It will at least give us a starting point to go from.

[blueblimp]

This probably requires you to get the average worth of cards in your deck over the magical 5/8 = 1.6, since otherwise you can probably go through a shuffle with all $7 hands. Once you are over 1.6, you are guaranteed at least one Province during one time through your deck. Of course, with worst shuffle luck your hand might be 5 Golds, and the rest of your hands being awful. So, it might end up being only one Province per shuffle with worst shuffle luck.

I think it's worse, because bad shuffle luck will cause your best treasures to miss the shuffle. So you might need to go through your whole deck about twice per Province, even if your money density is good enough.

[DStu]

The thing is, a bot won't find the worst-case scenario here.  You have to apply the worst possible shuffle luck in order to delay the first Province buy, but a bot can't be programmed to create "worst possible shuffle luck."  And as long as the average card value is under 7/5, you should be able to get through an entire shuffle without hitting $8.

i think powerman was suggesting something different. more along the lines of running a ton of simulations, isolating the worst few performances, and working from there.

Exactly.  Have a bot with buy rules of:
8+: Province
6,7: Gold
3,4,5: Silver

And run (say) 100,000 simulations to see how long it takes for the bot to buy 8 provinces.  Then the worst results can be modified to make it entirely "bad luck".  It will at least give us a starting point to go from.

I don't think we will get even near, but for the lulz:
500.000.000 sims, maximum is 40 turns: record is 40 (3 times)
Number of turns:  Money on turn #

Code: [Select]

40:  4 3 5 6 4 8 5 4 8 5 5 4 10 5 5 5 7 7 3 8 9 5 10 7 6 7 4 12 7 7 5 7 7 7 6 7 5 6 6 14
40:  2 5 5 3 8 4 2 8 5 5 1 8 8 4 5 2 4 9 4 8 4 5 8 2 4 6 7 5 4 6 7 7 6 6 7 5 6 7 6 9
40:  4 3 4 4 4 8 4 5 6 9 5 5 5 4 8 9 5 5 4 11 5 7 5 5 7 7 7 7 6 9 7 6 11 6 7 5 7 6 7 9


[blueblimp]

The thing is, a bot won't find the worst-case scenario here.  You have to apply the worst possible shuffle luck in order to delay the first Province buy, but a bot can't be programmed to create "worst possible shuffle luck."  And as long as the average card value is under 7/5, you should be able to get through an entire shuffle without hitting $8.

i think powerman was suggesting something different. more along the lines of running a ton of simulations, isolating the worst few performances, and working from there.

Exactly.  Have a bot with buy rules of:
8+: Province
6,7: Gold
3,4,5: Silver

And run (say) 100,000 simulations to see how long it takes for the bot to buy 8 provinces.  Then the worst results can be modified to make it entirely "bad luck".  It will at least give us a starting point to go from.

I don't think we will get even near, but for the lulz:
500.000.000 sims, maximum is 40 turns: record is 40 (3 times)
Number of turns:  Money on turn #

Code: [Select]

40:  4 3 5 6 4 8 5 4 8 5 5 4 10 5 5 5 7 7 3 8 9 5 10 7 6 7 4 12 7 7 5 7 7 7 6 7 5 6 6 14
40:  2 5 5 3 8 4 2 8 5 5 1 8 8 4 5 2 4 9 4 8 4 5 8 2 4 6 7 5 4 6 7 7 6 6 7 5 6 7 6 9
40:  4 3 4 4 4 8 4 5 6 9 5 5 5 4 8 9 5 5 4 11 5 7 5 5 7 7 7 7 6 9 7 6 11 6 7 5 7 6 7 9


Interesting that these allow the bot to buy an early Province, introducing a dead card into the deck and wasting money that could have been spent on treasure. I know that BMU teaches that early Provinces are bad, but it's neat to see a random simulation pick up on it.

[DStu]

The thing is, a bot won't find the worst-case scenario here.  You have to apply the worst possible shuffle luck in order to delay the first Province buy, but a bot can't be programmed to create "worst possible shuffle luck."  And as long as the average card value is under 7/5, you should be able to get through an entire shuffle without hitting $8.

i think powerman was suggesting something different. more along the lines of running a ton of simulations, isolating the worst few performances, and working from there.

Exactly.  Have a bot with buy rules of:
8+: Province
6,7: Gold
3,4,5: Silver

And run (say) 100,000 simulations to see how long it takes for the bot to buy 8 provinces.  Then the worst results can be modified to make it entirely "bad luck".  It will at least give us a starting point to go from.

I don't think we will get even near, but for the lulz:
500.000.000 sims, maximum is 40 turns: record is 40 (3 times)
Number of turns:  Money on turn #

Code: [Select]

40:  4 3 5 6 4 8 5 4 8 5 5 4 10 5 5 5 7 7 3 8 9 5 10 7 6 7 4 12 7 7 5 7 7 7 6 7 5 6 6 14
40:  2 5 5 3 8 4 2 8 5 5 1 8 8 4 5 2 4 9 4 8 4 5 8 2 4 6 7 5 4 6 7 7 6 6 7 5 6 7 6 9
40:  4 3 4 4 4 8 4 5 6 9 5 5 5 4 8 9 5 5 4 11 5 7 5 5 7 7 7 7 6 9 7 6 11 6 7 5 7 6 7 9


Interesting that these allow the bot to buy an early Province, introducing a dead card into the deck and wasting money that could have been spent on treasure. I know that BMU teaches that early Provinces are bad, but it's neat to see a random simulation pick up on it.

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.

[RyanRomanik]

Is there any chance that buying copper at 0-2 would help? I know it's normally bad, but since we're basically assuming all of our good cards are going to be constantly missing reshuffles, maybe it would increase the average $/hand of our effective deck.

[Schneau]

This probably requires you to get the average worth of cards in your deck over the magical 5/8 = 1.6, since otherwise you can probably go through a shuffle with all $7 hands. Once you are over 1.6, you are guaranteed at least one Province during one time through your deck. Of course, with worst shuffle luck your hand might be 5 Golds, and the rest of your hands being awful. So, it might end up being only one Province per shuffle with worst shuffle luck.

I think it's worse, because bad shuffle luck will cause your best treasures to miss the shuffle. So you might need to go through your whole deck about twice per Province, even if your money density is good enough.

This is true, but maybe the player can combat this by not buying Silvers when unnecessary to try to have a multiple of 5 cards in their deck every reshuffle? Actually, having 0, 1, or 2 cards missing the reshuffle shouldn't be too big of a deal, so the player could try to get those most of the time instead of the bad 3 or 4 cards missing. Since there's no drawing, this is relatively easy to do, but it's unclear how much it will hurt to miss those Silver buys.

[Davio]

It's a fun challenge: optimizing BM while trying to get poor results.

[Kirian]

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

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

[blueblimp]

55 turns is in fact the best that the bot can do. (I modified the program a bit so that instead of buying based on buy rules, the bot selects the option that gets it to win the fastest. This ups the complexity of the calculation, so it takes a couple minutes to run.)

One catch here: if the bot can buy something, it always does. I assume that buying Silver is always better than buying nothing... but you never know.

Code: [Select]

result = 55

Path:
CCVVV[x] CCCCC[S]
CCVVV[x] CCCCC[S] S
SCVVV[S] CCCCC[S] SC
SSSSC[G] CCVVV[x] CCCC
CCCCC[S] CCVVV[x] GSSSS[G]
CCVVV[x] CCCCC[S] SSSSS[P] GG
GGCVV[G] CCCCC[S] SSCVV[S] SSSS
SSSSV[P] CCVVV[x] CCCCC[S] GSSSS[P] GG
GGSSS[P] CCCCC[S] SSCVV[S] SSCVV[S] GSSVV[G]
SCCCV[S] SSCVV[S] SSCVV[S] SSSCV[G] SSSCV[G] GGGGS[P]
CCVVV[x] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GGGGG[P] G
GCCCC[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GSSVV[G] GSSVV[G] GGGGG[P] GG
GGVVV[G] SCCCV[S] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GGGGG[P]

 2  5  2  5  3  5  9  2  5  2 11  2  5 10  7  5  5  8  2  5
11 12  5  5  5  7  5  5  5  7  7 14  2  7  7  7  7  7 15  7
 7  7  7  7  7  7 15  6  5  7  7  7  7  7 15


[DStu]

One catch here: if the bot can buy something, it always does. I assume that buying Silver is always better than buying nothing... but you never know.

So why shouldn't that be the case? First idea: Gold missing the reshuffle due to bought Silver. That proposes a second unmentioned assumption: Not buying Copper.

Looking at the state, and trying to find states where that happens:

Code: [Select]

CCVVV[x] CCCCC[S]
CCVVV[x] CCCCC[S] S
SCVVV[S] CCCCC[S] SC
SSSSC[G] CCVVV[x] CCCC
[/quote]
4 Coppers missing is not that bad I think, and anyway I don't see a way to prevent this.
[code]
CCCCC[S] CCVVV[x] GSSSS[G]
CCVVV[x] CCCCC[S] SSSSS[P] GG
Two Golds missing. So not buying the Silver in the first turn will prevent this. Assuming that the Gold just goes into the SSSSS[P] hand, (so SSSSS->SSSSG, Silver is not bought), this will not help anything here

Code: [Select]

GGCVV[G] CCCCC[S] SSCVV[S] SSSS
4 Silvers missing the reshuffle, assuming we haven't changed anything before. That might be worth trying buying a Copper in the first turn of the previous shuffle. But it's of course hard to see what will happen from here.

Code: [Select]

SSSSV[P] CCVVV[x] CCCCC[S] GSSSS[P] GG
GGSSS[P] CCCCC[S] SSCVV[S] SSCVV[S] GSSVV[G]
SCCCV[S] SSCVV[S] SSCVV[S] SSSCV[G] SSSCV[G] GGGGS[P]
CCVVV[x] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GGGGG[P] G
GCCCC[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GSSVV[G] GSSVV[G] GGGGG[P] GG
GGVVV[G] SCCCV[S] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GGGGG[P]
The last part doesn't look that bad in terms of missing the reshuffles. 2, followed by 2x0, followed by 1G. So maybe drop out a Silver buy the shuffle before that one? Silver will probably not help much in the last shuffles, because you don't want Gold that urgently anymore and 3xSCP is still not a Province. If I counted right, that will also prevent both of the Golds to miss the reshuffle in the next to last shuffle. So that might help.

[Schneau]

55 turns is in fact the best that the bot can do. (I modified the program a bit so that instead of buying based on buy rules, the bot selects the option that gets it to win the fastest. This ups the complexity of the calculation, so it takes a couple minutes to run.)

One catch here: if the bot can buy something, it always does. I assume that buying Silver is always better than buying nothing... but you never know.

Code: [Select]

result = 55

Path:
CCVVV[x] CCCCC[S]
CCVVV[x] CCCCC[S] S
SCVVV[S] CCCCC[S] SC
SSSSC[G] CCVVV[x] CCCC
CCCCC[S] CCVVV[x] GSSSS[G]
CCVVV[x] CCCCC[S] SSSSS[P] GG
GGCVV[G] CCCCC[S] SSCVV[S] SSSS
SSSSV[P] CCVVV[x] CCCCC[S] GSSSS[P] GG
GGSSS[P] CCCCC[S] SSCVV[S] SSCVV[S] GSSVV[G]
SCCCV[S] SSCVV[S] SSCVV[S] SSSCV[G] SSSCV[G] GGGGS[P]
CCVVV[x] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GGGGG[P] G
GCCCC[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GSSVV[G] GSSVV[G] GGGGG[P] GG
GGVVV[G] SCCCV[S] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GGGGG[P]

 2  5  2  5  3  5  9  2  5  2 11  2  5 10  7  5  5  8  2  5
11 12  5  5  5  7  5  5  5  7  7 14  2  7  7  7  7  7 15  7
 7  7  7  7  7  7 15  6  5  7  7  7  7  7 15


Out of curiosity, how do you know this is the worst possible shuffle luck? Not that I don't believe you, but, for example, the fourth shuffle looks like this:

Code: [Select]

SSSSC[G] CCVVV[x] CCCC
Since four cards are missing the reshuffle, couldn't you instead have

Code: [Select]

SCCCV[S] SCCCV[S] SSCV
which makes it so you get 2 Silvers instead of Gold / nothing. Additionally 2 Silvers miss the reshuffle, and next shuffle you will have 1 more card so a Silver can miss that reshuffle as well. Is there some reason that this is better for the person and not worse?

My intuition says that Silver / Silver is worse than Gold / nothing. And in this situation, 2 Silvers makes your average card value 1.1875, where Gold / nothing makes it 1.2. Maybe my intuition is wrong here, which I would definitely believe if you are examining all possible paths through this tree.

[DStu]

If I remember dynamic programming correctly, what he did is the following.

You solve the problem WC(C, S, G, V, c, s, g, v),
which gives you the worst case number of turns for getting 8 Provinces, when your deck starts with C Copper, S Silver, G Gold, V Victory cards in deck and c Copper, s Silver, g Gold, v Victories in the discard.
For all reasonable values of C,S,V,G,c,s,g,v as described above. Now some instances of this problem are pretty easy, for example WC(C, S, G, 11, c, s, g, v) is 0 for all values of CSGcsgv.

So you start with these, save the result, and try to solve WC(C, S,G, 10, c, s, g, v). But that's now also not so difficult, you just look for the worst-case, given this starting points, to gain a Province. You calculate all of them, and go to WC(..., 9, ...), and so on, until you have WC(7, 0, 0, 3, 0, 0, 0, 0), which is what you where looking for.

About like that. Probably you do it recursively starting form WC(7, 0, 0, 3, 0, 0, 0, 0) and only calculate the WCs you really need, but more or less that's the idea.  The important point is that you, in all the branches you get from this starting point, will always be in one of the states described above, and so you only need to calculate each state once, and you are finished when you have calculated WC for all states (or probably a bit earlier).

Edit: So what you do is having a giant/small (depending if you are a human or a computer) table in which you navigate, the cell you are in represents the state of your deck. Once you are in a cell in which you have already been, you can take the short-cut and use just the result from last time.

Edit2: So for me, that counts as examining all paths in this tree.

Edit3: The "small" set from the perspective of the computer actually has 1.5GB, so small is relative...

[DStu]

4 Silvers missing the reshuffle, assuming we haven't changed anything before. That might be worth trying buying a Copper in the first turn of the previous shuffle. But it's of course hard to see what will happen from here.

if I've not made a mistake, it increases to 56 turns if done.

Edit:

The last part doesn't look that bad in terms of missing the reshuffles. 2, followed by 2x0, followed by 1G. So maybe drop out a Silver buy the shuffle before that one? Silver will probably not help much in the last shuffles, because you don't want Gold that urgently anymore and 3xSCP is still not a Province. If I counted right, that will also prevent both of the Golds to miss the reshuffle in the next to last shuffle. So that might help.

Also 55.

[-Stef-]

I like the idea of solving this dynamicly, but I've got a strong feeling some bug still wanders around in this program.

Code: [Select]

result = 55

Path:
CCVVV[x] CCCCC[S]
CCVVV[x] CCCCC[S] S
SCVVV[S] CCCCC[S] SC
SSSSC[G] CCVVV[x] CCCC
CCCCC[S] CCVVV[x] GSSSS[G]


If I read this correctly, after turn 11 you get gold*2, silver * 5 and nothing * 4.  Fresh reshuffle, so no remaining cards.
However this plan...

Code: [Select]

CCVVV[x] CCCCC[S]
CCVVV[x] CCCCC[S] S
SCSVV[S] CCCCC[S] VC
CCVVV[x] CCCCC[S] SSSS
SSSSS[G] CCVVV[x] CCCCC[S]

results in one gold less and one silver more. Still no remaining cards.

I can barely imagine that won't make at least 1 turn difference by the time we get to turn 55/56. How could getting $3 on turn 5 be the worst possible scenario?

[blueblimp]

Hmmm that does look suspect. (On the other hand, maybe S vs G is not a big enough difference to matter for total turns. But as you point out, it's so early that it ought to matter.)

[Jimmmmm]

Perhaps we could use this idea to rate the speed of certain kingdom cards. Eg in a solo game you're guaranteed to be able to have 8 Provinces in x turns given Laboratory or Smithy or whatever is in the kingdom.

[blueblimp]

I gave this a check and the program claims it really doesn't matter whether you have 2G 5S at the end of turn 11 or 1G 6S. Strange, but it gives paths.

Path for 1G 6S:

Code: [Select]

CCVVV[x] CCCCC[S] SSSSS[G] GS
GSVVV[S] CCCCC[S] SSSCC[G] GSSS
GSSSV[P] CCCCV[S] SCCCV[S] SSSSS[P] GG
GGSCC[P] SCCCV[S] SSCVV[S] SSCVV[S] SSSSS[P] G
GGSSS[P] SCCCV[S] SSCVV[S] SSCVV[S] SSSCV[G] SSSCV[G] G
GGGSS[P] CCVVV[x] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GG
GGCVV[G] SSCCC[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GSSVV[G] GGGGG[P] GSS
GSSVV[G] CCVVV[x] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GGGGG[P]

Path for 2G 5S (same as it was before):

Code: [Select]

CCVVV[x] CCCCC[S] SSSSS[P] GG
GGCVV[G] CCCCC[S] SSCVV[S] SSSS
SSSSV[P] CCVVV[x] CCCCC[S] GSSSS[P] GG
GGSSS[P] CCCCC[S] SSCVV[S] SSCVV[S] GSSVV[G]
SCCCV[S] SSCVV[S] SSCVV[S] SSSCV[G] SSSCV[G] GGGGS[P]
CCVVV[x] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GGGGG[P] G
GCCCC[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GSSVV[G] GSSVV[G] GGGGG[P] GG
GGVVV[G] SCCCV[S] SSSCV[G] SSSCV[G] SSSCV[G] SSSCV[G] GSSVV[G] GGGGG[P]


[blueblimp]

If I remember dynamic programming correctly, what he did is the following.

You solve the problem WC(C, S, G, V, c, s, g, v),
which gives you the worst case number of turns for getting 8 Provinces, when your deck starts with C Copper, S Silver, G Gold, V Victory cards in deck and c Copper, s Silver, g Gold, v Victories in the discard.
For all reasonable values of C,S,V,G,c,s,g,v as described above. Now some instances of this problem are pretty easy, for example WC(C, S, G, 11, c, s, g, v) is 0 for all values of CSGcsgv.

So you start with these, save the result, and try to solve WC(C, S,G, 10, c, s, g, v). But that's now also not so difficult, you just look for the worst-case, given this starting points, to gain a Province. You calculate all of them, and go to WC(..., 9, ...), and so on, until you have WC(7, 0, 0, 3, 0, 0, 0, 0), which is what you where looking for.

About like that. Probably you do it recursively starting form WC(7, 0, 0, 3, 0, 0, 0, 0) and only calculate the WCs you really need, but more or less that's the idea.  The important point is that you, in all the branches you get from this starting point, will always be in one of the states described above, and so you only need to calculate each state once, and you are finished when you have calculated WC for all states (or probably a bit earlier).

Edit: So what you do is having a giant/small (depending if you are a human or a computer) table in which you navigate, the cell you are in represents the state of your deck. Once you are in a cell in which you have already been, you can take the short-cut and use just the result from last time.

Edit2: So for me, that counts as examining all paths in this tree.

Edit3: The "small" set from the perspective of the computer actually has 1.5GB, so small is relative...

This is essentially what I did. The state I used was:
- g0, s0, p0: the total number of golds, silvers, and provinces in your deck, respectively
- g, s, c, v: the number of golds, silvers, coppers, and victory cards in your draw deck, respectively

And yeah, I do it recursively to only calculate the states I need, but I don't prune at all, so it could be optimized somewhat.

By good fortune, the size of this table is (barely!) small enough to fit in a reasonable amount of RAM and calculate in a reasonable amount of time. If I were to allow the entire copper pile to be purchasable, I would need to do something crazy, like storing intermediate results on disk.