Monthly Archives: August 2014

Why are tiny systems so big?

The last five or so years has been a remarkable period in computing. About five years ago, I began to fear that computing would be increasingly pre-packaged: that laptops and tablets would totally take over the market and the ability to find computers which were well suited for programming and experimentation would more and more difficult.

But something remarkable happened that I didn’t see coming: the opposite occurred. The market for small development boards and computers exploded. At many different performance levels, and very inexpensive price points, computers for experimentation flourished and people began programming in a way that they didn’t before. We see the rise of platforms like the Arduino, the Raspberry Pi, and the Beaglebone Black at super-inexpensive price points. It is truly an awesome time for computer experimentation.

But aesthetically there is something that jars me a bit: that these small, simple systems aren’t really that small or simple. Consider the Arduino Uno: it is a small 8 bit computer with only 32K of flash memory. But the development environment for the Arduino isn’t self-hosted: you need a separate cross compiling host, and the software is dozens of megabytes in size. In the 1980s, we had systems of comparable overall power (based upon processors like the 6502 or Z80) but these machines typically self-hosted interpreters (most commonly for BASIC) that allowed development to proceed without an additional cross-compiling development system. While these systems lacked some of the power of modern development environments, they also were simpler and easier to master.

Systems like the Raspberry Pi are at least self-hosted. I really like that feature: you load up an SD card with a system like Raspbian or Ubuntu, and you have a complete Unix system. But I can’t help but wonder if this is a bit too daunting for the hobbyist without three decades of Unix experience.

I guess what I think is interesting is providing a smaller, closer to the “bare-metal” environment for embedded programming that can be self-hosted: that can run on the target hardware, with only the thinnest layers of operating system.

Okay, so that’s the idea. What options are there?

One of the most interesting things I’ve begun looking at is Fabrice Bellard’s TCC compiler. Having a C compiler built into your embedded machine may seem a bit odd, but Bellard’s compiler is relatively tiny and can generate code for either Intel or ARM. Experimenting with a few of my own programs shows it to be remarkably capable: it compiled both my toy raytracer and the dump1090 software defined radio program. The resulting code is obviously not super efficient: my raytracer runs about 1/2 speed relative to the code compiled with gcc. But it does work, and the compiler is fast and small enough to self host. Pretty interesting.

What kind of target hardware should we target? It seems like we can get a lot of leverage by targeting ARM based boards, and adopting popular, easily available platforms would make it easier for people to get started. In most respects, it’s hard not to pick the Raspberry Pi: it’s popular, it’s available, and a fair amount of information about “bare metal” programming it seems to be available. It also seems that we can use emulators like QEMU to help bootstrap and debug.

Do we need an operating system? If so, how much of one? It’s kind of an open question. I’d like to see something whose size is maybe a few thousand lines of code. Minix? Xinu? A simple real time OS/executive maybe?

Milhouse still doesn’t know the first thing about FIrst Position…

White to move and win, position analyzed by Payne in 1756 in the first English book on checkers...

White to move and win, position analyzed by Payne in 1756 in the first English book on checkers…

Until Milhouse can play this position out, it really can’t be considered a real checkers program. Right now, even with an endgame database, it’s still clueless about how to proceed.

Addendum: Reinfeld’s How to Win at Checkers gives some details on winning positions like this. I recall reading it (my puzzle database includes puzzles from this book) but I’m unsure as to how to effectively merge the knowledge into my evaluation function. Still, worth looking at.

Are improvements in computer chess due mostly to hardware or software?

file000183685005My recent revival in interest in computer chess/checkers/gameplaying was in part spawned by the impression (not particularly support by evidence at the time) that the dramatic increase in computer chess strength must have come from more than just basic hardware improvements. It seemed obvious to me that some fraction of the increase in the play was due to new cleverness and discoveries by chess programmers. But I had no real datapoints to figure out what that split might have been.

Until I found this 2010 post by Bob Hyatt. Bob has been an expert programmer in computer chess for decades, first for Cray Blitz and later for Crafty, an awesome open source Chess program. It’s source code is amazingly interesting, and has tons of features which are pretty cool.

In the forum post, Bob compared Crafty 23.4 (which was at the time the highest ranked version he had produced) with Crafty 10.18, the version which was available 15 years earlier from 1995. Running on the same hardware, you find that Crafty 23.4 was 360 ELO points higher than older version.

But how much would we expect to gain from the factor of 1000x increase in speed between 1995 and 2006? I remember reading that each doubling of CPU speed would be worth about 100 ELO points. Bob did some experiments that suggests for Crafty, that result might be something more like 80 ELO points. That means that from hardware improvements alone, you might expect to see an increase of 800 ELO points.

