Sylvain Zimmer
Hacker, Entrepreneur & Conference Organiser

Archive for Tech stuff

Adding support for the SpaceNavigator into Sketchfab

SpaceNavigator

After trying Liquid Galaxy a couple times at Google offices, I became interested in the controller they use: the 3DConnexion SpaceNavigator. It’s a great device to explore 3D environments and it is surprisingly easy to master!

So I bought one and started hacking support for it in my first angel investment: Sketchfab. My goal was to use the Gamepad API to be able to move around 3D models hosted on Sketchfab with the SpaceNavigator, directly inside the browser!

I quickly discovered that the support for gamepads was not actually merged yet into Firefox. All I could use was very old builds with deprecated APIs. So I shifted my focus to Chromium and it turned out that the Gamepad API was already activated for everybody and that the SpaceNavigator was supported out of the box. Still, after digging in the code I ended up sending my first patch to Chromium to support another USB gamepad ;-)

One interesting implementation detail of the Gamepad API is that users first need to push a button on the device before it becomes discoverable by the webpage, mostly to prevent webpages from uniquely identifying users based on the devices they connected. But it makes it really hard to display some kind of help text like “Push a button to activate your gamepad” because you don’t even know it is connected. There should be a “there is *something* connected” event!

With the SpaceNavigator sending DOM events inside Chromium, the next step was to bind them to the 3D viewer. Sketchfab uses an open source 3D library called OSGJS under the hood so I submitted a patch to add Gamepad support. It actually made me quite proud to be both an investor and a committer ;-)

Anyway, here is a live demo of browsing Sketchfab using the SpaceNavigator. You can try it for yourself with Chrome and any gamepad!

YouTube Preview Image

Optimizing the ISS solar arrays, a Python solution to the NASA Longeron Challenge

Two weeks ago, while waiting for my flight to San Francisco at an airport in Paris I stumbled on a coding challenge by NASA to optimize the solar arrays of the International Space Station. I’ll let the video explain:

YouTube Preview Image

Being very interested in Optimization for my soon-to-be-unveiled new startup, I was quite excited and promptly downloaded all the required material to spend my 10-hour flight hacking ;-)

The rules forbid talking about code while the contest is running but since it just finished, I would like to share how I built my solution with tools like OpenOpt, EC2 Spot Instances and MongoDB.

Disclaimer: Shortly after landing I was the top Python solution and 10th overall but I couldn’t spend enough time on my code while abroad to stay that high in the charts. Final rankings are due this Friday so this is not a post describing the optimal solution but I hope it will be somewhat entertaining for Python coders and others. 

The contest

TopCoder made a Java simulator available along with the detailed description of the problem. The space station has 10 joints that can be rotated so all your program had to do was to output 10 angles and speeds for each of the 92 minutes of the ISS orbit, which would be visualized like this in the local tester:

The goal of the contest was to maximize the total power output of the station over the whole orbit (In the screenshot above I’m at 163kW on the 69th minute of the orbit) while respecting a couple of hard limits like the maximum speed & acceleration of each rotary joint, minimum power output for each panel and shadowed ratios on some parts like the longerons to avoid breaking due to heat expansion.

So the whole contest was basically about minimizing the shadows cast by the front solar arrays and the station itself.

My solution

TopCoder made the 3D model of the station available so theoretically (and that may be what the winner does) you could build an exact mathematical model of all the shadows and minimize that. However this was completely out of scope for my 10 hour flight so instead I decided to use a mixed approach based on both mathematical modelling and numerical optimization. The plan was to do most of the maths offline in the plane and then run a couple VMs over the following week that would optimize the parameters of my simplified model without oversight.

Pointing to the sun

Panels pointing to the sun

The first task was to align the panels at all time to the normal vector of the sun. That was made easy by the simulator that showed the viewpoint from the sun on the right. The hardest part there was to remember (or rediscover) all the formulas for cartesian/spherical conversions ;-)

One early optimization was to deviate from that sun angle so that the backpanels (in red) would have minimal shadowing. That was by far the most important gain and I built an almost-exact model of the sun angles on these panels to find the optimum (check nabuk’s schema).

Minimizing the station shadows

Worst position for station shadows

In order to point to the sun at all times, the panels have to do one full rotation per orbit (check the video at the end of this post). Which means that 2 times per orbit, a large part of the back panels will be heavily shadowed by the station. You can see on the right a screenshot at minute 82, one of the worst times of the orbit.

