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.

DIY kosho?

Surely someone at some point has been inspired by watching The Prisoner and set up their own kosho ring. Preliminary searches on Google and YouTube only turn up things related to “real” kosho and not the product of Patrick McGoohan‘s imagination.

Come on, in the post-Jackass era, can you seriously tell me no one has done this? And videotaped the results and posted them on the Internet?

If you have no idea what I’m talking about, watch this (from the episode It’s Your Funeral, if I’m not mistaken):

Music Applet 2.4.1 released

Music Applet 2.4.1 has been released. This is a bug-fix release, with no new features. The dependency on the deprecated python-dcop, previous used for Amarok support, has been removed. A bug in password handling for MPD has also been fixed. See the release notes for details.

Lazy Spammers

I see that nowadays comment spammers don’t bother figuring out what markup they need to use to make hyperlinks, so they try half a dozen different formats and hope one works.

They’re also apparently too dumb to not put two dozen spam comments in the same recent post and think that won’t get noticed right quick.

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.]

ur doin it wrong: Direct Marketing Edition

Living in an apartment means having a greater incidence of people leaving ads on your door. Whoever went through here today, however, clearly didn’t quite grasp the concept of how this marketing scheme works. The ads were clearly intended to be the direct-mail kind, what with having printed addresses and the “PRESRT STD U.S. POSTAGE PAID” thingy where the stamp would go. Yet it was shoved between the doorknob and doorjamb.

Naturally, the would-be mailing address is for a residence about two miles away.

Any ideas why someone would bother buying a database of residential addresses if they’re just going to pay some schmuck to walk around in the middle of summer shoving the ads in doors?

FLummoxing CLeverness

You wouldn’t think it’d be so difficult to rip a few DVDs. Well, it isn’t, unless you’re trying to do it in a way that’s far too clever for your own good.

A refresher for those of you who haven’t committed my personal computing resources to memory: I have two computers, holly and kryten. (No points for guessing the naming scheme.) holly is my eight-year-old former desktop computer, now relegated to running MythTV. kryten is my four-year-old tablet that I use for pretty much everything else.

Ripping and encoding DVDs is a CPU-intensive process, so naturally I wanted to do the job on kryten, whose wimpy 1.7 GHz Pentium-M is still quite a bit better than holly’s mere 933 MHz Pentium-III. The problem is, kryten doesn’t really have a DVD drive per se. I have a DVD drive that connects via the PCMCIA slot, but it’s slow (as in, too slow to play a DVD real-time) and sometimes hangs the Linux kernel when you eject the card.

My clever plan to get around this was to read the DVDs on holly, copy the raw data over to kryten via the local network, and do the actual encoding from there. Pretty much any program on Linux that reads from a DVD is just as happy to read from a directory where you copied a DVD’s files to, after all.

For the first disc, this worked just fine. For the second one, not so much. For some reason no program could read the VOB files on the DVD without projectile vomiting error messages to the system logs. (I wound up with 600+ MB of error messages in each of three system log files when all was said and done — log files that are typically around 50 KB for a week’s worth of data. So yeah.)

Since the VOBs are where the actual video content of the DVD is stored, this was a bit of a problem. I ran into the same problem with the third disc I wanted to rip. Thinking it might be a flaky DVD drive or driver, I tried rebooting holly (soft and hard), but no change. First disc fine, second and third not. Each disc played perfectly in my set-top DVD player, so the discs themselves were clearly undamaged. kryten’s external DVD drive wasn’t any more successful.

My best guess as to what was going on was that the discs in question had deliberately bad sectors to serve as copy protection to prevent someone from doing exactly what I was trying to do. But if that were the case, you’d think that all three discs would have had it, since they were all part of the same three-disc set. It doesn’t make much sense for only some of the discs to have copy protection. But if it wasn’t deliberate, it’s awfully suspicious that only the VOB files on the two discs were affected.

I wound up ripping the two problematic discs the easy way, doing everything on holly and having MEncoder read from /dev/dvd directly instead of mounting the UDF filesystem and reading that. Lo and behold, that worked, albeit taking longer to encode because of the slower processor. Whatever method programs use to read from the DVD directly instead of via the filesystem apparently never tries to access the sectors causing the errors.

Given that holly is effectively headless (given the “quality” of ATI’s Linux drivers, I didn’t want to switch from MythTV to the console if I could help it), this posed the question of how to figure out which titles on the DVD were the ones I wanted to rip, and not previews or special features or copyright notices or anything. The solution? Playing each title one by one in MPlayer, running in AAlib mode to render the video in glorious ASCII art though the SSH session from kryten to holly. Converting uncompressed DVD-quality video to ASCII art is a lot more bandwidth-friendly than sending it across the network directly, and while it is hardly the way I’d want to watch a video, it’s good enough to recognize the opening scene is what you’re looking for.

