Computer Games

When computers finally managed to beat us at chess, a game of ingenious human invention, we did not say they were now officially smarter than us. What we did was give computers another game - another puzzle to struggle with.

Go is a board game that is a magnitude more complex than chess. Whereas computers could memorize well studied opening books for chess, such a strategy is unmanageable for Go, since there are 361 possibilities... for the first move alone. Today's fastest computers with the best Go algorithms are still beaten by human players with a few months of experience - mere novices.


I believe that computers will one day manage to beat us at Go. But that is a discussion for another time. Now I want to talk about what game, what puzzle we will toss future-computers after that, to assuage ourselves that NO - they are still not smarter.

Settlers of Catan is a board game that is a magnitude more complex than Go. Whereas future-computers only had to think about winning or losing for Go, a binary 1/0 that they are familiar with, such a strategy simply doesn't work for Settlers, since bartering between players involves the hazy variables of human psychology that computers are ill-equipped to define. First there is the game. It is played on a board, which has over a million different possible configurations - and that's before any player has had a turn.

Then there is the meta-game. It involves players bartering with each other, forming alliances, and knowing when to stab their former partners in the back. To give you an example of how complex the thought process can be, we need to take a quick diversion.


From personal experience, I've seen a human player propose an ingenious trade, that would have given her an enormous advantage. To fully understand the significance however, you first need to understand more about the game. Victory in Settlers is achieved when a player has 10 victory points. There is a longest road development card, which is awarded to whichever player has the longest road* of at least 5 segments. It is worth 2 victory points.

