After completing CS 188 (Intro to Artificial Intelligence) at my school I felt inspired to try out some of the techniques I had learned. It occurred to me while taking the class that blackjack could be modeled as a Markov Decision Process (MDP), and thus I could learn the optimal policy (or strategy) by performing Policy Iteration on it. For more general conceptual info see ai.berkeley.edu.
All the code for this project can be found at github.com/lukefeilberg/blackjack.
For this project I’ve first denoted states as tuples (num_aces, sum), where num_aces denotes the number aces drawn so far, and sum denotes the running sum of the values of cards drawn so far minus the ace values since they can either be one or eleven (hence why num_aces is stored separately). These tuples are a bit clunky to work with so I then number them from 0 to 216 for later simplicity, shown in the next section!
I'll denote our set of possible states with the symbol $\mathcal{S}$. We thus have $\mathcal{S} = [0,216]$, and each integer maps to the more interpretable tuple (num_aces, sum) as shown in the table below:
0: (0,0), 1: (0,2), 2: (0,3), ..., 29: (0,30), 30: (0,31)
31: (1,0), 32: (1,2), 33: (1,3), ..., 60: (1,30), 61: (1,31)
62: (2,0), 63: (2,2), 64: (2,3), ..., 91: (2,30), 92: (2,31)
...
186: (6,0), 187: (6,2), 188: (6,3), ..., 215: (6,30), 216: (6,31)
Note: (n,1) is not included for any n since drawing a 1 would actually be drawing an ace and is thus captured by (n+1, 0) instead. Also note that ending at 6 aces was arbitrary but pulling 7 or more aces seemed sufficiently unlikely for me to care about how to play in that situation. (Note too that casinos often play with seven or eight decks, thus why we have the possibility of more than 4 aces in the first place). Lastly having the sum run to 31 was an arbitrary choice in order to give a much more legible transition function.
In blackjack you have two possible actions:
We'll denote the set of all possible actions as $\mathcal{A}$, thus we have $\mathcal{A}=\{\text{draw}, \text{stop}\}$.
First, I’ll make the assumption that when we draw cards we'll replace them back in the deck -- this way our strategy doesn’t have to depend on the specific cards drawn/left (plus casinos often play with around eight decks anyways).
Thus there is a $\frac{1}{13}$ chance when you draw you’ll pull an ace. Since there are 31 columns $T(s, \text{draw}, s+31) = \frac{1}{13}$ (recall that adding 31 takes you down exactly one row as should be clear by looking at the sample of states provided above). Similarly there is a $\frac{1}{13}$ chance of pulling a 2 and increasing your sum by 2, a $\frac{1}{13}$ chance of pulling a 3 and increasing your sum by 3, and so forth giving: $T(s, \text{draw}, s+k) = \frac{1}{13}, \;\, \forall k \in [2,9]$ . Lastly, since 10, jack, queen, and kings all have a value of 10, those four ranks yield: $T(s, \text{draw}, s+10) = \frac{4}{13}$. Any other transition is impossible and will return a value of zero. Since I’m going to need these values very often I’m going to compute them once in a matrix called draw_matrix during initialization.
You only receive a reward in blackjack for exiting the game with a sum less than or equal to 21. Thus if your action is stop you receive your sum plus the optimal value of your aces, or zero if this is greater than 21. For example:
Policy Iteration begins by first defining an arbitrary initial policy, any policy will work but the closer to the optimal policy the quicker the algorithm converges. I’ll define the initial policy as “draw” no matter what to make initialization easy and to hammer home the point that we’ll find the optimal policy despite a terrible initial policy! Now we’ll repeat the following two steps until convergence:
In the Policy Evaluation step we evaluate the expected value of our score for each state. This will be a system of $|\mathcal{S}|$ equations given by the (lightly modified) Bellman Equation: $$ V^{\pi}(s) = \sum_{s' \in \mathcal{S}} T(s, \pi(s), s') \cdot \left( R \left(s,\pi(s), s' \right) + \gamma V^{\pi}(s') \right) $$ Since there's no discount in blackjack (scores remain the same no matter the number of timesteps taken to obtain sum/score) we can set $\gamma = 1$ yielding:
$$ V^{\pi}(s) = \sum_{s'\in \mathcal{S}} T(s, \pi(s), s') \cdot \left( R \left(s,\pi(s), s' \right) + V^{\pi}(s') \right) $$ Now if the policy of a state is “draw” we obtain the following equation: $$ V^{\pi}(s) = \sum_{s'\in \mathcal{S}} T(s, \text{draw}, s') \cdot \left( R \left(s,\text{draw}, s' \right) + V^{\pi}(s') \right) $$ The reward for drawing is always zero, because we only get rewarded for stopping before 21! This gives us $R \left(s,\text{draw}, s' \right) = 0,\;\; \forall s, s' \in S$:
$$
\begin{align}
V^{\pi}(s) &= \sum_{s'\in \mathcal{S}} T(s, \text{draw}, s') \cdot \left( V^{\pi}(s') \right) \newline
%
V^{\pi}(s) &= \frac{1}{13}\cdot V^{\pi}(s+31)
+ \left[
\sum_{k=2}^{9} \frac{1}{13} \cdot V^{\pi}(s+k)
\right]
+ \frac{4}{13} \cdot V^{\pi} (s+10) \newline
%
\implies
%
0 &= -V^{\pi}(s) +
\frac{1}{13}\cdot V^{\pi}(s+31)
+ \left[
\sum_{k=2}^{9} \frac{1}{13} \cdot V^{\pi}(s+k)
\right]
+ \frac{4}{13} \cdot V^{\pi} (s+10)
\end{align}
$$
Otherwise, if the policy of a state is “stop”, there is no possible states to transition to (we'll denote this as an extra state just called $\text{game over}$) yielding simply:
$$
\begin{align}
%
V^{\pi}(s) &= R(s, \text{stop}, \text{game over}) \newline
%
\implies
-R(s, \text{stop}, \text{game over}) &= -V^{\pi}(s)
%
\end{align}
$$
Now we have our system of equations in matrix form and can use numpy’s built in system of equation solver to compute the value of each state under our given policy.
Now that we have the value of each state under our given policy, let’s go ahead and improve our policy! Using our computed values of each state from above we will create a new policy that selects the action that gives the maximum score, according to the equation:
$$\pi_{i+1}(s) = \text{argmax}_{a\in\mathcal{A}}
\sum_{s'\in\mathcal{S}} T \left( s, a, s' \right)
\cdot \left[ R\left( s, a, s' \right) + \gamma V^{\pi}(s') \right]
$$
Now notice that if our action is “stop” we simply return the reward of stopping at that state. Therefore “stop” does not depend on our computed values of states. This means we only have to compute this value once and can then store it! We’ll do that in an array called stop_value. The values of “draw” in each state can be computed by multiplying our transition matrix by our array of computed values, let’s save this as an array called draw_value. Now we can define our new policy to be “draw” everywhere except the indices where stop_value is greater than draw_value.
If our new policy is equivalent to our old policy then the algorithm has converged and we have found the optimal policy! Otherwise we return to the policy evaluation step and repeat all the above until our policy converges.
In our case we converge to the following policy (recall the formatting is (number of aces, running sum excluding aces):
My computed policy seems fairly conservative, for example stopping at a sum of 13 with no aces. To aid me in investigating I recreated my program in a far more simplified manner letting aces only take on the value of one, thus states can be represented solely by the running sum of the cards drawn. Under this simplified version the optimal policy says to “stop” at states 12 and above. However, let’s consider state 14. We only will bust if we draw an 8, 9, 10, or face card. Thus we have a 6/13 chance of busting which is less than half. Let’s thus define a second policy to “stop” at states 15 and above.
Now, when I play a hundred thousand games of blackjack under the computed optimal policy I get a score (or average sum) of about 16.02. When I play a hundred thousand games with my second strategy I get a score (average sum) of about 15.01. So our computed policy does have a higher expected score as we hoped. HOWEVER, when I play these two strategies against each other, the second policy performs better! In fact our computed policy wins 37,557 of 100,000 games and the second policy wins 54,209 (with the rest being ties). The lesson here is to be very careful how you define your reward function. I prioritized coming out with the highest score overall, rather than outscoring my component. Another interesting lesson is that a strategy with a higher expected score does not guarantee outperforming a lesser expected score strategy on average.