Blackjack

October 17, 2014

We represent a deck as a list of integers from 0 to 51, from ace of spades, through hearts and diamonds, to the king of clubs; then we ignore the suit, and treat face cards as if they were ten-spots:

(define (pips n)
  (let ((rank (+ (modulo n 13) 1)))
    (if (= rank 1) 11
      (min rank 10))))

Next is a function to count a hand, which is complicated by the fact that an ace can be either 1 or 11. We first compute the sum of the non-aces, plus 1 for each ace. If the total is greater than 21, we are bust. Otherwise, we add 10 for each ace as long as the sum doesn’t exceed 21, then return the final total.

(define (count cards)
  (call-with-values
    (lambda () (split-while (lambda (n) (< n 11)) (sort < cards)))
    (lambda (numbers aces)
      (let ((sum (+ (apply + numbers) (length aces))))
        (if (< 21 sum) sum
          (let loop ((sum sum) (n (length aces)))
            (if (or (zero? n) (< 21 (+ sum 10))) sum
              (loop (+ sum 10) (- n 1)))))))))

To play one game, we folow the same strategy for both play and dealer, holding on 17 or more and hitting below:

(define (play) ; 1 player, 0 tie, -1 dealer
  (let* ((deck (map pips (shuffle (range 52))))
         (pcards (take 2 deck)) (deck (drop 2 deck))
         (dcards (take 2 deck)) (deck (drop 2 deck)))
    ;(display "deal: ")
    ;(display pcards) (display " ")
    ;(display dcards) (display " ")
    ;(display deck) (display " ")
    ;(display (count pcards)) (display " ")
    ;(display (count dcards)) (newline)
    (if (= (count pcards) 21) (if (= (count dcards) 21) 0 1)
      (let player ((pcards pcards) (deck deck))
        ;(display "player: ")
        ;(display pcards) (display " ")
        ;(display deck) (display " ")
        ;(display (count pcards)) (newline)
        (if (< 21 (count pcards)) -1
          (if (< (count pcards) 17)
              (player (cons (car deck) pcards) (cdr deck))
              (let dealer ((dcards dcards) (deck deck))
                ;(display "dealer: ")
                ;(display dcards) (display " ")
                ;(display deck) (display " ")
                ;(display (count dcards)) (newline)
                (if (< 21 (count dcards)) 1
                  (if (< (count dcards) 17)
                      (dealer (cons (car deck) dcards) (cdr deck))
                      (if (< (count pcards) (count dcards)) -1
                      (if (< (count dcards) (count pcards)) 1 0)))))))))))

If you wish, you can uncomment the diplay lines and watch as a game is played. Finally we are ready to run the simulation, summing the wins, losses and ties:

(define (simulate n)
  (let loop ((n n) (sum 0))
    (if (zero? n) sum
      (loop (- n 1) (+ sum (play))))))

If we run ten simulations, playing 1000 games each time, we see that the player always loses; that’s because he has to play first, and may go bust before the dealer ever plays:

> (simulate 1000)
-31
> (simulate 1000)
-89
> (simulate 1000)
-14
> (simulate 1000)
-46
> (simulate 1000)
-122
> (simulate 1000)
-16
> (simulate 1000)
-33
> (simulate 1000)
-113
> (simulate 1000)
-114
> (simulate 1000)
-73

Don’t play Blackjack!

You can run the program at http://programmingpraxis.codepad.org/BN3OknEY, where you will also see the functions that we used from the Standard Prelude.

Pages: 1 2

