Chesskelet

The question

Before anything else, the question is: is it possible to write the smallest chess game in the world?

The answer needs to be developed, but itís simple: no, it is not.

Historically, thre's been a need to trim the scope of the mini chess game implementation even before starting to write code. RAM memory available in last 70s and early 80s computers used for this purpose was in the range of 1K, and it does not seem possible to cover the full FIDE set of rules of chess without a big amount of code, at least, much bigger than 1KB. And this sort of limitation has been accepted by later wirters as a de-facto rule. This is the first assumption in this text: weíll look at programs smaller than 1KB (actually, much smaller).

This trimming applies specially rules beyond the basics like castling, promotion, 50-move rule, 3-fold repetition, clock management, stale mate and others. 

Secondly, there is no common definition or understanding of what a minimal chess implementation should cover, how it should be measured and how different implementaions compare.  Therefore, we can never compare pears with pears. Programs do different things with different amounts of memory, and results were achieved with very different state-of-the-art technology. Can you compare a program written in 1976 for a Z80 processor with few KB of RAM with a program written in 2016, in an emulated environment, with GB or RAM for x86 processors? I guess not.

In a more pragmatic approach, considering the existing minimal implementations, we will be able to profile what can be achieved, and especially what cannot be achieved is such small space. Weíll look deeper into this when different programs are analyzed.

Code-golfing vs. Size-coding

One of the many debates in this area is how the programs are written. While code-golfing focuses in producing small pieces of human readable code, size-coding tries to produce the smallest pieces of executable code.

Therefore, another question is if both options are valid when writing small programs and if it is possible to compare them. Although there is no scientific answer, there are some clues that will help us decide what the best option for this case is:

If we look at the particular case of mini chess programs, the earliest attempts were all implemented in assembly (Microchess, Tiny Chess 86, Superchess, ZX81 1K Chess). There were not many alternatives at that time: commercial HW, so limited in terms of memory would not allow anything but assembly.

Later, in the second wave of mini chess programs, some chose to write their code in other languages (Micromax, Toledo Nanochess, Super Micro Chess), mostly developed in C++, Java or JavaScript. All of them result in a code bigger than 1000 bytes in text and even bigger when looking at the size of the compiled version (if such thing is possible). The interesting thing here is that except Micromax, Toledo and Super Micro Chess have assembly versions produced later.

Although there are no official guidelines on this, there seems to be some consensus that assembly code produces smaller programs, even if both types of development cannot be objectively compared. Therefore size-coding seems to be the right choice when aiming for the smallest chess game. However, in my case I'm only on the size-coding side of things by accident.

History

Early era

Besides the famous 1K Chess, Iíve found a good number of similar projects. Analyzing the different sizes and features implemented in each case may give us a good idea of what the set of features you may expect from a program size range. There is a point where the programmerís ability reaches a limit. At that point the code size cannot be reduced, and the feature cutoff sword needs to be unsheathed if size has to be further reduced. Aspects like graphical representation, colored boards, and apparently basic features like castling or stalemate are sacrificed.

The first attempts I've found to write small chess programs in the 70s (Microchess, Tiny Chess 86) had similar approaches: personal computers did not exist yet and developers had to use development kits, where developers not only had to to write their own code but also to integrate different hardware parts like keyboard or screen, becoming a much bigger challenge than just writing a piece of software. I must say that any achievement in this area in the 21st century pales in comparison with the task they had to face at that time.

The eighties

Things got a little bit better in the eighties, with the arrival of 8-bit based home computers, the task became slightly easier. At least the hardware came developed. However, programmers would still have to tackle with RAM restrictions. There was activity especially on ZX81 (ZX 1K Chess and Superchess).

I need to stop here to talk about ZX81 1K Chess. While Superchess would work in a 16KB ZX81, with 1K Chess David Horne managed to write a much smaller code (672 bytes), and he was the actual father for this size-coding trend in chess programming. The achievement received lots of recognition at its time. If you read comments from people who played it when it was launched, they were so amused with the game that the fact that it was missing some basic rules like castling or en-passant that they would not care about it.

However, there has been some debate upon later improvements on how much compliant to the full FIDE rules a chess program has to be to be even considered a chess game.

https://news.ycombinator.com/item?id=9151552

http://www.pouet.net/prod.php?which=64962

This must not deviate our attention from the fact that Horneís achievement inspired other programmers many years later.

With the arrival of superior models like ZX Spectrum, Amstrad family, Commodore or MSX, developers were probably keener on writing more powerful games than small ones and 2nd wave...and 1K Chess reigned for a long time. Well, until the 2010s.

The 2010s

Coming soon...