TSCP is too long ago for me to remember exactly what it has. But I see no reason to copy TSCP, what would be the point? It would make more sense to make something more modern.Mike Sherwin wrote: ↑Sun Feb 16, 2025 4:50 pm The first version should be equal to TSCP in features. What potential newbies are looking for is just the bare minimum that will play at "chess club" level, about 1800 human elo at most. I do not like pure PSTBL eval because engines that use that approach while they can be quite strong do not understand chess. I like TSCP's eval because it has some understanding. It is harder for me to win against TSCP than to win against the 2500 elo version of Leorik because Leorik while strong in engine elo is weak in positional understanding. Leorik NNUE is a different story that I have not looked at yet. Basically I think TSCP is a good starting point. But like you said it is poorly written. If TSCP was written well then there would be no need for Protozoa. These are just my thoughts. But I will go with a consensus if there are enough participants to have one. I would just go with Thomas Jahn's minimal chess but it is written in C# and C# has too big of a learning curve for the average newbie.
Amoeba : A Modern TSCP Type Engine
Moderator: Ras
-
- Posts: 28341
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Protozoa : A Modern TSCP Type Engine
-
- Posts: 965
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: Amoeba : A Modern TSCP Type Engine
You are correct. small code is better for this project. I just wanted a board[64] to make it easy to use some modern techniques like having a uint64_t for white pieces and black pieces to more efficiently traverse the board during move generation. TSCP looks at every square to find the pieces and I can't stand that. I remember that you had a method to avoid looking at every square but I can't remember what it is. Also in a future version I want to be able to make it fully bitboard. In my bitboard engines I always have a board[64]. That is the main reason that a vector/magnitude algo appealed to me.hgm wrote: ↑Sun Feb 16, 2025 5:33 pmIt seems you are trading simplicity for speed, here. And I wonder if that is consistent with your goal for this project. If you would be going for speed you would eventually end up with something like I discussed in the 'Mailbox Trials' threads.Mike Sherwin wrote: ↑Sun Feb 16, 2025 4:10 pmThis rings a bell. Didn't we discuss this very thing like 20 years ago? Well, I like it!
I think it can be improved. MoveTable can be accessed by fromSquare and pieceType. There can be a bit array (is that a correct term) with bits set to 1 for each possible direction from that square. That way only valid directions will be tested. You already have the range so that does not add anything more. We just change range to magnitude and we never have to check for EDGE_GUARD. It would be more data but not much compared to bitboards. Your thoughts?
Remember a 'view distance' table that gives you the distance to the board edge will heve to be initialized, which will require extra code. (Of course only executed at startup, so no impact on speed. But it still means extra code complexity.) Having a larger board array with edge guards is comparatively simple. You still need a move table, but this is quite small. And must be initialized data anyway, because it defines the game rules. Something like
Code: Select all
typedef struct { char step, range, capability; } MoveDescriptor; MoveDescriptor moveTable[] = { {16,1,MOVE_ONLY}, {15,1,CAPTURE_ONLY}, {17,1,CAPTURE_ONLY}, {0,0,0}, // white Pawn {-16,1,MOVE_ONLY}, {-15,1,CAPTURE_ONLY}, {-17,1,CAPTURE_ONLY}, {0,0,0}, // black Pawn {14,1,0}, {18,1,0}, {-14,1,0}, {-18,1,0}, {31,1,0}, {33,1,0}, {-31,1,0}, {-33,1,0}, {0,0,0}, // Knight {1,0,0}, {-1,0,0}, {16,0,0}, {-16,0,0}, {0,0,0}, // Rook {1,0,0}, {-1,0,0}, {16,0,0}, {-16,0,0}, {15,0,0}, {17,0,0}, {-15,0,0}, {-17,0,0}, {0,0,0}, // Queen and Bishop {1,1,0}, {-1,1,0}, {16,1,0}, {-16,1,0}, {15,1,0}, {17,1,0}, {-15,1,0}, {-17,1,0}, {0,0,0}, // King }; int firstDirection[] = {3, 1, 4, 8, 26, 17, 22, 31 };
-
- Posts: 965
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: Protozoa : A Modern TSCP Type Engine
TSCP is Alpha/beta Negamax with principle variation search. The Eval is PSTBLs, pawn structure and rooks on open files. That is about it.hgm wrote: ↑Sun Feb 16, 2025 5:44 pmTSCP is too long ago for me to remember exactly what it has. But I see no reason to copy TSCP, what would be the point? It would make more sense to make something more modern.Mike Sherwin wrote: ↑Sun Feb 16, 2025 4:50 pm The first version should be equal to TSCP in features. What potential newbies are looking for is just the bare minimum that will play at "chess club" level, about 1800 human elo at most. I do not like pure PSTBL eval because engines that use that approach while they can be quite strong do not understand chess. I like TSCP's eval because it has some understanding. It is harder for me to win against TSCP than to win against the 2500 elo version of Leorik because Leorik while strong in engine elo is weak in positional understanding. Leorik NNUE is a different story that I have not looked at yet. Basically I think TSCP is a good starting point. But like you said it is poorly written. If TSCP was written well then there would be no need for Protozoa. These are just my thoughts. But I will go with a consensus if there are enough participants to have one. I would just go with Thomas Jahn's minimal chess but it is written in C# and C# has too big of a learning curve for the average newbie.
Maybe TSCP was minimal for its day. How would we define minimal today? What should we include in a 1.0 version? Can we have beta 0.x versions that are more minimal? Maybe we should write it like we are writing a book and each beta version is like a chapter in a book getting more complex with each chapter. At some point I'd like to get started!
-
- Posts: 28341
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Amoeba : A Modern TSCP Type Engine
The conventional method to prevent a board scan for finding own pieces is to have a piece list next to the board. This piece list is indexed by piece number, and for each piece contains the number of the square it is on. That square in the board[] array then holds the piece number. To do something with all pieces of a given color (like move generation) then just requires looping through the piece list for that color (i.e. through 16 items rather than 64).
If the list gets very sparse even this becomes relatively inefficient. To prevent that you could use a uint32_t 'presence map' for indicating which pieces are present in the list, and only loop through those by bit-extraction. But then you would be trading simplicity for speed again.
Disadvantage is that the board does not directly tell you the piece type. But this could be added as another 'column' in the piece list. More efficient is to directly list all the quantities that depend on the piece type, though. Such as which PST or Zobrist array to use, the MVV/LVA sort keys, the point where to start in the moveTable... Eventually you would have to get to these through their tabulated address, and whether you index that table by piece type or by piece number makes no speed difference. The table would need 32 items rather than 13, but who cares?
And by cleverly assigning the piece numbers you can still derive some important conclusions from them. Like whether the piece is a Pawn (to provide an efficient test for whether a square is attacked by a Pawn; you would only have to look on two squares). And of course the King will have a unique piece number too, making it easy to test for King capture.
If the list gets very sparse even this becomes relatively inefficient. To prevent that you could use a uint32_t 'presence map' for indicating which pieces are present in the list, and only loop through those by bit-extraction. But then you would be trading simplicity for speed again.
Disadvantage is that the board does not directly tell you the piece type. But this could be added as another 'column' in the piece list. More efficient is to directly list all the quantities that depend on the piece type, though. Such as which PST or Zobrist array to use, the MVV/LVA sort keys, the point where to start in the moveTable... Eventually you would have to get to these through their tabulated address, and whether you index that table by piece type or by piece number makes no speed difference. The table would need 32 items rather than 13, but who cares?
And by cleverly assigning the piece numbers you can still derive some important conclusions from them. Like whether the piece is a Pawn (to provide an efficient test for whether a square is attacked by a Pawn; you would only have to look on two squares). And of course the King will have a unique piece number too, making it easy to test for King capture.
-
- Posts: 28341
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Protozoa : A Modern TSCP Type Engine
Well, PVS is already needlessly complex compaired to vanilla alpha-beta, for very little speed gain. And open files are basically a Pawn-structure thing as well.Mike Sherwin wrote: ↑Sun Feb 16, 2025 6:24 pm TSCP is Alpha/beta Negamax with principle variation search. The Eval is PSTBLs, pawn structure and rooks on open files. That is about it.
Maybe TSCP was minimal for its day. How would we define minimal today? What should we include in a 1.0 version? Can we have beta 0.x versions that are more minimal? Maybe we should write it like we are writing a book and each beta version is like a chapter in a book getting more complex with each chapter. At some point I'd like to get started!
I would add Mobility and some King Safety.
I like the idea of making this a 'modular' design, where you add modules step by step to make it stronger.
I would start with a negamax King-capture engine with PST eval, including QS and MVV/LVA capture sorting. Everything else can be an add-on.
-
- Posts: 965
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: Protozoa : A Modern TSCP Type Engine
Thanks! I'll get something going. I imagine though that you already have the code base to do this in short order. Please feel free to post more code or even to make the first beta version. I don't want to impose on your time though. I'll get started but if you beat me too it I wouldn't complain.hgm wrote: ↑Sun Feb 16, 2025 6:44 pmWell, PVS is already needlessly complex compaired to vanilla alpha-beta, for very little speed gain. And open files are basically a Pawn-structure thing as well.Mike Sherwin wrote: ↑Sun Feb 16, 2025 6:24 pm TSCP is Alpha/beta Negamax with principle variation search. The Eval is PSTBLs, pawn structure and rooks on open files. That is about it.
Maybe TSCP was minimal for its day. How would we define minimal today? What should we include in a 1.0 version? Can we have beta 0.x versions that are more minimal? Maybe we should write it like we are writing a book and each beta version is like a chapter in a book getting more complex with each chapter. At some point I'd like to get started!
I would add Mobility and some King Safety.
I like the idea of making this a 'modular' design, where you add modules step by step to make it stronger.
I would start with a negamax King-capture engine with PST eval, including QS and MVV/LVA capture sorting. Everything else can be an add-on.

-
- Posts: 28341
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Amoeba : A Modern TSCP Type Engine
Well, to make actual code you have to worry about the pesky details. Like how to encode promotions, e.p. capture and castling, and how to track castling rights.
Perhaps we should encode moves as
And make the move list element a union of an int and a Move. (So that you can sort the Moves by sortKey as if they were ints.) The special Effect could then contain the promotion piece type (if below a certain value), or flag the fact that something special has to be done when performing the move (like removing a piece to the left or right of the fromSquare, moving an additional rook or setting an e.p. square) for the next move.
Perhaps we should encode moves as
Code: Select all
typedef struct {
unsigned char sortKey, specialEffect, fromSquare, toSquare;
} Move;
-
- Posts: 965
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: Amoeba : A Modern TSCP Type Engine
Seems simple enough. My question would be what is the sort key? (VV - VA) / 4 so it will fit in a char or is it something else?hgm wrote: ↑Sun Feb 16, 2025 7:13 pm Well, to make actual code you have to worry about the pesky details. Like how to encode promotions, e.p. capture and castling, and how to track castling rights.
Perhaps we should encode moves as
And make the move list element a union of an int and a Move. (So that you can sort the Moves by sortKey as if they were ints.) The special Effect could then contain the promotion piece type (if below a certain value), or flag the fact that something special has to be done when performing the move (like removing a piece to the left or right of the fromSquare, moving an additional rook or setting an e.p. square) for the next move.Code: Select all
typedef struct { unsigned char sortKey, specialEffect, fromSquare, toSquare; } Move;
-
- Posts: 28341
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Amoeba : A Modern TSCP Type Engine
I often take something like vv[victim] - av[piece], where piece and victim are piece numbers, and the vv[] and av[] tables contain chars.
But I am always wrestling with how to handle promotions; there doesn't seem to be a universally good way to do this, and I always end up with some compromise. When all properties of a piece are tabulated indexed by piece number, it would take a quite some effort (and code, which is worse, as promotions are rare in the tree, so that speed is not really an issue) to change the type of a given number. So what you would want to do is assign a new number. Or use the type as an extra level of indirection, where you first look up the type indexed by number, and use that to index all property tables (PST, Zobrist, vv, av, firstDirection, ...).
For changing the number you would need spare entries in the piece list, to make it efficient with pre-initialized properties of the promotion piece. If you really want to allow 10 Knights, 10 Bishops, 10 Rooks or 9 Queens, your piece list would need 48 entries per color. This could of course be done, e.g. by encoding white pieces as 01xxxxxx, and black pieces as 10xxxxxx (binary), while edge guards would be 11000000, and empty squares 0. That leaves room for 64 piece numbers per color. And when sideToMove can take values 0x40 or 0x80, you can use the test (victim & sideToMove) to test for an own piece and an edge guard at the same time. (Both of which should cause rejection of the attempted move.)
Promotions could simply add 10, 20, 30, or 39 to the piece number of the promoting Pawn, as each Pawn would have its private slots for all possible promotion choices. Disadvantage is that the piece list becomes almost as sparse as the board, so that there is not much advantage of having it, and you might as well have stored the piece types directly in the board. (Which would make promotion trivial: just change the code on the board.) This problem could of course be ameliorated by putting the promotion slots all after the initially occupied part of the piece list, Queens in front, so that the piece list only has to be expanded after a promotion takes place, and not by very much if it is a promotion to Queen. (By that time the game is almost certainly decided, and speed is no longer an issue.) Or you could keep a 64-bit presence mask for each color, to efficiently loop through a sparse piece list by bit extraction. (Extra stuff to update in MakeMove, though...)
I guess in this case I would go for the extra indirection, using pieceType[pieceNumber] as an index to all the property tables. And then old-fashioned looping through the piece list, where some invalid square number would indicate the piece is not present. Promoted Pawns would then keep their number, but get the corresponding type changed. A disadvantage is that you cannot easily loop through all pieces of a given kind anymore, e.g. for doing a check test. But I guess that is the price we have to pay for simplicity.
The specialEffect field of the Move could then be used in a switch statement to decide what to do after the normal part of the move has been done: promote the Pawn, remove the e.p. victim, set the e.p. square, or move the Rook.
But I am always wrestling with how to handle promotions; there doesn't seem to be a universally good way to do this, and I always end up with some compromise. When all properties of a piece are tabulated indexed by piece number, it would take a quite some effort (and code, which is worse, as promotions are rare in the tree, so that speed is not really an issue) to change the type of a given number. So what you would want to do is assign a new number. Or use the type as an extra level of indirection, where you first look up the type indexed by number, and use that to index all property tables (PST, Zobrist, vv, av, firstDirection, ...).
For changing the number you would need spare entries in the piece list, to make it efficient with pre-initialized properties of the promotion piece. If you really want to allow 10 Knights, 10 Bishops, 10 Rooks or 9 Queens, your piece list would need 48 entries per color. This could of course be done, e.g. by encoding white pieces as 01xxxxxx, and black pieces as 10xxxxxx (binary), while edge guards would be 11000000, and empty squares 0. That leaves room for 64 piece numbers per color. And when sideToMove can take values 0x40 or 0x80, you can use the test (victim & sideToMove) to test for an own piece and an edge guard at the same time. (Both of which should cause rejection of the attempted move.)
Promotions could simply add 10, 20, 30, or 39 to the piece number of the promoting Pawn, as each Pawn would have its private slots for all possible promotion choices. Disadvantage is that the piece list becomes almost as sparse as the board, so that there is not much advantage of having it, and you might as well have stored the piece types directly in the board. (Which would make promotion trivial: just change the code on the board.) This problem could of course be ameliorated by putting the promotion slots all after the initially occupied part of the piece list, Queens in front, so that the piece list only has to be expanded after a promotion takes place, and not by very much if it is a promotion to Queen. (By that time the game is almost certainly decided, and speed is no longer an issue.) Or you could keep a 64-bit presence mask for each color, to efficiently loop through a sparse piece list by bit extraction. (Extra stuff to update in MakeMove, though...)
I guess in this case I would go for the extra indirection, using pieceType[pieceNumber] as an index to all the property tables. And then old-fashioned looping through the piece list, where some invalid square number would indicate the piece is not present. Promoted Pawns would then keep their number, but get the corresponding type changed. A disadvantage is that you cannot easily loop through all pieces of a given kind anymore, e.g. for doing a check test. But I guess that is the price we have to pay for simplicity.
The specialEffect field of the Move could then be used in a switch statement to decide what to do after the normal part of the move has been done: promote the Pawn, remove the e.p. victim, set the e.p. square, or move the Rook.
-
- Posts: 965
- Joined: Fri Aug 21, 2020 1:25 am
- Location: Planet Earth, Sol system
- Full name: Michael J Sherwin
Re: Amoeba : A Modern TSCP Type Engine
For simplicity and speed we can have a very small MoveGen loop that calls functions by function pointers indexed by type. Each little function exactly takes care of that type. Pawn promotions, ep-captures and castling can be handled using pseudo pieces.hgm wrote: ↑Sun Feb 16, 2025 8:31 pm I often take something like vv[victim] - av[piece], where piece and victim are piece numbers, and the vv[] and av[] tables contain chars.
But I am always wrestling with how to handle promotions; there doesn't seem to be a universally good way to do this, and I always end up with some compromise. When all properties of a piece are tabulated indexed by piece number, it would take a quite some effort (and code, which is worse, as promotions are rare in the tree, so that speed is not really an issue) to change the type of a given number. So what you would want to do is assign a new number. Or use the type as an extra level of indirection, where you first look up the type indexed by number, and use that to index all property tables (PST, Zobrist, vv, av, firstDirection, ...).
For changing the number you would need spare entries in the piece list, to make it efficient with pre-initialized properties of the promotion piece. If you really want to allow 10 Knights, 10 Bishops, 10 Rooks or 9 Queens, your piece list would need 48 entries per color. This could of course be done, e.g. by encoding white pieces as 01xxxxxx, and black pieces as 10xxxxxx (binary), while edge guards would be 11000000, and empty squares 0. That leaves room for 64 piece numbers per color. And when sideToMove can take values 0x40 or 0x80, you can use the test (victim & sideToMove) to test for an own piece and an edge guard at the same time. (Both of which should cause rejection of the attempted move.)
Promotions could simply add 10, 20, 30, or 39 to the piece number of the promoting Pawn, as each Pawn would have its private slots for all possible promotion choices. Disadvantage is that the piece list becomes almost as sparse as the board, so that there is not much advantage of having it, and you might as well have stored the piece types directly in the board. (Which would make promotion trivial: just change the code on the board.) This problem could of course be ameliorated by putting the promotion slots all after the initially occupied part of the piece list, Queens in front, so that the piece list only has to be expanded after a promotion takes place, and not by very much if it is a promotion to Queen. (By that time the game is almost certainly decided, and speed is no longer an issue.) Or you could keep a 64-bit presence mask for each color, to efficiently loop through a sparse piece list by bit extraction. (Extra stuff to update in MakeMove, though...)
I guess in this case I would go for the extra indirection, using pieceType[pieceNumber] as an index to all the property tables. And then old-fashioned looping through the piece list, where some invalid square number would indicate the piece is not present. Promoted Pawns would then keep their number, but get the corresponding type changed. A disadvantage is that you cannot easily loop through all pieces of a given kind anymore, e.g. for doing a check test. But I guess that is the price we have to pay for simplicity.
The specialEffect field of the Move could then be used in a switch statement to decide what to do after the normal part of the move has been done: promote the Pawn, remove the e.p. victim, set the e.p. square, or move the Rook.
CASTLING
A WK on the board can castle. A Wk on the board cannot castle. A WR can castle but a Wr cannot castle. No castling rights needed. Just when a WK or WR moves it becomes a Wk or Wr. When it un moves it becomes a WK or WR again.
EN-PASSANT and PROMOTION
A WP on rank 5 becomes a WP5. Actually there are 6 pseudo pawns--WP2, WP3, WP4, WP5, WP6, WP7. WP3,4,6 call the same function. WP2 calls the double move. WP5 calls the EP pawn code and WP7 calls the promotion code and the promotion code puts all promotion possibilities in the move list. MakeMove and UndoMove can work in the same way. There is more code but all the little pesky details just don't cause any problems.
