Re: Chess

Posted by dolomiti7 on
URL: http://nand2tetris-questions-and-answers-forum.52.s1.nabble.com/Chess-tp4035234p4037647.html

The Chess program is really great! And finally my toolchain managed to bring it below 32k! So it is now available as Hack machine code for CPU Emulators or FPGAs.

I have outlined the techniques that I'm using to reduce the program size in this post. With all the described tricks - and a few more - I could just bring it down to 32,609 words. So it's really a close call.

The translation is based on:
- the original Chess VM files (Jack source code is not available)
- my own OS in a size optimized version
- my VM code optimizer
- my own optimizing compiler
- my own threaded code based VM translator

Special settings in my toolchain:
- exact evaluation of signed comparisons
 (catches signed overflow during comparison - required for Chess)
- remove error handling (removes calls to Sys.error and Sys.error itself)
  (unfortunately that was the last small thing required to stay below 32k, otherwise it is 77 words too long...)
- compress string literals

Changes to the Hack conventions (mapping/OS):
- Heap Memory start at offset 928 instead of 2048 (required for Chess)
  (I'll explain why below)
- Keyboard limits input to 4 chars (saves memory and Chess doesn't require more)

Effect of the toolchain:
I made a first test using the stock OS, the stock compiler and just applied some dead code elimination. That left me with 33,112 VM commands (excluding labels). At that time I wasn't too confident that Chess could ever be compiled into 32k machine code instructions (without reprogramming it or parts of it in assembler). Even considering a ratio of 2 asm instructions per VM command, the expected size was at best around 64k...

Things looked a bit better after using my own OS which is significantly smaller than the stock OS. And finally together with my Compiler+Optimizer, I could bring down the number of VM commands to 22,172 - a reduction by one third.

Finally with lots of optimizations, my VM translator managed to translate the program using only 1.47 ASM instructions per VM command in average. That was possible because there are many code duplications within the Chess program.

Memory layout:
Chess has been programmed for the VM Emulator and takes implicitly advantage of some specialties that won't work in the CPU Emulator or on a real Hack computer. Specifically the VM Emulator keeps all internal data structures of the OS in its own memory and doesn't map them to the Hack memory. Most importantly that applies to the Charset. Therefore the VM Emulator has the full 14k (16k minus 2k for Registers+Static+Stack) available for the emulated applications. A fully translated program (including the OS) needs to place the charset and other internal data structures in the heap memory. The stock OS leaves for example only 11,512 words available on the heap when entering Main.main. The rest is used by the charset etc. For the same reason, Chess will not work in the VM Emulator if you copy the OS VM files into the working folder.

My own OS has a significantly lower memory footprint and leaves 13,245 words out of the 14,336 words heap memory available. Unfortunately that is still not enough for Chess which uses nearly the whole 14k. When I managed to bring down the program size below 32k for the first time, Chess was still crashing because of that. I started to test how much of the nearly 2k stack memory is really needed and found that even in level 5 there is more than enough buffer if I reduce the stack memory and increase the heap instead. Effectively I increased the heap by 1,120 words which is just enough to operate.

Execution speed:
The program will work in the CPU Emulator and I would say you can play it in levels 1 and 2 reasonably. Starting from level 3, you will need much time - a move can take an hour or more (depends a lot which Java version you are using, but everything from level 3 onward is really slow...).
I tested with level 5 in my own emulator which runs at much higher speeds in the GHz range. At that speed it is fun to play even at level 5. On FPGAs it should be ok with the higher levels as long as you run at 50 MHz or higher.

Download:
Chess.hack

Have fun and feel free to ask if you have any further questions.
Axel