I just got started on Macros chapter in ANSI Common Lisp:
I'm trying to make an evaluator for a poker hand, given a list of
strings for cards:
> (setf hand '("2H" "AC" "TS" "TC" "5D"))
I thought this would be the best way to easily compare multiple hands
in a showdown:
> (rate-hand hand)
#13r188c30
> (when (> (rate-hand hand1) (rate-hand hand2))
(wins-pot hand1))
The code below works but it seems really long for a lisp program. What
would be the more idiomatic way to tackle hand-evaluation? I want to
be able to handle cases like '("AC" "TS" "8C" "4D" "2D") vs. '("AD"
"TC" 8H" "4S" "3D"), where hand2 wins because of the 3D over hand1's
2D.
Thank you for your help in advance.
- - -
(defparameter straight "AKQJT98765432A")
(defparameter card-value
'((#\2 . #13r0)
(#\3 . #13r1)
(#\4 . #13r2)
(#\5 . #13r3)
(#\6 . #13r4)
(#\7 . #13r5)
(#\8 . #13r6)
(#\9 . #13r7)
(#\T . #13r8)
(#\J . #13r9)
(#\Q . #13ra)
(#\K . #13rb)
(#\A . #13rc)
(#\C . #13r10)
(#\D . #13r20)
(#\H . #13r30)
(#\S . #13r40)))
(defun rate-hand (hand)
(eval-hand (sort-hand hand)))
(defun sort-hand (hand)
(let ((values (mapcar #'(lambda (c) (aref c 0)) hand)))
(sort hand #'(lambda (a b) (card> a b values)))))
(defun card> (a b values)
(cond ((= (count (aref a 0) values)
(count (aref b 0) values))
(> (cdr (assoc (aref a 0) card-value))
(cdr (assoc (aref b 0) card-value))))
(t
(> (count (aref a 0) values)
(count (aref b 0) values)))))
(defun eval-hand (hand)
(let ((values (mapcar #'(lambda (c)
(cdr (assoc (aref c 0) card-value))) hand))
(rank (cond ((royal-flush-p hand) 9)
((straight-flush-p hand) 8)
((four-of-a-kind-p hand) 7)
((full-house-p hand) 6)
((flush-p hand) 5)
((straight-p hand) 4)
((three-of-a-kind-p hand) 3)
((two-pairs-p hand) 2)
((one-pair-p hand) 1)
(t 0))))
(reduce #'(lambda (a b)
(+ (* 13 a) b)) values :initial-value rank)))
(defun pairs-p (hand n pos)
(let ((values (mapcar #'(lambda (c) (aref c 0)) hand)))
(= n (count (nth pos values) values))))
(defun royal-flush-p (hand)
(and (straight-p hand) (flush-p hand) (char= #\A (aref (car hand)
0))))
(defun straight-flush-p (hand)
(and (straight-p hand) (flush-p hand)))
(defun four-of-a-kind-p (hand)
(pairs-p hand 4 0))
(defun full-house-p (hand)
(and (pairs-p hand 3 0) (pairs-p hand 2 3)))
(defun straight-p (hand)
(let ((values (mapcar #'(lambda (c) (string (aref c 0))) hand)))
(search (reduce #'(lambda (a b) (concatenate 'string a b)) values)
straight)))
(defun flush-p (hand)
(let ((suits (mapcar #'(lambda (c) (aref c 1)) hand)))
(apply #'char= suits)))
(defun three-of-a-kind-p (hand)
(pairs-p hand 3 0))
(defun two-pairs-p (hand)
(and (pairs-p hand 2 0) (pairs-p hand 2 2)))
(defun one-pair-p (hand)
(pairs-p hand 2 0))
·······@gmail.com writes:
> I just got started on Macros chapter in ANSI Common Lisp:
>
> I'm trying to make an evaluator for a poker hand, given a list of
> strings for cards:
> > (setf hand '("2H" "AC" "TS" "TC" "5D"))
My first idomatic lisp suggestion is to not use strings for defining the
cards but instead use a more lisp-ish representation. (Of course, it may
be that the card representation is given as part of the problem.)
'((2 :hearts) (:ace :clubs) (10 :spades) (10 :clubs) (5 :diamonds))
possibly substituting 11, 12, 13, 14 for :jack, :queen, :king, :ace,
although it is trivial to write a card-value function:
(defun card-value (card)
(let ((rank (first card)))
(typecase rank
(integer rank)
(symbol
(ecase rank
(:jack 11)
(:queen 12)
(:king 13)
(:ace 14))))))
If you want to have string input, I would first of all parse that into
the lisp-like representation and then do the manipulations using the
symbolic and numeric comparisons needed. If you nicely separate the
representation into rank and suit, then you can write the flush-p like
(defun flush-p (hand)
(let ((suit (second (first hand))))
(every #'(lambda (card) (eq suit (second card)))
(rest hand))))
or maybe even like
(defun flush-p (hand)
(null (remove (second (first hand)) hand :key #'second)))
Also, since this is a chapter on macros, you might want to write very
simple accessor macros for getting the card rand and suit.
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas, thanks for your reply. I like your suggestions for (flush-p)
and I appreciate the encouragement to use macros.
Now I apologize because I might not be understanding you exactly
because of my inexperience:
why is it more idiomatic to use integers instead of strings to
represent cards?
Thomas A. Russ wrote:
> My first idomatic lisp suggestion is to not use strings for defining the
> cards but instead use a more lisp-ish representation. (Of course, it may
> be that the card representation is given as part of the problem.)
>
> '((2 :hearts) (:ace :clubs) (10 :spades) (10 :clubs) (5 :diamonds))
>
> possibly substituting 11, 12, 13, 14 for :jack, :queen, :king, :ace,
> although it is trivial to write a card-value function:
>
> (defun card-value (card)
> (let ((rank (first card)))
> (typecase rank
> (integer rank)
> (symbol
> (ecase rank
> (:jack 11)
> (:queen 12)
> (:king 13)
> (:ace 14))))))
>
> If you want to have string input, I would first of all parse that into
> the lisp-like representation and then do the manipulations using the
> symbolic and numeric comparisons needed. If you nicely separate the
> representation into rank and suit, then you can write the flush-p like
>
> (defun flush-p (hand)
> (let ((suit (second (first hand))))
> (every #'(lambda (card) (eq suit (second card)))
> (rest hand))))
>
> or maybe even like
>
> (defun flush-p (hand)
> (null (remove (second (first hand)) hand :key #'second)))
>
> Also, since this is a chapter on macros, you might want to write very
> simple accessor macros for getting the card rand and suit.
·······@gmail.com writes:
> why is it more idiomatic to use integers instead of strings to
> represent cards?
It's more practical. It's easier to write 2 or 3 than #\2 or #\3
(And I find (2 :diamond) more readable than "2D").
Anyways, it shouldn't matter much, because anyway, you use the
abstraction layer, the function: (card-suit c) (card-val c), etc. If
card-val returns directly an integer instead of a character, it'll be
easier to use it to index vectors, etc.
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
Pascal, thank you for that answer. It was helpful.
Pascal Bourguignon wrote:
> ·······@gmail.com writes:
> > why is it more idiomatic to use integers instead of strings to
> > represent cards?
>
> It's more practical. It's easier to write 2 or 3 than #\2 or #\3
> (And I find (2 :diamond) more readable than "2D").
>
> Anyways, it shouldn't matter much, because anyway, you use the
> abstraction layer, the function: (card-suit c) (card-val c), etc. If
> card-val returns directly an integer instead of a character, it'll be
> easier to use it to index vectors, etc.
·······@gmail.com writes:
> Thomas, thanks for your reply. I like your suggestions for (flush-p)
> and I appreciate the encouragement to use macros.
>
> Now I apologize because I might not be understanding you exactly
> because of my inexperience:
>
> why is it more idiomatic to use integers instead of strings to
> represent cards?
Actually, my claim is that using a structured approach such as
(2 :diamonds) is more idiomatic than "2D"
One could also go directly into structures (with DEFSTRUCT) but with
such a simple representation, a short LIST seems adequate.
The reason this is more idiomatic is because it eliminates the continual
step of needing to do string manipulation and interpretation in order to
compare ranks and suits. The ranks are directly represented by the
integers, providing a sorted order. The suits are symbols, which is one
of the staples of lisp programming, especially for representing symbolic
objects (like card suits).
Using symbols lets you use a whole host of symbol-based routines, such
as EQ for comparison, CASE for dispatching, etc. It also gives you a
place to put things like a relative suit weighting, none of which you
get with characters without creating your own mapping tables. (On
symbols you can use the property list or plist for such simple
associations. Or you could use association lists alists.)
Lisp does quite well when dealing with list structures so using symbols
and lists plays to Lisp strengths. String manipulation is possible, but
I figure it isn't worth the effort and doesn't really gain you much,
except for a more compact external representation. If that is
important, I would handle it as an input/output transformation rather
than force the guts of the algorithm to use an inconvenient representation.
--
Thomas A. Russ, USC/Information Sciences Institute
·······@gmail.com wrote:
> I just got started on Macros chapter in ANSI Common Lisp:
>
> I'm trying to make an evaluator for a poker hand, given a list of
> strings for cards:
> > (setf hand '("2H" "AC" "TS" "TC" "5D"))
>
> I thought this would be the best way to easily compare multiple hands
> in a showdown:
> > (rate-hand hand)
> #13r188c30
> > (when (> (rate-hand hand1) (rate-hand hand2))
> (wins-pot hand1))
>
> The code below works but it seems really long for a lisp program. What
> would be the more idiomatic way to tackle hand-evaluation? I want to
> be able to handle cases like '("AC" "TS" "8C" "4D" "2D") vs. '("AD"
> "TC" 8H" "4S" "3D"), where hand2 wins because of the 3D over hand1's
> 2D.
>
> Thank you for your help in advance.
[I misread your post. For some reason I thought you said it takes a
"long time" to execute, so I did a quick profile; and Google was giving
me problems so it submitted a couple times. Argh.]
First off, you'll want to rename these vars:
(defparameter straight ...
(defparameter card-value ...
to:
(defparameter *straight* ...
(defparameter *card-value* ...
That's the idiomatic Lisp naming convention.
Also, helper functions like the following are clearer, modulo Pascal
B.'s comments:
(defun card-suit (card) (aref card 1))
(defun card-val (card) (aref card 0))
(defun card-code (card)
(cdr (assoc (card-val card) *card-value*)))
Tayssir
·······@gmail.com writes:
> Thank you Pascal and Tayssir for helpful suggestions.
> I think the code looks much easier to read from your suggestions.
>
> - - -
>
> (defparameter *straight* "AKQJT98765432A5432")
> (defparameter *card-value* "23456789TJQKA")
> (defparameter *card-suit* "CDHS")
>
> (defun rate-hand (hand)
> (eval-hand (sort-hand hand)))
>
> (defun sort-hand (hand)
> (let ((values (mapcar #'(lambda (c) (card-val c)) hand)))
> (sort hand #'(lambda (a b) (card> a b values)))))
Once you have defined an accessor function, card-val, you
can pass it directly, ie
(defun sort-hand (hand)
(let ((values (mapcar #'card-val hand)))
(sort hand #'(lambda (a b) (card> a b values)))))
I found the next bit of code baffling.
>
> (defun card> (a b values)
> (cond ((= (count (card-val a) values)
> (count (card-val b) values))
> (> (card-code a)
> (card-code b)))
> (t (> (count (card-val a) values)
> (count (card-val b) values)))))
With a name like card> I'm expecting it to compare cards,
something like
(defmethod higher ((a card)(b card))
(or (stronger-suit a b)
(and (same-suit a b)
(higher-figure a b))))
There as a strong tradition in computer science education of
forcing students to write trivial comments, and overcomment
their code, until they join secret societies and swear blood
oaths to refrain from writing comments for the rest of their
lives.
However, you have a cunning plan. Sort-hand will group cards
of the same value, and place longer groups ahead of higher values.
With this cannonical form, all the predicates you need such
as three-of-of-kind-p, know where to look, and can thus pass
specific positions and counts to the somewhat opaque
pairs-p.
A comment, giving away the gist of the plan, allows your
audience to read your code to see how it implements the
plan. This is much easier than reading the code blind in the
hope of being able to reverse engineer the plan.
It looks to me as though card> doesn't have much prospect of
leading an independent life away from sort-hand. If you put
it inside using flet it can access the values as part of the
surrounding lexical environment, which gets rid of the
lambda expression. You end up with something like (not
tested):
(defun sort-hand (hand)
(let ((values (mapcar #'(lambda (c) (card-val c)) hand)))
(flet ((card> (a b)
(if (= (count (card-val a) values)
(count (card-val b) values))
(> (card-code a)
(card-code b))
(> (count (card-val a) values)
(count (card-val b) values)))))
(sort hand #'card>))))
I have my doubts about the plan. It is treating the cards in
the computer much as you would treat physical cards in real
life, arranging them in your hand then looking at them. This code
> (defun four-of-a-kind-p (hand)
> (pairs-p hand 4 0))
> (defun full-house-p (hand)
> (and (pairs-p hand 3 0) (pairs-p hand 2 3)))
> (defun two-pairs-p (hand)
> (and (pairs-p hand 2 0) (pairs-p hand 2 2)))
> (defun one-pair-p (hand)
> (pairs-p hand 2 0))
is clever, but feels somehow oblique. It is very hard to
come up with a form of words that says what pairs-p actually
does, even harder to come up with a good name for it.
The basic idea is that a full house is 3,2 and two pairs
2,2,1 while one pair is 2,1,1,1 and three and four of a kind
are 3,1,1 and 4,1.
Let us call these "grouping signatures". Can we write a
hairy function that just gets stuck in and computes them?
This seems to do it
(defun grouping-signature (hand)
(sort (mapcar #'cdr ;discard the card identities
;once the duplicates are gone
(remove-duplicates
;; convert (a a a b b) into
;; ((a . 3)(a . 2)(a . 1)(b . 2)(b . 1))
(maplist
(lambda(cards)
(cons (card-val (car cards))
(count (card-val (car cards))
cards
:key #'card-val)))
hand)
:key #'car
:from-end t))
#'>))
The grouping signatures don't work quite as smoothly as one
would hope because CL's built-in case statement uses eql, so
will not match grouping signatures. I find it attractive to
write a macro to fix this
(defmacro equal-case (form &body clauses)
(let ((value-holder (gensym "value")))
`(let ((,value-holder ,form))
(cond ,@(loop for clause in clauses
collect `((equal ,value-holder ',(car clause))
,@(cdr clause)))))))
Then one gets to write code such as
CL-USER> (equal-case (grouping-signature (print (deal-hand)))
((2 1 1 1) 'pair)
((2 2 1) 'two-pair)
((3 1 1) 'three-of-a-kind)
((3 2) 'full-house)
((4 1) 'four-of-a-kind))
(3 of DIAMONDS. 2 of DIAMONDS. 4 of DIAMONDS. 4 of SPADES. KING of DIAMONDS.)
=>PAIR
and repeating it at the REPL
(2 of HEARTS. QUEEN of CLUBS. 5 of DIAMONDS. QUEEN of HEARTS. 5 of HEARTS.)
=> TWO-PAIR
One of the obstacles to writing good code in CL is that it
is lots of fun and that creates a temptation to
self-indulgence. I'm writing `grouping-signature' and I say
to myself: I get to use maplist, my favourite mapping
function, purrrrr :-) There might be much clearer ways to
write the code.
Alan Crowe
Edinburgh
Scotland
Alan, I appreciate your taking time to help a beginner. I see your
point about letting lisp parse the hand structure itself by using
(grouping-signature); it is far more elegant (and shorter).
Unfortunately, I'm having difficulty wrapping my head around how I
would be able to determine the hand winner(s) in split-pot and/or
side-pot[1] situations using (grouping-signature).
[1] http://www.gamesandcasino.com/poker-dictionary.htm#s
If this requirement was not clear, then this is yet another good reason
for me to describe my goals more exactly in the OP, as well as for
better commenting. Sorry, and I'll try to do better in the future.
As you identified, I tried to be clever by generating a hand-score of
the sorted hand; this allows for relatively simple comparison of scores
to find multiple levels of multiple winning hands. To account for all
possibilities, I must incorporate all 5 cards in a hand, or I would not
be able to determine the winner in the below situation:
PeateyK wrote on Feb 8 2006:>
> I want to be able to handle cases like
> (AC TS 8C 4D 2D) vs. (AD TC 8H 4S 3D),
> where hand2 wins because of its 3D over hand1's 2D.
Alan Crowe wrote:>
> I have my doubts about the plan. It is treating the cards in
> the computer much as you would treat physical cards in real
> life, arranging them in your hand then looking at them. This code
>
> > (defun four-of-a-kind-p (hand)
> > (pairs-p hand 4 0))
> > (defun full-house-p (hand)
> > (and (pairs-p hand 3 0) (pairs-p hand 2 3)))
> > (defun two-pairs-p (hand)
> > (and (pairs-p hand 2 0) (pairs-p hand 2 2)))
> > (defun one-pair-p (hand)
> > (pairs-p hand 2 0))
>
> is clever, but feels somehow oblique. It is very hard to
> come up with a form of words that says what pairs-p actually
> does, even harder to come up with a good name for it.
>
> The basic idea is that a full house is 3,2 and two pairs
> 2,2,1 while one pair is 2,1,1,1 and three and four of a kind
> are 3,1,1 and 4,1.
>
> Let us call these "grouping signatures". Can we write a
> hairy function that just gets stuck in and computes them?
> This seems to do it
>
> (defun grouping-signature (hand)
> (sort (mapcar #'cdr ;discard the card identities
> ;once the duplicates are gone
> (remove-duplicates
> ;; convert (a a a b b) into
> ;; ((a . 3)(a . 2)(a . 1)(b . 2)(b . 1))
> (maplist
> (lambda(cards)
> (cons (card-val (car cards))
> (count (card-val (car cards))
> cards
> :key #'card-val)))
> hand)
> :key #'car
> :from-end t))
> #'>))
>
> The grouping signatures don't work quite as smoothly as one
> would hope because CL's built-in case statement uses eql, so
> will not match grouping signatures. I find it attractive to
> write a macro to fix this
>
> (defmacro equal-case (form &body clauses)
> (let ((value-holder (gensym "value")))
> `(let ((,value-holder ,form))
> (cond ,@(loop for clause in clauses
> collect `((equal ,value-holder ',(car clause))
> ,@(cdr clause)))))))
>
> Then one gets to write code such as
>
> CL-USER> (equal-case (grouping-signature (print (deal-hand)))
> ((2 1 1 1) 'pair)
> ((2 2 1) 'two-pair)
> ((3 1 1) 'three-of-a-kind)
> ((3 2) 'full-house)
> ((4 1) 'four-of-a-kind))
>
> (3 of DIAMONDS. 2 of DIAMONDS. 4 of DIAMONDS. 4 of SPADES. KING of DIAMONDS.)
>
> =>PAIR
>
> and repeating it at the REPL
>
> (2 of HEARTS. QUEEN of CLUBS. 5 of DIAMONDS. QUEEN of HEARTS. 5 of HEARTS.)
>
> => TWO-PAIR
>
> One of the obstacles to writing good code in CL is that it
> is lots of fun and that creates a temptation to
> self-indulgence. I'm writing `grouping-signature' and I say
> to myself: I get to use maplist, my favourite mapping
> function, purrrrr :-) There might be much clearer ways to
> write the code.
·······@gmail.com writes:
> Alan, I appreciate your taking time to help a beginner. I see your
> point about letting lisp parse the hand structure itself by using
> (grouping-signature); it is far more elegant (and shorter).
>
> Unfortunately, I'm having difficulty wrapping my head around how I
> would be able to determine the hand winner(s) in split-pot and/or
> side-pot[1] situations using (grouping-signature).
>
> [1] http://www.gamesandcasino.com/poker-dictionary.htm#s
>
> If this requirement was not clear, then this is yet another good reason
> for me to describe my goals more exactly in the OP, as well as for
> better commenting. Sorry, and I'll try to do better in the future.
>
> As you identified, I tried to be clever by generating a hand-score of
> the sorted hand; this allows for relatively simple comparison of scores
> to find multiple levels of multiple winning hands. To account for all
> possibilities, I must incorporate all 5 cards in a hand, or I would not
> be able to determine the winner in the below situation:
>
> PeateyK wrote on Feb 8 2006:>
> > I want to be able to handle cases like
> > (AC TS 8C 4D 2D) vs. (AD TC 8H 4S 3D),
> > where hand2 wins because of its 3D over hand1's 2D.
>
> Alan Crowe wrote:>
> > I have my doubts about the plan. It is treating the cards in
> > the computer much as you would treat physical cards in real
> > life, arranging them in your hand then looking at them. This code
> >
> > > (defun four-of-a-kind-p (hand)
> > > (pairs-p hand 4 0))
> > > (defun full-house-p (hand)
> > > (and (pairs-p hand 3 0) (pairs-p hand 2 3)))
> > > (defun two-pairs-p (hand)
> > > (and (pairs-p hand 2 0) (pairs-p hand 2 2)))
> > > (defun one-pair-p (hand)
> > > (pairs-p hand 2 0))
Whoops, I wasn't clear about the strategy I was advocating.
The tactical aspect is that you need predicates such as
full-house-p. Working out the grouping signature and then
doing a simple look up looks like a nice way of coding this.
Stategically you still need the exact details of the cards
in the hand. However, you do not need to confine yourself to
rearranging your data. Your can build up its analysis as it
goes along.
So you might start with
(defun score-hand (hand)
(let ((signed-hand (sign-hand hand)))
...
where
(defun sign-hand (hand)
(cons hand
(grouping-signature hand)))
Then it is very easy to write a predicate such as
full-house-p for a signed-hand, it just has to look at the
signature.
Building up your analysis in this way also helps with
debugging, you get a static audit trail in your data
objects, and can see the stage containing the bug without
needing to follow the dynamic path of program execution.
Perhaps the grouping-signature is only useful for the
pairing predicates. Then you would want
(defun score-hand (hand)
(let ((paired-hand (pair-hand hand)))
...
where
(defun pair-hand (hand)
(cons hand
(equal-case (grouping-signature hand)
((3 2) 'full-house
....
You have a tactical choice to make about whether you really
want to actually build a data object
(defun score-hand (hand)
(let ((pairing (equal-case (grouping-signature hand)
((3 2) 'full-house)
...)))
...code that can see both the hand and how it is paired.
The issue is that you want to break up your code into
bite-sized pieces that you can test separately. If you build
up your analysis in variables then you have to finish the
analysis within the scope of those variables. You might end
up with a function that is over large, or you might have to
pass several bits of incomplete analysis to helper
functions. You where doing this earlier with passing
`values' to `card>'.
The alternative is to build up your analysis in a single
data object. The trade-off is that it is easy to /pass/ all
your analysis so far to a helper function, but then, inside
the helper function the code is obscured with accessor
functions that are getting at the relevant parts of the
analysis.
My grouping-signatures code solves much less of your problem
than you hoped.
Alan Crowe
Edinburgh
Scotland