Friday, January 30, 2009

Go is like Crack

Go is something unearthly . . . If there are sentient beings on other planets, then they play Go.

-- Emmanuel Lasker, former World Chess Champion

I played Go for the first time a few months ago. Fortunately for me, I didn't play enough to understand how amazing it is. That changed this week, and my work-Go balance (Go-life balance?) has tanked as a result.

Go is an ancient, originally Chinese game played between two people with black and white stones on a 19x19 grid. The rules are really simple:
* black goes first
* you take turns putting stones on the vertices (or passing)
* if a connected group of stones is completely surrounded, it's captured
* the ko rule: you can't create the same board twice
* the game ends after two consective passes
* territory consists of empty vertices surrounded by your stones. Each vertex is worth a point, as is each captured stone. whoever has the most points at the end wins
* to make things fair, a komi compensates white for going second, usually by 6.5 or 7.5 points. The extra .5 ensures that games are never tied -- they have a binary outcome.

Chess is Baroque by comparison. Despite its simplicity, Go is very deep. The average chess position has about 25 legal moves available to the current player. A typical Go move is chosen from about 250. (Since it's a 19x19 grid, the first move can go on any one of 361 vertices.)

The real reason I started playing Go, though, isn't because of its simplicity, beauty, or depth. It's because Go is fun and because I learned that computers can't do it.

In 1999, IBM's Deep Blue beat Garry Kasparov in tournament chess. It was a giant machine with about 4000 special-purpose chips, dedicated to evaluating literally billions of chess positions per second. In other words, Deep Blue beat Kasparov by brute-force attack, thinking as far as forty moves ahead on some turns. A very intelligent person lost to a machine with lots of number-crunching power, but no intelligence at all.

Go is not like Chess. There are simply too many possibilities for any kind of exhaustive search. Like Chess, humans play it with advanced pattern recognition and and with directed strategies. Go differs from other games, however, because humanlike intelligence seems to be the only way to play well. Humans balance lots of difficult trade-offs -- is it better to keep playing in a part of the board with lots of activity, or to jump away and stake out a territory claim somewhere else? Is it better to go for secure territories along the sides of the board or influence over the center? Better to finish an impenetrable fortress or to branch out and make a bigger, more porous one? Questions like that take experience, intuition, and lots of pattern recognition to answer well. They can't easily be forced with faster algorithms and bigger supercomputers.

The best Go-playing programs today are using Monte Carlo sampling, like the stuff I blogged about earlier. Running on computers three orders of magnitude faster than Deep Blue, they're on par with skilled amateurs. Earlier this month, one program became the first to defeat a professional Go player in a tournament match--by accepting a massive nine-stone handicap. For now, Go is a game where real intelligence isn't just helpful, but required. There are few others like it.

Go is simple, yet radically open-ended, and it seems like a uniquely human game. Could it be AI-hard? We'll find out. Lots more info and links at the Stanford Go Club. I would write more, but the night is young, and it just became my turn to place a stone.

Tuesday, January 6, 2009

Winning science fairs

... I've never done it, but I did get a "third award" at Intel ISEF '07. That's International Science + Engineering Fair, and it was one of the most fun things I've ever done. My friend Tom and I built the project, took it to regional fairs, improved it between each fair, and of course partied the nerdy way for a week at the main event. Our project was on Stirling Engines, building four from scratch. The last two worked.

We built the engines using parts from my garage and from Home Depot. The last engine also included two borosilicate glass-graphite piston cylinders generously donated by Airpot. The Riverton Science Department hooked us up with real-time pressure and rotation sensors. The end result was an engine that could run on a candle and a faster one that ran off of a propane stove; we measured the thermodynamic cycle of the second engine, creating and experimental PV diagram.

My partner-in-crime Sawyer just facebooked:
Hey! You went to ISEF a while ago, didn't you? Any advice on choosing a project?

Sure! In my unhumble opinion, engineering is the way to go.
Pick something fun or cool, because then you'll spend time on it and make it great. Also, pick something that you can build. I have way better experience with that than doing pure science or math, at least in the context of a science fair. (Science fairs are really science/math/engineering fairs; I like the engineering part best.) If you do pure math or science, then you'll need a mentor. Many entrants in those categories, even at Utah-level fairs, partner with university professors; needless to say, it's very hard to compete if you're going it alone. Building stuff is different; you need a lot less arcane knowledge. I wrote some of the programs I'm most proud of before I had any formal CS training; my friend Nathan built a car -- from scratch -- that does 0-60 in under four seconds -- before he went to Stanford and took introductory mechanical engineering. If you're excited about it, if you persevere, and if you're willing to use Wikipedia a lot, you can learn as you go and build really cool stuff.

I also recommend building something physical. You can enter a computer science project, but you'll have plenty of chances to code. In my experience, the clubs, groups, and other orgs you'll be part of in college never have enough programmers. Web developers are especially in demand -- you'll spend lots of time sitting in front of a screen hacking apps into existence. Science fairs are your chance to design, machine, tinker with, and generally build stuff, and get recognition for it. Companies sponsor you. Teachers love it and are often very helpful. It's a very good deal, and one you really don't get once you're out of school. I can't overstate how great an experience my project was. Find something interesting and build it. You'll rock the science fairs and get more out of it than you can imagine.

(Tom and I at Sandia National Labs. One of our judges invited us to come see his project there: harvesting solar energy with Stirling engines. The dish focuses sunlight onto the hot end of a 25KW engine. The other side is cooled with a radiator.)

Thursday, January 1, 2009

Celebrating 2009 the manly way

... with Patrick's New Year's resolutions. His story:

So, I watched "Wanted" again tonight instead of going out. And you know what? I probably had more fun that way. 2009 is going to be my year, the year that I stop trying to live like everyone else, justifying my unsavory actions by the social acceptance in our decadent society...and other non-pompous reasons. I will not bore any readers with any sort of analysis of my faults. Those are irrelevant. What matters is how I'm going to fix things. So, let me begin...

1. I will no longer be scared by my (lack of) potential. I have put myself on the path of the creator, the writer, and I will no longer hold myself back by a terror that I will not live up to anyone's standards. So, for 2009, I vow that by the end of freshman year, I will write/direct/create something that I am proud of. It will be my vindication, my tangible proof that I deserve to call myself an artist. For you see, I watched "Wanted" for reasons other than to see mind-blowing action and Angelina Jolie's fantastic ass. The beginning of the movie scares me. I see visions of Wesley in myself, a bright young man, suddenly waking up out of his stupor and wondering where the last ten years went. I don't intend to assassinate anyone but I am ready to rise up, step into the shoes that have been waiting by the door of life for as long as I can remember. So, I will create, I will prove myself.

2. I will work out. Several years ago, I exercised with a vigor I had never shown anything before. I was fit, toned, and a damn sexy beast. The trouble was, I was still too shy and withdrawn to stand out to anyone except my closest friends. So, my transformation went unnoticed. I felt fantastic but I was too immature to care about anything other than what others noticed. I slowly lost my will power and gave up. Rabbit food turned back to junk food and fab turned back to flab. No one noticed this either, except my dog who started enjoying the left-overs a lot more. Since then, I have tried several unsuccessful times to start again but it never took. I lacked the devotion. Until now.

3. I will stop chasing girls with which I have no chance. I cannot even begin to describe how much time I waste thinking about the fairer sex. That is not to say I forgo romantic involvement. Instead, I will not seek it out needlessly like a crack addict looking for his next fix. I will leave that to sluttier people than me (Adam O. and Sri, here's looking at you). I will, instead, just let whatever happens happen. I remember about 2 or 3 months ago, I was laying on the roof of the dorm late at night. I was stargazing and thinking about girls. Suddenly, I saw a shooting star go streaking across the sky. My first thought was that I had to make a wish. My second thought was, "Please, let me find someone that I can care about." Even though circumstances have changed since then, that wish remains. No more chasing, no more games. Please, let me simply find someone that I can care about.

4. I will be a manly man. I will stand tall and proclaim the words from the hills, blowing a sea shell, my man blouse billowing in the wind. I will drink unleaded and shit mustaches. Mountains will quake and panties will vanish into thin air. I will ride an imaginary horse and call it a steed like the pretentious prick that I am for I am a manly fucking man. I am Sir Patrick Sean Kelly TM the 17th, beyotch!

2009. Here I come.