Do old ladies like Prolog?

First, an Old Lady update. I’ve implemented a small but important subset of Standard American bidding into the computer players’ AI, as seen below:

Old Lady screenshot

As can be seen from that screenshot, for bidding sequences that start with a trump bid at the 1 level, the computer player can go as far as the opener’s rebid before not knowing what to do; otherwise there’s no way East would have settled for a 1♠ contract given his utter lack of support. (I believe the correct next bid for East would have been 2 to deny a spades fit and signal extra length in hearts.) For the record, the deal was:

West: ♠AQ96 K 642 ♣AQ853
North: ♠10732 J64 3 ♣J10976
East: ♠J54 AQ10873 AK108 ♣Void
South: ♠K8 952 QJ975 ♣K42

The bidding system itself is currently specified as an XML file that describes all possible bids at each state, and the conditions that must be satisfied in order to make them. To give you an idea of what this looks like, here’s the fragment that told West to rebid 1♠:

<!-- Up-the-line at the 1 level -->
    <exists name="suit">
            <denomination-range low="open" high="closed">
        <integer value="1"/>
        <variable name="suit"/>
    <transition state="1-respond-again"/>
            <integer value="13"/>
            <integer value="18"/>
                <variable name="suit"/>
            <integer value="4"/>

In human terms, that says that if there’s a suit greater than the last suit the partner bid but no higher than spades, bid that suit at the 1 level if you have between 13 and 18 HCP and at least four cards in that suit. Specifying the bidding rules as data means that the Python code that decides what to bid and the Python code that figures out what the partner’s bid meant work together properly. In principle, the bid interpretation code will see that a bid of 1♠ fits this rule, telling the AI that partner has 13-18 HCP and at least four spades. In practice, though, all it does is tell which state to go into for that player’s next bid.

Getting information about a bid is trickier than might initially be expected. In particular, let’s say we’re East in the above game, and our partner West bid 1♠. From the above, it’s pretty obvious what we just learned about our partner’s hand. But what if West didn’t bid 1♠? Logically, by de Morgan’s law, we know that West either does not have 13-18 HCP, or West has fewer than four spades, or possibly both. If we later learn that West has 13-18 HCP, or that he has at least four spades, then we can conclude which one of those two things in the disjunction holds, but until then, we can’t really act on it. In fact, since West had opened with 1♣, we know he has at least 13 HCP, so we should be able to deduce that West lacks four-card support for hearts. In this case, at least.

Now consider that we have this information learned from what our partner didn’t bid for each bid the partner didn’t make that has a higher precedence than the bid he eventually made. Continuing our example, 1♠ wasn’t the first option West had. In the full XML file, we see that the other options were to bid 2, 3, or 4 if West had at least four hearts and HCP in the appropriate range. We can quickly build a list of potential information known about our partner’s hand, but it’ll usually be in the form of “either this is false or that is false, or both”.

Stepping back a bit, it’s clear that just keeping a simple list of information learned from our partner’s bids is insufficient. In fact, we need to do some amount of logical reasoning on it to learn new information. And futhermore, new bids can refine previous information. For example, an opening bid might indicate 13+ HCP, but a later bid might indicate 17-18 HCP. At first we knew partner’s HCP could be 15, but later on learned that it couldn’t. (Unless partner was lying or screwed up, of course, but the AI will assume your bids mean what the system says they do.) That later bid’s information in a sense supersedes what we learned earlier, even though they don’t contradict each other.

So, being a virtuous programmer (at least as far as the Camel Book is concerned), I want to be too lazy to write my own logic deduction engine if I don’t have to. I’m wondering if I might be able to pawn that work off on something written in Prolog.

Prolog is a logic programming language, which is inherently different than any programming languages you’re probably familiar with. Prolog is all about the logical deduction; you can give it facts and rules for deducing new facts, and it will do the leg work of figuring out if something can be proven as true or not. I’m certainly no expert on Prolog — most of my prior exposure to it is from having taken a class with a professor who was a fan of it, and liked to use it to demonstrate reference monitor decisions for access control — but it seems like it might be a good fit here. Maybe. I’ll have to work through some tutorials and actually, you know, learn Prolog a bit before knowing if it’s a good idea to try using it or not.

But even if the answer turns out to be “no”, I’ll still have learned some things about the logic programming paradigm, which is bound to be helpful in the future. Even if I never use Prolog, it’s good to be exposed to different ways of thinking about programming, just like learning functional programming can help you see new ways to solve problems even if you stick with object-oriented languages.

Or, if nothing else, you can use that kind of knowledge to write breathtakingly misguided code.

4 Responses

  1. I researched Prolog for a project at work. I’m convinced we should have used it for our Perverse Incentives research.

  2. Good to hear from ya!

  3. Paul, is there a link to the latest build of OLB?

    Nice work on it so far. Too bad you’re working on it at 1:30 in the morning on a workday…

  4. I’m going to hold off on making a new release until Old Lady is more playable than the previous release. You can grab the latest files out of the mirror of its bzr repo at if you’re so inclined.

Comments are closed.