Lukas Biewald

This comment, buried deep in an article on kuro5hin from 2002, expressed a deep way to think about complexity through games (it came from an excellent article that summarizes why Go is such an amazing game):

Chess and Go provide one of my most often used models for different types of complexity, particularly that arising from rule-based or algorithmic systems.

Chess has a fair amount of complexity built in explicitly - there are lots of different rules and special cases for different pieces and situations, so the structure and pattern that makes the game fun develops out of this overt complexity.

Go, on the other hand, has (depending on how you count) somewhere between 2 and 5 rules. That’s it, and everything develops by implication from this axiomatic foundation. The structure and pattern (and implications strong enough to be rules) develops or grows out from this simple core.

This is not to place one over the other - I just find it a useful model in many circumstances. I find many systems tend to evolve from one to the other over time, and most have elements of both in their various aspects. Some examples off the tip of my head, all of which can of course be debated:

* perl is chess-complex, lisp and scheme are go-complex.
* legos used to be go-complex when they had a few very general pieces, now they tend to be more chess-complex (lots of specialized pieces).
* science tends to be a motion from chess-complexity (lots of descriptive special cases) to go-complexity (general rules that imply the special cases).
* feudalism and hierarchical power systems are chess-complex, democracy a bit more go-complex, though this is complex (heh).
* free-markets are go-complex, managed markets chess-complex.

And so forth. Drink enough coffee and everything starts to fit into place…

Barney Pell (CEO of Powerset, where I work), told me that he wrote his dissertation on randomly generating chess-like games. He commented that most of the generated games were “interesting”. I could never imagine building a random generator of Go-like games and have any of them be interesting. That’s what makes Go special.

I will post about my 3d go theories and implementations soon…

Steven Landsburg makes a compelling argument that you should give all your money to a single charity:

You might think that you want to diversify your giving like you diversify your investments, but if the amount of money you’re giving is small compared to the total contributions to the charities in question, risk is not an issue. You can check out the economist math but the argument is very clear.

Landsburg comments:

People constantly ignore my good advice by contributing to the American Heart Association, the American Cancer Society, CARE, and public radio all in the same year–as if they were thinking, “OK, I think I’ve pretty much wrapped up the problem of heart disease; now let’s see what I can do about cancer.” But such delusions of grandeur can’t be very common. So there has to be some other reason why people diversify their giving.

I think I know what that reason is. You give to charity because you care about the recipients, or you give to charity because it makes you feel good to give. If you care about the recipients, you’ll pick the worthiest and “bullet” (concentrate) your efforts. But if you care about your own sense of satisfaction, you’ll enjoy pointing to 10 different charities and saying, “I gave to all those!”

I think this is a very compelling argument.

But what if everyone acted like this? Would it be a good thing? People’s estimated utilities of a given charity are not independent. Imagine if everyone had exactly the same beliefs about which charities did the most good. In that case you would start to care a lot about diversification. But that doesn’t seem to be the case.

When Yahoo Answers started, I was working at Yahoo and a little skeptical. But I have completely changed my mind:

Last night I was playing Zelda and got stuck. I have no patience for this kind of thing living in a world with FAQs and walkthroughs, so I went straight to Google. But the particular way I was stuck was too embarrassingly simple for any website to mention (I think I’m getting old and don’t understand the logic of modern videogames).

Finally, I went to Yahoo Answers and typed in the question:

“I died in the Faron Woods and I had left my horse there. I restarted outside of the gate and now I can’t get over it. But I think my horse is inside the gate. Any way to cross the gate without the horse or find my horse?”

In three minutes I got this response:

“There is a tunnel that is to the right of the gate a bit. Go to it and crawl through. To do that, just stand at the mouth of the tunnel. It will ask you if you want to enter. Just push “A” and then crawl forward. If it’s the other gate (there are two), go through the tunnel to this gate anyway. On the other side, there is some horsegrass. Pick it and blow it. Epona will come to you. There may be some horsegrass in Ordon village, too. I’ve forgotten if there is or isn’t. But the horsegrass is the key.”

Three minutes for a detailed answer like that?! I think the same question on a newsgroup might have worked but it would have taken hours. The Internet is an amazing place…

I was once at a party and I overheard the following conversation:

Undergrad: “What do you study?”

Grad Student: “Algebraic Topology.”

Undergrad: “Is it hard studying something so abstract?”

Grad Student: “Oh no it’s very applied.”

Undergrad: “Really? What for example?”

[[Long awkward pause]]

Grad Student: “I can prove that somewhere on earth there is no wind.”

I am so glad I didn’t to grad school in math. If you would like to learn more: http://en.wikipedia.org/wiki/Hairy_ball_theorem. I do remember thinking it was a nice result and a little surprising.

I love simple job interview brainteaser style math puzzles. But these days it’s rare for me to hear one I haven’t already heard. Since Mike posted my math post to reddit.com I’ve suddenly gotten thousands of visitors. Do any of you know any good ones?

Two of my favorites that you might not have heard:

(Told to me by my friend Travis Kopp)

N people are in a room. Each person has a number from 1-N (not necessarily unique) written on their hat, so that they know everyone else’s number, but not their own. Simultaneously, they must all guess the number written on their own hat. Can they come up with a system so that at least one person will always guess correctly?

(Told to me by my friend Ben Blum)

2N people are labeled 1-2N (no duplicates) at
random by a referee. None of them know their labels; the point of the
game is for each person to find out their label. Each person gets to
ask the referee N questions (half the number of players) of the form
“Who is labeled k?”. From the start of the game, the players are NOT
allowed to communicate or even see what the other players are asking. They can
only devise a strategy together before the game begins. They only win
if EVERY player guesses his label correctly. What’s the highest win
probability you can achieve?

I think the second one is harder and longer to explain, but I think the result is more surprising.

Would a hot woman be more than four times as effective as a 50% discount at selling a car?

Here is a working paper that claims that adding a 2x matching bonus (making your donation effectively half the price) increases donations by only 22%. Worse, increasing the 2x matching bonus to a 3x matching bonus has no effect.

Here is a paper that finds that attractive white female solicitors raised double the average in contribution dollars per hour.

Maybe this is an obvious result, but it worries me as I’m attracted to attractive females and I want to make sure they don’t influence what kind of donations I make (more than any one else).

Random bonus fact: the first paper shows that in “blue” states, even the 2x matching bonus gives no increase in donations. Not sure the statistical significance of this effect — you can check the papers yourself.

For some reason I feel like I should add to this post the fact that I have never voted for a Republican.

The proof that the square root of two is irrational is one of those proofs you see a thousand times. The legend goes that after the Greek mathematician discovered the proof, and thus showed the existence of irrational numbers, he was exiled (The Wikipedia says drowned, but that’s not what I remember). It’s short and cute, but it’s hard to understand the motivation of each step, so you’re left with the feeling that it came out of nowhere. I’m always embarrassed that I can’t remember it.

So when Mike Love showed me this blogs post: http://blog.plover.com/math/sqrt-2-new.html that has a much more motivated and geometrical proof, published in 2000 at first I was thinking there must be a catch. But no, it’s just a really nice variant of a 2,500 year old theorem.

But it turns out a Russian textbook from 1892 also had essentially the same proof.

Anyway, here it is (from http://www.cut-the-knot.org/proofs/sq_root.shtml ) If you haven’t seen it before, you should take a minute to admire it:

(1) if sqrt(2) was rational, you could scale an isosceles triangle by some number to make the smallest such triangle with all integer length sides.

(2) But then you could construct a smaller integer-side isosceles triangle as below:

(3) But you just said you had made the smallest such triangle. Quod Erat Demonstrandum.

The “New” Way:

The Russian textbook way (left) and variation (right):

Either way it is such a beautiful proof, and I will never again have to worry about someone asking me to show that the square root of two is irrational. But why didn’t the Greeks come up with the more direct and much more geometrical version?

My friend Mike Love (http://mikelove.wordpress.com) showed me this amazing Harpers essay, The Ecstacy of Influence. It’s one of my favorite authors (Jonathan Lethem) talking about one of my favorite issues (intellectual property).

The best part is that he plagiarized the whole thing! I completely missed that until the end, although at one point I was thinking he sounded a lot like Lawrence Lessig, and I kept thinking wow, there are so many amazing quotes I want to write down.

I remember Lethem discussion in “The Disappointment Artist” about his obsession as a teenager of finding the root of any art. He would watch a movie and like it, but then he would discover an earlier movie that influenced it and want to watch that and no longer like the first movie. Somehow this ended up with him really liking Bob Dylan.

I remember deciding as a teenager that I would only spend my attention on very contemporary art. If so many artists used incorporated an older work in their art, wouldn’t at least some of that art be better than the original? Why waste your time with the inferior older stuff? In some ways I still have this sensibility: for example most of what I read for fun is contemporary fiction. Maybe it’s ironic that this includes Jonathan Lethem.

But anyway, that essay was awesome. I think Lethem might also be in my top five people I would like to meet.

The overwhelming feedback about this blog so far is that I should not fill this blog completely with technical posts. So I will try to take a break from the Powerset and Wordnet themes. (Which both need a part 2 I think…) Because you need to know:

Super Monkey Ball 1 and 2 (http://en.wikipedia.org/wiki/Super_Monkey_Ball) are the greatest video games ever made. For a long time I thought the only people that knew this were me and my close circle of friends, but the internet has revealed that other pockets of nerds have independently come to this conclusion as well. Don’t be confused by Super Monkey Ball Adventure — it’s awful. But even after that bad experience I spent 500$ on a Wii in order to play the newest Super Monkey Ball game (which has a few flashes of the original brilliance).

I always felt that the levels in Super Monkey Ball 1 and 2 had to be designed by a graphics programmer. There levels consist of so many interesting curves, and not just chunks of cylinders and spheres pasted together but beautiful, smooth, mathematical splines.

With no knowledge of the videogame industy I imagine this: In the old days, the programmers would design the levels, and you would often see this beauty, but now they make tools for graphic designers. The artists make everything more realistic and sometimes more visually appealing, but you never see the same kind of overall vision because they are constrained by the programmer’s tools.

I think my hunch was finally confirmed in the final level of SMB 2 when someone slipped in the famous Utah Teapot (http://en.wikipedia.org/wiki/Utah_teapot) a reference that would only be understood by graphics programmers.

I could go on and on about the brilliant details and the love that was obviously put into these games, but the best thing and the unique thing about SMB 1+2 is that each level exists as a single pure thought. Unlike other great games in the genre (http://media.ebaumsworld.com/swf/n-game.swf) there is only one idea per level, and every detail contributes to the idea. Sometimes it’s running through a maze pasted onto a rotating cube, or sometimes it’s rolling up a 3d geometric spiral, but that’s all there is. There’s no random add-ons at the beginning or the end to make it a little harder or longer. Because of this, although it’s a game based on reflexes, once you can visualize beating it, you quickly will beat it. And that makes it fun and beautiful.

I always wondered what changed after Super Monkey Ball 1 and 2, and it turns out that the lead designer Toshihiro Nagoshi was promoted after Super Monkey Ball 2 and didn’t work on Super Monkey Ball Adventure (the bad one). I guess he came back as an advisor to the Wii version (the mixed one).

I haven’t thought about this much, but I think if I have a thirty minute conversation with any living person, I might pick Toshihiro Nagoshi. There’s a hilarious interview with him here: http://games.kikizo.com/features/sega_toshihiro_nagoshi_iv_jun06_p1.asp.

WordNet (http://wordnet.princeton.edu/) is an amazing project that attempts to enumerate all concepts and put them into a hierarchal structure. I’ve spent a lot of time dealing with it at Stanford, Yahoo, and Powerset. The whole time I’ve been working on it, I’ve been forming a rant in my head, and now that I have a blog like this I think it’s time to let it out:

Are concepts really a hierarchy? I’ve heard cognitive scientists think so, but I disagree. And I think that trying to make all the concepts conform to this artificial hierarchal structure has turned WordNet into a much less useful resource.

The classic examples of WordNet is the concept (or “synset”) dog. Dog is a mammal. Mammal is an animal. Animal is a living organism. If I know something about all mammals then it’s true for all dogs. If I know something about some dogs, then I know something about some mammals.

I just checked WordNet and it’s even better than that, Dog->Canine->Carnivore (Mammal)->Placential Mammal->Mammal->Craniate->Cordate->Animal->Organism.

Another classic example of WordNet is places. San Francisco->California->United States->Earth->etc.

What do these hierarchical WordNet examples have in common? They are groups of concepts that actually have a hierarchical structure for an unrelated real-world reason. Why was Carl Linnaeus so successful in making his taxonomy of living things, but the no one knows the guy who tried to classify all rocks? Because evolution causes animals to fit into a tree structure due to common ancestors. Rocks don’t have this structure, and depending on the aspect you choose to focus on they will break into different types of categories. Places also have this structure and it comes the political and geological features of the world we live in. Most countries aren’t in two continents. Most cities aren’t in two countries. But sometimes this breaks down: where does something like the Nile River fit into this scheme? (If anyone reads this who really knows Wordnet well, I know that places are related to eachother with the “is-part-of” and not “is-a” relationship, but I’ve seen many people explaining wordnet use this example.)

But this hierarchy completely breaks down for more conceptual things. Is respect in the sense of “respect for my Father”, a type of “attitude” or “politeness” or “filial duty” or “ affection?” Clearly it’s all these things. But the guys making WordNet didn’t want to believe that, so they make respect as a type of attitude one semantic category, and respect as a type of politeness another, and so on, until there are ten separate senses for respect.

It breaks down even more with metaphors. Take the verb plant, as in “plant flowers in the garden”. It’s a type of “put”. But what about plant as in “plant a foot in his ass” – is that the same semantic category?

Since the parent of plant (a foot in his ass) is more naturally “insert” it becomes necessary to make a separate entry for this type of plant. But then what about “plant fish in a river”? The parent of that should be stock, so it becomes another category. There’s a total of six senses for plant, but five are metaphorical uses of the first one. I’m surprised they stopped at six. The verb run has around forty senses.

So do the mind experiment: do you think all meanings are in a strict hierarchy in our mind? Certainly our brains encode semantic relationships, but why don’t you think it looks much more like a bush (a.k.a directed acyclic graph)?

…

I guess this post is getting way too long, so I’ll stop here. I respect the daunting task of WordNet, and as an engineer I hate when people complain about meaningless details of a large project. But this unnecessary forced hierarchical structure makes WordNet almost unusable for some purposes.

To be continued…

Preview:

The most insidious thing about the forced hierarchy is people naively believe that two very similar senses will still be close to each other in this hierarchy of meaning. So if we have two similar meanings of respect they should have a common parent or at least a common grandparent.

(BTW: I know sometimes words have multiple hypernyms, but it’s rare and doesn’t affect my argument.)