Simplified Blackjack

Consider a simplified game of blackjack / 21, with an infinite deck of cards labeled 1-10. That means there is always a 10% chance to draw any card value regardless of what's been drawn before. The dealer always plays deterministically, according to the following rules:

1. If the dealer's total is less than 17, the dealer draws another card.

2. If the dealer's total is at least 17, but not more than 21, the dealer stands.

3. If the dealer's total is over 21 the dealer has busted (lost).

Approach 1: Brute Force

The Idea: Like with many problems, often the best way to begin is to first go some examples just to make sure you understand the problem contextually. This is especially more important with mathematical problems such as these.

We know immediately that if the hand greater than 21, then the probability of busting is 100%. Similarly, if the hand is between 17 and 21, the dealer stands, so the probability of busting is 0%.

Now lets deal with the case when the hand is 16 or lower. This is where need to account for having to potentially draw another card. For example, if our hand is `15`, then `4/10` cards will favor the bust, and there is a `1/10` chance we will draw a `16`. In the case that we do, it will follow that we then have a `5/10` chance of then leading into a bust. Since both events have to happen and each is independent, the chances of it happening is `1/10*5/10`. In total we then have `4/10 + 5/100` in favor of a bust.

Notice how the entire tree sums to 1: `P(bust0) + P(not bust) + P(bust1) = 4/10 + 5/10 + 10/100 = 1`

Complexity: If your hand between 22 and N, then the complexity will be O(16-N!)

``````import queue
import math

def p_bust(hand):

if hand > 21:
return 1
elif 17 <= hand <= 21:
return 0

q = queue.Queue()
q.put((hand, 0))
geo_sum = 0

while not q.empty():
parent = q.get()
p_hand = parent[0]
p_lvl  = parent[1]

# how many card favor the current bust
tmp = (p_hand + 10) - 21
amount_bust = tmp if tmp > 0 else 0
geo_sum += math.pow(.1, p_lvl) * amount_bust/10

# how many cards do we have to draw?
amount_draw = 16 - p_hand
for i in range(1, amount_draw + 1):
q.put((p_hand + i, p_lvl + 1))

return geo_sum

for i in range(23, -1, -1):
print(i, p_bust(i))

# will output:
# 23 1
# 22 1
# 21 0
# 20 0
# 19 0
# 18 0
# 17 0
# 16 0.5
# 15 0.45
# 14 0.39499999999999996
# 13 0.3345
# 12 0.2679500000000001
# 11 0.19474500000000008
# 10 0.21421950000000015
# 9 0.23564145000000022
# 8 0.2592055949999989
# 7 0.28512615449999784
# 6 0.31363876994999573
# 5 0.345002646944992
# 4 0.3795029116394856
# 3 0.4174532028034251
# 2 0.4591985230837547
# 1 0.5051183753922686
# 0 0.555630212931779``````

Approach 2: Dynamic Programming

Complexity: O(1) time after preprocessing but technically since were only preprocessing numbers 1 - 16 (a constant amount), preprocessing is also finished in constant time. Constant space too.

``````import queue
import math

class Solution:

# static dp array
__p_bust_sol = {}
def p_bust(self, hand):

if hand > 21:
return 1
elif 17 <= hand <= 21:
return 0

if Solution.__p_bust_sol:
return Solution.__p_bust_sol[hand]

# just compute all the answers really fast
for hand in range(23, -1, -1):
q = queue.Queue()
q.put((hand, 0))
geo_sum = 0

while not q.empty():
parent = q.get()
p_hand = parent[0]
p_lvl = parent[1]

if p_hand in Solution.__p_bust_sol:
geo_sum += Solution.__p_bust_sol[p_hand] * .1
else:
# how many card favor the current bust
tmp = (p_hand + 10) - 21
amount_bust = tmp if tmp > 0 else 0
geo_sum += math.pow(.1, p_lvl) * amount_bust / 10

# how many cards do we have to draw?
amount_draw = 16 - p_hand
for i in range(1, amount_draw + 1):
q.put((p_hand + i, p_lvl + 1))

Solution.__p_bust_sol[hand] = geo_sum
return Solution.__p_bust_sol[hand]

obj = Solution()
for i in range(23, -1, -1):
print(i, obj.p_bust(i))

# will output:
# 23 1
# 22 1
# 21 0
# 20 0
# 19 0
# 18 0
# 17 0
# 16 0.5
# 15 0.45
# 14 0.39499999999999996
# 13 0.3345
# 12 0.2679500000000001
# 11 0.19474500000000008
# 10 0.21421950000000015
# 9 0.23564145000000022
# 8 0.2592055949999989
# 7 0.28512615449999784
# 6 0.31363876994999573
# 5 0.345002646944992
# 4 0.3795029116394856
# 3 0.4174532028034251
# 2 0.4591985230837547
# 1 0.5051183753922686
# 0 0.555630212931779``````

Last updated