Steve’s Blog

So during my trip to Las Vegas for Black Hat 2008, I played my first game of blackjack at a casino. I had turned on the TV in my room earlier that day and happened to see a program that was explaining basic strategy in blackjack. The basic strategy is this: since ten is the most common card value that will come up, assume that every card you don’t see has a value of ten.

This is pretty simple and I was getting the hang of playing – even getting help from the dealer when I made an incorrect move. However, one situation that kept coming up was when I was delt sixteen and the dealer was showing a ten. All week I was wondering what the correct move is for this scenario, so I decided to develop a program to tell me. I didn’t get around to writing it until the plane ride home, and even then I had to rewrite it twice before it started producing the correct output, but I’m pretty sure it’s correct as it is almost identical to the optimal playing strategy found on Wikipedia and other websites.

The method behind it is actually very simple – there are six main functions: player-hit, player-stand, player-turn, dealer-hit, dealer-stand, dealer-turn.

The player-hit function returns the probability of the player winning if the player hits on the current hand. It does this by calling player-turn for each possible card that could be delt to the player and averaging the results.

The player-turn function returns the probability of the player winning in his current situation. First it evaluates whether the player is over 21 – if so, it returns zero indicating that the player loses. Otherwise, it finds the probabilities of winning if the player should hit and if the player should stand, and returns whichever is higher.

The player-stand function returns the probability of the player winning if the player accepts no more cards for this game. All it really does is call dealer-turn.

The dealer-hit function works exactly like the player-hit function.

The dealer-turn function works similarly to the player-turn function, except that the dealer has strict rules as to whether they can hit or stand – if the dealer is 16 or under, or has 17 with an ace, the dealer must hit. Otherwise, the dealer stands.

The dealer-stand function checks to make sure the dealer isn’t over 21, then it tests to see who has a higher hand value. The function returns 1.0 if the player has a higher hand, 0.5 for a draw, and 0.0 if the dealer has a higher hand.

The value of each hand is stored in two numbers: one number is the sum of all the cards in the hand (with aces holding a value of 11), and the other is the number of aces in the hand. This is done so that some aces can be counted as having a value of one if the hand goes over 21.

And that’s basically it. You can use the probability-table function to produce a table of every starting blackjack scenario which will tell you the optimal move – hit or stand. Note that the table function takes a long time to run. Also, the program assumes an infinite deck, which obviously won’t be the case for any real situation.

Blackjack Optimal Strategy Calculator

6 comments

Everyday I wake up for work at 6:00am and get home at around 8:00pm. Since this only leaves me with two hours of spare time I try to get something constructive done during both 70 minute train rides. As much as I try, however, a little Minesweeper always manages to get played. While playing the other day, I was examining a small subset of the grid when I noticed that when I calculated all the possible mine positions for that isolated subset, it became apparent that there was a spot that couldn’t have a mine (normally when I play, I only examine a single cell to determine where mines may or may not be located). It was during this game that I decided to write a Minesweeper solver.
And it works pretty simply. When you examine a particular cell containing a number in a game of Minesweeper, it tells you how many adjacent spaces contain mines. For example, if you were to come across this configuration:

  A B C
1|? 0 0
2|0 1 ?
3|0 ? 0

You would know that there is one bomb which lies in either location A1, B3, or C2. Later it will become useful to also note which spaces do not contain mines. This will break each possibility into two groups: one group contains the spaces which have mines, the other contains spaces which do not. So our example above would be stored as:

mine-group: (A1), not-mine-group: (B3 C2)
mine-group: (B3), not-mine-group: (A1 C2)
mine-group: (C2), not-mine-group: (A1 B3)

As it turned out, writing code to divide these three unknown spaces into two groups was the hardest part. The function which does it is called ‘GenCombo’, and the function works by being passed in a list of elements to be divided – (a b c) for example – and a list of the group sizes, which in the above case would be size one for the ‘mine’ group, and size two for the ‘not mine’ group. The function then recursively pops an element off the first list and appends it to a particular group.

Now that the program can determine the possible configurations of a particular cell, there must be a way to combine them in order to reduce the total number of mine configurations. The particular configuration that made me realize how to do this looked like this:

  A B C D
1|? ? ? 0
2|0 1 1 0
3|0 0 0 0

