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.