Archive for the ‘Reviews’ Category

Beginning Go

October 1, 2007

If you’re interested in learning more about the game of Go, whether you’re an absolute beginner or already know something about the game, a good starting point is “Sensei’s Library”, a huge wiki (it currently contains 15722 pages) all about Go. There are many ways to explore the wiki, and tons of interesting topics to explore.

There are are many nice English language books on Go. I will just recommend, if you are a beginner, the excellent five volume “Learn to Play Go Series” by Janice Kim and Jeong Soo-hyun. (If you already know the rules and have played a couple games, you probably want to begin with volume 2).

Go-playing programs, unlike Chess programs, are no match for even moderately strong human amateurs, but for beginners or weak players like myself, they can provide an interesting challenge. I very much like the free Goban Go GUI for Mac OS X, which includes GNU Go, which is one of the best Go-playing programs. Goban also serves as a client for online Go servers and lets you replay Go games in the .sgf format.

Gallager’s LDPC error-correcting codes

September 28, 2007

Error-correcting codes are a technology that most people don’t think much about, if they even know they exist, but these codes work quietly in the background to enable such things as cell phones and other wireless technology, cable and satellite TV, and also the internet, including DSL, fiber-optic communications, and good old-fashioned dial-up modems. The modern communications revolution could not have begun without these codes.

So what’s the idea behind these codes? There’s a lot to say, and many textbooks have been written on the subject, so I’ll only give the briefest of introductions. [Some excellent textbooks I recommend include MacKay's textbook which I've already reviewed, McEliece's "Theory of Information and Coding", and Lin and Costello's "Error Control Coding." See also this post for two forthcoming books available online.] EDIT: I’ve added some more information about LDPC decoders, with pointers to available software, in this post.

The basic idea is that we want to transmit some bits which represent some piece of text or picture or something. Unfortunately, when we transmit those bits, they need to travel through some channel (say a wire or through the air) and when they are received, the receiver only gets a noisy version of each bit. For example, each bit might be flipped independently from a 0 to a 1 or vice versa with some small probability (this is called the binary symmetric channel; many other channel models exist too).

To combat this noise, we send extra bits; so instead of sending say the 1000 bits that represent our message, we might send 2000, where the extra 1000 “check” bits have some known relationship to the original 1000. Both the transmitter and receiver agree on that relationship ahead of time; that is the “code.” Of course, all 2000 bits are now subject to the noise, so some of those extra bits could be flipped. Nevertheless, if the noise is small enough, the receiver can try to “decode” the original 1000 bits by finding the configuration of the 2000 bits which obeys all the constraints and is most probable.

In 1948, Claude Shannon proved a theorem that essentially said that if the noise in the channel was small enough, and if the number of extra bits that you were willing to send per original bit was large enough, that one could design very long codes, that if optimally decoded, would always remove all the noise and recover the transmitted message.

(By the way, it is this amazing property that codes can remove 100% of the noise that means that we can watch crystal-clear high-definition TV coming in over the airwaves, something I very much appreciate when I watch a football game these days. When advertisers talk about “digital this” or “digital that,” they really mean “error-corrected digital”.)

As an example of Shannon’s theorem, if one was willing to use one extra bit for every original bit, and the percentage of flipped bits in your binary symmetric channel was less than the Shannon limit of about 11%, his theorem tells you that codes exist that will reliably remove all the noise. However, Shannon’s proof was non-constructive; he didn’t tell us what these wonderful codes were. Shannon also proved a theorem that if the noise was higher than the “Shannon limit,” no codes exist that can reliably correct the noise.

So error-correcting coding theory deals with the problems of designing codes, and efficient encoders and decoders for those codes, that work as close to the Shannon limit as possible. Many theorists invented many interesting and useful codes and encoders and decoders over the years, but until the 1990’s, it still seemed a distant dream to most coding theorists that we would be able to find practical codes that performed near the Shannon limit.

What is very strange is that the best codes and decoders that were discovered in the 1990’s were actually a rediscovery of codes and decoders invented by Robert Gallager in the early 1960’s, for his Ph.D. thesis. Gallager’s thesis introduced “low density parity check” (LDPC) codes, and their decoding algorithm, the famous “belief propagation” decoding algorithm. His thesis also introduced many other important ideas in coding theory, including “density evolution,” simplified “bit-flipping decoders,” and analysis methods for optimal LDPC decoders. It is a truly remarkable work, that every aspiring coding theorist should read. Fortunately, it’s available online.

images.jpg

How is it possible that this work was forgotten? Well, in 1968, Robert Gallager wrote a magnificent textbook on information theory, called “Information Theory and Reliable Communication,” where he explained most of the information and coding theory known at the time, but neglected to talk about LDPC codes! I’m not sure why. Possibly he thought that he’d already covered the material in the 1963 monograph that was made from his thesis, or perhaps he didn’t think LDPC codes were practical at the time. In fact, the decoder was too complex for 1960’s technology, but Moore’s Law took care of that, although only now are LDPC codes widely replacing previously-developed codes in communications systems.

So the moral of the story is: if you write a ground-breaking Ph.D. thesis about a remarkable technology that is 30 years ahead of its time, please don’t forget to mention it in your classic textbook a few years later. Not a moral too many of us have to worry about, but still…

Artificial Intelligence: A Modern Approach

September 20, 2007

images.jpeg

“Artificial Intelligence: A Modern Approach,” by Stuart Russell (professor of computer science at UC Berkeley) and Peter Norvig (head of research at Google) is the best-known and most-used textbook about artificial intelligence, and for good reason; it’s a great book! The first edition of this book was my guide to the field when I was switching over from physics research to computer science.

I feel almost embarrassed to recommend it, because I suspect nearly everybody interested in AI already knows about it. So I’m going to tell you about a couple related resources that are maybe not as well-known.

First, there is the online code repository to the algorithms in the book, in Java, Python, and Lisp. Many of the algorithms are useful beyond AI, so you may find for example that the search or optimization algorithm that you are interested in has already been written for you. I personally have used the Python code, and it’s really model code from which you can learn good programming style.

Second, if you haven’t ever visited Peter Norvig’s web-site, you really should. I particularly recommend his essays “Teach Yourself Programming in Ten Years,” “Solving Every Sudoku Puzzle,” and “The Gettysburg Powerpoint Presentation.”

Multicellular Logic Circuits, Part II: Cells

September 18, 2007

In my post “Multicellular Logic Circuits, Part I: Evolution,” I discussed evolution and genetic algorithms; I want to continue that discussion here.

There are two salient facts of biology that are completely inescapable. The first is that all organisms are shaped by the process of evolution. The second is that all organisms are constructed from cells.

Furthermore, all complex multicellular organisms begin life as a single cell, and undergo a process of development through cell division to mature into an adult. And no matter how different any two organisms may be on the gross macroscopic level that we are used to, inside their cells the chemical processes of life are fundamentally very similar.

080534635x.jpg 0815340729.jpg

Thus it is no accident that the titles of the two leading textbooks in molecular biology are The Molecular Biology of the Gene by Watson, et. al. and The Molecular Biology of the Cell by Alberts et. al. [These are both great books. This link to the first chapter of MBOC is an excellent entry point into modern biology. And if you are serious about learning biology, I also strongly recommend the companion Molecular Biology of the Cell: A Problems Approach, by Wilson and Hunt, which will force you to think more actively about the material.]

It therefore seems reasonable that if we want to construct artificial systems that achieve the performance of natural ones, we should consider artificially evolving a system constructed from cells.

Although there are typically many different cell types in a mature multi-cellular organism, all the different cells of the organism, with the exception of sperm and egg cells, share an identical genetic specification in their DNA. The different behavior of cells with identical genetic specifications is the result of the cells having different histories and being subjected to different environments.

More specifically, the behavior of a biological cell is controlled by complex genetic regulatory mechanisms that determine which genes are transcribed into messenger RNA and then translated into proteins. One very important regulatory mechanism is provided by the proteins called “transcription factors” that bind to DNA regulatory regions upstream of the protein coding regions of genes, and participate in the promotion or inhibition of the transcription of DNA into RNA. The different histories of two cells might lead to one having a large concentration of a particular transcription factor, and the other having a low concentration, and thus the two cells would express different genes, even though they had identical DNA.

Another important mechanism that controls the differential development of different types of cells in a multi-cellular organism is the biochemical signaling sent between cells. Signals such as hormones have the effect of directing a cell down a particular developmental pathway.

In general, the transcription factors, hormones, and multitude of other control mechanisms used in biological cells are organized into a network which can be represented as a “circuit” where the state of the system is characterized by the concentrations of the different biochemical ingredients. In fact, biologists are now using wiring diagrams to help summarize biological circuits; see for example, the “Biotapestry editor” developed by Eric Davidson’s lab at Caltech.

books.jpeg books2.jpeg

[I strongly recommend Davidson's recent book The Regulatory Genome: Gene Regulatory Networks in Development and Evolution for an exciting introduction to the burgeoning "evo-devo" field; if you don't have any background in biology, you may prefer The Coiled Spring, by Ethan Bier for a somewhat more popular account.]

Turning to the problem of designing artifical systems, a natural question is what theoretical advantages exist, from the point of view of designing with evolution, to using an identical genetic specification for all the cells in a multi-cellular organism.

One potential advantage is that relatively small changes to the genetic specification of the organism can concurrently alter the behavior of many different kinds of cells at many different times during the development of the organism. Therefore, if there is the possibility of an advantageous change to the circuitry controlling a cell, then it can be found once and used many times instead of needing to find the same advantageous mutation repeatedly for each of the cells in the organism.

Another related potential advantage is that a highly complicated organism can be specified in a relatively compact way. If each of the trillions of cells in a complex organism like a human had to be separately specified, then the overall amount of information required to describe the human genome would be multiplied more than a trillion-fold. Clearly, it is much more efficient to re-use the identical circuitry in many different types of cells.

In other words, biology uses a strategy of specifying a complex multi-cellular organism by just specifying a single cell–all the other cells in the mature organism are grown organically out of the developmental process. This seems like a strategy worth imitating.

On the other hand, the constraint that each cell in an organism should share an identical genetic specification clearly causes complications from the point of view of design. For example, it is important that genes that are designed to function in one type of cell at one point in development not cause problems for different type of cell at a different point in development. Clearly, good design of the control logic that turns genes on and off is essential to the proper functioning of a multi-cellular organism.

In the next post in this series, I will turn to the construction of a concrete model for multi-cellular circuits that tries to capture, as simply as possible, the essence of what is happening in biology. 

Mindbusters for Magic the Gathering

September 16, 2007

Today we have a guest article from my son Adam, about a variant of Magic the Gathering that we enjoy playing. I wrote a post introducing Magic and other trading card games previously, so if you know nothing about them, you might want to read that first. Adam’s article is definitely addressed to the advanced Magic player.

There are a few problems with Magic that this variant addresses: in particular the luck of the draw and the expense of buying packs. This variant is essentially a no-luck version which just requires two packs of cards. This type of variant can also be used for other trading card games.

If you’re interested in other variants to games like chess, go, bridge, etc., or perhaps in learning how to design your own variants or games, I highly recommend R. Wayne Schmittberger’s “New Rules for Classic Games.”

And if you’re interested in adding some Magic-like luck to the no-luck game of Chess, rather than eliminating the luck from Magic to make it more like Chess, you should read this post.

Read about the “Mindbusters” variant of Magic the Gathering.

(One comment for those who try to follow the article without much Magic experience: “milling” is the strategy of trying to run your opponents out of cards to draw: if you can’t draw a card when you’re supposed to, you lose the game.)

Two Draft Books

September 13, 2007

If you’re interested in learning about statistical mechanics, graphical models, information theory, error-correcting codes, belief propagation, constraint satisfaction problems, or the connections between all those subjects, you should know about a couple of books that should be out soon, but for which you can already download extensive draft versions.

The first is Information, Physics, and Computation by Marc Mézard and Andrea Montanari.

The second is Modern Coding Theory by Tom Richardson and Ruediger Urbanke.

I also recommend the tutorial on Modern Coding Theory: the Statistical Mechanics and Computer Science Points of View, by Montanari and Urbanke, from the lectures they gave at the 2006 Les Houches summer school.

Cards & Chess

September 10, 2007

If you enjoy Chess, but want to spice it up a bit, you’ll probably enjoy some of the games in this post, which introduce the random element of cards into the royal game.

kc2sm.jpg

The first game(s) you might consider are Knightmare Chess and Knightmare Chess 2 (there is also a slightly different French language version called “Tempête sur L’echiquier”) designed by Bruno Faidutti. This game is a kind of mix between Chess and a trading card game like Magic the Gathering. You’ll hold a hand of cards which will let you do some special event each turn (e.g. “For this turn, any one of your pieces may move as if it were a Knight. You cannot capture a piece with this move.”)

Faidutti, a French historian and sociologist, is one of the best-known and respected game designers. His games tend to have a strongly chaotic element. His most popular game, which I highly recommend, is Citadels (“Citadelles” in French), which is best played with large numbers of players (up to seven, and the closer to that number, the better).

Faidutti has an exceptional web-site, particularly notable for his Ideal Game Library, reviewing hundreds of games.


pic21524_t.jpg

Returning to the subject of cards and Chess, the other set of games I want to recommend is Karten Schach, designed by Reiner Knizia, the prolific German mathematician and game designer whom I already discussed in this post. Karten Schach was a labor of love by Knizia (I can’t imagine he thought it would sell very well, and the rulebook is over 100 pages, mostly taken up by discussions of the game mechanics, with plentiful strategy tips).

