Paul Kuliniewicz

The GNOME Panel Applet Library Reference Manual mentions the following about the panel_applet_set_size_hints function:

Set a list of desired size ranges for an applet with the PANEL_APPLET_EXPAND_MAJOR flags set.

This is a lie. The applet must also have the PANEL_APPLET_HAS_HANDLE flag set; otherwise, the applet will not display after you call the function.

Why? panel_applet_set_size_hints packages its arguments up in a Bonobo (i.e., CORBA) message and sends them to the PanelAppletFrame object that manages the space allocated to the applet in the panel. They eventually find their way to the following internal function, which is supposed to do the actual setting of the size hints:

This function is supposed to set up the size_hints array with the list of hints that you originally passed to panel_applet_set_size_hints. However, it only populates the array if the applet has a handle — i.e., if it has the PANEL_APPLET_HAS_HANDLE flag set. If it doesn’t, the array stays initialized to all zeros, which the panel is for some reason perfectly OK with. Now your applet is guaranteed to be exactly 0 pixels in size, and thus invisible.

This is really a bug in the GNOME Panel, since it should handle the case where there isn’t a handle. (No pun intended.) Since the two applets shipped with GNOME that set size hints both use handles, apparently nobody noticed until now. I’ll file a bug tomorrow about this.

Remember kids, the moral is: trust the source code, not the documentation.

Last time, I mentioned one obstacle I ran into when writing a reverse engineering tool for Nintendo games. Namely, just because a piece of code is called using the JSR (Jump to SubRoutine) instruction doesn’t mean the code being called actually is a subroutine. Subroutines eventually execute an RTS (ReTurn from Subroutine) instruction to go back to the code immediately following the JSR. This bit of code in Super Mario Bros., however, doesn’t:

As I mentioned before, the above code treats the “return address” that JSR pushed onto the call stack as the address of a jump table, with the index into the jump table passed in the A register.

The reverse engineering tool needs to be aware of this, since otherwise it won’t know about the jump table, and thus won’t find the executable code pointed to by the jump table’s entries.

To solve this problem, I added a little static analysis routine that inspects all the code called by a JSR, checking for stack-based shenanigans. A normal subroutine may push and pop values on and off the call stack, but it will leave the return address alone, and when the RTS is reached, the return address will be at the top of the stack. A jump table engine like the above will pop the “return address” off the stack and end not with a RTS but with an indirect JMP (JuMP). Truly weird code will do something else.

My program now uses the Boost Graph Library to build a control flow graph of the executable code it’s located, showing all the possible paths of execution through the program. The analysis runs as a depth-first traversal of each alleged subroutine, checking what the depth of the call stack will be at each instruction.

Naturally, the analysis is only a heuristic. It’s possible for the code to be a normal subroutine and look like a jump table engine if, say, it manually pops the return address off the call stack and does an indirect JMP to it instead of an RTS. I’m making the assumption that the code isn’t deliberately obfuscated like that.

During testing, I tried running the jump table engine detector against Mega Man to see what would happen, and look at what it found:

The details of how it works are different (it passes the index in the X register instead of A, and it only uses two bytes of zero-page memory instead of four), but it does the same thing as the jump table engine in Super Mario Bros. The fact that my detector seems to work on two different games written by two different developers is a good sign — both that the detector works, and that the jump-table-via-subroutine trick is likely to be used in many games. (The detector also found a few subroutines that do some other form of stack weirdness, but I haven’t look yet at just what’s going on with those.)

The reverse engineering tool doesn’t actually make use of this new information yet, but that’s the next thing on the to-do list.

In case you’re wondering what I’ve been up to with the relative silence here lately, for some reason I’ve decided to write a reverse engineering tool for NES games. This might eventually lead to answering a long-standing question, or even lead into a revival of Wallace.

One of the challenges with writing such a tool is figuring out just what the various bytes in a ROM image even mean. In most operating systems, the internal structure of executable files contains some structural information. In particular, the executable code itself (aka .text, counterintuitively) is stored separately from global data (aka .data) that the executable code uses. So right off the bat, you can find the machine code and disassemble it back into something fairly readable.

No such luck with a NES ROM image. While there is segmentation in the file format, it’s based on whether the memory bank in question is part of CPU memory (PRG, or “program”, banks) or PPU memory (CHR, or “character”, banks). CHR banks contain the pattern tables that store the game’s graphics, so those are pretty straightforward to interpret.

However, PRG banks store both code and data in whatever layout the developers chose to. All you have to go by is the fact that the uppermost 6 bytes of CPU memory contain pointers to three pieces of code: the non-maskable interrupt handler (invoked by the PPU), the reset handler (invoked after power-on or reset), and the software interrupt handler (invoked by the BRK instruction). That’s all you know for sure about the memory layout.

