Problem Set 2 - Comments

Question 3: Define a procedure higher-card? that takes two cards are operands and evaluates to #t if and only if the first card has a higher rank than the second card. Note that the card suit does not matter in this comparison.

(define (higher-card? card1 card2)  
  (> (card-rank card1) (card-rank card2)))

Note that we could use (car card1) instead of using (card-rank card1) and the procedure would still behave correctly. It is better to use card-rank though, since this deals with the card as an abstraction, not the details of how we represent it as a cons pair. It makes it easier to understand what higher-card? is doing, and it means if we decide to change how cards are represented (that is, change make-card), we would only need to change card-rank and card-suit, but not all the other procedures that use cards.

Question 4: Define a procedure sort-hand that takes one operand that is a list of cards, and evaluates to the cards sorted by decreasing card value (the highest card should be first in the list).

(define (sort-hand cards) (sort card higher-card?))

Question 5: Define the higher-similar-hand? procedure, completing the template we have provided in ps2.scm. It should take two poker hands as operands, and can assume the hands are of the same category. It should evaluate to #t if and only if the first hand beats the second hand.

(define (higher-similar-hand? hand1 hand2)
  ;; precondition: hand1 and hand2 must be the same class of hand 
  ;;                    (e.g., they are both flushes, or both full
  ;;                            houses, etc.)
  ;; for hand1 to be higher than hand2, the first non-equal card 
  ;; must be higher
  (define (higher-hand-helper? shand1 shand2)
    ;; precondition: shand1 and shand2 must be sorted by ranks
    (if (null? shand1)
        #f ; got to the end, the hands are equal
        (if (higher-card? (car (car shand1)) (car (car shand2)))
            #t ; hand1's most paired card is higher, evaluate to true
            (if (higher-card? (car (car shand2)) (car (car shand1)))
                #f ; hand2's most paired card is higher, evaluate to false
                (higher-hand-helper? (cdr shand1) (cdr shand2))
                ))))
  (higher-hand-helper? (sort-by-ranks hand1) (sort-by-ranks hand2)))

When the first cards are of matching strength in the two hands, we then compare the rest of the hands.

Question 6: Define the possible-hands procedure, completing the template we have provided in ps2.scm. It should take two operands: the first is a list of two cards representing a player's hole cards; the second is a list of 5 cards representing the community cards. It should evaluate to a list of all possible hands that could be made using 0, 1, or 2 of the player's hole cards and enough of the community cards to make a five-card hand.

The easy way to do this is to realize that what we are really doing is just choosing 5 cards out of the seven cards that we get by combining the hole cards and community cards:

(define (possible-hands hole-cards community-cards)
  (choose-n 5 (append hole-cards community-cards)))

Question 7: Define the find-best-hand procedure, completing the template we have provided in ps2.scm. It should take two operands: the first is a list of two cards representing a player's hole cards; the second is a list of 5 cards representing the community cards. It should evaluate the best possible hands that could be made by the player using 0, 1, or 2 of the player's hole cards and enough of the community cards to make a five-card hand.

We can find the best hand by sorting all the possible hands according to higher-hand? and then picking the first one:

(define (find-best-hand hole-cards community-cards)
  (car (sort (possible-hands hole-cards community-cards) higher-hand?))

Question 8: Predict how long it will take to evaluate an application of analyze-flop-situation (for example, (analyze-flop-situation connect67 aces-in-hole straight-draw3)). You should start by timing analyze-turn-situation. You can do this using the time procedure: (time (show-analysis (analyze-turn-situation connect67 aces-in-hole straight-draw4))). This will print out something like cpu time: 3523 real time: 4823 gc time: 203 (the numbers here are made up for the example). The number after real time gives the number of milliseconds it took to do the evaluation (in this case 4.823 seconds). If you want to try evaluation and timing analyze-flop-situation you can, but you should predict how long it will take first.

We need to estimate how much work analyze-flop-situation is compared to analyze-turn-situation. Here's the definition of analyze-flop-situation:

 (let ((current-deck (remove-cards (append hole1 hole2 community) 
                                   full-deck)))
    (map
      (lambda (turn-card) 
        (map 
           (lambda (outs)
             (cons turn-card outs))
           (analyze-turn-situation hole1 hole2 
                                   (cons turn-card community))))
     current-deck)))

The map procedure evaluates (analyze-turn-situation ...), so it will evaluate once for each element in the list. The list is current-deck which is the initial deck of 52 cards with the already dealt cards removed. This leaves 45 cards (since 7 cards have been dealt after the flop), which means we will need to evaluate analyze-turn-situation applied 45 times. The actual time each application takes will vary a bit with the actual cards, but it is reasonable to assume that the average time will be about the same. The extra work of the map and cons is small compared to the analyze-turn-situation work, so it is a good guess that it will take about 45 times longer than one analyze-turn-situation evaluation.

Here are the actual timings on my laptop (the lab machines have somewhat more memory, so your timings were probably faster):

> (time (show-analysis (analyze-turn-situation connect67 aces-in-hole straight-draw4)))

