Linked by Thom Holwerda on Thu 5th Mar 2015 19:54 UTC
General Development

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.

Order by: Score:
jgagnon
Member since:
2008-06-24

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.

Reply Score: 6

ssokolow Member since:
2010-01-21

...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)

Reply Score: 5

JAlexoid Member since:
2009-05-19

Arduino and RaspberryPi are quite high level. I prefer Atmel AVR and Microchip PIC assembly.

Reply Score: 3

jgagnon Member since:
2008-06-24

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.

Reply Score: 3

ssokolow Member since:
2010-01-21

But, the Arduino is no less low level than the AVR or PIC.


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.)

Reply Score: 3

Comment by BeamishBoy
by BeamishBoy on Thu 5th Mar 2015 20:48 UTC
BeamishBoy
Member since:
2010-10-27

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.

Reply Score: 5

Comment by kurkosdr
by kurkosdr on Thu 5th Mar 2015 21:28 UTC
kurkosdr
Member since:
2011-04-11

Sometimes I feel like these kinds of programmers are a dying breed.


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

Reply Score: 3

RE: Comment by kurkosdr
by jgagnon on Thu 5th Mar 2015 21:42 UTC in reply to "Comment by kurkosdr"
jgagnon Member since:
2008-06-24

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.


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.

Reply Score: 4

RE[2]: Comment by kurkosdr
by galvanash on Fri 6th Mar 2015 06:24 UTC in reply to "RE: Comment by kurkosdr"
galvanash Member since:
2006-01-25

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.

Reply Score: 3

RE[3]: Comment by kurkosdr
by galvanash on Fri 6th Mar 2015 07:03 UTC in reply to "RE[2]: Comment by kurkosdr"
galvanash Member since:
2006-01-25

Also relevent:

http://js1k.com/2010-first/demo/750

That is a full chess game, with AI, in 1KB of javascript.

Reply Score: 3

RE[4]: Comment by kurkosdr
by krakal on Fri 6th Mar 2015 17:50 UTC in reply to "RE[3]: Comment by kurkosdr"
krakal Member since:
2015-01-03

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

Reply Score: 3

RE[5]: Comment by kurkosdr
by galvanash on Fri 6th Mar 2015 20:15 UTC in reply to "RE[4]: Comment by kurkosdr"
galvanash Member since:
2006-01-25

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.

Reply Score: 3

v RE[6]: Comment by kurkosdr
by krakal on Fri 6th Mar 2015 20:49 UTC in reply to "RE[5]: Comment by kurkosdr"
RE[7]: Comment by kurkosdr
by Megol on Fri 6th Mar 2015 22:31 UTC in reply to "RE[6]: Comment by kurkosdr"
Megol Member since:
2011-04-11

"[q]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" [/q]

Wrote.
And if we should proceed in pedant mode you _wrote_ 50mb which is 1/160 of a byte. Pretty damn small.


2. Who cares


You obviously. Why else would you respond?

Reply Score: 4

RE: Comment by kurkosdr
by roverrobot on Thu 5th Mar 2015 23:34 UTC in reply to "Comment by kurkosdr"
roverrobot Member since:
2006-07-23

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.


Oh really! Please preach the gospel to those who work on weather prediction, or nuclear simulations, or or protein modelling, or data mining

Reply Score: 7

RE: Comment by kurkosdr
by galvanash on Fri 6th Mar 2015 06:39 UTC in reply to "Comment by kurkosdr"
galvanash Member since:
2006-01-25

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.


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

Reply Score: 7

Comment by krakal
by krakal on Thu 5th Mar 2015 22:11 UTC
krakal
Member since:
2015-01-03

I'm the proud owner of a zx-81.

Gonna type this one in.

Reply Score: 2

Comment by Kroc
by Kroc on Thu 5th Mar 2015 22:12 UTC
Kroc
Member since:
2005-11-10

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.

Reply Score: 4

This article is 14 years old....
by Onyx_RE2 on Thu 5th Mar 2015 22:15 UTC
Onyx_RE2
Member since:
2015-03-05

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

Reply Score: 6

WorknMan Member since:
2005-11-13

In 1976 Peter Jennings wrote Microchess for the 6502 based Kim-1 board which was also 1k.


There was also one on the Atari 2600, though it took like 3 days for the CPU to make a move on harder levels ;)

Reply Score: 5

Onyx_RE2 Member since:
2015-03-05

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!

Reply Score: 2

WorknMan Member since:
2005-11-13

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.

Reply Score: 3

zima Member since:
2005-07-06

Not bad for a 4k cartridge!

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

Reply Score: 3

Bobthearch Member since:
2006-01-27

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

Reply Score: 2

Hello World
by Soulbender on Fri 6th Mar 2015 02:55 UTC
Soulbender
Member since:
2005-08-18

Is the greatest program ever written.

Reply Score: 4

Dying breed
by avgalen on Fri 6th Mar 2015 09:20 UTC
avgalen
Member since:
2010-09-23

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...

Reply Score: 3

Hurray David Horne
by Ex-NCR on Fri 6th Mar 2015 19:31 UTC
Ex-NCR
Member since:
2015-03-06

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!

Reply Score: 2

Slightly smaller
by sykosoft on Fri 6th Mar 2015 21:13 UTC
sykosoft
Member since:
2015-03-06

Surely you guys have seen this recently? http://www.pouet.net/prod.php?which=64962

Reply Score: 3

Comment by judgen
by judgen on Sat 7th Mar 2015 12:08 UTC
judgen
Member since:
2006-07-12

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.

Reply Score: 2

487 bytes. that's less than half 1k
by rkoot on Sat 7th Mar 2015 18:00 UTC
rkoot
Member since:
2006-01-03
The Story of Mel
by richarson on Sun 8th Mar 2015 22:23 UTC
richarson
Member since:
2014-05-24

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

Reply Score: 2