Sunday, July 19, 2009

Shed Skin 0.2

I have just released version 0.2 of Shed Skin, an experimental (restricted) Python-to-C++ compiler. It comes with 7 new example programs (for a total of 40 example programs, at over 12,000 lines) and several important improvements/bug fixes. See here for the full changelog.

The new example programs consist of Disco, an elegant go player (see my previous blog post), a larger Voronoi implementation at 800 lines, a TSP algorithm simulating ant colonies, a nicer neural network algorithm and three compressors (Lempel-Ziv, huffman block, and arithmetic).

Other than bug fixes for these programs, this release adds some important optimizations. First and foremost, inlining was greatly improved, resulting in potential speedups across the board. Second, loops such as 'for a, b in enumerate/zip(sequence[, sequence])' should now be dramatically faster (also inside list comprehensions), by avoiding allocation of intermediate tuples. Finally, basic list slicing should now be much faster.

Thursday, July 09, 2009

Disco: an elegant Python Go player

There's this shiny new technique to implement computer Go players, called Monte Carlo UCT. It shocked the Go world by powering the first computer player (Mogo) to beat (quite unexpectedly I think) a professional player in an official match (with only a 7 stone handicap). Ever since hearing about this rather simple new technique, my hands have been itching to implement it in Python and compile the result with Shedskin.

The name of the resulting Go player is Disco (think "staying alive"), and its source code of only 350 lines can be found here. Given enough time, it can play some pretty interesting games on a 9x9 board. And of course you can connect it to a graphical Go board, although I only tested it with Gogui. See the README for installation and configuration details.

It has become quite a nice test case/example for Shedskin. Not only does it become about 5 times faster on my computer after compilation, and shows that you can write a pretty fast Go engine using it, it also shows how easy it is to generate an extension module with Shedskin and effectively use this in a larger program. In this case, there is a Parallel Python wrapper that fires up an abitrary number of processes, each importing and using the extension module to do part of the thinking.

Sometimes everything can come so beautifully together: an elegant Python program of only 350 lines, compiled to an extension module, imported in multiple Python processes, connected to a graphical Go board and playing according to some brilliant but simple new mathematical formula that can somehow make computers play Go! Now if only I would be better at Go myself, so I could really test it..

BTW, Shedskin 0.1.2 should be right around the corner. Obviously I got a bit distracted by the above.. In all, it contains many optimizations and bug fixes and adds 5 other new example programs.