Probably Dance

Shenzhen I/O is a brilliant game. In case you haven’t heard of it, it’s a game about programming micro-controllers. It distills programming down to the fun parts, removing the inertia, self-inflicted complexity, overhead, uncertainty and drag of real programming. It’s just about coming up with clever tiny algorithms and micro-optimizing the heck out of them. It’s great alone, but it’s even better if you have a friend that’s playing at the same time. Competing on the leaderboards for puzzles is enormous fun. From playing that game, here are a couple lessons:

1. There is no optimal code. There is only code that’s faster than the code that you’re comparing to

Shenzhen I/O shows you a histogram of all the scores that other people have reached. If my solution would fall on the right of the bell curve, I would optimize it until I was on the left. After a lot of work I would usually arrive at an “optimal” solution that puts me in the best bracket on the histogram. Those solutions were always far from optimal.

When you’re competing with another player, they will probably find a way to beat your score by just a few points. Let’s say my score is 340 and a friend beats me with a score of 335. (lower is better. The score is just the number of executed instructions) What follows is a bunch of head-scratching about how you could possibly get any more cycles out of the algorithm. After an hour of staring and trying different things you find a small improvement, and your new score is 332! Proudly you tell your friend that you beat their score. Soon after your friend will beat your score with 320. Such a big jump seems impossible. But your friend somehow did it. So now you need to think outside of the box. You’re thinking the only way that you could possibly achieve such a big jump is if you could somehow combine these two different parts of the algorithm, so that they can share this one part of the work. It doesn’t seem possible, and it’s not even clear that this will buy this much of a score improvement, but it’s the only thing you can think of. So after another hour of head-scratching about how you could possible achieve this you find a way to do it, and lo and behold it the wins are far bigger than expected, the new score is 310! And the next day your friend comes back with 290…

My friend and I have literally had cases where we went from a score of more than 500, where my friend thought that my score was impossible, down to a score of 202 for me, and 200 for my friend which put us completely off the charts. At that point a new patch hit that changed the level slightly so that our solutions didn’t work any more. (the game is still in early access)  But if it hadn’t been for that, I wouldn’t have been surprised if we could have optimized this further. Almost every single time that I thought the limit was reached, we broke through it soon after.

I can now say for a fact that a lot of code out there is far from optimal. Even the code in our standard libraries that’s maintained by some of the best programmers and that’s used by millions is slower than it needs to be. It is simply faster than whatever code they compared it against.

2. You can’t think of a solution until you know it’s possible

On the second puzzle in the game, which serves as a kind of tutorial, the only possible score is 240. Except there were some people over on the left of the histogram. And wondering how to get over there, my friend somehow got to 180, telling me “I think this one is optimal.” The score seemed unreachable. With a few tricks I got it down to 232. After literally days of thinking about this problem I managed to think outside the box and match my friend’s score of 180. It wasn’t until we talked about it that we realized that we had used different solutions. It was crazy to realize that there were in fact two entirely different ways to reach 180. Once I realized that I had used a different solution, I also realized that the solution that my friend picked could not be optimized further, but mine could. It took me hours, but I got the score down to 156, and then very quickly down to 149. My friend then beat me with 148 using my technique, forcing me to find one last cycle.

If nobody had gotten to the score of 180 before me, I couldn’t have thought of any faster way of solving this puzzle. Without that piece of information, the brain just comes up with reasons why the score is already optimal. Only once you know for a fact that a better solution is possible can you actually think of that solution. If you now say “but how did the first person get to a lower score?” then the answer is that the technique that my friend used is actually useful in other levels, so they could have gotten the trick from one of those and then just applied it in earlier levels once they had come up with it in a later level. Or maybe somebody got to the score of 232 which is just the 240 score with a few dirty tricks, and somebody else thought about how to get to the “impossible” score of 232, and accidentally got to 180 instead.

Or Michael Abrash has told the story of how he was optimizing an inner loop, and he was asking a friend for help. The friend stayed long in the office and at night left a message for Abrash telling him that he had gotten two more instructions out of the seemingly optimal inner loop. Abrash didn’t think that was possible, but before the friend came into work the next day Abrash had already found how to reduce the loop by one instruction. At that point the friend told Abrash that the friend had actually made a mistake, and the two cycle optimization wasn’t valid. But just the thought that the friend could have gotten two more instructions out of the loop made it possible for Abrash to find another optimization.

3. You can’t get to the good solution right away

In the puzzle above where my friend and I brought our score down from more than 500 to 200, the final solution was actually much cleaner than the solution that has a score of 500. Well my final 202 score solution is a dirty mess, but somewhere around 220 I had just the most beautiful code. It was much cleaner than the code I had for a score of 270, which in turn was much cleaner than the code I had for 340, which in turn was cleaner than the code I had for 410. But even though the fast solution is much simpler and cleaner than the bloated, slow solution, you have to write the bloated, slow solution first. It is a necessary step in getting familiar with the problem. Only once you’re familiar with it can you recognize the points where it could be cleaner. The only way to get to the good solution is to perform many steps of filing off the bumps and cleaning up the dust.

