14 ms·

David Horne's 1K Chess on the ZX81 (2001)

380 points by jermo 12y ago

StavrosK 12y ago
Why does the author say "memory" when he means "disk space"? Or does he actually mean "memory", as in "RAM"? In that case, why would the size of the executable matter?
- ctdonath 12y ago
  There was no "disk" on a ZX81. Storage was audio cassette tape. The size of the executable mattered because it all had to fit in 1024 bytes RAM (no "K", no "M", certainly no "G") with all video & operating system memory.
  - StavrosK 12y ago
    Oh wow, I didn't know that, thanks. By the way, to whomever downvoted a legitimate question: Nice.
    - ColinWright 12y ago
      I didn't downvote you, but you asked a question the answer to which is easily available with the most trivial of web searches. You assumed he meant "disk space", assuming the author made a mistake when you could easily have checked and not asked the question here. In some sense, it's not a legitimate question for this context.
      - angersock 12y ago
        The question asked exactly is the sort of thing that "the most trivial of web searches" wouldn't have answered as well as either of the replies already up. One reply puts it into historical context, and educates the reader about the memory/persistence model of the ZX81. The other reply points out that the lack of virtual memory and whatnot means that, in previous times, you needed to have the entire thing loaded into memory to execute something. Without some digging and a knowledge of what to look for, those are non-obvious but useful points.
        TheOtherHobbes 12y ago
        Well - you could just search for "ZX81". First thing that appears is a Wikipedia article which explains how the memory and off-line storage worked. So I don't think finding this out would have been rocket science. Having said that, and having written my first code on a ZX81 (if you don't count an even older TI programmable calculator with even less RAM) I'm old enough to be amused by the question. :) However you slice it, chess in 1K was awesome coding.
      - nsxwolf 12y ago
        Must we obtain all information via dry web searches, and never from human exchange?
        sago 12y ago
        Well, this is the site where, in an article about "the 36 questions it takes to fall in love" someone suggested building a bot so you could go through the questions on your own.
      - ctdonath 12y ago
        Thing is, this context is way out of the norm for a great many HN readers. The notion of a general-purpose home computer without rapid-access storage, and hence without virtual memory, is so foreign to the younger crowd that the question is fair and the answer is almost unbelievable in their experience. There's nothing to prompt a web search, as what's being searched for is at odds with axiomatic presumptions.
      - metaphorm 12y ago
        its a 100% legitimate question. it was asked in good faith because the person asking it didn't know and wanted to know. its not a trivial web search either, because even knowing what to google for requires contextual knowledge that OP didn't have. punishing a person for being ignorant while they are trying to learn and become less ignorant is terrible behavior.
  - jameshart 12y ago
    "Operating System" is a stretch. BIOS would even be an overelaborate term for what the ZX81 had, given that IO was basically handled through fixed memory-mapping. What it had was a few inbuilt ROM routines and a main run loop that cobbled together a text-mode display, a line editor and a basic interpreter.
- deleted 12y ago
  [deleted]
- pyrois 12y ago
  "Memory" means RAM, here. As for why the size of the executable matters, you needed to have the entire executable in RAM before you could actually execute it. That's not so true these days, but it was back in the good ol' days* when you hooked tape cassettes up as your external storage. * Get off my lawn!
ctdonath 12y ago
TL;DR - chess, in 1K RAM including video and OS memory space.
tibbon 12y ago
Link to the code: http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ http://users.ox.ac.uk/~uzdm0006/scans/1kchess/
luma 12y ago
If you can't castle, you can't promote a pawn, and you can't en passant, it isn't chess.
- pyrois 12y ago
  True, but even "Chess lite" in 672 bytes is mind-blowing.
- pavel_lishin 12y ago
  You are welcome to add these things; we'll give you a generous extra 100 bytes.
  - bsaul 12y ago
    Wonder if any student somewhere isn't trying to take up the challenge of adding castling to the code, using an emulator. I like to think that's something i would try to do as a student, because i'm pretty sure there's a tremendous amount of skill to gain by doing it.
3327 12y ago
Holy smokes... blown away. 1K RAM? less then most email's we write... Now'a days rockstars and Ninja's are the glorified ruby guys who "seemingly" do Ruby/django magic... This is what counts...This is the real deal...
- pfortuny 12y ago
  Now you only have less than 800 bytes left. And counting.
- stpe 12y ago
  On this topic, check what was done (and still is, to some extent on the homebrew scene) on the Atari 2600 with 128 bytes of RAM and no framebuffer.
  - JonathonW 12y ago
    Of course, the Atari (unlike the Sinclair in the OP) executed code directly from the cartridge-- you didn't have to fit your whole program into that 128 bytes of RAM. Atari cartridges could be up to 4kB, or 32kB with bank switching, which is downright roomy for the era.
- moron4hire 12y ago
  Weeeell... The entire point of computers is to be able to do work that would be too tedious for humans. Computers exist so people can be lazy. Making better programming languages so programmers can be lazy is kind of the whole point of the job.
  - blowski 12y ago
    Exactly. For many, many projects nowadays, the project does not require a 1024 executable because RAM is cheap. Making code that's really easy to work with is just as impressive as this.
  - sago 12y ago
    The entire point of computers is to be able to do work that would be too tedious for humans. Really? News to me. Like the entire point of cars is to take you on journeys that would be too tedious to walk?
samatman 12y ago
Thanks to the Archive, the code and commentary is available: https://archive.org/stream/your-computer-magazine-1982-12/YourComputer_1982_12#page/n67/mode/2up https://archive.org/stream/your-computer-magazine-1982-12/Yo... https://archive.org/stream/your-computer-magazine-1983-01/YourComputer_1983_01#page/n79/mode/2up https://archive.org/stream/your-computer-magazine-1983-01/Yo...
- Doctor_Fegg 12y ago
  Oh, wow: there are issues of Your Computer on archive.org. Thanks. I loved that magazine.
  - didgeoridoo 12y ago
    There was a great interview on The Web Ahead recently with Jason Scott about Archive.org and the challenge of preserving these amazing bits of history: http://5by5.tv/webahead/97 http://5by5.tv/webahead/97
