6 ms·
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 e
by 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 agoI 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'?
- astine 12y agoThe idea is that you have to actually implement all of the rules, even if your AI never invokes them. The game in this article for example, was originally designed as a two player game. If you can swap out the AI for a second human player and still play a correct game of chess, then you have 'full chess' now matter how bad the AI is.
- Someone 12y agoI know, but would a program that implements all the rules, but plays lousy, qualify? If so, it seems more reasonable to ask people to write a language checker (does this series of moves constitute a valid chess game?) than a chess playing program, as, of example, it seems one should prefer a program that plays a lousy game of chess but never castles itself over one that plays an incredibly lousy game but actively uses all the rules. 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 http://en.m.wikipedia.org/wiki/Fifty-move_rule#History)
- sago 12y agoThere's a rather ahistoric perspective at work here. I wonder if there's a generational thing. 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.
- david-given 12y agoI strongly recommend playing with this sort of machine. It's an utter education. It will, literally, change the way you think about programming. Also, the ZX81 had the best cover art for any programming manual EVER: http://uknet.com/gallery2/d/16341-2/076_Sinclair_ZX81_Manual.jpg 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 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.
- mattnewport 12y agoJust for context, your comment: 1452 bytes, well over twice the size of this chess program.
- astine 12y agoI think it's helpful to consider that this program in 672 bytes of machine code rather than source code or assembler. That helps the comparisons to English text seem a little less jarring: if my words were expressed as 8bit bytes rather than a series of byte sized chars you'd see a lot of compression in my communication. 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.
- acqq 12y ago> 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. 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?
- astine 12y agoIn a way you're right, the executable is definitely within bounds and if that is your definition of the program, it's small enough. If you count resources that are necessary to make the program run, however, you'd use a different metric.
- acqq 12y agoWhat do you mean? The program really plays chess against the user by running in the 1K RAM of the computer that is designed to spend 768 bytes of the said 1K just for the screen content. http://en.wikipedia.org/wiki/ZX81 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-15/PopularComputing_Weekly_Issue_1982-07-15#page/n11/mode/2up 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.
- mathetic 12y agoThe smallest implementation of full chess is an irrelevant question. It all depends on the underlying machine and how the instructions are designed. At one extreme, a closed circuit with no programming interface but with the ability to play chess is a chess implementation with code size 0. 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.
- unfamiliar 12y agoI had no idea that move even existed! Are there any other "non-standard" moves?
- hackmiester 12y ago> 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 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.
- userbinator 12y agoThat raises the question of what is the smallest implementation of full chess? In terms of source code, probably Toledo Nanochess: http://en.wikipedia.org/wiki/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.)
- etrain 12y agooh, with my latest chess programming language, the source code for chess is 0 bytes. feed an empty file to the chess compiler and out comes a working binary which plays chess.