Simulating card draw and trashing in Dominion

In my previous blog post, I laid out how the Money deck played and started simulating the outcome. This time around I want to mimic how card drawing and trashing of cards affect speed and coin value of the strategy. I’ll define the term domain by which I mean all the cards the player has in his deck combined with his hand and discard pile. The domain is his playing set of cards. By obtaining cards, the player figuratively expands his domain or demesne with buildings, services, or people.

In my current build, each player has a current draw stack and a discard pile. Each turn consists of only drawing, by popping from the list, five cards from the draw stack and counting the coin value. The player then buys Silver, Gold or a Province with the calculated currency worth. The turn ends with discarding the played cards onto the discard pile by appending each card to the discard list. Here is the current version of the simulation code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class DominionPlayer(object):    
    def __init__(self, game):
        self.game = game
        self.deck = [1 for x in range(7)]  # Add Coppers to the deck.
        self.deck.append("E")  # Add Estate to the deck.
        self.deck.append("E")  # Add Estate to the deck.
        self.deck.append("E")  # Add Estate to the deck.
        random.shuffle(self.deck)  # Shuffle deck
        self.discard_pile = []  # Empty Discard Pile
        # print(self.deck)
        self.won = False
        self.buy_log = []

    # Draw a card
    def draw_card(self):
        if not self.deck:
            if self.discard_pile: # Safety measure, if there is no deck, there has to be a non-empty discard_pile.
                self.deck = self.discard_pile
                random.shuffle(self.deck)
                self.discard_pile = []
            else:
                return None

        return self.deck.pop()

    # Play the turn by drawing 5 cards and buying Silvers or Provinces.
    def play_turn(self):
        starting_five = [self.draw_card() for x in range(5)]  # Draw possibly 5 cards
        starting_five = [x for x in starting_five if x]  # Remove None elements from list
        drawn_cards = [x for x in starting_five if x not in ("E", "P")]  # Get only cards with coin value.
        coin_value = sum(drawn_cards)
        bought = self.purchase_new_cards(coin_value)
        for card in starting_five:
            self.discard_pile.append(card)
            # print("Had cards %s, with value %s and bought %s." % (starting_five, coin_value, bought))

    def purchase_new_cards(self, coin_value):
        if coin_value >= 8:
            self.discard_pile.append("P")
            self.buy_log.append("P")
            self.game.player_buys_province(self)
            return "Province"
        elif coin_value >= 6:
            self.discard_pile.append(3)
            self.buy_log.append(3)
            return "Gold"
        elif coin_value >= 3:
            self.discard_pile.append(2)
            self.buy_log.append(2)
            return "Silver"
        else:
            self.buy_log.append("Nothing")
            return "Nothing"

    def get_victory_points(self):
        result_deck = self.deck + self.discard_pile
        provinces = [6 for x in result_deck if x == "P"]
        duchies = [3 for x in result_deck if x == "D"]
        estates = [1 for x in result_deck if x == "E"]
        return sum(provinces) + sum(estates) + sum(duchies)

    def get_provinces(self):
        return len([6 for x in self.deck + self.discard_pile if x == "P"])

    # For solo simulation.
    def check_for_win(self):
        domain = self.deck + self.discard_pile
        domain = [x for x in domain if x == "P"]
        self.won = len(domain) > 6

    def play_until_win(self):
        turns = 0
        while not self.won:
            turns += 1
            # print("Turn %s" % turns)
            self.play_turn()
            self.check_for_win()
        # print("Won on turn %s with domain %s" % (turns, self.deck + self.discard_pile))
        # print("Buy order was %s." % self.buy_log)
        return turns

What this version is missing is :

  1. Buying other cards than currency cards or victory points;
  2. Using action cards.

Let’s address the second problem. I’ll add Steward and Smithy. Steward gives a choice between providing two coin value, drawing two cards, or trashing exactly two cards from your hand. Smithy lets the player draw three cards. I need to add one buy and one action per turn. I’ll also add a data structure for the cards. Each card will have a name, a cost, a coin value and possibly some effect names.