GregBuchholz 12y ago
Olivier Poudade has recently written and even smaller version of the chess program, clocking in at 468 bytes: http://olivier.poudade.free.fr/ http://olivier.poudade.free.fr/ http://www.bbc.com/news/technology-31028787 http://www.bbc.com/news/technology-31028787
- ctdonath 12y ago
  Prior HN discussion: https://news.ycombinator.com/item?id=8954630 https://news.ycombinator.com/item?id=8954630
VonGuard 12y ago
Just for the record, the Atari 2600 also had a chess game with AI. It also had only 1024 bits of RAM, but it had access to all of it because there was no OS or underlying hardware support, like in the Speccy. So while this is definitely amazing, the 2600 version is very close in the "insanely well coded" category, especially because the 2600 had some SERIOUSLY quirky hardware to deal with. For example, on the 2600, you could only draw half the screen's background: the other side had to be a mirror image. Additionally, the columns of pixels that you drew on the screen were enumerated, to the halfway point on the screen as follows: 12345678,87654321,1234 So you were drawing forward, backward, then forward again, and that only got you half the screen!
- ymra 12y ago
  It may only have had 128 Bytes of RAM, but it used 4K ROM cartridges, even more than that if the cartridge used bank switching. So Atari 2600 programmes had quite a bit more room to fit inside.
  - mgkimsal 12y ago
    IIRC, early cartridges only had 1 or 2k - the 4k was a limit for a while, but I don't think they all shipped with 4k in the beginning (cost savings). IIRC there was a trick later to allow for 8k cartridges (Pitfall II was 8k, I think, but memory may be failing me).
    - wazoox 12y ago
      IIRC, Pitfall II was 2K. 255 different levels in 2K, memorable isn't it ? :)
- tragomaskhalos 12y ago
  I read that chess was originally considered impossible to implement on the 2600, but there were promotional materials showing a guy playing chess on it and a customer complained that it wasn't available, so Atari went ahead and wrote it. The graphics were horrible but the AI was actually pretty good, so we just used to set up a real board and mirror the moves on that.
illsorted 12y ago
Original source: http://www.kuro5hin.org/story/2001/8/10/12620/2164 http://www.kuro5hin.org/story/2001/8/10/12620/2164
- SwellJoe 12y ago
  Whoah, I'd almost completely forgotten Kuro5hin, and a lot of other people obviously have, too, as the site is a ghost town. It was a really neat pre-reddit user-generated social media site; kind of a more democratic Slashdot. I knew the founder in some capacity (I don't even remember how/why, now, or their name...maybe because I worked on Squid or because I worked in Perl), and used to advertise my old company on Kuro5hin to be able to send some money their way. I quite liked it, and there was a brief time when I divided my time between Slashdot and Kuro5hin, as I currently divide my time between reddit and HN.
  - bokchoi 12y ago
    My favorite Kuro5hin article is the intro to the K language: https://www.kuro5hin.org/story/2002/11/14/22741/791 https://www.kuro5hin.org/story/2002/11/14/22741/791
    - Rodeoclash 12y ago
      Mine was the Casino story: http://www.kuro5hin.org/story/2001/7/19/181127/355 http://www.kuro5hin.org/story/2001/7/19/181127/355 Almost 15 years ago now yet I still remember it. That was Kuro5hin at its peak.
Fastidious 12y ago
Does anyone have a link to find out more about David Horne?
- Sevzi 12y ago
  Why? I hear Fastidious produces better code, faster, and without errors.
shubhamjain 12y ago
Amazing! it is hard to imagine to even barely scratch the surface with constraints like that. Sinclair ZX81 does seem to have an emulator[1], would it be possible to see it run? It seems the emulator would need a assembled binary, something I am not sure would be possible without whole lot of grunt work. [1]: http://www.chuntey.com/ http://www.chuntey.com/
smoyer 12y ago
I have that program! The cassette it came on is still in my basement (along with a couple of ZX-81s and TS-2000s). While it might be rudimentary AI, I also didn't beat it every time (maybe not even half the time when I started playing against it).
- pmontra 12y ago
  I believed to have it too but I checked and I've got the Chess program from PSION instead, which is for the 16kB ZX81. I remember that I lost every single game. I keep it on the old CDs bookshelf, with a cassette of Defender. They're maybe the last two tapes left from those years. The ZX81 is somewhere at my parents house. I also kept the BASIC Programming Manual. I develop with Ruby and JS now, probably no less than 16 MB for any program I run :-)
brownbat 12y ago
Olivier Poudade's BootChess claims to be the new record holder, 487-bytes of assembly: http://mashable.com/2015/01/30/play-it-better-tiny-chess-game/ http://mashable.com/2015/01/30/play-it-better-tiny-chess-gam...
- ctdonath 12y ago
  Now if someone could arrange a competition between the two...
