2009 October 19
So, Dominion seams to be a hot new game in the friend circles. And I needed a new hobby. And Rival gave express instructions…
So I’ve been writing the game logic and AI to play Dominion on my computer. It seams that writing the basic game mechanics was rather easy, though some of the action cards are much less strait forwards. It was also almost trivial to write an (Stupid) AI capable of playing the game. That said, it doesn’t play the game all that well, but it’s enough to start with. I’ve also started what I deem a Medium AI with several optimizations and minor points of strategy.
The best part about doing this on the computer is that if I turn of the UI and just let the computers play against themselves, they can play 1000 games in about 10 seconds, and I can start to see a more statistical representation on how effective a particular strategy is.
Questions worth investigation:
- Does going first give you a substantial advantage? With multiple (AI) players of the same skill level, using the same strategy, the player going first wins 3-5% more games. So yes, there is a minor advantage. That said, this difference is still substantially smaller than the difference between players of different skill levels. My medium AI wins almost 10% more games than the stupid one, and the medium AI isn’t even that smart yet.
- What new cards would be fun to introduce?
- For a given subset of cards in the game, is there an ideal strategy?
- Is there a general mindset/strategy that prevails regardless of the choice of cards in the game.
So, this is where you come in. Would you be interested in:
- Formalizing general strategies for an AI? I’ll do the implementation, but I’m curious to see what people think of as supirior strategy.
- Formalizing speficic strategies for specific decks. See if you can out-perform a generalized strategy.
- Actually writing code for your own AI strategy?
- AI tournaments.
- AI vs Human tournaments.
- Human tournaments.
- Inventing new cards.
- Playing against AI in a text UI. (The quickest, easiest to implement)
- Playing against AI in a graphic UI. (Will take longer to implement) (Now I really want a Surface dev kit)
- Playing against other human players remotely over a network.
Do speak up, I’d love to hear what people are interested in.
Comments
Z:I would love to see how well this chapel strategy stacks up:
Buy chapels the first two turns. For turns thereafter, use the following priority list (sometimes you can do more than one of these, so do the highest priority and then the next highest priority that's possible, for instance buying a silver and also trashing a copper -- but don't trash a copper that's necessary to buy the silver this turn, etc.):
- if you can buy a province, do it
- if you can buy a gold, do it
- if you can buy a silver, do it unless you have gold in your deck
- if you can chapel an estate, do it
- if you can chapel a copper, do it unless your deck has only:
- 0 silver & 0 gold & 3 copper
- 1 silver & 0 gold & 1 copper
- if you can chapel a silver, do it unless your deck has only:
- 0 or 1 gold
- 1 silver
- if you can chapel a chapel, do it if your deck has 7 or fewer cards
The way this usually goes down is that you chapel your hand down to 3 coppers and, trade up those coppers for silvers and then golds via buying and trashing, then go into a cycle of "buy province when you can, gold when you can't". I can usually get 5 provinces by turn 20-ish, which isn't that far along, and it doesn't really slow down. (It doesn't really sped up after that, either.)
I'm also interested in seeing a village/smithy or laboratory/throneroom "use your entire deck each turn" strategy, but I haven't codified that as thoroughly.
I'd love to see that source code. I've been meaning to try this, myself. :-)
S:
For more cards, there is an expansion called Intrigue, and another expansion on the way. There is a general strategy I'm curious about (and I may have more specific ideas later, but I don't have a lot of time at the moment)
I'm interested in seeing how a no Action Cards strategy would do. So, the AI only purchases Money or Victory Points. Let's say it picks whichever the most expensive it can afford is, but does not buy Copper.
T:
I have references that include the Intrigue expansion (which has messed with my model somewhat already).
- http://www.brettspielwelt.de/Hilfe/Anleitungen/Dominion/Karten
I'll like your strategy and it should be very easy to test. I'll give it a try here soon and see what happens. Let me know what else you come up with.
Z:
It's actually a really viable strategy. I consider it the "base" strategy that any other strategy I try has to beat before I'll consider playing it. Basically you use this priority:
* if you can buy a province, do it
* if you can buy a gold, do it
* if you can buy a silver, do it
The trick is to *not* buy estates or duchies, as that will muck with the treasure/victory balance of your deck, preventing you from buying provinces. You need four silvers or 2 golds and a silver, after all...or hands involving copper, but the point is that you need 3 or 4 treasure cards in your 5-card hand to buy province, so keep your treasure:victory ratio around 4:1. You start out 7:3 == 2.3:1, so buying victory points early in the game really screws you for buying provinces.
T:
Eliminating Estates from the list brings the wins in the already described scenario up to 88.7% (With Gardens and Coppers). Also eliminating Duchies brings you down to 84.6%. Replacing the Duchies with Witches brings you up to 90%.
Buying Moats instead of Estates pushes you up to 92%. Combining this with Witches does not change the outcome much.
That said, my other AIs have a lot of work ahead of them. A reasonably strict priority system does seam to help quite a bit.
Z:
Iiiinteresting. I'd be really interested in seeing how the golddigger AI performs against my chapel strategy above -- in my own games, the chapel strategy is nearly unbeatable, although variants of it (notably, adding markets and/or laboratories) often beat the base strategy.
Also, What are the specs for eliminating both duchies and estates against eliminating just estates? What are the specs for games without Gardens?
T:
Wow, you just butchered me. I've named your AI Gold-Digger
Wins in 100,000 games:
Rival's Gold-Digger AI: 80,361, 80.3%
Medium AI 1: 7,549
Medium AI 2: 7,506
Stupid AI: 2,670
Ties: 1,914
Starting Player Won: 25,913, 25.9%
That said, I haven't implemented about half of the action cards yet, so those may erode your advantage, but wow.
I tried adding Gardens to see if that helped much. It didn't make much difference. But then I added Copper to the list and Gold-Digger went up to 87%. Buying Copper without Gardens drops you down to 79%.
If I let three Gold-Digger's play against each other, they tie 95.5% of games played. The starting player wins 3.2%, and the other two are less than 1%.
Z:
Gardens plus cards that let you gain multiple cards per turn (like Woodshop or Worksmith) and buying as many cards as possible will really crush people. Unless the other player buys a couple gardens as well, and buys a bunch of provinces.
S:
Yeah, I've found that to be the case, too. When I play a Gardens based strategy, I tend to buy up Gardens when possible, and when not, cards that let me get more cards, and always take as many as I can.
Z:
Btw, "golddigger" is what a lot of other people call this strategy, too. :-)
S:
Huzzah! Victory is (presently) mine (roughly 4 times out of 5)
Also, I have spoken with the roommate, and he'd be interested in doing some experiments, if you have an API at some point.
T:
"To play an Action, the player takes an Action card from his hand and lays it face-up in his play area. He announces which card he is playing and follows the instructions written on that card from top to bottom."
Hmm, I've been playing the Spy wrong. Custom actions come after basic actions. I used to play the Spy, peek at my top draw card, optionally discard it, then draw. By the above instructions, I should draw, then peek at my NEXT card and optionally discard it.
Do other people make this mistake?
S:
I'd suspected that that was the correct rule, but when there was ambiguity, I mostly played by a consensus on how it would be played this game.
J:
Please be advised: I just opened up a copy of the Seaside Expansion (at Uncle's, as our demo copy) and it is AWESOME!
T:
Oooh, when can we get our hands on that??
ZB:
I think this is fantastic.
Can you set up your stat generator to report on how often in the course of the game each criteria executes or doesn't? Oh, and how often the entire strategy tree fails. I suck at this game. >.>
Maybe you could set up a little page where your friends can pick a set of cards, write a set strategy tree, and then get a report of how it stacks up against the best play your AI came up with. I'd be in favor of not being told what the AI's strategy was; finding these things out oneself being more fun.
Also, I'm in the process of developing an exploration game. How hard is it to make these AIs? Even the easy and simple tier you first put out would be pretty useful for testing out my game when I get it a bit further along.
T:
"Can you set up your stat generator to report on how often in the course of the game each criteria executes or doesn't?" Probably, but I would only want to for a very specific strategy. Thats a lot of logging.
"Oh, and how often the entire strategy tree fails." - Define fails? I easily count losses, and could even keep track of losses with an especially low score.
"Maybe you could set up a little page where your friends can pick a set of cards, write a set strategy tree, and then get a report of how it stacks up against the best play your AI came up with." - Feel free to post such lists & strategies here. A designer page is more UI work than I'd like to get into, but here's a handy reference: http://dominion.diehrstraits.com/list.html
"Also, I'm in the process of developing an exploration game. How hard is it to make these AIs?" - Path finding algorithms are easy. Priority driven AIs are easy. It's when they have to make choices that don't have clear priority that things get tricky. Here I generally revert to random and it does reasonably well if I let it fail a lot. What kind of AI did you have in mind?
ZB:
1. Fair enough. :)
2. By fail I mean how often the strategy tree fails to be able to give any useable advice and the bot ends up doing nothing with a turn.
3. If I was better at the game I'd play, but I don't have any gambits to try out. UI sucks.
4. I'll shoot you an email about this later on when I'm not at work...
S:
So, another thought I had: I'm curious as to the effect of card counting on the game.
I was thinking in terms of a function (or set of functions) that could be plugged into an AI. Step one is to keep track of how many victory point cards each player has been purchasing. Then, when the priority chart would result in the end of the game, check to see if ending the game in that fashion would result in victory. If not, either demote down the priority chart until a non game ending condition is reached, or purchase a non game ending victory card if possible.
I'm not sure whether or not such a check would make a difference, or if the difference it made would be dependent on the main strategy, so I'm curious as to whether it matters.
T:
I have considered this, and have built in the mechanics to do such card counting. However, I have not attempted an AI that actually takes this into account.
If you want to write out a variable priority chart I'd be glad to test it out.
S:
The idea I had was more of a plug-in for the charts. So something like...
*Check Buy Province
-If I will not lose, do so
-Else check next
*Check Buy Gold
-If I will not lose, do so
-Else check next
Etc. Alternatively...
*Check Buy Province
-If I will not lose, do so
-Else check Buy Duchy
*Check Buy Duchy
-If I will not lose, do so
-Else check Buy Estate
*Check Buy Estate
-If I will not lose, do so
-Else check Buy Estate
-Else check next
*Check Buy Gold
-If I will not lose, do so
-Else check Buy Duchy
*Check Buy Duchy
-If I will not lose, do so
-Else check Buy Estate
*Check Buy Estate
-If I will not lose, do so
-Else check Buy Estate
-Else check next
It would be interesting to see how either of these strategies could effect other AIs, and if one is stronger than the other in general.
Sorry if this is a bit sloppy, btw. I blame pain meds.
SW:
This sounds like a ridiculous amount of fun. I'd love to participate in an AI tournament, or at least try to develop one that would beat the "Medium AI" that you've come up with. In what language have to written all this?
T:
This is all C#. All you have to do is extend the Player class and implement the few key methods like Play, Buy, Choose...
SW:
Could you send me the code? I'd love to play around with it over the weekend.
I miss messing around with projects like these. I used to really enjoy this sort of thing, and sort of stopped doing it once I started at Microsoft.
T:
So I've implemented all of the cards from the base set now, and about half of the Intrigue cards. (it's a fun thing to do on the shuttle in the morning.) There are just a few I don't expect to be able to implement: Bridge, Coppersmith, & Black Market. See here for details - http://dominion.diehrstraits.com/list.html
Johnny says the next expansion, (Seaside?) is awesome, so I'm anxious to get my hand on that.
The other part I've been working on is a learning AI. So far it goes something like this:
- Start playing like my stupidest AI, mostly random.
- When you win a game, remember what cards you bought, played, trashed, etc.
-- Use the averages of this information for prioritizing in future games.
Thus far it looses tournaments frequently. However, in tournaments where it does accidentally find a successful strategy in the first 1000 games, it can maintain that strategy indefinitely, with win ratios above 2 to 1 (still against StupidAI). It's favorites I've observed so far:
- Buy: Copper(30+), Gardens(5), Great Hall(?)
- Buy: Silver(34), Province(6), Masquerade(5)/Pawn(3-4)
I'm very curious to see what else it comes up with.
SW:
Yeah - this is exactly the sort of thing I was interested in trying out!!
I wanted to attempt to program a genetic algorithm to come up with a strategy. It's got a really obvious fitness function, and many of the traits would be really easy to splice with each other. I don't actually think a genetic algorithm is going to come up with anything that would be able to beat a reasonable human player, but I'm really curious as to what local maxima it might run into.
SW:
Oh yeah - I was also very curious: how many players are you using for the games where you pit AI against AI? It seems like the strategies chosen might vary depending on the number of players... You know, running out of Provinces faster, and such.
2009 November 1
Two Dominion related topics:
-
There have been a number of people that have expressed interest in getting together and just talking / testing strategies, especially as they relate to AIs. This sounds like a delightfully nerdy way to spend an afternoon. But when? I’m not free any evenings this coming week, but there is some time next Saturday/Sunday evening if people are interested?
-
Multiple people have expressed a desire to have access to, and possibly even contribute to, the source code for the game engine and AIs. I don’t mind posting static copies to share with a limited number of people, but that doesn’t address the contribution challenge. To really do that I’d have to set up a depot. To avoid legal questions this depot should be private (unless of course Rio Grande would like to contribute?). I have a server on which I could host it myself, but that feels like slight overkill. I also don’t know what good (free) depot software there is? Or bug & work item tracking tools for that matter. Is there a public site where we could host a private depot? Or if I hosted it, what software would people recommend?
That said, I don’t particularly look forward to implementing some of the seaside cards / mechanics, and wouldn’t mind outsourcing the work.
And on a completely unrelated note, thanks for an Awesome Halloween party everyone!
Comments
S:I tried out a modified Gold Digger and ran that. The new one, Gold Digger Market is just that: a Gold Digger AI that purchases Markets when it has 5 coins. Gold Digger Market ties against normal Gold Digger a large amount of the time, but of the non-ties, it beats Gold Digger more often than not. Adding a Chaplin reduces the amount of ties, and nets the Chaplin a fair amount of wins, but never enough to overtakes Gold Digger for second place in the win count.
2009 November 4
They fixed it!!!
I implemented the Dominion : Seaside Duration card mechanic, and the four basic/simple Duration cards. THEY BEAT GoldDigger!!!
Test setup: 10,000 random 2 player games with random cards from the specified decks; MediumAI vs. pure GoldDiggerAI. S = Seaside (5/26 implemented). I = Intrigue (17/25 implemented). B = Basic Dominion (fully implemented). The following shows MediumAI’s win ratio for the given configuration: B: 16% B + I: 14% B + I + S: 18% S + I: 19% B + S: 23% S: 64%
Even StupidAI goes from 1% in a base game to 7% in a Seaside game against GoldDiggerAI.
If their other new cards prove as useful, it might just be worth implementing them, not to mention getting a Seaside set.
Comments
S:Impressive! And that's just an untuned Medium that now has access to the duration cards?
T:
Yup. Just un-tuned Medium AI that can only choose from:
Bazaar,
Caravan,
FishingVillage,
MerchantShip,
Wharf
SW:
I've got an AI running now that beats GoldDigger at 6:1 ratios. It's basically just GoldDigger, but it will grab a Market if it has five coins, a Caravan if it has four coins, and has a little bit of logic to grab a duchy or an estate if there's only one province left.
GoldDigger can definitely be beaten, but I'm interested to note that I played the chapel strategy against it myself, and lost multiple times. It seems I must have been wrong about the strength of the strategy...
SW:
Note: that's a 6:1 ratio when both a Market and a Caravan are included in the cards. When the cards are completely random, it drops to a 2.5 : 1 ratio.
Z:
After our recent talks, I've been playing the golddigger strategy against other strategies, and golddigger consistently loses against the folks I'm playing (who are all very good). This is true for basic, intrigue, and basic+intrigue.
T:
I agree that it can be beaten, but we have yet to be able to outline a strategy that will consistently do so. That said, Seaside now makes Gold Digger outright inferior to an average player, which is great.
T:
A trained PirateAI (Copied from MediumAI) beats pure GoldDiggerAI 89% of the time on Seaside.
B: 16%
B + I: 14%
B + I + S: 29%
S + I: 40%
B + S: 38%
S: 89%
S:
Pirate Ship is a fantastic card, and seems like it would be a particularly good candidate for an anti-Gold Digger.
How do you determine when the Pirate Ship should used to attack and when it should be used as money? I assume you have it be used as money if that would result in getting a Province, but there's a fair bit of room for variation beyond that.
T:
For simplicity I told it to use it's attack whenever it couldn't use its Pirate Treasure to buy a Province.
It also doesn't buy any cards over cost 4 (except Provinces) until the Pirate Ships are gone.
2009 November 18
Check-in 33. That’s the last of the Seaside cards. I also did the promo cards. I declare the game engine functional. Now all we need are brainz!
How goes the Gardener, Rival?
ChrisP?
Others?
I’ve worked a bit more on StatAI, and it’s to the point where it is capable of beating Medium in ~2/10 game series played, and Gold Digger in ~1/10 series. It is really interesting to see the strategies it comes up with. Aperantly a Market and six Militias completely destroys Gold Digger 95% of the time.
Comments
S:I haven't had a chance to work on it recently, but I'll take a look once I get the new code.
S:
I've posted a Gardens AI. It needs the new AITools file that I checked in to work.
T:
Not bad Rival. It destroys Stupid, and does well against Medium (60-70%). It ties a lot with GoldDigger, but doesn't usually beat it.
What shocks me the most is that it doesn't require Gardens to be present. It does just fine on Seaside and Intrigue games, which hardly have any buy-positive cards. On closer inspection it's heavily GoldDigger focused, it just has a preference for Gardens, and buying other cards when the money is gone.
Next challenge. What is the ideal game setup for your GardensAI? I tried building one that was all buy-positive cards and it went horribly.
Note, I've fixed a few glitches and infinite loops in the buy logic. I'll check that in soon.
S:
I'm not surprised. It was late when I did the coding, and that while loop seemed a bit iffy. I do wonder if it would do better if Action cards out prioritized Treasure cards. Tifa also reminded me that there are cards that just give you a card, rather than being explicitly buy positive. I didn't have time to implement specific logic to purchase/utilize such cards.
As for ideal deck, I'm not entirely sure. Gardens, obviously, although I do wonder if Islands would help (the buy and use logic would have to be suitably modified) and I have a feeling that Markets would be a good card to have handy. Perhaps Bureaucrat as well. Tifa has a Gardens specific deck, but that's in Redmond. I'll take a look at it when I get back.