Very compact pseudolegal movegenerator - help me compact it more [C++]

[dangi12012]

So I was playing around with mailslot engines - and for the pseudolegal movegenerator I created a universal lookup table (no index is calculated all 8 ray indices and lookup for every square is already in memory).

This has the advantage that you dont ever need to check for "off board moves" and can get almost branchfree because the piecetype 0..11 is also just an index onto the square. So the main lookup is just a int** [64][12] with an extra config that tells the algorithm how to behave.

Move loops can be breaking (rays) or not. And this movegenerator does everything including castling and enpassant. pawn pushes and all the stuff is handled correctly. Pawns can only attack enemies diagonally, Pawns can only move forward in empty squares and can only push 2 squres on first rank etc.
The content or rays is not important here since it already works.

I want to make this code more compact so insights are appreciated: https://godbolt.org/z/bKnnzsb3o

Code: Select all

#define _move(FROM, TO) *movelist++ = ((FROM << 6) | TO)
#define Color(X) (('_' > X) - (X > '_')) //Branchless fen piece to color -1..0..1

extern int** rays[64][12]; //Lookups and rays - ep and castling included
extern char board[64];
extern int piecetable[128]; //FEN char to 0..11 int

extern int ep, castle, halfmove, fullmove;
int movecolor;

const int raycnt[12] = { 3,3,1,1,4,4,4,4,8,8,3,3 };
enum mov { move_slide = 1, square_enemy = 2, square_empty = 4, square_ep = 8, move_cstl = 16 };

extern bool Legal(int kingcolor, int from, int to); //Query into 

void GetMoves(int sq, int piece, int*& movelist)
{
	//pP nN bB rR qQ kK
	int** begin = rays[sq][piece];
	int* end = *(begin + raycnt[piece]);
	int* ray;

	while((ray = *begin++) != end)
	{
		int* end = ray + (ray[-1] & 0xFF);
		int config = (ray[-1] >> 8);
		int co = Color(board[sq]);
		
		while (ray != end)
		{
			int to = *ray++;
			char tpiece = board[to];
			int ce = Color(tpiece);
			if ((config & square_empty) && ce == 0) _move(sq, to);
			else if ((config & square_enemy) && ce != co) _move(sq, to);
			else if ((config & square_ep) && ep == to) _move(sq, to);
			else if ((config & move_cstl) && Legal(co, sq, to)) _move(sq, to);
			else if (config & move_slide) break;
		}
	}
}

int main(){
    static int moves[256];
	int* movelist = moves;

	for (int i = 0; i < 64; i++)
	{
		char piece = board[i]; int color = Color(piece);
		if (color == 0 || color == movecolor) continue;
		GetMoves(i, piecetable[piece], movelist);
	}
    
}

[dangi12012]

Also im unsure if its better to have

Code: Select all

void function(int*& movelist) {movelist++}

vs

Code: Select all

int* function(int* movelist) {movelist++
return movelist;}

[hgm]

This is a bit reminiscent of how the old GNU Chess (was it 4 or 5?) did it. It had two list indexed by piece type, from-square, and to-square of the last generated move, which would contain the next to-square to try. One in case this last square was empty, the other for when it was occupied (skipping to the next direction/ray). This eliminated the overhead of a loop over directions, and avoided any off-board attempts. But, being a mailbox engine, it of course did have to test for every square what the occupant was.

I am not sure which problem you think you are solving. Moves will have to be sorted before they can be searched. Pre-computed lists cannot be sorted. So at some point you would have to copy that list to a node's local storage, where you can then sort it. Or prepare a list with pointers to the pre-computed list private to the node, and sort those.

[dangi12012]

This is a bit reminiscent of how the old GNU Chess (was it 4 or 5?) did it. It had two list indexed by piece type, from-square, and to-square of the last generated move, which would contain the next to-square to try. One in case this last square was empty, the other for when it was occupied (skipping to the next direction/ray). This eliminated the overhead of a loop over directions, and avoided any off-board attempts. But, being a mailbox engine, it of course did have to test for every square what the occupant was.

I am not sure which problem you think you are solving. Moves will have to be sorted before they can be searched. Pre-computed lists cannot be sorted. So at some point you would have to copy that list to a node's local storage, where you can then sort it. Or prepare a list with pointers to the pre-computed list private to the node, and sort those.

The precomputed list has nothing to do with this thread - but i have to test if memcpy is faster than a loop over each individual bit. You are right about sorting. Is while(bsr(x)) {makemove()} slower than memcpy(movelist, movesource[config])