henrik_w 12y ago
Kevlin Henney mentions this program in his talk "Cool Code". The whole talk is really worth watching. http://www.infoq.com/presentations/Cool-Code http://www.infoq.com/presentations/Cool-Code
tzs 12y ago
Impressive, as is the recent smaller program from a French programmer. Note, however, that both have sacrificed some rules. I believe they have both left out en passant, which is rare enough that it won't be missed most of the time. It's rare enough that if you use it against a casual player, there is a good chance they will accuse you of making it up. Castling, however, which is also omitted, is much more serious. Getting castled is one of the top goals of the opening. It happens in nearly every game. Taking that out is huge. Pawn promotion is missing from the older program but included in the smaller French program (making the French achievement even more impressive). I'd say that is not as big an omission as castling, because many games end before it gets to that point. Still, the threat of promotion has a major influence on endgame play. So what we actually have are very impressive implementations of chess-like games. That raises the question of what is the smallest implementation of full chess? I suspect that both these programs could be expanded to the full rules without making them a lot bigger, by taking the short cut of allowing the human to make those moves, but not the computer (especially if the computer trusts the human and does not check for legality of the human's move). I think you could defend a claim that you then have full chess, and it is just a limitation of the AI that it does not consider those moves.
- Zitrax 12y ago
  I am also curious, what is the smallest implementation of full chess ? I tried to search a bit but only found more examples that skipped some rule.
- Someone 12y ago
  "That raises the question of what is the smallest implementation of full chess?" Technically, that is a program that prints "I concede". If you also want it to play black (IIRC, this 1k chess doesn't) and validate moves, it would have to know the 20 opening moves for white and concede on black's first move. Of course, you could claim that isn't playing chess. But it is hard to define what, then, is chess. Picking a random move? Moving only one of one's knights, and conceding when it is taken? Does a program need an ELO rating of at least 1500 to be considered an implementation of 'full chess'?
  - 12y ago
DodgyEggplant 12y ago
For the record, drawing on screen was poking bytes directly to the screen memory.
jonjacky 12y ago
Also pertinent: Peter Jennings' Microchess for the 1K Kim-1. His page says it "was the first game program sold for home computers", shipped in 1976. http://www.benlo.com/microchess/ http://www.benlo.com/microchess/
- phkahler 12y ago
  Was going to bring this up. My father keyed that into his Kim-1 by hand and played it. Definitely predates the one here by several years and also fit into 1K. On a side note, I wrote one that ran on a PIC16 and fit into 4K of flash, while the part had only 176 bytes of RAM. It played over the serial port in a terminal. The 4K is not impressive, but I wrote it in C with a compiler that didn't support recursion because the stack is for return addresses only and is only 8 levels deep. IIRC I could do a 5 level minimax search on it.
- billforsternz 12y ago
  I put a bit of effort into that, basically making C macros to emulate 6502 assembly and getting the program to run on modern machines that way. Peter gives me credit on his site. I often think it would be a good idea to load up his machine code on a 6502 emulator and try to round trip confirm the accuracy of my translation, but time, as always is the enemy.
Sevzi 12y ago
Everything I write is the greatest. Anytime I write or update something, it's the new greatest. Simple!
vanderZwan 12y ago
Given that the TI-8X series of calculators run on a z80 chip, we could port this almost as-is to that little machine, right? http://en.wikipedia.org/wiki/TI-84_Plus_series http://en.wikipedia.org/wiki/TI-84_Plus_series
Supraperplex 12y ago
By the standards of the linked article I would say the greatest program is the original Elite game. A whole universe complete with star systems and 3D models for spaceships plus some other content like missions... I think the name says it: elite. All in 52 kb on disk.
- ctdonath 12y ago
  A close candidate for "greatest" indeed. Which is greater, the long-recognized summary of human intelligence in 672 bytes? or a universe in 77x the space?
- david-given 12y ago
  Having disk available is cheating --- you get to load chunks of code off disk while the game runs! Cassette Elite had to load the entire game into RAM. It had some omissions --- fewer ships, no (or fewer?) missions, no docking computer, etc. But it was completely self contained. Source, BTW, is available from Ian Bell's website: http://www.iancgbell.clara.net/elite/bbc/index.htm http://www.iancgbell.clara.net/elite/bbc/index.htm Here's an excerpt. It's machine code using BBC Basic's built in assembler as a cheapo macro assembler: 7000.SHPPT JSREE51:JSRPROJ:ORAK3+1:BNEnono:LDAK4:CMP#Y*2-2:BCSnono:LDY#2:jsrShpt:ldy#6:ldaK4:ADC#1:jsrShpt:LDA#8:ORAXX1+31:STAXX1+31:LDA#8:JMPLL81+2:PLA:PLA:.nono lda#&F7:andXX1+31:staXX1+31:RTS 7010.Shpt STA(XX19),Y:iny:iny:STA(XX19),Y:LDAK3:DEY:STA(XX19),Y:ADC#3:BCSnono-2:dey:dey:STA(XX19),Y:rts 8040.LL5 \2BSQRT Q=SQR(RQ) 8045LDYR:LDAQ:STAS:LDX#0:STXQ:LDA#8:STAT:.LL6 CPXQ:BCCLL7:BNELL8:CPY#&40:BCCLL7:.LL8 TYA:SBC#&40:TAY:TXA:SBCQ:TAX:.LL7 ROLQ:ASLS:TYA:ROLA:TAY:TXA:ROLA:TAX:ASLS:TYA:ROLA:TAY:TXA:ROLA:TAX:DECT:BNELL6:RTS 8065.LL28 \BFRDIV R=A*256/Q 8070CMPQ:BCSLL2:LDX#254:STXR:.LL31 ASLA:BCSLL29:CMPQ:BCCP%+4:SBCQ:ROLR:BCSLL31:RTS:.LL29 SBCQ:SEC:ROLR:BCSLL31:RTS:.LL2 LDA#FF:STAR:RTS 8085.LL38 \BADD(S)A=R+Q(SA) 8090EORS:BMILL39:LDAQ:CLC:ADCR:RTS:.LL39 LDAR:SEC:SBCQ 8095BCCP%+4:CLC:RTS:PHA:LDAS:EOR#128:STAS:PLA:EOR#255:ADC#1:RTS 8100.LL51 \XX12=XX15.XX16 8105LDX#0:LDY#0:.ll51 LDAXX15:STAQ:LDAXX16,X:JSRFMLTU:STAT:LDAXX15+1:EORXX16+1, X:STAS:LDAXX15+2 8115STAQ:LDAXX16+2,X:JSRFMLTU:STAQ:LDAT:STAR:LDAXX15+3 8120EORXX16+3,X:JSRLL38:STAT:LDAXX15+4:STAQ:LDAXX16+4,X:JSRFMLTU:STAQ:LDAT:STAR:LDAXX15+5:EORXX16+5,X 8130JSRLL38:STAXX12,Y:LDAS:STAXX12+1,Y:INY:INY:TXA:CLC:ADC#6:TAX:CMP#17:BCCll51:RTS
- gpvos 12y ago
desireco42 12y ago
Impressive, Elite game also comes to mind. For you who don't remember, it was a really immersive game with huge universe that can fit on a floppy drive. I remember when my friend show me proudly cd he just purchased with it, and didn't believe game is small enough to not needing it. His face was precious when he opened cd and saw how big the game was.
j2kun 12y ago
I'm not sure why the size of a program has any serious bearing on it's greatness. Sure it's an incredible feat of engineering, but shouldn't the "greatest program ever written" be primarily judged by what it allows us to do, not need to do, to build, or what insights it provides? For example, certainly the first widely used assembler was a "greater" program than any chess game, not only because it stopped us from having to track memory locations by hand, but because it allowed us to dedicate our brain cycles to actual problem solving and writing more useful programs.
- ctdonath 12y ago
  The greatness of an achievement may be in and of itself. The Mona Lisa is great purely based on its appearance, not that anything useful comes of it. The "7 Wonders of the World" are noted for their scale vs the ability of then-modern construction, not their ability to move water or house dead bodies. Great exploration often leads to laudable yet largely unproductive dead ends (Everest, Antarctica). In this case, cramming a viable AI playing the quintessential expression of human intelligence (playing chess) into less than 700 bytes is astounding, and at least a candidate for greatness. The first widely used assembler may vie for "greatest tool", but it did little of interest in and of itself.
  - j2kun 12y ago
    And yet, when you ask what is the greatest thing or idea ever created by humans, the reply is not usually any of the Wonders of the World, or the Mona Lisa, or a chess program. It is usually language or writing or something which was similarly a sea change in the development of humanity as we know it today. My argument is that these are the better criteria for "greatness" than the relative ease of performing a specific task, though that task may implicitly represent the great thing. E.g., one may call the printing press the greatest invention ever, not because it was great but because it ushered in a new age.
    - x0x0 12y ago
      And this ushered in the age of chess on your home computer :) So it was practical while simultaneously being an engineering challenge, which is what (I guess?) most of us find so appealing.
