Bidding System System

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

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

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

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

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

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

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

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

<?xml version="1.0" encoding="UTF-8"?>
        <include path="system" src="stdio.h"/>
                            <string>Hello, world!  I am %s.\n</string>

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

Time is not on your side

For over a year now, I’ve been running MythTV on holly, my seven-plus-years-old former desktop PC, and it’s been working out pretty well. Having a DVR is infinitely more convenient than watching live TV — no having to stay up until midnight to watch The Colbert Report, and being able to trust it to find out when the next season of, say, Frisky Dingo, starts.

Plus, it’s a much better deal economically. Instead of having to lease a DVR-capable digital tuner box from the local cable company (and upgrade to digital cable to use it) and end up having to pay an extra $20 or $25 a month, there’s no extra charge (modulo the one-time need to buy a TV tuner card) to running MythTV.

Or at least, there wasn’t.

Zap2it used to offer TV program listings for free for private, noncommercial use, thus allowing MythTV to know what’s on when. Without that information, a DVR is little more than a VCR that uses a hard drive instead of tapes. But apparently they had problems with people using their free service for non-private and/or commercial things, putting too big a load on their system to continue supporting for free. As a result, their free listings end at the end of the month. So, so much for that.

Luckily, some kind of deal was worked out to offer the same information through newly formed non-profit corporation Schedules Direct for a fee that currently works out to $5/month which, while not being cheap-as-free, is still better than what the cable company offers. (And with luck and a sufficiently large user base, that price will come down.)

The only problem is, a software upgrade is necessary to take advantage of the new source. And as loyal readers may recall, things didn’t work out so well last time I tried upgrading holly, largely thanks to finding out afterwards that ATI dropped support for holly’s video card in their proprietary Linux drivers, the TV-out only half works with the open-source drivers (literally: the top half of the image is stretched over the whole screen, and the bottom half is gone), and holly’s old enough to not be compatible with even the low-end video cards you can buy off the shelf these days. After much frantic struggling to revert the ATI driver packages, as well as the X server packages needed to be compatible with the old driver, I finally managed to get holly back into an operational state. I then vowed never to upgrade anything on it unless absolutely necessary.

Which turned out to be this week.

Amazingly, the upgrade went much more smoothly than I anticipated. Sure, holly’s package management seemed to be FUBAR, with aptitude bombing out whenever you’d try to change anything, but it turned out I had just forgotten to roll back one last package to an older version to make all the versioned dependencies work out. With that fixed, upgrading all the software went pretty smoothly. All the software except, of course, for the video drivers and the X server; holly’s MOTD threatens violence if I dare upgrade those, and I know the guy who wrote that will totally follow up on that. I had been concerned that having an older version of the X server could cause dependency problems, since new packages generally depend on the current-when-built versions of their dependencies, but thanks to X’s client/server architecture, applications depend on the libraries that talk to the X server, rather than the server itself (which, after all, could be elsewhere on the network). Fiddling with the nightly cron job to use the new listings source wasn’t too difficult and seems to be working, though it’ll take a little time to test properly.


Almost. Somehow, during the upgrade, something decided to change holly’s time zone from Eastern to something in western Alaska (which happened to be the first alphabetically in the list). I have no idea how that happened, especially since I never ran into that problem on kryten. Luckily I checked up on holly to make sure it was recording the next thing scheduled and got suspicious when it was still listed as “will record” even half an hour into it. (And doubly luckily, the episode appears to be downloadable anyway, so no loss anyway.)

Given everything that could have gone wrong with this mass upgrade of hundreds of packages after eight months of not tracking unstable, it’s the time zone that got screwed up.

I hate you, Murphy.

What happened to Wallace anyway?

So it’s been several months since the last Wallace update. What’s been going on since then. Well, not much.

It may surprise you, but the main reason I sort of wandered away from it has been frustration with getting GStreamer to do what I wanted it to. I wanted to use GStreamer for the audio/video output since then I effectively get video encoding for free: it’s just a matter of building a pipeline that sends the output to a video file instead of the screen and speakers.

However, my skills at writing GStreamer elements are wanting at best, and the fact that the design I was going for — a real-time source that has separate audio and video sources — was a bit more advanced than what’s covered in the beginners’ documentation. Everything suddenly got to a point where sending the A/V to the speakers and screen would either hang the program or cause a very noticable amount of desync. I think I also managed to track part of it to a bug in GStreamer at the time, which presumably has since been fixed, but I never really went back to the code after throwing my hands up.

On the actual what-the-program-is-supposed-to-be-doing front, I’ve come to the conclusion that to do things “right” would require having some degree of debugging/disassembly features in Wallace, to allow you to pick apart the game and figure out what’s going on inside it. There’s some things — in particular, determining the player’s position within a level — that just can’t be done without getting at whatever internal state the game uses to keep track of it.

Of course, doing that would entail treating the emulator code (which I took from FCE Ultra) less like a black box. While the emulation itself is pretty solid, the source code to it, while not quite being WTF-worthy, is hardly the easiest thing to understand, especially if you aren’t intimitely familiar with the NES’s internals.

Reverse engineering a game is certainly possible. After all, ROM hacks aren’t hard to find — for example, look one post down — and can certainly require a good understanding of the game’s code and data to pull off. It’s just that that’s more effort that would be required to have some degree of reverse engineering support in Wallace.

