Lukas Biewald

I can’t stop playing this flash game called DesktopTD I found on Jeremy Zawodny’s blog. It’s the best flash game I’ve ever played, and I’ve played a lot of flash games…

It combines a beautiful Go-like strategy of making interesting patterns to use minimal resources in the most efficient possible way with a satisfying mini-Civilization like progression of building bigger and more powerful things. They also did a really fantastic job of tuning it to make lots of different strategies work well.

After a really embarrassing amount of time playing it, I got to level 48 out of 50 on hard. I challenge anyone to beat that :).

It’s funny how hard it is to generalize games into three dimensions. Almost all board games are in two dimensions, but 3d is so much cooler! Several times I’ve tried to play Go on a cube, but it’s not much fun. Since each center point is connected to six other points instead of the usual four, it’s simultaneously impossible to capture stones and impossible to make eyes. I wouldn’t be surprised if perfect play ends in full board seki.

My old roommate Henry Segerman came up with an ingenious approach: by using a diamond lattice for the connections, he made a 3d board where middle points are connected to only four other points.

The lattice also contains corners with two connections and edges with three connections. You might start to wonder if it’s isomorphic to a 2d grid — one way to see that it’s not is that each internal point takes six moves to a neighbor before it arrives back at itself, while on a 2d grid it only takes four moves.

It’s a much better way to play 3d go than the obvious “3d-cube” method. I wonder what other games could be made into 3d using his method.

If you’re interested, a few years ago I made an arcade version of the game that you should be able to download here. Several friends have asked for the code to generalize it further into topological Go, but as fas as I know, no one ever finished it.

I’ve been swapping cute math tricks with my coworker Paul Pedersen, and recently he showed me this beautiful method for sketching polynomials:

As an example let’s pick a random polynomial:

y⁴ + x³ - y² + x - 1 = 0.

Plot on the x axis of a graph a point for every x power. For example for x³ plot the point (3,0). For x¹ plot the point (1,0).

Now label “+” the positive coefficient’s points and “-” the negative coefficient’s points. Do the same for the y axis.

Now connect the lines.

Now reflect across both axis. If you have an even exponent flip the sign.

Now draw a line between every positive and negative sign.

Now connect the lines. My freehand splines are a little sloppy, but you get the idea…

And there it is. Compare with an actual graph:

Let’s try with some simpler curves where we know the answer: take x² + y² = 1 or x²
+ y² - 1 = 0:

Connect the lines:

Circle!

Just for fun, try x² - y² - 1 = 0:

Connect the lines:

Wow. Why don’t they teach this as part of the high school math cannon? These kinds of simple inexplicable patterns remind me why I loved math in the first place. Can anyone figure out why it works? I’ve been thinking about it for a while but I don’t think I have the right training and tools. I can’t even come up with a rough sketch. Please let me know if you can figure it out!

Update:

(Thanks for all the comments! If you want to plot a function like y=x^3, transform it into 0=x^3-y and follow the above steps and it should work. Does this answer some of the questions?)

Rahul points out an interesting counterexample in x^2+y^2-4x+3=0, but I might argue that in some sense it does work. You end up with a diamond and the x axis has a + at (0,0), a - at (1,0) and a + at (2,0). No other edges should have lines through them. So you would draw a circle. I think it’s clear that this method can’t make any claims about x intercepts and y intercepts, just the overall shape. Same comment about x^4-3x^3+x^2-x+20.

Can anyone find a counterexample where the shape is completely “wrong” (for some definition of wrong that doesn’t include intercepts or stretching)?

∀x ln x < 50

(I remember Andrew Ng wrote this on the board before his Machine Learning class at Stanford and sat there with a mischievous grin on his face. It turns out he had learned it from his advisor but with a 40 instead of a 50.)

I like casually repeating it once in a while when CS Theory guys/mathematicians are around to see how they react. It’s kind of like mentioning to a group of Japanese people that you think all tea tastes like hot water.

I told this to Kenny, who was surprisingly unfazed (I think he’s used to my sacrelidge by now ), and suggested an excellent variation:

∀x ln x < (Current Year - 1960)

I started writing a comment on John Battelle’s excellent search blog last night and it turned into more of a long rant than I expected. I guess I have a vested interest in believing that I work on something that’s not evil :).

What do other people think about Yahoo’s compliance with the Chinese government. I think it’s a fascinating moral issue, and I’m still not completely sure what I think about it.

My take:

Why do we keep blaming Yahoo and Google for the Chinese government’s actions? These stories are extremely sad, and it’s natural to have an emotional response that sides with the victims, but it’s the Chinese government’s fault here, not Yahoo’s. Would we prefer that Yahoo put its own employees’ livelihoods in jeopardy by asking them to disobey an order from the Chinese government? What if the order came from the US government? I understand that the US government can demand similar records of Internet usage, search history, etc.

It seems the only reasonable thing we can ask of Yahoo or Google is to stay out of a country like China altogether. There is no way we can ask local employees to break Chinese laws. Demanding that Yahoo or Google avoid this kind of situation by not keeping logs or by providing some services and not others is really asking for the impossible since there’s so many unpredictable ways that a government could make a Yahoo or Google complicit in actions that we consider unjust.