So the second biggest but perhaps most difficult gain was to accelerate the rotation of the panels when they were passing behind the station in order to minimize these bad angles.

There were 2 constraints: the hard limits on joint speed and acceleration, and the fact that any deviation from the “optimal” sun-pointing angle was reducing the potential power of the panels.

There was definitely a middle ground to be found between potential power and shadowing but given the complex shape of the station I wasn’t going to find it by an exact formula in a few days, let alone hours.

So I decided to approximate that function associating each angle with the optimal amount of deviation by numerical means, namely Global Optimization.

Enter OpenOpt

Python is one of my languages of choice not only because I love its syntax but because it has a mature ecosystem. Among the many availables modules are powerful scientific libraries like SciPy and OpenOpt.

OpenOpt is a suite of tools and optimization algorithms for solving both Linear and Nonlinear problems, supporting a large number of solver backends and (sometimes confusing) interfaces. There may have been better frameworks for my problem but I downloaded it in a rush just before my flight was departing as it seemed the most comprehensive and experimentation-friendly with its multiple algorithms.

Some optimization problems can make use of Vectorization, meaning that OpenOpt can build an internal model of their result function in order to speed up the process and make some assertions on the optimal result. However that is not the case for this problem: I had to consider the local ISS simulator as a black box that had about 92*20 input variables and one result, the total power output (which was the challenge score before maluses).

OpenOpt has several algorithms available for Global Optimization that can converge towards the best solution when there are many variables and multiple local optima. After some tinkering I settled on Differential Evolution (DE), a kind of genetic algorithm that was bundled in OpenOpt.

Parallelization

The biggest issue for this kind of numerical optimization was that the downloadable Java tester was very slow. Supposedly because it had to calculate all the exact shadows it took about 10 seconds to run on my MacBook Pro. Moreover, the contest specified 6 different beta angles which meant about 1 minute was required to evaluate the performance of one set of input values.

1 minute is an extremely high amount of time for algorithms like DE that require a large population of input candidates to be tested at each step of the evolution process. I guessed I would need about 6 (beta angles) * 50 (evolution steps) * 100 (population size) * 10 (different input sets) evaluations to have a good enough solution, which meant 35 days of my CPU time.

That was obviously not going to be possible so after landing I decided to launch about 50 EC2 spot instances where I could run DE in parallel, have them send the results to a free MongoHQ database and just merge them together before submitting my solution. Parallelization was made easier by the fact that there was several independent variables like the beta angle that could just be split among instances.

Spot Instances are great because they are often 10 times cheaper than regular ones. Their downside is that they can be terminated at any time by Amazon if their market price exceeds your initial bid but that wasn’t going to be an issue for this kind of computation. My final bill was about $50.

I want to pause there for a second and pay my respects to the AWS team that makes this possible. When you think about it, bidding for CPU time from your command line is insanely cool ;-) And when it’s for optimizing the space station, I guess that’s geek heaven.

Anyway, my biggest issue with Spot Instances was their launch time. You have to submit a bid that is evaluated for some time before AWS decides to allocate you the actual instances. That delay was at times as high as 10-15 minutes. I also ran into a known bug where the quota of spot instances wasn’t freed after them being terminated.

Putting it all together

There were a couple other numerical parameters (like station yaw) and approximations I optimized for in my solution but they yielded limited gains compared to the above.

This is a video of my solution for beta=75:

YouTube Preview Image

That’s it! I really enjoyed this challenge. The TopCoder rules were a bit weird at times but kudos to them and NASA for getting people involved and sharing some of their daily challenges. However I’m quite sure NASA has a whole team dedicated to this kind of optimizations and no significant improvement over their own solution will be made here, unlike the Netflix Prize.

I’m also sure I won’t be #1 but regardless, it was by far the coolest time I ever had on a plane ;-)

The third day Flash died?

My previous post about the ongoing death of Flash got a lot of support but also a few sceptics, which were obviously expected.

The halt of mobile browser Flash development by Adobe today is another milestone that directly confirms my two main points:

  1. The number of valid use cases for Flash is shrinking fast. There are still some ones that make sense, don’t get me wrong, but they’ll get more and more specific as time goes by.
  2. Adobe continues to demonstrate major courage and open-mindedness. I’m betting they’ll have one of the best HTML5 creative tools in a few years.

