Jeopardy, Artificial Intelligence, and a Chess Playing Robot

Tomorrow Jeopardy will feature a computer facing off against former champions Ken Jennings and Brad Rutter.  I have been looking forward to this for a couple of months since I first heard about it, and it is an amazing feat of computer science that a computer can go head to head with humans on a game show as complex as Jeopardy.  IBM is the true leader in feats (stunts?) such as these having staged previous competitions against former chess master Garry Kasparov.  The show has already been filmed (in a special sound stage at IBM’s location) but I do have an inkling of what the engineering team probably went through prior to the event.

Artificial Intelligence

My freshman year in college, I managed to convince my professors that I could and should skip the computer science prerequisite for everything, COS120.  This put me into a data structures course in the first semester of my freshman year, and several linked lists and b-trees later, I was able to take any class I wanted in the spring.  I made  bee-line for a class called “Intro to Artificial Intelligence” as I was more than intrigued by the possibility that I could build Skynet and cause the human race its final doom.  Sweetening the pot was a rumor circulating the labs that the class would make use of the very recently released Lego Mindstorms.  Fulfilling the dreams of nerds and lego aficionados (with there being an admittedly strong correlation between the two groups) the Mindstorms were fantastically expensive to a college kid (several hundred bucks) and required programming knowledge to really make them hum along.  This AI class in other words was my ticket to Lego Nirvana, not the other way around.

Legos and LISP

I managed to sign up for the class and was one of (I think) two freshman.  Having spent high school and the fall semester doing work in C and C++ along with learning Perl and a new fangled language called PHP, it was quite a surprise to show up for class and begin learning LISP.  For those of you who are non-techies, LISP is a complete paradigm shift from how most programming languages allow you to express yourself.  The analogy might be like going from sketching in black and white to being handed multiple colors of modeling clay and being told to sculpt in three dimensions.  LISP is the oldest programming language still used in a mainstream capacity today.  LISP treats data and the program the same, so you can build a self modifying program which is one of the reasons Artificial Intelligence researchers and applications use it so much.  LISP has a weird looking “list based” syntax (LISP stands for LISt Processor) and allows you to solve weird problems in fairly elegant ways.  In fact, some like it so much and feel it is so powerful that LISP is the reason that Paul Graham (a well respected computer scientist and technology entrepreneur) credits for his business success. He felt he was able to elegantly and more efficiently out-build his competition simply because of their language choice.  I don’t really agree with Graham, but the point is that LISP is a very cool and very different language that was a pleasure to learn.  This class remains the only one in college where I did every single homework assignment.  The problems were just too fun and the ways of solving them were extremely different. Along with LISP of course came the Legos.  Almost immediately, we began building simple Lego robots that would following a line on the floor, be able to navigate a room, follow a light source in a dark room or navigate a maze.  It was unbelievably cool and a testament to Lego’s design prowess that their system allowed for such flexibility.  Each kit provided a command unit and several motors and sensors.  There was a touch sensor, light sensor, and a few others, and the command unit would download the programs via a cable hooked into a computer.  There was a Lego provided GUI-based way you could program the processor, but hackers had already provided several other languages, and we used Not Quite C (NQC) which was very similar to the C programming language with a few restrictions.

A Chess Playing Robot

All in all, we were having a blast, and just like kids get bored with a slide and start daring each other to go down backwards, or standing up, we began competing to build a bigger better robot.  Our professor was also the chair of the department, and he sensed he had something brewing, so he got the class together and challenged us to come up with a project that could bring fame and glory to our small liberal arts university.  A robot that could get us soda from the machine!  A robot to gather up homework assignments and drive them back to the professor!  Not as popular as the food or waiter suggestions.  Finally from the back of the class came the ultimate idea: a chess playing robot!  A senior in our class had been working on an independent study in addition to taking this class, and had produced a fairly workable Chess simulator, written in LISP.  The class began buzzing with excitement.  We could build the robot, then challenge students to beat it! I started to get a bad feeling about the project – building a Lego chess playing robot would be quite the undertaking.  My good friend Aaron Williamson upped the ante – “I could get the university TV station to film a match!”  Uh oh.  A third student offered to get one of the most popular professors in the school to face off against the robot, and just like that we had ourselves our very own TV spectacle: Man vs. Machine.  Nerds vs. Normals.  Technology (us) vs. Philosophy (the professor).

