PieceLists ?

[hgm]

Code: Select all

struct Board {
    uint32_t bitlist[64]; /* For each square, what pieces attack it? */
    char piecelist[32];   /* For each piece, which square is it on? */
    char index[64];       /* For each square, which piece is on it? */
    uint32_t sidemask[2];
    char side;
    char castle;
    char ep;
    char fifty;
    uint32_t piecemask[6];
    uint64_t hash;
    uint32_t rep[100];
};

This qualifies as mailbox, right? index[64] is a mailbox board...

[ZirconiumX]

Code: Select all

struct Board {
    uint32_t bitlist[64]; /* For each square, what pieces attack it? */
    char piecelist[32];   /* For each piece, which square is it on? */
    char index[64];       /* For each square, which piece is on it? */
    uint32_t sidemask[2];
    char side;
    char castle;
    char ep;
    char fifty;
    uint32_t piecemask[6];
    uint64_t hash;
    uint32_t rep[100];
};

This qualifies as mailbox, right? index[64] is a mailbox board...

Yes, it's mailbox. I have never said it was bitboard.

[hgm]

Indeed. But some people seem to be unaware of that, so it is goot to make that explicit.

Note that I don't want to say anything bad about your code. Attack maps are great. It is just that the part you posted does't do any move generation, and thus cannot be compared to conventional or slightly smart from-scratch bitboard or mailbox generators.

[Sven]

As Matthew explained above, "bitlist", "sidemask" and "piecelist" are part of his board representation and are obviously updated incrementally with each move that is made. So his capture move generator is actually both very simple and very clever.

Except that it is not a capture generator. It is just code that extracts moves from an attack map. An attack map is just a data structure to hold previously generated moves. My mailbox code would practically look the same. The nested loops over victims (outer) and attackers (inner) is forced by the requirement of the problem (generating captures in MVV order).

Read also the comments inside the code and you can understand how it works. The question "Where do you generate moves?" can be answered by reading as well. The outer loop determines the current target square "dest", the inner loop the current source square "from", and AddMove() adds the move (from+dest) to the move list pointed to by "m". A capture with promotion is handled by AddCapturePromotions() instead. Additionally EP generation is handled fully outside the loop, as everyone else does in his own move generator. Not hard to understand, I think.

Sure,I understand all that, of course. At least enough to see that none of this code has anything to do with move generation. More like move sorting.

It is irrelevant how a move generator works internally, what counts is the result: it produces a list of moves. Whether these moves are constructed from scratch while the "move generator function" is running, or extracted from a precalculated database, or constructed partially with the help of precalculated data and partially from scratch (the latter applies to move generators of classical bitboard engines where essentially only sliding move generation uses precalculated data) does not matter at all. So the code shown by Matthew is certainly a move generator.

[Sven]

This qualifies as mailbox, right? index[64] is a mailbox board...

Yes, it's mailbox. I have never said it was bitboard.

Indeed. But some people seem to be unaware of that, so it is goot to make that explicit.

