PieceLists ?

[abulmo2]

So I am willing to take up the challenge: I claim I can write a capture generator that is both faster and simpler than any bitboard generator could ever be. (And maintainable! ) The question is how to measure it. Perhaps this should be done in a captures-only perft from some positions with many captures. To not contaminate the matter with issues of little relevace for the speed of an engine, we could count pseudo-legal moves. (I.e. assume moving in check is legal, and that King capture terminates the game.) As a requirement the captures should be generated in victim value order, so that staged move generation is possible. (Which would have no advantage at all in perft.)

I released my own perft here:
https://github.com/abulmo/hqperft
It uses a bitboard move generator based on hyperbola quintessence & rank attacks and is largely related to my chess program amoeba. However it is written in C instead of D.
It only produce legal moves (pseudo-legal is a too blurry definition to be implemented without infinite debates).
Here is the help describing its possibilities.

Code: Select all

HQPerft (c) Richard Delorme - 2017
Bitboard move generation based on (H)yperbola (Q)uintessence & rank attacks
hqperft &#91;--fen|-f <fen>&#93; &#91;--depth|-d <depth>&#93; &#91;--hash|-H <size>&#93; &#91;--bulk|-b&#93; &#91;--div&#93; &#91;--capture&#93; &#91;--help|-h&#93; 
Enumerate moves.
	--help|-h            Print this message.
	--fen|-f <fen>       Test the position indicated in FEN format &#40;default=starting position&#41;.
	--depth|-d <depth>   Test up to this depth &#40;default=6&#41;.
	--bulk|-b            Do fast bulk counting at the last ply.
	--hash|-H <size>     Use a hashtable with <size> bits entries &#40;default 0, no hashtable&#41;.
	--capture|-c         Generate only captures.
	--loop|-l            Loop from depth 1 to <depth>.
	--div|-r             Print a node count for each move.

For example:

Code: Select all

$ hqperft -d 7 -b
HQPerft (c) Richard Delorme - 2017
Bitboard move generation based on (H)yperbola (Q)uintessence & range attacks
Perft setting: no hashing; with bulk counting;
  a b c d e f g h
8 r n b q k b n r 8
7 p p p p p p p p 7
6 . . . . . . . . 6
5 . . . . . . . . 5
4 . . . . . . . . 4
3 . . . . . . . . 3
2 P P P P P P P P 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  7 :      3195901860 leaves in     12.197 s    262032065 leaves/s

It can do capture generation only:

Code: Select all

$ hqperft -d 15 -f 'rnbqkbnr/8/8/pppppppp/PPPPPPPP/8/8/RNBQKBNR w KQkq - 0 1' -c -l -b -H 29
HQPerft (c) Richard Delorme - 2017
Bitboard move generation based on (H)yperbola (Q)uintessence & rank attacks
Perft setting: hashtable size: 12288 Mbytes; with bulk counting; capture only;
  a b c d e f g h
8 r n b q k b n r 8
7 . . . . . . . . 7
6 . . . . . . . . 6
5 p p p p p p p p 5
4 P P P P P P P P 4
3 . . . . . . . . 3
2 . . . . . . . . 2
1 R N B Q K B N R 1
  a b c d e f g h
w, KQkq
perft  1 :              14 leaves in      0.000 s     19581066 leaves/s
perft  2 :             169 leaves in      0.000 s     48038360 leaves/s
perft  3 :            1709 leaves in      0.000 s     83881431 leaves/s
perft  4 :           14813 leaves in      0.000 s     71124697 leaves/s
perft  5 :          108742 leaves in      0.001 s     93194381 leaves/s
perft  6 :          723016 leaves in      0.006 s    129488522 leaves/s
perft  7 :         4260221 leaves in      0.021 s    203550423 leaves/s
perft  8 :        23933522 leaves in      0.075 s    318096595 leaves/s
perft  9 :       121794742 leaves in      0.229 s    531548794 leaves/s
perft 10 :       600959923 leaves in      0.643 s    935060362 leaves/s
perft 11 :      2712171201 leaves in      1.592 s   1703789119 leaves/s
perft 12 :     11886845933 leaves in      3.723 s   3192437950 leaves/s
perft 13 :     47701666802 leaves in      7.939 s   6008729387 leaves/s
perft 14 :    184019931141 leaves in     15.942 s  11543036668 leaves/s
perft 15 :    646995992152 leaves in     29.824 s  21693571576 leaves/s
total 15 :    894068404100 leaves in     62.775 s  14242533137 leaves/s

To compile it, I recommend using gcc and the given Makefile with the command:

Code: Select all

make pgo

Compared to qperft by H.G.Muller, this perft is:
- ~30% faster
- more stable: return error messages instead of crashing.
- ~10% simpler: less line of code, less statements, smaller McCabe complexity, etc.
- more complete: can generate only captures, without bulking, etc.
- better coded (less warning from gcc).

On modern CPU, my implementation is both simple and fast. There are faster implementation, though, the fastest I know about (on CPU) having been done by Paul Byrne (gperft).

[Karlo Bala]

I do not consider given code reasonably elegant. Generating attacks of pieces is not equal to generating legal moves.

What is elegant is to transform attacks bitboards into legal move bitboards generically as possible.

IMO, the most elegant (not the best, just elegant) move generator I've seen is from Hans Eric Sandstroem, implemented in GNU Chess 3.

Code: Select all

New move Generation algoritm:
Revision: 1989-09-06
Author: Hans Eric Sandstroem.

This algortim is the result of an attempt to make an hardware move generator, but since I newer had the time and resources to build the hardware I wrote a software version and incorporated that one into gnuchess. This was the best way I could think of sharing this algorithm with the computer chess community.

If there is anybody out there with the time and rescources to build a hardware move generator I will be glad to assist.

The general idea behind this algoritm is to pre calculate a lot of data. The data that is pre calculated is every possible move for every piece from every square disregarding any other pieces on the board. This pre calculated data is stored in an array that looks like this:

struct sqdata {
  short nextpos;
  short nextdir;
};
struct sqdata posdata[8][64][64];
/* posdata[piecetype][fromsquare][destinationsquare] */
example:
	the first move for a queen at e8 is stored at;
	posdata[queen][e8][e8].nextpos
	suppose this is e7 and e7 is occupied then the next move
	will be found in;
	posdata[queen][e8][e7].nextdir

To handle the differeces between white and black pawns (they move in opposite directions) an array ptype has been introduced:  
static const short ptype[2][8] = {
  no_piece,pawn,knight,bishop,rook,queen,king,no_piece,
  no_piece,bpawn,knight,bishop,rook,queen,king,no_piece};
           ^^^^^
And it is used like this:
   piecetype = ptype[side][piece]
When generating moves for pieces that are not black pawns, piece can be used directly in posdata. As in the example above.

Thus the only thing one has to do when generating the moves is to check for collisions with other pieces.  the move generation to do this looks like this: (for non pawns)

    p = posdata[piece][sq];
    u = p[sq].nextpos;
    do {
      if (color[u] == neutral) {
        LinkMove(ply,sq,u,xside);
        u = p[u].nextpos;
      }
      else {
        if (color[u] == xside) LinkMove(ply,sq,u,xside);
        u = p[u].nextdir;
      }
    } while (u != sq);

 - I`nt this just beautiful!

The array posdata is initialized in the routine Initialize_moves. This routine is called just once and it works so no time has been spent on the structure of this code. GenMoves and CaptureList generates the moves but the routines ataks, BRscan, Sqatakd, KingScan and trapped also relies on the move generation algoritm so they have also been rewritten.

[pkumar]

IMO, the most elegant (not the best, just elegant) move generator I've seen is from Hans Eric Sandstroem, implemented in GNU Chess 3.

Code: Select all

    p = posdata[piece][sq];
    u = p[sq].nextpos;
    do {
      if (color[u] == neutral) {
        LinkMove(ply,sq,u,xside);
        u = p[u].nextpos;
      }
      else {
        if (color[u] == xside) LinkMove(ply,sq,u,xside);
        u = p[u].nextdir;
      }
    } while (u != sq);

My noncapture slide move generator is somewhat similar, probably slower.

Code: Select all

enum PieceType{EMPTY, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING};
enum ColorType {WHITE, BLACK, FREE, EDGE};
struct Square
{
    char piece;
    char color;
    char list;//link to piecelist
    char junk;
};

    Square board[65];//board[0..63] are usual, board[64] is set to piece= EMPTY and color=EDGE

//moves_piece[from][direction][slides+1]
    char moves_B[64][4][8];
    char moves_R[64][4][8];
    char moves_Q[64][8][8];

//movept_piece[from][directions+1]
    char* movept_B[64][5];
    char* movept_R[64][5];
    char* movept_Q[64][9];

/*
After initialisation, ROOK at A1 would have
	moves_R[A1]=
	{{B1,C1,D1,E1,F1,G1,H1,64}
	,{A2,A3,A4,A5,A6,A7,A8,64}
	,{64,64,64,64,64,64,64,64}
	,{64,64,64,64,64,64,64,64}};
	movept_R[A1]={moves_R[A1][0],moves_R[A1][1],NULL,NULL,NULL};
*/

void getSlideMoves(int from, char** movept)
{
    int to;
    int piece=board[from].piece;
    char* moves= *movept++;

	//Only open directions are scanned, e.g., 3 directions for Q at A1
	//For QUEEN, up to 8 edges may be tested(tad wasteful) unless obstracted
    do
	{
        to= *moves++;
        if(board[to].color== FREE)
            PUSH(MOVE(from,to,piece));
        else //obstacle or edge
        {
            moves= *movept++;
            if(moves==NULL) break;
        }
	}while(true);
}

//calling code
	switch(board[from].piece)
	{
	...code...
        	case BISHOP: getSlideMoves(from, movept_B[from]); break;
	...code...
	}