brudgers 12y ago
The other day, my son brought a discarded 3.5" floppy from PrintShop home from school. It got me thinking about the fact that 1440kb or even 720kb is more information than a person can wrap their head around unless it's dumbed down to a simply interpreted bitmap...i.e. we can interpret it with our visual cortex. 1024 bytes has 2^8192 permutations. And 3-SAT is NP-Complete.
owenversteeg 12y ago
Wow, that's amazing. I love programs written in less than a kilobyte. Personally, I developed a CSS framework that is only 995 bytes (not to compare it to this program) - http://mincss.com/ http://mincss.com/. In the same vein as this program, there's JS1k. Some of the stuff on there is also really amazing.
- TylerJay 12y ago
  > Patients that switched from Bootstrap to Min reported up to a ninefold decrease in markup hehe. Actually though, as someone who learned CSS with the rule "Use Divs! No Tables!" What does a page with less divs even look like? What are the workhorses for page layout?
  - owenversteeg 12y ago
    That rule is good. Using divs normally is fine. However, it is possible to overuse divs. Sometimes you'll have a div nested inside a div (and so on) six levels deep. That's considered bad. For example, <div id="div-holder"> <div id="inner-padding-div"> <div id="right-align-div"> <div id="centering-div"> <div id="actual-content"> is bad - you could reduce that to one or two divs at most.
    - TylerJay 12y ago
      Gotcha. Thanks!
bhz 12y ago
In homage to things like this, there are a number of 512 byte, 1k, etc. game development competitions. You can find them allover for a variety of machines. If you're interested these tiny masterpieces, you should enter a competition, or at least check them out. Years ago I made a 512 byte maze game, I put up the listing here: http://burninghorizon.com/pub/c64/tinyrinth/tinyrinth.htm http://burninghorizon.com/pub/c64/tinyrinth/tinyrinth.htm I made that page before I ever saw the article (and much later webpage) describing this 1k chess program. The article should enlighten anyone who isn't sure just how small 1k of code actually is: http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ http://users.ox.ac.uk/~uzdm0006/scans/1kchess/
jpalomaki 12y ago
A bit related: David Braben's presentation about the original Elite. http://www.gdcvault.com/play/1014628/Classic-Game-Postmortem http://www.gdcvault.com/play/1014628/Classic-Game-Postmortem
atlantic 12y ago
And here are the rules that formed the core of the AI (in case you missed them): Score provides a move score based on the following: first, the "To" position results in taking of a piece. Second, the "From" position is attacked. Third, the "To" position is attacked. Fourth, "To" enables the computer to obtain a check and finally the "From" position is defended.
stillsut 12y ago
This is the opposite of a great program. A great program scales with Moore's Law: when you get 2x memory, the program gets better, ideally more than 2x better. Human limitations remain constant through the ages, that's why climbing Mt. Everest or the 4 minute mile are so compelling. But the most basic fact about computing capacity is its (exponential) upward trend.
anjc 12y ago
A lot of the comments here are depressing, showing no appreciation of computing history or engineering challenges.
angularly 12y ago
Nice! ZX81 was my first computer. I didn't even have the tape storage. I just typed some program in from a magazine and left it on for a couple of days. I even got the Lampda 16K memory expansion, which was a big external module mounted on the back :)
ddorian43 12y ago
See kkrieger. 96KB doom3-like fps-demo

