Print

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

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