And looking farther out, assuming everything else gets worked out, it all comes down to how much processing power you can throw at “growing” your “solution”. And unless someone suddenly donates me a 500 YHz processor, that’ll involve distributed computing, which to implement well would require (among other things) splitting the emulator core and the genetic algorithm into separate libraries, to minimize the dependencies on the distributed client code. Which wouldn’t be all that difficult in principle, as FCE Ultra already had a quasi-library-like interface, but it was geared towards code that got directly linked in, and the function calls went both ways. So, it’s just one more thing to clean up.

Plus, having gotten distracted by a shiny new thing to work on is only going to delay things further. I’d at least like to get its AI to the point where it can’t be beaten by whatever’s been growing in my old college dorm refridgerator for the past five years or so before running off to something else.

So, to answer your question Ryan, in theory, yes, Wallace could play it. In theory. In theory, communism works. In theory.

Comments Off

Thank goodness I have W blue-sky lives

One can, I am told, have fun with hacked versions of Super Mario Bros.

Others might not: (warning: copious, but well-justified, NSFW language)

And if you think that hack is evil, take a gander at this:

Yes, there is an explanation of just WTF is going on there. And yes, there is a faster speedrun out there, but the one above is much more entertaining.

Only old ladies play bridge

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

Old Lady 0.1.0 screenshot

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

I may have been overly hasty…

I may have to retract my earlier dismissal of Rebuild on laughably little information, given how the two trailers floating around on YouTube don’t look half bad. (The soundtrack backing them was of course inevitable, but there’s not much you can do about that.)

I’m not sure whether I should be proud of the fact that I can readily identify the scenes from which 95% of the clips in each trailer are from. Probably not.

Comments Off

Doctor When?

One nifty thing about programming your open-source DVR box to record any episodes of Doctor Who that air (with the intention of watching the new episodes), is that when the local PBS affiliate starts running the old episodes at midnight on weekends, those get recorded too.

Ah, the good old days where the monster-of-the-week was obviously a guy in a rubber suit who couldn’t see out of his costume, forced to walk slowly with arms flailing in front of him to avoid running into the set. (That’s right, Nimon, I’m looking at you.) The days when the spaceships and phone booths were all done with models instead of computer graphics. The days when theme music played on a synthesizer sounded futuristic.

The only problem is that MPT started near the beginning of a stretch of Dalek-free episodes. *sigh*

Comments Off

Cyberterrorism for Dummies

So! You’re a disgruntled ex-government employee out for revenge and/or to make a truckload of cash. To achieve those goals, you’ve arranged for a series of crippling cyberterrorist attacks against the nation’s infrastructure that will a) stick it to everyone who laughed at your warnings about crippling cyberterrorist attacks and b) write yourself a check for $ALL out of America’s economy while everyone’s too distracted trying to not die. You’ve assembled a crack team of hackers and a kung-fu chick, rented out a big rig to stick them all in, and made sure your technobabble is completely credible.

There’s only one problem: Bruce Willis is going to track you down and kick your ass. If he finds you, you’re dead. He can’t be stopped. He can’t be killed. That’s a fact of life. You know those movies where he dies in the end, or turns out to be dead the whole time? That’s him acting. He’s not acting now. Chuck Norris has nightmares about what Bruce Willis can do to him, and you, sir, are no Chuck Norris. You’re not even a Bruce Schneier.

The good news is, Bruce Willis doesn’t know who you are. The bad news is, you know all those l33t h4><0r d00dz you outsourced the prep work to? They know who you are. Bruce Willis doesn’t have to find you — he just has to find them.

Luckily, you’ve given a little thought to how to deal with the h4><0rz. You’ve been careful to only hire h4><0rz whose PCs have been manufactured in China. As everyone knows, these days every single one of China’s exports is guaranteed to have some sort of deadly little extra. In this case, someone at the factory thought it would be a good idea to strap a couple blocks of C-4 to the motherboard. Now all you have to do is detonate it while they’re surfing the ol’ Ted Stevens Memorial Series of Tubes, and you’ve taken care of both the h4><0r and all the evidence on his hard drive in one fell swoop. Er, blast.

So far, so good. But here’s where you plan starts to go off the rails. You’ve sent your Guys With Guns to watch from across the street to make sure the job gets done. But instead of just detonating the C-4 remotely like any sane terrorist would do, you have them upload a “virus” to the computer, and it will detonate the C-4. OK, I guess that’ll work, in case you don’t want the Guys With Guns to be the Guys With Binoculars And A Remote Detonator. So, the (sigh) “virus” will wait to see some user input to make sure someone’s there, and then detonate, right?

No? The victim has to hit the Delete key to trigger the “virus”? What, the Any key wasn’t good enough? What if the victim’s more of a Backspace man? I mean, I guess you could’ve picked a worse key to use as the trigger (SysRq anyone? Didn’t even know you had one of those, did you?). What if hitting Delete gives him superpowers instead? (It’d make as much sense….) But still, how do you know he’s going to press it before Bruce Willis comes a-knockin’?

You’re… you’re going to make his screen go all weird like a busted TV? Are you serious? First of all, that’s not a sinister plot, that’s a screensaver. Second, wouldn’t that just get the victim to check his video cables? Why would he use the Delete key to try to fix that? These people are supposed to know a thing or two about computers, aren’t they?

Uh oh, is that Bruce Willis knocking on the guy’s door before he reaches for the Delete key? Better get out of there — pretty soon Bruce Willis will be in ur victim’s apartment, killing ur doodz.