Chess

[ashort]

I'm proud to announce Jack CHESS, written in Jack.  

It's you against the computer.  

Copy the vm files to a folder, and open the folder in the VMEmulator. Set the VMEmulator speed to "Fast" and set animation to "No animation", then run the app.

Choose White or Black, then choose the level of play:

Level 1: computer plays random but legal moves.  Plays instantly.

Level 2: computer has a fixed shallow search depth.  Plays almost instantly.

Level 3: computer will vary its search depth. [on my 2017 Mac, moves vary between 10 and 40 seconds]

Level 4: computer will vary its search depth. [on my 2017 Mac, moves vary between 45 seconds and 3 min]

Level 5: computer will vary its search depth. [on my 2017 Mac, moves vary between 90 seconds and 6 min]

Jack CHESS plays 100% legal chess, including castling, en passant, promotions, under-promotions, draw by stalemate, draw by 50 move rule, and draw by repetition.  

Jack CHESS has a small opening book.  This is so you get varied play - otherwise it would always play the same game and be very boring.  

I couldn't find anyone else that has written a chess app in Jack, so I'm happy to make this contribution to the nand2tetris community.  If you like Jack CHESS, also check out my much simpler tic-tac-toe game, written in Jack. It's you against the computer.

Here is a screenshot:



Notes:

(1) To enter a move, type 4 characters using square coordinates, e.g. E2E4.  I considered using arrow keys, but arrow keys would be very annoying.  Imagine right-right-right-right-up-up-Enter-right-right-up-Enter just to select a Knight and move it.  Note that algebraic notation, e.g. e4, Nf3, O-O, Nxe5, Rdf8, R1a3, or Qh4xe1 is not supported.

(2) Despite going to great lengths to speed up the engine, Jack CHESS is still very slow, because running VM code in the VM Emulator is not exactly a blazing fast environment.  On my 2017 Mac, Jack CHESS is analyzing approximately 550 positions per second, which sounds fast but it isn't.  Also, real chess engines save time by using of gobs of heap (a hash table) to store evaluations of positions it has already searched, and the 14k heap that I was working with is just too small for that (I am using much of the heap for other stuff).  So the end result is Jack CHESS in the VMEmulator is not going to search very deep, but it still plays strong chess, and beats me regularly!

(3) Jack CHESS adheres to the Hack machine's heap and stack size limits and runs in the VMEmulator, but because Jack CHESS was written with performance (not program size) in mind, the program would not fit within the 32k Hack ROM (and the Hack ROM must also contain the Jack OS).  So I will never have the satisfaction of running Jack CHESS in the CPUEmulator. On the other hand, one could theoretically write a chess app that WOULD fit in the 32k ROM, but it would have to be optimized for program size, not performance. Meaning, the Jack code would need a total re-write, and you would need a VM Translator that outputs highly optimized Hack Assembly code.

(4) During development, sometimes the VMEmulator would give me a Jack-code crashing error such as "Out of segment space in Piece.getValue.3". Any time I received an error like this, it meant I had a null pointer, e.g. I was calling getValue() on a Piece object but the object was null.  The VMEmulator shows the Call Stack, which makes finding and fixing these crashing bugs much easier.  I eventually created my own Debug class so I could sprinkle my code with asserts, which helped a lot.  At present I have played many full games with zero crashes of any kind.

(5) It helped that I had written a chess engine 20 years ago. There are millions of articles on the internet related to chess engine programming, and many were very useful to me.  In particular I want to give credit to Bruce Moreland, whose clear writings on chess programming were very helpful.  For those of you who have written game engines, Jack CHESS is a relatively simple chess engine featuring (a) 0x88 board representation, (b) piece lists, (c) alpha-beta with quiescence search, (d) null move forward pruning, (e) iterative deepening with aspiration windows, (f) piece-square tables, and (g) move order: PV move, captures in MVV-LVA order, non-capture killer moves.  Since my move ordering is not ideal, I didn't implement LMR (late move reduction), which would have allowed for more pruning and deeper searches. Also, I did not implement pondering.  Finally, the draw by repetition detection only catches the shortest case where the intervening moves are the same, for performance reasons.  That covers most draw by repetitions and perpetual checks, so it's ok.  My goal was to create an engine that could beat me (with modest thinking time) when run in the VMEmulator, and I met that goal.