Chess@home: Building the largest Chess AI ever

Update: We’ve won Node Knockout in the “Completeness” category ! Congrats to the team!

How we got there

SETI@home
Many people are familiar with the SETI@home project: a very large scale effort to search for patterns from alien civilizations in the ocean of data we receive from the sky, using the computing power of millions of computers around the globe (“the grid”).

SETI@home has been a success, obviously not in finding aliens, but in demonstrating the potential of large-scale distributed computing. Projects like BOINC have been expanding this effort to other fields like biology, medicine and physics.

Last weekend, a team at Joshfire (Thomas, Nathan, Mickael and myself) participated in a 48-hour coding contest called Node Knockout. Rules were simple: code the most amazing thing you can in the weekend, as long as it uses server-side JavaScript.

JavaScript is an old but exciting technology, currently undergoing a major revival through performance breakthroughs, server-side engines, and an array of new possibilities offered by HTML5. It is also the language that has the biggest scale. Any computer connected to the web can run your JavaScript code extremely easily, just by typing an URL in a browser or running a script in a command line.

We decided to exploit this scale, together with Node’s high I/O performance, to build a large-scale distributed computing project that people could join just by visiting a web page. Searching for aliens was quickly eliminated as we didn’t have our own antenna array available at the time. So we went with a somewhat easier problem: Chess.

None of us is a particularly skilled Chess player. But as we discovered that there was an entry in the Guinness World Records for largest networked Chess AI at 2070 nodes, we realized it was definitely something we could beat. The Chess@home project was born!

48 hours later, the prototype still had a few bugs but was in a very playable state and looked like this:

Challenges of a distributed Chess AI

As we started doing research, we identified several challenging areas:

Latency. We wanted to follow standard tournament rules (~90min games) which meant each move should be computed in about a minute on average. Moreover, players on the web would prefer even shorter response times so we had to aim as low as we could.

This short compute window wouldn’t play well with most existing distributed computing infrastructures which typically optimize for throughput. We had to come up with a new, almost real-time infrastructure. Websockets would definitely be a part of the solution.

Parallelism. Optimizing for latency means sending smaller amounts of computation to each worker. So we had to find a simple way to divide the computation for each move into thousand of smaller pieces.

Without going too deeply in the specifics, the minimax algorithm used in most Chess AI relies on a tree walk which is inherently sequential when you want to do alpha-beta pruning. We researched various algorithms that would be suited to parallelism keeping the following in mind:

  • The workers shouldn’t rely too much on shared variables because websockets don’t work from client to client (going through a server wouldn’t scale).
  • The work for each move should be divisible in thousands of smaller units.

We found two potential matches : APHID (simple, used in ChessBrain.net, current holder of the Guinness Record) and variants of YBWC (more complex but more efficient). Given the 48h coding limit, we chose to go with APHID for the time being.

JavaScript performance. State-of-the-art Chess AIs are able to scan more than 15 million nodes per second (NPS) on today’s high-end hardware. GarboChess, the open source JavaScript Chess AI we forked, had performances around 100k NPS under Chrome with a modern Macbook Pro. This 150x factor didn’t surprise us that much and in our 48 hours we decided not to invest time into profiling and optimizing this code which was already capable of beating us on only one machine anyway ;-)

For reference, it is said it took 200mm NPS for Deep Blue to beat Kasparov, which would be theoretically achieved in our 2070-node goal.

Fault tolerance / Security. Running JavaScript code on third-party clients means they can’t be trusted, both for availability (the users can leave the page at any time) and for reliability (malicious clients could send wrong scores and make the AI play dumb moves).

Reliability was ruled out-of-scope in the initial run but availability seemed important if we wanted the algorithm to finish on time without missing obvious paths in the decision tree. We settled on a FIFO queue for the work units stored in a MongoDB server. We set a timeout of 5 seconds on each work unit so that a second worker could grab the unit and recompute it if the first worker didn’t send anything back.

Our 48h prototype implementation

Here is an overview of the prototype design:

