Dr. Markov

Last week, in CS106X, I programmed Boggle.

Boggle is played with a set of cubes that have letters on each face. You shake them up, put them in a grid, and try to find words made of adjacent dice faster than the other players can.

Computer Boggle is different. It gives you time, letting you find as many words as you can, and then beats your score by an order of magnitude or so by finding all the remaining words on the board that are in the (huge) Scrabble player's dictionary. You can also play 5x5 "BigBoggle" instead of the standard 4x4, in which case the computer generally beats you even more thoroughly.

One of the cool things about CS106 is that they don't just want solutions, though. It's good style to extend them in some way, and solve some additional problems that weren't in the assignment. For Boggle, I wanted to write code that would find boards with unusually few (or many) words, using only the standard cubes.

So I tried Markov chain Monte Carlo, which I'd Wikied a long, long time ago when I was really into raytracing.

In a nutshell: the algorithm tries to find a global minimum of a function that can be sampled and which is roughly continuous, but which may be in many dimensions and may not have any other nice properties.

You start with a guess.
At each step, you find a distribution centered at the current guess and randomly sample it. If you know what the global minimum should be (e.g. zero) the variance of the distribution will vary with the cost (the value of the function at the current guess), so that if you're far away from the minimum, you're sampling over a wide area, while if you're getting close, you make more incremental guesses. Each 'probe' sampled this way is evaluated, and then you randomly decide whether to accept or reject it, depending on its cost. If the probe cost is significantly lower than the current cost, then you almost certainly accept it, and if the cost is significantly higher, then you almost always reject; in between, it's a toss-up: if you accept, then that probe becomes your current guess, and if you reject, then you keep probing.

Doing all this with Boggle boards took a bit of approximation and rule-of-thumb coding because I don't know a way to actually define a probability distribution over the set of possible Boggle boards. Instead, I defined 'swapping' as taking two cubes at random, switching their places, and randomly rotating each one. I started with a standard, randomly-generated board and, after each evaluation, did a number of swaps proportional to my cost function, with a maximum of about ten. When the guesses started getting so good that I wasn't switching any cubes, I picked single cubes and rotated them randomly to create new probes. The idea is similar: the closer you get to a global minimum, the closer your probes are to your current guess.

I made two cost functions, one preferring boards with lots of words and and the other preferring boards with few words. I already had a function that could quickly search a Boggle board and find all the words on it.

The result: it worked. I was surprised.

BigBoggle boards tend to have around 150 words on them. Here's one with no words at all:


On regular boggle boards, the computer will score ~90. Here, it scored 917:


The code is private because of academic policy, but if you want to play with the program, it's here.

Markov chain Monte Carlo rules.

Timesinks

The internet makes lots of tasks infinitely easier than they used to be. Want an executive summary of the War of 1812? Check Wikipedia. Want to know more? Keep reading. If you're really hardcore, the article lists eighty-two scholarly references. Need an obscure book printed by some shop in Khazakstan? Amazon can probably ship it to you for free in ten days or so. Want to convert a kilowatt hour into BTUs? Google "a kilowatt hour in btus". I have no experience here, but I bet that before the web, lots of these tasks would have taken minutes or hours rather than seconds.

Isn't it strange, though, that such a powerful tool for getting stuff done gets used so extensively for the purpose of not getting stuff done? I can't think of another way to explain the fifty-or-so bits of chatlist spam that land in my inbox every day, the SuperPokes, the pirates, the ninjas, the lolcats, and everything else along those lines. Even respectable, otherwise interesting sites like Digg and Youtube are filled with mildly funny, mildly shocking, and mildly sexual banalities.
A while ago, I posted about Twitter, the flagship time-waster-in-chief of all web 2.0 apps. Never before has humanity been this effective at wasting time.

I don't think that lost time is the real problem, though. When the novelty wears off and everything else they could have done with all that time sinks in, people will stop. I'm worried about money.

Parallel to this Cambrian explosion of "web 2.0" apps, replete with tweets, pokes, nudges, posts, threads, and lists, there have been all sorts of new revenue models, further and further removed from the sale of actual goods and services to consumers. Take Slide, Inc, which recently got a $500m valuation from some venture capitalists. It makes slideshow widgets (and little gems like "SuperPoke Pets!") which it plans to monetize by integrating targeted ads into users' slideshows. Many of the ads I see (and ignore) all the time are already advertise other ad-supported sites that don't actually sell anything. It's only a matter of time before I see some ads for Slide.

I think that the system by which dotcoms are funded today looks suspiciously like the way they were funded in the nineties. People are spending way too much money building castles in the air.

Someday, people will tire of spending so much time connected to each other, wasting each others time. The torrent of tweets, pokes, FWD:fwd:Fwd:Fwd:funny pics, and all their unholy brethren will start slowing down as people take back the time that used to be theirs. Maybe someday, sending pointless emails to a chatlist will have the same social stigma that shouting across a crowded room might have now. Maybe the parents of 2015 will tell their kids to finish their homework before they comment on each other's blogs. Maybe they'll warn their kids that too much Twitter rots your brain, or that Facebook bullies are probably just looking for attention and are best left ignored. Maybe someday, I'll log into Facebook and nobody will care what my hooker name would be. I can't wait for that day to come!

Let me skip back for a moment, to the first stock I ever owned ~ two shares of Microsoft, back in 1998 when I was in second grade. My best friend's dad thought that a market in which grade-schoolers own stock couldn't possibly be sustainable. He was right. Today, we've got a market in which investors bet billions on web startups with Rube Goldberg business plans, with almost no connection to reality. They're betting on people barely older than myself trying to capitalize on the time-wasting habits of people, often a lot younger than me, by showing them ads. As people become savvier and the web becomes fully integrated into our culture, my guess is that many dotcoms will be winnowed out in a second crash.

President Obama

This past weekend has been a blur. Some of my fellow students and I went to Las Vegas to help swing Nevada to Obama's side. We drove all day on Saturday; we worked on Sunday and Monday. I woke up at five on Election Day to put up door hangers, stayed up until one in the morning with the most energetic crowd I've ever seen, and woke up at five yesterday to fly back to California.

All the campaigning and partying, while fun, was on some level superficial. I got into some heated arguments with a junior in our group who seemed to be channeling Karl Marx, and into some more interesting arguments with other, more moderate fellow campaigners. For the most part, though, we focused on the very vague messages of "hope" and "change", and passed out policy fliers to the handful of people who wanted to know more. Nobody really asked the question of what America would become (or, now, will become) under an Obama presidency.

I've been looking for some good opinions. I thought that this article had an interesting take on it.

Like lots of what's been published since Election Day, it focuses pretty heavily on race. I'm more interested in what will happen to the economy. At least for the national debt, change seems like a good thing. Obama's tax plan has always bothered me, though.

Like most of us, I'll wait and see.

If there's one thing thats unambiguously good, it's that people care now. Lots of them who never voted before, voted this time. Students stopped ignoring politics. If you'd asked me just a few weeks ago, during New Student Orientation, what I thought about the next four years, I would have been gung-ho and pretty self-centered: Yes, Stanford will be fantastic. I'm still excited about the next four years, but like lots of other people I think about them in a broader way. What are we doing to help bring change?

Waltzing cubes

Lucas, who I know from math and CS, has an absurd number of Rubik's cubes. He has the standard cubes in every size from 2x2 to 5x5. He has combinatorically ridiculous 7x7 cube that probably takes days to solve. He also has variations like square one. In a few weeks, he'll get a package from Japan and in it will be a void cube. (How you would build something like that without breaking the laws of physics is beyond me.)

Years ago, Lucas also made a Rubik's cube waltz. This means: he scripted and raytraced the whole animation in POV-RAY and Mathematica. Props!

Happy Birthday!

to you.

Congrats!

Sticking it to the Man

My classmate Ravi had a cool, but not neccesarily original idea. He wants to pay his $50,000 tuition in nickels, starting with the next ~$17,000 quarterly bill.

I love Stanford and if it was up to me, I wouldn't change anything -- except, of course, the tuition. Stanford's endowment grew by 23% to $17b last year, which means that they made about $200,000 for each student in every school. Most undergrads are on financial aid, but those who aren't pay more than $50K a year -- not a particularly large item on Stanford's balance sheet, but huge for a lot of the parents who write the checks.

And it's not just parents. Lots of us, especially grad students, leave with ridiculous debt loads. If I've gotten anything out of the market meltdown that we're in the middle of, it's that ridiculous debt loads are a bad idea.

Financial aid is difficult, too. Need-blind admission does a reasonable job of ensuring that everyone who gets in can come, but it doesn't guarantee fair treatment. At best, it lets smart kids without money or college degrees in their family come to Stanford and become seeds of change, close the poverty gap, and live happily ever after. At worst, it penalizes parents who work hard and save and subsidizes the ones who outspend their incomes.

If Ravi actually manages to wheel-barrow a million nickels to the Registar's Office, I'll be there, blogging the pictures and videos for you.

President Palin

Matt Damon had a some thoughts on the danger of Palin becoming President in a recent interview.

Then, yesterday, Palin spoke her mind on education.

Say it ain't so, Joe, there you go again pointing backwards again. You preferenced your whole comment with the Bush administration. Now doggone it, let's look ahead and tell Americans what we have to plan to do for them in the future. You mentioned education and I'm glad you did. I know education you are passionate about with your wife being a teacher for 30 years, and god bless her. Her reward is in heaven, right?

(From the CNN transcript of the VP debate.)

Later in the debate, both running mates discussed the possibility of taking over if the president died.

If McCain wins, he'll be the oldest president ever to take office. If he doesn't make it to 2012, Palin will lead the free world in his stead. Scary? Yes. Embarassing? Even more so...

Vote for change.

Putnam math competition

This is really cool. Tonight, I joined the kids here who will give this math test a shot in a few months. We had an overflow crowd at our first meeting.

The professor who's teaching us the ropes in weekly sessions is a great guy.

Here's one problem I did, from the promo poster:

Find the smallest natural number n which has the following properties:
(i) its decimal representation has a 6 as its last digit, and
(ii) if the last digit 6 is erased and placed in front of the remaining digits, the resulting number is four times as large as the original number n.

If n starts with 6, and n = 4k, then k must start with a 1. So:

n = 61 ..,

k = 1 ... 6

Now the cool part: some recursive long multiplication.

Multiplying 6*4 gives you 24, so 4 is the last digit of n. This means that 4 is also the second-to last digit of k. So 4*4 +2 = 18. 8 is the second-to-last digit of n, and third-to-last digit of k. We know that 1 is the second digit of n, so eventually, we have to get to a 1.

    2
1....6
    x4
61...4

   1
1...46
    x4
61..84

  3
1..846
    x4
61.384

25
153846
    x4
615384

This is true. So I think that 153846 is the smallest n that ends in 6 where shifting the digits right gives you 4n.
I love this stuff.

Hello world

This is my first real blog. I started my freshman year at Stanford a week ago today, and it’s been fantastic. There are too many great things to do and not enough hours in a day to do them. So much is going on, in fact, that I think it’s high time for me to write a blog.

I’ll write about Stanford, about programming, about math, and about whatever looks fun or interesting to me.

Onwards…