380 points by jermo 12y ago

Why does the author say "memory" when he means "disk space"? Or does he actually mean "memory", as in "RAM"? In that case, why would the size of the executable matter?

ctdonath 12y ago
There was no "disk" on a ZX81. Storage was audio cassette tape. The size of the executable mattered because it all had to fit in 1024 bytes RAM (no "K", no "M", certainly no "G") with all video & operating system memory.
- StavrosK 12y ago
  Oh wow, I didn't know that, thanks. By the way, to whomever downvoted a legitimate question: Nice.
  - ColinWright 12y ago
    I didn't downvote you, but you asked a question the answer to which is easily available with the most trivial of web searches. You assumed he meant "disk space", assuming the author made a mistake when you could easily have checked and not asked the question here. In some sense, it's not a legitimate question for this context.
    - angersock 12y ago
      The question asked exactly is the sort of thing that "the most trivial of web searches" wouldn't have answered as well as either of the replies already up. One reply puts it into historical context, and educates the reader about the memory/persistence model of the ZX81. The other reply points out that the lack of virtual memory and whatnot means that, in previous times, you needed to have the entire thing loaded into memory to execute something. Without some digging and a knowledge of what to look for, those are non-obvious but useful points.
      - TheOtherHobbes 12y ago
        Well - you could just search for "ZX81". First thing that appears is a Wikipedia article which explains how the memory and off-line storage worked. So I don't think finding this out would have been rocket science. Having said that, and having written my first code on a ZX81 (if you don't count an even older TI programmable calculator with even less RAM) I'm old enough to be amused by the question. :) However you slice it, chess in 1K was awesome coding.
    - nsxwolf 12y ago
      Must we obtain all information via dry web searches, and never from human exchange?
      - sago 12y ago
        Well, this is the site where, in an article about "the 36 questions it takes to fall in love" someone suggested building a bot so you could go through the questions on your own.
    - ctdonath 12y ago
      Thing is, this context is way out of the norm for a great many HN readers. The notion of a general-purpose home computer without rapid-access storage, and hence without virtual memory, is so foreign to the younger crowd that the question is fair and the answer is almost unbelievable in their experience. There's nothing to prompt a web search, as what's being searched for is at odds with axiomatic presumptions.
    - metaphorm 12y ago
      its a 100% legitimate question. it was asked in good faith because the person asking it didn't know and wanted to know. its not a trivial web search either, because even knowing what to google for requires contextual knowledge that OP didn't have. punishing a person for being ignorant while they are trying to learn and become less ignorant is terrible behavior.
- jameshart 12y ago
  "Operating System" is a stretch. BIOS would even be an overelaborate term for what the ZX81 had, given that IO was basically handled through fixed memory-mapping. What it had was a few inbuilt ROM routines and a main run loop that cobbled together a text-mode display, a line editor and a basic interpreter.
deleted 12y ago
[deleted]
pyrois 12y ago
"Memory" means RAM, here. As for why the size of the executable matters, you needed to have the entire executable in RAM before you could actually execute it. That's not so true these days, but it was back in the good ol' days* when you hooked tape cassettes up as your external storage. * Get off my lawn!

ctdonath 12y ago

TL;DR - chess, in 1K RAM including video and OS memory space.

tibbon 12y ago

Link to the code: http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ http://users.ox.ac.uk/~uzdm0006/scans/1kchess/

luma 12y ago

If you can't castle, you can't promote a pawn, and you can't en passant, it isn't chess.

pyrois 12y ago
True, but even "Chess lite" in 672 bytes is mind-blowing.
pavel_lishin 12y ago
You are welcome to add these things; we'll give you a generous extra 100 bytes.
- bsaul 12y ago
  Wonder if any student somewhere isn't trying to take up the challenge of adding castling to the code, using an emulator. I like to think that's something i would try to do as a student, because i'm pretty sure there's a tremendous amount of skill to gain by doing it.

3327 12y ago

Holy smokes... blown away. 1K RAM? less then most email's we write... Now'a days rockstars and Ninja's are the glorified ruby guys who "seemingly" do Ruby/django magic... This is what counts...This is the real deal...

pfortuny 12y ago
Now you only have less than 800 bytes left. And counting.
stpe 12y ago
On this topic, check what was done (and still is, to some extent on the homebrew scene) on the Atari 2600 with 128 bytes of RAM and no framebuffer.
- JonathonW 12y ago
  Of course, the Atari (unlike the Sinclair in the OP) executed code directly from the cartridge-- you didn't have to fit your whole program into that 128 bytes of RAM. Atari cartridges could be up to 4kB, or 32kB with bank switching, which is downright roomy for the era.
moron4hire 12y ago
Weeeell... The entire point of computers is to be able to do work that would be too tedious for humans. Computers exist so people can be lazy. Making better programming languages so programmers can be lazy is kind of the whole point of the job.
- blowski 12y ago
  Exactly. For many, many projects nowadays, the project does not require a 1024 executable because RAM is cheap. Making code that's really easy to work with is just as impressive as this.
- sago 12y ago
  The entire point of computers is to be able to do work that would be too tedious for humans. Really? News to me. Like the entire point of cars is to take you on journeys that would be too tedious to walk?

samatman 12y ago

Thanks to the Archive, the code and commentary is available: https://archive.org/stream/your-computer-magazine-1982-12/YourComputer_1982_12#page/n67/mode/2up https://archive.org/stream/your-computer-magazine-1982-12/Yo... https://archive.org/stream/your-computer-magazine-1983-01/YourComputer_1983_01#page/n79/mode/2up https://archive.org/stream/your-computer-magazine-1983-01/Yo...

