The greatest program ever written | Hacker News Reader

The greatest program ever written

kuro5hin.org

141 pointsniyazpk56 comments

I grew up coding assembly for 6502... and you can fit a lot in 1k.

the 1k is aided and abetted by the architecture of the computer.

* Reading keyboard is reading a register/known address, not loading the keyboard library, allocating a structure and jumping into an OS routine.

* Clear screen is writing zeros to a known address space

* Drawing is writing a 1 to a known address space

* Yours is the only process on the machine

* Text compresses well with Huffman

With those assumptions a lot more can fit in the 1K

I don't see how these assumptions really help - 'greatest program ever written' is a bit bombastic but working chess program in a few hundred bytes of z80 code is still quite impressive.

Reading keyboard is reading a register/known address, not loading the keyboard library, allocating a structure and jumping into an OS routine

Or calling a ROM routine. Reading the keyboard directly at the lowest level would probably just make the program bigger

Clear screen is writing zeros to a known address space

Generally, another ROM routine call.

Drawing is writing a 1 to a known address space

Not really. Just about all these machines had color. The Apple ][ had a fun non-linear video buffer layout, to boot.

Text compresses well with Huffman

Not a lot of text in a chess program.

It sounds like you're helping my point... thanks.

ROM routines is a jump into known addresses... so no extra impact on the 1K. Parameters are read from registers.

Color of 4bit? only a slight increase. Often acheivable in 1 instruction. Limit of 2 colors in 8x8 block on ZX81[1]

--------------------

[1] http://www.giantbomb.com/zx-spectrum/60-16/

I suppose if 'just about everything you said to support your point is wrong' is 'helping you', there's probably not much left to discuss.

You're linking to information on a ZX Spectrum which is not a ZX81. The ZX81 had a monochrome character mapped display with no pixel access (well - there were tricks that could sort of give you pixel access but they came much later than the time 1k chess was written)

Sorry about that... i didn't mention colour depth originally, someone else brought it up (trying to look smart).

6502 was my platform, so I missed the exact Z* platform...

I was sharing general info on assembly for 8bit, not specific to one platform (ZX81). This seems to have incensed some people who took a narrow view on what sort of comment was permitted.

I had a ZX81. Drawing was indeed done by writing directly to a special address space. However, you didn't write pixels directly but rather bytes which where rendered as characters on the screen by the system.

The ZX81 did not have colors.

In fact, if you look at the source code in the actual article, you can see the graphical characters used to draw the board right in the Basic code listing. :)

Reading the keyboard directly at the lowest level would probably just make the program bigger

Generally, another ROM routine call.

Thats @tezza's point. (Edit For Clarity): Since its just one instruction, you can shrink the size of your program, making fitting it into a small space less impressive (though, not unimpressive).

Not a lot of text in a chess program.

Fair enough, so that one doesn't help, but the other two do.

Thanks roundsquare.

For reference to my original post: I wasn't trying to deny that this program is amazing... it is.

I was intending to illustrate that you could do a lot more with 1k historically than you can nowadays, and that some of the worst offenders to bulking out a process don't apply on older computers in assembly.

That doesn't take away from the brilliance of AI in 1k, but rather I think the focus should be on that and not the chessy bit.

Except it's not one instruction - you still have to put the result somewhere, potentially save registers (of which there is a great dearth) and so forth. My point is none of the things listed (aside from not really being part of 'the architecture') are significant factors on top of being largely inaccurate. What does make a difference is that the instructions themselves are short, the addresses are short, alignment is on the byte, etc. Can you fit a lot into 1k? Sure, if you're clever, you can apparently fit a whole chess program in less. But the fact that, say, there's just your process or that Huffman encoding is neat has next to nothing to do with it.

Some of the 'results' that need storing can be stored on the screen itself. An example of a difference between these 8bit machines and today's machines that @tezza is talking about.

I'm really not clear on where we disagree at all. We seem to agree that:

1) Reading keyboard input and clearing the screen can both be executed via a ROM command.

2) Doing these things otherwise would have made the program bigger.

Am I right that we agree on these? If so, I don't see how you don't agree that:

3) Having both of these as ROM commands helps make the program smaller.

As far as I can tell, we agree on these 3 points. You, however, seem to be bringing up a few more points:

4) Instructions are short.

5) Alignment is on the byte.

...

And, from what I can tell, you are saying that these were more helpful in reducing the size of the program. Am I right so far?

If so, you maybe right that compared to modern computers, but that doesn't mean that @tezza is wrong that the other factors helped.

Also, I believe its already been agreed that Huffman encoding doesn't help...

Heh, well, I'm not clear what is unclear. The poster said 'well, the program is short because of these N things'. Except none of the N things were accurate or relevant. There are architectural factors that much more significantly affect the size of the program, but poster didn't mention any of them. My point is tezza either didn't know or didn't think what s/he was posting about. It's sort of like having the discussion "So, airplanes fly because of magic" - "Well, no actually airplanes fly because of [a bunch of physics]" - "Right, you're making my point, airplanes fly!".

Okay, I feel like there is a real break in communication and I'm curious to explore it. If it gets too tedious for you, feel free to ignore me.

Going back to the N = 5 things. Three seem to help, two don't.

The helpful ones:

* Reading keyboard is reading a register/known address, not loading the keyboard library, allocating a structure and jumping into an OS routine. *

Doens't this make make the program smaller? Getting the key entered is just a read instruction. Sure, there maybe things that happen afterwards (as you said) but just getting the key is one instruction i.e. read <some memory spot>

* Clear screen is writing zeros to a known address space *

Again, instead of doing a number of instructions to clear the screen (I have no idea how many this takes on a modern computer) you just need to write do write 0 <memory location>

* Drawing is writing a 1 to a known address space *

My understanding is that on modern computers this is a complex operation. But, in this it appears that drawing is again a single operation.

In each case, the point @tezza is making is: Hey, all you people who haven't ever used these crazy old machines, these are the types of things that make it easier to create a very small chess program (in terms of size of the program itself, not the resources it uses). All these things that nowadays require a lot of instructions only required a single instruction on this machine.

The other two points, I agree, are probably not helpful.

Using the keyboard reading as an example, it seems whoever designed this machine said "one way to reduce the size of programs is to make it easy to read keyboard inputs. Lets have the hardeware store that in a known address." Thus, the fact that you can do this does help reduce the size of the program.

Am I wrong? Let me know. I've never worked on these machines so I could be completely off base. A friend of mine used to wonder if it would be instructive to learn about programming under these limitations so I'm genuinly curious.

Note: I'm not objecting to your points about what reduced the size of the program. I'm just trying to figure out why you think @tezza's points don't help.

Dude, you're going over the top, under the bottom and around the sides.

8bit coding was very different. I listed some common tricks not necessarily specifically ZX81, nor necessarily used in this chess game, but illustrative of common scenarios.

Thus you could fit much more in 1k than you can today.

ENDE (please take a deep breath)

