Lukas Biewald

I’ve played so many games in my life I have to hope it’s had some effect on the way I think. Lately I’ve been thinking every great game has some non-obvious strategy that makes it interesting and also teaches a more general principle that can be applied to life.

Here’s my list:

• Go

  Always play the move that feels aesthetically correct over the one that seems to help your tangible short term goals. A good example is creating thickness over making territory.

  This property is, for me, totally unique to Go and why it’s my favorite game. I could write a whole blog post on this…

• Chess

  On every move think hard about what your opponent can do to you before thinking about your own strategy.

  I would be curious what a stronger Chess player would say as it could apply to any game, but in my opinion it is especially important in Chess. I wonder if it accounts for why Chess players are often so paranoid :).

• Poker

  You have to bluff, not because it is necessarily an effective strategy on the turn you do it, but because a reputation for bluffing is critical to keep opponents from folding when you do have a strong hand.

  It took me a while to figure this one out. The lesson about letting go of sunk costs is too obvious.

• Backgammon

  When bad things happen, you must let go of your ego and objectively judge whether the outcome is the result of your own mistake or the result of bad luck. The most common example of this is when to take the doubling cube in a bad position. Correct strategy in that situation says you can be wrong three out of four times and still have a sound strategy.

  I guess this is more of a meta strategy about improving your play over time, but I’ve found it applies to my life a lot. One thing that makes backgammon so hard to learn is that the outcome is so noisy.

• Mancala/Othello

  In games without good patterns to generalize or interesting global strategy, often a really good heuristic is just to limit the number of moves your opponent can make.

  I can’t believe I’m giving away the reason I never lose these two games :). I realized this strategy while training an Othello playing AI when the weight on the number of available moves for an opponent greatly exceeded the weight on the current score. In fact, the weight on the current score was negative because it was inversely correlated with the weight on number of available moves.

• Blokus

  Your opponents territory is much more valuable than your own.

  Aggressive game players always do way better at Blokus than cautious ones. Four player Blokus has a lot of Risk/Settlers/Diplomacy strategy of convincing your opponents that you’re losing so they don’t gang up on you. I would like to read some deeper analysis of Blokus — I feel like there’s a lot of interesting strategy there.

Any comments/additions?

John Langford had a nice post on optimizing experimental code. He gives ten rules of thumb, but I think his last rule is by far the best:

Optimize while you wait. There is always a question about how much time should be spent on optimization vs. other aspects of programming. A reasonable rule of thumb is to spend time on optimization when you are waiting for the program to finish running. This is ammortization, applied to yourself.

In many cases this makes absolutely no sense, but it’s certainly true thats it’s “amortization, applied to yourself”, and it does contain a nice kernel of truth.

Lately I’ve been writing a significant amount of production code for the first time in a long time. It’s definitely satisfying in a certain way. But sometimes I feel like years of writing throw away code for experiments has permanently damaged my ability to write really efficient, understandable code in the same way that years of writing math papers and problem sets damaged my ability to write clear, understandable English.

My boss Tim made an offhand comment the other day that he wanted to make sure we weren’t trying to enumerate the rational numbers row by row. The more I think about it the more it seems like a brilliant metaphor that generalizes to a lot of things in life.

For the non-mathematicians who read this blog, a set is “countable” if you can define an order on its elements where you will reach any particular element in finite time. Good Math, Bad Math always has a few nice posts for non-mathematicians on this topic.

For example you can think of the positive rational numbers (i.e. fractions) as an infinite grid where the numerator is the x-axis and the denominator is the y-axis (there is some redundancy but let’s not worry about it). If you tried to enumerate it (1/1, 1/2, 1/3, 1/4 … ) you would never get to 2/1.

But if you do it this way you will get to all elements:

If you imagine the rows as tasks and the columns as steps in tasks the lessons are:

• If you have a finite number of things to do that all take infinite time you should work on one step for each task and then switch to the next one.
• If you have a infinite number of things to do that all take finite time you should finish each thing before you go on to the next task.
• If you have an infinite number of things that all take infinite time you should use the pattern above and you will still get to everything eventually. But if you try to start each task before doing the next step for any task, or try to finish each task before moving on to the next one you’re screwed.