But finally, I now have the videos shrunk down into a format my portable media player is happy with. All it took was to stop trying to be so clever about how I was doing it, and thus avoiding whatever the underlying problem was.


Since I’ve had this running through my head ever since I put last night’s post together, I figured you should have the opportunity to suffer/enjoy it similarly:

(It’s also available in the original Japanese with Engrish subtitles, if you’re in to that sort of thing.)

Comments Off


Speaking of things that are either going to be awesome or completely suck: Mega Man 9 is coming out on WiiWare later this year. And it’s going back to its 8-bit roots:

Mega Man 9 screenshot

If Keiji Inafune is indeed trying to channel the greatness of Mega Man 2, which everyone knows is one of the greatest video games of all time, Mega Man 9 could indeed rescue the series from the mediocrity and repetitiveness it slid into after Mega Man 3.

(Side note: in retrospect, the ability to charge normal shots introduced in Mega Man 4 threw off the game mechanics by making the weapons you get from beating robot masters much less useful. Since charged shots works pretty well against almost everything, there’s little reason to switch weapons unless you need to exploit some gimmicky trajectory they have to get through an area. Mega Man X made it work, but the original series never did.)

(Another side note: I know nobody plays a Mega Man game for the plot, but Capcom wasn’t even trying with Mega Man 6. Not only was it the fourth game in a row with a less-than-credible “no, Dr. Wily isn’t the villain this time, really!!!” premise, but “Mr. X” was clearly just Dr. Wily with a fake beard.)

Anyway, announcements like this are going to finally make me get around to buying a Wii one of these days.

On the other hand, if Mega Man 9 turns out to somehow be three worse than Mega Man 6 was, I’d be willing to play whatever the hell this is (especially the part starting around 5:26):

(Fun fact: if you ever find yourself wondering “is that a …” while watching the above, I assure you, the answer is “yes”.)

(Fun fact: if I put any more parentheses in this post, it might be mistaken for Lisp.)

Even Stephen Colbert thinks it’s over the top

Is it possible that the most patriotic video game ever created was developed and released exclusively in Japan? I am talking, of course, about Metal Wolf Chaos.

The TV Tropes page for it describes it thusly:

Michael Wilson, veteran of the Arizona Conflict and 47th President of the United States has been deposed in a military coup by his running mate, RICHAAAAAAARD! Hawk. Now, he must take up the guise of Metal Wolf and take back America city by city, armed only with his Humongous Mecha and the power of BURNING AMERICAN FREEDOM.

This game could only have been made in Japan.

Metal Wolf Chaos is an original Xbox game made by From Software, unfortunately never released in America. The game is a Humongous Mecha title focused around the highly American pursuit of blowing stuff up, with a plot and dialog that would be the epitome of American Patriotic Fervor (or the most over-the-top satire of it ever made) were it not coming from a different country altogether. Weaponry includes machine guns, rocket launchers, and a shark gun – Yes, a shark gun – while the plot takes you to shootouts in the southwest, bomb threats in Beverly Hills, battles against giant robots in Manhattan, redecorating the White House with missiles, a showdown with Richard in Vegas, and space, assisted along the way by a resistance force skilled only in blocking tank cannons with their helicopters and the President’s slightly psychotic secretary, Jody Crawford.

Naturally, YouTube has videos of this game in action. Note in particular the sequence where the President (and his giant robot), after battling a heavily armored White House, hitches a ride on the side of the space shuttle, blows up a space station, and then surfs the debris back to the surface. Seriously.

I don’t know what else to say. I don’t know what else can be said, aside from wondering whether this sort of post is going to become a yearly tradition.

Comments Off

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 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.

A Tale of Two Doctors

First: did you know that Joss Whedon, of Firefly fame, is working on a musical, Dr. Horrible’s Sing-Along Blog, to be released on the Internet mid-July, for free (initially)? Here is the trailer:

Yes, it’s starring Doogie Howser Neil Patrick Harris. As a pathetic villain. If he’s only half as terrible at villainy as The Monarch, it should still be awesome. Oh, and Mal Reynolds Nathan Fillion is the hero.

Second: You watch Doctor Who, right? Of course you do. Remember last season’s episode The Family of Blood, where The Doctor had recorded a message for Martha before wiping his memories and becoming human? Wonder what he was saying during the parts you didn’t hear?