Please don't 'dude' me. My breath is perfectly even. And at this point I don't think I was even replying to you. The things you said make make a program short are simply inaccurate and not the significant factor in making programs shorter. That's all. Nobody made their programs shorter by the 'tricks' you describe. And it's not a ZX81 thing. To read the keyboard on, say, a 6502 apple ][ you have to do a store to clear the strobe, a read to get a value and a check on the most significant bit of the value to check for keypress and then you need to mask out the actual value. I don't need to go into endless detail about the rest of them. The primary factor is the size of the instructions and the size of their operands (8 and 16 bit addresses).

While we're on the subject, might as well point out the amazing .kkrieger game: http://en.wikipedia.org/wiki/.kkrieger

A high quality 3D FPS that is a mere 97,280 bytes through the magic of procedural generation.

IMHO this 128 Byte(!) 3d demo is even more impressive: http://pouet.net/prod.php?which=53871 (Click on the Youtube link at the right to see it running)

Not to knock Mr. Horne's achievement, but Peter Jennings wrote Microchess for the KIM-1 (a 6502-based machine with 1K of RAM) back in 1976.

Source code here: http://users.telenet.be/kim1-6502/microchess/microchess.html

I had the PET 2001 version (running in 7K of RAM) back in the day, and it played quite well, all things considered.

In fact, just to show what we're talking about, here it is

     D8A2FF9AA2C886B2201F1F206A1FC5F3F0F685F3C90CD00FA21FB5709550CA10F986DCA9CCDO12C90ED00720B202A9EED007C914D00B20A20385FB85FA85F9D0BFC90FD006204B034C9D0l4C960110000304000702O50l06101711161215141373747077727571766067616662656463F0FF0l1011OFEFF1DFElEEF2120E1F210B0A0606040404O40202020202020202A6B5305

CA5B0F308EO08D004C5E6F02EF6E3C901D002F6E3501EA00FA5B1D96000 F0038810F8B9A000D5E4900494E695E4180875E595E528E004F00330316 0A5E885DDA90085B5204B0320B20220000220B202A90885B52009022031 034C8017E0F9DO0BA560C5B1D004A90085B46050FDA007A5B1D96000F00 588F0F110F6B9A000D5E2900295E2C6B5A9FBC5B5F003202503E6B560C9 08B01220EA03A21FB550C5FAF003CA10F786FB86BO4C000000A210A9009 5DECA10FBA91085B0C6B0100l60201E03A4B0A20886B6C0081041C00610 2EC004101FC00lF009100E208E02D0FBF0D9209C02DOFBF0D2A20486B62 09C02D0FBF0C7209C02A5B6C904D0F7F0BCA21086B6208E02A5B6C908D0 F7F0ADA20686B620CA025005300320000l201E03C6B6A5B6C9O5F0EB20C A02708F308D20000lA5B129FOC920FOEE4C0D0220CA023003200001201E 03C6B66020CA02900250F930070820000l2850F0201E03C6B660A20F38B 460A977F550956094503550CA10EB60A5B1A6B618758F85B12988D042A5 B1A220CA300ED550D0F9E0103033A97F69017001B8A5B53024C90810204 808A9F985B585B4204B0320B202200902202E03286885B5A5B4300438A9 FF6018A90060A9FF18B860A6B0B55085B160204B0320B20220090220820 2BA86B3A6B29A6885B66885B0AA68955068AA6885B195504C7003BA86B3 A6B29AA5B148A8A21FD550F003CA10F9A9CC95508A48A6B0B5509450488 A48A5B648BA86B2A6B39A60A6E4E4A0D004A900F00AA6E3D006A6EEDO02 A9FFA20486B5C5FA900CF00A85FAA5B085FBA5B185F94C1F1FA6DC1017A 5F9D5DCD00FCAB5DC85FBCAB5DC85F9CA86DCD01A85DCA20C86B586FAA2 14200202A20486B5200002A6FAE00F9012A6FBB55085FA86B0A5F985B12 04B034C0000A9FF60A20406F926FACAD0F905F985F985B1600000000000 0018A98065EB65EC65ED65El65DF38E5F0E5F1E5E2E5E0E5DEE5EFE5E3B 002A9004A18694065EC65ED38E5E44A18699065DD65DD65DD65DD65El38 E5E4E5E4E5E5E5E5E5E0A6B1E033F016E034F012E022F00EE025F00AA6B 0F009B450C01010031869024C7703

There you go: a fully functional Chess program, with AI.

To actually run that on the PC I'm using right now, I would presumably need to also download an emulator for the machine it was designed for, which is presumably larger than 1K. Just saying.

I don't want to sound negative, but 'greatest program ever written' is really an overstatement. He has created this program, because he needed to fit into 1k. If it was needed nowadays, hundreds of programmers could achieve this result. (I would be so happy to code these kind of things at my working place instead of the bloated overcompilcated softwares...)

If someone would create a prize (a prize like the netflix prize or the Hutter prize) with $100k or something, to create the smallest chess program, I suppose hundreds of contestants would fit into 1k. But the competition would be high, and the winners would be probably very sophisitcated algorithms, which might deserve the 'greatest program ever written' title. But without competition it is easy to be the best.

Get them playing each other and then pick a winner that way.

Isn't this like saying "Orville and Wilbur wright really didn't do anything that great. Thousands of hobbiests could easily build an airplane that is safer, faster and more maneuverable than the wright flyer, and in their garages on weekends!".

It is the nature of tech to build on what was done before. It's hard to remember that something that now might be laughable, was at one point considered impossible.

I haven't read a blog post titled "The Wright brothers built the best plane ever" recently.

The Wright Brothers made the first powered heavier-than-air aircraft capable of sustained controlled flight.

The subject of the article is a person who wrote a chess program. Not the first chess program. Not the first successful chess program. A chess program. Nonetheless, it is still an impressive feat to fit a chess program with AI into 1k. But it is not comparable to the Wright Brothers' airplanes.

Link to the Full ZX-81 Chess in 1K article by David Horne:

http://users.ox.ac.uk/~uzdm0006/scans/1kchess/

And here's a ZX-81 emulator to play the actual game:

http://www.zx81stuff.org.uk/zx81/emulate.php?tzx=0%2F1KZXChe...

Totally off-topic: Does anyone else miss the kuro5hin peak days? I can't seem to find any single community to capture the soul of what it was. HN and Reddit are close, but something is lacking. Anyone know of such places?

I don't think either comes close to capturing the spirit of K5. Remember the "Dorm Wars" and "Fast Times at Phillips 66" serials?

I'd love to find a place like K5 again. Rusty killed it with the $5 registration fee for new accounts. The dupe accounts, multiple personalities, and role playing were part of the charm.

Yeah, those are exactly the sort of thing I'm talking about. Topic oriented communities are great, hence I really like HN; it's full of smart people who will discuss things well, but its all computers all the time. The thing about k5 was the whole "renaissance man" vibe.

The unique thing about k5 was that all the content was written by the users. Every other community on the web is just a link-n-blurb site with a discussion forum bolted on: Slashdot, Digg, Reddit, HN, MetaFilter, and on down the line. Only at k5 do you have long form, decently well-written pieces on any variety of subjects.

Thanks, I have no idea how I was unable to connect "renaissance man vibe" with "users wrote all the content". But you are absolutely correct!

What made it work? I would think it would be filled with a lot of low quality "articles."

Or is that where all the admin work came in?

What made it work, for a while, was that the community voted collectively (and still does) on the submitted articles. There are two queues: the edit queue and the voting queue. You are expected to put your article in the edit queue and deal with community feedback for about 24 hours before moving the article to the voting queue. Your ability to satisfy the community often went a long way toward whether or not you were voted up or down. If your article made a certain threshold of votes (or votes plus sufficient conversation) it was posted, if not it was dumped.

Poor moderation and poor adminship killed the site. There were no (permanent) negative consequences for bad behavior, since a dupe account could just be made, and if it was banned it was no big deal. There were also no real benefits for good behavior. So after a certain critical mass of trolls and griefers assembled, they managed to drive everyone off the site from 2004-2006.

You can see the overall rise and fall of the site here: http://k5.trolltrack.com/stats.php

You can see the new users flatline when the $5 paywall was instituted.

Fascinating system. Seems like it would require a host of very devoted users. I wish I had known about it earlier.

Anyone know of anyone trying to clone it since then (on any topic)?

There used to be a list of sites run on Scoop software (the CMS that k5 is built on, a counterpart to 'Slashcode' running Slashdot). It used to be hosted at scoop.kuro5hin.org, but rusty let that subdomain fail about a couple months ago and hasn't fixed it.

DailyKos is the most prominent site using Scoop to manage frontpage content and diaries. They made a host of extensions, fixes, features, and changes, but apparently didn't share anything back with the main Scoop codebase.

It's not clear anymore where one can download the Scoop sourcecode, although I think some k5 users have upped a copy somewhere.

As far as I know, k5's still one-of-a-kind. The closest copy is a site called hulver.com ("HuSi" short for "Hulver's Site"). HuSi was created by a disaffected member of the k5 community, hulver, who got fed up with the trolls. It is much more focused on diary content rather than frontpage-quality long form content. Basically, the entire British portion of k5 fled to HuSi, and they have pretty active admins there who ban the occasional visitor from k5 trying to troll. Still, it remains very small, and doesn't produce the same caliber of content that k5 once did.

To be fair, $5 registration fee came at the tail of a fairly long decline in quality.

That being said, it was great at its peak. Combination of a blog community, debating club and much more.

I miss trhurler.

You should have told him not to take a hike then.

Rusty no longer wanted to have to deal with dupe hordes gaming the system, crapflooding, griefing, harassing, and so on. The $5 killed user growth, but it also killed 99% of the admin workload. The tradeoff worked for rusty, even though it didn't work for the 'community.' Rusty's favorite site is MeFi anyway...

I fled k5 into the arms of reddit, but K5 had been dead for a long time prior to that.

It was funny reading the article, since I recognized a few names and immediately thought, "Holy Shit, that guy's still there?"

Then I saw the date.

I'm writing a javascript chess game write now and I'm currently at 200 lines + 50 of HTML. The source code of mine is larger than the byte code of his program. I am a moron.

source code can often be larger than byte code.

My first attempt at a javascript chess game was almost 7 years ago. 159 lines of javascript and html. Unfortunately, it's nothing more than a pieces-on-board sim. It doesn't do anything to control play or prevent cheating. It was college, it was fun http://members.gamedev.net/capn_midnight/chess/chess.html

When I saw the ZX81 reference I thought surely he meant 3d monster maze by Malcom Evans which was the first 3d game for a home computer (although it did need 16k of RAM).

Try 3d Deathchase - it's better than Doom!

I respect the acomplishment but I can think about a lot of other computer systems/programs with way more cultural, economic and scientific impact than this program.

E.g.: Unix, Java, Sabre, VisiCalc, Mars Rover and Hubble controlling software, etc.

C Chess program in less that 1200 chars: http://home.hccnet.nl/h.g.muller/max-src2.html

I think we should compare the size of the assembly code generated for this with the original.

Other than reducing the readability, I cannot think of any advantage offered by the mere compression of the source code.

I remember when I was six, my dad programmed a chess game on the Sinclar ZX81. He used to play real-life chess a lot so naturally, this was his first use for this little box. It was slow as hell and he had to pause screen rendering to make it faster. If you call simple backtracking "AI" then I think my dad wrote that "greatest program ever" too without knowing David Horne. (And my dad is definitely no urban myth, either...)

Are you sure the ZX81 he was using didn't have a 16Kb ram pack attached? Most people I know (me included) had one, since it was hard to do anything without it.

Very true, but I had this game, it was one of the few that ran without the rampak. I think I used the pak primarily for Bomber and 3D Monster Maze.

Good times!

This page would never show up in a search engine that de-lists ad-sense pages.

The greatest program ever written

The Best HN Hyperbole. (For today!)

The code referenced in the article is located at:

http://users.ox.ac.uk/~uzdm0006/scans/1kchess/

I suppose the theoretical limit is 1 bit -- if you define the program in terms of a virtual machine that takes 1 instruction -- "play a game of chess".

Reply on news.ycombinator.com