Here is the class definition for a card :

1
2
3
4
5
6
7
8
class DominionCard(object):
    def __init__(self, name, cost, value=0, victory_points=0, effects=list(), cards_used=-1):
        self.name = name
        self.cost = cost
        self.value = value
        self.victory_points = victory_points
        self.effects = effects  # Should always be a list which will be a choice.
        self.cards_used = cards_used  # -1 means infinity

The idea behind this construction is that we only need one copy (object) of each card. To use this scheme, we have to define a game state :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class DominionGameState(object):
    def __init__(self):
        self.PLAY_SET = {"Copper": DominionCard("Copper", 0, 1),
                         "Silver": DominionCard("Silver", 3, 2),
                         "Gold": DominionCard("Gold", 6, 3),
                         "Estate": DominionCard("Estate", 2, victory_points=1, cards_available=24),
                         "Duchy": DominionCard("Duchy", 5, victory_points=3, cards_available=12),
                         "Province": DominionCard("Province", 8, victory_points=6, cards_available=12),
                         "Smithy": DominionCard("Smithy", 4, effects=["DRAW 3 CARDS"], cards_available=10),
                         "Steward": DominionCard("Steward", 3, effects=["DRAW 2 CARDS",
                                                             "ADD 2 COIN VALUE",
                                                             "TRASH 2 CARDS"], cards_available=10)}
    def get_card(self, card_name):
        return self.PLAY_SET[card_name]

    def purchase_card(self, card_name):
        card = self.PLAY_SET[card_name]
        if card.cards_available == 0:
            return None
        elif card.cards_available > 0:
            card.cards_available -= 1 # This cards is infinitely available
        return card.name

    def card_has_effect(self, card_name):
        return not not self.get_card(card_name).effects # Fast cast to boolean

    def card_has_value(self, card_name):
        return not not self.get_card(card_name).value # Fast cast to boolean

We get the object by using the get_card function. Our implementation is another form of the Singleton design pattern. We use this design pattern because we want to store the available cards for purchase count. Furthermore, we can use the available cards count as a game end condition. And using only one object per card type makes handling the cards in play easier as we can reduce the hand, deck, trash and discard pile representation to a list of strings where we can draw by popping and discard by appending the correct collection. After the deck list is empty, we switch it with a shuffled discard pile. The discard pile is then empty. Trashing cards reduces then to removing the cards from the hand and appending them to the trash pile, effectively removing them from play. Here is the updated Player class definition:

1
2
3
4
5
6
7
8
9
10
11
12
class DominionPlayer(object):
    def __init__(self, game_state, strategy=None):
        self.game = game_state
        self.strategy = strategy
        self.deck = [self.game.purchase_card("Copper") for x in range(7)]  # Add Coppers to the deck.
        self.deck += [self.game.purchase_card("Estate") for x in range(3)] # Add Estates to the deck.
        random.shuffle(self.deck)  # Shuffle deck
        self.discard_pile = []  # Empty Discard Pile
        self.trash_pile = []
        # print(self.deck)
        self.won = False
        self.buy_log = []

For the player to decide which action card to play, he has to know how many copies of each card he has in his domain. In regular play with friends, I would consider this cheating, but we try to simulate a perfect playstyle. The function ge_card_count returns the number of copies of the provided card name in the domain of the player. The method get_total_money_cards counts the total currency card in the domain.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def get_card_count(self, cardname, turnstate=None):
    if turnstate:
        cards = self.deck + self.discard_pile + turnstate.hand
    else:
        cards = self.deck + self.discard_pile
    all_cards_with_name = [x for x in cards if x == cardname]
    return len(all_cards_with_name)

def get_total_money_cards(self, turnstate=None):
    if turnstate:
        cards = self.deck + self.discard_pile + turnstate.hand
    else:
        cards = self.deck + self.discard_pile
    all_cards_with_name = [x for x in cards if self.game.card_has_value(x)]
    return len(all_cards_with_name)

