Porting micro-Max to a small teaching language

[octogonz]

Hi hgm,

This is my first post here. I couldn't find another way to contact you, so I hope a public message is acceptable.

I'm Pete Gonzalez ("octogonz" on GitHub). I built Hybrix, a commercial educational 32-bit computer that runs in a web browser. It has a custom CPU with its own assembly language, a small low-level programming language with a garbage collector, and hardware comparable to Sega Genesis. The idea is that a student can understand the whole system down to individual bytes, the way you could with an early home computer, while still being able to make programs you can be proud of.

I have an idea to rewrite micro-Max in the Hybrix language, and then add a graphical frontend with sprites for the pieces and a Sargon-style board. It will be a free playable ROM as well as a coding tutorial for students. Using micro-Max would allow the tutorial to focus on coding, while pointing readers to your docs for understanding the chess algorithm.

What do you think of this idea? Would you want to be credited? Would you be interested to code the algorithm yourself? (The language is small enough to learn in an afternoon, and I could handle the graphical part.)

Thanks for making micro-Max and documenting it so well!

[hgm]

Well, I am always interested in CPU architecture and machine language. And I have certainly no objection against you using micro-Max. I cannot say much more without knowing some details of this Hybrix virtual machine.

[octogonz]

The programming language's framework is open source on GitLab. It's an easy way to see what real Hybrix source code looks like:

https://gitlab.com/writenrun/hybrix-framework/

These docs give an idea of how good the CPU is for chess playing:
- CPU/GPU timing
- Memory segments
- Chombit CPU overview

The framework includes a simple text console. Here's a mockup of what the text mode micro-Max could look like:


I'm thinking the GUI version might look something like this (apologize for the integer rounding errors in this mockup):

[octogonz]

(BTW I'm in Amsterdam today for the JSNation conference. If you are interested in chatting about this project in person, let me know! talkchess@octogonz.com)

[hgm]

Unfortunately I will be in Zeist today, and be back only by 20:30, so this doesn't seem really feasible.

[octogonz]

No problem, thanks for the quick reply.

There is no hurry on the project, so let me know whenever you have a chance to look at the docs.

[hgm]

I had a quick glance at the docs.

The main problem seems to be that the amount of RAM is artificially limited to 256KB, even though there is some 16MB of address space. Micro-Max quite heavily relies on a large hash table, and 256KB might not be enough to store a large enough part of the search tree. With such cramped RAM a search algorithm using the PV would probably work much better.

[octogonz]

A little background first:

The reason that micro-Max originally appealed to me is that it's small, even after we prettify it and rename the variables to have longer names. The "code golf" causes the algorithm to be a bit dense, but psychologically I think small programs feel less intimidating, so people are more willing to try it at all. (The Hybrix garbage collector gc.casm faced this: a serious GC cannot be truly simple, so instead I minimized the number of assembly instructions.)

For a comparison, I dug up your KingSlayer program. It is certainly superior for teaching chess algorithms, but as such it has more code and more features. The Hybrix tutorials really intend to teach how to write code, how to work with data structures, not the theory of chess solvers. Thus micro-Max could still be a better fit than KingSlayer.

Given this framing, if we want to weigh micro-Max versus a PV-based algorithm, then we shouldn't be asking "Does PV play better chess?" but rather "While being better, does PV still achieve the same small code size?" If yes, then for Hybrix maybe we could add a "micro-PV" to your catalog of chess algorithms. But I think it would need to be a large gain to justify that work. Micro-Max is well-known and already nicely explained on your website, so maybe it has some cultural or pragmatic value that justifies using it, even if it's not optimal.

So now back to your question: Can micro-Max work reasonably with a much smaller hash table? I have done a few experiments to see how the C program performs when the table is reduced to 8192 entries (estimated to fit the algorithm in about 100k of Hybrix RAM, leaving room for a graphical frontend), and around 5,000 search nodes (estimated for a few seconds of thinking for a CPU with 2,400,000 ops/second).

At about 5000 nodes, the 8192 table holds roughly 1000 to 1800 entries with no discarded stores, and the move, score, and depth are unchanged for the chess positions I tested. Saturation begins near 8000 and is heavy by 20000 but the decisions didn't seem to change. So, in this parameter range, micro-Max might be okay? What do you think?

[hgm]

Well I never really tried to measure the Elo loss on using such very small hash tables and low node counts. But if the purpose is to beat the average human, I guess the bar is not very high. In the eighties I had a Chess program written in 6502 assembly that could run on a 4KB machine, and most people could not beat that.

In any case the hash replacement algorithm should be made a little bit more advanced (like replace lowest depth of two, rather than replace always) This doesn't couse terribly much more code complexity. But in micro-Max it was of course optimized out because just defining an insanely large hash size achieves the same without any increase in character count.

BTW, I cannot keep myself from commenting on the Hybrix/Chombit architecture. I am too busy these times to do much Chess programming, but to stave off boredom during a long train ride I was able to have a look at the instruction set. One of the features that I missed most sorely is normal memory addressing, where the instruction simply specifies the memory address from which the data should be loaded. (I hope I did not overlook anything.) It seems you cannot access memory without first loading a memory address in a 'frame register'. Which is extra damaging, because the frame registers are really memory locations. This makes global variables very inefficient. LOAD and STORE instructions that would use a trio as address (rather than as immediate data) would allow direct access to the full 24-bit address space, and would not exceed the 5-byte limit. (And why would you want to have such a limit anyway? What is wrong with 6-byte instructions form which 5-byte instructions do not suffer?)

And the concept of frame registers is not really novel; the TMS 9900 (the first single-chip 16-bit micro-processor, form the late seventies) did map its register set to memory, through a hardware 'frame pointer'. (Which is why it could have so many 16-bit registers, for the technology of that time.) And most micro-processors can basically do the same thing. Except that it is called differently. E.g. on the 6809 'indexed' addressing mode adds a byte offset to the X (= index) register to get the memory address that should be accessed, and in indirect indexed mode whatever was fetched there is used as the memory address for the operrand data. So the X register is basically a frame pointer there.

The WITH instruction actually seems more like an instruction prefix (so that 6-byte instructions would exist anyway), and the WF flag seems not really a feature of the programming model, but more a micro-architectural method for implementing instruction prefixes. It seems pointless to consider it as a part of the flag register. One could argue that it makes the difference between an atomic operation and in interruptable one, and indeed if an interrupt could intervene directly after the WITH instuction it would be essential to store WF in the flags that the handler saves and later restores. But the machine ha no interrupts, and if you would have those, it would be easier to just not allow one after WITH. Not that I have anything against instruction prefixes; it could be useful to have a prefix that flips the default sign extension for too short operands (i.e. whether these are interpreted as signed or unsigned).

I like the IF instruction as a general method for not only branching, but also conditional execution of other instructions.

[Aleks Peshkov]

I built Hybrix, a commercial educational 32-bit computer that runs in a web browser. It has a custom CPU with its own assembly language

Being not a RISC-V is huge disadvantage.