Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
The greatest program ever written

By codemonkey_uk in Op-Ed
Fri Aug 10, 2001 at 01:13:48 PM EST
Tags: Technology (all tags)
Technology

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.

The Sinclar ZX81.

Think about that amount of memory for a moment. 1 kilobyte. 1024 bytes. Can you write down the rules of chess in less than one thousand characters? That's a tricky task in itself. Fire up you favourite compiler, and build a minimal application. I'm guessing that its more than 1k in size, and it doesn't do anything yet.

But wait a second. 1k was the capacity of the machine. How much was actually available? The answer, as you will find if you follow the link at the end of the article, is a meagre six hundred and seventy two bytes! This article takes up more space than that.

And it had AI. Not very tough AI mind you, but AI none the less. So not only could is display the board, verify the your moves according to the rules, and detect a win or a draw, but it could select moves for itself and play them.

All this and more. He not only conceived and executed the idea that a game of chess could be packed into so few bytes, but he published the source code, along with a detailed explanation of how it was done in the February 1983 issue of `Your Computer' magazine. This article is essential reading, a trip down memory lane for those of us old enough to remember those furious, exciting 8 bit days, when the limitations defined the experience of programming, and an important piece of history for those brave young hackers who take for granted the luxuries of life, like compilers, swap space, and keyboards that click.

So, David Horne, if your out there - this is for you. I, and I'm sure, my fellow programmers, bestow upon you this honour: You, sir, created The Greatest Program Ever Written.

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o Carmak
o Abrash
o urban myth
o Sinclar ZX81
o The Greatest Program Ever Written
o Also by codemonkey_uk


Display: Sort:
The greatest program ever written | 25 comments (22 topical, 3 editorial, 0 hidden)
1k is plenty! (2.75 / 4) (#1)
by pallex on Fri Aug 10, 2001 at 12:25:54 PM EST

Enough to run a power station, apparantly. (Or did you need the 16k ram pack for that?)

Power station (4.00 / 1) (#12)
by fluffy grue on Fri Aug 10, 2001 at 06:25:00 PM EST

Power station logic really isn't all that complex, AFAIK.
--
"Is not a quine" is not a quine.
I have a master's degree in science!

[ Hug Your Trikuare ]
[ Parent ]

Yes (4.50 / 2) (#13)
by marimba on Sat Aug 11, 2001 at 12:34:43 AM EST

Yeah, it's pretty much

while(!california) ;
exit -1;



[ Parent ]
Atari 2600 Chess (3.33 / 3) (#2)
by IntlHarvester on Fri Aug 10, 2001 at 12:32:56 PM EST

OK, it had a 4K ROM, but still a pretty amazing accomplishment considering that the machine only had 64 bytes (or whatever) of RAM. The AI is actually fairly decent too, or so I hear from chess players.

I'm sure there will be plenty of other examples of 1K chess from the old minicomputer days.

cartridge systems (none / 0) (#19)
by codemonkey_uk on Mon Aug 13, 2001 at 04:37:27 AM EST

The Atari 2600 was a cartridge based system. That means that the entire program is in ROM, and comes with any additional RAM required. I have done a few searches, and as far as I can see there is no indication that this system only had 64 bytes of ram, so I put it to you that you made it up.

Theres is one other example of 1k chess - see this comment for more information.

PS Anyway, I don't count chess games that sometimes cheats.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Sorry, 128 bytes (5.00 / 1) (#21)
by IntlHarvester on Tue Aug 14, 2001 at 12:40:46 AM EST

http://www.atariage.com/2600/faq/index.html?SystemID=2600#specs

And I'll bet my left nut that there's nothing but an EPROM in the Video Chess cartridge, but I'm not breaking mine open to see. 2600 programming is fairly well documented on the web, take a look. I thought you might be interested in a chess implementation on another very limited system.

(I know a couple people that played it excessively, and they've never complained about it cheating.)

[ Parent ]
Clever stuff (none / 0) (#22)
by codemonkey_uk on Tue Aug 14, 2001 at 04:09:35 AM EST

I'd assume 64 bytes for the 8x8 board, and the other 64 for intermediate results & calculations. That is damn tight. Interesting link! :)
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
RAM in the VCS (none / 0) (#24)
by davidduncanscott on Thu Aug 16, 2001 at 05:31:39 PM EST

128 bytes included the stack, so you had to count your procedure calls to make sure that you didn't overwrite your variables.

It's been a long time since I wrote for the thing (and nothing like chess), but I would've squozed that 64 byte board:

There are 64 squares, but only 32 pieces. At any given time at least half the board is empty, so I'd work the other way and make a list of the men and store their positions. Let's see, 64 squares map to 6 bits, leaving two bits for status -- let's say the high bit for "captured" and the next for "queened" (yes, I know that one can in principle promote a pawn to any piece except king, but who the hell does? I'd live with the limitation). Complete board in 32 bytes.

Thank God I don't have to do that stuff anymore.

[ Parent ]

Assembly (3.33 / 6) (#5)
by ucblockhead on Fri Aug 10, 2001 at 01:01:44 PM EST

It is amazing what you can do out of necessity. It is also amazing how little memory you need when you give up the bloat of languages and OS and just code at the raw metal. It is unfortunate that younger programmers don't get the experience of trying to cram stuff into limited program space.

I also find it amusing that in these days of games delivered on multiple cds, some of my favorite games of all time fit on 140k floppies, with room left over.


-----------------------
This is k5. We're all tools - duxup

cs.nmsu (4.00 / 1) (#11)
by fluffy grue on Fri Aug 10, 2001 at 06:22:24 PM EST

Here at the NMSU CS department, one of the required classes is CS273 - Machine Programming and Organization. Through the course of a semester, students build an atonomous car out of lego. The car is controlled by a Motorola 68HC11, which is an embedded microcontroller which is similar to the 6502 (though it has two accumulators and two index registers). They get 256 bytes of RAM and 1.5K of EEPROM to play with. All coding is done in assembler.

When I took that class, I think my final code (which had to solve a simple maze) took about 200 bytes of ROM and 10 bytes of RAM, and even then it was bloated by my standards. :)

A friend of mine went above and beyond when he took that class. For his final project, he wrote a miniature UNIX (complete with a scheduler and command prompt) and put a few programs on it. It has become the stuff of legends here.
--
"Is not a quine" is not a quine.
I have a master's degree in science!

[ Hug Your Trikuare ]
[ Parent ]

RAM-pack wobble, anyone? (3.50 / 2) (#7)
by projectzero on Fri Aug 10, 2001 at 03:59:02 PM EST

The ZX81 had an extremely dodgy edge-connector expansion port on the back - a hallmark of all Sinclair machines - which was only secured by the pressure of the female connector pressing down on it. People who went out and bought the (extremely expensive) 16K RAM expansion packs offered by various vendors soon found out exactly how crap the connector was. Hit a key too hard typing in your latest opus (like, say, 1K Chess from Your Computer, which I may still have a copy of somewhere if I look deeply enough into my cupboards), or cause the machine to otherwise move about, and you were very likely to suffer from RAM-pack wobble; one line of the expansion port disconnected was all it took to reset the machine - and lose your program - entirely.

It was the BSOD of its day :-)

Seriously, though - all programmers should have to try doing something useful with a ZX81 or Spectrum or some other memory-limited system. It teaches you to think your way around problems. Too many lazy programmers these days just use brute force or CPU cycles to get over a hump they could have coded elegantly around. Makes me ashamed to admit to coding in VB...


RAM-pack wobble, anyone?: Solved (3.00 / 2) (#14)
by nickrud on Sat Aug 11, 2001 at 01:14:09 AM EST

Electrical tape and a metal brace, with tiny plastic disks glued to the membrane keyboard. It was recommended in Sinclair's newsletter :) I have no idea who wrote the programs I got from Sinclair and a fanzine, but keying in that source was my first experence with computers. Altered _my_ career path.

[ Parent ]
Premature optimization is the root of all evil (4.33 / 3) (#16)
by afeldspar on Sat Aug 11, 2001 at 11:28:17 AM EST

Seriously, though - all programmers should have to try doing something useful with a ZX81 or Spectrum or some other memory-limited system. It teaches you to think your way around problems. Too many lazy programmers these days just use brute force or CPU cycles to get over a hump they could have coded elegantly around.

On the other hand, you would want to be very careful about how you introduced this particular educational experience, because it could end up teaching entirely the wrong lesson: not how you can optimize when it's necessary, but how to optimize everything -- even when the optimization is premature and not needed.

A sadly human flaw is learning how to do one thing (such as optimize) and coming to believe that this is the skill which matters above all others. The truth is that, even though programs which use too much memory and too much disk-space are annoying, it is almost always easier to solve these afflictions than the affliction of difficult, convoluted, hard-to-understand-or-maintain code which may originate as, theoretically, the solution to the above.

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." -- Donald Knuth

-- For those concerned about the "virality" of the GPL, a suggestion: Write Your Own Damn Code.
[ Parent ]
The thing to remember ... (none / 0) (#20)
by codemonkey_uk on Mon Aug 13, 2001 at 04:40:42 AM EST

The thing to remember is that, when working on very restricted systems, one person can easly hold the whole program in their head, so heavy optermisation isn't a problem - its a solution.

On modern systems, it takes so much work to get anything new done, and there are significant resources available, that it pays to put readability before optimisations.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]

Bah! (3.33 / 3) (#8)
by cyberdruid on Fri Aug 10, 2001 at 04:35:11 PM EST

What kind of random rant is this?! Many people wrote 1k chess-programs. There were even competitions for them!
To my knowledge this Horne-dude was not the first to do it either (although I did not have the energy to research the matter). For example, in 1976, a Canadian named Peter Jennings wrote a program called Microchess 1.0; it ran on an obscure microcomputer (the Kim 1), which contained a 6502 CPU, no ROM, and 1K of RAM. The program even played decent chess.
By the way, the greatest programmer ever was probably Newton or perhaps Eratosthenes. They thought up algorithms just for the theoretical pleasure. Totally impractical in a time without Turing-like automatons, but used hundreds of year later.

/Mr. Cyberdruid

Cite reference (none / 0) (#18)
by codemonkey_uk on Mon Aug 13, 2001 at 04:24:06 AM EST

I did research this article, and I really don't think "many people wrote 1k chess-programs". The only reference I can find to this Peter Jennings is here, and its only a breif mention. It is quite an acheavement and it predates Horne, but as there is no sign of sourcecode, I can't really compare.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
Consider some of the programs... (3.50 / 2) (#9)
by jd on Fri Aug 10, 2001 at 04:37:37 PM EST

On the ZX80, the infamous predecessor to the ZX81. This had something like 256 bytes available, and yet some amazing programs were written for it.

Going back a LONG way, the first-ever stored program was a program for calculating the highest common factor of two numbers. IIRC, it occupied a grand total of 12 32-bit words.

A little bit further forward in time, now, and you reach =THE= two games that defined the 1980s - ELITE, and REVS. The first was a space trading and combat simulator, supporting 32 tradable items, 2 types of solar system, over 100 spaceships, 4096 systems, 2 missions, some stunning graphics (for the time), an economics engine, a political engine, a decent AI, medium-resolution graphics (in two different resolutions at the same time), =and= a very nice logo. The whole thing fit onto 7K of RAM and a 100K floppy. Or, it you wanted to cut out the missions, half the spaceships, and half the systems, you were left with something that just took that 7K.

REVS, on the other hand, was a Formula 3 simulator, with OK graphics. The main attraction of REVS was the quality of the simulation. The aerodynamics and the car's behaviour were very respectable. Far better than any other program of the time, and (IMHO) respectable in comparison to any program today. This program was a little larger, weighing in at something like 17K, but name a programmer today who could even DREAM of coding something that compact!

That's easy (2.00 / 2) (#10)
by Rainy on Fri Aug 10, 2001 at 04:50:01 PM EST

Even today, I dream about coding something like that every day. Unfortunately, I don't know any assembly and very little C, so it remains a dream, alas..
--
Rainy "Collect all zero" Day
[ Parent ]
Maybe you should try it (3.66 / 3) (#15)
by Tatarigami on Sat Aug 11, 2001 at 05:04:16 AM EST

Assembly isn't difficult, you just need a list of commands for the processor you're coding for, and a lot of patience. (It makes you write out every step, there's very little pre-written to save you some time. One of my class projects was writing a random number generator. That took me about six hours.)

I don't think it's any more complicated than a high level language, provided you're satisfied with achieving simply goals. If someone suggested that I write something as basic as Life in assembly language, I'd probably soil myself in fear.

But if you want to do it, there's no reason to hold back. I learned on a freeware emulator for a particular chipset that escapes my mind now, I'll bet there's an obscure FTP site out there where you could get something similar.

[ Parent ]
I was kidding. (3.00 / 3) (#17)
by Rainy on Sat Aug 11, 2001 at 02:24:41 PM EST

I don't really dream about writing assembly programs. I'm quite happy with python.
--
Rainy "Collect all zero" Day
[ Parent ]
Buggy? (none / 0) (#23)
by gordonjcp on Thu Aug 16, 2001 at 10:13:12 AM EST

a poorly documented, buggy machine

Gzzht? Whh? (other noises of incoherent indignation) WTF?
Come on, the ZX81 was rock solid. I still have my original one, along with a couple of others. Read the article, Chess in 1k!! Thus no ram pack, hence no infamous ram pack wobble.
And poorly documented? The user manual had 4 pages or so describing the internal system variables, and what you could poke into them. All 20-odd variables fully documented!

[splutter, rage...]

Give a man a fish, and he'll eat for a day. Teach a man to fish, and he'll bore you rigid with fishing stories for the rest of your life.


Yes. Buggy. (none / 0) (#25)
by codemonkey_uk on Tue Oct 02, 2001 at 09:49:17 AM EST

How about you read the article. What is line 2 in the 1k chess program for? Line 2 is:
A Slow statement. This has been called from Basic to ensure that all ZX-81s will work irrespective of whether you have an early ROM with error or not.
I guess you got the later model with the fixed ROM, or perhaps your just blowing hot air.
---
Thad
"The most savage controversies are those about matters as to which there is no good evidence either way." - Bertrand Russell
[ Parent ]
The greatest program ever written | 25 comments (22 topical, 3 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!