Tricky Trick-y Algorithm

Old Lady’s bidding logic is based on constraint logic programming over finite domains. Old Lady starts off with a set of variables that describe which cards are in each player’s hand. Each bid is used to constrain the possible values of the variables — for example, if a player opens the bidding with 1♠, that means his hand has at least 13 points and at least 5 spades. As more and more constraints are added, more information is known about each hand’s contents, since there are fewer and fewer possible assignments of variables that satisfy all constraints.

More specifically, each hand is described by 52 variables, one for each card in the deck. Each variable can be either 0 or 1. Naturally, 0 means the card is not in the hand, and 1 means it is. Even more specifically, the code looks like this:

default_knowledge(dealt(Spades, Hearts, Diamonds, Clubs)) :-
        length(Spades, 13),
        length(Hearts, 13),
        length(Diamonds, 13),
        length(Clubs, 13),
        append([Spades, Hearts, Diamonds, Clubs], AllCards),
        AllCards ins 0..1,
        sum(AllCards, #=, 13).

For convenience, the 52 variables are partitioned into four lists, one for each suit. Note that one constraint is already imposed here: the sum of the 52 variables must be exactly 13. Why? Because each player has 13 cards.

Of course, in one deal of bridge, there are four hands, and there’s the additional constraint that each card is in exactly one hand. The following code initializes each hand’s variables and then applies this no-overlap constraint:

default_everyone(SelfInfo, LeftInfo, PartnerInfo, RightInfo) :-
        maplist(default_knowledge, [SelfInfo, LeftInfo, PartnerInfo, RightInfo]),
        maplist(all_cards, [SelfInfo, LeftInfo, PartnerInfo, RightInfo],
                           [AllSelf, AllLeft, AllPartner, AllRight]),
        disjoint_holdings(AllSelf, AllLeft, AllPartner, AllRight).
 
disjoint_holdings([], [], [], []) :- !.
disjoint_holdings([SelfH | SelfT], [LeftH | LeftT], [PartnerH | PartnerT], [RightH | RightT]) :-
        SelfH + LeftH + PartnerH + RightH #= 1,
        disjoint_holdings(SelfT, LeftT, PartnerT, RightT).
 
all_cards(dealt(Spades, Hearts, Diamonds, Clubs), AllCards) :-
        append([Spades, Hearts, Diamonds, Clubs], AllCards).

Of course, one of the four hands’ contents are known, so the next step is to set the appropriate 13 variables to 1. Immediately, the constraint handling sets the other 39 variables for that hand to 0, as well as the variables for other hands that correspond to those 13 cards. The reasons should be obvious, but already it’s clear that those cross-hand constraints show how learning about one hand tells us something about the other three hands as well.

Why define the variables in this way? Because it makes lots of the common constraints used to choose and interpret bids easy to define. For example, checking the number of cards in a particular suit is easy: just add those 13 variables together:

suit_length(HandInfo, Suit, Length) :-
        suit_sublist(Suit, HandInfo, SuitedCards),
        sum(SuitedCards, #=, Length).

In the above fragment, suit_sublist does exactly what you might think: it unifies SuitedCards with the list of 13 variables for the given Suit.

High card points are slightly more complex, but also fall to a very simple constraint like that. In high card points, each ace is worth 4, each king is worth 3, each queen is worth 2, and each jack is worth 1. The following code checks the high card points in a hand, either within a single suit or across all suits combined:

high_card_points(HandInfo, HCP) :-
        maplist(high_card_points(HandInfo), [spades, hearts, diamonds, clubs], SuitHCPs),
        sum(SuitHCPs, #=, HCP).
 
high_card_points(HandInfo, Suit, HCP) :-
        suit_sublist(Suit, HandInfo, [Ace, King, Queen, Jack | _]),
        HCP #= Ace * 4 + King * 3 + Queen * 2 + Jack.

Not all the ways to evaluate a hand are quite so simple, however. For example, no trump bids often require the hand to be balanced across the four suits. In particular, “balanced” means 4-3-3-3, 4-4-3-2, or 5-3-3-2 distribution, where it doesn’t matter which suit has which length.

There’s no apparent way to write an algebraic expression to define what “balanced” means, but fortunately the finite domain constraint logic programming library has a few more tools we can use. We can give it a list of constraint variables and a list of possible assignments to those variables. For example, to force a 4-3-3-3 distribution, we could constrain [Spades, Hearts, Diamonds, Clubs] to be one of [4, 3, 3, 3], [3, 4, 3, 3], [3, 3, 4, 3], or [3, 3, 3, 4].

Naturally, we don’t want to have to list each possible order ourselves, so we can write a little code to give us the list of all possible permutations, with no duplicates:

expand_distribution(A-B-C-D, PermSet) :-
        findall(Perm, permutation([A, B, C, D], Perm), PermList),
        list_to_ord_set(PermList, PermSet).

With that, we can write code to take a list of desired distributions, find all permutations of each one, and constrain the lengths of the suits to match one of those possibilities:

distribution(HandInfo, Distributions) :-
        maplist(suit_length(HandInfo), [spades, hearts, diamonds, clubs], SuitLengths),
        maplist(expand_distribution, Distributions, PermSets),
        union_permutation_sets(PermSets, PermSet),
        tuples_in([SuitLengths], PermSet).

And now defining what a balanced hand means is easy:

balanced(HandInfo) :-
        distribution(HandInfo, [4-3-3-3, 4-4-3-2, 5-3-3-2]).

Note that - only means subtraction is certain contexts in Prolog. Any other time, it’s just another way to join terms together into a larger term. Prolog interprets A-B-C-D the exact same way as -(-(-(A, B), C), D). It just so happens that A-B-C-D matches conventional bridge notation for what a hand distribution looks like, making the code easier to read.

Another slightly tricky way to look at a hand is to count quick tricks. As the name suggests, this measures how many tricks the hand could easily take. Quick tricks within a suit are defined thusly:

  • ace and king = 2 quick tricks
  • ace and queen = 1.5 quick tricks
  • ace = 1 quick trick
  • king and queen = 1 quick trick
  • king and something else = 0.5 quick tricks

Intuitively, quick tricks require having high cards in a suit, and the better your high cards, the more easily you can take a couple tricks quickly before your opponents can trump you. Again, there’s no algebraic way to define quick tricks, but we can take advantage of reifiable constraints. In other words, we can treat the truth or falseness of a constraint as its own variable, and compare it to other variables with logical operators like “and“, “or“, and “if and only if“. It’s a little ugly, but it’s not too difficult to specify all the possibilities for quick tricks in a single suit, and a way to add them together to get the quick tricks for an entire hand:

demi_quick_tricks(HandInfo, DQT) :-
        maplist(demi_quick_tricks(HandInfo), [spades, hearts, diamonds, clubs], SuitDQTs),
        sum(SuitDQTs, #=, DQT).
 
demi_quick_tricks(HandInfo, Suit, DQT) :-
        suit_sublist(Suit, HandInfo, SuitedCards),
        SuitedCards = [Ace, King, Queen | _],
        suit_length(HandInfo, Suit, Length),
        DQT in 0..4,
        DQT #= 4 #<==> (Ace #= 1 #/\ King #= 1),
        DQT #= 3 #<==> (Ace #= 1 #/\ King #= 0 #/\ Queen #= 1),
        DQT #= 2 #<==> ((Ace #= 1 #/\ King #= 0 #/\ Queen #= 0) #\/
                        (Ace #= 0 #/\ King #= 1 #/\ Queen #= 1)),
        DQT #= 1 #<==> (Ace #= 0 #/\ King #= 1 #/\ Queen #= 0 #/\ Length #>= 2),
        DQT #= 0 #<==> (Ace #= 0 #/\ King #= 0).

Note that since the variables I’m using must be integers, I “cheat” by measuring quick tricks in units of 0.5, so that for example ace-king is 4 demi quick tricks. Converting to plain old quick tricks is just a matter of dividing by 2.

Now for the tricky one. When you’re considering making an preemptive opening bid, you look at the number of tricks you expect your hand to take if trumps are in your long suit. We’re interested in all tricks, not just the quick ones. How exactly do you define that?

That’s a good question, actually. The book I’m following doesn’t give any guidance beyond offering a few examples. The implication is that there’s a judgment call based on how good your suits look, with some leeway depending on how optimistic or pessimistic you are. As Justice Potter Stewart might have observed if he played bridge, you can’t define how to count tricks in your hand, but you know it when you see it.

Needless to say, that isn’t much to go off of when you’re writing a computer program to do it.

The best I could come up with is the following heuristic. I won’t paste the code, since it’s a bit long and you’re probably tired of seeing Prolog if you haven’t stopped reading already, but the idea is to do this for each suit in your hand:

  1. Make a list of the cards in your hand and a list of the cards not in your hand.
  2. Assume the cards not in your hand are split evenly between the two opponents.
  3. Simulate trying to win tricks with your hand. Play your highest card. If the opponents can beat it, they play their highest card and their lowest card, and you lose the trick. Otherwise, they play their lowest two cards, and you win the trick.
  4. Repeat until either you or your opponents run out of cards.
  5. If you still have cards, win one trick for each card you have left.
  6. To make the heuristic a bit less pessimistic, if you started with at least 7 cards and lost more than 3 tricks, add one to your count of won tricks, guessing that your opponents won’t be able to play perfectly.

I’m not saying this is the right way to do it, but it seems to work well enough. At least, its results match the examples I’ve come across in the book so far, which must count for something.

The big problem with it, however, is that it only works in one direction. Everything else works both ways. For example, with suit_length, if you know the length of a suit, you can constrain the variables for that suit. With demi_quick_tricks, if you know a suit has 2 quick tricks in it, you know the hand has the ace and king. And so on.

But here, you need to know exactly what cards your hand has. You can’t go the other way: given the number of tricks, constrain what the hand could possibly be. Even worse, in my initial implementation, instead of failing outright when trying to go the other way, it would enumerate over all possible hands looking for one that matched the number of tricks. Given (39 choose 13) = 8,122,425,444 possible hands the player could have, that doesn’t terminate in anything even remotely approximating a reasonable time.

For the time being, I punt on this problem. My code checks which direction the count-tricks rule is being used, and if it’s in the backwards direction, it does nothing. Good enough for now, but that’ll have to be fixed eventually.

Unfortunately, the only algorithm I can think of to count the tricks in a suit is to exhaustively enumerate all 213 = 8,192 possibilities, count the tricks in each, and use that as a lookup table. It’d be a pretty big lookup table, but not unreasonably so, so it might actually work in practice, especially if I can precompute it once on startup. At least, no better alternatives suggest themselves, so this might be the way I end up going.

Feel free to offer your own suggestions, if only for a better trick-counting heuristic.

Status Report

As you can see in the repository’s feed over on the right, development of Old Lady continues. I’m at a good point to talk a bit about its current status at a higher level, for those of you not checking each diff to see what’s happening with each checkin.

Thus far I’ve been going through the introductory bridge book I bought, implementing its bidding system (a simplified version of Standard American, though the book never calls it that) along the way. The most recent commit as of this writing more or less finishes Chapter 6. With that, the computer can open bidding at the 1 level, handle a 1NT opening essentially all the way through, and get through the first four bids for other 1-level openings.

Well, mostly. There’s lots of cases that wind up in the “todo” state, the catch-all for parts I haven’t figured out or gotten to in the book yet, but where more bidding might need to happen. As a result, the computer can get through most of the bidding, but then not know what to do when it comes times to seal the deal and pick a final contract.

Thus far, the decision logic has been based on the contents of the player’s hand and the bidding history. It doesn’t look at the information it’s derived about other hands from the bidding history. In other words, if it’s choosing a response to partner’s 1♠ opening bid, it will look at “partner bid 1♠” and not “I know partner definitely has at least 5 spades and 13-22 points”. This works fine early on, but becomes a pain after a few rounds of bidding, thanks to combinatorial explosion. Late-auction bids will probably need to take this latter route, when a fairly good picture of partner’s hand should be available, and it can start making decisions like “which suits do partner and I have at least 8 cards in together, and do we have enough points for game?”

There’s several more chapters on bidding I haven’t implemented yet. In the short term, I’ll work on those and leave the aforementioned loose ends for later. The next chapters are:

  • Opening bids at the 2-level or higher, and the bids that come after them. The decision logic here needs to consider the vulnerability of the partnerships, which is information the Prolog code doesn’t (yet) have access to.
  • Bidding slams and grand slams. Right now, the highest bidding the computer will ever try to go to is game.
  • Overcalls and takeout doubles; and the following chapter on competitive auctions. Right now, the computer gives up on bidding as soon as the other partnership bids anything. You might think that’s an easy way to stop the enemy computer plays from ever reaching a contract, but keep in mind that your partner also stops bidding! Not good.

After that, of course, is implementing the code for playing tricks. Right now a pretty dumb Python AI is there that doesn’t take advantage of any information learned from the auction or what cards have been played. The whole point of writing the bidding code in Python is to provide that information.

When all that is done, the computer players should be roughly as good as a beginner who’s been practicing, at which point you could actually consider Old Lady playable.

There’s lots of other features I’d like to add once I reach that point:

  • Making the code much faster. There are cases where the computer will spend a very noticeable and excessive amount of time “thinking”. A lot of the code is definitely sub-optimal, but it’s too early to start optimizing yet.
  • Support for other bidding systems. Standard American is just one of the ones out there, after all.
  • Support for having each partnership use different bidding systems.
  • Hints and other help for players who don’t know how to play bridge very well. This would include being able to explain the meaning behind bids and cards played.

It might be useful to write a domain-specific language for bidding systems. The closer they can be written in a way that matches how a person thinks of them, the better. That would also make it much easier to add help information for each bid. Ideally, the implementation in the DSL would be the help information for the bid.

But let’s finish implementing the basics before I start with any of that.

How many bridge auctions are possible?

Implementing the bidding logic in Old Lady has become a real slog. Each new bid branches the decision tree even more, and each chunk of decision logic only applies to a handful of nodes in the tree. Right now I’m at the point where each check-in of a new set of code only applies to a fairly narrow case that can arise during the auction, but all those annoying little cases must be implemented.

It doesn’t take long until you start to wonder, just how many possible auctions are there in a round of bridge anyway?

As you’d probably guess even if you don’t play bridge, an auction is a sequence of bids. The ultimate goal of the auction is to arrive at a contract that one partnership will try to meet by taking tricks. (A secondary yet very important goal is to communicate with your partner through the bids you make what your hand looks like.) Ignoring whatever bidding system the players might be using, the rules of bridge constrain what the possible sequences of bids are.

While it’s theoretically possible to exhaustively enumerate all possible auctions, since we want to answer the question before we all die of old age, let’s use a little math to count faster.

The backbone of the auction are the bids that specify a possible contract. A contract is a rank (1 to 7) paired with either a suit (♣, ♦ ♥, or ♠) or no-trump (NT). That gives 7 x 5 = 35 possible contracts.

Contracts must be bid in ascending order, with the denominations ordered ♣ < ♦ < ♥ < ♠ < NT. For example, once 2♥ is bid, nobody can bid 2♣ or 1♠.

If we just look at the contracts that are bid during an auction, this means we don’t have to worry about the ordering of the contracts that are bid: the rules force one single possible ordering. Each contract may or may not be bid during the auction, for a total number of “backbones” of 235.

While that’s a pretty big number already (over 34 billion), we’re not even close to finished, since there’s plenty of other bids that don’t try to name a contract.

First, to get it out of the way, there is exactly one possible auction where no contracts are bid: all four players pass. We’ll ignore this special case for the time being and assume at least one contract is being bid in the auction.

Before the first contract is bid, up to three consecutive players may pass. We’ll call this series of passes at the beginning of the auction the “prelude”. There are 4 possible preludes in a non-trivial auction: no passes, one pass, two passes, and three passes.

Aside from passing, other possible bids are doubles and redoubles. A double can be bid by one of the opposing players after a contract is bid; it roughly means “there’s no way you’re going to make that contract”. A redouble can be bid after the other partnership bids double; it roughly means “wanna bet?”

Between two consecutive contracts in an auction is what we’ll call an “interlude”. There are a few things that can happen here:

  • Zero, one, or two players can pass.
  • The opposing partnership can double the contract, with possible passes before and after.
  • The opposing partnership can double the contract, and the original partnership can redouble it. Again, passes may occur before, after, and in between these bids.

Counting how many ways these three cases are possible:

  • If the contract is not doubled, there are 3 possibilities: no passes, one pass, or two passes.
  • If the contract is doubled but not redoubled, there are 6 possibilities: either zero or two passes, then the double, then zero to two passes. 2 x 1 x 3 = 6.
  • If the contract is doubled and redoubled, there are 12 possibilities: either zero or two passes, then the double, then zero or two more passes, then the redouble, then finally zero to two passes. 2 x 1 x 2 x 1 x 3 = 12.

All together, there are 3 + 6 + 12 = 21 possible interludes between each consecutive pair of contracts in the auction.

Finally, bidding ends when three consecutive passes are made after a contract is bid. Again, the contract can be doubled or redoubled. By a similar analysis for what we did for the interlude, there are 7 possible “epilogues”: 1 + 2 x 1 x 1 + 2 x 1 x 2 x 1 x 1 = 7. (Same analysis as before, but now the final set of passes must be three, so there are fewer possibilities in each case.)

Now, how to combine all these numbers together? Let’s use our terminology to look at the structure of a few simple auction templates:

  • No contracts: pass pass pass pass
  • One contract: prologue contract epilogue
  • Two contracts: prologue contract interlude contract epilogue
  • Three contracts: prologue contract interlude contract interlude contract epilogue

Let’s let i be the number of contracts in our auction. Whenever i > 0, the auction will have one prologue (3 choices), i – 1 interludes (21 choices each), and one epilogue (7 choices). That leaves the number of ways to choose i contracts out of the 35 possible contracts. Luckily, a little elementary combinatorics already gives us a function to compute that: 35 choose i.

So, for any given i > 0, the possible number of auctions with exactly i contracts is:

3 \cdot \binom{35}{i} \cdot 21^{i - 1} \cdot 7

Which can be simplified a bit to:

\binom{35}{i} \cdot 21^i

Interestingly, if we plug in i = 0 to that formula, it just so happens to return 1, which is the number of auctions with no contracts in them. We don’t need the i > 0 restriction after all.

As a result, the total number of possible auctions in a single deal of bridge is exactly:

\sum_{i=0}^{35} \binom{35}{i} \cdot 21^i

Which is roughly 9.7 x 1046, or exactly 96,559,237,760,273,012,340,173,944,583,707,028,522,342,023,168.

That’s a lot, though the vast majority of them will never come up in practice. Luckily not all of them require special handing.

[Edit: For comparison, the number of possible ways to deal the cards in bridge in the first place is “only” about 5.4 x 1028, or exactly 53,644,737,765,488,792,839,237,440,000.]

Sans Donald

My nefarious ploy of publishing the status of my code repositories has succeeded, as I’ve forced myself to finally sink some time into Old Lady lest anyone see how dusty the code base had gotten. (Playing video games for several hours is only part of the excuse for that.)

I’ve been cranking through the introductory bridge book I bought, implementing its guidelines for bidding in Old Lady. Thus far, the computer players can handle 1NT openings pretty much all the way through, and can respond once to any other 1-level opening bid before they find themselves in a situation they don’t know how to handle.

Old Lady screenshot

Here’s a screenshot of the most interesting 1NT bidding I was able to produce while playing it for a little while. North (computer partner) opened 1NT, since he had 15 points and balanced distribution. I (playing South) had 13 points and a long (5+ cards) spade suit, so I replied with 3♠. That reply is forcing to game, requiring North’s next bid to be at least at the game level. (His 1NT opening indicated 15-17 points, plus my 13 points meant we had 28-30 points total, and 26 points is the threshold for bidding game.) North could choose between game in spades or game in no trump, depending on whether our hands had enough spades between us. My 3♠ bid indicated I had at least 5 spades, plus his 3 spades gave us 8 total, which is enough for bidding in spades, so he chose 4♠ as our contract.

For the record, we (meaning I, since North was dummy) did indeed collect our 10 tricks.

The Prolog code that handles the computer players’ bidding works pretty well as far as it’s been implemented, though it runs noticeably slowly. The speed problems will be fixed later. I’ve implemented the bidding code as a state machine. The initial state is “opening”, and the bids made after that determine what the new state is. The state determines which set of rules to use when choosing (or interpreting the meaning of) the next bid.

Specifically, the names of the states just happen to be the names of the rules that implement their initial logic, allowing me to use call/4 to jump into the right section of code. The bidding logic itself is spread across multiple SWI-Prolog modules that keep related states’ implementations together and hide the internal details. For example, one module handles opening bids; another handles bidding after a 1NT opening; a third handles responses to a 1-suit opening; etc.

Key to the bidding code is the large set of unit tests for each module that make sure they’re doing the right thing. The vast majority of these are taken from the quizzes in the aforementioned bridge book. I figure if the self-tests are good enough for me, they’re good enough for Old Lady. Automated testing is essential for Old Lady; because of the randomness in each deal, you can’t just keep playing hands manually until the situation you want to test comes up, and then look to see if the computers behave correctly.

For the adventurous, you can check the latest code out of the repository (bzr get http://www.kuliniewicz.org/oldlady/bzr/oldlady) and try it out. There’s still lots of bidding logic to implement, and the AI for the trick-taking portion of the game is still dumb as rocks, but it is at least playable. The configure script should actually make sure you have everything you need to run the program now.

Browsable bzr repository

I’ve finally set up a browsable web interface to my bzr repositories. Now you can more easily track what’s going on in my various software projects without having to actually check out a copy of the repository. In particular, there’s also feeds that track the latest updates. I’ve also added those feeds to the sidebar of my blog, thus letting you keep tabs on what’s going on with almost no effort on your part.

If it breaks, let me know.

Old, but not dead

Wow, it’s been far too long since I’ve posted something here.

Old Lady, my fledgling open-source bridge game, has finally been seeing some updates lately. The main blocker had been me hitting the limits of my knowledge of bridge strategy augmented with the information readily available on the Internet. While Old Lady follows the rules of bridge just fine, it’s absolutely horrid at playing well. And since the computer plays not only your opponents but also your partner, this isn’t as nice as a novice might think.

Anyway, during a recent trip to the library I found an introductory bridge book that does a pretty good job explaining basic bidding and play, along with the rationale behind it. I started implementing its guidance in Old Lady’s Prolog code, but didn’t get very far into it before having to return the book. And since the copy I bought off of Amazon hasn’t arrived yet, things are once again on hold. Briefly, this time.

Old Lady is still pretty much unplayable, but if you’re really curious you can grab the latest code out of its bzr repository at http://www.kuliniewicz.org/oldlady/bzr/oldlady/. At least now the configure script actually checks to make sure you have SWI-Prolog installed, though it still pretty much assumes you have all the modules (both Prolog and Python) installed. That’ll be fixed eventually.

I tentatively plan the next tarball release for when enough of the bidding system is implemented to make at least that phase of the game playable.

Python v. Prolog: Round 1: Fight!

Finally, I’ve made some early progress in implementing Old Lady’s bidding system logic in Prolog. Specifically, SWI-Prolog.

While GNU Prolog looks like it has all the features Old Lady would need, it doesn’t look like it’s quite as robust a Prolog implementation as SWI-Prolog is. For example, GNU Prolog doesn’t have a module system, which might be useful whenever Old Lady supports more than just one bidding system — for example, you might want generic stuff in one module, and each particular bidding system in its own module. Also, integrating GNU Prolog into a Python program looks like a trickier proposition than I initially thought. Although GNU Prolog has a Prolog-to-C interface, it’s geared towards embedding a static copy of GNU Prolog into a standalone C program. Getting its compiler wrapper to output a shared library suitable for wrapping a Python module around is probably doable, but would involve more trickery than I’d really care to have to implement.

Which is all not to say that the road to using SWI-Prolog has been particularly wonderful, either. The Debian packages for it are pretty out of date (the last two uploads were in June 2006 and July 2004!). PySWIP provides a Python interface to SWI-Prolog, but requires SWI-Prolog’s shared library; there’s a five-year-old wishlist bug for the Debian packages to include that library, which they currently don’t. While supposedly there is work on getting a non-ancient version of SWI-Prolog packaged, you’ll forgive me if I don’t hold my breath.

Fortunately, compiling the latest SWI-Prolog from source and installing it manually wasn’t too difficult. Unfortunatley, the last released version of PySWIP (0.2.1) doesn’t actually work, so I had to grab the latest code from the SVN repository, which at least is functional.

Mostly.

My intention is to issue a Prolog query of the form

Hand=[...], History=[...], choose_bid(Bid, Hand, History)

where Hand is a list of cards in the player’s hand and History is the list of bids that have been made previously by all players. What the Prolog code will do is find a value for Bid that looks something like bid(1,hearts) or bid(pass), or something along those lines. Nothing fancy.

Unfortunately, PySWIP (or at least the version in the SVN repository) doesn’t provide very useful information out of a query like this. Say for example I issue the following query through PySWIP (with extra whitespace added between the main terms, for readability’s sake):

Hand=[card(7,clubs), card(8,clubs), card(9,clubs), card(ace,clubs), card(6,diamonds), card(8,diamonds), card(ace,diamonds), card(2,hearts), card(10,hearts), card(queen,hearts), card(king,hearts), card(5,spades), card(8,spades)],
 
Hist=[bid(pass)],
 
choose_bid(Bid, Hand, Hist)

For each solution found, PySWIP returns a dict with what term is assigned to each variable. In the above, PySWIP “helpfully” returns the string 'Functor5075212' as the value assigned to Bid.

Yes, PySWIP, thanks for telling me it’s some complex term. And giving me no way to look at what the term actually is.

I can only get a useful result back if I only ask for simple atoms to be assigned to the variables in the query. But since I don’t know whether there are one or two parameters to the bid term, I have to effectively do two separate queries, one for each case:

Hand=[card(7,clubs), card(8,clubs), card(9,clubs), card(ace,clubs), card(6,diamonds), card(8,diamonds), card(ace,diamonds), card(2,hearts), card(10,hearts), card(queen,hearts), card(king,hearts), card(5,spades), card(8,spades)],
 
Hist=[bid(pass)],
 
( choose_bid(bid(Level, Denom), Hand, Hist) ; choose_bid(bid(Action), Hand, Hist) )

That is, use a logical disjunction between two separate calls to the choose_bid predicate, which ends up doing twice the work as the original, “correct” query. But at least PySWIP returns useful information in this case:

'Denom': 'clubs', 'Level': 1, 'Action': Variable(362)

I can only assume this sort of brokenness in PySWIP is a bug, and not actually what it’s intended to do for non-atomic terms assigned to variables. (It also gives me the assignments to Hand and Hist, which are also expressed using the nonsense Functor notation, but at least for those it gives me the paramter list too, which would actually be useful, if not for the fact that I already told PySWIP what those variables’ values are, and in fact that I only made them variables instead of inlining them directly in the call to choose_bid since it’s forcing me to make two calls to choose_bid in the first place!)

Suboptimal, yes, but it is at least usable, and the ugliness can be safely hidden in my Python class that builds these queries and parses out the results.

For the truly adventurous, the code is in the Old Lady bzr repository, though it’s not really playable yet, since breathtakingly little of the Standard American Yellow Card has yet been implemented.

Pro Prolog

Last time, I mentioned that different programming paradigms involve thinking about the problem you’re trying to solve in completely different ways. Most languages you normally see in use, be they procedural, object-oriented, functional, or something else, typically involve giving the computer a series of commands to execute. The way you do that can vary quite a bit, but that’s essentially what’s going on. The computer doesn’t particularly care what you’re trying to accomplish; it just does as it’s told. We might call this the Meatwad Programming Paradigm:

Do what I said, ’cause I said it.

- Meatwad

Prolog is different; it’s a logic programming language. In logic programming, instead of giving the computer a series of commands, you give it a database of facts and rules. Facts are, well, simple facts that you know are true. Rules tell the computer how to derive new facts from other facts. Once you load the database, you can ask the computer where things are true. If the computer can use the facts and rules it knows to prove what you asked, it will tell you so. Otherwise, it will report failure.

An example might make this clearer. Let’s say we want to study the relationships between people in a family. Our database needs to have a simple set of relationships we know, such as:


father(george,michael).
father(george,lindsay).
father(george,gob).
father(george,buster).
father(michael,george_michael).
father(tobias,maeby).
 
mother(lucille,michael).
mother(lucille,lindsay).
mother(lucille,gob).
mother(lucille,buster).
mother(lindsay,maeby).

Our facts take the form of predicates with one or more arguments. Here, we’re using father(X,Y) to mean that X is the father of Y. We use mother(X,Y) similarly.

Given just this database, we can execute queries to see if certain parent-child relationships are true. For example:


| ?- father(george,lindsay).
 
true ?
 
(4 ms) yes
| ?- father(tobias,buster).
 
no

It should be exceedingly obvious that, given the above database, George is Lindsay’s father, but Tobias is not Buster’s father. Technically, Prolog hasn’t proved that Tobias isn’t Buster’s father, but it did fail to prove that he was, which is good enough for Prolog.

Naturally, if this were all we could do with Prolog, it wouldn’t be very interesting. One neat thing is that we can put variables in the arguments to, for example, get a list of everyone whose father is George:


| ?- father(george,X).
 
X = michael ? a
 
X = lindsay
 
X = gob
 
X = buster
 
(4 ms) yes

Prolog tells us all the values of X that would satisfy the query. We could have used a variable in the first argument to father instead (to find out who someone’s father is) or use variables for both arguments (to find out all father-child relationships).

Things get a bit more interesting once we start adding some rules to our database. For example, let’s start with a predicate parent(X,Y) that is true whenever X is Y‘s parent:


parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).

The first rule tells Prolog that X is Y‘s parent if X is Y‘s father. The second says that X is Y‘s parent if X is Y‘s mother. Now we can use the parent predicate just like the others we defined via facts:


| ?- parent(lucille,buster).
 
yes
| ?- parent(X,maeby).
 
X = tobias ? a
 
X = lindsay
 
yes

But this is kid’s stuff so far. Prolog wouldn’t be much of a programming language if we couldn’t use rules recursively, so let’s do that to define arbitrary ancestral relationships between two people:


ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).

The first rule simply says that X is Y‘s ancestor if X is Y‘s parent. The second one is where things get interesting: X is Y‘s ancestor if X is the parent of some Z, and Z is an ancestor of Y. Now we can use Prolog to probe ancestral relationships of arbitrary length:


| ?- ancestor(george,maeby).
 
true ?
 
yes
| ?- ancestor(X,maeby).
 
X = tobias ? a
 
X = lindsay
 
X = george
 
X = lucille
 
no

Observe that that last query finds not only Maeby’s parents (Tobias and Lindsay) but also her grandparents (George and Lucille).

Prolog also lets us use lists in additional to individual terms. To show that we can also implement algorithms in Prolog, here’s a (fairly unoptimized) implementation of mergesort:


mergesort([], []).
mergesort([X], [X]).
mergesort(In, Out) :-
    length(In, InLen),
    InLen >= 2,
    append(X, Y, In),
    length(X, XLen),
    length(Y, YLen),
    ( 0 is YLen - XLen; 1 is YLen - XLen ),
    mergesort(X, XSorted),
    mergesort(Y, YSorted),
    merge(XSorted, YSorted, Out).
 
merge([], Y, Y).
merge(X, [], X).
merge([XHead | XTail], [YHead | YTail], [XHead | RTail]) :-
    XHead =< YHead,
    merge(XTail, [YHead | YTail], RTail).
merge([XHead | XTail], [YHead | YTail], [YHead | RTail]) :-
    YHead < XHead,
    merge([XHead | XTail], YTail, RTail).

That may look quite a bit like a mergesort written in a functional language, but note that there is some logic programming uniqueness to it. In particularly, we split the “input” list in half by telling Prolog to find two lists X and Y who, appended together, equal the original list, and whose lengths are within 1 of each other. Prolog takes care of figuring out what X and Y should be in any particular instance. Having something called append do double duty as a way to split a list in twain is one of the crazy things logic programming lets you do.

Plain old Prolog does fall down a bit when it comes to math. While it can handle arithmetic just fine, it doesn’t know how to do algebra. For example:


| ?- X is 3 + 5.
 
X = 8
 
yes
| ?- 8 is X + 5.
uncaught exception: error(instantiation_error,(is)/2)

From what we’ve seen so far, Prolog doesn’t quite satisfy the needs for implementing a bridge bidding system for Old Lady. On the one hand, predicates and variable unification are a good fit for the bidding rules: something like bid(Bid, HandInfo) could be used to choose a bid if we pass it information about a hand, and can also be used to learn about a hand given a certain bid. This “it works in both directions”-ness is exactly what we’re looking for to both make our own bids and to interpret those of other players, without having to duplicate our rules.

However, an inability to do mathematics more complex than basic arithmetic is a problem, since most of the information communicated through bidding is precisely that: how many HCP a player has, or how many cards of a certain suit he has, and so on. There’s also known mathematical relationships between all the variables: for example, the deck only has 13 spades, so if I have 5 and my partner has at least 3, that tells me that the other two players have at most 5 spades between them. Plain old Prolog doesn’t have an elegant way to express these sorts of constraints.

But notice how I slipped “plain old” in front of Prolog? Some Prolog implementations, such as GNU Prolog (the one I’m experimenting with) also do constraint logic programming, which lets us express mathematical relationships between variables. For example, let’s try to find all numbers less than or equal to 100 that are equal to the square of a prime number:


| ?- fd_domain(X,0,100), fd_prime(Y), X #=# Y * Y.
 
X = _#3(4:9:25:49)
Y = _#23(2..3:5:7)
 
yes

The constraint solver in GNU Prolog has figured out that X must be 4, 9, 25, or 49, and Y must be 2, 3, 5, or 7. As we add constraints, we can narrow that down even further. For example, let’s also require that X is even:


| ?- fd_domain(X,0,100), fd_prime(Y), X #=# Y * Y, 0 #=# rem(X, 2).
 
X = 4
Y = 2
 
yes

Given this, a way to implement a bidding system in GNU Prolog reveals itself. Encode the bidding system rules in Prolog rules, using these numerical constraints. Then build a query that includes all the basic information we know, namely our hand and the bidding history so far. In evaluating the query, GNU Prolog will determine constraints on the variables of interest (i.e., who has how many of each suit, and their hands’ estimated strength), and pick the next bid we should make.

Even better, GNU Prolog has ways to issue queries from C code. While this might not seem very useful when Old Lady is written in Python, there are ways to interact between C and Python, so we just need to write a little duct tape in C that communicates between GNU Prolog and Python.

So, it turns out I was looking for a constraint logic solver all this time, and was writing an exceedingly two-ninths-assed one in Python.

If any of the above has piqued your interest in Prolog, there’s a pretty good Prolog tutorial here that does a much better job explaining Prolog than I’ve done here.

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 -->
<bid>
    <exists name="suit">
        <include>
            <denomination-range low="open" high="closed">
                <partner-denomination/>
                <spades/>
            </denomination-range>
        </include>
    </exists>
    <level>
        <integer value="1"/>
    </level>
    <denomination>
        <variable name="suit"/>
    </denomination>
    <transition state="1-respond-again"/>
    <conditions>
        <range>
            <hcp/>
            <integer value="13"/>
            <integer value="18"/>
        </range>
        <at-least>
            <length>
                <variable name="suit"/>
            </length>
            <integer value="4"/>
        </at-least>
    </conditions>
</bid>

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.

Bidding System System

As I may have mentioned earlier, there’s two phases of a single hand of bridge: the auction, and the part where you actually play the cards you were dealt. There’s lots of different bidding systems a partnership might use during the auction to decide how their bids will tell each other what they’re holding. So, to get a computer to play bridge, it’s necessary to program into it at least one bidding system.

So take a fairly common system such as, say, Standard American Yellow Card. Quick, what’s the best way to implement that?

As you can see if you click that link, a human-comprehendable description of the system involves all sorts of special cases. If your partner opens the bidding, the “rules” you’re supposed to follow when your partner opens with 1♠, 1NT, 2♣ or 2♠ are completely different. While from a coding point of view you’d like to implement a few basic, universally-applicable rules and have the complex behavior naturally follow from that, it seems unlikely that that’s really possible without lots of special cases.

It seems as though that, at a high enough level at least, you need some sort of finite state machine, where each state is associated with the set of rules you want to use to determine your next bid, and certain bids (by you or your partner) switch you over to a different state.

But even within each state, there’s lots of conditions to check for to decide which bid to make at any given point. A plain old code implementation leaves you with plenty of conditionals checking for each case you’re interested in. This becomes problematic when you then turn to writing the code that interprets what another player’s bid means. This ends up being sort of like your bidding code, but turned inside-out, since you’re now taking a bid and figuring out what conditions caused that bid to be made. If you squint a bit, this looks a lot like duplicating all your code, which is bound to leave you with hard-to-find bugs; inevitably your bid interpreter is going to misinterpret something in some cases.

Naturally, what you’d like to do is write the rules to follow once, and be able to use those rules going both in the forward direction (here’s what I know, what should I bid?) and the backwards direction (here’s what he bid, what does he have?). Thus our rules are implemented not as code but data. But can whatever data structure we use be expressive enough to adequately say what the rules are without winding up reimplementing half a “real” programming language in the process? There’s enough trickiness afoot in the bidding systems where the answer isn’t immediately obvious.

Of course, a theorist might argue that on a von Neumann architecture there’s no real difference between “code” and “data” anyway, but there’s a big difference in practice between analyzing a set of rules written in XML and analyzing the Python code you wrote to do something. A Lisp devotee might brag that Lisp lets you treat code as data, but nobody actually uses Lisp.

In my tinkering so far I’ve sort of been doing the state-machine-in-Python approach, but having to write functions going forward and backward is getting to be a pain. I think I’ll try writing bidding system rules in XML and then write generic “bidding” and “interpretation” functions that use it, and see if that turns out to be more promising. Hopefully the XML won’t wind up being something silly like this:


<?xml version="1.0" encoding="UTF-8"?>
<compilation-unit>
    <preprocessor>
        <include path="system" src="stdio.h"/>
    </preprocessor>
    <function>
        <name>main</name>
        <return-type>
            <int/>
        </return-type>
        <parameter-list>
            <parameter>
                <name>argc</name>
                <type>
                    <int/>
                </type>
            </parameter>
            <parameter>
                <name>argv</name>
                <type>
                    <array>
                        <pointer>
                            <char/>
                        </pointer>
                    </array>
                </type>
            </parameter>
        </parameter-list>
        <body>
            <statement>
                <call>
                    <target>
                        <identifier>printf</identifier>
                    </target>
                    <argument-list>
                        <argument>
                            <string>Hello, world!  I am %s.\n</string>
                        </argument>
                        <argument>
                            <ternary>
                                <condition>
                                    <greater-than>
                                        <first>
                                            <identifier>argc</identifier>
                                        </first>
                                        <second>
                                            <integer>0</integer>
                                        </second>
                                    </greater-than>
                                </condition>
                                <if-true>
                                    <subscript>
                                        <base>
                                            <identifier>argv</identifier>
                                        </base>
                                        <index>
                                            <integer>0</integer>
                                        </index>
                                    </subscript>
                                </if-true>
                                <if-false>
                                    <string>anonymous</string>
                                </if-false>
                            </ternary>
                        </argument>
                    </argument-list>
                </call>
            </statement>
            <statement>
                <return>
                    <integer>0</integer>
                </return>
            </statement>
        </body>
    </function>
</compilation-unit>

(If you’re bored, try writing some XSLT that converts that back into real C.)

Only old ladies play bridge

Given that, it’s inevitable what this program had to be called:

Old Lady 0.1.0 screenshot

Surprisingly, nobody seems to have written an open-source contract bridge program that wasn’t just a client for network play. That might mean that Old Lady is the first. Technically, at least. Currently, the rules of the game are implemented, but all the computer players really manage to do is play by the rules. Tactically and strategically, they’re dumb as rocks.

(Specifically, dumb as basalt. For reference, in no particular order, granite takes out subprime loans, obsidian invests in subprime loans, dolomite invests in the weekly lottery, flint uses 1337 unironically, gypsum believes the moon landing was a hoax, limestone believes the moon itself is a hoax, and shale thinks Mega Man 3 is better than Mega Man 2.)

(Also, perhaps it’s not so surprising it hasn’t been done, given how your stereotypical open-source programmers are young males and your stereotypical bridge players are old ladies. There’s not much overlap between those demographics.)

But I digress. While it might not immediately seem that having braindead opponents is such a bad thing, especially if you’re just learning how to play, bridge is a team game, and having a braindead partner is something else entirely. Currently, during the auction, the computer players always pass, and during the trick-taking phase, the computers will always play the lowest-valued card that will take the trick (if it isn’t currently being won by the partner), or throw away the lowest-valued card otherwise. It’s legal, but even a novice could defeat such players without much difficulty.

If you play chess, it’s a bit as though your opponent captured whenever possible, and otherwise moved the piece closest to square a1 towards the center of the board. You’re not going to win many games that way.

So, why bother with bridge? It’s actually an interesting game if you’re at all interested in communications. During the auction, your goal is to establish a contract: how many tricks you think your partnership will be able to take, and what suit (if any) should be trump. Of course, you’re not able to look at your partner’s hand, so you can’t tell what your best contract is just by looking at your own cards. However, the only communication with your partner you are allowed to make is through what bids you make.

As a result, bids don’t act just as a claim of what you want the final contract to be, but are also your only way for you and you partner to signal to each other about what your hands look like, using that knowledge to decide what contract to go for. There’s a whole host of bidding conventions that assign a meaning to each bid you can make in each situation, running the gamut from natural systems (where each bid also acts as a reasonable possible contract) to artificial systems (where many bids are not intended to become the contract at all, but merely serve as an arbitrary message).

To give you an example of the latter kind, under the Blackwood convention, a bid of 4NT (No Trump) doesn’t mean you think your partnership can take 10 tricks and not have a trump suit. Instead, it tells your partner you think your partnership can pull off a slam (a 6-level contract, taking all but one trick), and that you want him to tell you how many aces are in his hand, by bidding 5♣ if he has zero or four aces, 5 if he has one, 5 if he has two, and 5♠ if he has three; then you might bid 5NT to ask for how many kings are in his hand in a similar fashion, or otherwise bid the contract you actually want.

Now, your first thought might be that the bids you and your partner make act as a sort of covert channel, or at the very least a private one, and that you wouldn’t want your opponents to know what bidding convention your partnership is using. However, in bridge you are required to tell your opponents what your bidding convention is, and they can even ask your partner what your last bid means! I know, this is rife with pre-9/11 thinking, but apparently old ladies hate America and don’t care if bin Laden knows they have a fit for spades but few good honors in the side suits.

On top of that, there’s only at most 36 possible bids you can make at any point, which gives you all of 5.17 bits of information (rounding up) you can pass. And since this is an auction after all, bids have to keep going up — you can’t bid 2♣ after someone’s already bid 2♠ or 3♣. That further constrains how much detail you can effectively pass, since your bid must be no higher than the contract you will eventually try to establish. If you want to make 7NT signal “my hand ain’t worth expletive”, well, don’t expect to get many points. Conversely, making a high bid early on can effectively jam your opponents’ communications by taking away some of their maneuvering room.

So, bridge is very much a game of exploting small amounts of information to deduce what each player’s hand looks like, both to inform your bidding and what cards you play in each trick. And since one of the players in the partnership that wins the auction puts his entire hand face-up and has his partner play both that hand and his own, knowing how suits and high cards are distributed between the two hands you can’t see can be very helpful.

It seems that a computer player should be able to best a human because a computer could more fully exploit the information revealed during play. The computer after all has megabytes of memory, whereas the human is constrained by short-term memory and mnemonic tricks.

The computer players currently implemented for Old Lady do none of this, not even bothering to look at the face-up hand at all.

Of course, that leaves open the question of just how to program the computer to collect and use this information, given factors such as how the meanings of different bids change depending on context, and how few bids convey very precise information, and the thresholds for making one bid versus another can be fuzzied given confounding factors that may or may not be known by the other players. Also, ideally Old Lady would support many different conventions, so they should be readily swappable at run time.

The best approach to take for now is probably to focus on a single bidding convention and hard-code it in, and hope that the logic that would be general to most conventions will make itself apparent. There’ll be a lot of conditionals unless some natural way to express a convention purely as data makes itself evident. Something like a table of “if I know this, bid that”, which looks something like pattern matching or even reasoning in intuitionistic logic if you squint a bit. (The latter of those is probably overkill, but it’s hard to be certain at this point.)

It probably also doesn’t help that I’m a novice myself at the game. But then again, I don’t seem to have any competition in the open-source world, so my program beats their programs by default! In your face, hypothetical other people!