Hacker Newsnew | comments | show | ask | jobs | submit | tzs's commentslogin

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.

reply


There'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.

reply


I 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...

(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.

reply


> Also, the ZX81 had the best cover art for any programming manual EVER:

Nope.

http://globalnerdy.com/wordpress/wp-content/uploads/2007/09/...

reply


That made me spit my beer out. Man I miss the 80's sometimes.

reply


However, you will be frustrated with the ZX81;

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.

reply


> 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.

Sounds like a good argument for a software keyboard. Might make a good touchscreen app.

reply


How did BASIC work with just 1k of memory? A scripting language interpreter is quite complex, not?

reply


They didn't work like modern interpreters, which basically compile the program into bytecode and then interpret the bytecode. They would do simple very simple parsing of the program, mostly just tokenising it, and then more or less execute each Basic statement directly. (Sinclair Basic's wacky keyword-at-a-time entry system meant they didn't need to ship a tokeniser.)

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

reply


"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."

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 + 1

reply


Oh my god - that's we we had line numbers ! To reduce parse complexity - FFS!!!

That's amazing. Why am I so blind?

reply


Not quite - line numbers were also the text editor.

reply


The BASIC resided in ROM. Here is a complete listing of the ROM: http://www.wearmouth.demon.co.uk/zx81.htm

reply


> 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.

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.

reply


"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'?

reply


The 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.

reply


I 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)

reply


Just for context, your comment: 1452 bytes, well over twice the size of this chess program.

reply


I 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.

reply


There are 4.7 bits per character for Latin text, which means the comment would have 853 bytes of uncompressed information.

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.

reply


> Estimates of information density for English are as low as 1.5 bits per character

Can you expand on that?

reply


> 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?

reply


In 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.

reply


What 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

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.

reply


"the computer that is designed to spend 768 bytes of the said 1K just for the screen content."

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."

reply


Thanks for explaining the details of the screen handling of ZX81. Still note the author of Chess1K managed to use even the bytes of the "used" display lines for his calculations, and that I still stand to my claim that the 600-something bytes are really the whole thing the user needed to run the program.

reply


Even zipped your comment is still 867 bytes. It would be difficult to even explain the castling rule alone in English text in 672 bytes.

reply


castling:req K&R 1st rank,never moved,no pieces between;can't castle out of,through,or into check;single move:Ke>g&Rh>f or Ke>c&Ra>d

134 bytes, not compressed. Did I miss anything?

reply


> 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.

reply


That 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

However, that ~1k of source becomes closer to ~2.5k of binary (x86, Windows 32-bit.)

reply


oh, 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.

reply


The 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.

reply


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.

reply


I had no idea that move even existed! Are there any other "non-standard" moves?

reply


What astounds me is that all this fuss was made over a silly dongle joke.

If the guy had been overheard quietly telling his friend a joke like, say, The Aristocrats, then I could understand someone getting seriously offended. You don't tell a joke like that where there is even a small chance unintended people will here it.

But a lame joke based on "dongle" sounding like a dirty word? That's a joke that could be told on a children't show on TV and not even draw complaints from parents in the Bible Belt.

This kind of humor is acceptable for a general family audience on prime time television. For instance, in The Simpsons episode "Bart, the Mother", Bart raises a pair of lizards that are an illegal invasive species, and Skinner is explaining why they must be killed.

Skinnner: It's already wiped out the Dodo, the Cuckoo, and the Ne-Ne, and it has nasty plans for the Booby, the Titmouse, the Woodcock, and the Titpecker.

Similarly, in the episode "You Kent Always Say What You Want", where Kent Brockman says a very nasty swear word on live TV, and apparently has gotten away with it.

Grampa Simpson: I can't believe Kent Brockman got away with it. Back in my day TV stars couldn't say boobie, tushie, burp, fanny burp, water closet, underpants, dingle dangle, Boston marriage, LBJ, Titicaca, hot dog or front lumps!

Heck, I could easily see a "big dongle" joke being told on NPR on a Saturday morning by Garrison Keillor during the annual "Prairie Home Companion" joke show (which is hilarious, BTW).

If your reaction to overhearing such a joke is anything more than rolling your eyes at the childish humor, your offensiveness sensor needs recalibration. I've heard that getting a pet can bring calmness and help you recalibrate. A bird could be a good low maintenance pet for this. I recommend a Titpecker.

