Project Euler Problem 54

Ivar Thorson bio photo By Ivar Thorson

Poker! In order to solve problem 54, we need to basically model a poker hand and compute the strength of it relative to another hand.

I was surprised at how concisely the game of poker could be modeled in Clojure. Most of the work is done in a few let statements, followed by a small amount of branching logic. A more complete implementation of poker would probably require better management of a deck, as well as perhaps a better representation of a the data describing a card. A two-character string is a perhaps a little awkward to use at times.

use '[clojure.contrib.duck-streams :only (read-lines)])

(def card-nums (zipmap "23456789TJQKA" (iterate inc 2)))

(def card-suits (set "HDSC")) 

(defn card-val [c] (card-nums (first c)))

(def hand-rank (zipmap [:straight-flush
                        :four-of-a-kind
                        :full-house
                        :flush
                        :straight
                        :three-of-a-kind
                        :two-pairs
                        :pair
                        :high-card] (range)))

(defn hand
  "Returns the type of the hand and a list of the card groups."
  [cards]
  (let [cs (sort #(> (card-val %1) (card-val  %2)) cards)
        ns (into (sorted-set) (map #(card-val %) cs))
        straight? (and (= 5 (count ns)) (= 4 (- (last ns) (first ns))))
        flush? (apply = (map second cards))
        groups (sort #(> (count %1) (count %2))
                     (vals (group-by #(card-val %) cs)))
        g1 (count (first groups))
        g2 (count (second groups))
        hand-type (cond
                   (and straight? flush?)  :straight-flush 
                   (= 4 g1)                :four-of-a-kind 
                   (and (= 3 g1) (= 2 g2)) :full-house 
                   flush?                  :flush 
                   straight?               :straight
                   (= 3 g1)                :three-of-a-kind
                   (and (= 2 g1) (= 2 g2)) :two-pairs
                   (= 2 g1)                :pair
                   :else                   :high-card)]
    [hand-type groups]))

(defn break-tie
  "Assuming that g1 and g2 represent the same type of hand (eg: full house),
  returns the outcome for the g1 hand (:win, :lose, or rarely :tie)"
  [g1 g2]
   (let [a (first (first g1))
        b (first (first g2))]
    (if (or (nil? a) (nil? b))
      :tie
      (cond
       (> (card-val a) (card-val b)) :win
       (< (card-val a) (card-val b)) :lose
       :else (recur (next g1) (next g2))))))

(defn i-win? [me you]
  (let [[tm gm] (hand me)
        [ty gy] (hand you)]
    (cond
     (< (hand-rank tm) (hand-rank ty)) :win
     (> (hand-rank tm) (hand-rank ty)) :lose
     :else (break-tie gm gy))))

(defn euler-53 [file]
  (count
   (for [line (read-lines file)
         [me you] [(split-at 5 (re-seq #"\S+" line))] 
         :when (= (i-win? me you) :win)]
     :win)))

(time (euler-53 "/path/to/poker.txt"))

That solves the problem, but we can’t stop there! Let’s just use a brute-force approach to compute the probability of a given hand beating n opponents in a random 5-card no-draw game of poker. Let’s start by adding some functionality for a deck of cards. It wouldn’t make much sense if you could get the same cards as your opponent!

(def plain-deck (for [n "23456789TJQKA"
                      suit "DHCS"]
                  (apply str (str n) (str suit))))

(defn take-n-hands [n deck]
  {:pre [(< (* n 5) (count deck))]}
  (loop [r []
         d (shuffle deck)]
    (if (>= (count r) n)
      [r d]
      (recur (conj r (take 5 d)) (shuffle (drop 5 d))))))

(defn test-2-players [_]
  (let [[hs deck] (take-n-hands 2 plain-deck)
        [a b] hs]
    (i-win? a b)))

(frequencies (map test-2-players (range 100000))) ;; Wins about 50% of the time

Now we can define a hand for ourselves, and compute the probability that we will defeat 3 opponents in a no-draw, simplest-poker-possible kind of situation:

(def my-hand ["2C" "3S" "8S" "8D" "TD"])

(defn frequencies-i-win [my-cards other-players trials]
  (frequencies
   (for [d [(remove (into #{} my-hand) plain-deck)]
         t (range trials)
         [others _] [(take-n-hands other-players d)]]
     (if (every? #(= :win %) (map #(i-win? my-cards %) others))
       :win
       :lose))))

(defn probability-i-win [my-cards other-players trials]
  (let [fs (frequencies-i-win my-cards other-players trials)
        w (if-let [wins (:win fs)] wins 0 )
        l (if-let [losses (:lose fs)] losses 0)]
    (str (* 100.0 (/ w trials)) "% chance of win")))
 
(probability-i-win my-hand 1 100000) ;; "69.878% chance of win"

I imagine that a human-machine combination such as this – one in which a computer could help you evaluate the mathematical strength of your hand – would be very useful for improving your understanding of the strength of a particular hand.

Of course, the real magic of poker is in the betting strategy, and any simple computer algorithm I could implement here would doubtlessly do poorly against all but the most inexperienced of beginners.

Still, it might be fun to expand on this later, add a GUI, and some logic for Texas Hold ‘em.