Porting micro-Max to a small teaching language

[octogonz]

Thanks! This patch seems to be based on version 4.8 of your algorithm, whereas my Hybrix language port is working from version 3.2 on your website. (As mentioned, for a tutorial version 3.2 has good docs and a simpler algorithm.) Version 3.2 uses the multi-probe scan:

Code: Select all

                                               /* lookup pos. in hash table*/
 j=(k*E^J)&U-9;                                /* try 8 consec. locations  */
 W((h=A[++j].K)&&h-Z&&--i);                    /* first empty or match     */
 a+=i?j:0;                                     /* dummy A[0] if miss & full*/

So I can't drop the two-slot code in directly, as the table geometry differs. But the idea can be ported: re-add real replacement intelligence that the big-table versions could afford to drop.

For a small saturated table, would you still prefer the paired shallowest-of-two with undercut aging, or does a short linear probe (say 8 slots) with shallowest-of-N replacement buy anything over the pair? On Chombit I'm counting instructions per node rather than cache misses, so the probe width tradeoff is different from a PC.

(The full Hybrix language source code will take me a few weeks to finish. I'll post it here for review when it's ready.)

[hgm]

Shallowest-of-4 is hardly better than shallowest-of-2, and when I tested shallowest-of-7 it was even worse. The best way I found was 'equi-distributed draft', but the complexity might not be worth it: it would keep a histogram of the depth distribution in the table, and would replace the entry in the depth-preferred slot when the depth of the latter is present in the table more than the lowest depth is present in the table. Otherwise it would defer to the always-replace slot. This automatically takes care of aging. There still would be the option to have several depth=preferred slots defer to the same always-replace slot.

[octogonz]

Progress update: chess_engine.hyb is an initial draft of a Hybrix chess interface that allows different algorithms (e.g. micro-Max) to be used interchangeably by a chess front end such as my graphical game, a simple text console, or (later) a simple harness for community tournaments. Although it's a bit bureaucratic, I think this formalism is worthwhile because it enables tutorials to separately focus on the front end (sprites, mouse actions, etc) versus the algorithm. Also, if someone does the work to implement an alternative algorithm, their work can potentially be leveraged by multiple front ends.

As a software person I tend to sketch a full integrated design, then disable/delete the parts that aren't needed today. So, I've split the contract into four orthogonal features that are each optional:

- load_position(): ability to support loading/saving of board states
- undo_move(): ability to undo one or more moves
- collect_moves(): ability for a GUI to highlight possible next moves
- find_move(): ability to search for a move for computer play

I'm now working on two subclasses of the chess_engine base class:

- rules_chess_engine: a human-vs-human reference implementation that supports everything except find_move()

- micromax_chess_engine: the micro-Max port. We only need find_move() to reproduce micro-Max's text UI; however, for other front ends it seems relatively cheap to add collect_moves() and/or undo_move(). load_position() may not be worthwhile.

Let me know what you think of this approach. Is anything unconventional? Can you think of any popular algorithms that wouldn't fit this contract? (Keeping in mind the constraints of a 32-bit retro computer with 256KB, no OS, and a focus on teaching coding rather than professional app development.)

[octogonz]

More progress: I've updated my GitHub gist to add reference_chess_engine.hyb (formerly named "rules_chess_engine"). This is a basic implementation of the chess_engine contract.

I also added chess_console.hyb, which is a simple text console chess game, similar to the micro-Max stdio loop. Here's a ROM cart if you want to try playing it:



(To run, drag+drop this PNG file onto the https://www.hybrix.dev/emulator page.)