The work was divided up and we immediately had to start pulling late nights as we only had a few weeks to get everything together.  There would be a vision processing team (the robot had to know where the chess pieces were), a robotics team which would build the gantry crane and arm mechanisms, and the chess software team.  The Public Relations we soon learned, would take care of itself.  I was on the vision team, and our job, we felt, was quite possibly the hardest.  This was 2000, and web cameras were novel, low resolution, expensive, and rather rare.  At least, they were expensive for college students, so we used the only one we had available: a web camera attached to a Silicon Graphics O2 workstation that provided a 640×480 resolution color picture.  It provided enough resolution so we could film the board, and our algorithm would take one picture, save it, then take another after the human moved, and compare them to determine which two pieces had moved.  This seems pretty trivial, but it was complicated by a fisheye effect from the lens, and the fact that the robot arm (or human) wouldn’t actually place the pieces very accurately. Lighting and other conditions could also change depending on where the human was standing or for a host of seemingly random factors. As we started to work, even simple things seemed to derail us.  Silicon Graphics apparently used a proprietary RGB format which was reverse of standard RGB, so we had to write a converter.  Irix, the SGI OS, turned out to be a pain to develop for, at least compared to Linux, so we performed the processing on another computer.  This meant we also had to set up the workflow between the IRIX machine which captured the image, and the Linux machine which processed the image, and then interface with the robot and the chess playing program, which ran on another machine. The date for the campus wide demonstration was looming, and we were determined to not be humiliated.  The student newspaper ran a feature, and our opponent was quoted that “no hunk of metal would best him” to the delight of the student body.  

Media_httpwwwpeebsorg_gamba

Finally, the day was upon us, and we began preparing the lecture hall which would be ground zero.  We had lots of equipment to move from our basement computer lab to the lecture hall, and as we began calibrating everything alongside the film crew which was also setting up, we noticed that the vision system wasn’t working.  At all.  It couldn’t find the edges of the board, couldn’t determine the grid, and it couldn’t see which pieces had moved.  We were in trouble – the fluorescent lighting conditions of the basement worked but the incandescent lighting and TV lighting in the lecture hall didn’t and we needed to recalibrate everything.  Working like mad we began tracking down all intensity assumptions in our program and moving pieces around until finally we got it working. The format of the competition was designed so that while the computer was thinking we’d explain to the audience what was happening, and our opponent would also discuss the philosophical ramifications of sentient machines.  This was designed for another, secret reason – if something went wrong, we wanted to be able to troubleshoot without drawing too much attention.  We had a backdoor programmed into the chess program which could reset it if there was trouble, or in the event of a catastrophic failure, we could take over and manually play out the match.  The ethical dilemma of should we tell the audience what happened if that were to come to pass was hotly debated.

The clock struck 7:15, in came the audience, and on came the red blinking lights of the video cameras.  The lecture hall was packed out, and the professor did a great job making jokes as we introduced the event and briefly explained the rules.  Our class professor could have died of happiness at that moment.  As we began the competition, the professor picked white and made the first move.  “Take THAT you cold calculating MACHINE!” he proclaimed to resounding applause from the audience.  That pissed me off.  I had been championing a feature where the robot would insult and taunt its opponent with every move, but was shouted down for not being classy enough.  We had to endure a night of insults that could have been combatted and we all admitted in hindsight that we should fought fire with fire. At first, everything looked like it was going well.  The robot was working, it could see what was happening, and the chess program was making good decisions.  We started to relax a little, and the audience was clearly intrigued as the gantry crane would slowly move to the right spot, lower its arm, then grab the piece and move it.

Then disaster struck.  Just a few moves in, our opponent performed an En Passant which while being a rather esoteric move, also has the rather interesting distinction as Wikipedia puts it, as “the only occasion in chess in which a piece captures but does not move to the square of the captured piece.” Uh oh.  Our vision system was designed to look for what changed and was looking for either a move or a capture, not a weird combination of both.  Our program chose the two best coordinates to send which caused the chess program to have the wrong board information, and we watched in horror as the gantry crane moved into the wrong position, knocking over several pieces as it vainly swiped in air to make its move. “Uh oh, Houston, LOOKS LIKE WE HAVE A PROBLEM!” yelled our opponent as the crowd roared its approval, and he immediately launched into a discussion about how pure logic will never overcome the malleability of the human mind. It was chaos as we raced to reset the board, recalibrate the vision system, and instruct the chess program of the true state of the game.  I believe we had to simply reset the game state completely, in essence telling the computer that the game had started with the board situated the way it was since it didn’t understand an En Passant.  Things were looking up as the computer managed to make a move and actually captured a pawn to the crowd’s approval.  

For the next fifteen or so moves we each took turns giving a short talk about how the robot was built, the technologies we used, and the challenges we overcame. As the evening wore on, the game developed nicely.  I’m not a chess player but I could tell that the computer was holding its own and it could already beat everyone in the class, so we were optimistic about our chances.  Still, it was roughly an hour into the game and even though I wasn’t following every move closely it was a surprise when all of a sudden the professor announced “Checkmate!”  I looked over at the board and it was indeed checkmate!  However, the computer didn’t agree.  Turns out that either during the initial setup of the board or during the insane scramble to fix our En Passant adventure, someone had incorrectly placed the King and Queen on the computer’s side.  The computer had been defending its queen instead of its king, and thus had fallen prematurely. A disappointing end to what would end up being one of the most memorable projects of my college career.  Still, we couldn’t help but feel proud of being able to build something unique and stage a public spectacle of sorts that everyone seemed to enjoy.  Tomorrow as I tune into watch Watson and the team from IBM, I have a small sense of how they’ll be feeling, and win or lose (there are already rumors leaking out as to the results) it is an incredible achievement.  Congratulations and good luck!

Postscript:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s