David Horne's 1K Chess on the ZX81 (2001)
thad.frogley.info
thad.frogley.info
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.
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'?
And, but the way, "all the rules" can get quite complex if you consider the 50 move rule and draws by repeated positions, even more so if you pick a rule set from a time when the 50 move rule allowed for exceptions (http://en.m.wikipedia.org/wiki/Fifty-move_rule#History)
ZX81 chess was so impressive because it was impossible (at least, I'd have bet real money on it). It was the thing programmers namechecked as the kind of thing you couldn't do on these newfangled cheap home computers. You need a 'real' computer to do it. There's just no way. I was writing programs for the ZX81, and the kind of simplicity they had to have is difficult to communicate to someone who grew up with 8086 PCs on their desks. Get an emulator and have a go.
So, you're right, it wasn't 100% total, complete, full chess. But, good god, it was chess, recognizably chess, playably chess! And the guy did it on a freakin' ZX81. It is difficult to explain how astounding that was.
Pointing out it's lack of castling and en-passant (and stalemate, repetition, etc) seems a bit churlish then.
That's why the challenge for the smallest chess program uses the ZX81 rules, not the full rules. It is why smaller programs make it to HN, whereas you don't know about the smallest program to play FIDE chess. It is a historical honoring of that great achievement.
http://uknet.com/gallery2/d/16341-2/076_Sinclair_ZX81_Manual...
(Paintings by John Harris. He sells prints! http://www.alisoneldred.com/thumbsJohnHarris-Prints-3-1.html)
However, you will be frustrated with the ZX81; the built in BASIC was utterly appalling and also didn't have a tokeniser --- instead each key (plus modifiers) produced a different keyword. And it was stateful, so the keys did different things depending on what you were typing. This made typing on it horribly frustrating even when you had the keywords written on the keyboard, which you won't have with an emulator.
It may be of interest to check out the Jupiter Ace --- it's basically the same machine, made by some ex-Sinclair staff, except running Forth instead of Basic; you can at least type on that, and using Forth means you're much closer to the machine. (Plus, Sinclair's Basic was seriously horrifying. Any alternative is better.) There's a bunch of emulators. But it's a much more esoteric machine, so there'll be very limited resources around.
There are Javascript emulators for all the above, but they're pretty naff.
So:
10 LET I = 10
20 LET I = I + 1
30 GOTO 10
The program counter would point at the start of line 10; the interpreter would see LET (mandatory in Sinclair Basic) and know a variable name was next; it'd read that; it'd read the equals sign; then it would read the expression and evaluate it on the fly. Then the program counter would be pointing at the end of line 10, so it just advances over the line number, and it's ready for line 20. etc, etc.
Line 30 would read the GOTO, then read the line number, then reset the program counter to the beginning of the program and scan through looking at line number headers until it found the right one. Yes, O(n). Yes, you put most used subroutines at the beginning of the program for speed.
So the entire run-time state is a program counter, a couple of fixed-size stacks for FOR...NEXT and GOSUB...RETURN, and your variables. I've no idea how Sinclair Basic stored them, but BBC Basic used a hash table that was immediately after the end of your program. Strings were a problem because they could change size; Commodore Basic had the world's slowest garbage collector. BBC Basic just fragmented and ran out of space. I don't know how Sinclair Basic handled it.
If you're interested, the entire ROM is disassembled here: http://www.wearmouth.demon.co.uk/zx81.htm
That's amazing. Why am I so blind?
I expected that Sinclair Basic would have a rule that variable names have one significant character, and reserved space for 26 integers A% through Z%, 26 strings A$ through Z$, and forget about floating point, but reading http://www.worldofspectrum.org/ZX81BasicProgramming/chap06.h..., that isn't true; this language even allowed spaces in identifiers.
At the same time, we have (same link):
"You will get a report 2/0, & looking up 2 in appendix B, you will see that it means 'variable not found',
So. This enormous 8kB ROM wasn't large enough to hold error messages.
And, reading http://www.cs.columbia.edu/~%20sedwards/classes/2006/w4115-f..., it seems that loop and stir g variables had to be single-letter (yes, your program had at most 26 strings. Not that much of a limit if you have a few hundred bytes of RAM for your program and your data)
That PDF also gives some more limitations of the language, claiming that it wouldn't do complex expressions such as
10 let a = 2 * a + 1http://www.worldofspectrum.org/ZX81BasicProgramming/chap27.h...
...wow. The framebuffer is between the program and the variables? And as the program changes size, and the screen changes size, it relocates everything above there? No wonder editing lines in a big program is so slow...
Also, that mention of the calculator stack? That's used by an embedded Forth-like language used to do floating point operations; which is why Sinclair Basic's trig functions are so appalling.
Agree with that. The syntax check while you typed programs would break your concentration. Still have my first machine in it's foam box, a zx80 with ROM upgrade.
https://www.flickr.com/photos/bootload/tags/zx81
And thank you David for pointing out the John Harris prints, what a bonus.
Sounds like a good argument for a software keyboard. Might make a good touchscreen app.
Nope.
http://globalnerdy.com/wordpress/wp-content/uploads/2007/09/...
I think I shall resort to a strictly pedantic definition of the word 'best' here.
When I first read the Jargon File in '96 or so, I remember being uncharacteristically annoyed by its terse, dismissive attitude towards affordable home computers ("bitty boxes"). That particular sort of elitism seemed very much at odds with the challenge-loving, egalitarian hacker spirit that the rest of the document extols. One could argue that ESR was just faithfully documenting the usage at the time, but he frequently editorializes in other entries; I think one can assume that he didn't disagree, which was a bit disappointing.
He also 'cheats' a bit by keeping part of the program on tape and never loading it into memory so it doesn't count toward the 672 byte limit. That's a good trick that I wouldn't have thought to do with display code.
I'm missing something here, but if something is never loaded in the memory, why should be counted? Why do you consider that a part of the program at all?
Can you please also provide more technical details, since I don't understand what you mean?
http://en.wikipedia.org/wiki/ZX81
24 lines of 32 characters. 768 bytes usually cleared and scrolled away as you type. The user just has to load the cassette and play. Even if the program was developed on the Cray (it was not) everything needed for the program to run is less than 1K. Please explain your sentence "If you count resources that are necessary to make the program run, however, you'd use a different metric."
See the proof:
https://archive.org/stream/popular-computing-weekly-1982-07-...
"The tape loads every time, without problems, in about 30 seconds." The cassette speed of ZX 81 was 250 bits per second, 30 seconds is less than 1 KB, and the sync header (the bits that don't carry the program) were certainly also counted in the given 30 seconds by the reviewer.
No, it was designed to use up to 793 bytes (those 768 plus one byte for every line plus, it seems, one extra 'end of screen' byte) for the screen buffer. If you didn't write stuff, the size of the screen buffer was way smaller, down to 25 bytes for an empty screen (http://problemkaputt.de/zxdocs.htm#zx80zx81videomodetextandb...)
Also note that the main CPU drew the video from an interrupt handler. That's why one had fast and slow mode; fast mode disabled that interrupt, speeding up your program, but losing the screen display. I think it also means that one should interpret the expression 'halt instruction' as used in the description of the contents of video memory literally.
I also found this nugget in a disassembly listing:
"and although each interrupt interrupts the previous one, there are no stack problems as the 'return address' is discarded each time."
Estimates of information density for English are as low as 1.5 bits per character, giving 272 bytes in that comment.
The information density in machine code isn't 1 bits per bit though, because of the distribution of which opcodes are used, so the 672 would also drop.
So I think the analogy is a pretty good one, whether exact or not, some of the comments on this page contain more information than ZX81 chess.
Can you expand on that?
At that limit, the size of the compressed data has one bit per bit of information.
So, scaling back up, the estimate is (and it has to be an estimate, I guess, since we can't construct the actual theoretically smallest encoding) 1.5 bits of information per character.
I searched for this value, and didn't spend long figuring out if it was well calculated, so take it with a big googly pinch of salt.
134 bytes, not compressed. Did I miss anything?
A legitimate and interesting question is what is the smallest possible chess implementation in a particular instruction set architecture such as x86.
A comparable example is writing quines (a program that outputs its own source code without reading itself from a file). It is a badge of honour to write the shortest quine in a particular programming language but comparing the length of a python quine implementation to a Java implementation is pretty meaningless.
Ah, but, for instance, what if the only remaining move for the AI was to use the en passant rule, for instance? By not invoking the rule, the AI would not be playing chess by the book.
In terms of source code, probably Toledo Nanochess:
http://en.wikipedia.org/wiki/Toledo_Nanochess
However, that ~1k of source becomes closer to ~2.5k of binary (x86, Windows 32-bit.)
https://archive.org/stream/your-computer-magazine-1982-12/Yo... https://archive.org/stream/your-computer-magazine-1983-01/Yo...
12345678,87654321,1234
So you were drawing forward, backward, then forward again, and that only got you half the screen!
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.
The order isn't exactly what you wrote, it's bits 4567 / 76543210 / 01234567 for the three playfield registers for the left half of the screen. This can be either repeated or mirrored for the right half. A common trick as 2600 Video Chess did was to simply not use the leftmost (mirrored to rightmost) register, which still gets you 16x2 bits of mirrored playfield in the middle, trading computational cost for a slightly smaller play area.
Now an 8x8 checkered board is not symmetrical for mirroring. 2600 Video Chess actually draws only 7 of the files with the mirrored playfield registers, with the center one of the 7 (the 'e' file) straddling the mirror line. The additional (leftmost) file is actually a sprite object (the "ball"). Pretty clever.
The real trick in 2600 Video Chess is drawing 8 sprites per row on a system whose hardware only has 6. It does this with the "venetian blinds" trick, where each sprite is striped onto alternating scanlines. That way there's only ever 4 actual sprites at a time, which are moved back and forth by a square's-width on alternating lines.
http://www.vgmaps.com/Atlas/Atari2600/Adventure-Variation2.p...
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.
By the way, to whomever downvoted a legitimate question: Nice.
In some sense, it's not a legitimate question for this context.
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.
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.
punishing a person for being ignorant while they are trying to learn and become less ignorant is terrible behavior.
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!
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.
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.
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.
Therefore, for a chess enthusiast of 1981-1982, this program was groundbreaking. You could actually get a computer to play against you.
(Personally, I did not have ZX81 but I got ZX Spectrum. I had to mow a lot of lawn and dig some graves at the local cemetery to get the money for a 16K Speccie.)
That's a really good point I guess. Maybe if I was a bit older I would be much more amazed by the feat.
Take for instance the 48K ZX Spectrum: it had 16K ROM from 0000H to 3FFFH, then 16K RAM (some of which was display buffer) from 4000H to 7FFFH made of eight 16 kbit chips, and the remaining 32K RAM from 8000H to FFFFH was actually made of eight faulty 64kbit chips which Sinclair could buy cheaply. The chips that had failed in manufacturing testing were just tested again to determine whether the faulty part in the chip was in upper or lower half of the 64kbit address range. The high address bit of memory chip was connected permanently high or low to keep the address pointing to a working half of chips, thus enabling the extremely cheap broken 64kbit chips to be used as valid 32kbit chips.
(All eight chips of memory of course had to have be broken in the same upper/lower configuration).
The Psion chess program for Spectrum needed the 48K RAM model, although I think someone also wrote a full chess program for the 16K model (including castling, en passant and all).
Psion, by the way, was publisher for much of the early software for ZX Spectrum, including chess, spreadsheet and 3D design programs. Later on it was known for handheld devices, as well as the EPOC system which later on was to become Symbian, used in Nokia smartphones.
Better analogy in context of this thread that is
He meant the "movie budget" could be arbitrary chosen to satisfy the "feat under huge constraints".
Impressive but not necessarily deserving of the monicker: "best ever".
Right, which is exactly why that isn't a good analogy to something where the budget was fixed, and the 'greatness' isn't an aesthetic judgement, but whether it can be done.
The greatness of a movie is not measured by its budget, nor is the greatness of a program measured by its number of lines or memory footprint.
Do you see now why your analogy is not as good?
Maybe making an oscar winning movie with great CGI on $1000 is more appropriate
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.
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.
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.
Almost 15 years ago now yet I still remember it. That was Kuro5hin at its peak.
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.
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
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:RTSIn the same vein as this program, there's JS1k. Some of the stuff on there is also really amazing.
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?
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.
Years ago I made a 512 byte maze game, I put up the listing here: 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/
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.
Really? News to me.
Like the entire point of cars is to take you on journeys that would be too tedious to walk?
If you're ever in Bletchley Park in the United Kingdom, go visit the National Museum of Computing. They'll show you (and you'll get to play with) the Harwell Witch, a decimal computer designed to compete with humans who are using mechanical hand-cranked calculators:
http://www.tnmoc.org/special-projects/harwell-dekatron-witch
A well-trained human can actually outperform the Witch; for twenty minutes. (They tried it.) But the Witch doesn't make mistakes and it doesn't get tired.
It was only much later that they realised that computers could do things which humans weren't _able_ to do.
That the first computers were used that way, I don't doubt. But not the same thing, I'd say. The first cars were horseless carriages.
I was responding to a point above that seemed to imply that code like this can't be considered great (or at least, no greater than a Rails website), because its not what computers are for. They are for calculating things humans can't. I disagree with that. And not on a pedantic, language level. It is a genuine confusion, i think, between why something was made and what it can do.
Though on re-reading, I may have misinterpreted the OP.
why you're using this as an excuse to take cheap shots at web developers is beyond me.
If the ZX81 hadn't done anything of interest it wouldn't have persuaded those people that awesome programming was possible.
Dismissing this kind of coding as a side show is arrogant and ill-informed.
The ZX81 itself was a similar project that squeezed maximum usefulness and affordability out of very limited resources.
IMO this illustrates the difference between engineers and hacks. Hacks are pleased when code sort-of works. Engineers are only satisfied with designs that are minimal, elegant, and use resources as efficiently as possible.
This actually matters. Efficient coding influences everything from battery life to mobile data costs to cloud fees to data centre profitability.
Sure, it's easy to ignore. It's just not very professional.
I didn't dismiss it as a sideshow. My exact words were "low importance side project". It was a side project, as in, not the code he was working on full time for his business. It was low importance, because it was just a chess game, not a piece of system software or a business application or anything else that mattered materially.
Its possible to admire the skill and craft of a low importance side project and its author, and to be inspired by that skill and craft, and yet still acknowledge that it was a low importance side project.
When you slander me by accusing me of being arrogant and ill-informed you reveal your true character. You don't know me at all. You're eager to falsely attribute beliefs to me that I don't have and you're eager to criticize me for things I have not even said. You should probably take some time to consider why you feel the need to do this. Its pretty obscene.
http://www.gdcvault.com/play/1014628/Classic-Game-Postmortem
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.
1024 bytes has 2^8192 permutations. And 3-SAT is NP-Complete.
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.