Amoeba : A Modern TSCP Type Engine

[Mike Sherwin]

Let's do it!

I suggest a vector based approach. That way we can have an 8x8 board and we can migrate to bitboard later.

An example vector in pseudocode might be:

Code: Select all

int vecNW[64];

void Initialize() {
	for (int sq = 0; sq < 64; sq++) {
		int dx, dy;
		int x = sq & 7;
		int y = sq / 8;
		vecNW[sq] = 0;
		for (dx = -1, dy = 1; x + dx >= 0 && y + dy <= 7; vecNW[sq]++, dx--, dy++);
	}
}

void Gen() {
/*
	case WB:
        count = vecNW[fs];
		i = 0;
		while (count) {
		    i++;
			ts = fs + i * 7;
			if (board[ts] == BLACK) { Add(fs, ts); break;}
			if (board[ts] == EMPTY) { Add(fs, ts); count--;}
		}
		break;
*/
}

The benefits of the vector method are no explicit on board test needed, it looks simple, we can have some bitboards like white and black pieces to process the board quickly and moving to full bitboards for some future version should also be simple.

Does anyone have an opinion about a project like this for creating a modern TSCP type engine?

[mar]

hey Mike,

I'd perhaps change the name because there already is an engine called Amoeba (author Richard Delorme)