@HGM: I have never said the board representation were bitboard as well - just in case you were thinking for a moment that I have (although I don't know who else might have been addressed by your "some people seem to" remark). There was only one phrase where I mentioned the term "bitboard" in close relation to the code posted by Matthew and that was where I wrote about being "experienced in reading bitboard code", there I meant the style of the capture generator function which is clearly a bitboard style. Later on I clearly stated that the board representation was neither pure mailbox nor pure bitboard but based on attack tables.

[phhnguyen]

Yes, it's mailbox. I have never said it was bitboard.

Oops, sorry Matthew. Your code looks a bit strange to mailboxes with some terms similar to bitboard terms, thus I thought you wanted to protect the point of Richard Delorme: the capture move generator used in QS (and in staged move generation), much easier to implement with bitboard than with maibox.

[hgm]

It is irrelevant how a move generator works internally, what counts is the result: it produces a list of moves. Whether these moves are constructed from scratch while the "move generator function" is running, or extracted from a precalculated database, or constructed partially with the help of precalculated data and partially from scratch (the latter applies to move generators of classical bitboard engines where essentially only sliding move generation uses precalculated data) does not matter at all. So the code shown by Matthew is certainly a move generator.

Bullshit. The issue raised here is how complex and maintainable the code is, and for that how the generator works internally is all that matters. Code needed to precalculate a database is part of the move generator.

And you apparently do not understand the code: there is nothing "precalculated" here. The set of attackers to a given square is dependent on the position, and must be re-calculated in every node. It is just calculated by another routine than the one here. You even seem to think it is bitboard based, while in fact it is a mailbox generator. The code
shown does not have a single bitboard in it.

[hgm]

It is irrelevant how a move generator works internally, what counts is the result: it produces a list of moves. Whether these moves are constructed from scratch while the "move generator function" is running, or extracted from a precalculated database, or constructed partially with the help of precalculated data and partially from scratch (the latter applies to move generators of classical bitboard engines where essentially only sliding move generation uses precalculated data) does not matter at all. So the code shown by Matthew is certainly a move generator.

Bullshit. The issue raised here is how complex and maintainable the code is, and for that how the generator works internally is all that matters. Code needed to precalculate a database is part of the move generator.

And you apparently do not understand the code: there is nothing "precalculated" here. The set of attackers to a given square is dependent on the position, and must be re-calculated in every node. It is just calculated by another routine than the one here.

@HGM: I have never said the board representation were bitboard as well - just in case you were thinking for a moment that I have (although I don't know who else might have been addressed by your "some people seem to" remark). There was only one phrase where I mentioned the term "bitboard" in close relation to the code posted by Matthew and that was where I wrote about being "experienced in reading bitboard code", there I meant the style of the capture generator function which is clearly a bitboard style. Later on I clearly stated that the board representation was neither pure mailbox nor pure bitboard but based on attack tables.

Well, hat remark surely suggest you think the code has aything to do with bitboard.

FYI, I know how to extract the next bit from an integer using carry propagation already for more than 40 years. It is in the Kernighan & Ritchie introductary book about C.

[Sven]

It is irrelevant how a move generator works internally, what counts is the result: it produces a list of moves. Whether these moves are constructed from scratch while the "move generator function" is running, or extracted from a precalculated database, or constructed partially with the help of precalculated data and partially from scratch (the latter applies to move generators of classical bitboard engines where essentially only sliding move generation uses precalculated data) does not matter at all. So the code shown by Matthew is certainly a move generator.

Bullshit. The issue raised here is how complex and maintainable the code is, and for that how the generator works internally is all that matters. Code needed to precalculate a database is part of the move generator.

And you apparently do not understand the code: there is nothing "precalculated" here. The set of attackers to a given square is dependent on the position, and must be re-calculated in every node. It is just calculated by another routine than the one here.

@HGM: I have never said the board representation were bitboard as well - just in case you were thinking for a moment that I have (although I don't know who else might have been addressed by your "some people seem to" remark). There was only one phrase where I mentioned the term "bitboard" in close relation to the code posted by Matthew and that was where I wrote about being "experienced in reading bitboard code", there I meant the style of the capture generator function which is clearly a bitboard style. Later on I clearly stated that the board representation was neither pure mailbox nor pure bitboard but based on attack tables.

Well, hat remark surely suggest you think the code has aything to do with bitboard.

FYI, I know how to extract the next bit from an integer using carry propagation already for more than 40 years. It is in the Kernighan & Ritchie introductary book about C.

For a moderator, as you are, your tone is surprisingly close to being inappropriate.

Since I have no time for such a kind of "discussion" where your only goal is to show that you are the boss and others have no clue, this is my final post in this thread. Have a lot of fun with your challenge, which you already seem to have won before it even started.

[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).