Texas Hold ‘Em

March 23, 2010

This exercise is harder than it looks. We begin with the code to rank hands. A card is represented as a two-character string, with pips in the first character and suit in the second. The four possible suits are #\S spades, #\H hearts, #\C clubs and #\D diamonds. For pips, digits represent themselves, with #\T ten, #\J jack, #\Q queen, #\K king, and #\A ace. For instance, "AH" is the ace of hearts. The functions below identify the pips and suit:

(define pips
  (let ((ps (map cons (map char-upcase
          (string->list "23456789TJQKA")) (range 2 15))))
    (lambda (card)
      (cdr (assoc (char-upcase (string-ref card 0)) ps)))))

(define (suit card) (char-upcase (string-ref card 1)))

A flush has all five suits the same:

(define (flush? hand) (apply char=? (map suit hand)))

There are two kinds of straights, with ace high and ace low; straight returns the number of the highest-ranking card in a hand, or #f if no straight is present:

(define (straight cs)
  (cond ((equal? cs '(14 5 4 3 2)) 5)
        ((apply = 1 (map - (take 4 cs) (cdr cs))) (car cs))
        (else #f)))

The same function looks for n cards with the same rank; it returns the rank, or #f if the hand does not contain n cards of the same rank:

(define (same n cards)
  (let ((len (length cards)))
    (let loop ((i 0) (cards cards))
      (cond ((negative? (- len n i)) #f)
            ((apply = (take n cards)) (car cards))
            (else (loop (+ i 1) (cdr cards)))))))

Now we can look at the code to rank a hand. Rank returns a list of numbers. The first number is the type of hand, ranging from 9 for a straight flush to 1 for a high card. The remaining numbers are tie-breakers, from highest to lowest. Note the difference between a hand (a list of five cards) and a list of cards (a list of five pips, sorted in descending order):

(define (rank hand)
  (let ((cards (sort > (map pips hand))))
    (cond ((straight cards) =>
            (lambda (c)
              (if (flush? hand)
                  (list 9 c)
                  (list 5 c))))
          ((flush? hand) (cons 6 cards))
          ((same 4 cards) =>
            (lambda (c)
              (list 8 c (car (remove c cards)))))
          ((same 3 cards) =>
            (lambda (c)
              (let* ((cs (remove c cards))
                     (k (same 2 cs)))
                (if k (list 7 c k) (cons* 4 c cs)))))
          ((same 2 cards) =>
            (lambda (c)
              (let* ((cs (remove c cards))
                     (k (same 2 cs)))
                (if k (list 3 c k (car (remove k cs)))
                      (cons* 2 c cs)))))
          (else (cons 1 cards)))))

The order of the cond clauses is significant. The first clause identifies straights and straight flushes. The second clause identifies flushes. The next three clauses identify quads, trips and pairs; the trips clause also looks for full houses, and the pairs clause also looks for two pairs. The final clause catches anything else. The rank function is complicated enough to deserve a test:

(define (test-rank)
  (assert (rank '("AH" "KH" "QH" "JH" "TH")) '(9 14))
  (assert (rank '("7H" "7C" "3H" "7S" "7D")) '(8 7 3))
  (assert (rank '("TH" "JC" "TS" "JD" "TC")) '(7 10 11))
  (assert (rank '("4H" "7H" "AH" "KH" "9H")) '(6 14 13 9 7 4))
  (assert (rank '("AH" "2C" "3S" "4D" "5H")) '(5 5))
  (assert (rank '("9C" "4S" "KD" "9D" "9H")) '(4 9 13 4))
  (assert (rank '("6D" "6C" "8H" "TD" "8D")) '(3 8 6 10))
  (assert (rank '("9C" "3S" "4D" "7C" "3D")) '(2 3 9 7 4))
  (assert (rank '("4C" "KD" "8S" "6D" "2D")) '(1 13 8 6 4 2)))

Two hands are compared by running through the lists returned by rank; the first point of mis-match determines the winner:

(define (lt? hand1 hand2)
  (let loop ((h1 (rank hand1)) (h2 (rank hand2)))
    (cond ((or (null? h1) (null? h2)) #f)
          ((< (car h1) (car h2)) #t)
          ((< (car h2) (car h1)) #f)
          (else (loop (cdr h1) (cdr h2))))))

Now we return to the original problem. Here is a function that enumerates all combinations of n items taken from a list; it’s simple and elegant, and dates to the folklore of computing. We use combs to generate all possible five-card hands from a list of seven cards:

(define (combs n xs)
  (cond ((zero? n) '(()))
        ((null? xs) '())
        (else (append (map (lambda (c) (cons (car xs) c))
                           (combs (- n 1) (cdr xs)))
                      (combs n (cdr xs))))))

To find the best hand, loop through all the possibilities:

(define (best-hand cards)
  (let ((hands (combs 5 cards)))
    (let loop ((best (car hands)) (hands (cdr hands)))
      (cond ((null? hands) best)
            ((lt? best (car hands))
              (loop (car hands) (cdr hands)))
            (else (loop best (cdr hands)))))))

Here’s an example, two pairs of aces and eights, the “dead man’s hand” held in a game of five-card draw by Wild Bill Hickock at the time of his murder:

> (best-hand '("AC" "JD" "8S" "8C" "AS" "3D" "4D"))
("AC" "JD" "8S" "8C" "AS")

We used take, drop, range, cons*, remove, sort and assert from the Standard Prelude. You can run the code at http://programmingpraxis.codepad.org/tdgaPIju.

About these ads

Pages: 1 2

5 Responses to “Texas Hold ‘Em”

  1. [...] Praxis – Texas Hold ‘Em By Remco Niemeijer In today’s Programming Praxis exercise we have to write a program to rank poker hands. The provided Scheme [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/03/23/programming-praxis-texas-hold-em/ for a version with comments):

    import Data.Char
    import Data.List
    import qualified Data.List.Key as K
    
    toCard :: String -> (Int, Char)
    toCard ~[v,s] = maybe undefined (flip (,) $ toUpper s) .
                    lookup v $ zip "23456789TJQKA" [2..]
    
    flush :: [(Int, Char)] -> Bool
    flush = (== 1) . length . K.group snd
    
    straight :: [Int] -> Bool
    straight xs = (l:r) == [2,3,4,5,14] || isPrefixOf r [l + 1..]
                  where (l:r) = reverse $ map fromEnum xs
    
    same :: [Int] -> [Int]
    same = reverse . sort . map length . group
    
    rank :: [String] -> (Int, [Int])
    rank xs | straight s && flush cs     = (9, s)
            | elem 4 $ same s            = (8, s)
            | same s == [3,2]            = (7, s)
            | flush cs                   = (6, s)
            | straight s                 = (5, s)
            | elem 3 $ same s            = (4, s)
            | elem 2 . delete 2 $ same s = (3, s)
            | elem 2 $ same s            = (2, s)
            | otherwise                  = (1, s)
            where s = reverse . sort $ map fst cs
                  cs = map toCard xs
    
    choose :: Int -> [a] -> [[a]]
    choose 0 _      = [[]]
    choose _ []     = []
    choose n (x:xs) = map (x:) (choose (n-1) xs) ++ choose n xs
    
    bestHand :: [String] -> [String]
    bestHand = K.maximum rank . choose 5
    
  3. Remco Niemeijer said

    Phil pointed out a bug in my initial version where n-of-a-kind hands were compared on the values of the remaining cards. Here’s a fixed version:

    import Data.Char
    import Data.List
    import qualified Data.List.Key as K
    
    toCard :: String -> (Int, Char)
    toCard ~[v,s] = maybe undefined (flip (,) $ toUpper s) .
                    lookup v $ zip "23456789TJQKA" [2..]
    
    flush :: [(Int, Char)] -> Bool
    flush = (== 1) . length . K.group snd
    
    straight :: [Int] -> Bool
    straight xs = (l:r) == [2,3,4,5,14] || isPrefixOf r [l + 1..]
                  where (l:r) = reverse $ map fromEnum xs
    
    same :: [Int] -> [Int]
    same = map length . group
    
    rank :: [String] -> (Int, [Int])
    rank xs | straight s && flush cs     = (9, s)
            | elem 4 $ same s            = (8, s)
            | same s == [3,2]            = (7, s)
            | flush cs                   = (6, s)
            | straight s                 = (5, s)
            | elem 3 $ same s            = (4, s)
            | elem 2 . delete 2 $ same s = (3, s)
            | elem 2 $ same s            = (2, s)
            | otherwise                  = (1, s)
            where s = concat . reverse . K.sort (\x -> (length x, head x)) .
                      group . sort $ map fst cs
                  cs = map toCard xs
    
    choose :: Int -> [a] -> [[a]]
    choose 0 _      = [[]]
    choose _ []     = []
    choose n (x:xs) = map (x:) (choose (n-1) xs) ++ choose n xs
    
    bestHand :: [String] -> [String]
    bestHand = K.maximum rank . choose 5
    
  4. Mike said

    A Python version:

    from itertools import combinations, groupby, product, starmap
    from random import sample
    
    def rank(card):
        return "23456789TJQKA".index(card[0]) + 2
    
    def suit(card):
        return card[1]
    
    def score(hand):
        """
        The cards are grouped by rank.  Based on the grouping, make a list
        of the length of each group and a list of the rank of each group.
        
        The score of the hand is a tuple containing the two lists
            ex: AC KD 2S KD AH  -> ((2,2,1), (14,13,2))
        
        Made-up groups are used for straights and flushes so they sort properly
            triple (3,1,1) < straight (3,1,2) < flush (3,1,3)
                   < four of a kind (4,1) < straight flush (4,2)
        """
        
        ranks = sorted( map( rank, hand ), reverse=True )
        grouper = ( ( len( list( g ) ), r ) for r,g in groupby( ranks ) )
        groups, group_ranks = zip( *sorted( grouper, reverse=True ) )
    
        if groups == (1,1,1,1,1):
            flush = len( set( map( suit, hand ) ) ) == 1
            straight = ranks[0] == ranks[4] + 4 or ranks == [13,5,4,3,2]
    
            if straight and flush:
                groups = (4,2)
            elif flush:
                groups = (3,1,3)
            elif straight:
                groups = (3,1,2)
    
        return groups, group_ranks
    
    # examples
    fmt = "{deal:^42} {best:^30}"
    print fmt.format(deal="Deal", best="Best")
    
    # dead man's hand
    deal = "AC JD 8S 8C AS 3D 4D".split()
    best = max( combinations( deal, 5 ), key=score )
    print fmt.format(deal=deal, best=best)
    
    #random hands
    deck = map( ''.join, product( '23456789TJQKA', 'CDHS' ) )
    for n in range(10):
        deal = sample( deck, 7 )
        best = max( combinations( deal, 5 ), key=score )
        print fmt.format(deal=deal, best=best)
    
    
  5. Bill B said

    My solution to Texas Hold’Em (ruby) is on the long side, so it can be seen here http://codingjunkie.net/?p=326.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: