Did someone mention the GNUChess move Generator?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Michael Sherwin
Posts: 3046
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Did someone mention the GNUChess move Generator?

Post by Michael Sherwin » Mon Nov 12, 2007 6:35 pm

Yep! :lol:

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! :D
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Aleks Peshkov
Posts: 873
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: Did someone mention the GNUChess move Generator?

Post by Aleks Peshkov » Mon Nov 12, 2007 10:00 pm

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
Posts: 873
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: Did someone mention the GNUChess move Generator?

Post by Aleks Peshkov » Mon Nov 12, 2007 10:22 pm

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
Posts: 3046
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Did someone mention the GNUChess move Generator?

Post by Michael Sherwin » Tue Nov 13, 2007 12:29 am

Aleks Peshkov wrote: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! :D But, unless someone can give the correct name for it, I am not going to post it. :twisted: :lol:
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Aleks Peshkov
Posts: 873
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: Did someone mention the GNUChess move Generator?

Post by Aleks Peshkov » Tue Nov 13, 2007 2:19 am

Michael Sherwin wrote: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
Posts: 3046
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Did someone mention the GNUChess move Generator?

Post by Michael Sherwin » Tue Nov 13, 2007 4:00 am

Aleks Peshkov wrote: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.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Post Reply