Even big, algorithmic improvements come from writing the bad solution first and then making many small improvements. At some points the small improvements clarify something in the solution. They reveal a symmetry or uncover that some work was done twice. Sometimes a new fact reveals itself very hazily, and only more work and thought on the problem can slowly make it clearer. Sometimes you don’t realize that you just made a big, algorithmic improvement until after you’re done. “Oh I can delete this entire chunk of code now. How did that happen?” And then after the fact you can reason through the steps that took you there.

For all of this you have to keep working on the problem and you have to keep it in your head. (partly so that it’s in the back of your head when you’re sleeping or taking a shower) You can’t come up with improvements if you’re not actively working on the problem.

4. Tests can drastically improve iteration times

This is obvious for people who have worked with tests, but in the videogame industry where I work, unit tests are still rare. In Shenzhen I/O you are so ridiculously productive thanks to the automated tests, that I point out to everyone who has played it “you could be this productive at work if you just wrote tests.”

Tests allow you to have a feedback loop of seconds. Manual testing requires launching the game, teleporting to the point you want to test something, waiting for loading, then manually doing your test. (say by killing a goblin and checking that the right effects play when the goblin dies) Not only does the automated test drastically improve iteration times, it will probably test more cases and provide more helpful error messages when something goes wrong.

5. Iteration times are about more than just productivity

I think the fast iteration times in Shenzhen I/O are one of the main reasons for why it is so much more fun than normal programming. Fast feedback and fast iteration times just make programming better. Suddenly I want to go back to old code to see if I can improve it, because if I get a few more cycles out of it I can find out very quickly. How long does it take you to set up a test case at work that measures performance and measures improvements? How long does it take you to make sure that your optimization didn’t break anything? Does that keep you from trying more risky optimizations?

Slow iteration times make you work differently. Not only do they drag the fun out of programming, but they make you spend less time on improvements. They hurt your code quality. It’s worth spending time on improving iteration times even if you did the math and figured that people didn’t spend a lot of time compiling. It’s not just about time spent.

6. Competition can really improve code

If our libraries were set up like Shenzhen I/O puzzles, all of our code would run much faster. The way this could work is that the standard library would define an interface, tests, and a simple implementation. Then anyone could submit better implementations. And you could judge how fast each solution completes each test. You pick the test cases that you care about and pick the implementation that does best in those.

People could provide several different implementations that do better in different scenarios. (“this one does better if your data grows and shrinks a lot, this one does better if it’s mostly stable”) All you have to do is make sure that your implementation satisfies certain tests.

I think if we had this we would quickly find a new, faster sorting algorithm. The current favorites seem to be Introsort and Timsort, but I am confident that they would be beat immediately. The reason is simply that nobody has worked on sorting algorithms in an environment like the one in Shenzhen I/O.

7. A good story can enhance any game

Shenzhen I/O has impressively good writing, and it really enhances the game. The story is that you’re a programmer who moves to China for a job. It’s a simple story, entirely told in email conversations with your in-game coworkers, but the small story snippets really lighten up the game. Your coworkers have personalities that seem well-researched, almost as if the author has experience with working abroad himself. Each puzzle also has a little back story. I find that I use the back story to determine whether my solution is “cheating” or not. You can “cheat” by adapting your solution to the test cases, so that only those pass and other tests cases might fail. Usually if the device still fulfills its purpose according to the back story, I’m fine with taking a shortcut. (e.g. it’s fine to err on the side of false positives for the “spoiler-blocking headphones”, but not for the security card reader. For that puzzle however false negatives based on timing are OK because people can just swipe the card again)

The emails contain funny moments between coworkers, informative emails where you learn something about China, and emails that mirror your own emotions: When you get access to a new part that will make puzzles easier your coworkers are ecstatic and so are you. Or you are confused early in the game because you have to learn a lot, and the game acknowledges and plays with your confusion by making part of the documentation Chinese. This actually helps because it makes clear that you don’t have to learn everything to get started, and it’s OK to be a bit confused. It’s very impressive how all of this is told in very short email conversations that take maybe a minute or two between puzzles.

If this was just a series of programming puzzles, it wouldn’t work nearly as well. Before playing this game I wouldn’t have thought that programming puzzles need a story. The game would work without a story, it just wouldn’t be as good.

Conclusion

You should play Shenzhen I/O. It takes all the fun parts of programming and distills them into a game. If you can, convince a friend and start roughly at the same time.

The game teaches persistence and how to improve a solution with any means necessary. The game teaches out of the box thinking. When you have a tiny, constrained problem and somehow people are much faster than you, you have to think outside the box. (or sometimes you think outside the box for an hour only to realize that there was an obvious improvement left to do inside the box)

The game shows a great way to program, making you incredibly productive which will make your work feel sluggish in comparison. It’ll make you want to improve your tools at work.

Many of these lessons aren’t new, but since Shenzhen I/O is such a condensed experience, it makes these lessons clear and easy to acquire. It’s a great way to spend time as a programmer.