Card Games and Logic Programming - For the Win!

One of my favorite geek games is Dominion.

It is a fantasy themed card game in which players try to win by purchasing “Victory” cards. The cards a player purchases go into his or her deck. The Victory cards include Estate cards (worth 1 point and cost 2 copper each), Duchy cards (worth 3 points and cost 5 copper each), and Province cards (worth 6 points and cost 8 copper each). So obviously, Province cards are more desirable - if you can afford them.

There are strategies that allow a player to win by only buying Duchy cards. The most viable of these strategies includes the use of a Duke card, which is worth one point for every Duchy card you possess but costs the same as a Duchy card. So it can become more valuable than a Duchy.<div>The order in which the Duchy and Duke cards are acquired is important. A game of Dominion can end abruptly. Thus, a player cannot easily predict how many Duchy cards (s)he will possess at the end of a game. For example, purchasing Dukes in the first rounds would be a mistake because the Dukes are worth zero until the first Duchy is purchased.

I have thought about the ideal order for purchasing Duchies and Dukes for a long time. The first few rounds are obvious:

1. Purchase a Duchy - Total Score: 3 pts
2. Purchase a Duchy - Total Score: 6 pts
3. Purchase a Duchy - Total Score: 9 pts
4. Purchase a Duchy - Total Score: 12 pts
5. Purchase a Duke - Total Score: 16 pts

But after those rounds, it becomes difficult to decide whether to buy another Duke (because they are now worth more than a Duchy), or to buy a Duchy (which would boost the value of the Dukes even further).

To figure this out, I decided to write a program. And because the algorithm would be highly recursive I chose to write it in Prolog.

Scoring and Playing
I started by writing the rules for scoring a deck. The Deck variable is a list of cards possessed by a player. Each term in the list will be either a “duchy” or a “duke”.


After I was satisfied with the scoring predicates I began writing the predicates for building up all the possible decks a player could possess. The play predicate uses recursion to simulate the purchases made while playing a game of Dominion.


Once I was certain that the play predicate would backtrack through all the possible decks a player could have, I started to think about what would define a good deck - or even the best deck.

Finding the Best Deck
<div>I started by writing a predicate to find the deck with the highest score (I will call this value the “potential high score”). It didn’t take long before I realized that this could not be the only criterion. Many decks result in the potential high score, and not all are good decks. For example, one of the high scoring decks requires the purchase of nothing but Dukes at first - so the player’s score will be zero for many rounds.

Greedy
I was curious if a greedy algorithm that used a local maximum to decided the next card to purchase would result in he potential high score. So I wrote one in Ruby.


The greedy algorithm works for small deck sizes. But it begins to diverge from the potential high score for larger deck sizes.

Running the greedy algorithm for a game with 8 Dukes and 8 Duchies yields the following solution:

1. Purchase a Duchy - Total Score: 3 pts
2. Purchase a Duchy - Total Score: 6 pts
3. Purchase a Duchy - Total Score: 9 pts
4. Purchase a Duke - Total Score: 12 pts
5. Purchase a Duchy - Total Score: 16 pts
6. Purchase a Duke - Total Score: 20 pts
7. Purchase a Duchy - Total Score: 25 pts
8. Purchase a Duke - Total Score: 30 pts
9. Purchase a Duchy - Total Score: 36 pts
10. Purchase a Duke - Total Score: 42 pts
11. Purchase a Duchy - Total Score: 49 pts
12. Purchase a Duke - Total Score: 56 pts
13. Purchase a Duchy - Total Score: 64 pts

The game ends when either the Dukes or Duchies run out. In this case, the 13th purchase, a Duchy, is the last Duchy.

I decided at this point that a deck must ultimately reach the potential high score in order to be considered the best deck. But I also wanted to try and maximize the score after each card purchase - so if the game ends abruptly the player is not left with a very low score. To accomplish this I used a technique that is more like dynamic programming, but I’m told its not exactly that. Regardless, it is perfect for Prolog.

Reverse Greedy
The algorithm I chose to implement is like a reverse greedy algorithm. It makes a choice based on the deck with the highest score during any given round, but it starts with the final purchase. This differs from the Ruby algorithm, which started with the first purchase.
<div>
The algorithm starts by generating the set of all possible decks. But it treats them like a tree of card choices through the power of recursion. Thus we can picture the possible choices like this:</div><div>