The card effects are still missing from our implementation. In the current build, effects are represented by a short string. To breathe life in these strings we define in Card class a function which provides the actions to the effects.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def play_effect(self, player, turnstate, effect):
    if effect == "DRAW 3 CARDS":
        cards = [player.draw_card() for x in range(3)]
        turnstate.hand += [x for x in cards if x]  # Removes the None cards
    elif effect == "DRAW 2 CARDS":
        cards = [player.draw_card() for x in range(2)]
        turnstate.hand += [x for x in cards if x]  # Removes the None cards
    elif effect == "ADD 2 COIN VALUE":
        turnstate.coin_value += 2
    elif effect == "TRASH 2 CARDS":
        estates_count = len([x for x in turnstate.hand if x == "Estate"])
        copper_count = len([x for x in turnstate.hand if x == "Copper"])
        if player.get_total_money_cards(turnstate) - min(copper_count, 2) < 5:
            # Make sure we do not go below 5 currency cards.
            copper_count = max(0, min(copper_count, player.get_total_money_cards(turnstate) - 5))

        if estates_count + copper_count >= 2:
            # Determine combination of coppers and estates to remove
            estates_to_remove = min(estates_count, 2) # 0, 1, or 2
            coppers_to_remove = min(2 - estates_to_remove, copper_count, 2) # 0, 1, or 2
            # Remove the stuff
            if estates_to_remove:
                for x in range(estates_to_remove):
                    turnstate.hand.remove("Estate")
                    turnstate.trash_pile.append("Estate")
            if coppers_to_remove:
                for x in range(coppers_to_remove):
                    turnstate.hand.remove("Copper")
                    turnstate.trash_pile.append("Copper")

The high complexity of the codes lies in the “TRASH 2 CARDS” section. Firstly we want the player to trash exactly two cards from his hand. Secondly, we don’t want him to trash the ‘wrong’ cards, and thirdly we do not want him to trash too many possibly useful Copper cards.

With the functions play_effect, get_card_count and get_total_money_cards we can decide which action cards we want to use during the action phase. If we hold only one action card in hand the choice is trivial. If hold two or more action cards, we decide to use the most expensive one using the assumption that the game has been balanced by the game designer. Of course, this rule only holds in our simulated play. During regular gameplay, we should chain cards which combo best in the correct order.

1
2
3
4
5
6
7
8
9
10
11
12
13
def use_actions_cards(self, turnstate):
    action_cards = [x for x in turnstate.hand if self.game.card_has_effect(x)]
    if len(action_cards) > 1:
        # If we have more than 1 action card we need some decision to which card we play.
        # We decide which card to play by the action card price.
        action_cards_prices = [self.game.get_card(x).cost for x in action_cards]
        card_to_play = self.game.get_card(action_cards[action_cards.index(max(action_cards_prices))])
    elif len(action_cards) == 1:
        card_to_play = self.game.get_card(action_cards[0])
    else:
        card_to_play = None
    if card_to_play:
        card_to_play.play_effects(self, turnstate)

