Amoeba : A Modern TSCP Type Engine

[catugocatugocatugo]

Hello! hgm has suggested this post for me here: https://www.chessvariants.com/index/lis ... p?id=63107. I was trying my own engine here: viewtopic.php?t=81554. Unfortuneatly I ran into some problems. Maybe I can still do it, with the help of chatgpt. I am not sure. Unfortuneatly I can't focus enough and that gets me into basic trouble. Anyway I understand that this more didactic engine is going the variant fairy chess way. If that is the case then I'd be interested in participating. hgm is a great menthor, and judging by what I've read on this post he is not alone.
Also, hgm I was contemplating the idea of merging this project with the one here: viewtopic.php?t=83322 . That would be awesome. A general engine that is didactic, and maybe that supports some neural networks for the optimization of the evaluation function would be so great. Do I ask for to much? I'd put hard work into it two, once somebody else has made the very basics. I can write piece moves generators quite easily for example.
Guys, thanks for your time!

[hgm]

Well, that other project contains so much complexity that is not needed for orthodox Chess at all. That would hardly count as didactic anymore. But if we make the design of the didactic engine sufficiently modular, it would of course be possible to replace the move generator later.

For the time being I am thinking of implementing a somewhat more capable move generator as a separate module for extension of the didactic engine. Just like we could add more search heurisics (such as history) as more advanced modules.

The compact move generator for orthodox Chess that we discussed already can handle any finite-range rider (of which leapers are a special case, with range = 1), possibly divergent. This is done by describing every slide as a triple {step, range, capability}. That capability currently only allows specifying move-only and capture-only moves, for the benefit of FIDE Pawns. Other bits in there could be used to indicate the move is multi-leg. The basic move generator would then only have to test for any of those bits being non-zero, and would then invoke a more-capable, more complex move generator.

What I have in mind is to allow each slide-descriptor triple to specify (by 2 bits in the capabilities) whether it has a follow-up leg, specified by a descriptor that could be 5, 9 or 13 places further in the moveTable. Non-final legs could then also indicate they must end on an occupied square, off-board or capture a friendly piece. The strides 5, 9 or 13 are inspired by the fact that pieces are typically described by a set of 4 or 8 rides in different directions, followed by a descriptor with a 0-step to indicate the end of the list. So a Korean Cannon could be described as ABCD0abcd, where A-D are (infinite-range) rides in the 4 different orthogonal directions that must end (non-destructively) on an occupied square (the mount), and a-d the corresponding rides that can move to empty or capture an enemy. Each of those would be 5 places further in the table than the descriptor of the first leg in that direction.

A move discriptor indicating it is not the final leg would lead to calling the routine for complex move generation, which would recursively call itself for every realization of the leg it can find, to handle the next leg. The final leg would add a move to the move list for every realization. This would allow handling of bent riders like Griffon (infinite ride following a single step), hoppers and bifurcators (hop-on ride followed by another ride), locust capture (capture followed by another step or ride).

There would be limitations due to the move format used by the engine. In the current design a move was represented as a triple {origin, destination, specialEffect}, where the specialEffect can potentially indicate an arbitrary locust square. For Chess the latter is only used for e.p. capture. Which is a bit wasteful, as for this the locust square could have been derived from the origin or destination. But for simplicity reasons it would not be very desirable to pack the move description into two bytes, and using a separate byte for origin, destination and specialEffect conveniently leaves ample room for encoding the locust square explicitly, even on a large board.

Even though this is not completely general, (also because of board-size limitation to 15x15 with at most Knights or 14x15 with Camels), it would be sufficient for a very wide range of variants. And still pretty simple.

[catugocatugocatugo]

So, from what I understand the falcon is of the table although mao and moa are maybe not. Also there is the issue that my games have an imitator, and weirder promotion rules. But I think that once the basics are done, I can branch myself from the program and do what I need, like the things mentioned above. Also what about adding small neural networks to enhance the evaluation function? I know nobody has tried that, but maybe an Radial basis function NN is something to be considered, too, besides the obvious choice of a shallow MLP (2-3 hidden layers).

[catugocatugocatugo]

And I forgot to ask, how can I help?

[hgm]

Well, you are already helping, because the Falcon should definitely not be off the table. I suppose you mention it because it needs too many paths: 3 for each of the 16 destinations. So perhaps the 5, 9, 13 idea was not ideal. And the Chu-Shogi Lion would have 64 paths for performing hit & run captures. So perhaps it would be better to use 17, 67 and 81 as possible distances for the follow-up legs.

My idea was to encode the presence of continuation legs there with two bits in the capability field of the move descriptor. So that you could mask away all other bits, and use what is left for incrementing the 'currentLeg' pointer:

currentLeg += (moveTable[currentLeg].capability & 0x50) + 1;

