Did someone mention the GNUChess move Generator?

[Michael Sherwin]

Yep!

Since the GNUChess move generator was mentioned, here it is,
translated to the 'Crafty' type philosophy.

The upside is only two do-loops rather than three.

The downside is it requires a lot more data to drive it.

Unlike the GNUChess rendition, this version uses a 128
element board so some 0x88 tricks may be used elsewhere.

The board pointed at by *tblPtr stores next-squares in the left half
and the next-square for the next direction is in the right half.

To get from the left half to the right half just add 8 to the
to-square before getting the next to-square.

Code: Select all

// Non Promotion Moves only, No Captures - a la Crafty
// NOT BITBOARD
void GenMoves() {
  s32 fs, ts, type, vic;
  u32 *tblPtr;
  u64 pieces;

  pieces = picesOfColor[wtm];
  do {
       fs = FirstBit64(pieces);
       pieces &= clrBit64(fs);
       type = board[fs];
       tblPtr = tblPtrs[type][fs];
       ts = *(tblPtr + fs);  
       do {
            vic = board[ts];
            if(vic) ts += 8;
            else Link(type, fs, ts);
       } while((ts = *(tblPtr + ts)) != STOP);
  } while (pieces);
}

Once again, this is the entire move generator for all the pieces
(remember, non captures non promotions, only) including castling.

Edit: Rather than adding 8 to the to-square you can have two pointers, but that would increase register pressure and you might not need it anyway

And it is very, very fast!

[Aleks Peshkov]

I think this version of GNU generator will perform slightly better.

Code: Select all

struct NextMove {
    byte sq;      //current "to" square
    byte nextDir; //offset to next-dir
};
#define MAX_NUMBER_OF_MOVES 32
extern CACHE_ALIGN NextMove moveGen[PieceType::Size][Square::Size][MAX_NUMBER_OF_MOVES];

NextMove* nextMove = moveGen[piece][from];
do {
    if (board[nextMove->sq] == Empty) {
        LinkMove(piece, from, nextMove->sq);
        if (nextMove->nextDir == 0) { break; }
        ++nextMove;
    } else {
        if (board[nextMove->sq] == XSide) {
            LinkCapture(piece, from, nextMove->sq);
        }
        if (nextMove->nextDir == 0) { break; }
        nextMove += nextMove->nextDir;
    }
} while (1);

[Aleks Peshkov]

MAX_NUMBER_OF_MOVES can be easily reduced twice. We can share all Rook moves between Rooks and Queens from the same square, if we link nextDir from last Queen's Bishop direction inside Queens move space to Rook's move space of the same "from" square.

Code: Select all

NextMove moveGen[Square::Size][PieceType::Size][16];

If we encode Queens near to Rooks in PieceType enumeration, then all 27 possible Queens move will be inside one cache line!

[Michael Sherwin]

I think this version of GNU generator will perform slightly better.

Code: Select all

struct NextMove {
    byte sq;      //current "to" square
    byte nextDir; //offset to next-dir
};
#define MAX_NUMBER_OF_MOVES 32
extern CACHE_ALIGN NextMove moveGen[PieceType::Size][Square::Size][MAX_NUMBER_OF_MOVES];

NextMove* nextMove = moveGen[piece][from];
do {
    if (board[nextMove->sq] == Empty) {
        LinkMove(piece, from, nextMove->sq);
        if (nextMove->nextDir == 0) { break; }
        ++nextMove;
    } else {
        if (board[nextMove->sq] == XSide) {
            LinkCapture(piece, from, nextMove->sq);
        }
        if (nextMove->nextDir == 0) { break; }
        nextMove += nextMove->nextDir;
    }
} while (1);

I might be wrong (not had much sleep), but it seems that there is a flaw in your code.

1.) After linking a non capture you test for next direction and break if it is zero, however, if the piece moving is a sliding piece it will only link one move in the last direction.

2.) You have more branches in your code and you do the equivilent of ts += 8 with ++nextMove or nextMove += nextMove->nextDir. However, your increment/add must be done every time, even if there is no blocking piece.

3.) Don't know about CASHE_ALIGN, however, compilers do it anyway (?) and 128 element arrays should be very naturally cash aligned.

Please correct me on any of the above points.

Also this is not the same as the GNUChess move generator. In GNUChess, looking up a to-square in a 'next square board array' gives the next square unless there is a blocker at wich time it gets the next square from the 'next direction board array'. Your method iterates through a list of next squares and requires that a seperate indici be maintained.

I also have this type in my collection! But, unless someone can give the correct name for it, I am not going to post it.

[Aleks Peshkov]

1.) After linking a non capture you test for next direction and break if it is zero, however, if the piece moving is a sliding piece it will only link one move in the last direction.

Thank you, you discovered a bug. After non capture move actually we need not loop termination test. All that is needed append to move list an extra "from" square. This square guaranteed to be occupied by a piece of our color, so no illegal moves would be generated. . Queen on empty board will test for loop end only once, after last valid square.

Code: Select all

struct NextMove {
    byte sq;      //current "to" square
    byte nextDir; //offset to next-dir
};
#define MAX_NUMBER_OF_MOVES 32
extern CACHE_ALIGN NextMove moveGen[PieceType::Size][Square::Size][MAX_NUMBER_OF_MOVES];

NextMove* nextMove = moveGen[piece][from];
do {
    if (board[nextMove->sq] == Empty) {
        LinkMove(piece, from, nextMove->sq);
        ++nextMove;
    } else {
        if (board[nextMove->sq] == XSide) {
            LinkCapture(piece, from, nextMove->sq);
        }
        if (nextMove->nextDir == 0) { break; }
        nextMove += nextMove->nextDir;
    }
} while (1);

However, your increment/add must be done every time, even if there is no blocking piece.

Your forget that you do increment, memory lookup and test inside while() test.

[Michael Sherwin]

Your forget that you do increment, memory lookup and test inside while() test.

You are correct.

Seems that both methods are about equal since your extra branches are needed to link captures as well as moves.

Speed will then depend on how well the data cashes. For the 128 element boards it is possible to load them into the cashe perfectly by first reading the first element of the board array. I learned this from Gerd, but I do not remember it very well.

I use the Crafty pholosophy of seperating capture generation from move generation, because, it simplifies the link code and allows the generator to be small.

To link in captures and moves for the pawns will complicate the link function. It remains simple if the generation is seperated.