other than that - bitboards or not (I like them a lot and you're an expert when it comes to bitboard movegen techniques),
probably vector-based is fine for learning the very basics.
I guess a simple psqt-only eval would do, alphabeta + qs, nothing fancy (for didactic purposes)

I'm not sure about input - whether to poll within search (seems ugly) or use a separate search thread
or simply ignore commands during search (probably this, because the didactic engine should be as simple as possible (but not obfuscated)
to show the basic techniques)

IIRC someone was asking for a "hello world" chess program in another thread, so there probably would be interest out there

and as usual good luck with your project

[Mike Sherwin]

hey Mike,

I'd perhaps change the name because there already is an engine called Amoeba (author Richard Delorme)

other than that - bitboards or not (I like them a lot and you're an expert when it comes to bitboard movegen techniques),
probably vector-based is fine for learning the very basics.
I guess a simple psqt-only eval would do, alphabeta + qs, nothing fancy (for didactic purposes)

I'm not sure about input - whether to poll within search (seems ugly) or use a separate search thread
or simply ignore commands during search (probably this, because the didactic engine should be as simple as possible (but not obfuscated)
to show the basic techniques)

IIRC someone was asking for a "hello world" chess program in another thread, so there probably would be interest out there

and as usual good luck with your project

Thanks Martin,

Your comment mostly agrees with my thinking. But I don't want it to be just my project. I think the community needs to do something like this. I would like the Eval() to be on about the same level as TSCP just so beginners can get an idea how to approach that. Besides someone can make a NNUE version later. I did see the other thread. That is why I made this thread. I like the idea of an input thread because it would be more modern. When TSCP came out multi-threaded engines were not very common. Also I want the engine to be in a class. That is because Tom Kerrigan said it is easy to make an engine multi-threaded, just wrap it in a class. I personally don't know about that but I'll just take his word for it. Also thanks for this, "you're an expert when it comes to bitboard movegen techniques" but I'm just a little creative and a whole lot stubborn and I don't like giving up. Did you look at my latest bitboard code?



Okay I'll change it to Protozoa.

[mar]

yes, that would be nice. question is how to get people involved. motivation/time is a scarce resource.
I think people prefer to go to discord these days, or maybe that's just what discord kids want us to believe (yet they keep coming back

another thing is which language to use? I think C is still valuable to learn (C11 looks like they added some pretty cool stuff),
but apart from C++ there are many other languages to choose from.
D, Rust, Zig, Jai, Odin, Nim and I'm sure I forgot many of the new/modern ones. some people still prefer managed, like C#, Java, Go.
some still do Pascal, there are Javascript engines out there. I'd stay away from python for perf reasons, because two orders of magnitude slower isn't really cool.

I've noticed another of your projects after SISSY bitboards, but I'm not as active here as I used to be in the past so I don't know how it went.
your ideas are always fresh and interesting. unfortunately many don't appreciate creativity it seems.

it's a pity that movegen itself along with its speed contributes very little elo-wise, even though it's a very interesting and essential part of any engine.
I've seen that some engines even use third-party libraries for that - which is missing the joy of having to debug a move generator

[hgm]

If this is meant as an educational engine from which people could actually learns useful stuff, I would recommend to not use a move generator with a separate switch case for every piece and color, but just a table-driven one, which uses the same range loop for every piece. (BTW, note that the one you commented out jumps over white pieces...) I am also not that keen on tabulating ranges for every board square and direction; that doesn't really strike me as simple (and you would also need extra code to initialize all those tables). I think it would be much better to use a 10x12 or 16x12 (0x88) board. TSCP is an especially bad example in this respect, which gives you the worst of both worlds: it uses both a 64-square board and a larger board with edge guards, and then translate square numbers back and forth between those.

Code: Select all

int direction = firstDirection[pieceType];
while((step = moveTable[direction].step)) {
  int range = moveTable[direction].range;
  toSquare = fromSquare;
  do {
    toSquare += step;
    victim = board[toSquare];
    if(victim == EMPTY_SQUARE) {
      if(moveTable[direction].capability & CAPTURE_ONLY) break;
      AddMove(fromSquare, toSquare);
    } else {
      if(victim == EDGE_GUARD) break;
      if(COLOR(victim) == sideToMove) break;
      if(moveTable[direction].capability & MOVE_ONLY) break;
      AddCapture(fromSquare, toSquare, victim);
      break;
    }
    direction++;
  } while(--range);
}

[hgm]

Do you already have an idea about which features should be included?

E.g. for search:
Hash table (always replace?)
MVV/LVA sorting
Killers
Null move
LMR

For evaluation:
PST
Material (hashed)
Pawn structure (hashed)
Drawishness

[Mike Sherwin]

Code: Select all

int direction = firstDirection[pieceType];
while((step = moveTable[direction].step)) {
  int range = moveTable[direction].range;
  toSquare = fromSquare;
  do {
    toSquare += step;
    victim = board[toSquare];
    if(victim == EMPTY_SQUARE) {
      if(moveTable[direction].capability & CAPTURE_ONLY) break;
      AddMove(fromSquare, toSquare);
    } else {
      if(victim == EDGE_GUARD) break;
      if(COLOR(victim) == sideToMove) break;
      if(moveTable[direction].capability & MOVE_ONLY) break;
      AddCapture(fromSquare, toSquare, victim);
      break;
    }
    direction++;
  } while(--range);
}

This 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?

[Mike Sherwin]

Do you already have an idea about which features should be included?

E.g. for search:
Hash table (always replace?)
MVV/LVA sorting
Killers
Null move
LMR

For evaluation:
PST
Material (hashed)
Pawn structure (hashed)
Drawishness

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.

[hgm]

This 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?

It 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.

Remember a 'view distance' table that gives you the distance to the board edge will have 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. And if you use clever piece encoding you can make it such that testing for edge guards and friendly pieces can be done in the same test. 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 };

(Note that range 0 effectively means infinit range in the presented code.)

BTW, if you really want to go for view distances it might be better to go for a dynamic view-distance table, which does not hold the distance to the edge, but to the nearest obstacle. Whether that is edge or piece. This has the advantage that you can very easily make a capture-only generator: for slider you would just look up where the potential target is, without having to step through all empty squares. It is comparatively easy to incrementally update such a table.

[Mike Sherwin]

yes, that would be nice. question is how to get people involved. motivation/time is a scarce resource.
I think people prefer to go to discord these days, or maybe that's just what discord kids want us to believe (yet they keep coming back

another thing is which language to use? I think C is still valuable to learn (C11 looks like they added some pretty cool stuff),
but apart from C++ there are many other languages to choose from.
D, Rust, Zig, Jai, Odin, Nim and I'm sure I forgot many of the new/modern ones. some people still prefer managed, like C#, Java, Go.
some still do Pascal, there are Javascript engines out there. I'd stay away from python for perf reasons, because two orders of magnitude slower isn't really cool.

I've noticed another of your projects after SISSY bitboards, but I'm not as active here as I used to be in the past so I don't know how it went.
your ideas are always fresh and interesting. unfortunately many don't appreciate creativity it seems.

it's a pity that movegen itself along with its speed contributes very little elo-wise, even though it's a very interesting and essential part of any engine.
I've seen that some engines even use third-party libraries for that - which is missing the joy of having to debug a move generator

C/C++ is simply the most popular language at this time. QB64 is a great version of BASIC and it is totally free. And it is a compiled BASIC, compiled to C++ and then compiled to an exe. It seems to produce very fast executables. Just like TSCP has been translated into multiple languages I think people will do the same for Protozoa. Maybe we should just name it Proto? Another cute language is Euphoria. Euphoria is an interpreter but also has a Euphoria to C translator for the release version. Supposedly now there is a Python compiler. I can't remember the name. Personally I don't get Python. C to me is pure simplicity. When I wrote RomiChess (in C) it would not run in debug mode and I never figured out why. But C was so easy that I did not need a debugger. Careful design prevents most bugs. I did come to C via 32bit assembler. So C pointers were easy for me.