The next decision lies in using the right effect when playing a Steward. This is a primary source of complexity but can be broken down. We trash cards when viable, then use coin value when in Province range (on six or seven hand coin value) and lastly draw cards. However, if there aren’t enough cards to draw (seldom happening), we use the currency value to buy Gold or Silver hopefully.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def play_effects(self, player, turnstate):
    if len(self.effects) == 1: # We got only one effect, choice is trivial
        effect_name = self.effects[0]
        self.play_effect(player, turnstate, effect_name)
    else:
        # We got a Steward so we have to decide what to play.
        # First we check if trashing would make sense.
        estates_count = len([x for x in turnstate.hand if x == "Estate"])
        copper_count = len([x for x in turnstate.hand if x == "Copper"])
        if player.get_total_money_cards(turnstate) - min(copper_count, 2) < 5:
            # Make sure we do not go below 5 currency cards.
            copper_count = max(0, min(copper_count, player.get_total_money_cards(turnstate) - 5))

        # Check if trashing would make sense
        if estates_count + copper_count >= 2 and "TRASH 2 CARDS" in self.effects:
            self.play_effect(player, turnstate, "TRASH 2 CARDS")
        # If we are in Province buy range then take the 2 coin value
        elif 6 <= player.get_hand_coin_value(turnstate.hand) <= 7 and "ADD 2 COIN VALUE" in self.effects:
            self.play_effect(player, turnstate, "ADD 2 COIN VALUE")
        # We are not in coin range, then draw two cards to possibly get into range, but only if we can draw 2 cards.
        elif len(turnstate.deck + turnstate.discard_pile) >= 2 and "DRAW 2 CARDS" in self.effects:
            self.play_effect(player, turnstate, "DRAW 2 CARDS")
        # We cannot draw 2 cards, then add 2 coin value so we can maybe buy a Gold or Silver
        elif "ADD 2 COIN VALUE" in self.effects:
            self.play_effect(player, turnstate, "ADD 2 COIN VALUE")

Now we can get onto the purchase decision problem. As the cards do not provide extra actions per turn, we do not want to acquire too many action cards. If we play the Smithy, we could fit one or two additional Smithies in the deck based on the card count. Ideally, we only draw coin cards and no action card. The same applies to the Steward as it has multiple purposes. We divide the buying problem into three strategies each playing only one type of the two action cards. If we follow no plan, we default to the standard Money deck.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def purchase_new_cards(self, turnstate):
    coin_value = turnstate.coin_value + self.get_hand_coin_value(turnstate.hand)  # Get only cards with coin value.

    if self.strategy == "Smithy":
        if coin_value >= 8:
            self.discard_pile.append(self.game.purchase_card("Province"))
            self.buy_log.append("Province")
            return "Province"
        elif coin_value >= 6:
            self.discard_pile.append(self.game.purchase_card("Gold"))
            self.buy_log.append("Gold")
            return "Gold"
        elif coin_value >= 4 and self.get_card_count("Smithy")/self.get_domain_card_count(turnstate) < 1/20:
            self.discard_pile.append(self.game.purchase_card("Smithy"))
            self.buy_log.append("Smithy")
            return "Smithy"
        elif coin_value >= 3:
            self.discard_pile.append(self.game.purchase_card("Silver"))
            self.buy_log.append("Silver")
            return "Silver"
        else:
            self.buy_log.append("Nothing")
            return "Nothing"

    elif self.strategy == "Steward":
        if coin_value >= 8:
            self.discard_pile.append(self.game.purchase_card("Province"))
            self.buy_log.append("Province")
            return "Province"
        elif coin_value >= 6:
            self.discard_pile.append(self.game.purchase_card("Gold"))
            self.buy_log.append("Gold")
            return "Gold"
        elif coin_value >= 3 and self.get_card_count("Steward")/self.get_domain_card_count(turnstate) < 1/20:
            self.discard_pile.append(self.game.purchase_card("Steward"))
            self.buy_log.append("Steward")
            return "Steward"
        elif coin_value >= 3:
            self.discard_pile.append(self.game.purchase_card("Silver"))
            self.buy_log.append("Silver")
            return "Silver"
        else:
            self.buy_log.append("Nothing")
            return "Nothing"

    else: # No strategy defaulting to the no action card Money deck.
        if coin_value >= 8:
            self.discard_pile.append(self.game.purchase_card("Province"))
            self.buy_log.append("Province")
            return "Province"
        elif coin_value >= 6:
            self.discard_pile.append(self.game.purchase_card("Gold"))
            self.buy_log.append("Gold")
            return "Gold"
        elif coin_value >= 3:
            self.discard_pile.append(self.game.purchase_card("Silver"))
            self.buy_log.append("Silver")
            return "Silver"
        else:
            self.buy_log.append("Nothing")
            return "Nothing"

