Prologgin'

Monday, December 14, 2009 :: Tagged under: pablolife engineering plt. ⏰ 5 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 straight-up write-it-out 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 hard-code 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 5-tuple 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:

This should be enough (coming at you very fast!) to give you a flavor for how the program worked. Here is the top-level 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:

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.


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:

* = 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 SWI-Prolog 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([H1|T1], [H2|T2], 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([H|T], Sorted) :-
  filter_by_high_card(H,T,Lower,Higher),
  sort_hand(Lower,SortedLower),
  sort_hand(Higher,SortedHigher),
  append(SortedLower, [H|SortedHigher], Sorted).


filter_by_high_card(_, [], [], []).
filter_by_high_card(Pivot, [H|T], [H|Lower], Higher) :-
  beats(Pivot,H,Z),
  (Z = Pivot ; Z = tie),
  filter_by_high_card(Pivot, T, Lower, Higher).
filter_by_high_card(Pivot, [H|T], Lower, [H|Higher]) :-
  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 😄