Tuesday, May 24, 2005

Only a sith thinks in absolutes

So, I went to see star wars last night with 900 other geeks from Caltech.

There's one line from the movie that nobody's going to understand in 20 years. The line has nothing at all to do with the movie, and everything to do with the politics of W. Bush. Yes, if you've seen the movie, you've already recognized the title of this post as being from the dialogue between Obi Wan Kenobi and Anakin Skywalker as they fight in the volcano world of Mustafar. The dialog goes like this:

Anakin: "Either you're with me, or you're my enemy"
Obi Wan: "Only a sith thinks in absolutes"

Now, let's all admit that this is a pretty good jab at W. But, if you take the second line seriously for a moment, as if it is really from the movie, it makes no sense. Not only does it make no sense, but it sells out the basic premise of the entire series of movies, which is Jedi versus the Dark Side Of The Force. Good versus Evil, damnit! The Jedi are the ones who see the world in terms of good and evil. In my opinion, Lucas pretty clumsily pushed his analogy past its breaking point with this line.

And I was on board with the analogy too. Yes, let the Galactic Empire be the United States! Let Darth Vader be George W. Fine with me, although I wouldn't give the US president credit for having any extra midichlorians. Damnit Lucas, why did you have to mess it up by also turning the Jedi knights into postmodernist liberals. Still, given your tack, there was an obvious continuation:

Anakin: "Either you're with me, or you're my enemy"
Obi Wan: "Only a sith thinks in absolutes"
Anakin: "Actually, that's a misunderstanding. We Sith aren't really about 'good' or 'evil', we mostly just use the force as a means to our own ends. If you think about it, the Jedi are more the ones thinking in terms of absolutes."
Obi Wan: "yes, well what I mean to say is, you're accepting the narrative of the oppressor; try listening to the narrative of the oppressed."
Anakin: "What?"
Obi Wan: "Just give up, I have the high ground."
Anakin: "You think confusing me gives you some kind of moral superiority?"
Obi Wan: "No, I mean that if you jump at me, I'll cut off your good arm."
Anakin: "Oh, so it's back to the movie then is it?"

Thursday, May 19, 2005

Funny betting game

So, I play poker sometimes, and one aspect that really interests me is the game-theoretic aspects to betting. Here's an interesting abstraction of a certain situation involving repeated bets (i.e. pre-flop, flop, turn, river).

There are just two players. Each player can put any amount between $1 and $100 into the pot, and each chooses his amount secretly and independently of the other. If the amounts are unequal, then whoever put more money into the pot wins.

Now, there are two superpowers in this game, a tie-breaking superpower and a pot-stealing superpower. the tie-breaking superpower is you get to win in the event of a tie, which means if you put in $100, the other player can't beat you by putting in a bigger amount. The pot-stealing superpower is invoked when an ace comes off of the top of a shuffled deck of cards, in which case the player with that superpower automatically wins all the money. The pot-stealing superpower takes precedence over the tie-breaking superpower.

The question is: which superpower would you pick? Also, how would you play the game?

Tuesday, May 10, 2005

Computer go v. computer chess

What do you know about computer go?

There is a phenomenon that current computer programs for chess are on par with international chess grandmasters. Meanwhile, the best computer go can't even compete with average players who have played for a year.

What's the difference? Well, the common arguments are to the effect that go has a "bigger branching factor" because there are so many more possible moves in a typical position. This allows chess programs to look ahead up to twice as many moves ahead as a go program, given no pruning at all. Another reason is that chess programs can use sophisticated opening and endgame databases, and thus are really only able to lose a game in the mid-game.

This analysis is undermined if one notices that computer go is equally skillful (or unskillful) at playing 9x9 go as it is at playing 19x19 go. In 9x9 go, the branching factor is much closer to that in chess (around 40 moves on average). Again, opening databases can be used, and very few games are won or lost in the endgame anyway.

So, why do computers suck at go? The answer is that they don't suck at all. Rather, we humans are just much better at go than we are at chess. Spacial symmetry and spacial reasoning is much more meaningful in go than in chess, and we are good at spacial problems.

Go is a game where we win by proving to ourselves that a certain move is "good enough", not by finding the best move. Even pros play this way. In go, there are often many variations on a particular play that lead to essentially the same result. Though the stones might be in slightly different positions, we can see that the differences are either trivial or else don't matter at all. Our minds automatically fold these possibilities into each other and we forget about the unimportant differences. The effective branching factor is thus much smaller for go than it appears.

Logical separation of the action in different parts of the board is also possible in go to an extent that is not possible in chess. Long-range dependencies certainly exist in go, even on a relatively empty board, and good players take advantage of them. However, we can play reasonably well by forgetting about them, and it can save a lot of mental effort. That's a good trade-off, especially in the positions where we can prove to ourselves that the positions are truly independent.

These reasons make go a much more interesting game than chess in which to pit computers against humans. Sure, computers can beat us at chess using tree search and clever hacks. To beat us at go will take much more. Computers will have to think a lot more like we do.

Go is a game that offers big rewards for players that possess skills native to humans, to an extent that chess does not. The day that a computer became the world's chess champion was a milestone for artificial intelligence. The day that computers beat us in go will be a much bigger one.

Monday, May 09, 2005

Extreme Programming

What the hell is Extreme Programming anyway?

I guess it's a loose collection of software programming practices, philosophies, or just a cult. It looks like a cult because there are a few big advocates and because it's so damn controversial. One reason it's controversial is that it strongly de-emphasizes up front design in favor of methods that make code much more flexible. What methods are those? Well, there's refactoring, which is a way of moving code around so that you create a different abstraction without actually changing the functionality. Another one is pair programming, which strongly encourages the programmer to write readily understandable code.

Back to the controversy, it's more than just the way of presentation that causes controversy. XP gives a lot more responsibility to the programmer, relative to his boss the software engineer, which he hates.

Perhaps the one argument against the hollistic view taken by XP advocates is that it couples the practices that lead to code flexibility with big changes in the way projects are managed. Software evolves, but teams that adopt XP are supposed, in one Great Leap Forward, to change the processes such as UML models and other documentation.

Anyway, the core technical processes of XP are probably here to stay, and they're going to have a positive impact on most teams that choose to use them.

Sunday, May 08, 2005

China v. Taiwan

Well, this is a sticky issue, isn't it. First, let's look at the question of whether Taiwan is functionally an independent nation, shall we? Here are some reasons to take each position. First, the reasons to think Taiwan is an independent nation:

1. Taiwan has it's own government that does not recognize the authority of the Chinese government.
2. As a U.S. citizen, I need a visa to enter mainland China, but not Taiwan.
3. Taiwan has it's own top-level domain name. (.tw), Olympic team.
4. The U.S. and other nations have agreed to defend Taiwan if China were to make military threat toward Taiwan.

Some reasons to believe that Taiwan is not an independent nation:

1. Taiwan is not a member of the UN
2. Almost all nations officially do not recognize Taiwan as a nation.
3. The government of China claims sovereignty over the island of Taiwan.

If Taiwan is not an independent nation, then it might be a part of China, or logically it might be a land mass that isn't part of any nation, like Antarctica, though nobody seriously espouses this position.

The legal status of Taiwan is not agreed to by everybody. The pro-independence position cites the San Francisco Treaty as renouncing Japan's Sovereignty over Taiwan, but does not officially state which nation, if any, is sovereign over Taiwan. China did not sign the San Francisco Treaty.

Historically, China has exercised some degree of sovereignty over Taiwan at various times in history. See the pro-independence position and the pro-unification position on this issue.

So, why should anybody besides the Chinese and Taiwanese people themselves care about the issue? One possible reason is that there is a substantial gap in the status of human rights in the two countries. For a rough, but accurate comparison, worldaudit.org is a good place to start.

Friday, May 06, 2005

Calvin Poker!

Calvinpoker is a blog about poker. The name comes from my opinion about the house rules of a poker game that I play in sometimes. I won't explain how the rule came up right now, but one of the rules that we apparently officially play with is that if a board card is accidentally dealt before the round of betting is finished, we keep the card and finish the round of betting. After the round is over, any player can choose to have the card redealt, but this does not happen automatically. Somebody has to ask for it.

Sounds like CalvinBall, right? From Calvin and Hobbes. Exactly. CalvinPoker.