A simple model for the card game Dominion

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$.

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.