reply


I've often wanted spaces in C. Because C makes heavy use of required punctuation, there aren't many places that a keyword can be adjacent to an identifier, or two identifiers can be adjacent, so for the most part I don't think spaces would introduce ambiguity.

Offhand, I can only think of a couple problem areas (but my C language lawyer days are long gone and I'm way out of practice--anyone else have some I'm missing?).

1. "goto foo;" could either be a goto keyword and the label foo, or a really stupid expression involving the variable "goto foo".

2. "int foo();" could be a forward declaration of the function foo, or an invocation of the function "int foo".

There would also be some questions about preprocessing. If I have something like "x pos = 12;", and I have a #define pos foo" in effect, does that apply to the "pos" in my "x pos"?

reply


Peter Sagal on NPR's "Wait Wait...Don't Tell Me!" had a good one liner something along the lines of Uber heard Google's "Don't be evil" motto and thought "They are leaving an open market niche for us!".

reply


Haha, that's excellent as well! I think I'll just note both of them in my quotes file.

BTW. After watching all episodes of John Oliver's "Last Week Tonight" I'm looking for interesting shows. Is that podcast worth listening to? Anything else you'd recommend?

reply


Not the OP, but I pretty regularly listen to Wait Wait, it's always pretty humorous and sadly it keeps me up on current events. I also listen to Marc Maron's WTF podcast and Star Talk Radio with Neil Degrasse Tyson. Different strokes for different folks though.

reply


Thanks for recommendations, I'll check them out! :).

reply


> And yet, maybe those men were actually farmers, producing an irrigation ditch to produce the food they need to feed their families

I doubt that farmers in Afghanistan are idiots.

They will know that because farmers almost never work in the middle of the night digging right next to the road, and that bomber planters almost always work in the middle of the night digging right next to the road, that it is very very very dangerous to dig by the side of the road in the middle of the night.

Farmers who, for some bizarre reason, have decided that they want to dig an irrigation ditch right next to the road in the middle of the night are going to make sure that the Marines in the area know the farmers will be out at that location at that time.

The war has been a major part of the farmers' lives for many years. They know how it works.

reply


It's also worth raising an eyeball over (but probably not dropping a monocle over) Mozilla being one of the strongest proponents of strong (e.g., Title II) network neutrality regulation, and Verizon being probably the telecoms most opposed, and like the one that will put the most effort into lobbying and using to overturn net neutrality.

reply


> I don’t want to sound like a broken record, but Webkit was originally a fork of KHTML, which is LGPL, so they were required/forced to release it under the same license

No, they were forced to release parts of it under the same license. There was a lot of original Apple code that could be separated out easily and released under any license they wanted (or kept proprietary) as long as they released them as object files so could modify and relink in the modified LGPL parts.

The parts that Apple was not required to release under LGPL they released under BSD.

reply


In the case of Chattanooga, one of the cities that petitioned for this, there was little or no business to compete with. They want to expand their network to outside the city limits, largely two areas that currently have either no broadband at all, or only have low speed broadband.

This causes problems for the people in those areas. Schools assume students have access to the Internet at home, and assign homework that requires Internet for research. Parents have to frequently drive their kids to McDonalds or church or someplace else with public Wi-Fi so the kids can do their homework.

Tennessee does allow for a municipal electric company to offer municipal broadband, which is how it works in Chattanooga, but it can only serve areas where it offers electricity service which was why they could not expand the broadband to the neighboring communities.

reply


The $13 TI Tiva Series C LaunchPad model EK-TM4C123GXL is worth a look if you are looking at the Teensy.

reply


I don't understand the "Beyond the Brand" section. They imply that Millennials find brand less important than others, and in the "The Power of Social" section in the same area of the presentation, they social is growing as the importance of brands shrinks.

Yet looking at the chart in "Beyond the Brand", which shows for each age group when asked about the statement "When I shop, I always try to buy branded products", Millennials had the most people who answered "strongly agree", the most who answered that plus "tend to agree", the least who "strongly disagree", and the least who answer that or "tend to disagree".

The differences between the groups aren't very much, so I question whether there is any actual difference in brand importance among the age groups, but if there is I don't see how they can conclude that it is least among the Millennials.

reply

More

Applications are open for YC Summer 2015

Guidelines | FAQ | Support | Lists | Bookmarklet | DMCA | Y Combinator | Apply | Contact

Search: