ChessVibes

August 10, 2007


persconfkramnik.jpg

ChessVibes is a great chess web-site/blog with lots of interesting content. A highlight from the past year is their coverage of the Wijk aan Zee tournament held in January 2007, where most of the strongest players in the world played. They have videos taken from the post-game press conferences; in each video, the winner explains his victory for some 20-30 minutes.

Here are links to a couple of the best videos:

Kramnik (the world champion) explains his victory over Anand (the highest rated player today).

Svidler (ranked #12 in the world, and one of the most entertaining of the world elite) wins against former world champion Topalov after Topalov cracks in a better position.

If you like these, you can easily find lots more (with Anand, Topalov, Aronian, etc. explaining their wins) from that tournament.

A Simple but Challenging Game, Part I

August 9, 2007

My 15-year-old son Adam likes game theory. He invented the following simple game, and asked me about it when I got on the phone with him while I was away at a conference last month (I’ve simplified and formalized the set-up slightly):

There are two players, each of whom is given a real number which is chosen randomly from a uniform distribution between 0.0 and 1.0. The players know their own number but not their opponent’s. One player moves first and has the choice of passing or challenging. If he challenges, both players reveal their number, and the player with the higher number receives a payoff of 1, while the other player receives a payoff of 0. If the first player passes, the second player has a choice of challenging or passing. If he challenges, again both players reveal their numbers and the player with the higher number receives a payoff of 1, while the other player receives a payoff of 0. If the second player also passes, both players receive a payoff of 1/2. They play the game one time, and are interested in maximizing their expected payoff.

What is the right strategy? For example, if you received the number 0.17, would you pass or challenge if you were the first player? What about if you were the second player? What would you do if the number you received was 0.0017?

I’ll tell you more in a later post, but for now why don’t you think about it….

Mitsubishi Electric Research Labs is Hiring

August 8, 2007

Mitsubishi Electric Research Labs (MERL), the research lab where I work, is hiring. We have open research scientist positions in a number of different fields in computer science and electrical engineering.

Multicellular Logic Circuits, Part I: Evolution

August 7, 2007

If we want to construct artificial machines that rival the capabilities of biological organisms, we should try to understand the principles by which complex natural “machines” such as plants and animals are created.

It is generally agreed, at least by scientists, that all natural organisms have been “designed” by the completely blind and random process of evolution. Through evolution, a population of organisms tends to become progressively better adapted to its environment via the mutation of genomes of individuals in the population, and the selection and more rapid reproduction of the fittest organisms in that population.

51tk0pychxl_aa240_.jpg

Harvard professor Martin Nowak a has written a lovely and elegant book describing the mathematics of evolutionary dynamics, using the ideas of evolutionary game theory; here is a video of Nowak describing evolutionary game theory at Harvard in 2004.

My own interest is not so much in analyzing evolution, but in exploiting it. If we understand evolution so well, shouldn’t we be able to use it to design useful machines?

180px-img013biglittledogfx_wb.jpg

Of course, humans have already for many centuries exploited evolution, using artificial selection to breed domesticated animals or cultivate useful plants.

But I am looking for something else: the design of artificial machines through artificial selection. Although it has never been a mainstream idea, computer scientists have pursued such dreams since the 1950’s. When I was in graduate school in the 1980’s, I loved reading John Holland’s seminal 1975 book “Adaptation in Natural and Artificial Systems.”

adapt.jpg

Holland and his students were deeply influential in popularizing the whole field of genetic algorithms.

Another important figure in the field is John Koza, who has advocated for many years one of the most important variants of genetic algorithms, which he calls “genetic programming.” In genetic programming, computer programs, typically written in Lisp, are evolved through a process that involves mutating the programs by altering or swapping branches of the computation tree representing the program.

Genetic programming and genetic algorithms more generally, have had considerable success creating interesting and useful systems and programs. Nevertheless, I think it is fair to say that these ideas are still considered “fringe” ideas in the scientific and engineering community, and they have not widely replaced more conventional software and hardware design strategies.

So what might be missing? I will begin discussing that in Part II.


Marvel Trading Card Game / Magic the Gathering

August 7, 2007


61uwcobzlql_aa280_.jpg

Are you looking for a challenging strategy game in a portable format? If so, this is the game for you. This is an example of a remarkable piece of work that is being seriously under-appreciated.

A little background is in order. Collectible card games (now called “trading card games”) began in 1993 with “Magic the Gathering,” a game designed by Richard Garfield, who was just then earning his Ph.D. in mathematics at Penn.

The basic idea of Magic the Gathering is that you build your own deck of cards (which set of cards you can select from depends on the precise rules of the format you are playing) and then “duel” against an opponent who has built his own deck.

In a duel, you start with 20 “life” points, and the objective is to reduce your opponent to zero points before they do the same to you. You play some of your cards as “creatures” which attack your opponent or defend you against your opponent’s creatures. There are other cards that act as “sorceries,” “instants,” “artifacts,” or “enchantments,” which are “spells” that you cast and have all sorts of different effects, like killing creatures, reducing your opponent’s life, making your creatures stronger, and so on. (There are many other possibilities–there now exist roughly 10,000 different cards, so you can appreciate that they do many different things.) Each creature or other spell is paid for with “mana” that you usually obtain from your “land” cards.

When you play a “spell” it is put on a “stack,” and your opponent has a chance to respond to it before it “resolves.” Much as in a computer stack, the spells can pile up, and are resolved in last in, first out, order. Since many of the cards have effects which violate the normal rules, it can be very complicated to keep track of what is going on.

The key to winning in Magic is to design a deck where your cards act synergistically with each other, and then to be able to take advantage of all the subtle interactions and timing effects. It’s incredibly difficult and challenging to play well, no less challenging than Chess, and like Chess, it can be played either casually or in serious tournaments.

If you want to learn more about Magic, you should visit www.magicthegathering.com, which has a vast amount of information. You should probably start with the “Magic Academy” articles, and this article in particular.

250px-magic_players.jpg

I personally played seriously between 2004 and 2006, and my highlight was reaching 2nd place in a rather serious “Pro tour qualifier” tournament in 2005 (see the picture above for what one of these tournaments is like) with my Blue-White Ninja deck (although in that link, the Mike Flores gives me too much credit for the deck design; I copied an obscure but brilliant deck I found on the internet, a practice referred to as “net-decking”). For the last year, though, I haven’t played much, and my son Adam has seriously surpassed me in in both playing and deck-designing ability.

Magic the Gathering has been fantastically popular for a serious card game, and has spawned many imitations because of its ridiculously successful business model. Because the cards that are legal to build your decks with keep changing, the game keeps evolving (which is nice), but that means you have to keep spending money to buy more cards (which may not be so nice for you, but it is certainly nice for the publishers.) Actually, it’s a little more complicated than that–they’ve cleverly arranged it so that your old cards are still legal for some formats, and since they are no longer printed, those old cards tend to hold their value pretty well. And many Magic players actually quite enjoy collecting and trading their cards.

Anyways, most of the imitations, like Pokemon card game, Yu-gi-oh, or Duel Masters, are vastly simplified games targeting a younger set. (Most Magic players are males between the ages of 15 and 30.)

One imitative game, which at least roughly equals Magic in complexity and interest, is the “Marvel Trading Card Game” (also known as “Versus System.”) The theme is a little different; it has superheroes battling villains instead of monsters fighting and wizards casting spells and so on, but it works very similarly. Forgetting about the theme, and judging them strictly as abstract games, there’s little to make one prefer one game very much over the other–they are clearly closely related, and the competitive Marvel scene is dominated by Magic players.

Unfortunately, no versions of Magic have come out for portable game systems. There was a computer game back in 1998, but its AI was really pretty bad. There is a version of Magic the Gathering that can be played online, but you need to buy the cards for the same price as you pay for real cards. (You are able to play for free against other beginners with simple starter decks.) You can also play for free online using the excellent Magic Workstation program, but Magic Workstation doesn’t enforce the rules, so you need to be a relatively experienced player to use it.

Probably Wizards of the Coast (the publishers of Magic) haven’t wanted to cut into their card sales with a computer or portable game that effectively gives you a huge number of cards to play with for a relatively small price, or possibly they don’t believe that it’s possible to program an AI that plays Magic competently.

There have been numerous Yu-gi-oh and Duel Masters games for Nintendo DS’s and Gameboys, but I find those games to be distinctly inferior to Magic.

Anyways, we now have “Marvel Trading Card Game” for the DS, PSP, or PC. I have the DS version for my DS Lite. To play the game on a DS, you hold your DS sideways like a book. The game board is shown on the touchscreen, and you poke at your cards with the stylus to play them. On the other screen the currently selected card is shown in detail so that you can read all of its rules.

You can follow two “paths” through the game, one where you play with superhero cards, and one where you play with villain cards. When you win duels, you are rewarded with new cards, which you can use to make a more powerful deck, which you will definitely need to do, because your opponents’ decks will get more powerful. The game includes about 800 different cards in all. There are also tutorials and very challenging puzzles.

In general this is an extremely challenging game! The AI is very impressive (and it gets some advantage from having slightly better decks than you). You can win, but you will need think hard and play very carefully. After the first couple opponents, you start facing good decks, and I started losing duels more often than winning them. But since I can always identify my errors when I lose, it doesn’t feel unfair, just challenging. Each duel will take about 40 minutes (Versus duels tend to last longer than Magic duels, which typically only take 20 minutes). You can also play online with other players, but I haven’t tried that, because if I wanted to play online, I would just use Magic Workstation.

The game has been getting mediocre reviews (they mostly complain that the game is so hard; another problem is that the music is pretty bad–I agree that you should turn off the sound), so my viewpoint is obviously a minority one. But nevertheless, if you like Magic, or want to see what serious trading card games are about, or want something that will make the time fly during a long plane or train trip, I recommend you pick this up.

Version Control Using Subversion

August 5, 2007

I’ve worked with some twenty-odd interns over the last few years at MERL, all of them graduate students at top electrical engineering and computer science departments from around the world. I’ve also interviewed many more job candidates for our research lab. One fact that has continually amazed me is what a tiny fraction of them have had any previous experience using version control (also called “source code management”) systems.

Version control lets you save each version of a software project as you build it up. Because you know that you can always back up to a previous working version, you are much more confident in writing new code. All professional software developers use version control on every project they work on; working without it is sometimes compared to trying to write a novel with a word-processor that doesn’t have a delete key.

If you’re getting started with version control, I recommend that you use Subversion, (also known as “svn”) which has several fundamental improvements over the older CVS system. A free book explaining the system comes with it, but I also recommend “Pragmatic Version Control Using Subversion”, by Mike Mason.

If you’re a budding programmer or a graduate student in an EECS department, think of it this way–not only will using version control help you write better software, but it will help you get a job if you ever want to go into industry. I doubt we’re the only ones who routinely ask candidates whether they’ve used version control to help assess their software development skills. [And if it crossed your mind, you can’t fake your way through this; if you say that you’ve used it, you’ll get follow-ups.]

Generalized Belief Propagation

August 5, 2007

In 2002, I gave a lecture at the Mathematical Sciences Research Institute on the work I did, together with Bill Freeman and Yair Weiss on Generalized Belief Propagation, and the correspondence between free energy approximations and message passing algorithms. The lecture is available as a streaming video, together with a pdf for the slides, here.

It’s worth mentioning that there are many other interesting research lectures available in MSRI’s video archive, and that the more recent ones are of higher production quality.

Here is our most recent and comprehensive paper on this subject, published in the July 2005 issue of IEEE Transactions on Information Theory, which gives many additional details compared to the lecture: MERL TR2004-040.

If that paper is too difficult, you should probably start with this earlier paper, which was more tutorial in nature: MERL TR2001-22.

If you’re looking for generalized belief propagation software, your best bet is this package written by Yair’s student Talya Meltzer.

P.S.: I realized I haven’t told those of you who don’t know anything about it what generalized belief propagation is. Well, one answer is to that is look at the above material! But here’s a little background text that I’ve copied from my research statement to explain why you might be interested:

Most of my current research involves the application of statistical methods to “inference” problems. Some important fields which are dominated by the issue of inference are computer vision, speech recognition, natural language processing, error-control coding and digital communications. Essentially, any time you are receiving a noisy signal, and need to infer what is really out there, you are dealing with an inference problem.

A productive way to deal with an inference problem is to formalize it as a problem of computing probabilities in a “graphical model.” Graphical models, which are referred to in various guises as “Markov random fields,” “Bayesian networks,” or “factor graphs,” provide a statistical framework to encapsulate our knowledge of a system and to infer from incomplete information.

Physicists who use the techniques of statistical mechanics to study the behavior of disordered magnetic spin systems are actually studying a mathematically equivalent problem to the inference problem studied by computer scientists or electrical engineers, but with different terminology, goals, and perspectives. My own research has focused on the surprising relationships between methods that are used in these communities, and on powerful new techniques and algorithms, such as Generalized Belief Propagation, that can be understood using those relationships.

I’ll tell you more in future posts; I promise.

“Ageless Quest” by Lenny Guarente

August 5, 2007


519qsvhv4wl_sl210_.jpg

MIT professor Lenny Guarente is a pioneer and leader in the study of the molecular biology of aging. This book is a popularized account of some of the early research that he and his students and post-docs conducted; research that helped move the study of aging from being a kind of slightly disreputable scientific backwater to one of the most dynamic and exciting fields of modern molecular biology. Guarente’s research focused on sirtuins, which are proteins that are now understood to retard aging in a wide variety of organisms, with mechanisms that vary depending on the organism.”

Ageless Quest” is an easy read and a great introduction to the field. It had a surprising amount of impact on me; after reading this book I decided that I wanted to learn more about what was happening in this very important field, so I audited an MIT reading course on the molecular biology of aging taught by Angeiszka Czopik and Danica Chen, two post-docs in Prof. Guarente’s lab, and then I attended the 2006 Summer School Course on the molecular biology of aging at Woods Hole’s famous Marine Biological Laboratory, organized by Gary Ruvkun and Steve Austad.

This book probably won’t have that big an impact on you! It’s a pretty light book weighing in at only 154 pages; but you can learn a lot whether or not you have a background in biology.

SimPy and Discrete-Event Simulation

August 3, 2007

I’ve been using the SimPy discrete-event simulation package lately, and I really like it.

As the SimPy home page says, “SimPy (= Simulation in Python) is an object-oriented, process-based discrete-event simulation language based on standard Python.” What does that mean? Well, first of all, it is a Python module, and you import and then use it like any other Python module.

(If you haven’t used Python, get yourself over to www.python.org and download it now! Or if you use Mac OS X or Linux, you already have it. Python is a powerful, high-level general-purpose language, and comes with excellent documentation.)

“Discrete-event simulations” are something a good nerd will often need to write. They are simulations where things happen at discrete times. There are three levels of sophistication in handling such simulations. Level zero is to just step forward in time by small increments, checking every time step for each possible event. Not too bright, because you waste a lot of computation on time steps when nothing happens. Level one is the “event-oriented” approach, where you keep events in some “agenda,” and you process events in the agenda one at a time, with each event in the agenda possibly creating new events in the future that are then added to the agenda.

Level one is as far as most people get, but it’s not where you should stop, because writing an event-oriented simulation is painful and error-prone. The right thing to do is to go to the next level of sophistication, the “process-oriented” approach.

In the process-oriented approach, you create special objects, called processes, which are like “living” objects. Processes have a special event method which functions as an event loop. To program the events in your simulation, you need to write one or more process event methods which describes how each process object reacts to the possible events in the simulation. It turns out that these process event methods are very natural and easy to write, because they properly correspond to how we think about what is happening in the simulation.

So how does it work? Well, SimPy sets up and handles the event agenda underlying the system, so you don’t have to do it yourself. When you call the SimPy “simulate()” method, it begins stepping through the events in the event agenda, calling the appropriate process event methods defined in your processes in the correct order. The Python feature that makes the whole thing work is the Python “yield” statement, which is like a return, except that the next time a function with a “yield” is called, it picks up after the yield rather than at the beginning of the function. All the process event methods you define when using SimPy will use yields to give back control to the SimPy run-time system.

Anyways, Professor Norm Matloff from UC Davis has written some excellent tutorials, or you can use the documentation that comes with SimPy.

Zillions of Games

August 2, 2007

Visit Zillions of Games

If you like abstract games, especially chess variants, you should enjoy Zillions of Games. It’s quite an amazing piece of software; a piece of AI technology that I actually would have not thought possible.

Games are defined using a rules file (written in a Lisp-like language), and then a generalized alpha-beta search engine is unleashed. Basically, it works best for Chess and its many variants, but it plays a really surprising number of games very well. It comes with over 350 games and puzzles, and you can download thousands more.

It’s not that hard to modify existing rules files to define new games; my son was interested in having an opponent for a game he invented and we were able to modify an existing rules file to play his game in less than an hour–and it played very well.

Naturally, it doesn’t play all games as well as humans, but it plays so many games so well (with adjustable levels to make a fair fight if it’s too good) that one can’t complain. Unfortunately, it’s only available for Windows computers.