This would seem to imply that only 1/3 of the improvement of Crafty was due to software, with the remaining 2/3 of the improvement due to increases in hardware speed. Bob doesn’t believe the 360/800 numbers are accurate (they are likely too broad, 1995 Crafty was probably not 1100 points weaker than 2010 Crafty) but that the ratio of the two is likely to stand up.

Bob did this post to respond to this rather long thread which I find much harder to draw any real conclusions from. But it’s still good reading.

But it would seem that my intuition is likely wrong: that at least for Crafty, about 2/3 of its gains are likely to increases in hardware speed, with only 1/3 coming from software improvements. Interesting.

Pondering computer chess…

At the risk of name dropping, on my flight out to Vancouver for SIGGRAPH last week, I had the exceedingly high luck of scoring a seat next to Pat Hanrahan. 25 years ago, I was working at Princeton in the Applied Math department, and the single smartest thing I did was make Pat’s acquaintance. Besides providing countless insights into computer graphics over lunch and chats, he helped me score my current job, where I’ve been gainfully employed for the last 23 years. He claims that he occasionally even reads my blog, so if you are reading this Pat, thanks a million!

During the two hour flight, our chat ranged over a wide variety of topics. One topic that is completely unrelated to my work is my interest in computer chess and checkers, mainly as applications of game tree search. Even as an undergraduate, I was fascinated by this topic, but when Deep Blue beat Kasparov 2-1 in a six game series in 1997, I kind of pushed this to the back of my mind. I mean, I thought it was over.

I’ve made this mistake before.

What’s amazing is that computer chess programs have gotten better recently. And not just a little better, a lot better. One particularly interesting chess program is Stockfish. Firstly, it is an open source project, which means that its innards are available for your inspection. Secondly, it is available on a wide variety of platforms, including as a free application on the iPhone. I interrupt this diatribe to show the game I played against Stockfish on my return flight. I don’t play very often, but managed to eke out a shaky draw against Stockfish with it taking 10 seconds per move. I only lost concentration once and stumbled into an obvious blunder (which I shamelessly took back and went at for another try). Here’s the game, using a spiffy WordPress plugin.

[pgn width=”512″]
[Event “Airplane Chess Game”]
[Site “WestJet 1776”]
[Date “Aug 14, 2014”]
[Round “?”]
[White “Mark”]
[Black “Stockfish”]
[Result “1/2-1/2”]

1. e4 e5 2. Nf3 Nc6 3. c3 d5 4. Qa4 Bd7 5. exd5 Nd4 6. Qd1 Nxf3+ 7. Qxf3 Nf6 8.
Bc4 e4 9. Qe2 Bd6 10. O-O O-O 11. d3 exd3 12. Bxd3 Re8 13. Qc2 Nxd5 14. Bxh7+
Kh8 15. Bf5 Bb5 16. c4 Qh4 17. g3 Qxc4 18. Qxc4 Bxc4 19. Rd1 Be2 20. Rd4 Bf3
21. Rh4+ Kg8 22. Bd2 Be7 23. Ra4 Bf6 24. Nc3 Rad8 25. Rb1 Ne7 26. Be4 b5 27.
Rb4 c5 28. Rxb5 Bxc3 29. Bxf3 Bxd2 30. Rxc5 Ng6 31. Kf1 Ne5 32. Be2 Bb4 33. Rb5
Rd2 34. Rxb4 Rxe2 35. Kxe2 Nc6+ 36. Kd2 Nxb4 37. a3 Rd8+ 38. Ke2 Nc2 39. Rc1
Nd4+ 40. Ke3 g6 41. Rc5 Nf5+ 42. Ke2 Kg7 43. b4 Rd6 44. g4 Re6+ 45. Kd3 Nh4 46.
a4 Nf3 47. h3 Ng1 48. h4 Nh3 49. f3 Nf4+ 50. Kc4 Re1 51. Rc6 Ng2 52. h5 Nf4 53.
hxg6 Nxg6 54. Ra6 Rc1+ 55. Kb5 Rc7 56. Rc6 Rd7 57. Ka6 Ne5 58. Rc5 Kf6 59. Rb5
Nc6 60. Rb7 Rd4 61. Kb5 Nxb4 62. Kc5 Nc2 63. Rxa7 Rf4 64. a5 Rxf3 65. a6 Rc3+
66. Kb5 Nd4+ 67. Kb4 Rc1 68. Rb7 Nc6+ 69. Kb5 Ne7 70. a7 Rb1+ 71. Kc5 Ra1 72.
g5+ Ke6 73. Rb6+ Ke5 74. Rb7 Nc8 75. Rxf7 Nxa7 76. Kc4 Nc8 77. Kd3 Rg1 78. Rg7
Rg3+ 79. Ke2 Nd6 80. Rg8 Kf5 81. Rf8+ Ke6 82. Rg8 Ne4 83. Re8+ Kd5 84. Rd8+ Kc6
85. g6 Rxg6 86. Kd3 Nd6 87. Ra8 Rg5 88. Kd4 Rd5+ 89. Ke3 Kd7 90. Ra7+ Ke6 91.
Kf4 Rf5+ 92. Ke3 Rb5 93. Rh7 Re5+ 94. Kf3 Kd5 95. Rd7 Rh5 96. Kg4 Rh8 97. Kf4
Re8 98. Kf3 Ke5 99. Ra7 Nc4 100. Rf7 Rd8

[/pgn]

Anyway, the third thing that I thought was cool about Stockfish was that stockfish is really good. It’s clear that it would crush all human players in a match: it’s ranked about 400 points higher than Magnus Carlsen, which means that Stockfish 5 would be expected to score about 90% against Carlsen. I didn’t think that this increase in the state of the art could have been done purely as the result of CPU speed improvements, so I wanted to look into it a bit and see what might have helped Stockfish get so good.

Interestingly, I think one of the greatest causes is from exhaustive testing. The Stockfish project has implemented a distributed testing facility called Fishhtest. The idea is pretty simple: volunteers contribute cpu time to exhaustive test commits to the source tree to see the effect on gameplay You can read more about it here.. According to the Wikipedia article on Stockfish, this allowed Stockfish to gain 120 ELO points in just 12 months.

Anyway, my chats with Pat and pondering some of the ideas from Stockfish make me want to dust off my Milhouse checkers program, and see if I can’t borrow some ideas from Stockfish as well as other ideas from Pat (implementing checkers on an FPGA?). We’ll see what happens.

My Atari 2600 Pong Clock

While looking for something completely different, I ran across the code and binary images for my old Atari 2600 “Pong Clock”. I realized that my previous post on the matter didn’t have pictures of my final version, so just for fun, here are a couple of Stella screengrabs (in NTSC “TV” mode, for enhanced realism).

I included a tiny intro screen. I showed this at a 2010 get together. The Conway glider at the top is animated:

simple.bin_6

It plays a game of pong against itself, with the score representing the current time. You can set the time using the left joystick. When the minutes tick change, the right player wins. When the hours change, the left player does.

simple.bin_7

It also works on black and white tvs. I never did the changes necessary to make it play in PAL mode, although it should be pretty straightforward. The Atari 2600 was practically built for implementing Pong.

Still, it’s got some finesse in it. I never could have done it without all the hints from the Atari Age forums and the Stella 2600 emulator. My source code references a nice little bit of code from an Atari Age tutorial series, which I shamelessly purloined. I left a comment saying:

;;; According to the documentation, A isn’t really the position (0-160),
;;; you have to add +7 to the position. But I find that the offset in
;;; stella is +5. I haven’t done the cycle counting to figure it out,
;;; but I’ve had good luck trusting stella, so that’s what I’m going
;;; with.

Perhaps I’ll revisit that sometime and figure out what was right.

Two more “primitive” cameras…

My previous experiments with a foam core 4×5 camera has whetted my appetite for more camera experiments. In particular, I was looking for cameras that could be built quickly, and where amateurs could construct their own lenses out of surplus optics. I am particularly interested in cameras that use the old fashioned meniscus landscape lens design, which takes just a single meniscus lens, and symmetric lens designs like the Steinheil Periskop. Most DIY camera projects seem to fall back to using modern or antique lenses, but I did come across two cameras from the same maker that took a more basic approach.

This large format camera is basically a pinhole camera, but with a stop right at the lens, yielding a focal ratio of about 90. Check out the flickr set, which includes both pictures of the camera and taken through the camera. This camera doesn’t include a focus mechanism, but since it is operating around f/90, it already has a great deal of depth of focus. It straddles the line between a pinhole and a conventional camera. But still, it creates some cool images.

The same maker created another awesome camera, but this one is a lot more awesome. The frame is wood, it has a focusing bellows, and takes a 4×5 film holder. The Flickr set for this camera shows some really awesome portraits, and one can tell it’s a lot more versatile and fun to use. Awesome, inspiring stuff.