Garbled

Modeling Dominion

Over the past, roughly, 8 months I have gotten into playing a game called Dominion. It’s a card game that is often mistaken for Magic: The Gathering, but in many ways it plays more like some of the more complex board games out there (of which Settlers of Catan may be the most widely known, but not the best example for comparison). In it, there is a pool of common cards which each player may purchase on their turn via a currency mechanic. Cards purchased go into your deck which is drawn from  to make hands and periodically shuffled. It has a bit of the deck-building meta-game of Magic, but in a more primary role and without the annoying, money-sink aspect that collectible card games have. Everyone at the table is drawing from the same central pool of cards, so you can’t spend your way into a better deck between games.

Another aspect that I really like is that the pool of cards for purchase is not the same for each game. You (generally) randomly select 10 types from the box. The initial release had something like 28 types in it. There have been expansions released to add variety, but remember, it’s not a CCG, so buying expansions doesn’t give an advantage to any player over others except, I suppose, that they’ll have greater familiarity with what the cards do. I don’t want to get too into the rules and how the games works. Rio Grande has the rules available as a PDF, so you can go read them in full at the link above. What I really want to talk about is a little hacking exercise that I got into because of the game. Henceforth, I’ll assume you’ve at least read the base rules.

The Discussion

I’ve been playing at lunch with some of the guys at work and I got into a discussion with @hoonpark after one such game. The strategy we were discussing was using Chapel and Treasure Map together. For quick reference, Chapel lets you trash up to 4 (other) cards from your hand and Treasure Map lets you, if you have two in your hand, trash both and then put 4 Golds on top of your deck. The idea was to use the Chapel to reduce your deck size such that the likelihood of getting both your Treasure Maps at the same time went way up and then for most of your deck to just be Golds (with which you would buy Provinces). We disagreed on the exact particulars of how it should be played most optimally and I said, “I bet I could code up a simulator that would play this strategy a ton and give us real statistics.” I think the original debate might have been over whether you try to make two pairs of Treasure Maps work before starting to buy Provinces. At least, that’s what I thought would be best, at first. So I got to work the other evening and coded up the following in two or three sittings. Probably a total of an hour and a half or two.

The Simulation

I have the code up on github, or you can look at this gist. It’s messy as hell and you can tell I sort of just wrote it as I thought of it. I did one refactor, which ended up creating the Player class. That part is probably fairly reusable. The other file could probably be refactored and some bits reused. I want to draw your attention to the commented out lines. I made it so that you can uncomment all the puts statements and run it once to see how just one games goes (which might help you learn to replicate the strategy) or you can run it a bunch and just see a summary. I also ran it several times stopping after buying various numbers of Provinces (3 to 6 ended up being interesting).

As I mentioned above, the original idea was to make Treasure Maps work twice before acquiring Provinces. That ended up taking something like 17 turns on average to get 4 Provinces. When I showed it to Hoon, that didn’t match up with his anecdotal experience, so we looked at the difference between what he’d done (much faster) and what I was seeing. After making it so that the bot would only ever do one pair of Treasure Maps, the turn numbers dropped significantly. Another thing that was different was that Hoon would occasionally buy Silver (if he had less than 5 coins) or, say he drew 2 Golds, 2 Coppers and his Chapel, he would not Chapel the Copper and buy a Province. I think we’ve determined that doing those intuitive things are actually slower than taking the turn to do nothing in the first case or Chapeling the Copper and just buying a Gold.

The Data

The data out of this simulation looks like this (I ran 100,000 games):

  • To acquire 3 Provinces, it takes a minimum of 11 turns, max of 13 and average of 13.93
  • To acquire 4 Provinces, min: 12, max: 14, avg: 13.93
  • To acquire 5 Provinces, min: 15, max: 17, avg: 16.93
  • To acquire 6 Provinces, min: 16, max: 18, avg: 17.93

Notice the gap between 4 and 5. It’s spending those two turns buying Gold , probably. I might, for my own curiosity, run it where it buys Duchies instead, but that could have a slowing effect on the following two turns. Speaking of slowing effects, one thing that I found particularly interesting is that if you don’t ever Chapel Estates away, it dramatically increases turn counts. I set a limit of 100 turns and didn’t count those just as a practicality issue. When running this the published way, I never hit it. When running it without Chapeling Estates, you hit it so often that the simulation took long enough that I got worried and killed it. That’s just 3 krufty cards making a huge difference and really underscores why lean deck strategies are often so powerful.

The Limitations

The biggest limitation of this simulation is that it’s playing in a vacuum. There are no opponents and, more pertinently, no one playing Attack cards (or Masquerade, etc.). If an opponent were to bring Theif to the table, that could be potentially murderous to this strategy. I’m not really sure how the simulation would account for that, anyway. I guess you could figure out tons of strategies, then generate sets of Kingdom Cards and see how they fared against each other in various permutations. That sounds like a) a ton of work for me (or another human), b) a ton of work for some computer somewhere and c) like it might take some of the intuitiveness and gut-checking that I find enjoyable in Dominion. So I don’t think I’ll be chasing that down. I might, however, code up a few other strategies to see how they fare. It would be pretty simple to do a “Just Buy Money” to establish a baseline and a Chapel/Remodel; maybe Village/Smithy, since that’s popular and simple.