Let’s play Dominion — how about 20.000 games a second?

During the current Corona crisis, I find myself having a lot of spare time. Instead of using that for something useful, I ended up playing a lot of Dominion, a board game I can highly recommend checking out. It has very good replay value, and especially works well for two players (which many other board games don’t).

Since that wasn’t unproductive enough, I figured hey, I could instead instruct a computer to play Dominion! So here we are …

The program that plays Dominion

I wrote a small C++ application that plays the game. It is split into a pure C++ library that implements the game’s cards and rules, a small language which allows to phrase a strategy, and a very simple user interface interactively visualizing the results.

The Rebuild card (blue), famously considered too strong, winning 90% of games against Smithy-BigMoney (the strategy that buys 2 Smithies and only Money otherwise).

I didn’t implement all cards; see the Readme on the GitHub page for details. The cool thing about this project, I think, is the language I designed to phrase the strategies. It’s really easy to write, and the user interface will compute curves and results from 10.000 games as-you-type in real time.

The language allows to specify both what cards to buy in which order, as well as what to do with them, based on a simple syntax. Ever wanted to know if you should take the Copper offered by Ill-Gotten Gains? I can tell you:

The strategy that only buys Ill-Gotten Gains, never taking the Copper (see bottom part of the script on the left).
… and when always taking the Copper. In this simple case, that is clearly superior.

The idea of the UI is that you always real-time edit the blue player, while you can select one you wrote previously as the adversary (“Select” in the top right). Strategies can be saved and loaded as simple text files.

With this language, it is also possible to write relatively complicated engines, such as the buy-lots-of-highways-then-all-provinces-at-once one:

A Highway megaturn strategy. This one is really shaky — a lot of its parameters change the outcome a lot if changed by just 1.

You can also answer questions you always wanted answered, such as “How many Curses can I expect to give to my enemy by buying 2 Swindlers by turn 15, then turning his Copper into Curses?”

It’s 2.5.

Here’s one that plays Masquerade against Torturer, selecting the Curse from the Torturer’s attack when it has a Masquerade in hand, then passing the Curse right back (see bottom part of script on the left):

Who gets the curses now, huh?

There’s various other nice statistics graphs, such as the average amount of unplayed action cards in your hand by turn, which helps understand why this misguided Conspirator strategy doesn’t work at all:

A pretty dumb conspiracy.

Detailed game flow

Sometimes, it is more interesting to look at a few single games. For this, we can print a log of just one game:

Log of just one game. Click “Run another” to get a new one in milliseconds. This is very useful to debug your strategies.

Some technical background

The application is written in pure C++, with a very small Qt5 UI layer (~400 SLOC) on top. The game library tries to be without any assumptions about how players want to play the cards; it just offers an API and verifies the game’s rules.

On top of the game library, there is a concept of Actors, which execute turns. They can be written in C++ and do whatever they want there, but I found that to be rather cumbersome, which is why I came up with the domain-specific language presented above. This language is implemented as a bison/flex parser. I wanted to try that out; I’ll do it differently next time, it’s kind of a pain. (It’s nice when it is set up, but setting it up is urgh).

A Smithy / Throne Room strategy. Like many Throne Room strategies, it has the problem of having a lot of dead Throne Rooms in its hand, as can be seen from this “unplayed actions” graph.

The scripts in this language are executed by one specific Actor, the “buylist actor”. If you have a strategy which cannot be phrased in the language, you can implement it in C++, and benchmark it against other strategies relatively easily.

Other applications?

During “development” of this project, I found out I’m not the first one with this idea, there’s already at least one amazing application out there which does something similar. I still kept working on this a bit, since different approaches often turn out to have different advantages and disadvantages. I guess mine ended up a bit more flexible, especially if you are willing to write some logic in C++. It’s also quite a bit faster, on my not-that-great laptpop it runs about 20k games a second.

Interested?

I think I’ll stop investing much time into this at this point, it was a fun project for a few weeks but you just got to stop somewhere. If you are interested though, and think there is value in bringing this a bit further, please contribute! I could imagine for example a meta-tournament website which generates a few random decks a day, and then computes a ranking of strategies people submit. Could be quite fun. Would also be nice to have a few more cards implemented.

For more information, see the github page, especially the readme there, which as a lot of detailed info on how the language works.

Categories: Everything

1 reply

  1. Been there, done that. But not nearly as well as you did! Awesome article!

Leave a Reply

Your email address will not be published. Required fields are marked *