In principle, this is enough. You can start at the addresses indicated by those pointers and start reading off instructions, following any branches or jumps along the way. We aren’t actually executing anything, just stepping through the structure of the code to find where all the instructions are. We don’t know what the program will actually do when it executes — for example, we don’t know which way a branch will go — but for our static analysis, we can just trace both code paths until we run out of code. When we’re done, everything we’ve reached is an instruction and can be disassembled, and anything else is data (or filler).

Of course, since nothing can be easy, this static control flow analysis fails if the program does anything tricky. Chances of running into something tricky are pretty good. For example, take a look at this bit of code from a full disassembly of Super Mario Bros.:

JSR is the “jump to subroutine” instruction: it pushes the address of the following instruction onto the stack and jumps to the specified address. When an RTS (”return from subroutine”) is executed, that return address gets popped off the stack and jumped to. So, normally, the code after a JSR will get executed once the called subroutine does an RTS.

But clearly, that’s not what’s happening here, since we have eight bytes of data immediately following the JSR, instead of code. In particular, four 16-bit addresses. Needless to say, my current executable-code-detection algorithm chokes on this. What’s going on? The code for the JumpEngine “subroutine” reveals all:

For those who don’t speak 6502, this is basically a clever way of implementing a jump table. On entry, the A register contains the index of the table, and the top of the stack contains the address of the jump table itself. The routine multiplies A by 2 (the size in bytes of an address) and stores it in index register Y. It then writes the Yth entry in the jump table to memory address $0006, and then jumps to the address stored there.

The slightly convoluted routine to implement this is needed to get around the limitations of the 6502 processor — in particular, the fact that registers are too small to store an address. But for our purposes, this sort of thing demonstrates that we can’t blindly assume a JSR invokes a “normal” subroutine — we have to check whether the alleged subroutine does any kind of stack trickery like that, and if it does, not assume that the instructions following the JSR will get called.

Of course, since now I have a need to do two kinds of static analysis (the “executable code detector” and the “tricky subroutine detector”), ad hoc navigation methods through the PRG banks won’t cut it. Luckily, it looks like the Boost Graph Library will give me a fairly easy way to make the PRG banks look like a proper graph (without actually having to build one explicitly), at which time I can implement static analysis routines using standard graph traversal algorithms. That shouldn’t be too hard — most problems there will probably come from learning how to write the necessary wrappers around my classes.

Also, note how I’ve been talking as though I know for certain where each of the PRG banks will appear in memory. Well, nothing can be easy. NES ROMs make use of mappers, which swap different PRG and CHR banks into memory at runtime, sort of like how a virtual memory system does paging. Dozens of different mappers exist, each with different possible behavior. With just static analysis, all I can go off of is knowing which set of banks might be mapped to which ranges of addresses, without knowing which combinations will actually exist at runtime.

In fact, if writing an emulator, implementing the CPU is arguably the easiest part. The real pain comes in trying to implement each of the mappers, which vary widely from ROM to ROM based on whichever crazy hardware the developers used to get around the Nintendo’s memory limitations. No standardization whatsoever.

Of course, there’s lots of other challenges to reverse engineering a ROM. I haven’t even covered everything about just figuring out which bytes are for what — figuring out the text table, for example, has its own interesting issues. And that’s before we get to the point of actually figuring out what the ROM does when you run it.

If this were a program to generate driving directions, it’s still at the point of trying to figure out which squiggles on the map are roads and which are rivers. A critical thing, sure, but still a long way from the goal.

Music Applet 2.4.2 is out. This is another bugfix-and-translation-updates-only release. In particular, it fixes the slow creep in CPU usage after each song and updates the Polish (pl) translation.

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:

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:

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:

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:

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:

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:

And now defining what a balanced hand means is easy:

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:

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 2¹³ = 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.

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.

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.

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 2³⁵.

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:

Which can be simplified a bit to:

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:

Which is roughly 9.7 x 10⁴⁶, 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 10²⁸, or exactly 53,644,737,765,488,792,839,237,440,000.]

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.

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.

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.

Music Applet 2.4.0 has just been released. The main change is that it now supports the recently-released Banshee 1.0, in addition to older versions of Banshee. There’s also improved support for debugging crashes, as well as an updated Czech (cs) translation.

Unfortunately, the new version of Banshee doesn’t provide a way to manipulate song ratings. Once that gets fixed in Banshee, I’ll update Music Applet accordingly.

