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.

4 Responses

  1. Better trick-counting heuristic…

    hrm. better trick-counting heuristic…

    Maybe outsource the code? Hire some guy in India to count the tricks anytime the program is run? With the time zone difference I’m sure you wouldn’t notice how long it took to compute, and as long as they delivered the results in numeric characters, you couldn’t tell it wasn’t American.

  2. Would it be possible to program counting the *losers* in your hand as opposed to the winners? Most pro bridge players count the losers as opposed to the winners in their hand when determining what to bid.

    In fact, there’s a numerical way to value your hand by using the losing trick count. A good and quick primer for that is located here: http://www.phillipalderbridge.com/LTC.HTM

    It’s not perfect, but it’s a damn fine way of evaluating tricks… and it’s almost completely numerical and well “suited” (pun intended) for programming.

  3. Use reasoning program (prolog) to decide what to bid may not be a good choice. As we can see the bidding system itself has already been the outcome of experienced human player after decades of thinking and playing. I am not sure current computer program language can describe all of them in exact. You have given a good example in this case(evaluating tricks).

    Considering anther simple but subjective case, the 13 HCP for opening bid. It could also be the result that after enumerating all possible distribution, the computer decide 13 is the best number.

    So in my opinion, either implementing bidding system logic or run simulation (use deal generator to play large number of deals that follow existing constrains) to decide the best bid.

  4. Ryan: Man, if not for having to spend money on the service, I’d be tempted to implement an “AI” for the game that just called out to Mechanical Turk. I’m curious how well that could work out. After all, I have played games in roughly equally crazy ways.

    Mark: I’ll need to look at it more, but something like that might work.

    ed2k: If I were trying to come up with an optimal bidding system, you’d be right, but for the time being I’m only interested in a basic beginner-level one. It’d be interesting to see if a computer-generated bidding system would be something a human could realistically be expected to learn and play, or if it’d be full of bizarre artificial bids. Or, equivalently, to compute how much information (in the Shannon sense) is conveyed in each bid, and whether that can be improved. After all, it seems like there’s enough room in the auction for all four players to perfectly describe their hands, as long as you remove the constraint that one of the partnerships has to end with a reasonable contract.

Comments are closed.