Fairy-Max and chess variants rules generalization question to HGM

[maksimKorzh]

Mr. Muller

I have a question regarding rule generalization for micro/fairy/maxqi type engines.

Recently I've implemented a very basic xiangqi and janggi (yes! finally!) JS engines based on 3 nested loops + GUIs:
https://maksimkorzh.github.io/bmcp-variants/
(please be kind to have a look)

I did it not like in MaxQi. I used 11x14 board array as in my previous engines and coded the rules without looking to MaxQi.
I have a standard vertical board orientation, not horizontal like in MaxQi (and yeah, this obviously leads to extra loop to get opposed kings state).
Eventually xiangqi and janggi move generation became very similar.
(I can't share the source code in public for I'm gonna try to monetize it's didactic value, however I would be happy to share it with you via PM if you're interested - every engine is a tiny HTML file)

So this experience stated a question:
Can we actually generalize different historical variants into a single source?

A few more things to mention.
In xiangqi in order to limit pawns directions to loop over I was faking capture conditionally basing on the board zone (not sure how this is done in MaxQi)
In janggi I was adding extra directions for pawns, cannons and rooks if they are in the palace zone.
For cannons in both variants I was unfaking capture to continue the loop and handle cannon moves.

I don't dare for speed and strength - that's something I'm interested the least.
What really excites me is the opportunity to have a single function move validation library for historical variants.

What do you think about it?

P.S. I don't need it to be fast because max depth for the lib to run would be 2 - just to track a king capture, so branching for
various variants is totally fine.

[hgm]

Janggi and Xiangqi are fairly unique amongst chess variants, by having location-dependent movement capability of its pieces. Zone confinement can be considered as a special case of this (where the pieces lose the moves that would leave the zone when they are next to a zone boundary). But in Xiangqi the Pawn move depends on whether it has crossed the River, and in Janggi the P, A, C, R and K get extra moves in Palace corners. Such things are easily implemented by not having a move list per piece type, but a different move list for each type and square. Fairy-Max stores (zero-terminated) move-step lists in an array, and has another array indexed by piece type to point to the start of the applicable list. The only modification would be to use a piece-square table for these pointers, instead of just indexing by piece type. (And of course more different move lists to choose from.) This is not what MaxQi does, because it would give a rather length source code to have the initialized tables for that. But it is a very general method, and variants without location-dependent movement could just fill the tables with the same pointer to a single move list for the piece type. Or, for efficiency, take the effect of the board edge into account, so that it would never try to generate moves that step off-board immediately. (E.g., a Knight on a1 would only have a move list with two moves.) One of the discussed methods in the 'mailbox trials' thread uses that system for Chess.

The King-facing rule could be implemented as a restriction on what can capture what. This is a generalization of Fairy-Max' concept of 'move rights', which indicate whether the move can capture or non-capture. Instead of just capture and non-capture the move rights could be a larger set of bit flags, having a separate capture flag for each participating piece type. (Possibly even distinguished by color.) The standard rights would be that all the flags for the empty square (non-capture) and all of the opponent piece types (capture) are set, and all for friendly pieces are cleared. For the 'diverging' FIDE/Shatranj Pawn the non-capture bits would be the opposit of the enemy capture bits. The Xiangqi King facing rule can then be implemented as an extra (forward) Rook move of the King, that can only capture the opponent King.

[maksimKorzh]

Janggi and Xiangqi are fairly unique amongst chess variants, by having location-dependent movement capability of its pieces. Zone confinement can be considered as a special case of this (where the pieces lose the moves that would leave the zone when they are next to a zone boundary). But in Xiangqi the Pawn move depends on whether it has crossed the River, and in Janggi the P, A, C, R and K get extra moves in Palace corners. Such things are easily implemented by not having a move list per piece type, but a different move list for each type and square. Fairy-Max stores (zero-terminated) move-step lists in an array, and has another array indexed by piece type to point to the start of the applicable list. The only modification would be to use a piece-square table for these pointers, instead of just indexing by piece type. (And of course more different move lists to choose from.) This is not what MaxQi does, because it would give a rather length source code to have the initialized tables for that. But it is a very general method, and variants without location-dependent movement could just fill the tables with the same pointer to a single move list for the piece type. Or, for efficiency, take the effect of the board edge into account, so that it would never try to generate moves that step off-board immediately. (E.g., a Knight on a1 would only have a move list with two moves.) One of the discussed methods in the 'mailbox trials' thread uses that system for Chess.