A few technical notes on Banshee 1.0 support: since this new version of Banshee completely changed its D-Bus interface, there’s now two plugins for Banshee: the old one and the new one. While it’s inelegant to have two plugins for what the user sees as one program, it’s the only reasonable technical solution, given that the two versions of Banshee are completely different as far as Music Applet is concerned. If you have problems with Banshee support after upgrading the applet, check to make sure the new plugin (now called “Banshee”) is enabled. The old plugin has been renamed “Banshee (pre-1.0)”. I have no plans to remove support for old versions of Banshee any time soon.

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.

OK, maybe I’m not quite done with computing Fibonacci numbers. I’ve been playing around a bit with Haskell lately. Here’s what the Haskell equivalent of the C code I posted earlier is:

Most of the volume there is trying to mimic the same error handling I was doing in the C code in main. However, the code that computes Fibonacci numbers is much shorter. In C, I had to write a whole function. In Haskell, it’s a one-liner. Here it is again:

If you haven’t been exposed to Haskell before, that might make your head explode. Note that it isn’t a function at all. It’s a list of all Fibonacci numbers.

Yes, the Fibonacci sequence is infinitely long. Haskell is fine with that.

Yes, my definition is recursive. Haskell is also fine with that.

This works because Haskell is lazy: it only computes things at the point when the result of the computation is actually used. At runtime, it only actually computes the elements of the list up to the one that’s requested by the user, instead of trying to create an infinitely large list and then indexing into it. That’s also why the recursive definition works: each element is defined solely in terms of the elements that come before it, and I provide the first two elements explicitly.

Specifically, what’s going on in that line is this. zipWith takes two lists, performs an operation on pairs of elements taken from each list, and returns a list of the result of that operation. Here, the operation is (+), plain old addition. The two lists are the Fibonacci sequence we’re defining (fibonacci), and the Fibonacci sequence with the first element dropped off (drop 1 fibonacci).

For example, the first element produced by the zipWith expression takes the first element from fibonacci, which is 0, and the first element from drop 1 fibonacci, which is 1, adds them together to get 1, and returns that as the third element of fibonacci. For the fourth element, it takes 1 and 1 and returns 2. For the fifth element, it takes 1 and 2 and returns 3. And so on, as long as it needs to.

For the visually inclined, try this:

   0   1   1   2   3   5   8  13  21  34  ...   (fibonacci)
+  1   1   2   3   5   8  13  21  34  55  ...   (drop 1 fibonacci)
------------------------------------------------------------------
   1   2   3   5   8  13  21  34  55  89  ...   (drop 2 fibonacci)

Infinite lists aren’t unusual in Haskell. In fact, the standard library (called the Prelude), has several functions designed to help you create infinite lists.

Needless to say, trying to do this in a non-lazy language is a recipe for disaster. Your program will run until either the heat death of the universe or it runs out of memory (whichever comes first) building the infinite list and will never get around to actually using it.

This is at the core of why it’s worth studying other programming languages, even if you don’t expect to use them. You can often learn new ways to look at problems that you’d never even consider if you stick with a single language. No C programmer would ever compute Fibonacci numbers by constructing a list of all of them, but in Haskell, it’s downright natural.

A new release of Music Applet, version 2.3.1, is now available. This is primary a brown-paper-bag release, fixing the crasher that, in hindsight, probably affected everyone trying to use 2.3.0. If you were one of them, try upgrading to 2.3.1 and see if that fixes things for you.

For those interested, I’ve done a write-up of what was causing the bug and why it took me so long to figure it out.

There’s also a few other bug fixes, as well as a bunch of new translations for Czech (cs), German (de), Spanish (es), French (fr_FR), and Russian (ru).

For those of you who ran into the bug in Music Applet 2.3.0 where the applet would seem to crash as soon as you started it, well, I finally figured out what was going on. It turns out to be a blatant brown-paper-bag bug, and to proper chastise myself for releasing Music Applet with it, I will now detail what its cause was and how I discovered it.

Since I have Debian’s music-applet package installed, during development I install the new code in a separate directory and run it from there. This leaves the problem of actually loading the applet from its nonstandard location. Normally, when you add an applet to a panel, Bonobo checks its database to see what program needs to be run. However, if the program is already running, it will connect to it instead of starting a new instance. So, when testing new code, I start the new applet code from the command line, and then add it to the panel.

This way, I don’t have to touch the system files to run the new code. This method also gives me an opportunity to augment the Python path with the directory where the new code’s modules are, since naturally they’re in a nonstandard location too. It furthermore has the advantage of printing the output on stdout and stderr to the console, whereas if Bonobo started the applet, they’d wind up in /dev/null, which is bad for debugging.

Now, several people reported the crash-on-startup-if-Amarok-support-is-enabled bug, but I was completely unable to reproduce it on my system. None of them had a stacktrace or core file or any other debugging output to offer. However, they were all using Ubuntu and Python 2.5, whereas Debian still uses Python 2.4 by default. It looked like the trouble might lie there.