I’ve been fascinated by Prosper and other peer-to-peer lending sites for a while. The way these sites works is that someone puts up a request for a loan at a certain interest rate, describes what they would do with the money, and submits their credit report. Lenders can then ask the borrower questions and decide to loan them a small amount of money, taking the risk that if they default they lose the principle. But lenders can diversify the risk by loaning money to lots of different people. These sites claim that they have higher returns than the stock market, but they haven’t been around long enough to prove it.

One intriguing and disturbing thing about them to a machine learning guy like me is that you can use factors that are illegal to use in credit models such as age, race and gender to build your own superior credit model and then use that model to decide to whom to lend your money. In this way even in a perfect credit market you could make more money than a bank.

Prosper and others claim to be doing a social good by increasing lending liquidity and thereby giving people access to better interest rates. But the interest rates are still really high. I thought about investing some of my money in this stuff a while back and decided that while I believe poor people should be allowed access to loans, lending money at 20% or higher interest is just not a business I want to get involved in.

My friend Josh who recently left the world of investment banking was telling me that there is a huge arbitrage opportunity here. Apparently his friend uses his good credit to get loans on Prosper at 9% interest using his very good credit rating and then loans out money to higher risk people at much higher interest rates. The beauty is that everybody wins. Or do they?

The Axiom of Choice says that given a collection sets we can choose an element from each set. For a finite collection of sets this seems obviously true. For infinite sets it still seems to me like it should be true, but my friend Kenny has been trying for years to convince me that it’s obviously false, at least for uncountable collections.

He pointed me to a great post about it on The Everything Seminar, which gives the example that I occasionally use to explain the anti-Axiom of Choice argument at parties (obviously, I go to some amazing parties…).

I couldn’t have explained it better than The Everything Seminar, so if you want to learn more follow the link.

For some reason I woke up this morning wondering if we met some aliens what would they think about the Axiom of Choice. Obviously true? Obviously false? Religious war? How much of the mathematical formalisms are cultural?

If you’re not interested in such philosophizing, this is a great little puzzle to think about stolen from the same post:

100 prisoners are placed in a line, facing forward so they can see everyone in front of them in line. The warden will place either a black or white hat on each prisoner’s head, and then starting from the back of the line, he will ask each prisoner what the color of his own hat is (ie, he first asks the person who can see all other prisoners). Any prisoner who is correct may go free. Every prisoner can hear everyone else’s guesses and whether or not they were right. If all the prisoners can agree on a strategy beforehand, what is the best strategy?

I had seen clips of Will Wright’s talk about Spore at the GDC, but this morning I watched the complete video. I’m pretty sure this is going to be the best game ever.

When I was a kid my dad gave me Rudy Rucker’s Artificial Life Lab which fueled a lot of my early interest in AI. I remember at the end of the book he talks about how he wants to make a game which is essentially Spore. He asks for a programmer to help him build this thing, and I remember thinking that’s what I want to do when I grow up :).

I can’t wait to play this game.

Spore reminded me of a computer game that I used to love called WATOR. It’s a really crappy simulation of an ecosystem with predators and prey represented by pixels that chase each other around until they reach some kind of equilibrium. I loved it so much I made many of my own versions of it. Since then I’ve never heard any one mention it, but of course a web search turned up someone who made a java version. The internet is an amazing place…

I wasn’t sure if it was ok to show how we parse Miss South Carolina’s statements, but since it was posted to TechCrunch , I guess I can show you our parse tree of her comments:

And since a few people have been asking, here is the Charniak parser’s parse of the last and most coherent part of her statement:

I make no strong claims about which parse (or parser) is better, and the bulk of our parser in a second step that generates an LFG parse. The big lesson is that every type of text analysis you do on the web is going to be full of noise and you need to be very robust at handling mistakes and ambiguity.

Statistical Modeling, Causal Inference, and Social Science has a nice set of graph of votes by state plotted over time. Instead of plotting the percent of votes for a given party they plot the difference between votes for a candidate and the national average. The amount of correlation inside regions is pretty interesting.