Phil Laak, Los Angeles Times, July 18, 2005.
In this problem set, you will develop procedures that can calculate odds for poker. Actually creating a poker bot involves making decisions based on incomplete information about what the other players have and how they behave. This is much harder than just calculating odds, but knowing the odds is important for any poker strategy.
We will consider the game Texas Hold 'Em. This is the poker variant that is used in most major tournaments. Each player is dealt two hole cards. These are kept hidden from the other players and can only be used by the player who was dealt them. Then, five community cards are dealt. Every player may use these cards. There are betting rounds after the hold cards are dealt, and after the third, fourth, and final community cards.
At the end of the hand, each player makes their best five-card hand using as many of their own hole cards as they want and the remaining cards from the community cards. So, a player may make a hand using just the five community cards (and none of their hole cards), either of their hole cards and any four of the community cards, or both of their hold cards and any three of the community cards.
To calculate the odds a player will win a hand, we need to know all possible hands that player could get and how many of them beat the other player's hand. For example, when there is one community card left to be dealt, that means we need to consider how many of the remaining cards in the deck will allow the player to make a hand that is better than the other players hand.
Becoming Pros at Cons
and can hardly count all the money in your hip pocket, much less hold on to it.
Amarillo Slim
The elements in a cons pair can be anything, even another cons pair. By using cons pairs inside cons pairs inside cons pairs we can build up complex data structures to represent any data we want.cons cell
car element cdr element
Consider the following Scheme fragments:
- (cons 100 50)
- (cons (cons 1 2) 3)
- (cons 1 (cons 2 3))
- (car (cons (cons 1 2) null))
- (cdr (car (cons (cons 1 2) null)))
- (car (cdr (cons (cons 1 2) null)))
- Explain why the fragment is not a valid Scheme expression; or,
- Predict what value the expression will evaluate to. If the expression evaluates to a compound data structure, draw a picture showing the structure. ("Draw the structure" means "draw a box-and-pointer diagram showing all cons pairs," like in the lecture slides.)
Nullifying Null
A list is either the special value null (which represents the empty list), or a pair whose second element is a list.Scheme provides many useful procedures for manipulating lists. The ones we use in this assignment include:
- (list Expression^{*}) — evaluates to a list containing the values of all the operand expressions. Evaluating (list 1 2 3 4) is equivalent to (cons 1 (cons 2 (cons 3 (cons 4 null)))).
- (null? Expression) — evaluates to #t if and only if the operand evaluates to null
- (list? Expression) — evaluates to #t if and only if the operand evaluates to a list.
- (length Expression) — evaluates to the number of elements in the value the operand evaluates to. Produces an error if the operand does not evaluate to a list. Note that null is a list of length 0.
- (append Expression_{1} Expression_{2}) — evaluates to a list containing the elements of the list Expression_{1} evaluates to followed by the elements of the list Expression_{2} evaluates to. Produces an error if either operand does not evaluate to a list.
- (map Expression_{1} Expression_{2}) — evaluates to a list that contains elements that result from applying the procedure Expression_{1} evaluates to, to each elements in the list Expression_{2} evaluates to. Produces an error if Expression_{1} does not evaluate to a procedure or Expression_{2} does not evaluate to a list.
- (sort Expression_{1} Expression_{2}) — evaluates to a list that contains the elements that the list Expression_{1} evaluates to, but reordered according to the comparison procedure Expression_{2} evaluates to. For sort to make sense, Expression_{2} must evaluate to a transitive comparison procedure. That is, if (Expression_{2} x y) evaluates to true and (Expression_{2} y z) evaluates to true, then (Expression_{2} x z) must also evaluate to true. Then, the sorted list will have the least element (according to Expression_{2}) at the front. (Note that sort takes its parameters in the opposite order of map: the first parameter to map is the procedure, the first parameter to sort is the list.)
Consider the following Scheme fragments. Assume the following definition
for intsto3 is evaluated before each expression below is
evaluated:
(define intsto3 (list 1 2 3))
- (list? (car intsto3))
- (list? (cdr intsto3))
- (length (car intsto3))
- (length (cdr (cdr (cdr intsto3))))
- (length (append intsto3 intsto3))
- (length (append intsto3 4))
- (length (append intsto3 null))
- (map (lambda (x) x) intsto3)
- (car (map (lambda (x) (> x 2)) (map (lambda (x) (+ x 3)) intsto3)))
- (length (apply append (map (lambda (x) (list x (+ 1 x) (+ 2
x))) intsto3)))
The procedure (apply Expression_{1} Expression_{2}) expects the first operand to evaluate to a procedure and the second operand to evaluate to a list. It evaluates to the value Expression_{1} would evaluate to on operands that are the elements of the list Expression_{2} evaluates to. For example, (apply + (list 1 2 3)) means the same thing as (+ 1 2 3).
- (car (sort intsto3 >))
- Explain why the fragment is not a valid Scheme expression; or,
- Predict what value the expression will evaluate to. If the expression evaluates to a compound data structure, draw a box-and-pointer picture showing the structure (for example, see Figure 2.3 in SICP).
Your answers do not have to be correct to receive full credit, but you must clearly explain your reasoning.
- Indicate the correct answer and what you misunderstood. If the expression evaluates to a compound data structure, draw a picture showing that structure.
If you address all fragments in Question 1 and Question 2, and for each fragment you either predicted the correct answer (in Question 1 or Question 2) or explained the correct answer (in Question 3) you will receive full credit for Questions 1- 3.
This file contains:
- ps2.ss - A template for your answers. You should do the problem set by editing this file.
- poker.ss - Provided code for this problem set. You should examine, but not modify, this file.
Representing Cards
To represent a card we need to keep track of both its rank (2 through Ace) and its suit (Hearts, Diamonds, Clubs, or Spades). We can do this using a cons cell: (these definitions are in poker.ss(define (make-card rank suit) (cons rank suit)) (define card-rank car) (define card-suit cdr)We use the numbers 2 through 10 to represent the normal card ranks, and 11 (Jack), 12 (Queen), 13 (King), and 14 (Ace) to represent the special cards. The definitions in poker.ss allow us to use the names Ace, King, Queen, and Jack for these ranks.
If your higher-card? procedure is correct, you should get the following interactions:
> (higher-card? (make-card Ace Diamonds) (make-card King Spades))
#t
> (higher-card? (make-card 3 Clubs) (make-card 2 Clubs))
#t
> (higher-card? (make-card Ace Diamonds) (make-card Ace Spades))
#f
Sorting Hands
In order to evaluate a hand, it will be useful to sort the hand according to the card values.
No, really. Go read poker.ss.
If your sort-hand procedure is correct, you should get the following interactions (the display-cards procedure provided in poker.ss makes it easier to see the cards; the sample hands are also defined in poker.ss):
Hint: you should not need more than one line for your definition.> (display-cards (sort-hand royal-flush))
"Ah Kh Qh Jh 10h"
> (display-cards (sort-hand ace-higher))
"Ad 10s 8c 7c 3s"
Since the rankings of poker hands don't just depend on the card values, but on having pairs, triples, and quads of a given card, it will be more useful to sort the cards according to first the number of duplicates of each rank, and then by rank. For example, if the hand is Ac Js Jc 7d 4c the procedure sort-by-ranks should produce ((Js Jc) (Ac) (7d) (4c)) since the pair of Jacks are more important than the single A. Note that instead of being just a list of cards, the result is now a list of lists of cards.
The procedure sort-by-ranks is defined:
(define (sort-by-ranks cards) ;;; sorts cards into lists of cards of each rank, ordered by most ;;; cards and highest cards within group (sort (combine-adjacent-matches ;; combine them into lists of matching rank same-rank? (sort-hand cards)) ;; cards sorted by rank (lambda (r1 r2) (if (= (length r1) (length r2)) (higher-card? (car r1) (car r2)) (> (length r1) (length r2)))))
Ranking Hands
Mark Twain
- It is in a better category of hands (e.g., a flush beats a straight)
- It is in the same category of hands, but with higher cards
Category | Description | Example |
---|---|---|
Straight Flush | Five cards in sequence all of the same suit | Ks Qs Js 10s 9s |
Four-of-a-Kind ("Quads") | Four cards of the same rank | 3h 3d 3c 3s Jd |
Full House | Three cards of matching rank and two different cards of matching rank | Ac As Ah 7d 7h |
Flush | Five cards of the same suit | Qh 10h 8h 3h 2h |
Straight | Five cards in sequence | 9d 8h 7c 6h 5s |
Wheel Straight | Ace-2-3-4-5 straight | 5d 4h 3c 2h As |
Three-of-a-Kind ("Trips") | Three cards of matching rank | 5d 5h 5c Kh Js |
Two Pair | Two different pairs of matching rank | Jd Jh 5c 5h As |
One Pair | Two cards of matching rank | 8d 8h Ac 7h 3s |
High Card | Anything else | Kd 9h 7c 5h 2s |
(Note: we've listed wheel straight as a separate hand category, even though it is usually listed just as a straight. It is the only straight that can use A as a low card, and the lowest possible straight.)
We have provided the higher-hand? procedure that defines the poker rules:
(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))))) ((wheel-straight? hand1) (not (or (any-straight? hand2) (beats-straight? hand2)))) ((three-of-a-kind? hand1) (and (not (beats-trips? hand2)) (or (and (three-of-a-kind? hand2) (higher-similar-hand? hand1 hand2)) (not (three-of-a-kind? hand2))))) ((three-of-a-kind? hand1) (and (not (beats-trips? hand2)) (or (and (three-of-a-kind? hand2) (higher-similar-hand? hand1 hand2)) (not (three-of-a-kind? hand2))))) ((two-pair? hand1) (and (not (beats-two-pair? hand2)) (or (and (two-pair? hand2) (higher-similar-hand? hand1 hand2)) (not (two-pair? hand2))))) ((one-pair? hand1) (and (not (beats-pair? hand2)) (or (and (one-pair? hand2) (higher-similar-hand? hand1 hand2)) (not (one-pair? hand2))))) (#t (and (not (beats-high-card? hand2)) (higher-similar-hand? hand1 hand2)))))Your job is to define the higher-similar-hand? procedure it uses to compare two hands in the same category.
The rules for comparing poker hands of the same category specify that the most important part of the hand should be compared first. The most important part is the highest card with the highest number of duplicates. If the most important parts are equal, than the next most important part of the hand determines the higher hand. Note that the sort-by-ranks procedure we defined sorts the cards in a hand according to importance, so you can determine the higher hand by considering each element of the list produced by sort-by-ranks in order until you find one that is unequal.
Here are a few examples:
- Jenny has Ad Js Jc 3h 3d. Mark has Ks Js Jc 4h 4d. Mark has the higher hand. Both hands are in the category two pair. The most important part of the hand is the higher of the two pairs. Both Jenny and Mark have Jacks. The next most important part of the hand is the lower of the two pairs. Mark has fours, which beat Jenny's threes. The unpaired card doesn't matter, since the lower pair is more important than a single card.
- Anne has Ac Ad As 4s 4c. Dave has Ac Ad 4d 4s 4c. Anne has the higher hand. Both hands are in the category full house. The most important part of the hand is the three-of-a-kind. Anne's Aces beat Dave's fours.
- Greg has Ac Ks 5d 3s 2h. Erin has Ad Ks 5d 4c 2h. Erin has the higher hand. Both players have no pairs or special hands, so the high card wins. The highest card is most important. Both have Aces. The next highest card is next most important, but again they both have Kings. Next, we compare the fives, which again match. The fourth highest card is next most important. Erin's four beats Greg's three, so Erin has the higher hand.
- Alyssa has Ac Kc Qc Jc 10c. Ben has Ad Kd Qd Jd 10d. Neither player has a higher hand. Both players have straight flushes with the highest card an Ace. The hands are equal.
If your procedure is correct, you should get the following interactions:
> (higher-hand? pair-jacks pair-kings)
#f
> (higher-hand? pair-kings pair-jacks)
#t
> (higher-hand? queens-up queens-up)
#f
> (higher-hand? ace-high ace-higher)
#f
> (higher-hand? ace-higher ace-high)
#t
> (higher-hand? kings-full-of-aces kings-full-of-jacks)
#t
Finding the Monster
To find the best possible hand, we will need to consider all possibilities and use the higher-hand? procedure to identify the best hand among them. There are five community cards and two hole cards, so a player can make a hand by using both hole cards and choosing any three of the community cards, by choosing one of the hole cards and any four of the community cards, or by just using the five community cards.To find possible hands, you will find this procedure (defined in poker.ss) useful:
(define (choose-n n lst) ;; parameters: a number n and a list (of at least n elements) ;; result: evaluates to a list of all possible was of choosing n elements from lst (if (= n 0) (list null) (if (= (length lst) n) (list lst) ; must use all elements (append (choose-n n (cdr lst)) ;; all possibilities not using the first element (map (lambda (clst) (cons (car lst) clst)) (choose-n (- n 1) ;;; all possibilities using the first element (cdr lst)))))))
Note that your possible-hands procedure doesn't depend on the elements of the operands being cards. You may find it easier to test by using scalar values instead. For example, (possible-hands (list 1 2) (list 'a 'b 'c 'd 'e)) should evaluate to a list containing these elements (in any order):
((a b c d e) (1 b c d e) (1 a c d e) (1 a b d e) (1 a b c e) (1 a b c d) (2 b c d e) (2 a c d e) (2 a b d e) (2 a b c e) (2 a b c d) (1 2 c d e) (1 2 b d e) (1 2 b c e) (1 2 b c d) (1 2 a d e) (1 2 a c e) (1 2 a c d) (1 2 a b e) (1 2 a b d) (1 2 a b c))
Now that we have a list of all possible hands, we can find the best hand using the higher-hand? procedure.
If your procedure is correct, you should get the following interactions:
For the first hand, both hole cards are used with the three nines to make a full house. For the second hand, the Ace of clubs hole card is used with the four club community cards to make a flush. For the third hand, no hole cards are used and the five community cards make a straight flush.> (display-cards (find-best-hand aces-in-hole trip-nines))
"9d 9c 9s Ah Ad"
> (display-cards (find-best-hand big-slick community-clubs5))
"Ac Qc Jc 7c 5c"
> (display-cards (find-best-hand big-slick royal-flush))
"Ah Kh Qh Jh 10h"
Hint: as in Question 5, you should be able to define this using only one line. Don't worry about efficiency in your definition (for now).
After the Turn
After the fourth community card (known as the turn or fourth street) has been dealt, there is one more community card to come (known as the river or fifth street). To make good decisions, a player needs to know the likelihood that she will have the winning hand after the final card is dealt, but doesn't know what the final card will be.For simplicity, we will assume the player is playing against only one opponent, and has good enough card-reading skills to know the other player's exact hand. (Of course, no real poker player is that good, but in many cases players do have a reasonable guess what cards the other players are holding.)
To analyze a hand, we determine how many of the possible final cards would allow the player to win or draw. The analyze-turn-situation procedure is defined below (and in poker.ss):
(define (accumulate-outs lst) ; lst is a list of triples representingThe analyze-turn-situation procedure determines the cards left in the deck by removing the known hole cards and community cards as current-deck. Then, it uses map to try each possible final card from the current deck. If the final card would allow player 1 to produce a better hand than player 2, it puts that card as the first element in the list; if the hands would be equal, it puts that card as the second element; if player 2 would win, it puts that card as the third element. The accumulate-outs procedure combines all the sublists to form a list of all the winning and chopping outs.cards (if (null? lst) (list null null null) (let ((rest-outs (accumulate-outs (cdr lst)))) (list (append (car (car lst)) (car rest-outs)) (append (car (cdr (car lst))) (car (cdr rest-outs))) (append (car (cdr (cdr (car lst)))) (car (cdr (cdr rest-outs)))))))) (define (analyze-turn-situation hole1 hole2 community) ;; remove all known cards from the deck (let ((current-deck (remove-cards (append hole1 hole2 community) full-deck))) ;; we want to find out how many of the remaining cards produce each result (accumulate-outs (map (lambda (final-card) (let ((outcome (compare-hands? (find-best-hand hole1 (cons final-card community)) (find-best-hand hole2 (cons final-card community))))) (if (eq? outcome 'higher) (list (list final-card) null null) (if (eq? outcome 'equal) (list null (list final-card) null) ; chop (list null null (list final-card)))))) current-deck))))
Here's an example:
To consider the situation after the flop (the first three community cards have been dealt), we need to look at all possibilities for both the fourth and fifth card. The analyze-flop-situation does this:> (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 three-clubs))
(define (analyze-flop-situation hole1 hole2 community) ;; operands: hole cards for player 1 and play 2 and community cards ;; there must be 2 cards in each players hole cards and 3 community cards ;; result: a list of three elements (winning-outs, chopping-outs, loser) showing ;; the turn and river cards that will lead for the each outcome for player 1. (let ((current-deck (remove-cards (append hole1 hole2 community) full-deck))) ;; we want to find out how many of the remaining cards produce each result (map (lambda (turn-card) (analyze-turn-situation hole1 hole2 (cons turn-card community))) current-deck)))The show-flop-analysis procedure displays a flop analysis in a (barely) human-readable way.
(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.
Hint 1: Call and example display-analysis and display-flop-analysis to get a better idea of what is going on.
Hint 2: Phrase your answer in generic terms such as "If analyze-turn-situation takes X seconds, analyze-flop-sitatuion will take ...".
(define staff-comments "Weimer wouldn't know a cunning plan if it painted itself purple and danced on top of a mandolin singing 'cunning plans are here again'. The TAs, on the other hand, are pondering exactly what I'm pondering.)
More seriously, we would appreciate both positive and negative comments about your experience so far. Bonus points if you refer to specific people by name. We will not think less of you (or grade you more harshly later on) for negative comments. Actually, we prefer negative comments and constructive criticism: they tell us how to improve. When everyone has turned in the problem set, we look at all of the comments at the same time after stripping away your names.
If you are working with a partner, make a longer comment that addresses all of your concerns.
In any event, you will receive full credit for any comment longer than 20 characters.
We embrace this vision because:
- We wish to be leaders and role models in reaping and sharing the benefits of diversity.
- We seek to enhance the intellectual and creative environment of our department.
- We expect to produce happier, more capable and more broadly educated computer science graduates.
Unfortunately, we're totally unable to do this without your help. We need to be able to tell what we're doing wrong, and to measure the effectiveness of plans we put into place. To that end, you should fill out the Computer Science department Diversity survey. It's anonymous and only about 12 questions long (it's shorter than the PS1 survey). Your answers will actually help make the world a better place — how often can you say that?
Fine print: Because the survey is anonymous, I have no way of checking to see if you did it. Thus, you get full credit for it whether you do it or not. Please do it.
Extra Credit: Making $30 an Hour
Poker-playing robots are already a reality -- but so is on-line fraud. Read Gilbert Gaul's Players Gamble on Honesty, Security of Internet Betting from The Washington Post (Sunday, November 30, 2008). Cogently explain how you would use the techniques in this problem set to detect when a player is cheating. Explain whether or not your approach would likely be successful, how long it would take, and what results might ensue if it were wrong.Read the description of the Loki poker-playing algorithm in Using Probabilistic Knowledge and Simulation to Player Poker by Darse Billings, Lourdes Pena, Jonathan Schaeffer, Duane Szafron in AAAI 1999. Explain how Loki-1 works. For each element of Figure 1, indicate which part of this problem set it corresponds to (if any). Compare and contrast the techniques they use to what you saw in this problem set. What are the key areas in which Loki holds an advantage? Re-read the paragraph at the bottom of Page 6 that starts with "The metric used to measure". How much money would Loki earn if it played continuously for a year? How would you detect a robotic player like Loki? Be specific.
You may do the extra credit alone or with your partner, but all participating partners must read both documents. Append your extra-credit writeup (which should address the questions above and be at most one typed page) to your stapled turn-in for the other written questions. It is due at the same time.
and tested and improved by Dan Upton and Westley Weimer.
cs150: Computer Science
from Ada and Euclid to Quantum Computing and the World Wide Web
Instructor
Westley Weimer
Teaching Assistants
Zak Fry
Paul DiOrio
Rachel Lathbury
Email Address
cs150-staff@cs.virginia.edu
Mondays and Wednesdays, 3:30-4:45pm in MEC 341
Wednesdays, 7:00-8:00pm and 8:00-9:00pm in OLS 001
(Small Hall Lab)
Monday 5:00-6:00 (Zak)
Tuesday 3:15-4:15 (Rachel)
Thursday 5:00-6:00 (Paul)
Sunday 3:00-4:00 (on request)
(Small Hall Lab)
Monday 2:00-3:00 (Rachel)
Tuesday 11:00-12:00 (Wes in Olsson 219)
Tuesday 3:00-4:00 (Zak)
Wednesday 1:00-2:00 (Paul)