After jumping through hoops to get the applet running on my system under Python 2.5 (complicated by the fact that Debian for some reason doesn’t have versions of the DCOP modules for Python 2.5), I still wasn’t able to reproduce the problem. Naturally, if I can’t reproduce the problem, and I can’t get any good details from the bug reports, I can’t figure out what’s causing the bug, let alone verify that any fix I come up with works.

I finally decided to go all-out and try to reproduce the exact circumstances of the crash on my machine, without completely wrecking the copy of the applet provided by Debian. I hacked the Bonobo .server file for the applet to point to the local copy of the applet, and then hacked the applet startup code to explicitly run under Python 2.5. Oddly, when the applet started, it would identify its version of 2.2.1 (the version provided in Debian) and not 2.3.0.bzr (the version installed locally), nor would it have any of the features added in 2.3.0, including the Amarok plugin.

After banging my head on this for a while, I realized that even though Bonobo was running the local copy of the applet’s startup code, that startup code was then loading the support modules installed in the system paths — the 2.2.1 code — instead of the local code. When starting the applet from Bonobo, there’s no opportunity to tweak the include path like you get from the command line. I then further hacked the applet to add the right paths to sys.path, and finally it started working, in that it stopped working and crashed like it was supposed to. Or, not supposed to, but you know what I mean.

Finally, I was getting somewhere. To track down the line causing the crash, I started putting lines like this in the code to trace the control flow:

os.system("xmessage 'About to start thread'")

This would pop up a crude dialog box with the message, which I relied on instead of printing to stdout or stderr since, well, those were going to /dev/null now. After playing around with things for a while, I tracked down the offending line of code:

self.__plugin._app = kdecore.KApplication (sys.argv, "music-applet")

Thinking it might be throwing an exception for some reason, I tried wrapping it in a try/except block, but no luck. That was definitely the line, but still no clue why it was failing so spectacularly. Thinking there might be something on stdout or stderr that could help, I realized I could point them at files on applet startup so I could read them after the fact:

sys.stdout = open ("/home/paul/music-applet/debug.stdout")
sys.stderr = open (”/home/paul/music-applet/debug.stderr”)

Now I was seeing the normal debugging spew from the applet, but still no messages about the crash. It then hit me that this was only going to affect my Python code; everything else would still be using the “true” stdout and stderr. I’d have to literally dupe the system into redirecting the underlying file descriptors into writing into my debug files:

new_stdout = open ("/home/paul/music-applet/debug.stdout", "w")
new_stderr = open (”/home/paul/music-applet/debug.stderr”, “w”)
 
os.dup2(new_stdout.fileno(), sys.stdout.fileno())
os.dup2(new_stderr.fileno(), sys.stderr.fileno())

Aha! Now this showed up in the output right before the crash:

music-applet: Unknown option ‘--oaf-activate-iid=OAFIID:GNOME_Music_Applet_Factory’.
music-applet: Use --help to get a list of available command line options.

That option is one of the things that Bonobo puts on the command line when it starts an applet, and isn’t one of the things I was giving to the applet when launching it manually. Aha? Checking the source code of the KDE libraries for that error message turned up this:

void
KCmdLineArgs::usage(const QString &error)
{
    assert(KGlobal::_locale);
    QCString localError = error.local8Bit();
    if (localError[error.length()-1] == ‘\n’)
  localError = localError.left(error.length()-1);
    fprintf(stderr, “%s: %s\n”, argv[0], localError.data());
 
    QString tmp = i18n(”Use --help to get a list of available command line options.”);
    localError = tmp.local8Bit();
    fprintf(stderr, “%s: %s\n”, argv[0], localError.data());
    exit(254);
}

Aha! The KApplication constructor indirectly calls this when it sees something on the command line it doesn’t understand. It prints a message to stderr, and them immediately exits the program! The applet wasn’t crashing; the KDE libraries were terminating it because they didn’t understand the command-line arguments Bonobo uses!

Here’s where that brown paper bag comes in: this bug would affect anyone relying on Bonobo to start the applet. In other words, everyone who isn’t me. By always starting the applet from the command line first, I never tested the applet in the same runtime configuration that everyone else on the planet would be using, and so never encountered a bug that everyone else would suffer. The whole Python version thing was a red herring.

Now that I finally knew what was happening, the fix was trivial: strip out any command-line arguments before calling the KApplication constructor:

fake_argv = sys.argv[0:1]
self.__plugin._app = kdecore.KApplication (fake_argv, “music-applet”)

However, I still maintain that if there is a hell, there is a special place in it reserved for people who write libraries that call exit(), and thus do not give the user of the library an opportunity to try to recover from an error.

Needless to say, this bug is fixed in 2.3.1.