Let’s focus on some key components:

  • dnode. A Node.js library for asynchronous bidirectional remote method invocation. It provides network socket and websocket-style transports (via socket.io) so that system processes can communicate with each other and with processes running in browsers using the same interface. We used it for nearly all network interactions.
  • Web Workers. JavaScript is a single-threaded environment, meaning multiple scripts cannot run at the same time without risking a UI freeze. Web Workers allow us to fire up long-running scripts to handle computationally intensive tasks, but without blocking the UI or other scripts to handle user interactions. On the server-side we used node-webworker (a Web Workers implementation for Node) so that we had only one interface to talk with the AI.
  • MongoDB. MongoHQ was a sponsor of Node Knockout and we decided to use their turn-key MongoDB instances for storing game states and the potentially huge position cache.
  • Node. Central to the architecture, Node allows both fast development (sharing the same code on client and server) and high performance (its non-blocking I/O paradigm has been proved to provide excellent concurrency and throughput).
  • Local AI on master. This will probably not scale but we still make a few calls to the AI on the server, mainly because APHID needs to generate a small tree first to divide the work between the clients. It may be removed in the future.

Future improvements will be made on this implementation, remember that it was all done in 48 hours. But launching the AI inside Web Workers, both in browsers and servers will remain the basic design idea.

What lies ahead

Widget ethics. Using third-party processing power has usually been opt-in: people needed to install SETI@home or the BOINC software to lend their CPUs. JavaScript allows us to use people’s CPUs without their explicit consent just when they visit a page with the widget, which makes this a grey area.

We decided to allow people to opt-out with a checkbox but widget adoption on third-party websites remains a major challenge towards the 2070-node goal and we will do our best to answer any complaints or objections people might have.

For instance, as we use “public” resources, we definitely want to keep the result as open as we can. The code will remain open source on GitHub (code release this week). We might also open an API to the Chess AI.

AI improvements. After smashing the few remaining UI bugs, we’ll continue optimizing the AI in several areas:

  • Better parallelism: We plan to switch from APHID to YBWC to have a more elastic work split between workers. This is critical given the low performance of JavaScript: we must compensate it by very efficient scaling.
  • Unit tests: We’ve already unit-tested a couple hundred positions but there are a lot more datasets available on the web that we should integrate like STS.
  • Algorithmic improvements: GarboChess already implemented alpha/beta pruning, null-window searches, quiescence search, and a few other features but fine-tuning the evaluation function and adding more tweaks to the AI should make it play better in more situations.

Planning for D-Day. When the AI is strong enough, we’ll invite an actual french Chess Grand Master along with a Guinness official for the most epic Chess game, ever!

We need to coordinate for the maximum of people to join the compute grid at the same time. Installing the widget on a few high-traffic websites could do the trick. We also want people to be able to watch the game on the Chess@home page so that they also join the grid.

If you have other ideas on how to get the maximum number of people connected, please share them! We’re also looking for talented JavaScript developers to help in all the fields described above.

If you want to help you can also have a look at the current list of issues and try to find new ones on Chess@home. Good luck beating the Grid!

First to decode the Chrome OS video equation!! (+ won a Cr-48 ;-)

How crazy is this !! ;-)

By now if you’re as RSS-addicted as me you’ve probably seen the excellent “How to remain calm” Chrome OS video. Like the previous potato-powered Chrome ad, excellent job from the marketing guys at Google!

However this time with my fellow geeks at Jamendo we noticed an equation hidden at 2:23 in the video. We then proceeded to lose several hours of productivity running it through Wolfram Alpha…

The Chrome Equation

All we got was X = 900.91/191605050401140404051920181525 ~= 4.7*10^-27 and we were not even sure of this one number because of barely readable numbers in the original video. At this point we were quite sure that there was something to find (and hopefully to win) but still had to find a way to give a meaning to this number.

The first path we explored was in Physics, 1.66*10^-27 being the atomic mass constant u. Having X=2.83u didn’t make much sense: too far from 2.0x or 3.0x where the closest elements I knew are. Then my friend Joachim Rambeau tipped me off with an idea on “Chrome UX” being the name of the team that released the video. There was an X in there! With the equation X=(U/Chrome), U being the mass of Uranium (~238u depending on isotopes) and “Chrome” the mass of Cr-48 or related isotopes, we found ourselves very close to the 4.7 ballpark. I posted this as a comment in the video, without much hope of it being the definite answer.

So we left this for a few hours and got back to work. Funny coincidence? The current work at Jamendo is actually building a Jamendo Pro player on cheap Android tablets ;-) So we didn’t quite leave the Google world…

Anyway, while having drinks at the office at the end of the day (Yes, Jamendo is almost as cool to work at as Google) , we realized “900.91″ did actually reference the goo.gl url shortener. The division obviously meant a slash in an URL, and then we had to make sense of the 191605050401140404051920181525 to find an URL. But the excitation was growing, we knew we were on the right path this time!