The possible configurations for the number at position B2 are as follows:

mine-group: (A1), not-mine-group: (B1 C1)
mine-group: (B1), not-mine-group: (A1 C1)
mine-group: (C1), not-mine-group: (A1 B1)

Lets call these combinations C(B2).

The possible configurations for the number at C1 are:

mine-group: (B1), not-mine-group: (C1)
mine-group: (C1), not-mine-group: (B1)

This is C(C1).

To combine these, we take each possible pairing for each possibility and check for contradictions. To demonstrate, lets combine the first two possible configurations. To do this, we simply combine both ‘mine’ groups together and combine both ‘not mine’ groups together.

  (mine-group: (A1), not-mine-group: (B1 C1))
+ (mine-group: (B1), not-mine-group: (C1))
= (mine-group: (A1 B1), not-mine-group: (B1 C1 C1))

As we can see, there is a contradiction in this example in that there is an element that appears both in the ‘mine’ group AND in the ‘not mine’ group. What about two other pairs?

  (mine-group: (B1), not-mine-group: (A1 C1))
+ (mine-group: (B1), not-mine-group: (C1))
= (mine-group: (B1 B1), not-mine-group: (A1 C1 C1))

Aha, there are no contradictions, making this a viable combination. In total, there is one other viable combination for this example:

mine-group: (C1 C1), not-mine-group: (A1 B1)

If one were to plug this input into the code, the output returned would be in this form:

(
	(		; possible configuration 1
		(B1)	; mine group
		(A1 C1)	; not mine group
	)
	(		; possible configuration 2
		(C1)	; mine group
		(A1 B1)	; not mine group
	)
)

As you can see, it’s an ugly parenthetical mess. However its actually very simple: The function returns a list of possible configurations. Within each of these configurations, there are two groups. The first is the ‘mine’ group, and the second is the ‘not mine’ group. Within each of the groups, there is a number of ordered pairs which points to a place on the game board.

And that’s basically it. The game board is stored as a list, so the above example would be stored as: ‘(? ? ? 0 0 1 1 0 0 0 0 0). A function goes through each element in the list and generates the possible configurations for each individual cell, which would look like this:

'(nil nil nil nil
nil ( ((A1) (B1 C1)) ((B1) (A1 C1)) ((C1) (A1 B1)) ) ( ((B1) (C1)) ((C1) (B1)) ) nil
nil nil nil nil)

Phew. Next, a function takes this result, removes the nils, and reduces the list using
the Combine2Possibilities function, which would produce the output listed above.

Despite the output of this function being very ugly, it’s pretty versatile. Using some additional printing code, you can display the output in a number of different ways. In the example code, the original game state is printed first. Following the calculations, a list of possible mine location sets is printed out. But this output is hardly useful, so after that is a list of definite mine positions – positions that appear in every possible mine location set, as well as a list of definite not-mine positions. At the bottom is the most readable of all: the original game state with all definite mines and not-mines added.

Minesweeper Solver
(Note that in the code locations are represented as an ordered pair, not A1, B1, etc,.)

At the bottom is an example of it’s output using the example data provided in the code. ‘n’ means ‘not a mine’ – it’s possible to calculate this value for certain positions (those with no surrounding ‘?’s) but I’ll leave that as an exercise for the reader :)

Board before solution:
        1 ? ? ? ?
        1 ? ? 3 ?
    1 1 2 ? ? ? ?
    1 ? ? ? ? 1 ?
    1 2 ? 3 ? ? ?
      1 ? ? ? ? ?
    1 2 2 1 1 1 1
    1 ? 1
    1 ? 1
Possible mine location sets:
((5 0) (8 0) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 0) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (8 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (8 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))

Definite mine locations:
((3 7) (7 5) (4 5) (5 3) (3 3) (5 0))

Definite not mine locations:
((3 8) (8 5) (6 5) (5 5) (4 4) (4 3) (6 2) (7 2) (8 2) (8 3) (7 4)
 (8 4) (5 1) (5 2))

Board after solution:
        1 X ? ? ?
        1 n ? 3 ?
    1 1 2 n n n n
    1 X n X ? 1 n
    1 2 n 3 ? n n
      1 X n n X n
    1 2 2 1 1 1 1
    1 X 1
    1 n 1

3 comments