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

Write a function to determine the probability the dealer will bust (given a particular hand).

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

As another example, consider if the hand is 14.Now there are 3/10 cards that can immediately result in a bust. However, now there is a 2/10 chance of having to redraw, both of which have thier own probabilities associated with them.

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

Notice that ALOT of computations are reused in the tree. So an incredibly faster approach to this problem would be to literally compute all the answers, and then just statically _return them when a function call asks for it. In the image below for example, a hand of _13 can reuse just take 1/10 of tree(14).

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