Unfortunately, at this point I had to leave and go catch a TGV back to Paris. I’m actually still on the TGV as I’m writing this, thanks to Android tethering ;-) Anyway, I tried to convert the 30 numbers into 4 characters, like all goo.gl URLs. Didn’t have much luck, I was trying to prepend “00″ at the beginning to have 32 characters, but couldn’t make sense of the resulting sequence “00191605 05040114 04040519 20181525″.

That was when I noticed there were far too many zeroes in that sequence, even without the ones I added… So I tried different splits, and ended up with “19 16 05 05 04 01 14 04 04 05 19 20 18 15 25″.

There, any geek would have known what to do! I translated it to letters and got “s p e e d a n d d e s t r o y”. Obviously, at this point my fingers were very shaky! But I managed to type goo.gl/speedanddestroy in my browser and got to a form telling me that I was the “first to figure out our MENSA-certified puzzle” and would receive a Cr-48. WIN ! ;-)

Here is a screenshot of that page:

I think I was indeed the first because now the goo.gl link just says “The form you are trying to access has either expired or reached its maximum registration limit.”. Well, that’s pretty cool if you ask me ;-) (Funny details, while submitting the form, I crossed the Luxembourg/France border, the tethering went off and I started sweating they were going to check the IP address but I was still able to submit the form from France)

Big credits must go to the to the tech team at Jamendo: our genius lead developer Vincent who showed us the video first, our incredible Android hacker Mauro who helped me a lot with the actual equation, my fellow Jamendo Co-Founder Laurent and my own personal Physics expert Joachim Rambeau.

Anyway, congrats to Google for being such nerds. The video itself is really funny, embedding an easter egg is even cooler, and, well, most people I know including myself couldn’t go back to anything else than Chromium/V8 anymore.

I’m obviously quite happy to have won the Cr-48 notebook, I also hope Google may start giving a little more attention to Jamendo! If you pardon the plug, we’re the biggest Creative Commons music repository, and we’ve never succeeded inking a deal with YouTube about these hundred of thousands of CC music tracks (be it AudioSwap integration, proper CC attribution, revenue sharing, …). Let’s hope that will happen in the future!

PS: Hey Google, could we also have one of the destroyed notebooks to include in our gallery ? ;-)

PS2: The form says that I should live in the U.S. to receive the notebook but sorry that’s not the case obviously! I left the address of a U.S. relative but I can’t imagine it being a real issue just for one laptop. I’ll keep everybody updated as I get contacted by Google.

First post from my iphone ;)

I’m testing the new wordpress iPhone app, and it rocks! The UI is neat while still exposing a lot of features so congrats to the wp devs!

How to install MySQLdb on Leopard with MAMP

Like many others, I struggled for a good hour to install the recommended MySQL module for Python, which is MySQLdb. So I’m sharing here the solution I found ;-)

The latest MAMP (1.7.1) uses MySQL 5.0.41, and MacOS X Leopard (10.5) uses Python 2.5.1 . As I couldn’t find a prebuilt MySQLdb binary for those versions, well, I had to compile my own.

So let’s go for it :


$ tar zxvf mysql-5.0.41.tar.gz
$ cd mysql-5.0.41
$ ./configure && make
$ sudo make install
$ cd ..

(now MySQL is installed in /usr/local/)

$ tar zxvf MySQLdb...
$ cd MySQLdb...

  • In the MySQLdb folder, edit the file _mysql.c
    • Delete the following lines :

      #ifndef uint
      #define uint unsigned int
      #endif

    • Replace 2 occurences of “uint” by “unsigned int”
  • Then edit the site.cfg file, and set the mysql_config variable to “/usr/local/bin/mysql_config”


(Still in the MySQLdb folder)

$ python setup.py clean
$ python setup.py build
$ sudo python setup.py install
$ sudo rm /tmp/mysql.sock
$ sudo ln -s /Applications/MAMP/tmp/mysql/mysql.sock /tmp/mysql.sock

And that’s it! You should now be able to “import MySQLdb” in python. Good luck!

Secure IM for the Real Guys…

jscrypt: the best (well… at least the geekiest) way to chat with your buddies about your top-secret projects you don’t want Gmail or Facebook to know about ;-)