You also need to understand more about this particular instance of the game. There were four players. The human player and another player (let's call him the opponent) were both just mere points away from victory. One of the two other players currently held the longest road card. However the opponent had two large sections of road, and if he was able to connect them, held a good chance of gaining the longest road card for himself.

The human player proposed that she refrain from building a road at a position where it would block the opponent from connecting his two road sections in return for him giving one of his resource cards on every turn to her for the rest of the game (like a tax). Right as the opponent was about to agree to this outrageous deal (remember he still might not have gotten the longest road card), the human player realized it was better to take away all possibility of the opponent gaining the longest road card, and she built the road anyway.

What will happen when future-computers beat us at Settlers of Catan? That's when we can say they are officially smarter than us - and be right.


* The length of a road is the longest possible segment, not counting branches.

Business Card

Look at that subtle off-white coloring.

The tasteful thickness of it.

Oh my God, it even has a watermark QR Code!

Doorbell Hacking

What's the first thing a thief does when he's casing a house? Ring the doorbell to see if anyone's at home, right? If someone answers, he can play it off like he's a door-to-door camera peddler or some kind of religious fanatic. If nobody answers, it's a good sign that the house is empty and ripe for the picking. The burglar proceeds to break in and steal everything that catches his fancy, including the ancient Chinese sword, the antique Italian restaurant menu, and the highly-valuable anime pencil-sketches. Meanwhile, the owner comes home to find all his shit missing, but there's nothing he can do because the perp is long gone.

Well, it's a different story when it comes to my house. Shortly after the thief rings my doorbell, I get an SMS message on my phone. I then rush home as fast as I can, where I find him struggling to lift the TV. I quietly grab my can of mace, sneak up behind him, yell "Surprise Motherfucker!", and get him good in the eyes (which are the testicles of the face). I am called a hero by my friends and neighbors.

This is how it works: My house has an oldschool mechanical doorbell. Normally, pressing the doorbell closes a circuit that activates an electromagnet which slams the chime against the tone bar. I bought a 12V reed relay from Radio Shack and hooked it up in parallel so that pressing the doorbell also activates the relay. This sends a signal to my computer (I'm glossing over this part because it's a bit complicated and involves a Phidget, not to be confused with a midget).

There's a program running on the computer that listens for the signal and makes a status update to Twitter user baic_house using Twitter's REST API. My main Twitter account follows baic_house and is set up to recieve an SMS message whenever baic_house makes an update. The whole process from pressing the doorbell to SMS message recieved on phone only takes a few seconds.

Image Editing with Java and Excel

Here's a nice 2560x1600 image I found the other day. I thought I had the perfect desktop wallpaper, except there was this unsightly dark rectangle on the left side of the image. I'm the kind of guy who gets irked by dead pixels on my monitors and TVs; I can't enjoy a movie unless the picture is perfect. So, there was no way I could use this wallpaper as is. However, it seemed like such a travesty to waste an otherwise perfectly good image.

First, I tried trusty old Photoshop. I selected the dark rectangle and applied the brightness/contrast filter. But alas, it seemed like no combination of brightness and contrast values did the trick of completely removing the rectangle.

After a little thought, I realized that the dark rectangle is really just a function, mapping the original pixel value to another pixel value. If I knew what that function was, I could apply the inverse function and restore the original pixel values! Finding that function is the tricky part. If I could only get a good sample of original pixel values and corresponding dark pixel values, I could approximate it however. Then it hit me; I could look at the right edge of the dark rectangle. Pixel values generally don't change too much over just a few pixels, so I could take the pixel just to the right of the edge to be the original value and take the pixel just to the left of the edge to be the corresponding dark pixel value! Of course, JPEG artifacts and high texture areas in the image would make the data a bit noisy, but the idea should still work.

I wrote a quick Java program to get the data. The program went down the edge, making a map from original pixel value to a list of all corresponding dark pixel values. When finished, it would output all the original pixel value it had seen, and the average corresponding dark pixel value. I had it only output the original value if it had seen it at least 3 times (to reduce noise in the data). I then imported the data into Excel, made a scatter chart, and computed a liner regression.

I created another Java program to apply the inverse function to the rectangle. This is the final result. You can still make out the outline of the rectangle, but it's much better than before.

Dual 30" Monitors

Dependency Graph

In order to play Tales of Vesperia, I need an XBOX360.

In order to use an XBOX360, I need an HD TV and a TV stand.

In order to enjoy the TV, I need a couch and a coffee table.

In order to acquire a couch, I need to rent a truck.



I think I'll stick with PC gaming for now.

Dell 3008WFP Input Lag

I've been watching the 3008WFP monitor like a hawk on Dell's website, and it's price has never dropped below $2000. I've also called Dell to order it twice, but gave up after only managing to negotiate the price down a measly $50. Even after pointing them to this forum thread where people were getting $400 discounts and more. I'm pretty bad at negotiating.

So I'm about ready to just give in and order the 3007WFP HC, which can be had for $1200. It doesn't have as wide a color gamut, and it only has DVI input, but other than that, it's about the same. In fact, you could say it's better since it has less input lag. That extra 30ms input lag could mean the difference between life and death when playing TF2 right?

I know, sour grapes...

Ubuntu

Yet another reason why Ubuntu 8.04 is teh awesome.

Java Color Console

Here's a Java snippet that prints color output to the console (in a VT100 emulating terminal, i.e., in linux only):

for (int i = 30; i < 38; i++) {
System.out.println("\033[" + i + "mHello " +
 "\033[1;" + i + "mWorld!\033[m");
}

It works by "printing" special terminal control commands that change the color. There are other VT100 terminal control commands that let you move the cursor around, clear the screen, and other things.

Who needs Swing, when you can make old-school ASCII interfaces, right? No fancy libraries required either.

AMIP

I've been searching for a way to make using iTunes more bearable. There are only two reasons I keep it around: I need it to sync with my iPhone, and I need it to keep track of my playcounts (I don't rate my music, I just use playcounts). It's a terribly slow and bulky music player, and I would ditch it for Winamp in a heartbeat if not for the reasons I just mentioned. Winamp is much much faster and has features I need like, global hotkeys, jump-to dialog, better visualizations, and smooth fade on play/pause.

Thank God there's AMIP. AMIP is like the Swiss Army knife of plugins - it can do almost anything and is compatible with every popular music player. You need to download the version of AMIP for your player and the AMIP Configurator. Out-of-the-box you get the extremely useful search/jump feature, much like Winamp's jump-to dialog. Just press the hotkey to bring up the search/jump box, start typing the song you want and see the results filter down as you type, then hit enter to play the song and make the box go away.

