Creating a Dominion AI
There was a recent discussion over whether a brute-force Dominion AI was feasible; the enthusiast claimed that the variety of combos, the random draws, the expanding deck, and the "creative thinking" would make it more difficult than Chess.
Of course, I think that's ridiculous. Dominion is widely agreed to be a fairly shallow game while Chess has lasted hundreds of years. People have been working on Chess AIs for over four decades compared to the handful of people who have bothered coding up the rules to Dominion, and the far fewer (all hobbyist and unsponsored) who have attempted an AI.
There are fewer skill levels between Dominion players and Chess players partly because of the raw amount of decision-making involved. Victor Allis estimated that in a game of Chess, each player makes roughly 40 decisions of 35 options each time (for Go involves each player making 75 decisions each with 250 options). Let's have a look at Dominion.
Hordes of people play Dominion on the Isotropic server; many of them play 2p because it's faster, and they prefer the competitive zero-sum nature of that format. (For the record, I prefer the more fun 4p where piles can run out and more strategies come into play.) Stats show that the simple 2p games (no attacks, no Colonies/Platinum) last for 15 turns, with 18 cards available; therefore there are 15 purchase decisions between 18 options each time - far smaller than Chess.
Even amongst the purchase decisions, players seldom get enough money to make all 18 cards an option - except for near the end of the game, where they will be buying Provices anyway. (In 2p games you can argue that you need 8+ coin just 5 times in order to get 5 of the 8 Provinces and win.)
This isn't the whole picture: games with attacks are longer (sometimes 20-30 turns); there are choices between Action cards, on Action cards, and on other players turns. Additionally, some cards introduce indirect strategic interaction (my favourite type) - for an example if an opponent plays Workshop/Gardens, other players have to to spoil the strategy or they will be wiped out.
Of course, a major difference between Dominion and Chess is the card draw of the former; while it isn't decision-making, it introduces significant outcome-branching. At first glance it looks like this makes the combinations explode.
However, there are significant simplifications:
* You draw your deck each time, so you know exactly what cards you'll get before the next reshuffle, just not the order.
* The order of cards in a hand doesn't matter, just how your deck is divided into hands.
* Your deck is more likely to have multiples of the same card rather than lots of single cards.
* Cards purchased only become accessible after the next reshuffle, therefore it doesn't matter the order they are bought before then.
* The order in which your hands are played usually doesn't matter to opponents.
* The decision-making during the Action phase and with multiple Buys is frequently very simple.
* There are seldom decisions that cause the value of choices to fluctuate wildly (cards like Pirate Ship are the rare cases).
* Analysing the money- and VP-generating potential of a deck is quite simple, making positional evaluation fairly easy.
I've made some lazy attempts at writing Dominion AIs, but haven't tried very hard to model the special card effects. This results in a fairly weak opponent that relies on hardcoded basic strategies. The AI can only use the tricks I've specifically taught it, and will be destroyed out when an unknown combo appears. So using the analysis above can I do better?
Because the randomness of the card draw isn't based on decision-making, it can be modelled effectively using Monte Carlo simulation. Positional evaluation only has to be performed for the reshuffles, with a focus on average deck efficiency over various separations into hands. Cardplay can be dealt with using a separate tactical optimisation system.
It's looking good.
Of course, I think that's ridiculous. Dominion is widely agreed to be a fairly shallow game while Chess has lasted hundreds of years. People have been working on Chess AIs for over four decades compared to the handful of people who have bothered coding up the rules to Dominion, and the far fewer (all hobbyist and unsponsored) who have attempted an AI.
There are fewer skill levels between Dominion players and Chess players partly because of the raw amount of decision-making involved. Victor Allis estimated that in a game of Chess, each player makes roughly 40 decisions of 35 options each time (for Go involves each player making 75 decisions each with 250 options). Let's have a look at Dominion.
Hordes of people play Dominion on the Isotropic server; many of them play 2p because it's faster, and they prefer the competitive zero-sum nature of that format. (For the record, I prefer the more fun 4p where piles can run out and more strategies come into play.) Stats show that the simple 2p games (no attacks, no Colonies/Platinum) last for 15 turns, with 18 cards available; therefore there are 15 purchase decisions between 18 options each time - far smaller than Chess.
Even amongst the purchase decisions, players seldom get enough money to make all 18 cards an option - except for near the end of the game, where they will be buying Provices anyway. (In 2p games you can argue that you need 8+ coin just 5 times in order to get 5 of the 8 Provinces and win.)
This isn't the whole picture: games with attacks are longer (sometimes 20-30 turns); there are choices between Action cards, on Action cards, and on other players turns. Additionally, some cards introduce indirect strategic interaction (my favourite type) - for an example if an opponent plays Workshop/Gardens, other players have to to spoil the strategy or they will be wiped out.
Of course, a major difference between Dominion and Chess is the card draw of the former; while it isn't decision-making, it introduces significant outcome-branching. At first glance it looks like this makes the combinations explode.
However, there are significant simplifications:
* You draw your deck each time, so you know exactly what cards you'll get before the next reshuffle, just not the order.
* The order of cards in a hand doesn't matter, just how your deck is divided into hands.
* Your deck is more likely to have multiples of the same card rather than lots of single cards.
* Cards purchased only become accessible after the next reshuffle, therefore it doesn't matter the order they are bought before then.
* The order in which your hands are played usually doesn't matter to opponents.
* The decision-making during the Action phase and with multiple Buys is frequently very simple.
* There are seldom decisions that cause the value of choices to fluctuate wildly (cards like Pirate Ship are the rare cases).
* Analysing the money- and VP-generating potential of a deck is quite simple, making positional evaluation fairly easy.
I've made some lazy attempts at writing Dominion AIs, but haven't tried very hard to model the special card effects. This results in a fairly weak opponent that relies on hardcoded basic strategies. The AI can only use the tricks I've specifically taught it, and will be destroyed out when an unknown combo appears. So using the analysis above can I do better?
Because the randomness of the card draw isn't based on decision-making, it can be modelled effectively using Monte Carlo simulation. Positional evaluation only has to be performed for the reshuffles, with a focus on average deck efficiency over various separations into hands. Cardplay can be dealt with using a separate tactical optimisation system.
It's looking good.