Doctor_Fegg 12y ago
Oh, wow: there are issues of Your Computer on archive.org. Thanks. I loved that magazine.
- didgeoridoo 12y ago
  There was a great interview on The Web Ahead recently with Jason Scott about Archive.org and the challenge of preserving these amazing bits of history: http://5by5.tv/webahead/97 http://5by5.tv/webahead/97

GregBuchholz 12y ago

Olivier Poudade has recently written and even smaller version of the chess program, clocking in at 468 bytes: http://olivier.poudade.free.fr/ http://olivier.poudade.free.fr/ http://www.bbc.com/news/technology-31028787 http://www.bbc.com/news/technology-31028787

ctdonath 12y ago
Prior HN discussion: https://news.ycombinator.com/item?id=8954630 https://news.ycombinator.com/item?id=8954630

VonGuard 12y ago

Just for the record, the Atari 2600 also had a chess game with AI. It also had only 1024 bits of RAM, but it had access to all of it because there was no OS or underlying hardware support, like in the Speccy. So while this is definitely amazing, the 2600 version is very close in the "insanely well coded" category, especially because the 2600 had some SERIOUSLY quirky hardware to deal with. For example, on the 2600, you could only draw half the screen's background: the other side had to be a mirror image. Additionally, the columns of pixels that you drew on the screen were enumerated, to the halfway point on the screen as follows: 12345678,87654321,1234 So you were drawing forward, backward, then forward again, and that only got you half the screen!

ymra 12y ago
It may only have had 128 Bytes of RAM, but it used 4K ROM cartridges, even more than that if the cartridge used bank switching. So Atari 2600 programmes had quite a bit more room to fit inside.
- mgkimsal 12y ago
  IIRC, early cartridges only had 1 or 2k - the 4k was a limit for a while, but I don't think they all shipped with 4k in the beginning (cost savings). IIRC there was a trick later to allow for 8k cartridges (Pitfall II was 8k, I think, but memory may be failing me).
  - wazoox 12y ago
    IIRC, Pitfall II was 2K. 255 different levels in 2K, memorable isn't it ? :)
tragomaskhalos 12y ago
I read that chess was originally considered impossible to implement on the 2600, but there were promotional materials showing a guy playing chess on it and a customer complained that it wasn't available, so Atari went ahead and wrote it. The graphics were horrible but the AI was actually pretty good, so we just used to set up a real board and mirror the moves on that.

illsorted 12y ago

Original source: http://www.kuro5hin.org/story/2001/8/10/12620/2164 http://www.kuro5hin.org/story/2001/8/10/12620/2164

SwellJoe 12y ago
Whoah, I'd almost completely forgotten Kuro5hin, and a lot of other people obviously have, too, as the site is a ghost town. It was a really neat pre-reddit user-generated social media site; kind of a more democratic Slashdot. I knew the founder in some capacity (I don't even remember how/why, now, or their name...maybe because I worked on Squid or because I worked in Perl), and used to advertise my old company on Kuro5hin to be able to send some money their way. I quite liked it, and there was a brief time when I divided my time between Slashdot and Kuro5hin, as I currently divide my time between reddit and HN.
- bokchoi 12y ago
  My favorite Kuro5hin article is the intro to the K language: https://www.kuro5hin.org/story/2002/11/14/22741/791 https://www.kuro5hin.org/story/2002/11/14/22741/791
  - Rodeoclash 12y ago
    Mine was the Casino story: http://www.kuro5hin.org/story/2001/7/19/181127/355 http://www.kuro5hin.org/story/2001/7/19/181127/355 Almost 15 years ago now yet I still remember it. That was Kuro5hin at its peak.

Fastidious 12y ago

Does anyone have a link to find out more about David Horne?

Sevzi 12y ago
Why? I hear Fastidious produces better code, faster, and without errors.

shubhamjain 12y ago

Amazing! it is hard to imagine to even barely scratch the surface with constraints like that. Sinclair ZX81 does seem to have an emulator[1], would it be possible to see it run? It seems the emulator would need a assembled binary, something I am not sure would be possible without whole lot of grunt work. [1]: http://www.chuntey.com/ http://www.chuntey.com/

smoyer 12y ago

I have that program! The cassette it came on is still in my basement (along with a couple of ZX-81s and TS-2000s). While it might be rudimentary AI, I also didn't beat it every time (maybe not even half the time when I started playing against it).

pmontra 12y ago
I believed to have it too but I checked and I've got the Chess program from PSION instead, which is for the 16kB ZX81. I remember that I lost every single game. I keep it on the old CDs bookshelf, with a cassette of Defender. They're maybe the last two tapes left from those years. The ZX81 is somewhere at my parents house. I also kept the BASIC Programming Manual. I develop with Ruby and JS now, probably no less than 16 MB for any program I run :-)

brownbat 12y ago

Olivier Poudade's BootChess claims to be the new record holder, 487-bytes of assembly: http://mashable.com/2015/01/30/play-it-better-tiny-chess-game/ http://mashable.com/2015/01/30/play-it-better-tiny-chess-gam...

ctdonath 12y ago
Now if someone could arrange a competition between the two...

henrik_w 12y ago

Kevlin Henney mentions this program in his talk "Cool Code". The whole talk is really worth watching. http://www.infoq.com/presentations/Cool-Code http://www.infoq.com/presentations/Cool-Code

tzs 12y ago

Impressive, as is the recent smaller program from a French programmer. Note, however, that both have sacrificed some rules. I believe they have both left out en passant, which is rare enough that it won't be missed most of the time. It's rare enough that if you use it against a casual player, there is a good chance they will accuse you of making it up. Castling, however, which is also omitted, is much more serious. Getting castled is one of the top goals of the opening. It happens in nearly every game. Taking that out is huge. Pawn promotion is missing from the older program but included in the smaller French program (making the French achievement even more impressive). I'd say that is not as big an omission as castling, because many games end before it gets to that point. Still, the threat of promotion has a major influence on endgame play. So what we actually have are very impressive implementations of chess-like games. That raises the question of what is the smallest implementation of full chess? I suspect that both these programs could be expanded to the full rules without making them a lot bigger, by taking the short cut of allowing the human to make those moves, but not the computer (especially if the computer trusts the human and does not check for legality of the human's move). I think you could defend a claim that you then have full chess, and it is just a limitation of the AI that it does not consider those moves.