Winning outs (15): 2c 3c 5h 5d 5c 5s 9c 10h 10d 10c 10s Jc Qc Kc Ac
Chopping outs (0):
Losers (29): 2h 2d 2s 3h 3d 3s 4h 4d 4s 6h 6d 6s 7h 7d 7s 8h 8d 8s 9h 9d Jd Js Qh Qd Qs Kh Kd Ks As
cpu time: 6910 real time: 6970 gc time: 1260

> (time (show-flop-analysis (analyze-flop-situation connect67 aces-in-hole straight-draw3)))

Winners:
Turn: 2h Rivers: 2c 3c 5h 5d 5c 5s 9c 10h 10d 10c 10s Jc Qc Kc Ac
...
Turn: As Rivers: 2c 3c 5h 5d 5c 5s 10h 10d 10c 10s Jc Qc Kc
Choppers:
... Losers:
Turn: 2h Rivers: 2d 2s 3h 3d 3s 4h 4d 4s 6h 6d 6s 7h 7d 7s 8h 8d 8s 9h 9d Jh Jd Js Qh Qd Qs Kh Kd Ks As
...
Turn: Ac Rivers: 4h 4d 4s 8h 8d 8s 9h 9d 9c As
Turn: As Rivers: 2h 2d 2s 3h 3d 3s 4h 4d 4s 6h 6d 6s 7h 7d 7s 8h 8d 8s 9h 9d 9c Jh Jd Js Qh Qd Qs Kh Kd Ks Ac
Winning odds (1114): 0.5626262626262626 Chopping odds (0): 0.0 Losing odds (866): 0.43737373737373736
cpu time: 317827 real time: 320330 gc time: 58093

The real time, 320330 ms, is 320 seconds which is about 5 minutes. Reasonable enough to wait for the results, but much to long for playing poker. Comparing the reported cpu time for the two evaluations, we get:

> (exact->inexact (/ 317827 6910))

45.99522431259045

So, our 45 times slower estimate was quite accurate.

Question 9: This implementation is obviously too slow for many practical uses, including building a poker bot. Suggest some approaches you would use if you wanted to make a faster implementation.

Discussion: Based on the analysis from question 8, We can think about two ways to make our analysis faster: (1) reduce the number of times we need to evaluate analyze-turn-situation and (2) reduce the amount of time each evaluation takes. We consider each case next.

(1) The current evaluation evalautes each possible set of five community cards twice, since the order of the turn and river card do not matter when evaluating the final hands. For example, if the turn card is 5h and the river card is 7d, it is exactly the same outcome as when the turn card is 7d and the river card it 5h.

This means, we are evaluating analyze-turn-situation twice as many times as we need to. An easy way to fix this is to only evaluate the situations where the lower card is the turn card. So, we would evaluate 5h 7d but not 7d 5h.

To implement this, we need to add a parameter to analyze-turn-situation to reflect the set of cards we will condisider:

(define (analyze-turn-situation hole1 hole2 community deck)
  (accumulate-outs
   (map (lambda (river-card) 
          (let ((outcome (compare-hands?
                          (find-best-hand hole1 
                                          (cons river-card community))
                          (find-best-hand hole2 
                                          (cons river-card community)))))
            (if (eq? outcome 'higher)
                (list (list river-card) null null)
                (if (eq? outcome 'equal)
                    (list null (list river-card) null) ; chop
                    (list null null (list river-card))))))
        deck)))

And, in analyze-flop-situtation we filter out all cards below (and including) the current card from the deck:

(define (analyze-flop-situation hole1 hole2 community)
  (let ((current-deck (remove-cards (append hole1 hole2 community) 
                                    full-deck)))
    (map (lambda (turn-card) 
           (map (lambda (outs)
                  (cons turn-card outs))
                (analyze-turn-situation 
                 hole1 hole2 
                 (cons turn-card community)
                 (filter (lambda (card)
                           (or (higher-card? card turn-card) 
                               (and (same-rank? card turn-card) 
                                    (> (suit-num (card-suit card)) 
                                       (suit-num (card-suit turn-card)))))) 
                            current-deck))))
            current-deck)))

As expected, this halves the time:

> (time (show-flop-analysis (analyze-flop-situation connect67 aces-in-hole straight-draw3)))

... Winning odds (557): 0.5626262626262626 Chopping odds (0): 0.0 Losing odds (433): 0.43737373737373736
cpu time: 144708 real time: 145419 gc time: 15961

Note that the odds are the same as before, except the number of actual situations counted is half what was counted when both orderings of the turn and river card were considered.

We could try other ways of reducing the number of cards considered, but anything else would require complex poker logic (to decide that a set of cards are equivalent for this situation) and risk producing incorrect results.

(2) To make analyze-turn-situtation more efficient, we need to understand what is taking most of the time. In complex programs, programmers use a tool called a profiler to measure where the time is going. In this case, we can guess that most of the time is spent in find-best-hand, which calls higher-hand?.

The higher-hand? procedure does lots or repetitive work:

(define (higher-hand? hand1 hand2)
  (cond
    ((straight-flush? hand1)  (or (not (straight-flush? hand2)) 
                                  (and (straight-flush? hand2) 
                                       (higher-similar-hand? hand1 hand2))))
    ((four-of-a-kind? hand1)  (or (and (not (straight-flush? hand2)) 
                                       (not (four-of-a-kind? hand2)))
                                  (and (four-of-a-kind? hand2) 
                                       (higher-similar-hand? hand1 hand2))))
    ((full-house? hand1)      (or (and (not (straight-flush? hand2)) 
                                       (not (four-of-a-kind? hand2)) 
                                       (not (full-house? hand2)))
                                  (and (full-house? hand2)
                                       (higher-similar-hand? hand1 hand2))))
    ((flush? hand1)           (and (not (beats-flush? hand2))
                                   (or (and (flush? hand2) 
                                            (higher-similar-hand? hand1 hand2))
                                       (not (flush? hand2)))))
    ...

Note that each of the category comparisons does much of the same work. For example:

(define (beats-flush? hand)
  (or (straight-flush? hand) 
      (four-of-a-kind? hand) (full-house? hand)))

It might be a lot faster if we just categorized each hand once, and did not need to repeat those comparisons. We do this by giving each hand category a number value: 0 (high card), 1 (pair), 2 (two pair), 3 (three-of-a-kind), 4 (wheel straight), 5 (straight), 6 (flush), 7 (full house), 8 (four-of-a-kind), 9 (straight flush).

Surprisingly (to me at least), this change didn't actually help, it actually slowed things down a little bit (see if you can figure out why):

Winning odds (557): 0.5626262626262626 Chopping odds (0): 0.0 Losing odds (433): 0.43737373737373736
cpu time: 152529 real time: 153140 gc time: 25487

It does, however, make it easier to enable another change. Most of the hand categorization routines begins by first evaluating sort-by-ranks to sort the cards. If we modify these procedures to expect a pre-sorted hand instead, we can avoid all this duplicate work.

(define (hand-category hand)
  (if (flush? hand)
      (if (any-straight? hand) 9 6)
      (if (straight? hand) 
          5
          (if (wheel-straight? hand) 
              4
              (let ((shand (sort-by-ranks hand)))
                (cond
                  ((s-four-of-a-kind? shand) 8)
                  ((s-three-of-a-kind? shand) (if (s-full-house? shand) 7 3))
                  ((s-two-pair? shand) 2)
                  ((s-pair? shand) 1)
                  (#t 0)))))))


(define (s-four-of-a-kind? hand) (= (length (car hand)) 4))

(define (s-full-house? hand)
  (and
   (= (length (car hand)) 3)
   (= (length (car (cdr hand))) 2)))

(define (s-three-of-a-kind? hand) (= (length (car hand)) 3))

(define (s-two-pair? hand)
  (and (= (length (car hand)) 2)
       (= (length (car (cdr hand))) 2)))

(define (s-pair? hand) (= (length (car hand)) 2))

This helps a lot:

Winning odds (557): 0.5626262626262626 Chopping odds (0): 0.0 Losing odds (433): 0.43737373737373736
cpu time: 60106 real time: 61428 gc time: 6390

So, we have gone from 5 minutes down to 1 minute.

The next thing we observe is that find-best-hand does a lot more work than necessary. It sorts all the possible hands in order, when all we need to do is find the best hand. We will talk a lot about sorting in class this week, but even the best way of sorting requires many more comparisons than just finding the best element. So, we replace the find-best-hand definition with this:

(define (find-best comparator lst)
  (define (find-best-helper current-best lst)
    (if (null? lst) current-best
        (if (comparator current-best (car lst))
            (find-best-helper current-best (cdr lst))
            (find-best-helper (car lst) (cdr lst)))))
  (find-best-helper (car lst) (cdr lst)))
  
(define (find-best-hand hole-cards community-cards)
  (find-best higher-hand? (possible-hands hole-cards community-cards)))

This helps a lot:

Winning odds (557): 0.5626262626262626 Chopping odds (0): 0.0 Losing odds (433): 0.43737373737373736
cpu time: 17526 real time: 17666 gc time: 2322

If we need to do more, there are lots of options. We could change the representation of cards to use simple numbers instead of cons pairs. Note that we could do this by just changing the make-card, card-rank, and card-suit procedures, and the rest of the code would still work. Some people suggested rewriting the code in a more performance-focused programming language such as C. This could help a lot, but would be a lot of work (and risk introducing bugs). We could also use a Scheme compiler to compile the code we already have, instead of running it in the interpreter. This would translate the Scheme code into a lower-level machine language so it would run faster. We could try to use more poker logic to group possible cards into equivalence classes. This is what most human players do, thinking of which cards would help their hand improve and using heuristics to approximate the odds. It would be tricky to program, however, and have lots of possible pitfalls where we could miss important cards.

I'll leave further improvements as an open challenge program. A significant improvement is worth one or more gold stars.