The bits that the 0x50 mask leaves are worth 64 or 16. The Falcon moves could then be indicated by 3 legs, the first two MOVE_ONLY, spaced by 65 entries in the moveTable. Of the 64 elements that ly in between only 49 would be filled. But I don't think it would be very harmful to have a few unused entries in the move table. And one could always try to fit some other piece with less than 14 moves in there.

It is a bit annoying that the three alternative paths to a given destination can potentialy generate the same move 3 times, if all paths are unblocked. We could apply a general test to all generated moves for being a duplicat, and discard those that are. But perhaps it is better to just reserve a bit in the capability field for indicating "don't try this if the previous one already succesfully generated a move". That would save you the time of generating and testing moves that you are going to discard.

The Interactive Diagram uses something similar to the 'capability' in its move table, and also reserves bits there for indicating a move is jumping or non-jumping. But these are really not needed: such moves can be indicated as multi-leg moves requiring the squares they (non-destructively) pass through to be either occupied or empty.

Code: Select all

/* capability codes:
  1 = to empty
  2 = leave board
  4 = hop over white
  8 = capture white
  32 = hop over black
  128 = capture black
*/
int kindTable = { 1, 0x0C, 0xA0, 2 }; // for empty, white, black and edge guard

int OneLeg(int currentLeg, int fromSquare, int intermediateSquare, int locustSquare)
{
  int step = moveTable[currentLeg].step;
  int range = moveTable[currentLeg].range;
  int capability = moveTable[currentLeg].capability;
  do { // step through ride
    intermediateSquare += step;
    victim = board[intermediateSquare].type;
    victimKind = kindTable[victim >> 6]; // index by COLOR bits
    hit = victimKind & capability;
    if(hit) { // valid target type
      int legStep = capability & 0x50;
      if(legStep == 0) { // no more legs, this is the destination
        AddMove(fromSquare, intermediateSquare, locustSquare);
      } else {
        if(hit & 0x88) OneLeg(currentLeg + legStep + 1, fromSquare, intermediateSquare); // destructive encounter
        if(hit & 0x27) OneLeg(currentLeg + legStep + 1, fromSquare, locustSquare); // non-destructive encounter
      }
    }
    if(victim != EMPTY) break;
  }  while(--range);
}

// in the loop over directions of the simple move generator:
  if(moveTable.direction].capability & 0x76) {
    OneLeg(direction, fromSquare, fromSquare, 0);
    continue;
  }

Considering the wide variety of moves this could generate, it is still pretty simple. The fromSquare is always passed from the caller to the generated move unchanged. The locustSquare is set to 0 by the caller, but can pick up a value in a destructive leg. The intermediateSquare starts at the fromSquare, and then follows the path until a valid final destination is reached.

There is one problem: this code is not color-blind. It would be more convenient if the moveTable would not have to explicitly indicate whether a move can capture white or black, but instead whether it can capture friend or foe. This could be achieved by having different kindTable for black and white, and before we start generating moves for a particular player initialize the table (or a pointer to it) such that the white and black entries indicate the applicable friend and foe bits. (I.e. swap the 0x0C and 0xA0 when generating for black.)

[Mike Sherwin]

Simple piecewise Neural Net for creating piece square tables prior to the search. For example a knight can have a number of inputs.

.mobility
.centrality
.SEE
.targets attacked
.targets attacked in one move
.history value
.outpost

Hidden layers I do not understand yet.

So only two layers for now, the inputs and one evaluation.

The weights are learned from self play. It starts off with random weights. Two versions play each other. The weights from the winner are kept.

Before the search the knight's NN is applied to each square of the knight table to build the knight table.

This is like an HCE that is improved upon by the use of an NN.

[hgm]

Doing this only in the root seems a bit static to me. It might be no longer valid in the leaves where you use it.

How about putting piece-square tables in the Pawn hash table? That would make the Pawn-hash entry awfully large, of course. But memory is cheap, nowadays. And it makes sense: the Pawn is the soul of Chess. Creating a complete PST for a given Pawn structure could be wasteful. But you could use a special value for indicating the score for that square has not been calculated yet (by a neural net or otherwise). When you consider a move to such a square you would then calculate it on the fly. There might be squares you never get to with pieces of a certain type. Imagine you have only one Bishop in the root...

This is basically a generalization of an open-file bonus for Rooks. This relates good positions for the Rooks to the Pawn structure as well.

[Mike Sherwin]

Doing this only in the root seems a bit static to me. It might be no longer valid in the leaves where you use it.

How about putting piece-square tables in the Pawn hash table? That would make the Pawn-hash entry awfully large, of course. But memory is cheap, nowadays. And it makes sense: the Pawn is the soul of Chess. Creating a complete PST for a given Pawn structure could be wasteful. But you could use a special value for indicating the score for that square has not been calculated yet (by a neural net or otherwise). When you consider a move to such a square you would then calculate it on the fly. There might be squares you never get to with pieces of a certain type. Imagine you have only one Bishop in the root...