6 Responses to “Blackjack”

  1. Johann Hibschman said

    I should stop, but here’s a J solution:

    suit=: (2+i.9),(3#10),11          NB. aces are 11 initially
    deck=: 4#suit
    deal=: 3 : '2 11$({~ ?~@#) deck'  NB. we need at most 11 cards each
    dealN=: 3 : 'deal"0 i.y'
    score=: 3 : '(s1>21){s1,(_10*+/11=y)+s1=.+/y'
    stopAt17=: {~ 1 >. I.&17
    score17=: stopAt17@(score\"1)
    winner1=: 3 : '(p1<:21)*.(p2>21)+.p1>p2[''p1 p2''=.|:y'
    winner2=: 3 : '(p1>21)+.(p2<:21)*.p2>p1[''p1 p2''=.|:y'
    istie=:   3 : '(p1<:21)*.(p2<:21)*.p1=p2[''p1 p2''=.|:y'
    

    A sample run is

       scores=. score17 dealN 10000
       (+/ % #) winner1 scores
    0.4028
       (+/ % #) winner2 scores
    0.5031
       (+/ % #) istie   scores
    0.0941
    
  2. matthew said

    I don’t have time to work this up into a full solution right now, but it should be possible to calculate the exact percentages as follows:

    Build a graph of the possible game states; a game state is a target value (initially 16), a score so far, and a deck (or maybe a shoe) that is just a bag of integers 1-10. Initially, for the player, the target is 17, the score is 0 and the deck is whatever we want to start with, eg. 1-9 map to 4, 10 maps to 16 for a single pack.

    Each transition takes one element out of the bag and adds it to the score, a final state is one where the score is greater that the target, at which we stop (with the player bust or not). Each non-final state has a probability associated with each outgoing transition (just the probability of selecting that particular bag element) and we can propagate backwards to get the probabilities of the various final states.

    There are a few thousand possible finishing states where the player doesn’t go bust and we need to use each one as a starting point for a simulation of the dealer, but this shouldn’t be completely intractable.

  3. matthew said

    Here’s some Python then. Use a dictionary to keep track of states (just store the remaining deck as a tuple in here – dictionary keys must be immutable). Divide up the probabilities as we go and combine afterwards for an overall win/lose/draw value, we seem to be able to do this without too much problem with rounding error. Starting with a single pack, we end up with 1336 state in which the player hasn’t busted & must be simulated for the dealer. Total runtime on my i3 laptop is 25 secs and the final probabilities are: lose: 48.9%, win: 41.2%, draw: 9.8%.

    #!/usr/bin/python

    # Create a new deck with ith count decremented
    def makenewdeck(deck,i):
    newdeck = list(deck)
    newdeck[i] -= 1
    return tuple(newdeck)

    class State:
    def __init__ (self,score,ncards,aces,deck,prob):
    self.score = score; self.aces = aces
    self.deck = deck; self.prob = prob;
    self.ncards = ncards; self.ndeck = sum(deck)
    def __str__ (self):
    return “[%d %d %d %g %s]”%(self.score,self.aces,
    self.ncards,self.prob,self.deck)
    def finalstate(self):
    return self.score > 16
    def getscore(self):
    if self.score > 21: return None
    else: return self.score
    def blackjack(self):
    return self.ncards == 2 and self.score == 21

    def play(initdeck):
    initstate = State(0,0,0,initdeck,1.0)
    states = [initstate]
    deckindex = { initdeck: 0 }
    i = 0
    while(i != len(states)):
    s = states[i]; i += 1
    if not s.finalstate():
    for j in range(0,len(s.deck)):
    if s.deck[j] > 0:
    newdeck = makenewdeck(s.deck,j)
    newprob = s.deck[j]*s.prob/s.ndeck
    n = deckindex.get(newdeck)
    if n != None:
    # Seen this state already
    states[n].prob += newprob
    else:
    newscore = s.score
    newaces = s.aces
    if (j == 0):
    # Aces initially valued at 11
    newscore += 11; newaces += 1
    else:
    newscore += j+1
    if newscore > 21 and newaces > 0:
    # If we busted with an ace left, count it as 1
    newscore -= 10; newaces -= 1
    newstate = State(newscore,s.ncards+1,
    newaces,newdeck,newprob)
    n = len(states)
    states.append(newstate)
    deckindex[newdeck] = n
    return states

    initdeck = (4,4,4,4,4,4,4,4,4,16)
    pstates = play(initdeck)
    dealerprob = 0; playerprob = 0; drawprob = 0 # Final probabilities

    for i in range(0,len(pstates)):
    pstate = pstates[i];
    if pstate.finalstate():
    pprob = pstate.prob
    pscore = pstate.getscore() # player score
    if pscore == None:
    dealerprob += pprob # Player is bust
    else:
    dstates = play(pstate.deck)
    # Accumulate subsidiary probabilities here
    # to reduce rounding errors
    dealerprob2 = 0; playerprob2 = 0; drawprob2 = 0
    for j in range (0,len(dstates)):
    dstate = dstates[j]
    if dstate.finalstate():
    dprob = dstate.prob
    dscore = dstate.getscore() # dealer score
    if dscore == None or dscore < pscore:
    playerprob2 += dprob
    elif dscore == pscore:
    if pstate.blackjack() and not dstate.blackjack():
    playerprob2 += dprob
    else:
    drawprob2 += dprob
    else:
    dealerprob2 += dprob
    # Add in the subsidiary probabilities
    dealerprob += pprob*dealerprob2
    playerprob += pprob*playerprob2
    drawprob += pprob*drawprob2

    print (dealerprob,playerprob,drawprob,dealerprob+playerprob+drawprob)

  4. matthew said

    And with proper indentation (it would be nice if comments were editable):

    #!/usr/bin/python
    
    # Create a new deck with ith count decremented
    def makenewdeck(deck,i):
        newdeck = list(deck)
        newdeck[i] -= 1
        return tuple(newdeck)
    
    class State:
        def __init__ (self,score,ncards,aces,deck,prob):
            self.score = score; self.aces = aces
            self.deck = deck; self.prob = prob;
            self.ncards = ncards; self.ndeck = sum(deck)
        def __str__ (self):
            return "[%d %d %d %g %s]"%(self.score,self.aces,
                                       self.ncards,self.prob,self.deck)
        def finalstate(self):
            return self.score > 16
        def getscore(self):
            if self.score > 21: return None
            else: return self.score
        def blackjack(self):
            return self.ncards == 2 and self.score == 21
    
    def play(initdeck):
        initstate = State(0,0,0,initdeck,1.0)
        states = [initstate]
        deckindex = { initdeck: 0 }
        i = 0
        while(i != len(states)):
            s = states[i]; i += 1
            if not s.finalstate():
                for j in range(0,len(s.deck)):
                    if s.deck[j] > 0:
                        newdeck = makenewdeck(s.deck,j)
                        newprob = s.deck[j]*s.prob/s.ndeck
                        n = deckindex.get(newdeck)
                        if n != None:
                            # Seen this state already
                            states[n].prob += newprob
                        else:
                            newscore = s.score
                            newaces = s.aces
                            if (j == 0):
                                # Aces initially valued at 11
                                newscore += 11; newaces += 1
                            else:
                                newscore += j+1
                            if newscore > 21 and newaces > 0:
                                # If we busted with an ace left, count it as 1
                                newscore -= 10; newaces -= 1
                            newstate = State(newscore,s.ncards+1,
                                             newaces,newdeck,newprob)
                            n = len(states)
                            states.append(newstate)
                            deckindex[newdeck] = n
        return states
    
    initdeck = (4,4,4,4,4,4,4,4,4,16)
    pstates = play(initdeck)
    dealerprob = 0; playerprob = 0; drawprob = 0 # Final probabilities
    
    for i in range(0,len(pstates)):
        pstate = pstates[i];
        if pstate.finalstate():
            pprob = pstate.prob
            pscore = pstate.getscore() # player score
            if pscore == None:
                dealerprob += pprob # Player is bust
            else:
                dstates = play(pstate.deck)
                # Accumulate subsidiary probabilities here
                # to reduce rounding errors
                dealerprob2 = 0; playerprob2 = 0; drawprob2 = 0
                for j in range (0,len(dstates)):
                    dstate = dstates[j]
                    if dstate.finalstate():
                        dprob = dstate.prob
                        dscore = dstate.getscore() # dealer score
                        if dscore == None or dscore < pscore:
                            playerprob2 += dprob
                        elif dscore == pscore:
                            if pstate.blackjack() and not dstate.blackjack():
                                playerprob2 += dprob
                            else:
                                drawprob2 += dprob
                        else:
                            dealerprob2 += dprob
                # Add in the subsidiary probabilities
                dealerprob += pprob*dealerprob2
                playerprob += pprob*playerprob2
                drawprob += pprob*drawprob2
    
    print (dealerprob,playerprob,drawprob,dealerprob+playerprob+drawprob)
    
  5. ;; Interactive console Black jack

    (defn cartesian-product [l & ls]
    (reduce
    (fn [a b] (for [x a y b] (conj x y)))
    (map vector l) ls))

    ;; The deck of cards. The suits are not being used in the game but it’s more
    ;; fun if they’re printed anyway
    (def deck (cartesian-product ‘(\u2665 \u2660 \u2666 \u2663) (range 13)))

    (defn print-card [[color val]]
    (let [v (if (== val 0) ‘A
    (if ( a 9) 10 (+ a 1)))))

    (defn bust? [v] (> v 21))

    ;; Find all the possible sums of values of the cards and choose the appropriate one
    ;; return 50 if bust
    (defn hand-value [cards]
    (let [possible-values (apply cartesian-product (map card-value cards))
    possible-sums (map #(apply + %) possible-values)]
    (if (bust? (apply min possible-sums)) 50
    (apply max (filter #( v 16))

    ;; Interactive player’s logic
    (defn players-logic [hand value]
    (if (= 21 value) true
    (do
    (println (map print-card hand) “\n” value ” – More?”)
    (= “n” (read-line)))))

    ;; The two game phases:

    (defn dealers-game [hand pile value]
    (let [[d-hand pile d-value] (deal-hand pile dealers-logic)]
    (println “Dealer’s hand” (map print-card d-hand))
    (if (or (bust? d-value) (> value d-value)) :win :lose)))

    (defn game [pile]
    (let [[hand pile value] (deal-hand pile players-logic)]
    (println “Your hand” (map print-card hand))
    (cond (= 21 value) :win
    (bust? value) :lose
    :else (dealers-game hand pile value))))

    ;; Let’s play!

    (loop [won 0 lost 0]
    (let [result (game (shuffle deck))
    win (if (= :win result) 1 0)
    won (+ win won)
    lost (- (+ 1 lost) win)]
    (println ({:win “You win” :lose “Dealer wins”} result))
    (if ((fn [] (println “Play another game?”) (= “n” (read-line))))
    (do
    (println “You won” (int (* 100 (/ won (+ won lost)))) “% of the games”)
    (vector won lost))
    (recur won lost))))

  6. my previous post is about clojure.

    The commenting system on this blog goes bust! ;-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: