Prologgin'
Monday, December 14, 2009 :: Tagged under: pablolife engineering plt. ⏰ 9 minutes.
Hey! Thanks for reading! Just a reminder that I wrote this some years ago, and may have much more complicated feelings about this topic than I did when I wrote it. Happy to elaborate, feel free to reach out to me! 😄
Exam season is a royal pain, but I find ways to entertain myself. My most recent delight has been Project Euler: I discovered it late last semester, and took a break until about November to tackle some Facebook puzzles. But with the gaps between commitments getting smaller and smaller, and with a desire to use some more unorthodox languages (Facebook doesn't accept Scheme or SML submissions, for example), tackling 15 or so of the easier Project Euler problems proved fitting.
I recently solved Problem 54, an unusually straightforward implementation problem (most problems require some mathematical insight, this was a straightup writeitout problem). In Problem 54, they provide a file with 1000 games of poker, and you must determine how many games the first player wins.
So here I saw an opportunity: Prolog! Wouldn't it be more fun to just declare the rules of Poker and say "go," rather than hardcode every individual evaluation possibility?
For those who don't know what Prolog is, here's a quick (very, very brief) primer: Prolog is a language that attempts to satisfy truth clauses given a set of relations, and rules that govern them. So if I were to define the following relation R:
(a R b) is true if and only if a is the reverse of b.
Then we know that ("paul" R "luap") is a true statement, but ("paul" R "robert") is false.
In Prolog, you supply the language with any relations you like (such as R, above), and when you provide data to those relations it can tell you if they are true or not.
Yawn. Here's the kicker: In Prolog, you can supply variables to the relations, and the language will bind those variables to values that satisfy its truth, without having to specify exactly how to find such a value. Using the example above, if I fed Prolog
X R "cantankerous"
Prolog returns
X = "suoreknatnac"
The key to this is that I never told Prolog how to reverse a word, I simply declared that R is true when one side is the reverse of the other. This becomes more clear as I go through the poker example: when you program in Prolog, you aren't thinking "what instructions can I give a machine primarily using destructive memory updates such that I can compute my goal?" (generally what happens in imperative programs), or "what functional abstractions can I define such that one's output evaluates to my goal?" (functional programs), but rather "what is my goal?" (logical programs, of which Prolog is the most popular language).
I'll throw a little syntax in before we dive into the example. In Prolog, square brackets define a list, so[]
is an empty list,[paul, robert, annalisa]
is a list with my siblings and I, and[[galosh, wader], [souvlaki, moussaka, gyro], gawker]
is a list of two lists and "gawker."
In my poker program, each card is a list of the card's value and its suit (e.g.
[ace,spades]
or [8,diamonds]
). A list of five cards is a hand, and a list of
two hands is a game between two players.
Throwing it all together, here's are some of the rules I wrote that determine a player's hand in poker:
determine_hand([[_,X],[_,X],[_,X],[_,X],[_,X]], flush).
In English, this says: the relation determine_hand
is true if two conditions
are met. The first value is a hand of cards, for which the second value on
every pair (the suit) is the same value X. Second, the second value of
determine_hand
is the value "flush." The underscore in the place of the
values of the cards tells Prolog "we don't care what goes there," since
getting a flush is only dependent on the suits of the cards. Here is another:
determine_hand([[10,X],[jack,X],[queen,X],[king,X],[ace,X]], royal_flush).
This clause says: the relation determine_hand
is true if two things occur:
the first, its left side is a 5tuple of pairs. The values of the represented
cards must be 10, jack, queen, king, and ace; the second value (the suit) for
each card must all be the same value X. Secondly, the right side of
determine_hand
must be the value "royal_flush."
So if I then prompted Prolog with:
determine_hand([[10,clubs],[3,clubs],[8,clubs],[queen,clubs],[6,clubs]], HandType).
Prolog would search the possible values for HandType
(variables begin with
capital letters) until it found some value to make it true given the rules
I've provided above. We see that all suit values are the same ("clubs"), so
Prolog replies:*
HandType = flush.
Like any evaluator of conditional statements, the relation rules can be chained together with standard boolean operators. The following mean:
Left : Right
meansLeft
is true ifRight
is true. Commas mean logical AND.
 Semicolons mean logical OR.
 And, of course, you can group with parenthesis (AND gets higher precedence than OR).
This should be enough (coming at you very fast!) to give you a flavor for how the program worked. Here is the toplevel relation:
winner(H1, H2, Winner) : sort_hand(H1, Sorted_Hand1), sort_hand(H2, Sorted_Hand2), determine_hand(Sorted_Hand1, X1), determine_hand(Sorted_Hand2, X2), beats(X1, X2, Verdict), (Verdict = X1, Winner = H1; Verdict = X2, Winner = H2; Verdict = tie, tiebreak(X1, Sorted_Hand1, Sorted_Hand2, SortedWinner), (SortedWinner = left, Winner = H1 ; SortedWinner = right, Winner = H2)).
It goes something like this in English: The winner relation is true if the following are true, for two poker hands H1 and H2, and some value Winner:
Sorted_Hand1
is bound to the first value that makessort_hand(H1, Sorted_Hand1)
true.
In this case, it's true when a hand is sorted by ascending card value, so if
H1 = [[4,spades],[king,clubs],[9,hearts],[3,diamonds],[9,spades]].
the predicate becomes true if
SortedHand = [[3,diamonds],[4,spades],[9,spades],[9,hearts],[king,clubs]].
Which Prolog will find for us. More intuitively, SortedHand1
becomes H1
with
its cards sorted.

Do the same for the second Hand.

X1 and X2 are the values of
determine_hand
for theSorted_Hands
, and these are bound to the appropriate types of hand in poker (e.g. "two pair" and "full house"). 
beats
is true when the third value (in this case, Verdict) is the winner of the first two hands. We usually terminate here, as Prolog has enough information to complete the relation. 
If the two hands are the same, Verdict becomes "tie," and we continue with the
tiebreak
relation.
It's a pretty radical departure from more traditional ways of programming. For those interested in logic programming, there are some great chapters near the end of PLAI on the subject. Also, The Reasoned Schemer is essential, and the 'logical Scheme' they use is an interesting counterpoint to Prolog.
I firmly believe you should base your language choice on the problem you're trying to solve, and you shouldn't contort your problem to fit the language (this is why Lisp is so much fun). I don't run into too many problems where Prolog is the answer, but when I always greatly look forward to when I do ^_^
Prolog links:
 SWIProlog, a free and pretty nice implementation.
 GNU Prolog, a little harder to get started with, but worth looking into.
 99 Prolog Problems. These have since been copied many times over, but the first '99 Problems' set of this sort was by Prologgers.
 The First 10 Prolog Programming Contests. A good read for idiomatic language use, and seeing it solve all levels of problems.
* = If, given the definitions, you then passed determine_hand(X,Y)
, where x
was a royal flush, y would be bound to "flush." why? because the first
predicate we defined was successful (a royal flush is just a more specialized
flush, and prolog saw that determine_hand was true for the flush first). how
do we get around this? you can either by ordering your clauses appropriately,
or explicitly stating that one clause can only be true when the others are
false.
The complete code, which I ran on SWIProlog on a Powerbook G4:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Top Level main(Num_Wins) : open(hands, read, Fb), read(Fb, ListOfHands), play(ListOfHands, Num_Wins). play([],0). play([[Hand1,Hand2]Rst], Num_Wins) : winner(Hand1, Hand2, Winner), (Winner = Hand1, play(Rst,Remaining), Num_Wins is 1 + Remaining ; play(Rst, Num_Wins)). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Playing the game. winner(H1, H2, Winner) : sort_hand(H1, Sorted_Hand1), sort_hand(H2, Sorted_Hand2), determine_hand(Sorted_Hand1, X1), determine_hand(Sorted_Hand2, X2), beats(X1, X2, Verdict), (Verdict = X1, Winner = H1; Verdict = X2, Winner = H2; Verdict = tie, tiebreak(X1, Sorted_Hand1, Sorted_Hand2, SortedWinner), (SortedWinner = left, Winner = H1 ; SortedWinner = right, Winner = H2)). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Tiebreaks tiebreak(straight_flush, H1, H2, Winner) : higher_last_card(H1, H2, Winner). tiebreak(four_of_a_kind, H1, H2, Winner) : higher_middle_card(H1, H2, Winner). tiebreak(full_house, H1, H2, Winner) : higher_middle_card(H1, H2, Winner). tiebreak(flush, H1, H2, Winner) : tiebreak(high_card, H1, H2, Winner). tiebreak(straight, H1, H2, Winner) : higher_last_card(H1, H2, Winner). tiebreak(three_of_a_kind, H1, H2, Winner) : higher_middle_card(H1, H2, Winner). tiebreak(two_pair, H1, H2, Winner) : isolate_pairs(H1, [HighCard1,_], [LowCard1,_], Last1), isolate_pairs(H2, [HighCard2,_], [LowCard2,_], Last2), (beats_with_hand(H1, HighCard1, H2, HighCard2, Winner), Winner \= tie; beats_with_hand(H1, LowCard1, H2, LowCard2, Winner), Winner \= tie; beats_with_hand(H1, Last1, H2, Last2, Winner)). tiebreak(pair, H1, H2, Winner) : isolate_pair(H1, [PairCard1,_], Rst1), isolate_pair(H2, [PairCard2,_], Rst2), (beats_with_hand(H1, PairCard1, H2, PairCard2, Winner), Winner \= tie ; tiebreak(high_card, Rst1, Rst2, Winner)). tiebreak(high_card, H1, H2, X) : reverse(H1, RevH1), reverse(H2, RevH2), highest_card_chain(RevH1, RevH2, X). beats_with_hand(H1, C1, H2, C2, X) : beats(C1, C2, C1), X = left ; beats(C1, C2, C2), X = right ; X = tie. % Really ugly. How to better do this? isolate_pairs(Hand, High_Pair, Low_Pair, Last) : [[V1,S1],[V2,S2],[V3,S3],[V4,S4],[V5,S5]] = Hand, (V5 = V4, High_Pair = [[V4,S4],[V5,S5]], (V3 = V2, Low_Pair = [[V3,S3],[V2,S2]], Last = [V1,S1] ; V1 = V2, Low_Pair = [[V1,S1],[V2,S2]], Last = [V3,S3])) ; (Low_Pair = [[V1,S1],[V2,S2]], High_Pair = [[V3,S3],[V4,S4]], Last = [V5,S5]). isolate_pair(Hand, Pair, Rst) : [[V1,S1],[V2,S2],[V3,S3],[V4,S4],[V5,S5]] = Hand, (V1 = V2, Pair = [[V1,S1],[V2,S2]], Rst = [[V3,S3],[V4,S4],[V5,S5]] ; V2 = V3, Pair = [[V3,S3],[V2,S2]], Rst = [[V1,S1],[V4,S4],[V5,S5]] ; V4 = V3, Pair = [[V3,S3],[V4,S4]], Rst = [[V1,S1],[V2,S2],[V5,S5]] ; V4 = V5, Pair = [[V5,S5],[V4,S4]], Rst = [[V1,S1],[V2,S2],[V3,S3]]). highest_card_chain([H1T1], [H2T2], X) : beats(H1,H2,Verdict), (Verdict = H1, X = left ; Verdict = H2, X = right ; Verdict = tie, highest_card_chain(T1,T2,X)). higher_last_card(H1,H2,Winner) : H1 = [_,_,_,_,[V1,_]], H2 = [_,_,_,_,[V2,_]], beats(V1,V2,Higher), (Higher = V1, Winner = left ; Higher = V2, Winner = right). higher_middle_card(H1, H2, Winner) : H1 = [_,_,[V1,_],_,_], H2 = [_,_,[V2,_],_,_], beats(V1,V2,Higher), (Higher = V1, Winner = left; Higher = V2, Winner = right). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Hand determination determine_hand([[10,X],[jack,X],[queen,X],[king,X],[ace,X]], royal_flush). determine_hand([[A,X],[B,X],[C,X],[D,X],[E,X]], straight_flush) : successor(E,D), successor(D,C), successor(C,B), successor(B,A). determine_hand([[C,_],[A,_],[A,_],[A,_],[B,_]], four_of_a_kind) : C = A ; B = A. determine_hand([[A,_],[B,_],[C,_],[D,_],[E,_]], full_house) : A = B, D = E, (C = D ; C = B). determine_hand([[_,X],[_,X],[_,X],[_,X],[_,X]], flush). determine_hand([[A,_],[B,_],[C,_],[D,_],[E,_]], straight) : successor(E,D), successor(D,C), successor(C,B), successor(B,A). determine_hand([[A,_],[B,_],[C,_],[D,_],[E,_]], three_of_a_kind) : (A = B, B = C); (B = C, C = D); (C = D, D = E). determine_hand([[A,_],[A,_],[B,_],[B,_],[_,_]], two_pair). determine_hand([[_,_],[A,_],[A,_],[B,_],[B,_]], two_pair). determine_hand([[A,_],[A,_],[_,_],[B,_],[B,_]], two_pair). determine_hand([[A,_],[B,_],[C,_],[D,_],[E,_]], pair) : A = B; B = C; C = D; D = E. determine_hand(_,high_card). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Hand sorting (for easier pattern matching). sort_hand([], []). sort_hand([HT], Sorted) : filter_by_high_card(H,T,Lower,Higher), sort_hand(Lower,SortedLower), sort_hand(Higher,SortedHigher), append(SortedLower, [HSortedHigher], Sorted). filter_by_high_card(_, [], [], []). filter_by_high_card(Pivot, [HT], [HLower], Higher) : beats(Pivot,H,Z), (Z = Pivot ; Z = tie), filter_by_high_card(Pivot, T, Lower, Higher). filter_by_high_card(Pivot, [HT], Lower, [HHigher]) : beats(Pivot,H,H), filter_by_high_card(Pivot, T, Lower, Higher). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Card and Hand Precedence beats([V,_],[V,_],tie). beats([V1,S],[V2,_],[V1,S]) : value_greater_than(V1,V2). beats([V1,_],[V2,S],[V2,S]) : value_greater_than(V2,V1). beats(X,X,tie). beats(X,Y,X) : value_greater_than(X,Y). beats(X,Y,Y) : value_greater_than(Y,X). successor(royal_flush, straight_flush). successor(straigh_flush, four_of_a_kind). successor(four_of_a_kind, full_house). successor(full_house, flush). successor(flush, straight). successor(straight, three_of_a_kind). successor(three_of_a_kind, two_pair). successor(two_pair, pair). successor(pair, high_card). successor(ace,king). successor(king,queen). successor(queen,jack). successor(jack,10). successor(10,9). successor(9,8). successor(8,7). successor(7,6). successor(6,5). successor(5,4). successor(4,3). successor(3,2). value_greater_than(X,Y) : successor(X,P), (Y = P; value_greater_than(P,Y)).
Enjoy!
Thanks for the read! Disagreed? Violent agreement!? Feel free to drop me a line at , or leave a comment below! I'd love to hear from you 😄