The last thing we need to recode is the game logic to pit these players against each other. The redefined Dominion game class looks like this :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class DominionGame(object):
    def __init__(self):
        self.players = [DominionPlayer(self.card_state, None), DominionPlayer(self.card_state, "Steward"), DominionPlayer(self.card_state, "Smithy")]
        self.player_count = len(self.players)
        self.player_won = None
        self.provinces = 8 if self.player_count <= 2 else 12
        self.provinces_at_start = self.provinces
        self.card_state = DominionGameState()
        self.players = [DominionPlayer(self.card_state, None), DominionPlayer(self.card_state, "Steward"), DominionPlayer(self.card_state, "Smithy")]
        self.player_count = len(self.players)
        self.current_player = None
        self.pli = 0  # One turn = pli / player count. Each player gets one pli per turn.


    def check_end_game_condition(self):
        return self.card_state.get_card("Province").cards_available > 0

    def get_winner(self):
        victory_points = [player.get_victory_points() for player in self.players]
        # print(victory_points)
        self.won = victory_points.index(max(victory_points))
        vp_one_less = [x for x in victory_points] # shallow copy
        vp_one_less.remove(max(victory_points))
        if max(vp_one_less) == max(victory_points):
            winner = -1
        else:
            winner = self.won
        return (winner, self.pli // self.player_count)

    def current_player_plays(self):
        if self.player_count != 1:
            current = self.pli % self.player_count
            self.current_player = self.players[current]
        else:
            self.current_player = self.players[0]
        self.current_player.play_turn()
        self.pli += 1

    def play_until_over(self):
        while self.check_end_game_condition():
            self.current_player_plays()

        self.won = self.get_winner()
        # print("Player %s won with %s Provinces" % (self.won[0] + 1, self.players[self.won[0]].get_provinces()))
        return self.won

We determine the winner by checking if the one with the most victory points has more points than the one with the second most victory points. If not, we have a tie, and both should win, but we model only one winner. In this simple setup, the game ends when a player buys the last Province.

The simulation part becomes easy following using our construction. The only interesting section is the usage of multiple cores to speed up the calculations. Using a pool of eight workers, we distribute the workload on multiple cores and level the 20% CPU load of a single Python thread.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def get_game(x=0):
    return DominionGame().play_until_over()

if __name__ == '__main__':
    # g = Dominion()
    # g.play_until_win()
    pool = Pool(8)

    results = pool.map(get_game, range(1000000)) # Calculate on 8 cores.
    game_count = len(results)
    player_one = 0
    player_two = 0
    player_three = 0
    tie = 0
    for result in results:
        # print(result)
        if result[0] == 0:
            player_one += 1
        elif result[0] == 1:
            player_two += 1
        elif result[0] == 2:
            player_three += 1
        elif result[0] == -1:
            tie += 1
        else:
            print("Error")

    print("Average turns to win: %s" % (sum([result[1] for result in results]) / game_count,))
    print("Player one won %s out of %s games, quote %s" % (player_one, game_count, player_one / game_count))
    print("Player two won %s out of %s games, quote %s" % (player_two, game_count, player_two / game_count))
    print("Player three won %s out of %s games, quote %s" % (player_three, game_count, player_three / game_count))
    print("No player won (tie) %s out of %s games, quote %s" % (tie, game_count, tie / game_count))

Using the settings coded into the classes and methods, we get the followings stats with one million runs :

1
2
3
4
5
Average turns to win: 17.484122
Player one won 412001 out of 1000000 games, quote 0.412001
Player two won 156175 out of 1000000 games, quote 0.156175
Player three won 285652 out of 1000000 games, quote 0.285652
No player won (tie) 146172 out of 1000000 games, quote 0.146172

I find it odd that the run-of-the-mill no action cards Money deck wins by a large margin. This shows that my decision making in buying the right cards is either wrong or not fine-tuned enough. I am thinking of exploring this problem in a future post by using evolutionary algorithms, Monte-Carlo simulations, or a neural network. The game has a finite decision space, so maybe this is a possibility.

About me

Leave a Reply

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