The King-facing rule could be implemented as a restriction on what can capture what. This is a generalization of Fairy-Max' concept of 'move rights', which indicate whether the move can capture or non-capture. Instead of just capture and non-capture the move rights could be a larger set of bit flags, having a separate capture flag for each participating piece type. (Possibly even distinguished by color.) The standard rights would be that all the flags for the empty square (non-capture) and all of the opponent piece types (capture) are set, and all for friendly pieces are cleared. For the 'diverging' FIDE/Shatranj Pawn the non-capture bits would be the opposit of the enemy capture bits. The Xiangqi King facing rule can then be implemented as an extra (forward) Rook move of the King, that can only capture the opponent King.

Thank you for such a detailed and extended answer.

"This is not what MaxQi does, because it would give a rather length source code to have the initialized tables for that."
- so did I get it correctly like you mean that MaxQi was separated from Fairy Max not because it's imposiible to generalize the rules
but due to efficiency reasons? I mean things like rotating board for one line opposite kings detection etc.
So is it correct to say that you've separated MaxQi from Fairy max just come up with a faster/stronger engine
compared to what it be if merged into Fairy Max?

Please let me explain the reason behind this question to clarify what exactly I'd like to know.

So I see 2 approaches:
1. Make Micro-Max like engine for every single variant (something I'm doing now, but stripping almost everything from the search including even quiescence)
2. Make a more generalized version of Fairy Max like engine

I clearly understand that generalizations violate efficiency significantly but if are not talking about is as an engine but only
as a move validation library - in this case we can safely ignore the fact that performance is low and can sacrifice it as much as needed?

So this is an efficiency vs generality question in essence, is that correct?

[hgm]

Well, there is a wisdom known as the "maximum flexibility, minimum usefulness principle". MaxQi was a sort of half-hearted attempt to make the (source-code-wise) smallest Xiangqi engine, just as micro-Max was an attempt to make the engine with the best Elo/sorce-size ratio. And since I already had Fairy-Max at the time, which could do the lame leaps of Horse and Elephant, it wasn't much work. But Xiangqi has so many rules unique to it (I did not even know Janggi existed at the time), that I saw no point in generalizing Fairy-Max with all kind of optional features that would have to be configurable, and then would only ever be used in Xiangqi. So I just hard-coded the zone confinement, and the King facing in a separate derivative.

The methods of generalization I discussed above do not really cause a lot of inefficiency in terms of speed. But the goal with MaxQi was not speed, but code size. It is true that the more advanced your engine is, the more difficult it is to generalize. The micro-Max derivatives are simple King-capture engines, which do not employ a separate in-check test to vet the moves they search for legality. They just return a +INF score on King capture. And if a score ends at -INF (which is also the initial value of the bestScore variable) all the moves must have resulted in capture of your King, so that you are either check or stalemated. Which you would similarly determine (if it is relevant; in Xiangqi it would not be relevant as stalemate is a win too) by searching a null move (1 ply deep), and see how your King fares then. This is reliable but slow, and need extra search depth to recognize mates.

But most efficient dedicated check tests are hard to generalize. Because some properties they make use of do not generally apply. E.g. in Xiangqi you can have double-checks that you can still block by interposing (a Cannon behind a Rook). In Janggi you can even solve such a check by capturing one of the two checker. (Capture the Rook with a Cannon, and it will block the other Cannon.) It can also be hard to determine where checks are coming from if there are pieces that turn corners.

[maksimKorzh]

Well, there is a wisdom known as the "maximum flexibility, minimum usefulness principle". MaxQi was a sort of half-hearted attempt to make the (source-code-wise) smallest Xiangqi engine, just as micro-Max was an attempt to make the engine with the best Elo/sorce-size ratio. And since I already had Fairy-Max at the time, which could do the lame leaps of Horse and Elephant, it wasn't much work. But Xiangqi has so many rules unique to it (I did not even know Janggi existed at the time), that I saw no point in generalizing Fairy-Max with all kind of optional features that would have to be configurable, and then would only ever be used in Xiangqi. So I just hard-coded the zone confinement, and the King facing in a separate derivative.

The methods of generalization I discussed above do not really cause a lot of inefficiency in terms of speed. But the goal with MaxQi was not speed, but code size. It is true that the more advanced your engine is, the more difficult it is to generalize. The micro-Max derivatives are simple King-capture engines, which do not employ a separate in-check test to vet the moves they search for legality. They just return a +INF score on King capture. And if a score ends at -INF (which is also the initial value of the bestScore variable) all the moves must have resulted in capture of your King, so that you are either check or stalemated. Which you would similarly determine (if it is relevant; in Xiangqi it would not be relevant as stalemate is a win too) by searching a null move (1 ply deep), and see how your King fares then. This is reliable but slow, and need extra search depth to recognize mates.

But most efficient dedicated check tests are hard to generalize. Because some properties they make use of do not generally apply. E.g. in Xiangqi you can have double-checks that you can still block by interposing (a Cannon behind a Rook). In Janggi you can even solve such a check by capturing one of the two checker. (Capture the Rook with a Cannon, and it will block the other Cannon.) It can also be hard to determine where checks are coming from if there are pieces that turn corners.

This answer was a real treasure to me, thank you so much.
Btw, today I added makruk to my variants collection.
Obviously iwas absolutely trivial to derive from standard chess,
but I'm got really exited by the game's dynamic (or a lack of dynamic would probably be a more precise description).

So yeah, It's all about projects goals.
The only tricky thing is that ones you set up a goal many sub goals arising to deal with.
For instance when I tried to implement janggi in "solid" way it turned out to be highly demotivating,
however I'm more than happy with the current king capture implementation.

A few more questions if you'd be kind to answer please:
Say in... I don't know 70th-80th which goals did programmers set up in regards to chess?
Were the goals limited by the hardware of that time?
Was there any other sources of inspiration to come up with minimalist programs other than lack of memory or similar environment related things?

[Kotlov]

n.
Say in... I don't know 70th-80th which goals did programmers set up in regards to chess?
Were the goals limited by the hardware of that time?

Очевидно же

[mclane]

Most programmers had 8 bit machines with 1 mhz (c64) and maximal 16-32 KB engine size.
On the early 16 KB Ram homecomputers even less, e.g. engine sizes between 8 and 10 KB.

There were mainly z80 and 6502 machines.
One can say that a chess engine on 4 mhz z80 is maybe similar fast on a 2 mhz 6502.

In a 32 KB Size was engine and Opening book.
Ram was between 4-8 KB.
Earlier engines even less, only 2-4 kb.

The early dedicated chess computers had 2-4 mhz.
In the 80ies 4-5 mhz on 6502.

Programmers like ed schroeder, dave kittinger, maybe the spracklens, were capable to get 1950- Elo out of the
5 mhz 6502 CPU.

That was the end of the eighties.
In the beginning it was less.
Maybe 1600-1750 Elo when the software was 16 kb size and hardware maximal 3.6 mhz.

[smatovic]

...
In the beginning it was less.
Maybe 1600-1750 Elo when the software was 16 kb size and hardware maximal 3.6 mhz.

Hehe, my favor - Video Chess from 1978 for the Atari VCS gaming system:

- 8-bit 6507@1.19 MHz
- 128 Bytes RAM
- 4 KB ROM cartridge

--
Srdja

[mclane]

This is indeed a very weak engine....

There were later strong 4K and 16k engines from Kaare Danielsen.
Nevertheless programmers tried AI and B Strategy ideas in those early years.

David Broughton, Thomas Nitsche.

[maksimKorzh]

This is indeed a very weak engine....

There were later strong 4K and 16k engines from Kaare Danielsen.
Nevertheless programmers tried AI and B Strategy ideas in those early years.

David Broughton, Thomas Nitsche.

I don't care about strength.
Fairy Max is valuable for it's design.