But can we really ask Yahoo to stay out of China without the US government passing a law that explicitly forbids it? In general I would argue that it’s very dangerous to ask corporations to be socially responsible. I’m not sure how realistic this actually is in this situation, but people often claim that a company’s shareholders can sue their company for trying to be socially responsible and thereby not maximizing profits. Personally, I’m not sure that I actually want companies trying to be socially responsible, because I don’t think I would agree with a lot of the “socially responsible” things they might do, but this is a separate issue. I think we can all agree that our government bears at least the primary responsibility for forcing companies to behave responsibly.

As a separate issue, I wonder how different Chinese and US privacy policies really are. Especially post PATRIOT Act, can’t the US government demand anyone’s internet history logs? I don’t want to pretend that I know this area well, but before we complain about Chinese privacy violations, we should make sure we complain about our own policies.

So first and foremost blame the Chinese government, and if you really don’t want US companies operating in China then blame the US government. And if you still want to blame Yahoo I’m curious about what you really want it to do.

(Disclaimer: I am a former engineer for Yahoo search.)

Patrick had a nice response to my earlier post that asked what do we really mean when we say:

“The president has an approval rating of 35% plus or minus 3% with 95% confidence”

Patrick (Statistics grad student) says:

“The observed data is inconsistent with a true approval rate outside the range of 32-38%.”

I think the tricky part is defining “inconsistent” in a simple way: “Had the true approval rating been outside the range of 32-38%, there would have been less than a 5% chance of observing the data.”

But Kenny (Philosophy grad student) pointed out that Patrick’s explanation is obscuring another detail: “chance of observing the data” — actually the chance of observing any particular data is very unlikely.

So here is my new attempt at a full explanation, assuming they used a t-test (see Confidence Intervals and Beer).

Had the true approval rating been less than 32%, the chance of seeing an approval rating greater than 35% would have been less than 5%.

Had the true approval rating been greater than 38%, the chance of seeing an approval rating less than 35% would have been less than 5%.

Patrick, do you have a better simplification?

Several people have asked me the obvious question: why can’t they just claim something more understandable like the probability of the president’s approval rating being between 32% and 38% is greater than 95%?

Well, not being a statistician or a philosopher I don’t really know, but I do have an opinion :). But this post is too long already…

I had breakfast this morning with my friend Brett, the (soon-to-be-former) Google product manager for Google Labs and News Archive Search. He told me that he gave up Google for lent – using no Google products for forty days. So mostly he was (is) using Yahoo search. And he said except for handling of addresses not working quite as well as he expected, he didn’t notice the difference at all.

Would anyone guess that a company like Google could hold huge market-share with three other completely interchangeable products? Maybe you don’t think they’re interchangeable, but it’s pretty difficult to find a statistically significant relevance difference: for example this study.
And a product manager working on search at Google couldn’t tell the difference.

Maybe you think they have a great brand, but would you really expect this to matter either?

So what keeps people coming to Google? Yahoo has the huge user base, Ask has less ads, and Live has Ms Dewey. Clearly it’s a mix of things, but my guess is that their low latency matters more than people think or are consciously aware of.

I’m not sure what I think about Ruby function injection, but it is pretty cool.

I was looking at this code for adding a sum method to an Array class (enough of this type of thing and I can make Ruby like R with decent syntax which would be awesome):

class Array; def sum; inject( nil ) { |sum,x| sum ? sum+x : x }; end; end

Someone commented with another way:

eval arr.join(’+')

Does anyone find that as hilarious as me?

My Japanese host mom has been visiting and I’ve been trying to learn Ruby, so I’ve been working in a lot of foreign languages recently. I think my Japanese and my Ruby are at about the same level — I’m pretty sure I can express anything I want, but it takes way more energy.

The coolest thing about a foreign language is that you learn to express many things in the new language that you can’t quite express in your native language. For example, I was recently trying to explain my relationship with my coworker Chad. We worked together at Yahoo where he was the search run-time architect. We hung out on the bus and he taught me a lot about how search engines work and the search industry in general. He was a big factor in my decision to leave and now I’m working with him again at Powerset. Is he a mentor, a friend, or what? In Japanese I would say he’s a senpai but there’s no concise way to say it in English.

Ruby is the same way. In Perl, it wouldn’t be hard to calculate the minimum distance between where two keywords occur in a document, but in Ruby I can do it in a single easy to read line (not the most efficient implementation, but it doesn’t matter in this case):

min_dist = loc1.map { |l1| loc2.map { |l2| (l1-l2).abs } }.flatten.min;

There so many more interesting things to say about Japanese and Ruby, but I think I should save them for future posts…

This post is a little off-topic, although I’m not totally sure what the topic of this blog is exactly.

One of the reasons I started this blog was to practice writing (I think my math training has made me a significantly worse writer – but that’s another post ☺. ). And so I’ve been thinking some about who I want to write like. But if I could write like any one person, there’s no question who I would be: Dahlia Lithwick, a senior editor at Slate who writes a column “Judisprudence. It’s pretty random, there’s not many journalists I can name, and while I’m interested in the law, there are lots of things I’m equally interested in, but I just kept noticing that my favorite articles were all written by the same person. She’s concise and direct, but playful at the same time. More importantly, she comes across as incredibly thoughtful, insightful and open-minded.

Unllike most of my preferences, this one was completely uninfluenced by my friends. I might actually think that I was alone in my obsession with Lithwick, except that with the internet you can always find someone more obsessed than you about anything: a random law student actually made actually made a fan site…

If you’re interested, one of my favorite recent articles is How We Fool Ourselves into Believing We’re Dispassionate about the Duke Case” (by far the most reasonable thing I’ve read about the scandal) and a hilarious contest she had afterwards.