Prologgin'

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 cards 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:

• left:-right means left is true if right 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 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:

1. Sorted_Hand1 is bound to the first value that makes sort_hand(H1, Sorted_Hand1) true. In this case, it's true when a hand is sorted by ascending 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 ^_^


2. Find the same value for the second Hand.


3. X1 and X2 are the values of determine_hand for the Sorted_Hands, and these are bound to the appropriate types of hand in poker (e.g. "two pair" and "full house").


4. beats is true when the third value (in this case, Verdict) is the winner of the first two hands. If the two hands are the same, Verdict becomes "tie."


5. One of three things is true: Either Verdict is X1, and Winner is H1 (the left player has a higher hand), OR Verdict is X2, and Winner is H2, OR there was a tie, in which case tiebreak becomes true if it's fourth value is the winner of two hands of the same type. (the problem guarantees there's always a clear winner, so we won't have actual tie games, such as two royal flushes).

----

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:

• SWI-Prolog, 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.