Amoeba : A Modern TSCP Type Engine

[catugocatugocatugo]

Maybe after you achieve this first goal, I can help with some coding. I don't want to do the very basics as I'm not very careful nor that experienced. But I think we can find things I can do.

[hgm]

Still something we did not discuss: I suppose we want the PST to interpolate between an opening and an end-game value. For the gamePhase we could use minors + 3*Rooks + 6*Queens; then it would run from 0 to 32.

An efficient way to do this is to store the PST elements as 32-bit integers, with value endGame*(1<<19) + (opening - endGame), where opening and endGame are values that would fit in a (signed) 13-bit integer. By multiplying the with 1 + gamePhase*(1<<14) this would give:

endGame*gamePhase*(1<<33) + endGame*(1<<19) + (opening - endGame)*gamePhase*(1<<14) + (opening - endGame).

The first term would be clipped off the result by overflow. And the last term is negligible compared to the others, and will disappear when we shift the result right by 19 bits. That would leave

endGame + ((opening - endGame)*gamePhase >> 5),

where the right-shift by 5 is division by 32. So to obtain the interpolated evaluation we calculate:

eval = pstSum*(1 + (gamePhase << 14)) >> 19.

Instead of incrementally keeping track of gamePhase, we could already track (1 + (gamePhase << 14)) as a 32-bit integer, by using 1<<14, 3<<14 and 6<<14 as minor, Rook and Queen weights. With the given formula it would even be possible to specify the game-phase weights of the pieces twice as precise, e.g. 3<<13, 5<<13 and 10<<13. The result has a precision of 13 bits, and could thus run from -4096 to +4095. Which seems good enough for a score difference when it represents centi-Pawn. (It could overflow when one side is more than 5 Queens ahead. But it is unlikely that it would not see a checkmate in that case, to get a mate score that would trump the correct score in any case. And even then, it would just make the player that is ahead refrain from promoting to a 5th Queen, and try to win with justthe 4. Which should hardly be a problem.)

[catugocatugocatugo]

@hgm,
I can't say I understand all of the things you say. But once the basics are done, I think I can help. This was what I was going for. I have worked a bit with ChessV1 and a bit less with ChessV2 (I don't know C#). Greg Strong wanted to make things on his own, and I understood that, as the things I wanted were from fairly difficult to very difficult (ie the joker or imitator). But after the basics are done, I can easilly treat the coding more like scripting than actual programming, especially in this didactic engine. I'll manage. In my programs I usually I get stuck because I second guess myself and then complicate stuff, and then cannot exit the maze I find myself in. This is why I need, for lack of a bettter word, an architect.
By the way, about the joker. I do not think you can make this program with the joker in mind, besides maybe leaving some space in the FEN for the last piece moved. There will never be a good way to optimize such a complicated concept in a didactic environment especially. It will always slow down the program in a serious manner. But I don't panic. I have already accepted the later when concieving the rules of my games. I'll probably still need your guidance when branching away for that. But than when the time comes and which is not soon.

[Mike Sherwin]

I also feel that I can be of some help once the first version is out.

What about the name Probie?

"A "probie" is an informal term for a probationer."

[hgm]

I need some feedback, on whether what I have in mind is exceptionally educational or obfuscated madness:

If there is a hash move you have to dig it out of the move list; when you would just put it in front of the list the duplicat from the move generator would cause it to be searched twice. (I use a move list that can grow in both directions, so that the move generator can already place the captures in front.) You can hope the second search of it immediately cuts off by a hash hit on the result of the first, in the daughter node. But this is an uncertain method (the hash entry could have been replaced), and would still cause significant overhead. So you could loop through the move list, comparing all moves to the hash move, and then remove the duplicat.

But a very general principle in engine design is that you should not do things before they are actually needed. The hash move should be a cutoff in 90% of the cases, and then you would never get to the duplicat, or in fact any move of the generated list. So I moved the test for being the duplicat of the hash move to just before the move will be made and searched, so it could continue with the next move in the list.

The problem is that in this place the test would also intercept the hash move you put in front of the list, so that it would not be searched at all. This can be fixed by distinguishing the duplicat from the intended (leading) one through the sortKey included in the move format: the duplicat gets whatever the move generator gave it (e.g. MVV/LVA), while you give the one you placed in front sortKey = 0xFF, the largest at all. (Not that any sorting has to be performed on it, as you already placed it in front, but just for recognition.) So only a hash move with sortKey != 0xFF will be skipped.