AMIP's original purpose was to automatically announce the song your were playing to IRC, which is something I have no interest in. I am however, very interested in AMIP's ability to act as a server and the SDKs available to write your own client. In particular, the Java SDK makes it extremely easy to write a Java AMIP client.

You may be wondering what this means. Who cares if AMIP can act as a server? Why would you want to write a client? Well, it means that you have a substantial amount of control over your music player. It means, if you want, you never have to look at your player's slow ugly UI again; you can just keep it minimized and interact with it through your own homegrown frontend, personalized to show exactly the info you want with only the controls you want. It means you can log much more about your music listening habits, not just how many times you played each song, but when you played it, what other songs you played it with, and how much of it you listened to. It means you can control your player over a network, across your house on your LAN or across the internet (if you really wanted to).

Lego RCX Programming

I have two Lego RCX units sitting around as part of a large Lego collection. When I first got them about four years ago I played with them intensely. I would look at other people's designs online and then spend hours building cool things with them. This was about six months before I started college, where I didn't have access to them at all. Since I graduated, I have my Lego collection again, but I haven't really had time to do anything with them. Until now.

Four years is a long time when you're talking about technology. While I though my RCX units were the coolest thing ever four years ago, they've now lost some of their appeal (due to Lego releasing their second generation NXT based robotics kit, and me getting older among other things). Four years is also enough time to make the serial port virtually obsolete (try finding a modern-day laptop that has one, mine certainly doesn't). Of course, a serial port is exactly what I needed to connect the IR tower, which communicates with the RCX, to a computer. Luckily, I was able to find a USB to Serial adapter at Fry's for $25.

After hooking everything up and installing the Lego software, I was reminded of how outdated it was when I saw the unskippable intro movie with the terrible compression and the lame 3D graphics that was considered cool back in the day. Even four years ago, I felt Lego's programming language and IDE was overly simplistic, meant more for the 8-14 age group. Now, after three years of school to get a CS degree and half a year of working in the industry, there was no way I was going to program my RCX by dragging brightly colored blocks around, listening to a voice guide me through the tutorials, and watching that cheesy intro movie every time I wanted to edit my program!

Thankfully people have made several of their own languages for programming the RCX. NQC or Not Quite C is one such language based on a simplified version of C. I was surprised to find that the nqc binary not only lets you compile and download programs to the RCX, it also lets you sent raw commands via IR, which basically allows to remotely control everything about the RCX if you know the right opcodes! Good thing someone has compiled a list of opcodes.

As an added bonus, nqc is a command line program, so it can easily be called from other programming languages, like Java, my language of choice. This definitely opens up a whole slew of interesting possibilities.

mailto Bug in Vista

Something really weird happens in Vista when I click on mailto links in Firefox (Here's an example of the links that I'm talking about: email someone). When I try to open any mailto links in Firefox, Internet Explorer opens and tries to handle the link. A few seconds later 35 additional IE windows open in rapid succession for a total of 36 IE windows open! While the windows are fairly easy to close since they are grouped together, it's still extremely annoying that 36 windows pop up whenever I click on a mailto link.

How to Fix
I think the problem may have something to do with not setting up Microsoft Outlook even though it's the default email client in Vista. Since I detest Outlook, I'm not going to set it up.

Instead, I installed this Firefox Greasemonkey script to rewrite all mailto links in a webpage to open with Gmail in a new compose window.

In addition, I went into about:config and set the key network.protocol-handler.external.mailto to be false instead of true. This now has Firefox do nothing when you right click on a page and select "Send Link...".

How to do Backups with xcopy

The DOS xcopy command is like the copy command, on crack. Here's how you can use it to do incremental backups (only copies new or changed files).

xcopy "D:\Andy's Files\*" "I:\BACKUP\Data\" /h /r /s /e /i /c /y /d

Where "D:\Andy's Files\*" is the directory to back up and "I:\BACKUP\Data\" is the directory to back up to. /h copies hidden files, /r overrides read-only files, /s /e copies subdirectories including empty ones, /i assumes the destination to be a directory, /c continues even if errors occur, /y doesn't warn on overiding files, and /d copies only files that are newer than the destination file.

Blue Screening Vista

I thought Windows Vista was supposed to be more stable than XP. Last night I experienced not only my first bluescreen in Vista, but also my first reboot-bluescreen-reboot-bluescreen... cycle in Vista.

Don't Try This at Home
I was installing Alcohol 120% because I needed a program to burn my Ubuntu iso. Near the end of the installation, a red UAC dialog pops up asking if I wanted to install an unsigned driver. After I click yes, Vista bluescreens. "No big deal", I think, "I'll just reboot Vista and everything will be fine".

Just Try Rebooting
Well, I reboot Vista and immediately after I log in, I see a little icon appear in the system tray, and it's installing drivers. Frantically, I look for a way to stop it to no avail. About 10 seconds later, Vista bluescreens again. At this point I'm still not too worried because I think to myself, "I'll just start in safe mode; then I can run system restore." So I choose safe mode from the boot menu. Even before I can log in, while it's loading drivers, Vista bluescreens. "Okay", I think, "Now I'm really screwed."

Stuck Between a Sniper and a Hard Place
What I do next has almost no chance of success, but I do it anyway because I can't think of anything else. I boot Vista normally, and then I have about 10 seconds to fix the problem before Vista bluescreens again. The situation is similar to when I'm playing Day of Defeat: Source, and I know there's an enemy sniper looking for me outside, but I go up to the window anyway to try and snipe him first.

A Shot in the Dark
Recovery options exhausted, I try booting from my Vista installation DVD, not knowing anything about the recovery tools available. I'm pleasantly surprised to discover that there's an option to run system restore. I choose a restore point just before I installed Alcohol 120%. Vista reboots, I hold my breath, 10 seconds pass uneventfully, and then I exhale. I'm saved.

Vista File Permissions

I tried creating a new file on my external hard drive and I was very confused when I got a message saying it failed. It turns out Vista sets the default file permissions to not allow modifications on external hard drives.

To fix this, you can:

• Right clicking on the drive to bring up the context menu and select Properties.
• Go to the Security tab.
• Click on Edit, which pops up a UAC dialog.
• And then edit the permissions.

Analyzing Polyhedral Scenes

I recently read about a neat algorithm for determining the geometry of polyhedral scenes (an assembly of solids each of which is bounded by plane faces) in The New Turing Omnibus. The algorithm assumes that lines can only meet in a few ways, and each meeting has only a few possible labelings for the component lines. The algorithm starts by labeling the lines for one meeting and tries to make consistent labelings for its neighbors and so on. Usually, the algorithm will end up with one consistent labeling for the whole scene, with maybe a few ambiguities.

If the description is confusing, don't worry, I hope to make something soon that will make it all clear.

Regular Expressions in Java

One of the cool things about Perl, Ruby, and other scripting langauges is how easy it is to do some very complicated things. For example, Ruby has the =~ operator, which lets you easily match a string against a regular expression. It returns the position that the match starts or nil if there is no match.

"sector 19" =~ /\d/    # Returns 7

Another cool thing you can do in Ruby is String.scan - this iterates though a string, matching against a regular expression and returns an array with all the matches.

# Returns all the <item> tags
text.scan(/<item>.*?</item>/)

If you know the right Java APIs though, these operations are almost as easy. The following Java code does the same thing as the above Ruby code:

ArrayList<String> tagList = new ArrayList<String>();
Matcher matcher =
   Pattern.compile("<item>.*?</item>").matcher(text);
while(matcher.find()) {
   String match = feedString.substring(matcher.start(),
                                       matcher.end());
   tagList.add(match);
}

A Matcher object is returned by Pattern.matcher - it basically remembers a string, a regular expression to match against, and the last matched position. Matcher.find returns true if there's another match. Matcher.start, and Matcher.end returns the start and end indexes of the previous match.

I'll admit that the code is a bit longer than the Ruby version, but it's still quite easy.

MusicMill

You're looking at a sketch of a revolutionary interface for organizing and playing music. It's still in the early design phase, but a working prototype may come soon once I get some free time.

GeneVisualizer

I just finished making something called GeneVisualizer for an extra credit project in my Computational Biology class. It's a program that lets you explore an organism's genes visually in a very interactive way. You can read more about it at my website.