</div><div>In the diagram above, notice that the far left branch is selecting all Duchies, and the far right branch is selecting all Dukes. As the algorithm executes, it transforms the nodes of the tree into scores:</div><div>
</div><div>The paths with all Duchies and all Dukes become more evident now. Finally, the algorithm prunes the tree down to the path with the highest scores:</div><div>
Because we have only illustrated a tree that has a depth of three, the best path is the “all Duchies” path.</div>
At the core of this algorithm is the max_deck predicate (note that I have left out some auxillary predicates that serve to kickstart the program as well as terminate the recursion).


The variable SetOfDecks starts as the set of all possible decks (its actually more of a stack because each successive round is added to the front of the list). The variable N records our position in SetOfDecks. And the variable Set is the resulting best deck.

The max_deck predicate has three stages:
<ol><li>Determine the maximum score at N of the decks in SetOfDecks and store it in Max</li><li>Select all the Decks that have a score of Max and store them in SetOfDecksWithMaxAtN</li><li>Recursively invoke max_deck with the next position and the reduced set of decks</li></ol>I’m fairly certain there is a way to combine stages 1 and 2 into a single stage. But my Prolog chops are not that sharp.</div><div>
</div><div>
</div><div>Now lets take a look at the individual predicates that make up the algorithm. The max_n predicate is fairly straight forward. It recursively looks for the highest score at position N in the set of decks. This is the meat of it:</div><div>

The decks_with_n_of predicate is only slightly more exciting. It recursively looks through the set of decks for those that have a score of Max at position N. Like I said, this can probably be combined with max_n.


Both max_n and decks_with_n_of use a predicate called nth_score. This is a helper predicate that uses the score predicate described above:


The tail predicate just selects all the elements after and including the Nth element.

This approach is more effective that the greedy algorithm because it exhausts all possible solutions in a search for the optimal solution. At each stage it reduces the solution set to only those that meet its criteria.

Results
Running this program for a game with 8 Dukes and 8 Duchies yields the following optimal solution:

1. Purchase a Duchy - Total Score: 3 pts
2. Purchase a Duchy - Total Score: 6 pts
3. Purchase a Duchy - Total Score: 9 pts
4. Purchase a Duchy - Total Score: 12 pts
5. Purchase a Duke - Total Score: 16 pts
6. Purchase a Duchy - Total Score: 20 pts
7. Purchase a Duke - Total Score: 25 pts
8. Purchase a Duchy - Total Score: 30 pts
9. Purchase a Duke - Total Score: 36 pts
10. Purchase a Duchy - Total Score: 42 pts
11. Purchase a Duke - Total Score: 49 pts
12. Purchase a Duke - Total Score: 56 pts
13. Purchase a Duke - Total Score: 63 pts
14. Purchase a Duke - Total Score: 70 pts
15. Purchase a Duchy - Total Score: 80 pts

The game ends when there are no more Duchies left. Notice that the score at each round for this deck is almost identical to the deck derived from the greedy algorithm. They only diverge on the 13th round.

Because the Prolog program does an exhaustive search, I was able to gather some interesting statistics about the 8 Duke/8 Duchy game. There were 3,432 decks that were able to reach the potential high score of 80. Of those, there were 16 that resulted in a suitable solution. That is to say, the above deck is not the only deck with those scores at each round. Thus, choosing which of those 16 decks to model a game after depends on outside factors - such as how the competitors are playing.

Conclusion
There are many factors that determine what strategy to use. For example, if a player knows that other players are competing for the Dukes, (s)he may choose to grab them up before they run out. Or if another player is trying to “race out the game” (i.e. end the game before an opposing player can get his or her strategy to pay off) one may choose to purchase cards in the way the greedy algorithm did - because its unlikely that the number of Victory cards in that person’s deck will exceed five or six.

This all makes Dominion a great game. There is no rote pattern to follow. Each player must adapt his or her strategy as the game is played.
</div>

A full version of the Prolog program is located here.

And a full version of the greedy algorithm is located here.</div>