It is actually collection of 16 games (plus variants) highlighting all sorts of different possibilities in game design; a kind of game design version of Bach’s variations. The names of the games give you a flavor of the possibilities: “Purist Chess,” “Liar’s Chess,” “Ducat Chess,” “Daredevil Chess,” “Gambler’s Chess,” “Psycho Chess,” “Cornucopian Chess,” “Feudal Chess,” “Generational Chess,” “Oracle Chess,” “Prophet’s Chess,” “Eunuch’s Chess,” “Doppelganger Chess,” “Wicked Witch Chess,” “Mysterious Stranger’s Chess,” and “Capitalist Chess.”

Without explaining the rules in detail, I’ll just briefly describe how a couple are played. In Oracle Chess, you must, at the end of each move, put a card face down which commits you to the piece you will move next turn. In Capitalist Chess, on each turn a card is chosen, and you bid chips to have the right to move the piece displayed on the card. Each game is defined by less than a page of brilliant rules, by the master of boardgame design.

I would recommend that you buy Karten Schach, but it has been out of print since 2001, and the publisher has gone out of business. So instead I will point you to the English translation of the rules by Christine Biancheria and a pdf file for the Cards necessary to play the game. (Thanks to Matthew Gray, for pointing me to the English rules translations when they came out.)

And just as I did for Faidutti, I’d also like to recommend one much more mainstream multi-player Knizia game (in case Chess variants are not your cup of tea). The Knizia game I’ll recommend is “Modern Art,”, one of the most highly rated of the German games; a classic in the auction game genre.

Consistent Quantum Theory

September 4, 2007

Quantum mechanics is a notoriously confusing and difficult subject, which is terribly unfortunate given its status as a fundamental theory of how the world works. When I was an undergraduate and graduate student of physics in the 1980’s, I was always unsatisfied with the way the subject was presented. We basically learned how to calculate solutions to certain problems, and there was an understanding that you were better off just avoiding the philosophical issues or the paradoxes surrounding the subject. After all, everybody knew that all the challenges raised by physicists as eminent as Einstein had ultimately been resolved experimentally in favor of the “Copenhagen interpretation.”

Still, there was a lot of weird stuff in the Copenhagen interpretation like the “collapse of the wave-function” caused by a measurement, or apparently non-local effects. What I wished existed was a clearly-defined and sensible set of “rules of the game” for using quantum mechanics. The need for such a set of rules has only increased with time with the advent of the field of quantum computing.

cover.gif

In his book, “Consistent Quantum Theory,” (the first 12 out of 27 chapters are available online) noted mathematical physicist Robert Griffiths provides the textbook I wished I had as a student. With contributions from Murray Gell-Mann, Roland Omnes, and James Hartle, Griffiths originated the “consistent history” approach to quantum mechanics which is explained in this book, .

The best summary of the approach can be obtained from the comparison Griffiths makes between quantum mechanics and the previous classical mechanics. Quantum mechanics differs from classical mechanics in the following ways:

1. Physical objects never posses a completely precise position or momentum.
2. The fundamental dynamical laws of physics are stochastic and not deterministic, so from the present state of the world one cannot infer a unique future (or past) course of events.
3. The principle of unicity does not hold: there is not a unique exhaustive description of a physical system or a physical process. Instead reality is such that it can be described in various alternative, incompatible ways, using descriptions which cannot be combined or compared.

It is the 3rd point which is the heart of the approach. In quantum mechanics, you are permitted to describe systems using one “consistent framework” or another, but you may not mix incompatible frameworks (basically frameworks using operators that don’t commute) together.

Griffiths uses toy models to illustrate the approach throughout the book, and provides resolutions for a large number of quantum paradoxes. He stresses that measurement plays no fundamental role in quantum mechanics, that wave function collapse is not a physical process, that quantum mechanics is a strictly local theory, and that reality exists independent of any observers. All of these points might seem philosphically natural and unremarkable, except for the fact that they contradict the standard Copenhagen interpretation.

This is a book that will take some commitment from the reader to understand, but it is the best explanation of quantum mechanics that I know of.

Richard Feynman

August 31, 2007

Richard Feynman has been one of my heroes, ever since the end of my freshman year at Harvard. After my last final exam, but before I headed home for the summer, I was able to sit in the beautiful Lowell House library, without any obligations, and just read chapters from his wonderful Lectures on Physics. After that there wasn’t much doubt in my mind about what I wanted to do with my life.