Now the search will do Internal Iterative Deepening if it has to be searched much deeper than the result you got from the hash table, and every iteration should start with the best move of the previous iteration. So if that was not the first move, it would have to be placed in front of the list as well. Just copying it there would again create a duplicat; you somehow have to remove the original from the list. You could do that by moving up all following moves one place, but that could be a lot of work. So I just want to 'zap' the original, by replacing it by an invalid move, which can be recognized and skipped when the next iteration runs through the move list.

Since there already was code for skipping duplicats of the hash move, this could be done by replacing the moves you want to zap by another copy of the hash move (with sortKey != 0xFF). Then you don't need to put in an extra test for zapped moves; you can just leave it at:

Code: Select all

  if(MOVE_PART(move) == MOVE_PART(hashMove) && move.sortKey != 0xFF) continue;

And for moving the best move to front:

Code: Select all

  if(nrOfBestMove != 0) {
    moveStack[--firstMove] = moveStack[nrOfBestMove]; // place copy in front
    moveStack[nrOfBestMove] = hashMove; // zap original
  }

Does that sound like an acceptable method?

[Mike Sherwin]

I need some feedback, on whether what I have in mind is exceptionally educational or obfuscated madness:

Somewhere in the middle. It is probably a bit much for the purpose of this project. For chapter 1 I don't think a transformation hash is necessary. Just a bare minimum engine that plays at about 1800 elo that is easy to understand. Just a "good seed" that we can grow into a magnificent tree, later.

ChatGPT
This is certainly a clever and compact solution, but it does come with some caveats:

Assumption on sortKey values: The trick relies on the guarantee that a move generated normally will never have a sortKey of 0xFF. If that invariant holds, then distinguishing the “leading” hash move from a duplicate is safe.

Minimizing overhead: The idea is attractive because it avoids scanning the entire move list for duplicates—especially when the hash move is usually a cutoff (around 90% of the time). Only in the rarer cases does it need to “zap” the duplicate, which minimizes extra work.

Code clarity vs. cleverness: While the method is efficient, it is somewhat non-obvious. Clear documentation is essential so that future maintainers understand why you’re “zapping” moves by replacing them with a hash move copy (and how the sortKey is used to filter them).

Robustness in iterative deepening: The approach to move the best move to the front and then zap the original copy is efficient. Just ensure that the handling of these “zapped” entries is consistent across iterations, and that any potential edge cases (like multiple zappings or changes in move ordering later) are well-tested.

Overall, if your benchmarks show that this approach saves significant time without compromising correctness, it is an acceptable optimization. Just ensure that the invariants (especially regarding the sortKey) are well maintained and documented.

[hgm]

TSCP might have no transposition table, but it does learn from its earlier iterations. Otherwise Iterative Deepening would have very little benefit, and alpha-beta would be very inefficient in all iterations. The way it learns is that it remembers the PV, and then in the next iteration searches the PV first. That is, it treats the PV moves at the various ply levels exactly like it would treat a hash move in the nodes that are on the old PV, and searches it first.

Codewise this is very similar to having a hash table. And TSCP still calculates a Zobrist hash key, for the purpose of repetition detection. The main difference is that it has a 'hash table' of only some 100 moves indexed by the ply counter, instead of millions of moves indexed by a Zobrist key. And it still needs a somewhat complex algorithm to get the PV. (E.g. a triangular array.)

Having a real hash table also simplifies repetition detection: you just lock it in the entry for the newly reached position in the hash table table by setting the BUSY flag, whenever you make a move at game level. Then each hit on it would return a draw score. No need to keep a game history of hash keys, through which you have to loop until you reach the last irreversible move. Instead of finding the repeating key by searching through the array you find it by hashing, as the stored signature.

All in all I think having the hash table is simpler, and doing it like TSCP just needlessly drives up code complexity.

[catugocatugocatugo]

hgm,

I do not think it is overdoing as long as the comments/documentation is clear. After all it is a modern didactic engine.

[hgm]