[WBahn]

Impressive. You have WAY too much free time on your hands!

It really sounds like you put a lot of quality work and effort into this.

How big is your ROM code?

It really is amazing how much you can do with a resource-starved platform.

Like go to the moon.

The Apollo Guidance Computer (AGC) was a 16-bit machine with 2048 words of RAM and 36 kwords of ROM and ran at about 2 MHz. There were two basic versions, the Block I (flew on uncrewed missions) and the Block II (crewed missions). The Block I was made with 4100 IC packages each with a single 3-input NOR gate while the Block II used about 2800 ICs with dual 3-input NOR gates. The early Block I units had 1024 words of RAM and 12 kwords of ROM. The Block II units had 2048 kwords of RAM and 36 kwords of ROM.
 
While the Hack supports 28 instructions, the Block I AGC supported 11 and the Block II supported 34. So the Hack is very comparable in basic specs.

The AGC had more registers and it had a complex instruction set, so further comparison are much more difficult. But given the much higher clock speeds that we could drive a Hack at, I suspect that the overall computational power was roughly on par.

[ashort]

Jack CHESS with my VM Translator is 345,535 Hack assembly instructions (not counting comments and labels), which means 345,535 Hack machine language instructions.

However, my VM Translator does NOT output optimized .asm code - it merely conforms to the nand2tetris course.  I've read about optimizations on this forum and it seems one could get as much as a 65% reduction in program size with the best optimizations.

So perhaps someone's VM Translator could get this down to 345,535 * .35 = 120,000 instructions, still way bigger than the Hack 32k ROM, and I'm not even counting the Jack OS...

Interesting stuff on Apollo!

[ashort]

actually if someone has a really great optimizing VM Translator, I would love to hear how many .asm lines you get (not counting comments and labels).  Unfortunately my VM Translator has zero optimizations.

[Gerrit0]

This is amazing! I ran it through my translator, which does some space optimizations but is primarily focused on speed, and 32K is still way out of reach. With a translator that has optimal/near optimal Hack for each VM instruction, there are just over 200K Hack instructions. Applying all my optimizations, the assembled Hack has 146405 143827 instructions.

Note: These numbers include the stock Jack OS, my translator doesn't let you run unless all functions are defined.

It would be an interesting project to try to get this under 100K instructions. I think it's possible, but getting all the way down to 32K would be incredibly difficult.

[ashort]

Well that’s impressive. Assuming the full Jack OS is ~20k using your optimized VM Translator, then my estimate of 120k for Chess was pretty close.

[dolomiti7]

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

[dolomiti7]

For reference: Below is the instruction distribution of the Hack version. As usual for my threaded code, it consists mainly out of A-Instructions (49.6%) and jump commands (43.8%). The speed with the CPU Emulator on Java 21 at level 3 seems actually to be more around 10-15 minutes (from the starting position making an immediate out-of-book move a4).

[Renslay]

That is really impressive - both ashort's chess game and engine, and dolomiti7's optimization! I am in complete awe, and my mind is blown.

Congrats on such a fantastic project!

[ashort]

Wow, I would love to see a video of Chess running on FPGA.  If someone could post that I’d really appreciate it.

[Teledar]

This is really cool! I'd been working on my own chess engine in Jack, not realizing that anyone else had ever made one. Yours is way better.

Check out my JHack project - I converted my VM translator to output Java class files. I ran your chess engine on the JVM, and level 5 makes moves in less than 15 seconds.

[ashort]

wow, nicely done!  I would encourage you to finish your chess project - maybe challenge yourself to write a tiny one that plays valid, reasonable chess and fits in the Hack ROM.   Certainly doable, and I don't believe anyone has done that.