|
-
I was introduced to Dominion about 6 weeks ago and was immediately hooked! The friend who showed me the game didn't say a word about strategy so I made the noob mistake of buying all the shiny action cards that looked cool. After playing a few games and having no idea how to make a viable strategy, I browsed through these forums to learn about basic strategy. Since then, not only am I addicted to the game, I am also addicted to thinking about strategy. Being a professional software engineer and game developer, my mind has been racing nonstop since my first game about how to build a Dominion AI or at least a good strategy sim.
Over the weekend I wrote a basic strategy simulation that actually plays complete games with two players instead of measuring average turns to four provinces, which seems to be a standard way to measure strategies around here. Since I just started, I have only tested a few different Big Money strategies and then added Smithy. But already, my results are showing that strategies with a longer time to four provinces can and will beat those that just race for the provinces.
I wanted to share these results to see if they hold up against anybody else's work, as a sanity check to make sure I'm not doing something wrong, and to spark conversation about the best ways to test strategies.
Some notable results:
* Strict Big Money vs. Strict Big Money (buy only silver, gold, and provinces) gives player 2 an advantage because of the "win if less turns taken" tiebreaker rule.
* The optimal Big Money strategy I have found so far is to start buying Duchies after the fourth shuffle and Estates after the fifth. It prefers Duchies to gold starting the turn before the fifth shuffle. This strategy trounces strict big money even though its time to four provinces played solo is worse by three turns. It wins frequently with a 3-5 province split because it makes up for it with its other VPs.
* When introducing Smithy, I found that it is best to simply play my modified Big Money strategy and buy one Smithy. The second starts to decrease win % and three Smithies really start to negatively impact the win %. Using a Smithy with strict Big Money yields the fastest time to four provinces by far in this set, but is a very poor performer in a real game. Modified Big Money beats it handily even though its solo time to four provinces is five turns longer!
Here is a table of results. Again, this is only a start and I hope to do a lot more investigation. When I have a friendlier GUI built for my program, I will be happy to share it as well. These results are after runs of 10,000 games.
Strict BM = buy only silver, gold, or province
Modified BM = start buying Duchies after 4th shuffle, Estates after 5th shuffle
SmithyX = Modified BM buying X Smithies
BM Smithy = Strict BM + 1 Smithy
Solo Simulation Times to Four Provinces:
BM Smithy 14.93
Smithy1: 16.24
Smithy2: 16.64
Strict BM: 16.8
Modified BM: 19.76
Full Game Simulations:
P1 Strategy P2 Strategy Turns P1 Win P2 Win Tie
Strict_BM Strict_BM 17.35 24.25% 42.56% 33.19%
Strict_BM Modified_BM 17.86 19.98% 78.13% 1.89%
Strict_BM Smithy1 16.80 6.58% 91.73% 1.69%
Strict_BM Smithy2 16.84 9.71% 88.65% 1.64%
Strict_BM BM_Smithy 16.37 8.55% 70.16% 21.29%
Modified_BM Strict_BM 17.84 85.44% 11.19% 3.37%
Modified_BM Modified_BM 19.03 53.93% 40.30% 5.77%
Modified_BM Smithy1 17.48 30.72% 64.59% 4.69%
Modified_BM Smithy2 17.58 33.45% 62.49% 4.06%
Modified_BM BM_Smithy 16.69 59.03% 35.71% 5.26%
Smithy1 Strict_BM 16.77 94.61% 3.44% 1.95%
Smithy1 Modified_BM 17.50 76.56% 17.64% 5.80%
Smithy1 Smithy1 16.13 53.32% 37.87% 8.81%
Smithy1 Smithy2 16.20 55.85% 36.68% 7.47%
Smithy1 BM_Smithy 15.66 75.00% 18.87% 6.13%
Smithy2 Strict_BM 16.82 92.82% 4.77% 2.41%
Smithy2 Modified_BM 17.52 74.09% 20.71% 5.20%
Smithy2 Smithy1 16.21 50.88% 41.02% 8.10%
Smithy2 Smithy2 16.26 51.99% 40.18% 7.83%
Smithy2 BM_Smithy 15.72 71.86% 21.37% 6.77%
BM_Smithy Strict_BM 16.39 52.28% 18.71% 29.01%
BM_Smithy Modified_BM 16.67 46.64% 48.85% 4.51%
BM_Smithy Smithy1 15.65 26.01% 66.93% 7.06%
BM-Smithy Smithy2 15.72 27.52% 65.02% 7.46%
BM_Smithy BM_Smithy 15.44 25.47% 43.17% 31.36%
My conclusion so far is that it's really only worth evaluating strategies in the context of full game simulations. My simulation program is still really crude and needs a lot of work before being able to attempt more complex strategies, but I found this initial data interesting enough to share.
-
-
Interesting study.
Just a quick question, when implementing Strict BM, or in fact any of these strategies, do you also program the bot not to buy the last Province if doing so would cause it to lose?
-
-
No, actually I didn't think about that! Thanks for catching that. That's exactly the kind of thing I was hoping would come up. Though if I modify Strict Big Money to check for that condition, it's really no longer strict since it would have to buy Duchies or Estates at that point and see if it can catch up. I definitely think that's reasonable though.
I'll add that to the logic and see how it affects these outcomes.
-
-
Okay, so here is the updated data after adding the condition that neither player will buy the last Province if it will cause him to lose the game. Instead, a Duchy or Estate will be bought if available.
P1 Strategy P2 Strategy Turns P1 Win P2 Win Tie
Strict_BM Strict_BM 17.78 36.45% 31.77% 31.78%
Strict_BM Modified_BM 20.10 19.20% 78.81% 1.99%
Strict_BM Smithy1 19.09 7.47% 90.79% 1.74%
Strict_BM Smithy2 19.06 8.71% 89.34% 1.95%
Strict_BM BM_Smithy 16.88 18.60% 59.50% 21.90%
Modified_BM Strict_BM 20.90 85.49% 10.51% 4.00%
Modified_BM Modified_BM 20.36 53.31% 39.72% 6.97%
Modified_BM Smithy1 18.66 30.96% 63.98% 5.06%
Modified_BM Smithy2 18.70 33.87% 61.35% 4.78%
Modified_BM BM_Smithy 18.53 62.64% 31.07% 6.29%
Smithy1 Strict_BM 20.02 94.50% 3.12% 2.38%
Smithy1 Modified_BM 19.21 75.47% 17.45% 7.08%
Smithy1 Smithy1 17.35 53.27% 37.23% 9.50%
Smithy1 Smithy2 17.46 55.00% 35.75% 9.25%
Smithy1 BM_Smithy 17.98 78.99% 14.45% 6.56%
Smithy2 Strict_BM 20.08 92.26% 4.97% 2.77%
Smithy2 Modified_BM 19.15 73.00% 20.61% 6.39%
Smithy2 Smithy1 17.52 50.70% 40.05% 9.25%
Smithy2 Smithy2 17.61 52.59% 38.14% 9.27%
Smithy2 BM_Smithy 17.88 76.26% 16.87% 6.87%
BM_Smithy Strict_BM 16.93 55.07% 10.78% 34.15%
BM_Smithy Modified_BM 18.07 44.74% 49.88% 5.38%
BM_Smithy Smithy1 17.30 23.38% 69.94% 6.68%
BM-Smithy Smithy2 17.21 25.60% 67.04% 7.36%
BM_Smithy BM_Smithy 15.88 34.65% 30.73% 34.62%
The main effects appear to be extending the game up to a few turns in some cases, slightly increasing the chance of ties, and eliminating the player 2 advantage of less turns winning a tie when both players are playing a Province-only strategy until the end.
-
-
Xanadu wrote:
P1 Strategy P2 Strategy Turns P1 Win P2 Win Tie
Strict_BM Strict_BM 17.78 36.45% 31.77% 31.78%
Modified_BM Modified_BM 20.36 53.31% 39.72% 6.97%
Smithy1 Smithy1 17.35 53.27% 37.23% 9.50%
Smithy2 Smithy2 17.61 52.59% 38.14% 9.27%
BM_Smithy BM_Smithy 15.88 34.65% 30.73% 34.62%
Interesting. Could you run your simulations by allowing all players to get equal turns?
-
IrishFire Herself
United States
Indiana
-
My brain goes straight to the toilet when I read "Strict BM." That sounds . . . painful? Odd? Unpleasant, anyway!
-
-
This is great! I wish I had this kind of programming know-how. And this just validates the idea that optimal timing of "alternate" VP cards is just as important as the time to four provinces.
-
Erik Henry
United States
Manvel
Texas
-
Great work! Very interesting to see how simulating the full game flip flops some of the earlier results.
It'll probably be far down the road in your simulations, but I'd be curious to see when intransitive results start showing up (i.e., A beats B, B beats C, and C beat A). I'd assume that would need some of the Attack cards to be used -- since some sort of interaction would be required -- but maybe stacks running out could trigger it too?
Cool stuff!
-
Nate Finch
United States
Harvard
MA
-
Just so you know, I kinda pulled the "four provinces" thing out of my butt. It wasn't a standard, just something I thought might make sense as a way to compare strategies in the early to mid game. Also, if two of these strategies are going head to head, and they're both trying to buy provinces ASAP, then once they both have four, the game is over.... I guess the tie breaker of person with fewer turns is an interesting strategy to go after, and something I hadn't considered.
That being said, I think it's fantastic someone else is doing some programming to check this stuff out... now I have someone to compare notes with!
I'm kinda swamped right now, but I'll compare your times & win percentages to what I get... I can convert my code to run to game completion pretty easily.
-
-
This is definitely an interesting direction. I'd say given your interest in strategies that _don't_ just focus on provinces, you might want to simulate a bureaucrat deck next. That's probably the single card in the base set that best represents a duchy focused strategy. You could probably start off by ignoring the attack component of the card just to keep it simple.
Also, you'll probably want to work up a basic Chapel + Money strategy as another baseline comparison, since that is the strategy that's discussed almost as much as Smithy+Money. I suspect it would perform somewhat more poorly on Duchy buys than smithy, though, so it might get trounced if it attempts your "modified" variation.
There's an interesting article somewhere around here about the Chapel vs. Bureaucrat that discussed exactly your point, where Bureaucrat is behind 5-3 on provinces but has the duchies to make the difference. It's even more pronounced against the chapel since it dumps the initial 3 estates.
-
V L
United States
Virginia
-
I'm glad someone is running full sims now. Some of the sims people have been talking about aren't realistic to me because often people forget things like "how many points everyone else has" or they forget the fact that even if someone has 4 provinces before other people, they might not win. Especially when we throw in certain kinds of cards like Gardens and/or card gainer cards or +1 buys.
-
-
Xanadu wrote:
P1 Strategy P2 Strategy Turns P1 Win P2 Win Tie
Smithy1 Smithy1 17.35 53.27% 37.23% 9.50%
Smithy1 Smithy2 17.46 55.00% 35.75% 9.25%
Smithy2 Smithy1 17.52 50.70% 40.05% 9.25%
Smithy2 Smithy2 17.61 52.59% 38.14% 9.27%
Wow, that's a fairly sizable advantage for first player. I've never seen it shown quantitatively before. Thanks for the data.
Question: Did you optimize duchy and estate buys for strict big money, then just add smithies, or did you add smithies and then optimize duchy and estate buys?
I assume you did the first option, but I think that reoptimizing would produce more accurate results. I'd be curious to see if that changes much.
-
V L
United States
Virginia
-
Stunna wrote: Xanadu wrote:
P1 Strategy P2 Strategy Turns P1 Win P2 Win Tie
Smithy1 Smithy1 17.35 53.27% 37.23% 9.50%
Smithy1 Smithy2 17.46 55.00% 35.75% 9.25%
Smithy2 Smithy1 17.52 50.70% 40.05% 9.25%
Smithy2 Smithy2 17.61 52.59% 38.14% 9.27%
Wow, that's a fairly sizable advantage for first player. I've never seen it shown quantitatively before. Thanks for the data. Question: Did you optimize duchy and estate buys for strict big money, then just add smithies, or did you add smithies and then optimize duchy and estate buys? I assume you did the first option, but I think that reoptimizing would produce more accurate results. I'd be curious to see if that changes much.
I think that certain strategies don't work as well if you are following someone else. Someone on another thread mentioned that if you all you do is imitate someone else's purchases all game, you tend to lose. I contend that certain kingdom cards may provide an advantage to taking them second or at least equalize the gap. It would be interesting to see a reactive/adaptive AI that tries to not just follow but adapt. It starts with small things like "don't buy the last or second to last province if you think you're behind - maybe buy some duchies and/or other vp instead". Some of these techniques/ideas are more advanced programming though. It may even start earlier too. "if it looks like the players ahead in turns are leading with X provinces then consider adapting".
-
Whitney Barnes
California
-
Xanadu wrote: The optimal Big Money strategy I have found so far is to start buying Duchies after the fourth shuffle and Estates after the fifth. It prefers Duchies to gold starting the turn before the fifth shuffle. This strategy trounces strict big money even though its time to four provinces played solo is worse by three turns. It wins frequently with a 3-5 province split because it makes up for it with its other VPs.
Is shuffling really the right criterion? If I play witch against an AI, it probably shouldn't be buying Duchies as early, should it? I made mine to start buying Duchies once the province pile gets to a certain size.
I always sim 4 players against each other; so maybe that's the difference.
-
-
Thanks for all the comments and feedback, everybody! This has been an exciting project to work on and I'm glad it has generated some interest.
Henkka wrote:
Could you run your simulations by allowing all players to get equal turns?
I'll put this option on my list of things to do, but running every simulation with this variant on or off will add a lot of extra data to sift through. I'd rather get it implemented as an option people can set when I distribute this tool so they can experiment with that if they like. I will do it quickly for the ones you quoted where both players face off with the same strategy and post results later.
Erik17 wrote:
It'll probably be far down the road in your simulations, but I'd be curious to see when intransitive results start showing up (i.e., A beats B, B beats C, and C beat A). I'd assume that would need some of the Attack cards to be used -- since some sort of interaction would be required -- but maybe stacks running out could trigger it too?
I've been really interested in this as well. Like you said, when strategies with attacks or other interactions become involved, this could happen. I don't expect it for a while until more complicated strategies involving multiple action types are implemented.
Nate Finch wrote:
That being said, I think it's fantastic someone else is doing some programming to check this stuff out... now I have someone to compare notes with!
I'm kinda swamped right now, but I'll compare your times & win percentages to what I get... I can convert my code to run to game completion pretty easily.
Nate, I really looking forward to collaborating with you and anybody else who is interested in working on this! Even some of the basic strategies have tough decisions to make, and the more people working on it the better. I really want to try to make a strategy definition that can be saved out to XML, so any users can create their own strategies and import them into the program to test them. I don't know if it will be feasible to have enough control in a simple data structure to express all the logic that can go into a complex strategy though. Another possibility is supporting the Lua scripting language, which should be easy enough for most users to write strategies with. That would be way down the road, though.
medwards20x6 wrote:
This is definitely an interesting direction. I'd say given your interest in strategies that _don't_ just focus on provinces, you might want to simulate a bureaucrat deck next. That's probably the single card in the base set that best represents a duchy focused strategy. You could probably start off by ignoring the attack component of the card just to keep it simple.
Also, you'll probably want to work up a basic Chapel + Money strategy as another baseline comparison, since that is the strategy that's discussed almost as much as Smithy+Money. I suspect it would perform somewhat more poorly on Duchy buys than smithy, though, so it might get trounced if it attempts your "modified" variation.
I was actually planning on evaluating Chapel strategies next, but I am actually really intrigued (ha!) by the idea of a Bureaucrat strategy. That will actually be simpler to implement, and the attack portion is no problem. I think I'll put this together next, thanks for the suggestion!
Stunna wrote:
Question: Did you optimize duchy and estate buys for strict big money, then just add smithies, or did you add smithies and then optimize duchy and estate buys?
Yes, the first option is what I did. But then I did attempt to optimize it further by tweaking the timing of when to start buying Duchies and Estates... and I couldn't get a better result than what I was already doing with the modified big money. This is the kind of thing people will be able to tweak when I finish the GUI and can distribute it.
-
-
swbarnes2 wrote:
Is shuffling really the right criterion? If I play witch against an AI, it probably shouldn't be buying Duchies as early, should it? I made mine to start buying Duchies once the province pile gets to a certain size.
I always sim 4 players against each other; so maybe that's the difference.
You're absolutely right that it's a shortcoming of how I defined the strategy. It works well now but it won't when it takes curses or suffers from other attacks. I plan to make the strategy definitions flexible so they can use various triggers such as shuffle #, absolute turn #, remaining provinces, coin density, etc. to choose when to start making different buys.
-
Andrew Hardin
United States
Bentonville
Arkansas
-
The Four Province metric has been around awhile.
My best guess is that it started because it is easier to simulate basic strategies without worrying about the Supply. A full game requires more coding for benefits that are not always that good.
However, when possible I think it is a better metric, though turn order presents a real problem.
What I want to see is a simulation of the impact of a Single Militia buy strategy on a 4-player game (even if you play equal turns). I have a suspicion player 4 is pretty much screwed but I would like to see that tested.
- Lex
-
-
LexH wrote: The Four Province metric has been around awhile.
My best guess is that it started because it is easier to simulate basic strategies without worrying about the Supply. A full game requires more coding for benefits that are not always that good.
Also, if all players are equally devoted to racing for provinces, the first one to get to four is at a distinct advantage as the opponent(s) now have to buy at least one duchy/estate while still getting their quota of 4 provinces. Then the first player just buys a duchy if he can't afford a province in a given turn, etc. Easier to just call winning the race to 4 provinces as synonymous with winning.
As others have pointed out, however, if all players are not equally devoted to racing for provinces (by way of using other VP cards to generate point totals greater than 24), this assumption does not hold. The presence of more victory kingdom cards in the expansions makes it even less likely that players will always race for provinces. For this reason, a good way to defend against a Chapel strategy--the paradigm of a "race for provinces" approach--is simply to force the chapeller to buy all the provinces, or at least 5-6 of them, in order to win.
-
Julien Vion
France
Préseau
-
I tried a simulation myself. The object was to determine whether the original rule was good, or if it would be more fair to finish the turn if the Province stack becomes empty.
I used the following BM strategy:
If 8+, buy Province
ElseIf 5+ and 3- Provinces left, buy Duchy
ElseIf 6+, buy Gold
ElseIf 5+ and 6- Provinces left, buy Duchy
ElseIf 2+ and 3- Provinces left, buy Estate
ElseIf 3+, buy Silver
Else buy nothing.
Here are the results:
An average games lasts 15.4 turns.
1st player wins 27.4% games with 25.9 points
2nd player wins 25.6% games with 25.2 points
3rd player wins 23.9% games with 24.6 points
4th player wins 23.1% games with 24.0 points.
Average points is 24.9, that is 1.6 points per turn.
With the house rule, we obtain:
1st player wins 25.2% games
2nd player wins 25.0% games
3rd player wins 24.8% games
4th player wins 24.9% games.
Although seemingly better, the BM strategy provides nearly no interaction at all. If playing 4th in early game provides 1-2 points worth information about the cards bought by the earlier players, the author rule is better.
-
David desJardins
United States
Burlingame
California
-
scand1sk wrote: Although seemingly better, the BM strategy provides nearly no interaction at all.
In games with more interaction, the disadvantage of going last and being hit by the other players' attacks sooner is even worse.
-
Carl Bussema
United States
Lansing
Michigan
-
scand1sk wrote: I tried a simulation myself. The object was to determine whether the original rule was good, or if it would be more fair to finish the turn if the Province stack becomes empty.
I used the following BM strategy:
If 8+, buy Province
ElseIf 5+ and 3- Provinces left, buy Duchy
ElseIf 6+, buy Gold
ElseIf 5+ and 6- Provinces left, buy Duchy
ElseIf 2+ and 3- Provinces left, buy Estate
ElseIf 3+, buy Silver
Else buy nothing.
Here are the results:
An average games lasts 15.4 turns.
1st player wins 27.4% games with 25.9 points
2nd player wins 25.6% games with 25.2 points
3rd player wins 23.9% games with 24.6 points
4th player wins 23.1% games with 24.0 points.
Average points is 24.9, that is 1.6 points per turn.
With the house rule, we obtain:
1st player wins 25.2% games
2nd player wins 25.0% games
3rd player wins 24.8% games
4th player wins 24.9% games.
Although seemingly better, the BM strategy provides nearly no interaction at all. If playing 4th in early game provides 1-2 points worth information about the cards bought by the earlier players, the author rule is better.
Does that HR also use Virtual Provinces?
-
Nate Finch
United States
Harvard
MA
-
I tweaked my code to run full games and record what player wins the most, and added militia to the supported list of cards (which then requires not just a strategy for playing a hand but a strategy for choosing what to discard - luckily it turns out there's a fairly good heuristic in a game with just militia - 1, discard VP cards (duh), then discard militia if you have more than one, then discard copper, then silver, then gold (though if you're discarding a gold you're in a pretty good position).
I haven't had a chance to run it yet but hopefully tomorrow I can do the 4 player 1 militia each test.
Also, XML to define strategies sounds cool, but it seems like it would be way overly complicated for an end user to modify.
-
Mike Forrey
United States
Yoe
Pennsylvania
-
Although the big money strategy is efficient it can be defeated quite easily. Just make sure you have either a thief or a pirate ship available for purchasing and people will do everthing they can NOT to buy money anymore.
For my regular gorup we normally go with at least 3 attack cards, 6 action cards and 1 multi victory card. This usually keeps the games very competitive and deters anyone from trying the big money game unless they feel like losing badly.
-
Carl Bussema
United States
Lansing
Michigan
-
Another simple strategy would be 1 Baron
Variant A: always play Baron (always discard if you can)
Variant B: only play the Baron if you have the Estate
Variant C: as Variant B until some criteria (# of shuffles, # of provinces left, etc.) is met.
-
-
bearn wrote: Although the big money strategy is efficient it can be defeated quite easily. Just make sure you have either a thief or a pirate ship available for purchasing and people will do everthing they can NOT to buy money anymore.
Big Money generally eats thief for breakfast. Possibly in a 4-player game where 3 are going strict big money and one is going deck-cycling + thief, the thief will be a formidable attack. Pirate Ship, on the other hand, is extremely strong and has led to allegations of brokenness, albeit faulty.
-
|
|