This is basically a generalization of an open-file bonus for Rooks. This relates good positions for the Rooks to the Pawn structure as well.

What about training PSTs for the ECO positions? It would be much better than using just one static PeSTO like table.

[hgm]

That certainly is an option. But I have the feeling we are straying off the path for a simple didactic engine. And I doubt such unusual evaluation methods could really improve on NNUE evaluation. And the latter has the advantage that it is conceptually simple, and requires only very little code.

And there is plenty of opportunity to experiment with NNUE as well. We could for instance use dedicated passer detection, and feed passers as a 7th piece type to the NNUE. I have no doubt that passers are very important for evaluation of Chess positions, and using an efficient passer detection (i.e. a lookup from the Pawn hash) would relieve the neural net for figuring out which Pawns are passers, and being trained for that.

[Edit] Something I forgot when discussing hand-crafted evaluation: patterns. Engines are prone to stupid strategic blunders, which take a long time to punish, but unavoidably will be punished. Like white having a Bishop on a7 with black Pawns on b6 and c7. It pays Elo-wise to recognize these patterns, and award large penalty for those.

This is actually a special case of having Pawn-structure-dependent PST; a7 would be a very bad square in the Bishop PST for a Pawn structure with Pawns on b6,c7. Perhaps most advantage of the idea can already be captured by listing a few exceptional squares for some or all piece types. E.g. as {pieceType, square, score} triples. For the Rooks these are of course the (half-)open files, so perhaps there should be a method of indicating an entire file instead of a single square. E.g. by using an off-board square number. The squares where a Bishop would be trapped (or Knights on an enemy corner with an enemy Pawn behind them) could be mentioned with a large penalty. The castling target squares could get a bonus for Kings depending on the quality of the Pawn shield, half-open files aimed at it, and an approaching Pawn storm.

The evaluation would then run through the list of these special squares in the Pawn-hash entry, to test whether the mentioned pieceType is present there, and if so, award the mentioned score. This would not bloat the Pawn-hash entries too much; 5 special squares might suffice.

The Pawn-hash entry should also specify the number of Pawns on each shade, for evaluating good vs bad Bishop.

[hgm]

I have started coding a simple engine along the lines we discussed. First goal is to make it play orthodox Chess, with PST-only evaluation. I will keep extendability to more complex chess variants in mind, though. In particular by using macros and type definitions for parameters that might have to be increased to make it play another variant. Such as the board dimensions, the integer type used to store a square number etc.

That doesn't stop me from thinking how the capabilities of the move generator could be improved in order to handle more move types. One of the things that was still lacking is the efficient handling of 'crooked sliders': pieces that slide along an irregular path instead of a straight line. It is possible to specify arbitrary paths for a move with a specific destination, by making each step along the path a separate leg of a multi-leg move. To make a piece that scan also slide fewer steps along the same path, tou would have to define these as separate moves with fewer legs. Which start the same, but terminate earlier.

This is very inefficient, as the move generator would be testing time after time whether the early squares in the path are empty. It would be much better when the definition of a non-final leg would inform the move generator with "you can also stop here". Then the moveTable would only have to contain the description of the farthest move as a multi-leg move. And at each empty square the described slide would pass through, it would both go on with the next leg, to take the next step along the path, and generate a move that ends there. When it hits an enemy piece before reaching the end of its path it would generate the capture of it, but not continue with another step (instead of just aborting). To allow such pieces to be divergent the possibility to stop along the way should be indicated separately for capturing and non-capturing.

Unfortunately no more bits are available in the capability field of the move descriptors for indicating this, if we want to store it in a single byte. Of course we could extend its size to uint16_t. But there is another possibility: the range field would normally only be positive. If we use do-while(--range > 0) to loop through the slide, a zero or negative range would still do only a single step. Which is what we want for specifying an arbitrary path. So we can use negative range codes for specifying the possibility for an 'early exit', e.g. -1 = move only, -2 = capture only and -3 = both. Other negative ranges could be used for other special purposes. Such as indicating the piece is an imitator (making the move generator switch to using the moves of the previously-moved piece). Or a Universal Leaper, which would require dedicated code for generating its moves.

Negative range could also be used to specify looping in the moveTable, allowing a group of legs to be repeated. When such a value is encountered the move generation would again do two things: next to continuing with the next leg, like it would normally do, it would also 'rewind' the currentLeg to an earlier leg, to continue from there. It would in fact not really be necessary to rewind to an earlier leg of the current path; we could also allow continuing with another leg. So that you can do branched trajectories. E.g. a Griffon could be described by four right-bending two-leg moves. The first leg of those could specify a negative range. So that if the first step finds an empty square, it can continue with the second leg, but also with a one-leg slide braching off to the left.