Problem

This problem was asked by MIT.

Blackjack is a two player card game whose rules are as follows:

  • The player and then the dealer are each given two cards.
  • The player can then “hit”, or ask for arbitrarily many additional cards, so long as their total does not exceed 21.
  • The dealer must then hit if their total is 16 or lower, otherwise pass.
  • Finally, the two compare totals, and the one with the greatest sum not exceeding 21 is the winner.

For this problem, cards values are counted as follows: each card between 2 and 10 counts as their face value, face cards count as 10, and aces count as 1.

Given perfect knowledge of the sequence of cards in the deck, implement a blackjack solver that maximizes the player’s score (that is, wins minus losses).

Examples

Example 1

1
2
3
4
5
6
7

Input: deck = [10, 5, 2, 7, 8, 3, 1, 9, 6, 4]
Output: 1
Explanation: 
- Player gets [10, 5] = 15, Dealer gets [2, 7] = 9
- Player stands (15 is good), Dealer hits with 8 → 17
- Player wins (15 < 21, 17 < 21, but we need optimal strategy)
- With perfect play, player can achieve +1 overall score

Example 2

1
2
3
4
5
6
7

Input: deck = [1, 1, 10, 10, 5, 5, 2, 2]
Output: 0
Explanation:
- Player gets [1, 1] = 2, Dealer gets [10, 10] = 20
- Player must hit optimally, gets 5 → 7, then 5 → 12, then 2 → 14, then 2 → 16
- Dealer stands at 20
- Player loses this hand, optimal strategy yields 0 net score

Example 3

1
2
3
4
5
6

Input: deck = [10, 10, 1, 1]
Output: -1
Explanation:
- Player gets [10, 10] = 20, Dealer gets [1, 1] = 2
- Player stands at 20, Dealer must hit and gets busted or gets a good hand
- Even with perfect knowledge, this setup leads to net loss

Solution

Method 1 – Dynamic Programming with Game State

Intuition

With perfect knowledge of the card sequence, we can use dynamic programming to explore all possible game states and choose the optimal strategy. The key insight is that at each decision point, we know exactly what cards are coming next, so we can simulate both player and dealer actions to find the maximum expected score.

Approach
  1. State Representation: Define game state as (player_sum, dealer_sum, deck_position, whose_turn)
  2. Player Decision: At each turn, decide whether to hit or stand based on future card knowledge
  3. Dealer Simulation: Dealer follows fixed rules (hit if ≤16, stand if ≥17)
  4. Recursive Exploration: Use memoization to avoid recomputing same states
  5. Optimal Strategy: Choose action that maximizes final score difference

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
private:
    unordered_map<string, int> memo;
    vector<int> deck;
    
    string getKey(int playerSum, int dealerSum, int pos, int turn) {
        return to_string(playerSum) + "," + to_string(dealerSum) + "," + 
               to_string(pos) + "," + to_string(turn);
    }
    
    int solve(int playerSum, int dealerSum, int pos, int turn) {
        if (playerSum > 21) return -1; // Player busts
        if (dealerSum > 21) return 1;  // Dealer busts
        if (pos >= deck.size()) {
            // Game ends, compare sums
            if (playerSum > dealerSum) return 1;
            if (playerSum < dealerSum) return -1;
            return 0;
        }
        
        string key = getKey(playerSum, dealerSum, pos, turn);
        if (memo.count(key)) return memo[key];
        
        int result;
        if (turn == 0) { // Player's turn
            // Option 1: Stand (dealer plays)
            int standResult = solve(playerSum, dealerSum, pos, 1);
            
            // Option 2: Hit
            int hitResult = solve(playerSum + deck[pos], dealerSum, pos + 1, 0);
            
            result = max(standResult, hitResult);
        } else { // Dealer's turn
            if (dealerSum <= 16) {
                // Dealer must hit
                result = solve(playerSum, dealerSum + deck[pos], pos + 1, 1);
            } else {
                // Dealer stands, game ends
                if (playerSum > dealerSum) result = 1;
                else if (playerSum < dealerSum) result = -1;
                else result = 0;
            }
        }
        
        return memo[key] = result;
    }
    
public:
    int blackjackSolver(vector<int>& cards) {
        deck = cards;
        memo.clear();
        
        // Initial deal: player gets cards[0], cards[2], dealer gets cards[1], cards[3]
        int playerStart = cards[0] + cards[2];
        int dealerStart = cards[1] + cards[3];
        
        return solve(playerStart, dealerStart, 4, 0);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

func blackjackSolver(cards []int) int {
    memo := make(map[string]int)
    
    var solve func(playerSum, dealerSum, pos, turn int) int
    solve = func(playerSum, dealerSum, pos, turn int) int {
        if playerSum > 21 {
            return -1 // Player busts
        }
        if dealerSum > 21 {
            return 1 // Dealer busts
        }
        if pos >= len(cards) {
            // Game ends, compare sums
            if playerSum > dealerSum {
                return 1
            }
            if playerSum < dealerSum {
                return -1
            }
            return 0
        }
        
        key := fmt.Sprintf("%d,%d,%d,%d", playerSum, dealerSum, pos, turn)
        if val, exists := memo[key]; exists {
            return val
        }
        
        var result int
        if turn == 0 { // Player's turn
            // Option 1: Stand (dealer plays)
            standResult := solve(playerSum, dealerSum, pos, 1)
            
            // Option 2: Hit
            hitResult := solve(playerSum+cards[pos], dealerSum, pos+1, 0)
            
            result = max(standResult, hitResult)
        } else { // Dealer's turn
            if dealerSum <= 16 {
                // Dealer must hit
                result = solve(playerSum, dealerSum+cards[pos], pos+1, 1)
            } else {
                // Dealer stands, game ends
                if playerSum > dealerSum {
                    result = 1
                } else if playerSum < dealerSum {
                    result = -1
                } else {
                    result = 0
                }
            }
        }
        
        memo[key] = result
        return result
    }
    
    // Initial deal: player gets cards[0], cards[2], dealer gets cards[1], cards[3]
    playerStart := cards[0] + cards[2]
    dealerStart := cards[1] + cards[3]
    
    return solve(playerStart, dealerStart, 4, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Solution {
    private Map<String, Integer> memo;
    private int[] deck;
    
    private String getKey(int playerSum, int dealerSum, int pos, int turn) {
        return playerSum + "," + dealerSum + "," + pos + "," + turn;
    }
    
    private int solve(int playerSum, int dealerSum, int pos, int turn) {
        if (playerSum > 21) return -1; // Player busts
        if (dealerSum > 21) return 1;  // Dealer busts
        if (pos >= deck.length) {
            // Game ends, compare sums
            if (playerSum > dealerSum) return 1;
            if (playerSum < dealerSum) return -1;
            return 0;
        }
        
        String key = getKey(playerSum, dealerSum, pos, turn);
        if (memo.containsKey(key)) return memo.get(key);
        
        int result;
        if (turn == 0) { // Player's turn
            // Option 1: Stand (dealer plays)
            int standResult = solve(playerSum, dealerSum, pos, 1);
            
            // Option 2: Hit
            int hitResult = solve(playerSum + deck[pos], dealerSum, pos + 1, 0);
            
            result = Math.max(standResult, hitResult);
        } else { // Dealer's turn
            if (dealerSum <= 16) {
                // Dealer must hit
                result = solve(playerSum, dealerSum + deck[pos], pos + 1, 1);
            } else {
                // Dealer stands, game ends
                if (playerSum > dealerSum) result = 1;
                else if (playerSum < dealerSum) result = -1;
                else result = 0;
            }
        }
        
        memo.put(key, result);
        return result;
    }
    
    public int blackjackSolver(int[] cards) {
        deck = cards;
        memo = new HashMap<>();
        
        // Initial deal: player gets cards[0], cards[2], dealer gets cards[1], cards[3]
        int playerStart = cards[0] + cards[2];
        int dealerStart = cards[1] + cards[3];
        
        return solve(playerStart, dealerStart, 4, 0);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution:
    def blackjackSolver(self, cards: List[int]) -> int:
        memo: Dict[Tuple[int, int, int, int], int] = {}
        
        def solve(player_sum: int, dealer_sum: int, pos: int, turn: int) -> int:
            if player_sum > 21:
                return -1  # Player busts
            if dealer_sum > 21:
                return 1   # Dealer busts
            if pos >= len(cards):
                # Game ends, compare sums
                if player_sum > dealer_sum:
                    return 1
                elif player_sum < dealer_sum:
                    return -1
                else:
                    return 0
            
            state = (player_sum, dealer_sum, pos, turn)
            if state in memo:
                return memo[state]
            
            if turn == 0:  # Player's turn
                # Option 1: Stand (dealer plays)
                stand_result = solve(player_sum, dealer_sum, pos, 1)
                
                # Option 2: Hit
                hit_result = solve(player_sum + cards[pos], dealer_sum, pos + 1, 0)
                
                result = max(stand_result, hit_result)
            else:  # Dealer's turn
                if dealer_sum <= 16:
                    # Dealer must hit
                    result = solve(player_sum, dealer_sum + cards[pos], pos + 1, 1)
                else:
                    # Dealer stands, game ends
                    if player_sum > dealer_sum:
                        result = 1
                    elif player_sum < dealer_sum:
                        result = -1
                    else:
                        result = 0
            
            memo[state] = result
            return result
        
        # Initial deal: player gets cards[0], cards[2], dealer gets cards[1], cards[3]
        player_start = cards[0] + cards[2]
        dealer_start = cards[1] + cards[3]
        
        return solve(player_start, dealer_start, 4, 0)

Complexity

  • ⏰ Time complexity: O(21 × 21 × n × 2) = O(n), where n is the number of cards. Each state is defined by player sum (≤21), dealer sum (≤21), position in deck, and whose turn it is.
  • 🧺 Space complexity: O(21 × 21 × n × 2) = O(n), for the memoization table storing all possible game states.

Method 2 – Minimax with Alpha-Beta Pruning

Game Theory Approach

Since this is essentially a two-player game where the player wants to maximize score and we know the dealer’s strategy, we can model it as a minimax problem. The player tries to maximize the outcome while the dealer follows deterministic rules.

Strategy

  1. Game Tree Construction: Build a game tree where each node represents a game state
  2. Player Maximization: Player nodes choose actions that maximize the final score
  3. Dealer Deterministic: Dealer nodes follow fixed rules (no optimization needed)
  4. Alpha-Beta Pruning: Cut off branches that won’t affect the final result
  5. Perfect Information: Use knowledge of upcoming cards to make optimal decisions

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Solution {
private:
    vector<int> deck;
    unordered_map<string, int> cache;
    
    string encodeState(int pSum, int dSum, int pos, bool playerTurn) {
        return to_string(pSum) + "_" + to_string(dSum) + "_" + 
               to_string(pos) + "_" + (playerTurn ? "1" : "0");
    }
    
    int minimax(int pSum, int dSum, int pos, bool playerTurn, int alpha, int beta) {
        // Terminal conditions
        if (pSum > 21) return -1;  // Player bust
        if (dSum > 21) return 1;   // Dealer bust
        if (pos >= deck.size()) {
            if (pSum > dSum) return 1;
            if (pSum < dSum) return -1;
            return 0;
        }
        
        string state = encodeState(pSum, dSum, pos, playerTurn);
        if (cache.count(state)) return cache[state];
        
        int result;
        if (playerTurn) {
            result = INT_MIN;
            
            // Option 1: Hit
            int hitVal = minimax(pSum + deck[pos], dSum, pos + 1, true, alpha, beta);
            result = max(result, hitVal);
            alpha = max(alpha, result);
            if (beta <= alpha) return cache[state] = result;
            
            // Option 2: Stand (switch to dealer)
            int standVal = minimax(pSum, dSum, pos, false, alpha, beta);
            result = max(result, standVal);
            
        } else {
            // Dealer's turn - deterministic
            if (dSum <= 16) {
                result = minimax(pSum, dSum + deck[pos], pos + 1, false, alpha, beta);
            } else {
                // Dealer stands
                if (pSum > dSum) result = 1;
                else if (pSum < dSum) result = -1;
                else result = 0;
            }
        }
        
        return cache[state] = result;
    }
    
public:
    int blackjackSolverMinimax(vector<int>& cards) {
        deck = cards;
        cache.clear();
        
        int pStart = cards[0] + cards[2];
        int dStart = cards[1] + cards[3];
        
        return minimax(pStart, dStart, 4, true, INT_MIN, INT_MAX);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

func blackjackSolverMinimax(cards []int) int {
    cache := make(map[string]int)
    
    encodeState := func(pSum, dSum, pos int, playerTurn bool) string {
        turn := 0
        if playerTurn {
            turn = 1
        }
        return fmt.Sprintf("%d_%d_%d_%d", pSum, dSum, pos, turn)
    }
    
    var minimax func(pSum, dSum, pos int, playerTurn bool, alpha, beta int) int
    minimax = func(pSum, dSum, pos int, playerTurn bool, alpha, beta int) int {
        // Terminal conditions
        if pSum > 21 {
            return -1 // Player bust
        }
        if dSum > 21 {
            return 1 // Dealer bust
        }
        if pos >= len(cards) {
            if pSum > dSum {
                return 1
            }
            if pSum < dSum {
                return -1
            }
            return 0
        }
        
        state := encodeState(pSum, dSum, pos, playerTurn)
        if val, exists := cache[state]; exists {
            return val
        }
        
        var result int
        if playerTurn {
            result = math.MinInt32
            
            // Option 1: Hit
            hitVal := minimax(pSum+cards[pos], dSum, pos+1, true, alpha, beta)
            result = max(result, hitVal)
            alpha = max(alpha, result)
            if beta <= alpha {
                cache[state] = result
                return result
            }
            
            // Option 2: Stand (switch to dealer)
            standVal := minimax(pSum, dSum, pos, false, alpha, beta)
            result = max(result, standVal)
            
        } else {
            // Dealer's turn - deterministic
            if dSum <= 16 {
                result = minimax(pSum, dSum+cards[pos], pos+1, false, alpha, beta)
            } else {
                // Dealer stands
                if pSum > dSum {
                    result = 1
                } else if pSum < dSum {
                    result = -1
                } else {
                    result = 0
                }
            }
        }
        
        cache[state] = result
        return result
    }
    
    pStart := cards[0] + cards[2]
    dStart := cards[1] + cards[3]
    
    return minimax(pStart, dStart, 4, true, math.MinInt32, math.MaxInt32)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

class Solution {
    private int[] deck;
    private Map<String, Integer> cache;
    
    private String encodeState(int pSum, int dSum, int pos, boolean playerTurn) {
        return pSum + "_" + dSum + "_" + pos + "_" + (playerTurn ? "1" : "0");
    }
    
    private int minimax(int pSum, int dSum, int pos, boolean playerTurn, int alpha, int beta) {
        // Terminal conditions
        if (pSum > 21) return -1;  // Player bust
        if (dSum > 21) return 1;   // Dealer bust
        if (pos >= deck.length) {
            if (pSum > dSum) return 1;
            if (pSum < dSum) return -1;
            return 0;
        }
        
        String state = encodeState(pSum, dSum, pos, playerTurn);
        if (cache.containsKey(state)) return cache.get(state);
        
        int result;
        if (playerTurn) {
            result = Integer.MIN_VALUE;
            
            // Option 1: Hit
            int hitVal = minimax(pSum + deck[pos], dSum, pos + 1, true, alpha, beta);
            result = Math.max(result, hitVal);
            alpha = Math.max(alpha, result);
            if (beta <= alpha) {
                cache.put(state, result);
                return result;
            }
            
            // Option 2: Stand (switch to dealer)
            int standVal = minimax(pSum, dSum, pos, false, alpha, beta);
            result = Math.max(result, standVal);
            
        } else {
            // Dealer's turn - deterministic
            if (dSum <= 16) {
                result = minimax(pSum, dSum + deck[pos], pos + 1, false, alpha, beta);
            } else {
                // Dealer stands
                if (pSum > dSum) result = 1;
                else if (pSum < dSum) result = -1;
                else result = 0;
            }
        }
        
        cache.put(state, result);
        return result;
    }
    
    public int blackjackSolverMinimax(int[] cards) {
        deck = cards;
        cache = new HashMap<>();
        
        int pStart = cards[0] + cards[2];
        int dStart = cards[1] + cards[3];
        
        return minimax(pStart, dStart, 4, true, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

class Solution:
    def blackjackSolverMinimax(self, cards: List[int]) -> int:
        cache: Dict[Tuple[int, int, int, bool], int] = {}
        
        def minimax(p_sum: int, d_sum: int, pos: int, player_turn: bool, 
                   alpha: int = float('-inf'), beta: int = float('inf')) -> int:
            # Terminal conditions
            if p_sum > 21:
                return -1  # Player bust
            if d_sum > 21:
                return 1   # Dealer bust
            if pos >= len(cards):
                if p_sum > d_sum:
                    return 1
                elif p_sum < d_sum:
                    return -1
                else:
                    return 0
            
            state = (p_sum, d_sum, pos, player_turn)
            if state in cache:
                return cache[state]
            
            if player_turn:
                result = float('-inf')
                
                # Option 1: Hit
                hit_val = minimax(p_sum + cards[pos], d_sum, pos + 1, True, alpha, beta)
                result = max(result, hit_val)
                alpha = max(alpha, result)
                if beta <= alpha:
                    cache[state] = result
                    return result
                
                # Option 2: Stand (switch to dealer)
                stand_val = minimax(p_sum, d_sum, pos, False, alpha, beta)
                result = max(result, stand_val)
                
            else:
                # Dealer's turn - deterministic
                if d_sum <= 16:
                    result = minimax(p_sum, d_sum + cards[pos], pos + 1, False, alpha, beta)
                else:
                    # Dealer stands
                    if p_sum > d_sum:
                        result = 1
                    elif p_sum < d_sum:
                        result = -1
                    else:
                        result = 0
            
            cache[state] = result
            return result
        
        p_start = cards[0] + cards[2]
        d_start = cards[1] + cards[3]
        
        return minimax(p_start, d_start, 4, True)

Complexity

  • ⏰ Time complexity: O(21 × 21 × n), where n is the number of cards. Alpha-beta pruning reduces the average case significantly.
  • 🧺 Space complexity: O(21 × 21 × n), for the memoization cache and recursion stack.