This thread:
Im trying to describe chess in the most generic way possible. To find hidden truths by optimizing. And now i need help to compact the algorithm further if possible.
This is a successfull removal of all index calculation in mailslot engines and have the core algorithm as lean as possible.
What remains are two things: What to look for in a target square - and if to break on a failed attemt.

• Pawn push on first rank: move_slide | square_empty
  Pawn attacks: square_enemy
  Generic slider: move_slide | square_enemy | square empty
  King moves: square_enemy | square_empty
  King castling: move_slide | move_cstl

So a sliding move the loop gets breaked if condition is not met. And the condition is variable. For a pawn pushes its square_empty, for castling its legality, for a slider it is enemy or empty. For non sliders the loop is not breaked.
So really all you need for mailslot chess is a list of target squares (per ray) + a lookup list and 5 bits describing what to do.

[hgm]

Before making any compromises in what to optimize at the expense of what, it might be good to have an idea on what tasks an engine spends most of its time. The statistics in the tree I used as reference search in the mailbox trials was such that some 85% of all nodes were QS nodes, where only captures needed to be generated. And 94% of the moves that were made (not counting null moves) were captures; only 6% non-captures.

So it seems that to have a beneficial impact on speed, you should focus on fast ways to generate and sort the captures. Even when that goes at the expense of slowing down generation or making of non-captures.

[phhnguyen]

It is very strange you want to compact instead of optimizing for speed.

I am still not clear if you want to compact the source code or binary code. Some compilers are clever (or dumb) enough, making some efforts of programmers to optimize be the same. Sometimes you may get what you need just by setting compiling flags and/or changing the compiler.

Just a few tricks I have known to make it looks more compact, but not sure if the binary code got any change:

Code: Select all

void GetMoves(int sq, int piece, int*& movelist)
{
    //pP nN bB rR qQ kK
    int** begin = rays[sq][piece];
    int* end = *(begin + raycnt[piece]);
    int co = Color(board[sq]);
    int* ray;

    while((ray = *begin++) != end)
    {
        int* end = ray + (ray[-1] & 0xFF);
        int config = (ray[-1] >> 8);
        
        while (ray != end && !(config & move_slide))
        {
            int to = *ray++, ce = Color(board[to]);
            if (((config & square_empty) && ce == 0)
                || ((config & square_enemy) && ce != co)
                || ((config & square_ep) && ep == to)
                || ((config & move_cstl) && Legal(co, sq, to)))
                _move(sq, to);
        }
    }
}

[hgm]

If compactness of the source code is the goal, you will end up with something like micro-Max or Toledo nanoChess.

[dangi12012]

If compactness of the source code is the goal, you will end up with something like micro-Max or Toledo nanoChess.

Yes but with an UCI interface
For example non optimized fen parser would take 20 lines:

Code: Select all

static void Setup(std::string fen, std::string moves = "")
{
	char s, mv, pos[128], cas[5], enps[3];
	ep = 0; castle = 0; halfmove = 0; fullmove = 1;
	memset(board, '_', sizeof(board));
	int i = 0, k = 0,  col = 0, row = 7;
	if (sscanf(fen.c_str(), "%s %c %s %s %d %d", pos, &mv, cas, enps, &halfmove, &fullmove) < 3) {
		printf("Error parsing fen string %s\n", fen.c_str()); return;
	}
	//Board
	while ((s = pos[i++])) {
		if (s == '/') k = ((k + 7) / 8) * 8; //Round up to next 8 if not on 8
		else if (s >= '1' && s <= '8') k += s - '0';
		else board[k++] = s;
	}
	//Color
	movecolor = mv == 'b' ? -1 : 1; i = 0;
	//Castling
	while ((s = cas[i++])) {
		castle |= s == 'k' ? 1 : s == 'q' ? 2 : s == 'K' ? 4 : s == 'Q' ? 8 : 0;
	}
	//Enpassant
	if (enps[0] >= 'a' && enps[0] <= 'h') ep = (enps[0] - 'a') + (movecolor + 1) ? 24 : 32;
	if (moves != "") {
		printf("Moves are not supported yet. Use position fen <FEN>!\n");
	}
}

But I would still want the sourcecode to be readable. So no "#define _ if" trickery.

[leanchess]

If you really want to count the bytes, here's one off the top of my head:

Code: Select all

const int raycnt[6] = { 3,1,4,4,8,3 };

Code: Select all

	int* end = *(begin + raycnt[piece/2]);

[dangi12012]

If you really want to count the bytes, here's one off the top of my head:

Code: Select all

const int raycnt[6] = { 3,1,4,4,8,3 };

Code: Select all

	int* end = *(begin + raycnt[piece/2]);

Thanks!

Code: Select all

int* end = *(begin + raycnt[piece >> 1]);