My last post ended on the note that Dominion has a finite decision space. I mean by this, that Dominion has only so many options the player can take. Consequently, a round of Dominion should be foreseeable by a computer AI.
To explore this statement, I’m creating a series of posts where we build such an engine. This engine should be usable by an AI. The result should be that for any turn, the AI has a series of options which he then can evaluate by their win percentage. Our end goal is to create multiple AIs which play each a different tactic. Every strategy should be viable. We begin by playing a huge amount of rounds where the computer makes every choice possible, even if garbage, for every game setup possible, i. e. every possible set of 10 supply cards, following the standard rules of Dominion.
To reduce the impossibly huge amount of potential game states, we forsake the requirement that we play every draw and card composition, in math terms permutations, possible. Instead, we only play a huge number of randomized ones, simulating a standard Dominion game, where we reuse a shuffled discard pile a new deck when our deck runs out of cards to redraw.
In short, we need to implement:
- A Dominion game engine with all the rules,
- which is easily expandable for each expansion
- and can list each turn each possible choice to the player.
In this post, we define then a data structure to hold the cards with all their details and effects in a human-readable format.
Let’s boil down each card into their components. Each card has a name, a cost, a type and one or more effects possibly chained into other effects. For example, the card Cellar has the following attributes:
- Name: Cellar
- Cost: 2
- Type: Action
- +1 Action
- Discard Any Number Of Cards
- For each card discarded draw one card.
The first three attributes are simple. The chained effect is much harder to describe, implement and pull off correctly. We can say, that each effect is either a basic one, a special one or a composite one. The basic one provides either a card, a coin, a buy or an action. The special ones use other more complex keywords like “Discard card” or “Gain a card” strung together with a requirement like “any number” or “costing up to $4”. The composite one enables the player to do things with requirements and follow-up effects which are themselves composed of the stated effect types.
All effects in the core set are played out in the order they are stated on the card giving no options or choices which effect we want to play or not.
In this case, Cellar has a list of effects, the basic effect of giving an extra action and a composite one of discarding cards with the choices on the count of the cards. The number of cards discarded is, of course, limited by the number of cards in hand. After we discarded a series of cards, in total X, we then have to execute the follow-up effect which is the basic effect of drawing one card played X times.
Our data structure could look like this, using the YAML data serialization language :
name: Cellar # Name of the card
cost: 2 # Cost of the card
- Action # Is list for cards with multiple types
chain: and # The card is chained and has no OR clause
effect: # The list of chained effects is a list
- # The basic effect is a list
- action # Give actions
- 1 # Give one action
- # second effect
effect: # Composite effect
- Discard card # An effect with
- Any # the requirement of "any"
followed: # The composite effect is then followed by
- effect: # The composite effect which plays an effect
- For each # Play the following effect X times
- # where X is derived from the "any" clause above
- card # The basic effect a tuple which gives one card
A basic effect is a tuple like (“action”, 1). A composite effect with follow-up is a dictionary with an “effect” attribute and a “followed” attribute. The “effect” attribute leads to the special effect tuple “Discard card” keywords and its requirements (or specification) of “any”. The “followed” attribute points to another special effect tuple “For each” keyword and the target effect tuple (“card”, 1).
Describing the data structure is only one side of the coin. How do we implement this chain of actions or effects in the game engine? The “Discard any number of cards” clause must create a local variable which the “For each card discarded” clause then can reference. We tackle that problem when we implement the usage of actions cards in the player’s turn.
In the next post, we describe a possible turn order with player interactions involving attack card types.