Zitrax 12y ago
I am also curious, what is the smallest implementation of full chess ? I tried to search a bit but only found more examples that skipped some rule.
Someone 12y ago
"That raises the question of what is the smallest implementation of full chess?" Technically, that is a program that prints "I concede". If you also want it to play black (IIRC, this 1k chess doesn't) and validate moves, it would have to know the 20 opening moves for white and concede on black's first move. Of course, you could claim that isn't playing chess. But it is hard to define what, then, is chess. Picking a random move? Moving only one of one's knights, and conceding when it is taken? Does a program need an ELO rating of at least 1500 to be considered an implementation of 'full chess'?
- 12y ago

DodgyEggplant 12y ago

For the record, drawing on screen was poking bytes directly to the screen memory.

jonjacky 12y ago

Also pertinent: Peter Jennings' Microchess for the 1K Kim-1. His page says it "was the first game program sold for home computers", shipped in 1976. http://www.benlo.com/microchess/ http://www.benlo.com/microchess/

phkahler 12y ago
Was going to bring this up. My father keyed that into his Kim-1 by hand and played it. Definitely predates the one here by several years and also fit into 1K. On a side note, I wrote one that ran on a PIC16 and fit into 4K of flash, while the part had only 176 bytes of RAM. It played over the serial port in a terminal. The 4K is not impressive, but I wrote it in C with a compiler that didn't support recursion because the stack is for return addresses only and is only 8 levels deep. IIRC I could do a 5 level minimax search on it.
billforsternz 12y ago
I put a bit of effort into that, basically making C macros to emulate 6502 assembly and getting the program to run on modern machines that way. Peter gives me credit on his site. I often think it would be a good idea to load up his machine code on a 6502 emulator and try to round trip confirm the accuracy of my translation, but time, as always is the enemy.

Sevzi 12y ago

Everything I write is the greatest. Anytime I write or update something, it's the new greatest. Simple!

vanderZwan 12y ago

Given that the TI-8X series of calculators run on a z80 chip, we could port this almost as-is to that little machine, right? http://en.wikipedia.org/wiki/TI-84_Plus_series http://en.wikipedia.org/wiki/TI-84_Plus_series

Supraperplex 12y ago

By the standards of the linked article I would say the greatest program is the original Elite game. A whole universe complete with star systems and 3D models for spaceships plus some other content like missions... I think the name says it: elite. All in 52 kb on disk.

ctdonath 12y ago
A close candidate for "greatest" indeed. Which is greater, the long-recognized summary of human intelligence in 672 bytes? or a universe in 77x the space?
david-given 12y ago
Having disk available is cheating --- you get to load chunks of code off disk while the game runs! Cassette Elite had to load the entire game into RAM. It had some omissions --- fewer ships, no (or fewer?) missions, no docking computer, etc. But it was completely self contained. Source, BTW, is available from Ian Bell's website: http://www.iancgbell.clara.net/elite/bbc/index.htm http://www.iancgbell.clara.net/elite/bbc/index.htm Here's an excerpt. It's machine code using BBC Basic's built in assembler as a cheapo macro assembler: 7000.SHPPT JSREE51:JSRPROJ:ORAK3+1:BNEnono:LDAK4:CMP#Y*2-2:BCSnono:LDY#2:jsrShpt:ldy#6:ldaK4:ADC#1:jsrShpt:LDA#8:ORAXX1+31:STAXX1+31:LDA#8:JMPLL81+2:PLA:PLA:.nono lda#&F7:andXX1+31:staXX1+31:RTS 7010.Shpt STA(XX19),Y:iny:iny:STA(XX19),Y:LDAK3:DEY:STA(XX19),Y:ADC#3:BCSnono-2:dey:dey:STA(XX19),Y:rts 8040.LL5 \2BSQRT Q=SQR(RQ) 8045LDYR:LDAQ:STAS:LDX#0:STXQ:LDA#8:STAT:.LL6 CPXQ:BCCLL7:BNELL8:CPY#&40:BCCLL7:.LL8 TYA:SBC#&40:TAY:TXA:SBCQ:TAX:.LL7 ROLQ:ASLS:TYA:ROLA:TAY:TXA:ROLA:TAX:ASLS:TYA:ROLA:TAY:TXA:ROLA:TAX:DECT:BNELL6:RTS 8065.LL28 \BFRDIV R=A*256/Q 8070CMPQ:BCSLL2:LDX#254:STXR:.LL31 ASLA:BCSLL29:CMPQ:BCCP%+4:SBCQ:ROLR:BCSLL31:RTS:.LL29 SBCQ:SEC:ROLR:BCSLL31:RTS:.LL2 LDA#FF:STAR:RTS 8085.LL38 \BADD(S)A=R+Q(SA) 8090EORS:BMILL39:LDAQ:CLC:ADCR:RTS:.LL39 LDAR:SEC:SBCQ 8095BCCP%+4:CLC:RTS:PHA:LDAS:EOR#128:STAS:PLA:EOR#255:ADC#1:RTS 8100.LL51 \XX12=XX15.XX16 8105LDX#0:LDY#0:.ll51 LDAXX15:STAQ:LDAXX16,X:JSRFMLTU:STAT:LDAXX15+1:EORXX16+1, X:STAS:LDAXX15+2 8115STAQ:LDAXX16+2,X:JSRFMLTU:STAQ:LDAT:STAR:LDAXX15+3 8120EORXX16+3,X:JSRLL38:STAT:LDAXX15+4:STAQ:LDAXX16+4,X:JSRFMLTU:STAQ:LDAT:STAR:LDAXX15+5:EORXX16+5,X 8130JSRLL38:STAXX12,Y:LDAS:STAXX12+1,Y:INY:INY:TXA:CLC:ADC#6:TAX:CMP#17:BCCll51:RTS
gpvos 12y ago

desireco42 12y ago

Impressive, Elite game also comes to mind. For you who don't remember, it was a really immersive game with huge universe that can fit on a floppy drive. I remember when my friend show me proudly cd he just purchased with it, and didn't believe game is small enough to not needing it. His face was precious when he opened cd and saw how big the game was.

j2kun 12y ago

I'm not sure why the size of a program has any serious bearing on it's greatness. Sure it's an incredible feat of engineering, but shouldn't the "greatest program ever written" be primarily judged by what it allows us to do, not need to do, to build, or what insights it provides? For example, certainly the first widely used assembler was a "greater" program than any chess game, not only because it stopped us from having to track memory locations by hand, but because it allowed us to dedicate our brain cycles to actual problem solving and writing more useful programs.

ctdonath 12y ago
The greatness of an achievement may be in and of itself. The Mona Lisa is great purely based on its appearance, not that anything useful comes of it. The "7 Wonders of the World" are noted for their scale vs the ability of then-modern construction, not their ability to move water or house dead bodies. Great exploration often leads to laudable yet largely unproductive dead ends (Everest, Antarctica). In this case, cramming a viable AI playing the quintessential expression of human intelligence (playing chess) into less than 700 bytes is astounding, and at least a candidate for greatness. The first widely used assembler may vie for "greatest tool", but it did little of interest in and of itself.
- j2kun 12y ago
  And yet, when you ask what is the greatest thing or idea ever created by humans, the reply is not usually any of the Wonders of the World, or the Mona Lisa, or a chess program. It is usually language or writing or something which was similarly a sea change in the development of humanity as we know it today. My argument is that these are the better criteria for "greatness" than the relative ease of performing a specific task, though that task may implicitly represent the great thing. E.g., one may call the printing press the greatest invention ever, not because it was great but because it ushered in a new age.
  - x0x0 12y ago
    And this ushered in the age of chess on your home computer :) So it was practical while simultaneously being an engineering challenge, which is what (I guess?) most of us find so appealing.