There’s a lot to say about Feynman, but I will restrict myself for now to a couple rather recent items which give a picture of the character of this remarkable man. First, there is this 1981 BBC Interview, recently released to the web, where you can see him briefly discuss a few of the things that were important to him.

images3.jpg

Secondly, if you haven’t read Perfectly Reasonable Deviations From the Beaten Track, the collection of his letters edited by his daughter Michelle Feynman that was published in 2005, you owe it to yourself to do so. I was skeptical at first that a book of letters, even those of Feynman, could be very interesting, but I wound up reading every word.

Let me just give you one example of a pair of letters from 1964:

Dear Professor Feynman,

Dr Marvin Chester is presently under consideration for promotion to the Associate Professorship in our department. I would be very grateful for a letter from you evaluating his stature as a physicist. May I thank you in advance for your cooperation in this matter.

Sincerely,
D.S Saxon
Chairman
Dick: Sorry to bother you, but we really need this sort of thing.
David S.

Dr. D.S. Saxon, Chairman
Department of Physics
University of California, Los Angeles
Los Angeles, California

Dear David:

This is in answer to your request for a letter evaluating Dr. Marvin Chester’s research contributions and his stature as a physicist.

What’s the matter with you fellows, he has been right there the past few years–can’t you “evaluate” him best yourself? I can’t do much better than the first time you asked me, a few years ago when he was working here, because I haven’t followed his research in detail. At that time, I was very much impressed with his originality, his ablity to carry a theoretical argument to its practical, experimental conclusions, and to design and perform the key experiments. Rarely have I met that combination in such good balance in a student. Was I wrong? How has he been making out?

Sincerely yours,
R.P. Feynman

The above letter stands out in the files of recommendations. After this time, any request for a recommendation by the facility where the scientist was working was refused.

Edit: In the comments below, Shimon Schocken recommends Feynman’s “QED.” I thought of this book after finishing this post. It’s an amazing work. In it, Feynman gives a popular account (you don’t need any physics background to follow it) of his theory of quantum electrodynamics, for which he won the Nobel Prize. But it’s a popular account that makes no compromises in its scientific accuracy. The other books recommended in the comments (“Six Easy Pieces” and “Surely You’re Joking”) are also definitely great books, but “QED” is somehow often overlooked, even though it is the book that Feynman himself recommended to those interested in his work.

Combinatorial Game Theory

August 29, 2007

Combinatorial Game Theory (CGT) is a mathematical discipline that studies two-player, zero-sum games, where the players play sequentially, and there is perfect information and no chance. The aim of CGT is to build mathematical theories that will help players win such games! In practice, the ideas from CGT are of minimal help to the serious player in more complicated games like Chess or Go, but the theories are extremely helpful for simpler but still non-trivial games like Dots-and-Boxes.

9781568811307.jpg

The CGT bible is Winning Ways for Your Mathematical Plays, a four-volume set of books (for the 2nd edition from the early 2000’s; the first edition from 1982 was in two volumes), by the eminent mathematicians Elwyn Berlekamp, John Horton Conway, and Richard Guy.

The basic idea of CGT is to develop a calculus, which lets you assign a value to a position in the game. One normally considers games with the condition that a player who cannot move loses. If both players are without a move in a position (whoever moves loses), the position is assigned a value of 0. If the player on the right can make one move that transforms the position to one of value 0, and the player on the left cannot move at all, the position is assigned a value of 1 (if the roles are reversed, the position has value -1).

Now what happens if the player on the left has a move to a position of value 0, and the player on the right has a move to a position of value 1? What is the value of that position? It turns out to be worth 1/2, as can be seen by considering the position obtained by adding such two such positions together with a position of value -1, when one gets back to a position of value 0 where whoever moves loses (I’ll let you work out the details).

There are more different kinds of values than just fractions. Berlekamp, Conway, and Guy consider a multitude of different interesting games, which give rise to ever deeper mathematics, and game positions with strange values along with complex rules for combining those values.

The writing is informal, with constant punning, but the mathematics is serious. Still, one charm of the field is that there is no pre-requisite mathematical material needed to understand these books–bright high school students can launch right in.

After finishing “Winning Ways,” the ambitious student can move on to the two volumes “Games of No Chance” and “More Games of No Chance” (note that nearly all the papers in these books are available online), and then move onto the rest of the papers collected at David Eppstein‘s CGT page.

Also, take a look at Aaron Siegel‘s Combinatorial Game Suite software to help you do CGT computations.

There’s still much more to say, but I’ll leave that for other posts.


Follow

Get every new post delivered to your Inbox.

Join 25 other followers