I’m a programmer. I write games. Games programmers get a lot of respect, but none of them, not me, not Carmak, and not Abrash. None of them deserve the honour which I want to bestow on David Horne. This is because David Horne wrote the greatest program ever written: 1k chess on the ZX81.
David Horne is not an urban myth.
David Horne achieved what many would even now consider impossible. He wrote a chess game, with AI, that ran on a poorly documented, buggy machine that contained only 1k of memory.
Sometimes I feel like these kinds of programmers are a dying breed.
The programmers live on. They just don’t work their magic on what most of us consider computers these days. Real magic is still happening on more limited hardware like micro-controllers (like Arduino) and SBC’s like the Raspberry Pi.
…or specialty portable devices like the OpenPandora.
http://openpandora.org/
The amount of stuff I can do on the old 600MHz version of that thing is all down to them having some skilled, dedicated people in the community. For example:
1. Among other things, notaz has written a specialized SDL port which offloads as much as possible to the GPU’s hardware scaler/overlay support.
2. Again, among other things, lunixbochs has reimplemented most of the fixed-function OpenGL API on top of OpenGL ES under the name glshim.
3. Various NEON assembly wizards have put their effort into optimized versions of emulators for platforms like the PlayStation and Nintendo 64.
4. Relying on #1 and #2, various people have convinced indie developers to let them do free OpenPandora ports of their closed-source games for users who already bought the game resources via the PC version. (eg. VVVVVV)
Arduino and RaspberryPi are quite high level. I prefer Atmel AVR and Microchip PIC assembly.
For the record, I didn’t claim they were low level, only that they were limited hardware compared to what most people consider a computing device these days (like a desktop, laptop, or smartphone/tablet).
But, the Arduino is no less low level than the AVR or PIC. All three can be programmed in assembler or C, for instance. What Arduino adds is a preprogrammed bootloader. Not exactly rocket science to add that to your AVR or PIC programming.
You could also program a Pi with assembler and not use Linux at all (roll your own OS or go without). Incidentally, you could do the same thing with your PC today even if it is a multi-CPU server behemoth.
The Arduino hardware is built on AVR or, more recently, ARM chips.
I think he’s talking about the Arduino programming environment… and that relies on C++ to add a fair bit of abstraction. (eg. Function calls to read and set pins rather than bitwise operations, custom types like Serial and Servo, etc.)
I love old stories like this. Often, it’s not the ingenuity that I find so impressive; ingenious people are ten a penny. It’s the dedication, the sheer bloody minded force of will required to actually implement an ingenious idea that I find so attractive.
It reminds me in many ways of some of the effort that went into producing Hakmem.
And they should be. We don’t need more programmers trying to squezze the last KB out of the main memory anymore. Or programmers trying to optimize the fixed steps inside a loop.
We need progammers that code secure programs by checking buffers and such, and use smart data structures so that the O(x) of the program is good. The main reason programs lag today is because someone used a really dumb data structure, cranking out O(n^3) or exponential code, not because of an increased amount of fixed steps. We need smart algorithm scientists, not code hackers.
But anyway, it’s an impressive achievement. Just try to imagine it: A value with a range of 0 to 255. You ‘ve got only 1024 of them for data and the program text (instructions). Go and code a chess program.
Edited 2015-03-05 21:30 UTC
A display alone would eat up 64 of those bytes just for the board (81 if you want to label each column/row). You need as many as 10 bytes just to represent a chess move (it could easily take less internally but the display/input would require more). Every character of every text message you intend to display would also eat up a byte of memory (so displaying “check mate” would use up 10 bytes, for instance). It all adds up in a hurry.
This is a really old problem that programmers have worked to death over the years. Even modern chess programs do much better than you would think they would bother to (memory efficiency wise) when it comes to storing game state.
http://en.wikipedia.org/wiki/Board_representation_%28chess%…
Using a piece-list approach (store the state of each of the 16 pieces instead of the whole board), you can store the entire game state in 20 (packed) bytes of memory, plus another 2 bytes for stuff like whose turn is next, 50-move rule, en-passant, etc.
Also relevent:
http://js1k.com/2010-first/demo/750
That is a full chess game, with AI, in 1KB of javascript.
1) 1KB of javascript, 50 mb of runtime in the browser
2) Not a full game, you can’t even castle
I said relevant… It’s obviously not in the same league as the hand coded assembly on an 8-bit.
1. You said “relevent”
2. Who cares
1. You said “relevent” [/q]
Wrote.
And if we should proceed in pedant mode you _wrote_ 50mb which is 1/160 of a byte. Pretty damn small.
You obviously. Why else would you respond?
Yawn.
Oh really! Please preach the gospel to those who work on weather prediction, or nuclear simulations, or or protein modelling, or data mining
Some people are really good at modeling problems in terms of sound engineering (picking the right data structures, code organization, etc.). Their work tends to come out the other end looking like an optimal solution to the problem – clean and easily maintainable. However, when run on actual hardware sometimes you discover that math and the real world realities of modern computers are often at odds with each other (i.e. its too slow, uses too much memory, causes cache thrashing, etc.). When this happens these types usually throw up their hands and want expectations reduced…
I’m not saying your wrong – most of the time your right. But programmers who can mentally model how computers actually work (as opposed treating them as abstract Turing machines with infinite resources) are still extremely valuable. They are usually the ones that fix the kind of problems mentioned above…
The world needs both kinds of programmers.
Edited 2015-03-06 06:40 UTC
I’m the proud owner of a zx-81.
Gonna type this one in.
I would suggest “GCR decoding on the fly” as the greatest program ever written:
http://www.linusakesson.net/programming/gcr-decoding/index.php
It is close to the only possible solution to a highly specific timing problem where every single assemblt instruction counts and the code has to reach an exact number of cycles through different code paths. It’s insanely compact code.
I registered just to comment on this one.
First of all the article is a repost from a 2001 article. Original here: http://www.kuro5hin.org/story/2001/8/10/12620/2164
Second, the author claims that it was fitting a chess program into 1k a major reason for it being the best program. ZX81 chess is from 1983. In 1976 Peter Jennings wrote Microchess for the 6502 based Kim-1 board which was also 1k.
http://www.benlo.com/microchess/index.html
There are still lots of programmers who take pride in writing small, compact code. Take a look at IOCCC competition entries for some examples:
http://www.ioccc.org/
Tiny chess programs are still being written in various languages to this day. Look at these by Oscar Toledo for example:
http://nanochess.org/chess.html
Edited 2015-03-05 22:17 UTC
There was also one on the Atari 2600, though it took like 3 days for the CPU to make a move on harder levels
Atari Video Chess would take over 10 hours to make a move in the highest difficulty settings!
Highly recommend playing this 1979 classic though! It supported castling and en passant. Also illegal moves were recognized and the game “buzzed” you to that effect. Not bad for a 4k cartridge!
I remember my dad playing Atari chess a lot back in the day. He’d make a move, go to work, then come home and make another move
I myself have never been a big fan of chess, largely because I suck at it. And like many other things, the time it takes to get good at it hardly seems worth the effort.
And Atari 2600 only has 128 bytes of RAM.
BTW, nice historical outline of computer chess: http://www.andreadrian.de/schach/index.html (in German …but with screenshots!). Dedicated chess computers of the past had similarly limited specs…
Me, I cut my teeth on some version of http://en.wikipedia.org/wiki/Colossus_Chess for C64, still quite small by modern standards.
…and perhaps with quite decent playing strength, judging from comments on lemon64 links. Plus, http://en.wikipedia.org/wiki/Sargon_(chess)#Sequels “Even though chess programs of the time could not defeat a chess master, they were more than a match for most amateur players.” is soothing. 
(because while Colossus was a challenge, I could beat it – me being an amateur, never “formally” trained in chess; who knows, perhaps those Colossus matches from almost 2 decades ago taught me something… either way, other non-trained humans never seem to be a match for me – and, on the few occasions I played with chess-trained human players… they of course won, but it supposedly took them more time and effort than is typical, when confronted with other total amateurs)
Edited 2015-03-08 23:52 UTC
The brilliant and talented people at MenuetOS are still releasing new versions of their operating system that boots from a single floppy. In fact the last update was Feb 24, 2015.
And it’s not just some DOS-like text-based OS either, but a full operating system with a desktop GUI, drivers, internet browser, basic production apps, and even games like Quake and Doom. All on a single floppy disc! That’s 1.44 megabytes for the young folks who aren’t familiar with floppies.
For comparison, Window 8 requires 10-13 GIGAbytes of space. :O
Is the greatest program ever written.
These programmers were never a living breed. Programmers have always tried to fit their programs into the resources they were given. Those resources could be time, budget, hardware, latency, bandwidth or “it has to work exactly like the old system, only better”.
There were, and still are programmers who like to focus on the “fit it on the hardware” side. That is why old news like this gets surpassed by new news like this: http://hexus.net/tech/news/software/80086-computer-chess-program-wr…
Started as a CoBol programmer on 360. Gave Paul Allen $60K to buy out his code from MITS in Albuquerque. Owned two Sinclair Z81s. BUT never stuffed code into 1K. We were limited to 100K initiators on the 360 and wrote segmented code to make it fit. Gee whizz CoBol was an awful language!
Surely you guys have seen this recently? http://www.pouet.net/prod.php?which=64962
Some detractors say the amiga was held back by its hardware development being slow, some claim that it was exactly this that made it great. It had a commonality in what people had available as a base and software was tailored to run on machines that was not supposed to be able to. Hard to find more efficient programming than on the classical amiga of later years, where they really shaked out the absolute max the 68k had to offer.
487 bytes! that’s *tiny*
http://gizmodo.com/the-smallest-game-of-chess-takes-up-just-487-byt…
This article and Thom’s blurb comment reminded me of the Stoy of Mel.
A lot of people here probably already know of it and I’m sure a lot of us would also enjoy (re-)reading it:
http://www.jargon.net/jargonfile/t/TheStoryofMel.html
Cheers.
Edited 2015-03-08 22:25 UTC