brudgers 12y ago

The other day, my son brought a discarded 3.5" floppy from PrintShop home from school. It got me thinking about the fact that 1440kb or even 720kb is more information than a person can wrap their head around unless it's dumbed down to a simply interpreted bitmap...i.e. we can interpret it with our visual cortex. 1024 bytes has 2^8192 permutations. And 3-SAT is NP-Complete.

owenversteeg 12y ago

Wow, that's amazing. I love programs written in less than a kilobyte. Personally, I developed a CSS framework that is only 995 bytes (not to compare it to this program) - http://mincss.com/ http://mincss.com/. In the same vein as this program, there's JS1k. Some of the stuff on there is also really amazing.

TylerJay 12y ago
> Patients that switched from Bootstrap to Min reported up to a ninefold decrease in markup hehe. Actually though, as someone who learned CSS with the rule "Use Divs! No Tables!" What does a page with less divs even look like? What are the workhorses for page layout?
- owenversteeg 12y ago
  That rule is good. Using divs normally is fine. However, it is possible to overuse divs. Sometimes you'll have a div nested inside a div (and so on) six levels deep. That's considered bad. For example, <div id="div-holder"> <div id="inner-padding-div"> <div id="right-align-div"> <div id="centering-div"> <div id="actual-content"> is bad - you could reduce that to one or two divs at most.
  - TylerJay 12y ago
    Gotcha. Thanks!

bhz 12y ago

In homage to things like this, there are a number of 512 byte, 1k, etc. game development competitions. You can find them allover for a variety of machines. If you're interested these tiny masterpieces, you should enter a competition, or at least check them out. Years ago I made a 512 byte maze game, I put up the listing here: http://burninghorizon.com/pub/c64/tinyrinth/tinyrinth.htm http://burninghorizon.com/pub/c64/tinyrinth/tinyrinth.htm I made that page before I ever saw the article (and much later webpage) describing this 1k chess program. The article should enlighten anyone who isn't sure just how small 1k of code actually is: http://users.ox.ac.uk/~uzdm0006/scans/1kchess/ http://users.ox.ac.uk/~uzdm0006/scans/1kchess/

jpalomaki 12y ago

A bit related: David Braben's presentation about the original Elite. http://www.gdcvault.com/play/1014628/Classic-Game-Postmortem http://www.gdcvault.com/play/1014628/Classic-Game-Postmortem

atlantic 12y ago

And here are the rules that formed the core of the AI (in case you missed them): Score provides a move score based on the following: first, the "To" position results in taking of a piece. Second, the "From" position is attacked. Third, the "To" position is attacked. Fourth, "To" enables the computer to obtain a check and finally the "From" position is defended.

stillsut 12y ago

This is the opposite of a great program. A great program scales with Moore's Law: when you get 2x memory, the program gets better, ideally more than 2x better. Human limitations remain constant through the ages, that's why climbing Mt. Everest or the 4 minute mile are so compelling. But the most basic fact about computing capacity is its (exponential) upward trend.

anjc 12y ago

A lot of the comments here are depressing, showing no appreciation of computing history or engineering challenges.

angularly 12y ago

Nice! ZX81 was my first computer. I didn't even have the tape storage. I just typed some program in from a magazine and left it on for a couple of days. I even got the Lampda 16K memory expansion, which was a big external module mounted on the back :)

ddorian43 12y ago

See kkrieger. 96KB doom3-like fps-demo