A simple model for the card game Dominion

Question

This problem is inspired by the card game Dominion.

We play a card game. At the beginning, we get one card "Copper".

At each round, we draw a card uniformly at random form cards that we already have. If we draw a copper, we can obtain a new card, either another copper card, or an estate card. If we draw an estate card, then we cannot do anything.

The aim of the game is to maximize the number of estate card after $n$ rounds. What would be the optimal strategy in this game? How do we balance the number of copper cards and estate cards?

Answer 1

General comments

When you draw a copper and choose to obtain a copper or an estate, I will call that "buying" a copper/estate.

If you draw a copper in the last round, there is no point in buying a copper since it can't be used, so you should always buy an estate in the last round if you can.

I don't have a formal proof, but I strongly suspect that the best strategy to maximize the expected number of estates (at least for large $n$) never involves buying a copper after an estate. If you were to buy a copper after an estate, then swapping those two purchases in the strategy would give you the same estate at a higher probability. Because of this conjecture, I will investigate only strategies with this property, to obtain lower bounds on the expected numbers of estates.

Calculations

For a given $n$ rounds the strategies under consideration start by purchasing $k$ coppers for some $k$, and then buying estates whenever possible.

Note that if $k=n$, $0$ estates are purchased. From now on, we will consider $n\ge1$ and $0\le k<n$.

Note that if we have $e$ estates in our deck and have already purchased the $k$ extra coppers, the chance of drawing a copper is $\dfrac{k+1}{k+1+e}$ since we had a copper to begin with. This leads naturally to a Markov Chain, since we will buy changing the number of estates from $e$ to $e+1$ with that probability, and leaving it at $e$ with probability $1-\dfrac{k+1}{k+1+e}=\dfrac{e}{k+1+e}$.

If the states are $0$ estates up to $n-k$ estates, we get a transition matrix of a special bidiagonal form: $$P_{n,k}=\begin{bmatrix}\frac{0}{k+1} & \frac{k+1}{k+1} & 0 & 0 & \cdots\\ 0 & \frac{1}{k+2} & \frac{k+1}{k+2} & 0 & \ddots\\ 0 & 0 & \frac{2}{k+3} & \frac{k+1}{k+3} & \ddots\\ \vdots & \ddots & \ddots & \ddots & \ddots \end{bmatrix}$$ The size of $P_{n,k}$ is $(n+1-k)\times(n+1-k)$ since we can obtain anywhere from $0$ to $n-k$ estates. In order to make it a proper transition matrix (a "right stochastic matrix"), we should make the final row something like $\begin{bmatrix}0&0&0&\cdots&0&1\end{bmatrix}$, but this won't actually matter for our purposes since we'll never be in a position to buy after having obtained $n-k$ estates.

After buying $k$ coppers, we have $0$ estates, and then want to find the chances of having each number of estates $n-k$ more rounds in the future. By the way matrix multiplication works, the list of probabilities is given by the matrix product $\begin{bmatrix}1&0&0&\cdots\end{bmatrix}\cdot (P_{n,k})^{n-k}$. So, to find the expected number of estates, we multiply these probabilities by the numbers of estates and then add. But that is just a dot product, which can be written as the matrix product $$\boxed{E(\text{# of estates})=\begin{bmatrix}1&0&0&\cdots\end{bmatrix}\cdot (P_{n,k})^{n-k}\cdot\begin{bmatrix}0\\1\\2\\\vdots\end{bmatrix}}$$

This formula makes it very accessible for a computer to calculate. For example, if $n=300$ and $k=87$, you expect to win approximately $124.903$ estates. The exact number is a fraction that in lowest terms has a numerator with $16048$ digits.

To get a sense for good strategy, here is a chart of $n$ and the choice of $k$ that maximizes the expected number of estates: $$\begin{matrix}n & \text{best }k\\ 0\text{-}4 & 0\\ 5\text{-}7 & 1\\ 8\text{-}11 & 2\\ 12\text{-}14 & 3\\ 15\text{-}18 & 4\\ 19\text{-}21 & 5\\ 22\text{-}24 & 6\\ 25\text{-}28 & 7\\ 29\text{-}31 & 8\\ 32\text{-}35 & 9\\ 36 & 10\\ 100 & 28\\ 200 & 58\\ 300 & 87\\ 350 & 102 \end{matrix}$$

From these numbers, it appears that the ratio of the ideal $k/n$ is gradually rising. $k=1$ would be too many for $n=4$ (so $k/n<1/4$), but by the time $n$ reaches $350$, the ideal $k/n$ is almost $3/10$. I wonder if the limiting ratio is something nice like $1/3$ or $1/e$.

Answer 2

I assume we want a strategy that maximizes expected number of estates at the end.

Let $c$ denote coppers, $e$ estates, and have $n$ rounds left.

Let's try to create a lookup table $T$ mapping from $(c,e,n)$ to $(E, C)$ where $E$ means buy estate and $C$ means buy copper. Whenever you draw a copper, the lookup table should tell you the expectation maximizing decision. Let $V(c,e,n)$ be the expected number of estates you get at the end by following the lookup table starting from state $(c,e,n)$ when you have just drawn a copper.

$\forall c, e: T(c, e, 0) = E, V(c, e, 0) = e+1$ because there are no rounds left.

Suppose $T(c, e, n) = E$. Then $V(c,e,n)$ would be $(e+1)( \frac{e+1}{c+e+1})^{n} + \sum_{i=1}^n (\frac{e+1}{c+e+1})^{i-1} \frac{c}{c+e+1} V(c, e+1, n-i)$.

Suppose $T(c, e, n) = C$. Then $V(c,e,n)$ would be $e (\frac{e}{c+e})^{n}+\sum_{i=1}^n(\frac{e}{c+e+1})^{i-1} \frac{c+1}{c+e+1} V(c+1, e, n-i)$.

So to find $T(c,e,n)$ just take the larger of these two options.

Although it looks bad that the recursive cases are on larger arguments in $c$ and $e$, if you know beforehand the max number of rounds is $N$, it puts a bound on how many cards you could possibly have at any round $n$, so you can still fill out the table bottom up.