I was thinking about another design that might or might not be a bit over the top. In my engines I often use the method that I call "exit at the first floor". The idea of this is that you make an alternative return point in the node of the search, just before it calls UnMake(). This would then leave the game state as it is after making the move it has just searched, instead of taking that move back. With that feature the root search can also be used to perform an input move: you just perform a shallow (e.g. d=1) search with the request that when it has searched the input move in the root, and does not score it as an illegal move, it returns before doing UnMake().

The advantage of this is that you automatically augment the input move with any missing information. Like that it was an e.p. capture, or a castling. You cannot directly feed the input move, which is usually just a {fromSquare, toSquare} pair, to the MakeMove() used by the search; the latter counts on the specialEffects field of the move for recognizing it as an e.p. capture or castling. So you would then need extra code for recognizing input moves as such, and reconstructing the specialEffects field. When you use the search routine for performing the move, MakeMove() would always act on a completely described move from the move list, but recognize that move as the input move just by comparing the from- and to-squares. This can be done with fairly straightforward code, inserted just before UnMake():

Code: Select all

  if(ply == 0 // we are in root
     && score > -INFINITY // current move was legal
     && move.fromSquare == inputFromSquare && move.toSquare == inputToSquare) { // and matches input move
    return OK_SCORE;
  }
  UnMake(move, &u);

The returned score would ly outside the normal range, and indicate to the caller that the input move was legal and has been performed. Any other returned score would indicate the input move was not encountered in the generated move list for the position, or was illegal by exposing the King. So you get legality testing of the input move for free.

Note that this assumed there is no dedicated SearchRoot() function, but that the root is handled by the same routine as all other nodes. The Internal Iterative Deepening makes the handling of other nodes so similar to that of the root, that this can be easily done. The tiny differences that remain can be added in if-clauses testing for ply == 0. These provide virtually no overhead in the search, as branch prediction would know that the clause is 'never' executed; the only mispredictions would occur in the root node.

Other dedicated root-node tasks, such as reading the clock, could be hidden in that same if-clause before UnMake(). E.g. when time is up it could set depth = iterDepth, to declare the current iteration the final one. If it is confident the current partially executed iteration has already provided a good-enough move (i.e. score not much lower than that of the previous iteration), it could even force termination of the current loop over moves, by setting moveStackPointer = moveNr, to fake we reached the end of the move list already.

You could even arrange it such that timing out would automatically perform the best move found by the search, by copying this move to the input move, and ordering a new d=1 iteration to perform that:

Code: Select all

if(ply == 0) { // we are in root; do some root-specific stuff
  // exit at first floor, when current move must remain performed
  if(score > -INFINITY // current move was legal
     && move.fromSquare == inputFromSquare && move.toSquare == inputToSquare) // and matches input move
    return OK_SCORE; // signals the move was legal and has been done
  time = ReadClock() - startTime;
  if(time > timeLimit) { // search timeout
    if(replyDepth > 0) { // we are still doing deep searches in extended time
      inputFromSquare = moveStack[nrOfBestMove].fromSquare;
      inputToSquare   = moveStack[nrOfBestMove].toSquare;
    }
    iterDepth = 0; depth = 1; // this causes one more d=1 iteration to be done for performing the move
    if(alpha > oldScore - 50) moveStackPointer = moveNr + 1; // abort this iteration by clipping off remaining moves
  }  
}
UnMake(&u);

[Edit] This code only works as intended when it goes after the updating of alpha and nrOfBestMove with the results from the current move. Normally I place that update after UnMake(), so that (in case of a beta cutoff) it can break from the move loop without having altered the game state. But the beta cutoff can also be achieved in a delayed way, by setting moveNr = moveStackPointer. That would suppress the upcoming iterations of the loop over moves, but still finish the current one for unmaking the move. So that there is no harm in doing that before the root code and UnMake().

[catugocatugocatugo]

@hgm,

Two matters. FIrst: After you have some code you can send it to me, to see if I understand it, giving the comments, of course. This is a good check for it's didactic properties, as I am not that experienced.
Second:About the NNUE. I have said we can try small neural networks at the output of the evaluation function. I was wrong there, probably, as you have said a NNUE is the modern way to approach this problem. But maybe we can think about the later hidden layers. I have talked about a RBFNN (Radial Basis Function Neural Network) because they tend to perform well when the input is clustered, and chess inputs tend to cluster- as for example you rarelly push the pawns ahead of the king. I am reading right now the chessprogrammingwiki article on the matter. Hopefully I'll understand enough.