I will be back home late on saturday night, so I fear that I might not be able to work on the C code before sunday.
If by any change I find the time to do it earlier, I will do so, of course.Why C++ instead of C#?
Moderator: Ras
-
R. Tomasi
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Why C++ instead of C#?
If by any change I find the time to do it earlier, I will do so, of course.-
spirch
- Posts: 95
- Joined: Fri Nov 09, 2012 12:36 am
Re: Why C++ instead of C#?
removing static instance of struct to member of main method and making sure everything is passed by reference is maybe something
i remember reading that static struct are not saved in stack but in the heap
also killing the TPieceEnum and moving it to a static class with const byte help
now getting
i remember reading that static struct are not saved in stack but in the heap
also killing the TPieceEnum and moving it to a static class with const byte help
now getting
Code: Select all
Total: 1361558651 Nodes, 24790ms, 54922K NPS-
spirch
- Posts: 95
- Joined: Fri Nov 09, 2012 12:36 am
Re: Why C++ instead of C#?
i'm spamming i think but another thing
genrook and genbishop
inline these variable instead of declaring them and it save a little bit again; (remove the lines)
reason? less memory in the stack, they are single use, why saving them in memory?
genrook and genbishop
inline these variable instead of declaring them and it save a little bit again; (remove the lines)
reason? less memory in the stack, they are single use, why saving them in memory?
Code: Select all
ulong piece
ulong piecesup
ulong piecesdo
ulong piecesle
ulong piecesri Code: Select all
Total: 1361558651 Nodes, 24359ms, 55894K NPS-
lithander
- Posts: 915
- Joined: Sun Dec 27, 2020 2:40 am
- Location: Bremen, Germany
- Full name: Thomas Jahn
Re: Why C++ instead of C#?
Nice finds, spirch. I will make a version 1.5 then!
Do you want to post your code? Otherwise I'll try to replicate your changes but having the code to work with would probably be quicker.
Do you want to post your code? Otherwise I'll try to replicate your changes but having the code to work with would probably be quicker.
-
klx
- Posts: 179
- Joined: Tue Jun 15, 2021 8:11 pm
- Full name: Emanuel Torres
Re: Why C++ instead of C#?
Here's the Java version. Feel free to add it to your repo. Curious what your timings will show. It's slightly faster than the C# version for me, but based on your C# numbers I suppose you might find it a bit slower.
Code: Select all
/*
This perft implementation is based on QBBEngine by Fabio Gobbato and ported to Java by Emanuel Torres.
The purpose is to compare the speed differences of various languages for a chess programming workload.
*/
class QbbPerft {
static final long WHITE = 0;
static final long BLACK = 8;
/* define the piece type: empty, pawn, knight, bishop, rook, queen, king */
static final long EMPTY = 0;
static final long PAWN = 1;
static final long KNIGHT = 2;
static final long BISHOP = 3;
static final long ROOK = 4;
static final long QUEEN = 5;
static final long KING = 6;
/* define the move type, for example
KING|CASTLE is a castle move
PAWN|CAPTURE|EP is an enpassant move
PAWN|PROMO|CAPTURE is a promotion with a capture */
static final long CASTLE = 0x40;
static final long PROMO = 0x20;
static final long EP = 0x10;
static final long CAPTURE = 0x08;
/*
Board structure definition
PM,P0,P1,P2 are the 4 bitboards that contain the whole board
PM is the bitboard with the side to move pieces
P0,P1 and P2: with these bitboards you can obtain every type of pieces and every pieces combinations.
*/
static class TBoard {
long PM;
long P0;
long P1;
long P2;
byte CastleFlags; /* ..sl..SL short long opponent SHORT LONG side to move */
byte EnPassant; /* enpassant column, =8 if not set */
byte STM; /* side to move */
};
/*
Into Game are saved all the positions from the last 50 move counter reset
Position is the pointer to the last position of the game
*/
static TBoard[] Game = new TBoard[512];
static int pPosition;
static {
for (int n = 0; n < Game.length; ++n)
Game[n] = new TBoard();
}
/* array of bitboards that contains all the knight destination for every square */
static long[] KnightDest= {0x0000000000020400L,0x0000000000050800L,0x00000000000a1100L,0x0000000000142200L,
0x0000000000284400L,0x0000000000508800L,0x0000000000a01000L,0x0000000000402000L,
0x0000000002040004L,0x0000000005080008L,0x000000000a110011L,0x0000000014220022L,
0x0000000028440044L,0x0000000050880088L,0x00000000a0100010L,0x0000000040200020L,
0x0000000204000402L,0x0000000508000805L,0x0000000a1100110aL,0x0000001422002214L,
0x0000002844004428L,0x0000005088008850L,0x000000a0100010a0L,0x0000004020002040L,
0x0000020400040200L,0x0000050800080500L,0x00000a1100110a00L,0x0000142200221400L,
0x0000284400442800L,0x0000508800885000L,0x0000a0100010a000L,0x0000402000204000L,
0x0002040004020000L,0x0005080008050000L,0x000a1100110a0000L,0x0014220022140000L,
0x0028440044280000L,0x0050880088500000L,0x00a0100010a00000L,0x0040200020400000L,
0x0204000402000000L,0x0508000805000000L,0x0a1100110a000000L,0x1422002214000000L,
0x2844004428000000L,0x5088008850000000L,0xa0100010a0000000L,0x4020002040000000L,
0x0400040200000000L,0x0800080500000000L,0x1100110a00000000L,0x2200221400000000L,
0x4400442800000000L,0x8800885000000000L,0x100010a000000000L,0x2000204000000000L,
0x0004020000000000L,0x0008050000000000L,0x00110a0000000000L,0x0022140000000000L,
0x0044280000000000L,0x0088500000000000L,0x0010a00000000000L,0x0020400000000000L};
/* The same for the king */
static long[] KingDest = {0x0000000000000302L,0x0000000000000705L,0x0000000000000e0aL,0x0000000000001c14L,
0x0000000000003828L,0x0000000000007050L,0x000000000000e0a0L,0x000000000000c040L,
0x0000000000030203L,0x0000000000070507L,0x00000000000e0a0eL,0x00000000001c141cL,
0x0000000000382838L,0x0000000000705070L,0x0000000000e0a0e0L,0x0000000000c040c0L,
0x0000000003020300L,0x0000000007050700L,0x000000000e0a0e00L,0x000000001c141c00L,
0x0000000038283800L,0x0000000070507000L,0x00000000e0a0e000L,0x00000000c040c000L,
0x0000000302030000L,0x0000000705070000L,0x0000000e0a0e0000L,0x0000001c141c0000L,
0x0000003828380000L,0x0000007050700000L,0x000000e0a0e00000L,0x000000c040c00000L,
0x0000030203000000L,0x0000070507000000L,0x00000e0a0e000000L,0x00001c141c000000L,
0x0000382838000000L,0x0000705070000000L,0x0000e0a0e0000000L,0x0000c040c0000000L,
0x0003020300000000L,0x0007050700000000L,0x000e0a0e00000000L,0x001c141c00000000L,
0x0038283800000000L,0x0070507000000000L,0x00e0a0e000000000L,0x00c040c000000000L,
0x0302030000000000L,0x0705070000000000L,0x0e0a0e0000000000L,0x1c141c0000000000L,
0x3828380000000000L,0x7050700000000000L,0xe0a0e00000000000L,0xc040c00000000000L,
0x0203000000000000L,0x0507000000000000L,0x0a0e000000000000L,0x141c000000000000L,
0x2838000000000000L,0x5070000000000000L,0xa0e0000000000000L,0x40c0000000000000L};
/* masks for finding the pawns that can capture with an enpassant (in move generation) */
static long[] EnPassant = {
0x0000000200000000L,0x0000000500000000L,0x0000000A00000000L,0x0000001400000000L,
0x0000002800000000L,0x0000005000000000L,0x000000A000000000L,0x0000004000000000L
};
/* masks for finding the pawns that can capture with an enpassant (in make move) */
static long[] EnPassantM = {
0x0000000002000000L,0x0000000005000000L,0x000000000A000000L,0x0000000014000000L,
0x0000000028000000L,0x0000000050000000L,0x00000000A0000000L,0x0000000040000000L
};
/* extract the least significant bit of the bitboard */
static long ExtractLSB(long bb) { return bb & -bb; }
/* reset the least significant bit of bb */
static long ClearLSB(long bb) { return bb & (bb-1); }
/* Macro to check and reset the castle rights:
CastleSM: short castling side to move
CastleLM: long castling side to move
CastleSO: short castling opponent
CastleLO: long castling opponent
*/
static boolean CastleSM(TBoard Position) { return (Position.CastleFlags&0x02) != 0; }
static boolean CastleLM(TBoard Position) { return (Position.CastleFlags&0x01) != 0; }
/* these Macros are used to calculate the bitboard of a particular kind of piece
P2 P1 P0
0 0 0 empty
0 0 1 pawn
0 1 0 knight
0 1 1 bishop
1 0 0 rook
1 0 1 queen
1 1 0 king
*/
static long Occupation(TBoard Position) { return Position.P0 | Position.P1 | Position.P2; } /* board occupation */
static long Pawns(TBoard Position) { return Position.P0 & ~Position.P1 & ~Position.P2; } /* all the pawns on the board */
static long Knights(TBoard Position) { return ~Position.P0 & Position.P1 & ~Position.P2; }
static long Bishops(TBoard Position) { return Position.P0 & Position.P1; }
static long Rooks(TBoard Position) { return ~Position.P0 & ~Position.P1 & Position.P2; }
static long Queens(TBoard Position) { return Position.P0 & Position.P2; }
static long QueenOrRooks(TBoard Position) { return ~Position.P1 & Position.P2; }
static long QueenOrBishops(TBoard Position) { return Position.P0 & (Position.P2 | Position.P1); }
static long Kings(TBoard Position) { return Position.P1 & Position.P2; } /* a bitboard with the 2 kings */
/* calculate the square related to the opponent */
static long OppSq(long sp) { return sp^0x38; }
/*
The board is always saved with the side to move in the lower part of the bitboards to use the same generation and
make for the Black and the White side.
This needs the inversion of the 4 bitboards, roll the Castle rights and update the side to move.
*/
static void ChangeSide(TBoard Position) {
Position.PM^=Occupation(Position); /* update the side to move pieces */
Position.PM=Long.reverseBytes(Position.PM);
Position.P0=Long.reverseBytes(Position.P0);
Position.P1=Long.reverseBytes(Position.P1);
Position.P2=Long.reverseBytes(Position.P2);/* reverse the board */
Position.CastleFlags=(byte)((Position.CastleFlags>>>4)|(Position.CastleFlags<<4));/* roll the castle rights */
Position.STM ^= BLACK; /* change the side to move */
}
/* return the bitboard with the rook destinations */
static long GenRook(long sq,long occupation) {
long piece = 1L<<sq;
occupation ^= piece; /* remove the selected piece from the occupation */
long piecesup=(0x0101010101010101L<<sq)&(occupation|0xFF00000000000000L); /* find the pieces up */
long piecesdo=(0x8080808080808080L>>>(63-sq))&(occupation|0x00000000000000FFL); /* find the pieces down */
long piecesri=(0x00000000000000FFL<<sq)&(occupation|0x8080808080808080L); /* find pieces on the right */
long piecesle=(0xFF00000000000000L>>>(63-sq))&(occupation|0x0101010101010101L); /* find pieces on the left */
return (((0x8080808080808080L>>>(63-Long.numberOfTrailingZeros(piecesup)))&(0x0101010101010101L<<(0x3F ^ Long.numberOfLeadingZeros(piecesdo)))) |
((0xFF00000000000000L>>>(63-Long.numberOfTrailingZeros(piecesri)))&(0x00000000000000FFL<<(0x3F ^ Long.numberOfLeadingZeros(piecesle)))))^piece;
/* From every direction find the first piece and from that piece put a mask in the opposite direction.
Put togheter all the 4 masks and remove the moving piece */
}
/* return the bitboard with the bishops destinations */
static long GenBishop(long sq,long occupation) {
/* it's the same as the rook */
long piece = 1L<<sq;
occupation ^= piece;
long piecesup=(0x8040201008040201L<<sq)&(occupation|0xFF80808080808080L);
long piecesdo=(0x8040201008040201L>>>(63-sq))&(occupation|0x01010101010101FFL);
long piecesle=(0x8102040810204081L<<sq)&(occupation|0xFF01010101010101L);
long piecesri=(0x8102040810204081L>>>(63-sq))&(occupation|0x80808080808080FFL);
return (((0x8040201008040201L>>>(63-Long.numberOfTrailingZeros(piecesup)))&(0x8040201008040201L<<(0x3F ^ Long.numberOfLeadingZeros(piecesdo)))) |
((0x8102040810204081L>>>(63-Long.numberOfTrailingZeros(piecesle)))&(0x8102040810204081L<<(0x3F ^ Long.numberOfLeadingZeros(piecesri)))))^piece;
}
/* return the bitboard with pieces of the same type */
static long BBPieces(TBoard Position,long piece) {
// find the bb with the pieces of the same type
if (piece == PAWN) return Pawns(Position);
if (piece == KNIGHT) return Knights(Position);
if (piece == BISHOP) return Bishops(Position);
if (piece == ROOK) return Rooks(Position);
if (piece == QUEEN) return Queens(Position);
/*if (piece == KING)*/ return Kings(Position);
}
/* return the bitboard with the destinations of a piece in a square (exept for pawns) */
static long BBDestinations(long piece,long sq,long occupation) {
// generate the destination squares of the piece
if (piece == KNIGHT) return KnightDest[(int)sq];
if (piece == BISHOP) return GenBishop(sq,occupation);
if (piece == ROOK) return GenRook(sq,occupation);
if (piece == QUEEN) return GenRook(sq,occupation)|GenBishop(sq,occupation);
/*if (piece == KING)*/ return KingDest[(int)sq];
}
/* try the move and see if the king is in check. If so return the attacking pieces, if not return 0 */
static boolean Illegal(TBoard Position, int move) {
int moveType = move & 0xff;
int moveFrom = (move >> 8) & 0xff;
int moveTo = (move >> 16) & 0xff;
long From = 1L<<moveFrom;
long To = 1L<<moveTo;
long occupation,opposing;
occupation = Occupation(Position);
opposing = Position.PM^occupation;
long kings = Kings(Position);
long king, kingsq;
long newoccupation = (occupation^From)|To;
long newopposing = opposing&~To;
if ((moveType&0x07)==KING) {
king = To;
kingsq = moveTo;
} else {
king = kings & Position.PM;
kingsq = Long.numberOfTrailingZeros(king);
if ((moveType&EP) != 0) {newopposing^=To>>8; newoccupation^=To>>8;}
}
if ((KnightDest[(int)kingsq] & Knights(Position) & newopposing) != 0) return true;
if (((((king<<9)&0xFEFEFEFEFEFEFEFEL) | ((king<<7)&0x7F7F7F7F7F7F7F7FL)) & Pawns(Position) & newopposing) != 0) return true;
long qob = QueenOrBishops(Position) & newopposing; if (qob != 0) { if ((GenBishop(kingsq,newoccupation) & qob) != 0) return true; }
long qor = QueenOrRooks(Position) & newopposing; if (qor != 0) { if ((GenRook(kingsq,newoccupation) & qor) != 0) return true; }
if ((KingDest[(int)kingsq] & kings & newopposing) != 0) return true;
return false;
}
/* Generate all pseudo-legal quiet moves */
static int GenerateQuiets(TBoard Position, int[] quiets, int pquiets) {
long occupation,opposing;
occupation = Occupation(Position);
opposing = occupation^Position.PM;
for (long piece=KING;piece>=KNIGHT;piece--) { // generate moves from king to knight
// generate moves for every piece of the same type of the side to move
for (long pieces=BBPieces(Position,piece)&Position.PM;pieces!=0;pieces=ClearLSB(pieces)) {
long sq = Long.numberOfTrailingZeros(pieces);
// for every destinations on a free square generate a move
for (long destinations = ~occupation&BBDestinations(piece,sq,occupation);destinations!=0;destinations=ClearLSB(destinations)) {
quiets[pquiets++] = (int)(piece + (sq << 8) + (Long.numberOfTrailingZeros(destinations) << 16) + (EMPTY << 24));
}
}
}
/* one pawns push */
long push1 = (((Pawns(Position)&Position.PM)<<8) & ~occupation)&0x00FFFFFFFFFFFFFFL;
for (long pieces=push1;pieces!=0;pieces=ClearLSB(pieces)) {
long lsb = Long.numberOfTrailingZeros(pieces);
quiets[pquiets++] = (int)(PAWN + ((lsb-8) << 8) + (lsb << 16) + (EMPTY << 24));
}
/* double pawns pushes */
for (long push2 = (push1<<8) & ~occupation & 0x00000000FF000000L;push2!=0;push2=ClearLSB(push2)) {
long lsb = Long.numberOfTrailingZeros(push2);
quiets[pquiets++] = (int)(PAWN + ((lsb-16) << 8) + (lsb << 16) + (EMPTY << 24));
}
/* check if long castling is possible */
if (CastleLM(Position) && (occupation & 0x0EL) == 0) {
long roo,bis;
roo = ExtractLSB(0x1010101010101000L&occupation); /* column e */
roo |= ExtractLSB(0x0808080808080800L&occupation); /*column d */
roo |= ExtractLSB(0x0404040404040400L&occupation); /*column c */
roo |= ExtractLSB(0x00000000000000E0L&occupation); /* row 1 */
bis = ExtractLSB(0x0000000102040800L&occupation); /*antidiag from e1/e8 */
bis |= ExtractLSB(0x0000000001020400L&occupation); /*antidiag from d1/d8 */
bis |= ExtractLSB(0x0000000000010200L&occupation); /*antidiag from c1/c8 */
bis |= ExtractLSB(0x0000000080402000L&occupation); /*diag from e1/e8 */
bis |= ExtractLSB(0x0000008040201000L&occupation); /*diag from d1/d8 */
bis |= ExtractLSB(0x0000804020100800L&occupation); /*diag from c1/c8 */
if ((((roo&QueenOrRooks(Position)) | (bis&QueenOrBishops(Position)) | (0x00000000003E7700L&Knights(Position))|
(0x0000000000003E00L&Pawns(Position)) | (Kings(Position)&0x0000000000000600L))&opposing) == 0) {
/* check if c1/c8 d1/d8 e1/e8 are not attacked */
quiets[pquiets++] = (int)((KING|CASTLE) + (4 << 8) + (2 << 16) + (EMPTY << 24));
}
}
/* check if short castling is possible */
if (CastleSM(Position) && (occupation & 0x60L) == 0) {
long roo,bis;
roo = ExtractLSB(0x1010101010101000L&occupation); /* column e */
roo |= ExtractLSB(0x2020202020202000L&occupation); /* column f */
roo |= ExtractLSB(0x4040404040404000L&occupation); /* column g */
roo |= 1L<<(0x3F ^ Long.numberOfLeadingZeros(0x000000000000000FL&(occupation|0x1L)));/* row 1 */
bis = ExtractLSB(0x0000000102040800L&occupation); /* antidiag from e1/e8 */
bis |= ExtractLSB(0x0000010204081000L&occupation); /*antidiag from f1/f8 */
bis |= ExtractLSB(0x0001020408102000L&occupation); /*antidiag from g1/g8 */
bis |= ExtractLSB(0x0000000080402000L&occupation); /*diag from e1/e8 */
bis |= ExtractLSB(0x0000000000804000L&occupation); /*diag from f1/f8 */
bis |= 0x0000000000008000L; /*diag from g1/g8 */
if ((((roo&QueenOrRooks(Position)) | (bis&QueenOrBishops(Position)) | (0x0000000000F8DC00L&Knights(Position))|
(0x000000000000F800L&Pawns(Position)) | (Kings(Position)&0x0000000000004000L))&opposing) == 0) {
/* check if e1/e8 f1/f8 g1/g8 are not attacked */
quiets[pquiets++] = (int)((KING|CASTLE) + (4 << 8) + (6 << 16) + (EMPTY << 24));
}
}
return pquiets;
}
/* Generate all pseudo-legal capture and promotions */
static int GenerateCapture(TBoard Position, int[] capture, int pcapture) {
long opposing,occupation;
occupation = Occupation(Position);
opposing = Position.PM ^ occupation;
for (long piece=KING;piece>=KNIGHT;piece--) { // generate moves from king to knight
// generate moves for every piece of the same type of the side to move
for (long pieces=BBPieces(Position,piece)&Position.PM;pieces!=0;pieces=ClearLSB(pieces)) {
long sq = Long.numberOfTrailingZeros(pieces);
// for every destinations on an opponent pieces generate a move
for (long destinations = opposing&BBDestinations(piece,sq,occupation);destinations!=0;destinations=ClearLSB(destinations)) {
capture[pcapture++] = (int)((piece|CAPTURE) + (sq << 8) + (Long.numberOfTrailingZeros(destinations) << 16) + (EMPTY << 24));
}
}
}
/* Generate pawns right captures */
long pieces = Pawns(Position)&Position.PM;
for (long captureri = (pieces<<9) & 0x00FEFEFEFEFEFEFEL & opposing;captureri!=0;captureri = ClearLSB(captureri)) {
long lsb = Long.numberOfTrailingZeros(captureri);
capture[pcapture++] = (int)((PAWN|CAPTURE) + ((lsb-9) << 8) + (lsb << 16) + (EMPTY << 24));
}
/* Generate pawns left captures */
for (long capturele = (pieces<<7) & 0x007F7F7F7F7F7F7FL & opposing;capturele!=0;capturele = ClearLSB(capturele)) {
long lsb = Long.numberOfTrailingZeros(capturele);
capture[pcapture++] = (int)((PAWN|CAPTURE) + ((lsb-7) << 8) + (lsb << 16) + (EMPTY << 24));
}
/* Generate pawns promotions */
if ((pieces&0x00FF000000000000L)!=0) {
/* promotions with left capture */
for (long promo = (pieces<<9) & 0xFE00000000000000L & opposing;promo!=0;promo = ClearLSB(promo)) {
long lsb = Long.numberOfTrailingZeros(promo);
long withoutPiece = (PAWN|PROMO|CAPTURE) + ((lsb-9) << 8) + (lsb << 16);
for (long piece=QUEEN;piece>=KNIGHT;piece--) { /* generate underpromotions */
capture[pcapture++] = (int)(withoutPiece + (piece << 24));
}
}
/* promotions with right capture */
for (long promo = (pieces<<7) & 0x7F00000000000000L & opposing;promo!=0;promo = ClearLSB(promo)) {
long lsb = Long.numberOfTrailingZeros(promo);
long withoutPiece = (PAWN|PROMO|CAPTURE) + ((lsb-7) << 8) + (lsb << 16);
for (long piece=QUEEN;piece>=KNIGHT;piece--) { /* generate underpromotions */
capture[pcapture++] = (int)(withoutPiece + (piece << 24));
}
}
/* no capture promotions */
for (long promo = ((pieces<<8) & ~occupation)&0xFF00000000000000L;promo!=0;promo = ClearLSB(promo)) {
long lsb = Long.numberOfTrailingZeros(promo);
long withoutPiece = (PAWN|PROMO) + ((lsb-8) << 8) + (lsb << 16);
for (long piece=QUEEN;piece>=KNIGHT;piece--) { /* generate underpromotions */
capture[pcapture++] = (int)(withoutPiece + (piece << 24));
}
}
}
if (Position.EnPassant!=8) {
/* Generate EnPassant captures */
for (long enpassant = pieces&EnPassant[Position.EnPassant]; enpassant!=0; enpassant=ClearLSB(enpassant)) {
capture[pcapture++] = (int)((PAWN|EP|CAPTURE) + (Long.numberOfTrailingZeros(enpassant) << 8) + ((40+Position.EnPassant) << 16) + (EMPTY << 24));
}
}
return pcapture;
}
/* Make the move */
static void Make(int move) {
int moveType = move & 0xff;
int moveTypePiece = moveType & 7;
int moveFrom = (move >> 8) & 0xff;
int moveTo = (move >> 16) & 0xff;
int moveProm = move >> 24;
TBoard Position = Game[++pPosition];
/* copy the previous position into the last one */
Position.PM = Game[pPosition-1].PM;
Position.P0 = Game[pPosition-1].P0;
Position.P1 = Game[pPosition-1].P1;
Position.P2 = Game[pPosition-1].P2;
Position.CastleFlags = Game[pPosition-1].CastleFlags;
Position.EnPassant = Game[pPosition-1].EnPassant;
Position.STM = Game[pPosition-1].STM;
long part = 1L<<moveFrom;
long dest = 1L<<moveTo;
if (moveTypePiece == PAWN) {
if ((moveType&EP) != 0) {
/* EnPassant */
Position.PM^=part|dest;
Position.P0^=part|dest;
Position.P0^=dest>>8; /* delete the captured pawn */
Position.EnPassant=8;
} else {
if ((moveType&CAPTURE) != 0) {
/* Delete the captured piece */
Position.P0&=~dest;
Position.P1&=~dest;
Position.P2&=~dest;
}
if ((moveType&PROMO) != 0) {
Position.PM^=part|dest;
Position.P0^=part;
Position.P0|=(long)(moveProm&1)<<(moveTo);
Position.P1|=(long)(((moveProm)>>1)&1)<<(moveTo);
Position.P2|=(long)((moveProm)>>2)<<(moveTo);
Position.EnPassant=8; /* clear enpassant */
} else { /* capture or push */
Position.PM^=part|dest;
Position.P0^=part|dest;
Position.EnPassant=8; /* clear enpassant */
if (moveTo==moveFrom+16 && (EnPassantM[moveTo&0x07]&Pawns(Position)&(Position.PM^(Occupation(Position)))) != 0)
Position.EnPassant=(byte)(moveTo&0x07); /* save enpassant column */
}
if ((moveType&CAPTURE) != 0) {
if (moveTo==63) Position.CastleFlags&=0xDF; // ResetCastleSO /* captured the opponent king side rook */
else if (moveTo==56) Position.CastleFlags&=0xEF; // ResetCastleLO /* captured the opponent quuen side rook */
}
}
ChangeSide(Position);
} else if (moveTypePiece == KNIGHT || moveTypePiece == BISHOP || moveTypePiece == ROOK || moveTypePiece == QUEEN) {
if ((moveType&CAPTURE) != 0) {
Position.P0&=~dest;
Position.P1&=~dest;
Position.P2&=~dest;
}
Position.PM^=part|dest;
Position.P0^=(moveType&1) != 0 ? part|dest : 0;
Position.P1^=(moveType&2) != 0 ? part|dest : 0;
Position.P2^=(moveType&4) != 0 ? part|dest : 0;
Position.EnPassant=8;
if (moveTypePiece==ROOK) { /* update the castle rights */
if (moveFrom==7) Position.CastleFlags&=0xFD; // ResetCastleSM
else if (moveFrom==0) Position.CastleFlags&=0xFE; // ResetCastleLM
}
if ((moveType&CAPTURE) != 0) { /* update the castle rights */
if (moveTo==63) Position.CastleFlags&=0xDF; // ResetCastleSO
else if (moveTo==56) Position.CastleFlags&=0xEF; // ResetCastleLO
}
ChangeSide(Position);
} else if (moveTypePiece == KING) {
if ((moveType&CAPTURE) != 0) {
Position.P0&=~dest;
Position.P1&=~dest;
Position.P2&=~dest;
}
Position.PM^=part|dest;
Position.P1^=part|dest;
Position.P2^=part|dest;
/* update the castle rights */
Position.CastleFlags&=0xFD; // ResetCastleSM
Position.CastleFlags&=0xFE; // ResetCastleLM
Position.EnPassant=8;
if ((moveType&CAPTURE) != 0) {
if (moveTo==63) Position.CastleFlags&=0xDF; // ResetCastleSO
else if (moveTo==56) Position.CastleFlags&=0xEF; // ResetCastleLO
} else if ((moveType&CASTLE) != 0) {
if (moveTo==6) { Position.PM^=0x00000000000000A0L; Position.P2^=0x00000000000000A0L; } /* short castling */
else { Position.P2^=0x0000000000000009L; Position.PM^=0x0000000000000009L; } /* long castling */
}
ChangeSide(Position);
}
}
/*
Load a position starting from a fen.
This function doesn't check the correctness of the fen.
*/
static void LoadPosition(String fen) {
/* Clear the board */
pPosition = 0;
TBoard Position=Game[0];
Position.P0 = Position.P1 = Position.P2 = Position.PM = 0;
Position.EnPassant=8;
Position.STM=(byte)WHITE;
Position.CastleFlags=0;
/* translate the fen to the relative position */
long pieceside=WHITE;
long piece=PAWN;
long sidetomove=WHITE;
long square=0;
int cursor;
for (cursor=0;fen.charAt(cursor)!=' ';cursor++) {
char c = fen.charAt(cursor);
if (c>='1' && c<='8') square += c - '0';
else if (c=='/') continue;
else {
long pos = OppSq(square);
if (c=='p') { piece = PAWN; pieceside = BLACK; }
else if (c=='n') { piece = KNIGHT; pieceside = BLACK; }
else if (c=='b') { piece = BISHOP; pieceside = BLACK; }
else if (c=='r') { piece = ROOK; pieceside = BLACK; }
else if (c=='q') { piece = QUEEN; pieceside = BLACK; }
else if (c=='k') { piece = KING; pieceside = BLACK; }
else if (c=='P') { piece = PAWN; pieceside = WHITE; }
else if (c=='N') { piece = KNIGHT; pieceside = WHITE; }
else if (c=='B') { piece = BISHOP; pieceside = WHITE; }
else if (c=='R') { piece = ROOK; pieceside = WHITE; }
else if (c=='Q') { piece = QUEEN; pieceside = WHITE; }
else if (c=='K') { piece = KING; pieceside = WHITE; }
Position.P0|=(piece&1)<<pos;
Position.P1|=((piece>>1)&1)<<pos;
Position.P2|=(piece>>2)<<pos;
if (pieceside==WHITE) { Position.PM |= 1L<<pos; piece|=BLACK; }
square++;
}
}
cursor++; /* read the side to move */
if (fen.charAt(cursor)=='w') sidetomove=WHITE;
else if (fen.charAt(cursor)=='b') sidetomove=BLACK;
cursor+=2;
if (fen.charAt(cursor)!='-') { /* read the castle rights */
for (;fen.charAt(cursor)!=' ';cursor++) {
char c = fen.charAt(cursor);
if (c=='K') Position.CastleFlags|=0x02;
else if (c=='Q') Position.CastleFlags|=0x01;
else if (c=='k') Position.CastleFlags|=0x20;
else if (c=='q') Position.CastleFlags|=0x10;
}
cursor++;
}
else cursor+=2;
if (fen.charAt(cursor)!='-') { /* read the enpassant column */
Position.EnPassant= (byte)(fen.charAt(cursor) - 'a');
}
if (sidetomove==BLACK) ChangeSide(Position);
}
/* Check the correctness of the move generator with the Perft function */
static long Perft(int depth) {
int[] moves = new int[256 + 64];
long tot = 0;
TBoard Position = Game[pPosition];
int numMoves = GenerateCapture(Position, moves, 0);
numMoves = GenerateQuiets(Position, moves, numMoves);
for (int m = 0; m < numMoves; ++m) {
int move = moves[m];
if (Illegal(Position, move)) continue;
if (depth>1) {
Make(move);
tot+=Perft(depth-1);
pPosition--;
}
else tot++;
}
return tot;
}
static class PerftSettings {
String fen;
int depth;
long expectedCount;
PerftSettings(String fen, int depth, long expectedCount) {
this.fen = fen;
this.depth = depth;
this.expectedCount = expectedCount;
}
}
/* Run the Perft with this 6 test positions */
static void TestPerft() {
PerftSettings[] Test = {
new PerftSettings("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1",6,119060324),
new PerftSettings("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1",5,193690690),
new PerftSettings("8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1", 7,178633661),
new PerftSettings("r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1",6,706045033),
new PerftSettings("rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6",3,53392),
new PerftSettings("r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10",5,164075551)};
long totalCount = 0;
long totalTime = 0;
for (PerftSettings test : Test) {
LoadPosition(test.fen);
long time = System.nanoTime();
long actualCount = Perft(test.depth);
time = System.nanoTime() - time;
totalCount += actualCount;
totalTime += time;
System.out.printf("%5.0f ms, %.0f knps%s\n", time*1e-6, actualCount * 1e6 / time,
actualCount == test.expectedCount ? "" : (" -- ERROR: expected " + test.expectedCount + " got " + actualCount));
}
System.out.printf("Total: %.0f ms, %.0f knps\n", totalTime*1e-6, totalCount * 1e6 / totalTime);
}
public static void main(String[] args) {
System.out.println("QBB Perft in Java");
TestPerft();
}
}
[Moderation warning] This signature violated the rule against commercial exhortations.
-
R. Tomasi
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Why C++ instead of C#?
I finally got the time to implment the changes to the C version. I removed the redundant checks before clearing castling flags, removed redundant LSBs and changed MAX_PLY to the same value as in the C# version (32). Additionally I added a custom implementation of the clock_gettime POSIX function that compiles on windows.
Performance of the C version as it is currently in the repository:
Performance of the C version after the changes:
As expected, the performance impact is not of significance (it's smaller than the variations between different runs on my machine). Beware that I compiled against the MSVC Console project settings using clang. The option for -O3 and -native were not available to me, therefore. Somebody else should compile the code with all optimizations enabled to have results that are "real".
Here's the source code:
Performance of the C version as it is currently in the repository:
Code: Select all
QBB Perft in C
Expected: 119060324 Computed: 119060324
2713 ms, 43885K NPS
Expected: 193690690 Computed: 193690690
3946 ms, 49085K NPS
Expected: 178633661 Computed: 178633661
4473 ms, 39935K NPS
Expected: 706045033 Computed: 706045033
14610 ms, 48326K NPS
Expected: 53392 Computed: 53392
1 ms, 53392K NPS
Expected: 164075551 Computed: 164075551
3239 ms, 50656K NPS
Total: 1361558651 Nodes, 28982 ms, 46979K NPS
Code: Select all
QBB Perft in C
Expected: 119060324 Computed: 119060324
3093 ms, 38493K NPS
Expected: 193690690 Computed: 193690690
3776 ms, 51295K NPS
Expected: 178633661 Computed: 178633661
4068 ms, 43911K NPS
Expected: 706045033 Computed: 706045033
14628 ms, 48266K NPS
Expected: 53392 Computed: 53392
1 ms, 53392K NPS
Expected: 164075551 Computed: 164075551
3358 ms, 48861K NPS
Total: 1361558651 Nodes, 28924 ms, 47073K NPS
Here's the source code:
Code: Select all
/*
This perft implementation is based on QBBEngine by Fabio Gobbato
Some parts of this source call gcc intrinsic functions. If you are not using gcc you need to
change them with the functions of your compiler.
*/
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>
#define WHITE 0
#define BLACK 8
#define MAX_PLY 32
/* define the piece type: empty, pawn, knight, bishop, rook, queen, king */
typedef enum {EMPTY,PAWN,KNIGHT,BISHOP,ROOK,QUEEN,KING} TPieceType;
/* define the move type, for example
KING|CASTLE is a castle move
PAWN|CAPTURE|EP is an enpassant move
PAWN|PROMO|CAPTURE is a promotion with a capture */
typedef enum {CASTLE=0x40,PROMO=0x20,EP=0x10,CAPTURE=0x08} TMoveType;
/* bitboard types */
typedef uint64_t TBB;
/* move structure */
typedef union
{
struct{
uint8_t MoveType;
uint8_t From;
uint8_t To;
uint8_t Prom;};
unsigned int Move;
}TMove;
/* structure for a capture, it needs the Eval field for MVV/LVA ordering */
typedef struct
{
TMove Move;
//int Eval;
} TMoveEval;
/*
Board structure definition
PM,P0,P1,P2 are the 4 bitboards that contain the whole board
PM is the bitboard with the side to move pieces
P0,P1 and P2: with these bitboards you can obtain every type of pieces and every pieces combinations.
*/
typedef struct
{
TBB PM;
TBB P0;
TBB P1;
TBB P2;
uint8_t CastleFlags; /* ..sl..SL short long opponent SHORT LONG side to move */
uint8_t EnPassant; /* enpassant column, =8 if not set */
uint8_t STM; /* side to move */
} TBoard;
/*
Into Game are saved all the positions from the last 50 move counter reset
Position is the pointer to the last position of the game
*/
TBoard Game[MAX_PLY];
TBoard *Position;
/* array of bitboards that contains all the knight destination for every square */
const TBB KnightDest[64]= {0x0000000000020400ULL,0x0000000000050800ULL,0x00000000000a1100ULL,0x0000000000142200ULL,
0x0000000000284400ULL,0x0000000000508800ULL,0x0000000000a01000ULL,0x0000000000402000ULL,
0x0000000002040004ULL,0x0000000005080008ULL,0x000000000a110011ULL,0x0000000014220022ULL,
0x0000000028440044ULL,0x0000000050880088ULL,0x00000000a0100010ULL,0x0000000040200020ULL,
0x0000000204000402ULL,0x0000000508000805ULL,0x0000000a1100110aULL,0x0000001422002214ULL,
0x0000002844004428ULL,0x0000005088008850ULL,0x000000a0100010a0ULL,0x0000004020002040ULL,
0x0000020400040200ULL,0x0000050800080500ULL,0x00000a1100110a00ULL,0x0000142200221400ULL,
0x0000284400442800ULL,0x0000508800885000ULL,0x0000a0100010a000ULL,0x0000402000204000ULL,
0x0002040004020000ULL,0x0005080008050000ULL,0x000a1100110a0000ULL,0x0014220022140000ULL,
0x0028440044280000ULL,0x0050880088500000ULL,0x00a0100010a00000ULL,0x0040200020400000ULL,
0x0204000402000000ULL,0x0508000805000000ULL,0x0a1100110a000000ULL,0x1422002214000000ULL,
0x2844004428000000ULL,0x5088008850000000ULL,0xa0100010a0000000ULL,0x4020002040000000ULL,
0x0400040200000000ULL,0x0800080500000000ULL,0x1100110a00000000ULL,0x2200221400000000ULL,
0x4400442800000000ULL,0x8800885000000000ULL,0x100010a000000000ULL,0x2000204000000000ULL,
0x0004020000000000ULL,0x0008050000000000ULL,0x00110a0000000000ULL,0x0022140000000000ULL,
0x0044280000000000ULL,0x0088500000000000ULL,0x0010a00000000000ULL,0x0020400000000000ULL};
/* The same for the king */
const TBB KingDest[64] = {0x0000000000000302ULL,0x0000000000000705ULL,0x0000000000000e0aULL,0x0000000000001c14ULL,
0x0000000000003828ULL,0x0000000000007050ULL,0x000000000000e0a0ULL,0x000000000000c040ULL,
0x0000000000030203ULL,0x0000000000070507ULL,0x00000000000e0a0eULL,0x00000000001c141cULL,
0x0000000000382838ULL,0x0000000000705070ULL,0x0000000000e0a0e0ULL,0x0000000000c040c0ULL,
0x0000000003020300ULL,0x0000000007050700ULL,0x000000000e0a0e00ULL,0x000000001c141c00ULL,
0x0000000038283800ULL,0x0000000070507000ULL,0x00000000e0a0e000ULL,0x00000000c040c000ULL,
0x0000000302030000ULL,0x0000000705070000ULL,0x0000000e0a0e0000ULL,0x0000001c141c0000ULL,
0x0000003828380000ULL,0x0000007050700000ULL,0x000000e0a0e00000ULL,0x000000c040c00000ULL,
0x0000030203000000ULL,0x0000070507000000ULL,0x00000e0a0e000000ULL,0x00001c141c000000ULL,
0x0000382838000000ULL,0x0000705070000000ULL,0x0000e0a0e0000000ULL,0x0000c040c0000000ULL,
0x0003020300000000ULL,0x0007050700000000ULL,0x000e0a0e00000000ULL,0x001c141c00000000ULL,
0x0038283800000000ULL,0x0070507000000000ULL,0x00e0a0e000000000ULL,0x00c040c000000000ULL,
0x0302030000000000ULL,0x0705070000000000ULL,0x0e0a0e0000000000ULL,0x1c141c0000000000ULL,
0x3828380000000000ULL,0x7050700000000000ULL,0xe0a0e00000000000ULL,0xc040c00000000000ULL,
0x0203000000000000ULL,0x0507000000000000ULL,0x0a0e000000000000ULL,0x141c000000000000ULL,
0x2838000000000000ULL,0x5070000000000000ULL,0xa0e0000000000000ULL,0x40c0000000000000ULL};
/* masks for finding the pawns that can capture with an enpassant (in move generation) */
const TBB EnPassant[8] = {
0x0000000200000000ULL,0x0000000500000000ULL,0x0000000A00000000ULL,0x0000001400000000ULL,
0x0000002800000000ULL,0x0000005000000000ULL,0x000000A000000000ULL,0x0000004000000000ULL
};
/* masks for finding the pawns that can capture with an enpassant (in make move) */
const TBB EnPassantM[8] = {
0x0000000002000000ULL,0x0000000005000000ULL,0x000000000A000000ULL,0x0000000014000000ULL,
0x0000000028000000ULL,0x0000000050000000ULL,0x00000000A0000000ULL,0x0000000040000000ULL
};
/*
reverse a bitboard:
A bitboard is an array of byte: Byte0,Byte1,Byte2,Byte3,Byte4,Byte5,Byte6,Byte7
after this function the bitboard will be: Byte7,Byte6,Byte5,Byte4,Byte3,Byte2,Byte1,Byte0
The board is saved always with the side to move in the low significant bits of the bitboard, so this function
is used to change the side to move
*/
#define RevBB(bb) (__builtin_bswap64(bb))
/* return the index of the most significant bit of the bitboard, bb must always be !=0 */
#define MSB(bb) (0x3F ^ __builtin_clzll(bb))
/* return the index of the least significant bit of the bitboard, bb must always be !=0 */
#define LSB(bb) (__builtin_ctzll(bb))
/* extract the least significant bit of the bitboard */
#define ExtractLSB(bb) ((bb)&(-(bb)))
/* reset the least significant bit of bb */
#define ClearLSB(bb) ((bb)&((bb)-1))
/* return the number of bits sets of a bitboard */
#define PopCount(bb) (__builtin_popcountll(bb))
/* Macro to check and reset the castle rights:
CastleSM: short castling side to move
CastleLM: long castling side to move
CastleSO: short castling opponent
CastleLO: long castling opponent
*/
#define CastleSM (Position->CastleFlags&0x02)
#define CastleLM (Position->CastleFlags&0x01)
#define CastleSO (Position->CastleFlags&0x20)
#define CastleLO (Position->CastleFlags&0x10)
#define ResetCastleSM (Position->CastleFlags&=0xFD)
#define ResetCastleLM (Position->CastleFlags&=0xFE)
#define ResetCastleSO (Position->CastleFlags&=0xDF)
#define ResetCastleLO (Position->CastleFlags&=0xEF)
/* these Macros are used to calculate the bitboard of a particular kind of piece
P2 P1 P0
0 0 0 empty
0 0 1 pawn
0 1 0 knight
0 1 1 bishop
1 0 0 rook
1 0 1 queen
1 1 0 king
*/
#define Occupation (Position->P0 | Position->P1 | Position->P2) /* board occupation */
#define Pawns (Position->P0 & ~Position->P1 & ~Position->P2) /* all the pawns on the board */
#define Knights (~Position->P0 & Position->P1 & ~Position->P2)
#define Bishops (Position->P0 & Position->P1)
#define Rooks (~Position->P0 & ~Position->P1 & Position->P2)
#define Queens (Position->P0 & Position->P2)
#define Kings (Position->P1 & Position->P2) /* a bitboard with the 2 kings */
/* get the piece type giving the square */
#define Piece(sq) (((Position->P2>>(sq))&1)<<2 | ((Position->P1>>(sq))&1)<<1 | ((Position->P0>>(sq))&1))
/* calculate the square related to the opponent */
#define OppSq(sp) ((sp)^0x38)
/* Absolute Square, we need this macro to return the move in long algebric notation */
#define AbsSq(sq,col) ((col)==WHITE ? (sq):OppSq(sq))
/* get the corresponding string to the given move */
static inline void MoveToStr(char *strmove,TMove move,uint8_t tomove)
{
const char promo[7]="\0\0nbrq";
strmove[0] = 'a' + AbsSq(move.From,tomove) % 8;
strmove[1] = '1' + AbsSq(move.From,tomove) / 8;
strmove[2] = 'a' + AbsSq(move.To,tomove) % 8;
strmove[3] = '1' + AbsSq(move.To,tomove) / 8;
strmove[4] = promo[move.Prom];
strmove[5] = '\0';
}
/*
The board is always saved with the side to move in the lower part of the bitboards to use the same generation and
make for the Black and the White side.
This needs the inversion of the 4 bitboards, roll the Castle rights and update the side to move.
*/
#define ChangeSide \
do{ \
Position->PM^=Occupation; /* update the side to move pieces */\
Position->PM=RevBB(Position->PM);\
Position->P0=RevBB(Position->P0);\
Position->P1=RevBB(Position->P1);\
Position->P2=RevBB(Position->P2);/* reverse the board */\
Position->CastleFlags=(Position->CastleFlags>>4)|(Position->CastleFlags<<4);/* roll the castle rights */\
Position->STM ^= BLACK; /* change the side to move */\
}while(0)
/* return the bitboard with the rook destinations */
static inline TBB GenRook(uint64_t sq,TBB occupation)
{
TBB piece = 1ULL<<sq;
occupation ^= piece; /* remove the selected piece from the occupation */
TBB piecesup=(0x0101010101010101ULL<<sq)&(occupation|0xFF00000000000000ULL); /* find the pieces up */
TBB piecesdo=(0x8080808080808080ULL>>(63-sq))&(occupation|0x00000000000000FFULL); /* find the pieces down */
TBB piecesri=(0x00000000000000FFULL<<sq)&(occupation|0x8080808080808080ULL); /* find pieces on the right */
TBB piecesle=(0xFF00000000000000ULL>>(63-sq))&(occupation|0x0101010101010101ULL); /* find pieces on the left */
return (((0x8080808080808080ULL>>(63-LSB(piecesup)))&(0x0101010101010101ULL<<MSB(piecesdo))) |
((0xFF00000000000000ULL>>(63-LSB(piecesri)))&(0x00000000000000FFULL<<MSB(piecesle))))^piece;
/* From every direction find the first piece and from that piece put a mask in the opposite direction.
Put togheter all the 4 masks and remove the moving piece */
}
/* return the bitboard with the bishops destinations */
static inline TBB GenBishop(uint64_t sq,TBB occupation)
{ /* it's the same as the rook */
TBB piece = 1ULL<<sq;
occupation ^= piece;
TBB piecesup=(0x8040201008040201ULL<<sq)&(occupation|0xFF80808080808080ULL);
TBB piecesdo=(0x8040201008040201ULL>>(63-sq))&(occupation|0x01010101010101FFULL);
TBB piecesle=(0x8102040810204081ULL<<sq)&(occupation|0xFF01010101010101ULL);
TBB piecesri=(0x8102040810204081ULL>>(63-sq))&(occupation|0x80808080808080FFULL);
return (((0x8040201008040201ULL>>(63-LSB(piecesup)))&(0x8040201008040201ULL<<MSB(piecesdo))) |
((0x8102040810204081ULL>>(63-LSB(piecesle)))&(0x8102040810204081ULL<<MSB(piecesri))))^piece;
}
/* return the bitboard with pieces of the same type */
static inline TBB BBPieces(TPieceType piece)
{
switch(piece) // find the bb with the pieces of the same type
{
case PAWN: return Pawns;
case KNIGHT: return Knights;
case BISHOP: return Bishops;
case ROOK: return Rooks;
case QUEEN: return Queens;
case KING: return Kings;
}
}
/* return the bitboard with the destinations of a piece in a square (exept for pawns) */
static inline TBB BBDestinations(TPieceType piece,uint64_t sq,TBB occupation)
{
switch(piece) // generate the destination squares of the piece
{
case KNIGHT: return KnightDest[sq];
case BISHOP: return GenBishop(sq,occupation);
case ROOK: return GenRook(sq,occupation);
case QUEEN: return GenRook(sq,occupation)|GenBishop(sq,occupation);
case KING: return KingDest[sq];
}
}
/* try the move and see if the king is in check. If so return the attacking pieces, if not return 0 */
static inline TBB Illegal(TMove move)
{
TBB From,To;
From = 1ULL<<move.From;
To = 1ULL<<move.To;
TBB occupation,opposing;
occupation = Occupation;
opposing = Position->PM^occupation;
TBB newoccupation,newopposing;
TBB king;
uint64_t kingsq;
newoccupation = (occupation^From)|To;
newopposing = opposing&~To;
if ((move.MoveType&0x07)==KING)
{
king = To;
kingsq = move.To;
}
else
{
king = Kings&Position->PM;
kingsq = LSB(king);
if (move.MoveType&EP) {newopposing^=To>>8; newoccupation^=To>>8;}
}
return (((KnightDest[kingsq]&Knights)|
(GenRook(kingsq,newoccupation)&(Rooks|Queens))|
(GenBishop(kingsq,newoccupation)&(Bishops|Queens))|
((((king<<9)&0xFEFEFEFEFEFEFEFEULL)|((king<<7)&0x7F7F7F7F7F7F7F7FULL))&Pawns)|
(KingDest[kingsq]&Kings))&newopposing);
}
/* Generate all pseudo-legal quiet moves */
static inline TMove *GenerateQuiets(TMove *const quiets)
{
TBB occupation,opposing;
occupation = Occupation;
opposing = occupation^Position->PM;
TMove *pquiets=quiets;
for (TPieceType piece=KING;piece>=KNIGHT;piece--) // generate moves from king to knight
{
// generate moves for every piece of the same type of the side to move
for (TBB pieces=BBPieces(piece)&Position->PM;pieces;pieces=ClearLSB(pieces))
{
uint64_t sq = LSB(pieces);
// for every destinations on a free square generate a move
for (TBB destinations = ~occupation&BBDestinations(piece,sq,occupation);destinations;destinations=ClearLSB(destinations))
{
pquiets->MoveType = piece;
pquiets->From = sq;
pquiets->To = LSB(destinations);
pquiets->Prom = EMPTY;
pquiets++;
}
}
}
/* one pawns push */
TBB push1 = (((Pawns&Position->PM)<<8) & ~occupation)&0x00FFFFFFFFFFFFFFULL;
for (TBB pieces=push1;pieces;pieces=ClearLSB(pieces))
{
pquiets->MoveType = PAWN;
pquiets->To = LSB(pieces);
pquiets->From = pquiets->To -8;
pquiets->Prom = EMPTY;
pquiets++;
}
/* double pawns pushes */
for (TBB push2 = (push1<<8) & ~occupation & 0x00000000FF000000ULL;push2;push2=ClearLSB(push2))
{
pquiets->MoveType = PAWN;
pquiets->To = LSB(push2);
pquiets->From = pquiets->To -16;
pquiets->Prom = EMPTY;
pquiets++;
}
/* check if long castling is possible */
if (CastleLM && !(occupation & 0x0EULL))
{
TBB roo,bis;
roo = ExtractLSB(0x1010101010101000ULL&occupation); /* column e */
roo |= ExtractLSB(0x0808080808080800ULL&occupation); /*column d */
roo |= ExtractLSB(0x0404040404040400ULL&occupation); /*column c */
roo |= ExtractLSB(0x00000000000000E0ULL&occupation); /* row 1 */
bis = ExtractLSB(0x0000000102040800ULL&occupation); /*antidiag from e1/e8 */
bis |= ExtractLSB(0x0000000001020400ULL&occupation); /*antidiag from d1/d8 */
bis |= ExtractLSB(0x0000000000010200ULL&occupation); /*antidiag from c1/c8 */
bis |= ExtractLSB(0x0000000080402000ULL&occupation); /*diag from e1/e8 */
bis |= ExtractLSB(0x0000008040201000ULL&occupation); /*diag from d1/d8 */
bis |= ExtractLSB(0x0000804020100800ULL&occupation); /*diag from c1/c8 */
if (!(((roo&(Rooks|Queens)) | (bis&(Bishops|Queens)) | (0x00000000003E7700ULL&Knights)|
(0x0000000000003E00ULL&Pawns) | (Kings&0x0000000000000600ULL))&opposing))
{ /* check if c1/c8 d1/d8 e1/e8 are not attacked */
pquiets->MoveType = KING|CASTLE;
pquiets->From = 4;
pquiets->To = 2;
pquiets->Prom = EMPTY;
pquiets++;
}
}
/* check if short castling is possible */
if (CastleSM && !(occupation & 0x60ULL))
{
TBB roo,bis;
roo = ExtractLSB(0x1010101010101000ULL&occupation); /* column e */
roo |= ExtractLSB(0x2020202020202000ULL&occupation); /* column f */
roo |= ExtractLSB(0x4040404040404000ULL&occupation); /* column g */
roo |= 1ULL<<MSB(0x000000000000000FULL&(occupation|0x1ULL));/* row 1 */
bis = ExtractLSB(0x0000000102040800ULL&occupation); /* antidiag from e1/e8 */
bis |= ExtractLSB(0x0000010204081000ULL&occupation); /*antidiag from f1/f8 */
bis |= ExtractLSB(0x0001020408102000ULL&occupation); /*antidiag from g1/g8 */
bis |= ExtractLSB(0x0000000080402000ULL&occupation); /*diag from e1/e8 */
bis |= ExtractLSB(0x0000000000804000ULL&occupation); /*diag from f1/f8 */
bis |= 0x0000000000008000ULL; /*diag from g1/g8 */
if (!(((roo&(Rooks|Queens)) | (bis&(Bishops|Queens)) | (0x0000000000F8DC00ULL&Knights)|
(0x000000000000F800ULL&Pawns) | (Kings&0x0000000000004000ULL))&opposing))
{ /* check if e1/e8 f1/f8 g1/g8 are not attacked */
pquiets->MoveType = KING|CASTLE;
pquiets->From = 4;
pquiets->To = 6;
pquiets->Prom = EMPTY;
pquiets++;
}
}
return pquiets;
}
/* Generate all pseudo-legal capture and promotions */
static inline TMoveEval *GenerateCapture(TMoveEval *const capture)
{
TBB opposing,occupation;
occupation = Occupation;
opposing = Position->PM ^ occupation;
TMoveEval *pcapture=capture;
for (TPieceType piece=KING;piece>=KNIGHT;piece--) // generate moves from king to knight
{
// generate moves for every piece of the same type of the side to move
for (TBB pieces=BBPieces(piece)&Position->PM;pieces;pieces=ClearLSB(pieces))
{
uint64_t sq = LSB(pieces);
// for every destinations on an opponent pieces generate a move
for (TBB destinations = opposing&BBDestinations(piece,sq,occupation);destinations;destinations=ClearLSB(destinations))
{
pcapture->Move.MoveType = piece|CAPTURE;
pcapture->Move.From = sq;
pcapture->Move.To = LSB(destinations);
pcapture->Move.Prom = EMPTY;
//pcapture->Eval = (Piece(LSB(destinations))<<4)|(KING-piece);
pcapture++;
}
}
}
/* Generate pawns right captures */
TBB pieces = Pawns&Position->PM;
for (TBB captureri = (pieces<<9) & 0x00FEFEFEFEFEFEFEULL & opposing;captureri;captureri = ClearLSB(captureri))
{
pcapture->Move.MoveType = PAWN|CAPTURE;
pcapture->Move.To = LSB(captureri);
pcapture->Move.From = pcapture->Move.To -9;
pcapture->Move.Prom = EMPTY;
//pcapture->Eval = (Piece(LSB(captureri))<<4)|(KING-PAWN);
pcapture++;
}
/* Generate pawns left captures */
for (TBB capturele = (pieces<<7) & 0x007F7F7F7F7F7F7FULL & opposing;capturele;capturele = ClearLSB(capturele))
{
pcapture->Move.MoveType = PAWN|CAPTURE;
pcapture->Move.To = LSB(capturele);
pcapture->Move.From = pcapture->Move.To -7;
pcapture->Move.Prom = EMPTY;
//pcapture->Eval = (Piece(LSB(capturele))<<4)|(KING-PAWN);
pcapture++;
}
/* Generate pawns promotions */
if (pieces&0x00FF000000000000ULL)
{
/* promotions with left capture */
for (TBB promo = (pieces<<9) & 0xFE00000000000000ULL & opposing;promo;promo = ClearLSB(promo))
{
TMove move;
move.MoveType = PAWN|PROMO|CAPTURE;
move.To = LSB(promo);
move.From = move.To -9;
move.Prom = QUEEN;
pcapture->Move = move;
//pcapture->Eval = (QUEEN<<4)|(KING-PAWN);
pcapture++;
for (TPieceType piece=ROOK;piece>=KNIGHT;piece--) /* generate underpromotions */
{
move.Prom = piece;
pcapture->Move = move;
//pcapture->Eval = piece-ROOK-1; /* keep behind the other captures-promotions */
pcapture++;
}
}
/* promotions with right capture */
for (TBB promo = (pieces<<7) & 0x7F00000000000000ULL & opposing;promo;promo = ClearLSB(promo))
{
TMove move;
move.MoveType = PAWN|PROMO|CAPTURE;
move.To = LSB(promo);
move.From = move.To -7;
move.Prom = QUEEN;
pcapture->Move = move;
//pcapture->Eval = (QUEEN<<4)|(KING-PAWN);
pcapture++;
for (TPieceType piece=ROOK;piece>=KNIGHT;piece--) /* generate underpromotions */
{
move.Prom = piece;
pcapture->Move = move;
//pcapture->Eval = piece-ROOK-1; /* keep behind the other captures-promotions */
pcapture++;
}
}
/* no capture promotions */
for (TBB promo = ((pieces<<8) & ~occupation)&0xFF00000000000000ULL;promo;promo = ClearLSB(promo))
{
TMove move;
move.MoveType = PAWN|PROMO;
move.To = LSB(promo);
move.From = move.To -8;
move.Prom = QUEEN;
pcapture->Move = move;
//pcapture->Eval = (QUEEN<<4)|(KING-PAWN);
pcapture++;
for (TPieceType piece=ROOK;piece>=KNIGHT;piece--) /* generate underpromotions */
{
move.Prom = piece;
pcapture->Move = move;
//pcapture->Eval = piece-ROOK-1; /* keep behind the other captures-promotions */
pcapture++;
}
}
}
if (Position->EnPassant!=8)
{ /* Generate EnPassant captures */
for (TBB enpassant = pieces&EnPassant[Position->EnPassant]; enpassant; enpassant=ClearLSB(enpassant))
{
pcapture->Move.MoveType = PAWN|EP|CAPTURE;
pcapture->Move.From = LSB(enpassant);
pcapture->Move.To = 40+Position->EnPassant;
pcapture->Move.Prom = EMPTY;
//pcapture->Eval = (PAWN<<4)|(KING-PAWN);
pcapture++;
}
}
return pcapture;
}
/* Make the move */
static inline void Make(TMove move)
{
Position++;
*Position=*(Position-1); /* copy the previous position into the last one */
TBB part = 1ULL<<move.From;
TBB dest = 1ULL<<move.To;
switch (move.MoveType&0x07)
{
case PAWN:
if (move.MoveType&EP)
{ /* EnPassant */
Position->PM^=part|dest;
Position->P0^=part|dest;
Position->P0^=dest>>8; /* delete the captured pawn */
Position->EnPassant=8;
}
else
{
if (move.MoveType&CAPTURE)
{ /* Delete the captured piece */
Position->P0&=~dest;
Position->P1&=~dest;
Position->P2&=~dest;
}
if (move.MoveType&PROMO)
{
Position->PM^=part|dest;
Position->P0^=part;
Position->P0|=(TBB)(move.Prom&1)<<(move.To);
Position->P1|=(TBB)(((move.Prom)>>1)&1)<<(move.To);
Position->P2|=(TBB)((move.Prom)>>2)<<(move.To);
Position->EnPassant=8; /* clear enpassant */
}
else /* capture or push */
{
Position->PM^=part|dest;
Position->P0^=part|dest;
Position->EnPassant=8; /* clear enpassant */
if (move.To==move.From+16 && EnPassantM[move.To&0x07]&Pawns&(Position->PM^(Occupation)))
Position->EnPassant=move.To&0x07; /* save enpassant column */
}
if (move.MoveType&CAPTURE)
{
if (move.To==63) ResetCastleSO; /* captured the opponent king side rook */
else if (move.To==56) ResetCastleLO; /* captured the opponent quuen side rook */
}
}
ChangeSide;
break;
case KNIGHT:
case BISHOP:
case ROOK:
case QUEEN:
if (move.MoveType&CAPTURE)
{
Position->P0&=~dest;
Position->P1&=~dest;
Position->P2&=~dest;
}
Position->PM^=part|dest;
Position->P0^=(move.MoveType&1) ? part|dest : 0;
Position->P1^=(move.MoveType&2) ? part|dest : 0;
Position->P2^=(move.MoveType&4) ? part|dest : 0;
Position->EnPassant=8;
if ((move.MoveType&0x7)==ROOK) /* update the castle rights */
{
if (move.From==7) ResetCastleSM;
else if (move.From==0) ResetCastleLM;
}
if (move.MoveType&CAPTURE) /* update the castle rights */
{
if (move.To==63) ResetCastleSO;
else if (move.To==56) ResetCastleLO;
}
ChangeSide;
break;
case KING:
if (move.MoveType&CAPTURE)
{
Position->P0&=~dest;
Position->P1&=~dest;
Position->P2&=~dest;
}
Position->PM^=part|dest;
Position->P1^=part|dest;
Position->P2^=part|dest;
ResetCastleSM; /* update the castle rights */
ResetCastleLM;
Position->EnPassant=8;
if (move.MoveType&CAPTURE)
{
if (CastleSO && move.To==63) ResetCastleSO;
else if (CastleLO && move.To==56) ResetCastleLO;
}
else if (move.MoveType&CASTLE)
{
if (move.To==6) { Position->PM^=0x00000000000000A0ULL; Position->P2^=0x00000000000000A0ULL; } /* short castling */
else { Position->P2^=0x0000000000000009ULL; Position->PM^=0x0000000000000009ULL; } /* long castling */
}
ChangeSide;
default: break;
}
}
/*
Load a position starting from a fen and a list of moves.
This function doesn't check the correctness of the fen and the moves sent.
*/
static void LoadPosition(const char *fen, char *moves)
{
/* Clear the board */
Position=Game;
Position->P0 = Position->P1 = Position->P2 = Position->PM = 0;
Position->EnPassant=8;
Position->STM=WHITE;
Position->CastleFlags=0;
/* translate the fen to the relative position */
uint8_t pieceside=WHITE;
uint8_t piece=PAWN;
uint8_t sidetomove=WHITE;
uint64_t square=0;
const char *cursor;
for (cursor=fen;*cursor!=' ';cursor++)
{
if (*cursor>='1' && *cursor<='8') square += *cursor - '0';
else if (*cursor=='/') continue;
else
{
uint64_t pos = OppSq(square);
if (*cursor=='p') { piece = PAWN; pieceside = BLACK; }
else if (*cursor=='n') { piece = KNIGHT; pieceside = BLACK; }
else if (*cursor=='b') { piece = BISHOP; pieceside = BLACK; }
else if (*cursor=='r') { piece = ROOK; pieceside = BLACK; }
else if (*cursor=='q') { piece = QUEEN; pieceside = BLACK; }
else if (*cursor=='k') { piece = KING; pieceside = BLACK; }
else if (*cursor=='P') { piece = PAWN; pieceside = WHITE; }
else if (*cursor=='N') { piece = KNIGHT; pieceside = WHITE; }
else if (*cursor=='B') { piece = BISHOP; pieceside = WHITE; }
else if (*cursor=='R') { piece = ROOK; pieceside = WHITE; }
else if (*cursor=='Q') { piece = QUEEN; pieceside = WHITE; }
else if (*cursor=='K') { piece = KING; pieceside = WHITE; }
Position->P0|=((uint64_t)piece&1)<<pos;
Position->P1|=((uint64_t)(piece>>1)&1)<<pos;
Position->P2|=((uint64_t)piece>>2)<<pos;
if (pieceside==WHITE) { Position->PM |= 1ULL<<pos; piece|=BLACK; }
square++;
}
}
cursor++; /* read the side to move */
if (*cursor=='w') sidetomove=WHITE;
else if (*cursor=='b') sidetomove=BLACK;
cursor+=2;
if (*cursor!='-') /* read the castle rights */
{
for (;*cursor!=' ';cursor++)
{
if (*cursor=='K') Position->CastleFlags|=0x02;
else if (*cursor=='Q') Position->CastleFlags|=0x01;
else if (*cursor=='k') Position->CastleFlags|=0x20;
else if (*cursor=='q') Position->CastleFlags|=0x10;
}
cursor++;
}
else cursor+=2;
if (*cursor!='-') /* read the enpassant column */
{
Position->EnPassant= *cursor - 'a';
//cursor++;
}
if (sidetomove==BLACK) ChangeSide;
}
/* Check the correctness of the move generator with the Perft function */
static int64_t Perft(int depth)
{
TMove quiets[256];
TMoveEval capture[64];
TMove move;
move.Move=0;
int64_t tot = 0;
for (TMoveEval *pcapture=GenerateCapture(capture);pcapture>capture;pcapture--)
{
move = (pcapture-1)->Move;
if (Illegal(move)) continue;
if (depth>1)
{
Make(move);
tot+=Perft(depth-1);
Position--;
}
else tot++;
}
for (TMove *pquiets = GenerateQuiets(quiets);pquiets>quiets;pquiets--)
{
move = *(pquiets-1);
if (Illegal(move)) continue;
if (depth>1)
{
Make(move);
tot+=Perft(depth-1);
Position--;
}
else tot++;
}
return tot;
}
#if defined(_WIN32)
// Windows compilable replacement for POSIX clock_gettime
#include <windows.h>
#define BILLION (1E9)
#define CLOCK_MONOTONIC 0
static BOOL g_first_time = 1;
static LARGE_INTEGER g_counts_per_sec;
int clock_gettime(int dummy, struct timespec* ct)
{
LARGE_INTEGER count;
if (g_first_time)
{
g_first_time = 0;
if (0 == QueryPerformanceFrequency(&g_counts_per_sec))
{
g_counts_per_sec.QuadPart = 0;
}
}
if ((NULL == ct) || (g_counts_per_sec.QuadPart <= 0) ||
(0 == QueryPerformanceCounter(&count)))
{
return -1;
}
ct->tv_sec = count.QuadPart / g_counts_per_sec.QuadPart;
ct->tv_nsec = ((count.QuadPart % g_counts_per_sec.QuadPart) * BILLION) / g_counts_per_sec.QuadPart;
return 0;
}
#endif
/* Run the Perft with this 6 test positions */
static void TestPerft(void)
{
struct{
char fen[200];
int depth;
int64_t count;
}Test[] = { {"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1",6,119060324},
{"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1",5,193690690},
{"8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1", 7,178633661},
{"r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1",6,706045033},
{"rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6",3,53392},
{"r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10",5,164075551}};
int64_t totalCount = 0;
int64_t totalDuration = 0;
for (unsigned int i=0;i<(sizeof Test) / (sizeof (Test[0])); i++)
{
LoadPosition(Test[i].fen,"");
struct timespec begin,end;
clock_gettime(CLOCK_MONOTONIC,&begin);
printf("%s%"PRId64"%s%"PRId64"%s","Expected: ",Test[i].count," Computed: ",Perft(Test[i].depth),"\r\n");
clock_gettime(CLOCK_MONOTONIC,&end);
long t_diff = (end.tv_sec - begin.tv_sec) * 1000 + (end.tv_nsec - begin.tv_nsec) / (1000 * 1000);
long knps = Test[i].count / t_diff;
printf("%lu ms, %luK NPS\r\n", t_diff, knps);
totalCount += Test[i].count;
totalDuration += t_diff;
}
printf("\r\n");
printf("Total: %lu Nodes, %lu ms, %luK NPS\r\n", totalCount, totalDuration, totalCount / totalDuration);
exit(0);
}
int main (int argc, char *argv[])
{
printf("QBB Perft in C\r\n");
TestPerft();
return 0;
}
-
R. Tomasi
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: Why C++ instead of C#?
I also removed the redundant LSBs in the C# version.
Before the changes (as of current commit in the repo):
After the changes:
It seem's to pay of a little, but it's very close to the variance on my machine, too.
Source code:
Before the changes (as of current commit in the repo):
Code: Select all
QBB Perft in C#
https://github.com/lithander/QBB-Perft/tree/v1.4
OK! 3608ms, 32997K NPS
OK! 4967ms, 38994K NPS
OK! 5416ms, 32977K NPS
OK! 18950ms, 37257K NPS
OK! 1ms, 32249K NPS
OK! 4141ms, 39617K NPS
Total: 1361558651 Nodes, 37085ms, 36713K NPS
Code: Select all
QBB Perft in C#
https://github.com/lithander/QBB-Perft/tree/v1.4
OK! 3616ms, 32924K NPS
OK! 5204ms, 37214K NPS
OK! 5818ms, 30701K NPS
OK! 17808ms, 39646K NPS
OK! 1ms, 35370K NPS
OK! 4125ms, 39768K NPS
Total: 1361558651 Nodes, 36574ms, 37226K NPS
Source code:
Code: Select all
/*
This perft implementation is based on QBBEngine by Fabio Gobbato and ported to C# by Thomas Jahn
The purpose is to compare the speed differences of C# and C in chess-programming workload.
*/
using System;
using System.Buffers.Binary;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics.X86;
using System.Text;
using System.Threading;
namespace QBB
{
class QbbPerft
{
const int MAX_PLY = 32;
const int WHITE = 0;
const int BLACK = 8;
/* define the move type, for example
KING|CASTLE is a castle move
PAWN|CAPTURE|EP is an enpassant move
PAWN|PROMO|CAPTURE is a promotion with a capture */
/* define the piece type: empty, pawn, knight, bishop, rook, queen, king */
[Flags]
enum TPieceType : byte { EMPTY, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING, PIECE_MASK = 0x07, CASTLE = 0x40, PROMO = 0x20, EP = 0x10, CAPTURE = 0x08 }
/* move structure */
struct TMove
{
public TPieceType MoveType;
public byte From;
public byte To;
public TPieceType Promotion;
};
static TMove[][] MovesLists;
static QbbPerft()
{
MovesLists = new TMove[MAX_PLY][];
for (int i = 0; i < MAX_PLY; i++)
MovesLists[i] = new TMove[225];
}
/*
Board structure definition
PM,P0,P1,P2 are the 4 bitboards that contain the whole board
PM is the bitboard with the side to move pieces
P0,P1 and P2: with these bitboards you can obtain every type of pieces and every pieces combinations.
*/
struct TBoard
{
public ulong PM;
public ulong P0;
public ulong P1;
public ulong P2;
public byte CastleFlags; /* ..sl..SL short long opponent SHORT LONG side to move */
public byte EnPassant; /* enpassant column, =8 if not set */
public byte STM; /* side to move */
}
static TBoard[] Game = new TBoard[MAX_PLY];
static int iPosition;
private static TBoard Position;
/* array of bitboards that contains all the knight destination for every square */
static readonly ulong[] KnightDest = {
0x0000000000020400UL,0x0000000000050800UL,0x00000000000a1100UL,0x0000000000142200UL,
0x0000000000284400UL,0x0000000000508800UL,0x0000000000a01000UL,0x0000000000402000UL,
0x0000000002040004UL,0x0000000005080008UL,0x000000000a110011UL,0x0000000014220022UL,
0x0000000028440044UL,0x0000000050880088UL,0x00000000a0100010UL,0x0000000040200020UL,
0x0000000204000402UL,0x0000000508000805UL,0x0000000a1100110aUL,0x0000001422002214UL,
0x0000002844004428UL,0x0000005088008850UL,0x000000a0100010a0UL,0x0000004020002040UL,
0x0000020400040200UL,0x0000050800080500UL,0x00000a1100110a00UL,0x0000142200221400UL,
0x0000284400442800UL,0x0000508800885000UL,0x0000a0100010a000UL,0x0000402000204000UL,
0x0002040004020000UL,0x0005080008050000UL,0x000a1100110a0000UL,0x0014220022140000UL,
0x0028440044280000UL,0x0050880088500000UL,0x00a0100010a00000UL,0x0040200020400000UL,
0x0204000402000000UL,0x0508000805000000UL,0x0a1100110a000000UL,0x1422002214000000UL,
0x2844004428000000UL,0x5088008850000000UL,0xa0100010a0000000UL,0x4020002040000000UL,
0x0400040200000000UL,0x0800080500000000UL,0x1100110a00000000UL,0x2200221400000000UL,
0x4400442800000000UL,0x8800885000000000UL,0x100010a000000000UL,0x2000204000000000UL,
0x0004020000000000UL,0x0008050000000000UL,0x00110a0000000000UL,0x0022140000000000UL,
0x0044280000000000UL,0x0088500000000000UL,0x0010a00000000000UL,0x0020400000000000UL,
};
/* The same for the king */
static readonly ulong[] KingDest = {
0x0000000000000302UL,0x0000000000000705UL,0x0000000000000e0aUL,0x0000000000001c14UL,
0x0000000000003828UL,0x0000000000007050UL,0x000000000000e0a0UL,0x000000000000c040UL,
0x0000000000030203UL,0x0000000000070507UL,0x00000000000e0a0eUL,0x00000000001c141cUL,
0x0000000000382838UL,0x0000000000705070UL,0x0000000000e0a0e0UL,0x0000000000c040c0UL,
0x0000000003020300UL,0x0000000007050700UL,0x000000000e0a0e00UL,0x000000001c141c00UL,
0x0000000038283800UL,0x0000000070507000UL,0x00000000e0a0e000UL,0x00000000c040c000UL,
0x0000000302030000UL,0x0000000705070000UL,0x0000000e0a0e0000UL,0x0000001c141c0000UL,
0x0000003828380000UL,0x0000007050700000UL,0x000000e0a0e00000UL,0x000000c040c00000UL,
0x0000030203000000UL,0x0000070507000000UL,0x00000e0a0e000000UL,0x00001c141c000000UL,
0x0000382838000000UL,0x0000705070000000UL,0x0000e0a0e0000000UL,0x0000c040c0000000UL,
0x0003020300000000UL,0x0007050700000000UL,0x000e0a0e00000000UL,0x001c141c00000000UL,
0x0038283800000000UL,0x0070507000000000UL,0x00e0a0e000000000UL,0x00c040c000000000UL,
0x0302030000000000UL,0x0705070000000000UL,0x0e0a0e0000000000UL,0x1c141c0000000000UL,
0x3828380000000000UL,0x7050700000000000UL,0xe0a0e00000000000UL,0xc040c00000000000UL,
0x0203000000000000UL,0x0507000000000000UL,0x0a0e000000000000UL,0x141c000000000000UL,
0x2838000000000000UL,0x5070000000000000UL,0xa0e0000000000000UL,0x40c0000000000000UL
};
/* masks for finding the pawns that can capture with an enpassant (in move generation) */
static readonly ulong[] EnPassant = {
0x0000000200000000UL,0x0000000500000000UL,0x0000000A00000000UL,0x0000001400000000UL,
0x0000002800000000UL,0x0000005000000000UL,0x000000A000000000UL,0x0000004000000000UL
};
/* masks for finding the pawns that can capture with an enpassant (in make move) */
static readonly ulong[] EnPassantM = {
0x0000000002000000UL,0x0000000005000000UL,0x000000000A000000UL,0x0000000014000000UL,
0x0000000028000000UL,0x0000000050000000UL,0x00000000A0000000UL,0x0000000040000000UL
};
/*
reverse a bitboard:
A bitboard is an array of byte: Byte0,Byte1,Byte2,Byte3,Byte4,Byte5,Byte6,Byte7
after this function the bitboard will be: Byte7,Byte6,Byte5,Byte4,Byte3,Byte2,Byte1,Byte0
The board is saved always with the side to move in the low significant bits of the bitboard, so this function
is used to change the side to move
*/
//#define RevBB(bb) (__builtin_bswap64(bb))
public static ulong _RevBB(ulong bb)
{
//Swap adjacent 32-bit blocks
bb = (bb >> 32) | (bb << 32);
//Swap adjacent 16-bit blocks
bb = ((bb & 0xFFFF0000FFFF0000U) >> 16) | ((bb & 0x0000FFFF0000FFFFU) << 16);
//Swap adjacent 8-bit blocks
bb = ((bb & 0xFF00FF00FF00FF00U) >> 8) | ((bb & 0x00FF00FF00FF00FFU) << 8);
return bb;
}
public static ulong RevBB(ulong bb) => BinaryPrimitives.ReverseEndianness(bb);
/* return the index of the most significant bit of the bitboard, bb must always be !=0 */
//#define MSB(bb) (0x3F ^ __builtin_clzll(bb))
public static ulong MSB(ulong bb) => 63 ^ Lzcnt.X64.LeadingZeroCount(bb);
/* return the index of the least significant bit of the bitboard, bb must always be !=0 */
//#define LSB(bb) (__builtin_ctzll(bb))
public static ulong LSB(ulong bb) => Bmi1.X64.TrailingZeroCount(bb);
/* extract the least significant bit of the bitboard */
//#define ExtractLSB(bb) ((bb)&(-(bb)))
public static ulong _ExtractLSB(ulong bb) => bb & (0 - bb);
public static ulong ExtractLSB(ulong bb) => Bmi1.X64.ExtractLowestSetBit(bb);
/* reset the least significant bit of bb */
//#define ClearLSB(bb) ((bb)&((bb)-1))
public static ulong _ClearLSB(ulong bb) => bb & (bb - 1);
public static ulong ClearLSB(ulong bb) => Bmi1.X64.ResetLowestSetBit(bb);
/* return the number of bits sets of a bitboard */
//#define PopCount(bb) (__builtin_popcountll(bb))
public static ulong PopCount(ulong bb) => Popcnt.X64.PopCount(bb);
/* Macro to check and reset the castle rights:
CastleSM: short castling side to move
CastleLM: long castling side to move
CastleSO: short castling opponent
CastleLO: long castling opponent
*/
static bool CanCastleSM() => (Position.CastleFlags & 0x02) != 0;
static bool CanCastleLM() => (Position.CastleFlags & 0x01) != 0;
static void ResetCastleSM() => Position.CastleFlags &= 0xFD;
static void ResetCastleLM() => Position.CastleFlags &= 0xFE;
static void ResetCastleSO() => Position.CastleFlags &= 0xDF;
static void ResetCastleLO() => Position.CastleFlags &= 0xEF;
/* these Macros are used to calculate the bitboard of a particular kind of piece
P2 P1 P0
0 0 0 empty
0 0 1 pawn
0 1 0 knight
0 1 1 bishop
1 0 0 rook
1 0 1 queen
1 1 0 king
*/
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Occupation() => Position.P0 | Position.P1 | Position.P2; /* board occupation */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Pawns() => Position.P0 & ~Position.P1 & ~Position.P2; /* all the pawns on the board */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Knights() => ~Position.P0 & Position.P1 & ~Position.P2;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Bishops() => Position.P0 & Position.P1;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Rooks() => ~Position.P0 & ~Position.P1 & Position.P2;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Queens() => Position.P0 & Position.P2;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong QueenOrRooks() => ~Position.P1 & Position.P2;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong QueenOrBishops() => Position.P0 & (Position.P2 | Position.P1);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Kings() => Position.P1 & Position.P2; /* a bitboard with the 2 kings */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong SideToMove() => Position.PM;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static byte EnPass() => Position.EnPassant;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Opposing() => Position.PM ^ (Position.P0 | Position.P1 | Position.P2);
/* get the piece type giving the square */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Piece(int sq) => ((Position.P2 >> sq) & 1) << 2 |
((Position.P1 >> sq) & 1) << 1 |
((Position.P0 >> sq) & 1);
/* calculate the square related to the opponent */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int OppSq(int sp) => sp ^ 56;
/* Absolute Square, we need this macro to return the move in long algebric notation */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int AbsSq(int sq, int col) => col == WHITE ? sq : OppSq(sq);
/* get the corresponding string to the given move */
static string MoveToStr(TMove move, byte tomove)
{
Span<char> promo = stackalloc[] { ' ', ' ', 'n', 'b', 'r', 'q' };
StringBuilder result = new StringBuilder(6);
result.Append((char)('a' + AbsSq(move.From, tomove) % 8));
result.Append((char)('1' + AbsSq(move.From, tomove) / 8));
result.Append((char)('a' + AbsSq(move.To, tomove) % 8));
result.Append((char)('1' + AbsSq(move.To, tomove) / 8));
result.Append(promo[(byte)move.Promotion]);
return result.ToString();
}
static void ChangeSide()
{
Position.PM ^= Occupation(); /* update the side to move pieces */
Position.PM = RevBB(Position.PM);
Position.P0 = RevBB(Position.P0);
Position.P1 = RevBB(Position.P1);
Position.P2 = RevBB(Position.P2);/* reverse the board */
Position.CastleFlags = (byte)((Position.CastleFlags >> 4) | (Position.CastleFlags << 4));/* roll the castle rights */
Position.STM ^= BLACK; /* change the side to move */
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static ulong GenRook(int sq, ulong occupation)
{
ulong piece = 1UL << sq;
occupation ^= piece; /* remove the selected piece from the occupation */
ulong piecesup = (0x0101010101010101UL << sq) & (occupation | 0xFF00000000000000UL); /* find the pieces up */
ulong piecesdo = (0x8080808080808080UL >> (63 - sq)) & (occupation | 0x00000000000000FFUL); /* find the pieces down */
ulong piecesri = (0x00000000000000FFUL << sq) & (occupation | 0x8080808080808080UL); /* find pieces on the right */
ulong piecesle = (0xFF00000000000000UL >> (63 - sq)) & (occupation | 0x0101010101010101UL); /* find pieces on the left */
return (((0x8080808080808080UL >> (63 - (int)LSB(piecesup))) & (0x0101010101010101UL << (int)MSB(piecesdo))) |
((0xFF00000000000000UL >> (63 - (int)LSB(piecesri))) & (0x00000000000000FFUL << (int)MSB(piecesle)))) ^ piece;
/* From every direction find the first piece and from that piece put a mask in the opposite direction.
Put togheter all the 4 masks and remove the moving piece */
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static ulong GenBishop(int sq, ulong occupation)
{
/* it's the same as the rook */
ulong piece = 1UL << sq;
occupation ^= piece;
ulong piecesup = (0x8040201008040201UL << sq) & (occupation | 0xFF80808080808080UL);
ulong piecesdo = (0x8040201008040201UL >> (63 - sq)) & (occupation | 0x01010101010101FFUL);
ulong piecesle = (0x8102040810204081UL << sq) & (occupation | 0xFF01010101010101UL);
ulong piecesri = (0x8102040810204081UL >> (63 - sq)) & (occupation | 0x80808080808080FFUL);
return (((0x8040201008040201UL >> (63 - (int)LSB(piecesup))) & (0x8040201008040201UL << (int)MSB(piecesdo))) |
((0x8102040810204081UL >> (63 - (int)LSB(piecesle))) & (0x8102040810204081UL << (int)MSB(piecesri)))) ^ piece;
}
/* return the bitboard with pieces of the same type */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong BBPieces(TPieceType piece)
{
switch (piece) // find the bb with the pieces of the same type
{
case TPieceType.PAWN: return Pawns();
case TPieceType.KNIGHT: return Knights();
case TPieceType.BISHOP: return Bishops();
case TPieceType.ROOK: return Rooks();
case TPieceType.QUEEN: return Queens();
case TPieceType.KING: return Kings();
default: return 0;
}
}
/* return the bitboard with the destinations of a piece in a square (exept for pawns) */
static ulong BBDestinations(TPieceType piece, int sq, ulong occupation)
{
switch (piece) // generate the destination squares of the piece
{
case TPieceType.KNIGHT: return KnightDest[sq];
case TPieceType.BISHOP: return GenBishop(sq, occupation);
case TPieceType.ROOK: return GenRook(sq, occupation);
case TPieceType.QUEEN: return GenRook(sq, occupation) | GenBishop(sq, occupation);
case TPieceType.KING: return KingDest[sq];
default: return 0;
}
}
/* try the move and see if the king is in check. If so return the attacking pieces, if not return 0 */
private static bool Illegal(ref TMove move)
{
ulong From = 1UL << move.From;
ulong To = 1UL << move.To;
ulong king;
int kingsq;
ulong newoccupation = (Occupation() ^ From) | To;
ulong newopposing = Opposing() & ~To;
if ((move.MoveType & TPieceType.PIECE_MASK) == TPieceType.KING)
{
king = To;
kingsq = move.To;
}
else
{
king = Kings() & SideToMove();
kingsq = (int)LSB(king);
if ((move.MoveType & TPieceType.EP) != 0)
{
newopposing ^= To >> 8;
newoccupation ^= To >> 8;
}
}
bool kingIsSafe = //as soon as there's one attack you can stop evaluating the remaining peieces (early out)
(KnightDest[kingsq] & Knights() & newopposing) == 0 &&
((((king << 9) & 0xFEFEFEFEFEFEFEFEUL) | ((king << 7) & 0x7F7F7F7F7F7F7F7FUL)) & Pawns() & newopposing) == 0 &&
(GenBishop(kingsq, newoccupation) & QueenOrBishops() & newopposing) == 0 &&
(GenRook(kingsq, newoccupation) & QueenOrRooks() & newopposing) == 0 &&
((KingDest[kingsq] & Kings()) & newopposing) == 0;
return !kingIsSafe;
}
private static void GenerateQuiets(in TMove[] moves, ref int index)
{
ulong occupation = Occupation();
ulong opposing = Opposing();
// generate moves from king to knight
for (TPieceType piece = TPieceType.KING; piece >= TPieceType.KNIGHT; piece--)
{
// generate moves for every piece of the same type of the side to move
for (ulong pieces = BBPieces(piece) & SideToMove(); pieces != 0; pieces = ClearLSB(pieces))
{
int square = (int)LSB(pieces);
// for every destinations on a free square generate a move
for (ulong destinations = ~occupation & BBDestinations(piece, square, occupation); destinations != 0; destinations = ClearLSB(destinations))
moves[index++] = new TMove
{
MoveType = piece,
From = (byte)square,
To = (byte)LSB(destinations)
};
}
}
/* one pawns push */
ulong push1 = (((Pawns() & SideToMove()) << 8) & ~occupation) & 0x00FFFFFFFFFFFFFFUL;
for (ulong pieces = push1; pieces != 0; pieces = ClearLSB(pieces))
{
ulong lsb = LSB(pieces);
moves[index++] = new TMove
{
MoveType = TPieceType.PAWN,
From = (byte)(lsb - 8),
To = (byte)lsb //TODO: avoid calling LSB twice?
};
}
/* double pawns pushes */
ulong push2 = (push1 << 8) & ~occupation & 0x00000000FF000000UL;
for (; push2 != 0; push2 = ClearLSB(push2))
{
ulong lsb = LSB(push2);
moves[index++] = new TMove
{
MoveType = TPieceType.PAWN,
From = (byte)(lsb - 16),
To = (byte)lsb //TODO: avoid calling LSB twice?
};
}
/* check if long castling is possible */
if (CanCastleLM() && (occupation & 0x0EUL) == 0)
{
ulong roo = ExtractLSB(0x1010101010101000UL & occupation); /* column e */
roo |= ExtractLSB(0x0808080808080800UL & occupation); /*column d */
roo |= ExtractLSB(0x0404040404040400UL & occupation); /*column c */
roo |= ExtractLSB(0x00000000000000E0UL & occupation); /* row 1 */
ulong bis = ExtractLSB(0x0000000102040800UL & occupation); /*antidiag from e1/e8 */
bis |= ExtractLSB(0x0000000001020400UL & occupation); /*antidiag from d1/d8 */
bis |= ExtractLSB(0x0000000000010200UL & occupation); /*antidiag from c1/c8 */
bis |= ExtractLSB(0x0000000080402000UL & occupation); /*diag from e1/e8 */
bis |= ExtractLSB(0x0000008040201000UL & occupation); /*diag from d1/d8 */
bis |= ExtractLSB(0x0000804020100800UL & occupation); /*diag from c1/c8 */
if ((((roo & QueenOrRooks()) | (bis & QueenOrBishops()) | (0x00000000003E7700UL & Knights()) |
(0x0000000000003E00UL & Pawns()) | (Kings() & 0x0000000000000600UL)) & opposing) == 0)
/* check if c1/c8 d1/d8 e1/e8 are not attacked */
moves[index++] = new TMove
{
MoveType = TPieceType.KING | TPieceType.CASTLE,
From = 4,
To = 2,
};
}
/* check if short castling is possible */
if (CanCastleSM() && (occupation & 0x60UL) == 0)
{
ulong roo = ExtractLSB(0x1010101010101000UL & occupation); /* column e */
roo |= ExtractLSB(0x2020202020202000UL & occupation); /* column f */
roo |= ExtractLSB(0x4040404040404000UL & occupation); /* column g */
roo |= 1UL << (byte)MSB(0x000000000000000FUL & (occupation | 0x1UL));/* row 1 */
ulong bis = ExtractLSB(0x0000000102040800UL & occupation); /* antidiag from e1/e8 */
bis |= ExtractLSB(0x0000010204081000UL & occupation); /*antidiag from f1/f8 */
bis |= ExtractLSB(0x0001020408102000UL & occupation); /*antidiag from g1/g8 */
bis |= ExtractLSB(0x0000000080402000UL & occupation); /*diag from e1/e8 */
bis |= ExtractLSB(0x0000000000804000UL & occupation); /*diag from f1/f8 */
bis |= 0x0000000000008000UL; /*diag from g1/g8 */
if ((((roo & QueenOrRooks()) | (bis & QueenOrBishops()) | (0x0000000000F8DC00UL & Knights()) |
(0x000000000000F800UL & Pawns()) | (Kings() & 0x0000000000004000UL)) & opposing) == 0)
/* check if e1/e8 f1/f8 g1/g8 are not attacked */
moves[index++] = new TMove
{
MoveType = TPieceType.KING | TPieceType.CASTLE,
From = 4,
To = 6,
};
}
}
private static void GenerateCapture(in TMove[] moves, ref int index)
{
ulong occupation = Occupation();
ulong opposing = Opposing();
// generate moves from king to knight
for (TPieceType piece = TPieceType.KING; piece >= TPieceType.KNIGHT; piece--)
{
// generate moves for every piece of the same type of the side to move
for (ulong pieces = BBPieces(piece) & SideToMove(); pieces != 0; pieces = ClearLSB(pieces))
{
int square = (int)LSB(pieces);
// for every destinations on an opponent pieces generate a move
for (ulong destinations = opposing & BBDestinations(piece, square, occupation);
destinations != 0;
destinations = ClearLSB(destinations))
moves[index++] = new TMove
{
MoveType = piece | TPieceType.CAPTURE,
From = (byte)square,
To = (byte)LSB(destinations),
//Eval = (Piece(LSB(destinations)) << 4) | (KING - piece);
};
}
}
ulong pawns = Pawns() & SideToMove();
/* Generate pawns right captures */
for (ulong rpc = (pawns << 9) & 0x00FEFEFEFEFEFEFEUL & opposing; rpc != 0; rpc = ClearLSB(rpc))
{
ulong lsb = LSB(rpc);
moves[index++] = new TMove()
{
MoveType = TPieceType.PAWN | TPieceType.CAPTURE,
From = (byte)(lsb - 9),
To = (byte)lsb,
//Eval = (Piece(LSB(captureri)) << 4) | (KING - PAWN);
};
}
/* Generate pawns left captures */
for (ulong lpc = (pawns << 7) & 0x007F7F7F7F7F7F7FUL & opposing; lpc != 0; lpc = ClearLSB(lpc))
{
ulong lsb = LSB(lpc);
moves[index++] = new TMove()
{
MoveType = TPieceType.PAWN | TPieceType.CAPTURE,
From = (byte)(lsb - 7),
To = (byte)lsb,
//Eval = (Piece(LSB(capturele))<<4)|(KING-PAWN);
};
}
/* Generate pawns promotions */
if ((pawns & 0x00FF000000000000UL) != 0)
{
/* promotions with left capture */
for (ulong promo = (pawns << 9) & 0xFE00000000000000UL & opposing; promo != 0; promo = ClearLSB(promo))
{
for (TPieceType piece = TPieceType.QUEEN; piece >= TPieceType.KNIGHT; piece--)
{
ulong lsb = LSB(promo);
moves[index++] = new TMove()
{
MoveType = TPieceType.PAWN | TPieceType.PROMO | TPieceType.CAPTURE,
From = (byte)(lsb - 9),
To = (byte)lsb,
Promotion = piece
//Eval = (piece<<4)|(KING-PAWN);
};
}
}
/* promotions with right capture */
for (ulong promo = (pawns << 7) & 0x7F00000000000000UL & opposing; promo != 0; promo = ClearLSB(promo))
{
for (TPieceType piece = TPieceType.QUEEN; piece >= TPieceType.KNIGHT; piece--)
{
ulong lsb = LSB(promo);
moves[index++] = new TMove()
{
MoveType = TPieceType.PAWN | TPieceType.PROMO | TPieceType.CAPTURE,
From = (byte)(lsb - 7),
To = (byte)lsb,
Promotion = piece
//Eval = (piece<<4)|(KING-PAWN);
};
}
}
/* no capture promotions */
for (ulong promo = ((pawns << 8) & ~occupation) & 0xFF00000000000000UL;
promo != 0;
promo = ClearLSB(promo))
{
for (TPieceType piece = TPieceType.QUEEN; piece >= TPieceType.KNIGHT; piece--)
{
ulong lsb = LSB(promo);
moves[index++] = new TMove()
{
MoveType = TPieceType.PAWN | TPieceType.PROMO,
From = (byte)(lsb - 8),
To = (byte)lsb,
Promotion = piece
//Eval = (piece<<4)|(KING-PAWN);
};
}
}
}
if (EnPass() != 8)
{
for (ulong enpassant = pawns & EnPassant[EnPass()]; enpassant != 0; enpassant = ClearLSB((enpassant)))
moves[index++] = new TMove()
{
MoveType = TPieceType.PAWN | TPieceType.EP | TPieceType.PROMO,
From = (byte)LSB(enpassant),
To = (byte)(40 + EnPass())
//Eval = (PAWN<<4)|(KING-PAWN);
};
}
}
private static void Make(ref TMove move)
{
Game[iPosition++] = Position;
ulong part = 1UL << move.From;
ulong dest = 1UL << move.To;
switch (move.MoveType & TPieceType.PIECE_MASK)
{
case TPieceType.PAWN:
if ((move.MoveType & TPieceType.EP) != 0)
{ /* EnPassant */
Position.PM ^= part | dest;
Position.P0 ^= part | dest;
Position.P0 ^= dest >> 8; //delete the captured pawn
Position.EnPassant = 8;
}
else
{
//TODO: move.IsCapture
if ((move.MoveType & TPieceType.CAPTURE) != 0)
{
/* Delete the captured piece */
Position.P0 &= ~dest;
Position.P1 &= ~dest;
Position.P2 &= ~dest;
}
if ((move.MoveType & TPieceType.PROMO) != 0)
{
Position.PM ^= part | dest;
Position.P0 ^= part;
Position.P0 |= (ulong)((int)move.Promotion & 1) << move.To;
Position.P1 |= (ulong)(((int)move.Promotion >> 1) & 1) << move.To;
Position.P2 |= (ulong)((int)move.Promotion >> 2) << move.To;
Position.EnPassant = 8; /* clear enpassant */
}
else /* capture or push */
{
Position.PM ^= part | dest;
Position.P0 ^= part | dest;
Position.EnPassant = 8; /* clear enpassant */
if (move.To == move.From + 16 && (EnPassantM[move.To & 0x07] & Pawns() & Opposing()) != 0)
Position.EnPassant = (byte)(move.To & 0x07); /* save enpassant column */
}
if ((move.MoveType & TPieceType.CAPTURE) != 0)
{
if (move.To == 63) ResetCastleSO(); /* captured the opponent king side rook */
else if (move.To == 56) ResetCastleLO(); /* captured the opponent quuen side rook */
}
}
ChangeSide();
break;
case TPieceType.KNIGHT:
case TPieceType.BISHOP:
case TPieceType.ROOK:
case TPieceType.QUEEN:
if ((move.MoveType & TPieceType.CAPTURE) != 0)
{
/* Delete the captured piece */
Position.P0 &= ~dest;
Position.P1 &= ~dest;
Position.P2 &= ~dest;
}
Position.PM ^= part | dest;
//TODO: handle N, B, R & Q seperately?
Position.P0 ^= (((int)move.MoveType & 1) != 0) ? part | dest : 0;
Position.P1 ^= (((int)move.MoveType & 2) != 0) ? part | dest : 0;
Position.P2 ^= (((int)move.MoveType & 4) != 0) ? part | dest : 0;
Position.EnPassant = 8;
if ((move.MoveType & TPieceType.PIECE_MASK) == TPieceType.ROOK)
{
if (move.From == 7)
ResetCastleSM(); //king side rook moved
else if (move.From == 0)
ResetCastleLM(); // queen side rook moved
}
if ((move.MoveType & TPieceType.CAPTURE) != 0)
{
if (move.To == 63) ResetCastleSO(); /* captured the opponent king side rook */
else if (move.To == 56) ResetCastleLO(); /* captured the opponent quuen side rook */
}
ChangeSide();
break;
case TPieceType.KING:
if ((move.MoveType & TPieceType.CAPTURE) != 0)
{
/* Delete the captured piece */
Position.P0 &= ~dest;
Position.P1 &= ~dest;
Position.P2 &= ~dest;
}
Position.PM ^= part | dest;
Position.P1 ^= part | dest;
Position.P2 ^= part | dest;
ResetCastleSM(); /* update the castle rights */
ResetCastleLM();
Position.EnPassant = 8;
if ((move.MoveType & TPieceType.CAPTURE) != 0)
{
if (move.To == 63)
ResetCastleSO(); /* captured the opponent king side rook */
else if (move.To == 56)
ResetCastleLO(); /* captured the opponent quuen side rook */
}
else if ((move.MoveType & TPieceType.CASTLE) != 0)
{
if (move.To == 6)
{
Position.PM ^= 0x00000000000000A0UL;
Position.P2 ^= 0x00000000000000A0UL;
} /* short castling */
else
{
Position.PM ^= 0x0000000000000009UL;
Position.P2 ^= 0x0000000000000009UL;
} /* long castling */
}
ChangeSide();
break;
}
}
private static void LoadPosition(string fen)
{
/* Clear the board */
ref TBoard pos = ref Position;
pos.P0 = pos.P1 = pos.P2 = pos.PM = 0;
pos.EnPassant = 8;
pos.STM = WHITE;
pos.CastleFlags = 0;
/* translate the fen to the relative position */
byte pieceside = WHITE;
ulong piece = (ulong)TPieceType.PAWN;
byte sidetomove = WHITE;
int square = 0;
int cursor;
for (cursor = 0; fen[cursor] != ' '; cursor++)
{
char cur = fen[cursor];
if (cur >= '1' && cur <= '8')
square += cur - '0';
else if (cur != '/')
{
int bit = OppSq(square);
if (cur == 'p') { piece = (ulong)TPieceType.PAWN; pieceside = BLACK; }
else if (cur == 'n') { piece = (ulong)TPieceType.KNIGHT; pieceside = BLACK; }
else if (cur == 'b') { piece = (ulong)TPieceType.BISHOP; pieceside = BLACK; }
else if (cur == 'r') { piece = (ulong)TPieceType.ROOK; pieceside = BLACK; }
else if (cur == 'q') { piece = (ulong)TPieceType.QUEEN; pieceside = BLACK; }
else if (cur == 'k') { piece = (ulong)TPieceType.KING; pieceside = BLACK; }
else if (cur == 'P') { piece = (ulong)TPieceType.PAWN; pieceside = WHITE; }
else if (cur == 'N') { piece = (ulong)TPieceType.KNIGHT; pieceside = WHITE; }
else if (cur == 'B') { piece = (ulong)TPieceType.BISHOP; pieceside = WHITE; }
else if (cur == 'R') { piece = (ulong)TPieceType.ROOK; pieceside = WHITE; }
else if (cur == 'Q') { piece = (ulong)TPieceType.QUEEN; pieceside = WHITE; }
else if (cur == 'K') { piece = (ulong)TPieceType.KING; pieceside = WHITE; }
pos.P0 |= (piece & 1) << bit; //001
pos.P1 |= ((piece >> 1) & 1) << bit; //010
pos.P2 |= (piece >> 2) << bit; //100
if (pieceside == WHITE)
{
pos.PM |= (1UL << bit);
piece |= BLACK;
}
square++;
}
}
cursor++; /* read the side to move */
if (fen[cursor] == 'w')
sidetomove = WHITE;
else if (fen[cursor] == 'b')
sidetomove = BLACK;
cursor += 2;
if (fen[cursor] != '-') /* read the castle rights */
{
for (; fen[cursor] != ' '; cursor++)
{
char cur = fen[cursor];
if (cur == 'K') pos.CastleFlags |= 0x02;
else if (cur == 'Q') pos.CastleFlags |= 0x01;
else if (cur == 'k') pos.CastleFlags |= 0x20;
else if (cur == 'q') pos.CastleFlags |= 0x10;
}
cursor++;
}
else cursor += 2;
if (fen[cursor] != '-') /* read the enpassant column */
{
pos.EnPassant = (byte)(fen[cursor] - 'a');
//cursor++;
}
if (sidetomove == BLACK)
ChangeSide();
}
private static long Perft(int depth)
{
long total = 0;
int index = 0;
var moveList = MovesLists[depth];
GenerateCapture(moveList, ref index);
GenerateQuiets(moveList, ref index);
for (int i = 0; i < index; i++)
{
if (Illegal(ref moveList[i]))
continue;
if (depth > 1)
{
Make(ref moveList[i]);
total += Perft(depth - 1);
Position = Game[--iPosition];
}
else
total++;
}
return total;
}
struct PerftResult
{
public double Duration;
public long Nodes;
public PerftResult(double t, long n)
{
Duration = t;
Nodes = n;
}
public static PerftResult operator +(PerftResult a, PerftResult b) => new(a.Duration + b.Duration, a.Nodes + b.Nodes);
}
private static PerftResult TestPerft(string fen, int depth, int expectedResult)
{
LoadPosition(fen);
//PrintPosition(Game[Position]);
long t0 = Stopwatch.GetTimestamp();
long count = Perft(depth);
long t1 = Stopwatch.GetTimestamp();
double dt = (t1 - t0) / (double)Stopwatch.Frequency;
double ms = (1000 * dt);
if (expectedResult != count)
{
Console.WriteLine($"ERROR in Perft({fen}, {depth})");
Console.WriteLine($"Computed result: {count}");
Console.WriteLine($"Expected result: {expectedResult}");
}
else
Console.WriteLine($"OK! {(int)ms}ms, {(int)(count / ms)}K NPS");
return new PerftResult(dt, count);
}
static void Main(string[] args)
{
Console.WriteLine("QBB Perft in C#");
Console.WriteLine("https://github.com/lithander/QBB-Perft/tree/v1.4");
Console.WriteLine();
PerftResult accu = TestPerft("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", 6, 119060324); //Start Position
accu += TestPerft("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", 5, 193690690);
accu += TestPerft("8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1", 7, 178633661);
accu += TestPerft("r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1", 6, 706045033);
accu += TestPerft("rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6", 3, 53392);
accu += TestPerft("r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10", 5, 164075551);
Console.WriteLine();
Console.WriteLine($"Total: {accu.Nodes} Nodes, {(int)(1000 * accu.Duration)}ms, {(int)(accu.Nodes / accu.Duration / 1000)}K NPS");
Console.WriteLine("Press any key to quit");//stop command prompt from closing automatically on windows
Console.ReadKey();
}
//**** Debug Helpers not in the original C code
private static void PrintPosition(TBoard pos)
{
PrintBB(pos.PM, "PM");
PrintBB(pos.P0, "P0");
PrintBB(pos.P1, "P1");
PrintBB(pos.P2, "P2");
Console.WriteLine("- - - -");
PrintBB(Pawns(), "Pawns");
PrintBB(Knights(), "Knights");
PrintBB(Bishops(), "Bishops");
PrintBB(Rooks(), "Roosk");
PrintBB(Queens(), "Queens");
PrintBB(Kings(), "Kings");
Console.WriteLine($"CastleFlags: {pos.CastleFlags}"); /* ..sl..SL short long opponent SHORT LONG side to move */
Console.WriteLine($"EnPassant column: {pos.EnPassant} (8 if not set)");
Console.WriteLine($"SideToMove: {pos.STM}"); /* side to move */
Console.WriteLine();
}
static void PrintBB(ulong bb, string label)
{
if (label != null)
Console.WriteLine(label);
Console.WriteLine(Convert.ToString((long)bb, 16).PadLeft(16, '0'));
Console.WriteLine("----------------");
byte[] bbBytes = BitConverter.GetBytes(bb);
Array.Reverse(bbBytes);
foreach (byte bbByte in bbBytes)
{
string line = Convert.ToString(bbByte, 2).PadLeft(8, '0');
line = line.Replace('1', 'X');
line = line.Replace('0', '.');
var chars = line.ToCharArray();
Array.Reverse(chars);
Console.WriteLine(string.Join(' ', chars));
}
Console.WriteLine();
}
private static long Divide(int depth)
{
long total = 0;
int index = 0;
var moveList = MovesLists[depth];
GenerateCapture(moveList, ref index);
GenerateQuiets(moveList, ref index);
for (int i = 0; i < index; i++)
{
if (Illegal(ref moveList[i]))
continue;
long nodes = 1;
if (depth > 1)
{
Make(ref moveList[i]);
nodes = Perft(depth - 1);
Position = Game[--iPosition];
}
total += nodes;
Console.WriteLine($" {MoveToStr(moveList[i], Position.STM)}: {nodes:N0}");
}
return total;
}
}
}
-
spirch
- Posts: 95
- Joined: Fri Nov 09, 2012 12:36 am
Re: Why C++ instead of C#?
i did a few things, included the lsb tweak above
compare before & after
compare before & after
Code: Select all
/*
This perft implementation is based on QBBEngine by Fabio Gobbato and ported to C# by Thomas Jahn
The purpose is to compare the speed differences of C# and C in chess-programming workload.
*/
using System;
using System.Buffers.Binary;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime;
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics.X86;
using System.Text;
using System.Threading;
namespace QBB
{
static class PieceType
{
/* define the move type, for example
KING|CASTLE is a castle move
PAWN|CAPTURE|EP is an enpassant move
PAWN|PROMO|CAPTURE is a promotion with a capture */
/* define the piece type: empty, pawn, knight, bishop, rook, queen, king */
public const byte EMPTY = 0;
public const byte PAWN = 1;
public const byte KNIGHT = 2;
public const byte BISHOP = PAWN | KNIGHT;
public const byte ROOK = 4;
public const byte QUEEN = PAWN | ROOK;
public const byte KING = KNIGHT | ROOK;
public const byte PIECE_MASK = 0x07;
public const byte CASTLE = 0x40;
public const byte PROMO = 0x20;
public const byte EP = 0x10;
public const byte CAPTURE = 0x08;
}
class QbbPerft
{
const int MAX_PLY = 32;
const int WHITE = 0;
const int BLACK = 8;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int NewMove(byte moveType, byte from, byte to, byte promotion) => moveType | (from << 8) | (to << 16) | (promotion << 24);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int MoveType(int move) => move & 255;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int MoveFrom(int move) => (move >> 8) & 255;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int MoveTo(int move) => (move >> 16) & 255;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int MovePromotion(int move) => (move >> 24) & 255;
/*
Board structure definition
PM,P0,P1,P2 are the 4 bitboards that contain the whole board
PM is the bitboard with the side to move pieces
P0,P1 and P2: with these bitboards you can obtain every type of pieces and every pieces combinations.
*/
struct TBoard
{
public ulong PM;
public ulong P0;
public ulong P1;
public ulong P2;
public byte CastleFlags; /* ..sl..SL short long opponent SHORT LONG side to move */
public byte EnPassant; /* enpassant column, =8 if not set */
public byte STM; /* side to move */
}
//static TBoard[] Game = new TBoard[MAX_PLY];
static int iPosition;
//private static TBoard Position;
/* array of bitboards that contains all the knight destination for every square */
static readonly ulong[] KnightDest = {
0x0000000000020400UL,0x0000000000050800UL,0x00000000000a1100UL,0x0000000000142200UL,
0x0000000000284400UL,0x0000000000508800UL,0x0000000000a01000UL,0x0000000000402000UL,
0x0000000002040004UL,0x0000000005080008UL,0x000000000a110011UL,0x0000000014220022UL,
0x0000000028440044UL,0x0000000050880088UL,0x00000000a0100010UL,0x0000000040200020UL,
0x0000000204000402UL,0x0000000508000805UL,0x0000000a1100110aUL,0x0000001422002214UL,
0x0000002844004428UL,0x0000005088008850UL,0x000000a0100010a0UL,0x0000004020002040UL,
0x0000020400040200UL,0x0000050800080500UL,0x00000a1100110a00UL,0x0000142200221400UL,
0x0000284400442800UL,0x0000508800885000UL,0x0000a0100010a000UL,0x0000402000204000UL,
0x0002040004020000UL,0x0005080008050000UL,0x000a1100110a0000UL,0x0014220022140000UL,
0x0028440044280000UL,0x0050880088500000UL,0x00a0100010a00000UL,0x0040200020400000UL,
0x0204000402000000UL,0x0508000805000000UL,0x0a1100110a000000UL,0x1422002214000000UL,
0x2844004428000000UL,0x5088008850000000UL,0xa0100010a0000000UL,0x4020002040000000UL,
0x0400040200000000UL,0x0800080500000000UL,0x1100110a00000000UL,0x2200221400000000UL,
0x4400442800000000UL,0x8800885000000000UL,0x100010a000000000UL,0x2000204000000000UL,
0x0004020000000000UL,0x0008050000000000UL,0x00110a0000000000UL,0x0022140000000000UL,
0x0044280000000000UL,0x0088500000000000UL,0x0010a00000000000UL,0x0020400000000000UL,
};
/* The same for the king */
static readonly ulong[] KingDest = {
0x0000000000000302UL,0x0000000000000705UL,0x0000000000000e0aUL,0x0000000000001c14UL,
0x0000000000003828UL,0x0000000000007050UL,0x000000000000e0a0UL,0x000000000000c040UL,
0x0000000000030203UL,0x0000000000070507UL,0x00000000000e0a0eUL,0x00000000001c141cUL,
0x0000000000382838UL,0x0000000000705070UL,0x0000000000e0a0e0UL,0x0000000000c040c0UL,
0x0000000003020300UL,0x0000000007050700UL,0x000000000e0a0e00UL,0x000000001c141c00UL,
0x0000000038283800UL,0x0000000070507000UL,0x00000000e0a0e000UL,0x00000000c040c000UL,
0x0000000302030000UL,0x0000000705070000UL,0x0000000e0a0e0000UL,0x0000001c141c0000UL,
0x0000003828380000UL,0x0000007050700000UL,0x000000e0a0e00000UL,0x000000c040c00000UL,
0x0000030203000000UL,0x0000070507000000UL,0x00000e0a0e000000UL,0x00001c141c000000UL,
0x0000382838000000UL,0x0000705070000000UL,0x0000e0a0e0000000UL,0x0000c040c0000000UL,
0x0003020300000000UL,0x0007050700000000UL,0x000e0a0e00000000UL,0x001c141c00000000UL,
0x0038283800000000UL,0x0070507000000000UL,0x00e0a0e000000000UL,0x00c040c000000000UL,
0x0302030000000000UL,0x0705070000000000UL,0x0e0a0e0000000000UL,0x1c141c0000000000UL,
0x3828380000000000UL,0x7050700000000000UL,0xe0a0e00000000000UL,0xc040c00000000000UL,
0x0203000000000000UL,0x0507000000000000UL,0x0a0e000000000000UL,0x141c000000000000UL,
0x2838000000000000UL,0x5070000000000000UL,0xa0e0000000000000UL,0x40c0000000000000UL
};
/* masks for finding the pawns that can capture with an enpassant (in move generation) */
static readonly ulong[] EnPassant = {
0x0000000200000000UL,0x0000000500000000UL,0x0000000A00000000UL,0x0000001400000000UL,
0x0000002800000000UL,0x0000005000000000UL,0x000000A000000000UL,0x0000004000000000UL
};
/* masks for finding the pawns that can capture with an enpassant (in make move) */
static readonly ulong[] EnPassantM = {
0x0000000002000000UL,0x0000000005000000UL,0x000000000A000000UL,0x0000000014000000UL,
0x0000000028000000UL,0x0000000050000000UL,0x00000000A0000000UL,0x0000000040000000UL
};
/*
reverse a bitboard:
A bitboard is an array of byte: Byte0,Byte1,Byte2,Byte3,Byte4,Byte5,Byte6,Byte7
after this function the bitboard will be: Byte7,Byte6,Byte5,Byte4,Byte3,Byte2,Byte1,Byte0
The board is saved always with the side to move in the low significant bits of the bitboard, so this function
is used to change the side to move
*/
//#define RevBB(bb) (__builtin_bswap64(bb))
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong _RevBB(ulong bb)
{
//Swap adjacent 32-bit blocks
bb = (bb >> 32) | (bb << 32);
//Swap adjacent 16-bit blocks
bb = ((bb & 0xFFFF0000FFFF0000U) >> 16) | ((bb & 0x0000FFFF0000FFFFU) << 16);
//Swap adjacent 8-bit blocks
bb = ((bb & 0xFF00FF00FF00FF00U) >> 8) | ((bb & 0x00FF00FF00FF00FFU) << 8);
return bb;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong RevBB(ulong bb) => BinaryPrimitives.ReverseEndianness(bb);
/* return the index of the most significant bit of the bitboard, bb must always be !=0 */
//#define MSB(bb) (0x3F ^ __builtin_clzll(bb))
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong MSB(ulong bb) => 63 ^ Lzcnt.X64.LeadingZeroCount(bb);
/* return the index of the least significant bit of the bitboard, bb must always be !=0 */
//#define LSB(bb) (__builtin_ctzll(bb))
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong LSB(ulong bb) => Bmi1.X64.TrailingZeroCount(bb);
/* extract the least significant bit of the bitboard */
//#define ExtractLSB(bb) ((bb)&(-(bb)))
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong _ExtractLSB(ulong bb) => bb & (0 - bb);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong ExtractLSB(ulong bb) => Bmi1.X64.ExtractLowestSetBit(bb);
/* reset the least significant bit of bb */
//#define ClearLSB(bb) ((bb)&((bb)-1))
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong _ClearLSB(ulong bb) => bb & (bb - 1);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong ClearLSB(ulong bb) => Bmi1.X64.ResetLowestSetBit(bb);
/* return the number of bits sets of a bitboard */
//#define PopCount(bb) (__builtin_popcountll(bb))
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static ulong PopCount(ulong bb) => Popcnt.X64.PopCount(bb);
/* Macro to check and reset the castle rights:
CastleSM: short castling side to move
CastleLM: long castling side to move
CastleSO: short castling opponent
CastleLO: long castling opponent
*/
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static bool CanCastleSM(ref TBoard Position) => (Position.CastleFlags & 0x02) > 0;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static bool CanCastleLM(ref TBoard Position) => (Position.CastleFlags & 0x01) > 0;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void ResetCastleSM(ref TBoard Position) => Position.CastleFlags &= 0xFD;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void ResetCastleLM(ref TBoard Position) => Position.CastleFlags &= 0xFE;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void ResetCastleSO(ref TBoard Position) => Position.CastleFlags &= 0xDF;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void ResetCastleLO(ref TBoard Position) => Position.CastleFlags &= 0xEF;
/* these Macros are used to calculate the bitboard of a particular kind of piece
P2 P1 P0
0 0 0 empty
0 0 1 pawn
0 1 0 knight
0 1 1 bishop
1 0 0 rook
1 0 1 queen
1 1 0 king
*/
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Occupation(ref TBoard Position) => Position.P0 | Position.P1 | Position.P2; /* board occupation */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Pawns(ref TBoard Position) => Position.P0 & ~Position.P1 & ~Position.P2; /* all the pawns on the board */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Knights(ref TBoard Position) => ~Position.P0 & Position.P1 & ~Position.P2;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Bishops(ref TBoard Position) => Position.P0 & Position.P1;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Rooks(ref TBoard Position) => ~Position.P0 & ~Position.P1 & Position.P2;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Queens(ref TBoard Position) => Position.P0 & Position.P2;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong QueenOrRooks(ref TBoard Position) => ~Position.P1 & Position.P2;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong QueenOrBishops(ref TBoard Position) => Position.P0 & (Position.P2 | Position.P1);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Kings(ref TBoard Position) => Position.P1 & Position.P2; /* a bitboard with the 2 kings */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong SideToMove(ref TBoard Position) => Position.PM;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static byte EnPass(ref TBoard Position) => Position.EnPassant;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Opposing(ref TBoard Position) => Position.PM ^ (Position.P0 | Position.P1 | Position.P2);
/* get the piece type giving the square */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong Piece(int sq, ref TBoard Position) => ((Position.P2 >> sq) & 1) << 2 |
((Position.P1 >> sq) & 1) << 1 |
((Position.P0 >> sq) & 1);
/* calculate the square related to the opponent */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int OppSq(int sp) => sp ^ 56;
/* Absolute Square, we need this macro to return the move in long algebric notation */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int AbsSq(int sq, int col) => col == WHITE ? sq : OppSq(sq);
/* get the corresponding string to the given move */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static string MoveToStr(int move, byte tomove)
{
Span<char> promo = stackalloc[] { ' ', ' ', 'n', 'b', 'r', 'q' };
StringBuilder result = new StringBuilder(6);
result.Append((char)('a' + AbsSq(MoveFrom(move), tomove) % 8));
result.Append((char)('1' + AbsSq(MoveFrom(move), tomove) / 8));
result.Append((char)('a' + AbsSq(MoveTo(move), tomove) % 8));
result.Append((char)('1' + AbsSq(MoveTo(move), tomove) / 8));
result.Append(promo[(byte)MovePromotion(move)]);
return result.ToString();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void ChangeSide(ref TBoard Position)
{
Position.PM ^= Occupation(ref Position); /* update the side to move pieces */
Position.PM = RevBB(Position.PM);
Position.P0 = RevBB(Position.P0);
Position.P1 = RevBB(Position.P1);
Position.P2 = RevBB(Position.P2);/* reverse the board */
Position.CastleFlags = (byte)((Position.CastleFlags >> 4) | (Position.CastleFlags << 4));/* roll the castle rights */
Position.STM ^= BLACK; /* change the side to move */
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static ulong GenRook(int sq, ulong occupation)
{
occupation ^= 1UL << sq; /* remove the selected piece from the occupation */
return (((0x8080808080808080UL >> (63 - (int)LSB((0x0101010101010101UL << sq) & (occupation | 0xFF00000000000000UL)))) & (0x0101010101010101UL << (int)MSB((0x8080808080808080UL >> (63 - sq)) & (occupation | 0x00000000000000FFUL)))) |
((0xFF00000000000000UL >> (63 - (int)LSB((0x00000000000000FFUL << sq) & (occupation | 0x8080808080808080UL)))) & (0x00000000000000FFUL << (int)MSB((0xFF00000000000000UL >> (63 - sq)) & (occupation | 0x0101010101010101UL))))) ^ (1UL << sq);
/* From every direction find the first piece and from that piece put a mask in the opposite direction.
Put togheter all the 4 masks and remove the moving piece */
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static ulong GenBishop(int sq, ulong occupation)
{
/* it's the same as the rook */
occupation ^= 1UL << sq;
return (((0x8040201008040201UL >> (63 - (int)LSB((0x8040201008040201UL << sq) & (occupation | 0xFF80808080808080UL)))) & (0x8040201008040201UL << (int)MSB((0x8040201008040201UL >> (63 - sq)) & (occupation | 0x01010101010101FFUL)))) |
((0x8102040810204081UL >> (63 - (int)LSB((0x8102040810204081UL << sq) & (occupation | 0xFF01010101010101UL)))) & (0x8102040810204081UL << (int)MSB((0x8102040810204081UL >> (63 - sq)) & (occupation | 0x80808080808080FFUL))))) ^ (1UL << sq);
}
/* return the bitboard with pieces of the same type */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong BBPieces(byte piece, ref TBoard Position)
{
switch (piece) // find the bb with the pieces of the same type
{
case PieceType.PAWN: return Pawns(ref Position);
case PieceType.KNIGHT: return Knights(ref Position);
case PieceType.BISHOP: return Bishops(ref Position);
case PieceType.ROOK: return Rooks(ref Position);
case PieceType.QUEEN: return Queens(ref Position);
case PieceType.KING: return Kings(ref Position);
default: return 0;
}
}
/* return the bitboard with the destinations of a piece in a square (exept for pawns) */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static ulong BBDestinations(byte piece, int sq, ulong occupation)
{
switch (piece) // generate the destination squares of the piece
{
case PieceType.KNIGHT: return KnightDest[sq];
case PieceType.BISHOP: return GenBishop(sq, occupation);
case PieceType.ROOK: return GenRook(sq, occupation);
case PieceType.QUEEN: return GenRook(sq, occupation) | GenBishop(sq, occupation);
case PieceType.KING: return KingDest[sq];
default: return 0;
}
}
/* try the move and see if the king is in check. If so return the attacking pieces, if not return 0 */
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool Illegal(int move, ref TBoard Position)
{
int kingsq = MoveTo(move);
ulong To = 1UL << kingsq;
ulong king = To;
ulong newoccupation = (Occupation(ref Position) ^ (1UL << MoveFrom(move))) | To;
ulong newopposing = Opposing(ref Position) & ~To;
int moveType = MoveType(move);
if ((moveType & PieceType.PIECE_MASK) != PieceType.KING)
{
king = Kings(ref Position) & SideToMove(ref Position);
kingsq = (int)LSB(king);
if ((moveType & PieceType.EP) > 0)
{
newoccupation ^= To >> 8;
newopposing ^= To >> 8;
}
}
bool kingIsSafe = //as soon as there's one attack you can stop evaluating the remaining peieces (early out)
(KnightDest[kingsq] & Knights(ref Position) & newopposing) == 0 &&
((((king << 9) & 0xFEFEFEFEFEFEFEFEUL) | ((king << 7) & 0x7F7F7F7F7F7F7F7FUL)) & Pawns(ref Position) & newopposing) == 0 &&
(GenBishop(kingsq, newoccupation) & QueenOrBishops(ref Position) & newopposing) == 0 &&
(GenRook(kingsq, newoccupation) & QueenOrRooks(ref Position) & newopposing) == 0 &&
((KingDest[kingsq] & Kings(ref Position)) & newopposing) == 0;
return !kingIsSafe;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void GenerateQuiets(int[] moves, ref int index, ref TBoard Position)
{
ulong occupation = Occupation(ref Position);
ulong opposing = Opposing(ref Position);
ulong lsb;
// generate moves from king to knight
for (byte piece = PieceType.KING; piece >= PieceType.KNIGHT; piece--)
{
// generate moves for every piece of the same type of the side to move
for (ulong pieces = BBPieces(piece, ref Position) & SideToMove(ref Position); pieces > 0; pieces = ClearLSB(pieces))
{
int square = (int)LSB(pieces);
// for every destinations on a free square generate a move
for (ulong destinations = ~occupation & BBDestinations(piece, square, occupation); destinations > 0; destinations = ClearLSB(destinations))
moves[index++] = NewMove(
piece,
(byte)square,
(byte)LSB(destinations),
0);
}
}
/* one pawns push */
ulong push1 = (((Pawns(ref Position) & SideToMove(ref Position)) << 8) & ~occupation) & 0x00FFFFFFFFFFFFFFUL;
for (ulong pieces = push1; pieces > 0; pieces = ClearLSB(pieces))
{
lsb = LSB(pieces);
moves[index++] = NewMove(
PieceType.PAWN,
(byte)(lsb - 8),
(byte)lsb, //TODO: avoid calling LSB twice?
0);
}
/* double pawns pushes */
ulong push2 = (push1 << 8) & ~occupation & 0x00000000FF000000UL;
for (; push2 > 0; push2 = ClearLSB(push2))
{
lsb = LSB(push2);
moves[index++] = NewMove(
PieceType.PAWN,
(byte)(lsb - 16),
(byte)lsb, //TODO: avoid calling LSB twice?
0);
}
/* check if long castling is possible */
if (CanCastleLM(ref Position) && (occupation & 0x0EUL) == 0)
{
if (((((ExtractLSB(0x1010101010101000UL & occupation) /* column e */
| ExtractLSB(0x0808080808080800UL & occupation) /*column d */
| ExtractLSB(0x0404040404040400UL & occupation) /*column c */
| ExtractLSB(0x00000000000000E0UL & occupation) /* row 1 */) & QueenOrRooks(ref Position)) | ((ExtractLSB(0x0000000102040800UL & occupation) /*antidiag from e1/e8 */
| ExtractLSB(0x0000000001020400UL & occupation) /*antidiag from d1/d8 */
| ExtractLSB(0x0000000000010200UL & occupation) /*antidiag from c1/c8 */
| ExtractLSB(0x0000000080402000UL & occupation) /*diag from e1/e8 */
| ExtractLSB(0x0000008040201000UL & occupation) /*diag from d1/d8 */
| ExtractLSB(0x0000804020100800UL & occupation) /*diag from c1/c8 */) & QueenOrBishops(ref Position)) | (0x00000000003E7700UL & Knights(ref Position)) |
(0x0000000000003E00UL & Pawns(ref Position)) | (Kings(ref Position) & 0x0000000000000600UL)) & opposing) == 0)
/* check if c1/c8 d1/d8 e1/e8 are not attacked */
moves[index++] = NewMove(
PieceType.KING | PieceType.CASTLE,
4,
2,
0);
}
/* check if short castling is possible */
if (CanCastleSM(ref Position) && (occupation & 0x60UL) == 0)
{
if (((((ExtractLSB(0x1010101010101000UL & occupation) /* column e */
| ExtractLSB(0x2020202020202000UL & occupation) /* column f */
| ExtractLSB(0x4040404040404000UL & occupation) /* column g */
| 1UL << (byte)MSB(0x000000000000000FUL & (occupation | 0x1UL))/* row 1 */) & QueenOrRooks(ref Position)) | ((ExtractLSB(0x0000000102040800UL & occupation) /* antidiag from e1/e8 */
| ExtractLSB(0x0000010204081000UL & occupation) /*antidiag from f1/f8 */
| ExtractLSB(0x0001020408102000UL & occupation) /*antidiag from g1/g8 */
| ExtractLSB(0x0000000080402000UL & occupation) /*diag from e1/e8 */
| ExtractLSB(0x0000000000804000UL & occupation) /*diag from f1/f8 */
| 0x0000000000008000UL /*diag from g1/g8 */) & QueenOrBishops(ref Position)) | (0x0000000000F8DC00UL & Knights(ref Position)) |
(0x000000000000F800UL & Pawns(ref Position)) | (Kings(ref Position) & 0x0000000000004000UL)) & opposing) == 0)
/* check if e1/e8 f1/f8 g1/g8 are not attacked */
moves[index++] = NewMove(
PieceType.KING | PieceType.CASTLE,
4,
6,
0);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void GenerateCapture(int[] moves, ref int index, ref TBoard Position)
{
ulong occupation = Occupation(ref Position);
ulong opposing = Opposing(ref Position);
ulong lsb;
// generate moves from king to knight
for (byte piece = PieceType.KING; piece >= PieceType.KNIGHT; piece--)
{
// generate moves for every piece of the same type of the side to move
for (ulong pieces = BBPieces(piece, ref Position) & SideToMove(ref Position); pieces > 0; pieces = ClearLSB(pieces))
{
int square = (int)LSB(pieces);
// for every destinations on an opponent pieces generate a move
for (ulong destinations = opposing & BBDestinations(piece, square, occupation);
destinations > 0;
destinations = ClearLSB(destinations))
moves[index++] = NewMove(
(byte)(piece | PieceType.CAPTURE),
(byte)square,
(byte)LSB(destinations),
0);
//Eval = (Piece(LSB(destinations)) << 4) | (KING - piece);
}
}
ulong pawns = Pawns(ref Position) & SideToMove(ref Position);
/* Generate pawns right captures */
for (ulong rpc = (pawns << 9) & 0x00FEFEFEFEFEFEFEUL & opposing; rpc > 0; rpc = ClearLSB(rpc))
{
lsb = LSB(rpc);
moves[index++] = NewMove(
PieceType.PAWN | PieceType.CAPTURE,
(byte)(lsb - 9),
(byte)lsb,
0);
//Eval = (Piece(LSB(captureri)) << 4) | (KING - PAWN);
}
/* Generate pawns left captures */
for (ulong lpc = (pawns << 7) & 0x007F7F7F7F7F7F7FUL & opposing; lpc > 0; lpc = ClearLSB(lpc))
{
lsb = LSB(lpc);
moves[index++] = NewMove(
PieceType.PAWN | PieceType.CAPTURE,
(byte)(lsb - 7),
(byte)lsb,
0);
//Eval = (Piece(LSB(capturele))<<4)|(KING-PAWN);
}
/* Generate pawns promotions */
if ((pawns & 0x00FF000000000000UL) > 0)
{
/* promotions with left capture */
for (ulong promo = (pawns << 9) & 0xFE00000000000000UL & opposing; promo > 0; promo = ClearLSB(promo))
{
lsb = LSB(promo);
for (byte piece = PieceType.QUEEN; piece >= PieceType.KNIGHT; piece--)
{
moves[index++] = NewMove(
PieceType.PAWN | PieceType.PROMO | PieceType.CAPTURE,
(byte)(lsb - 9),
(byte)lsb,
piece);
//Eval = (piece<<4)|(KING-PAWN);
}
}
/* promotions with right capture */
for (ulong promo = (pawns << 7) & 0x7F00000000000000UL & opposing; promo > 0; promo = ClearLSB(promo))
{
lsb = LSB(promo);
for (byte piece = PieceType.QUEEN; piece >= PieceType.KNIGHT; piece--)
{
moves[index++] = NewMove(
PieceType.PAWN | PieceType.PROMO | PieceType.CAPTURE,
(byte)(lsb - 7),
(byte)lsb,
piece);
//Eval = (piece<<4)|(KING-PAWN);
}
}
/* no capture promotions */
for (ulong promo = ((pawns << 8) & ~occupation) & 0xFF00000000000000UL;
promo > 0;
promo = ClearLSB(promo))
{
lsb = LSB(promo);
for (byte piece = PieceType.QUEEN; piece >= PieceType.KNIGHT; piece--)
{
moves[index++] = NewMove(
PieceType.PAWN | PieceType.PROMO,
(byte)(lsb - 8),
(byte)lsb,
piece);
//Eval = (piece<<4)|(KING-PAWN);
}
}
}
if (EnPass(ref Position) != 8)
{
for (ulong enpassant = pawns & EnPassant[EnPass(ref Position)]; enpassant > 0; enpassant = ClearLSB((enpassant)))
moves[index++] = NewMove(
PieceType.PAWN | PieceType.EP | PieceType.PROMO,
(byte)LSB(enpassant),
(byte)(40 + EnPass(ref Position)),
0);
//Eval = (PAWN<<4)|(KING-PAWN);
}
}
//[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void Make(int move, ref TBoard Position, ref TBoard[] Game)
{
int to = MoveTo(move); ;
Game[iPosition++] = Position;
ulong part = 1UL << MoveFrom(move);
ulong dest = 1UL << to;
int moveType = MoveType(move);
switch (moveType & PieceType.PIECE_MASK)
{
case PieceType.PAWN:
if ((moveType & PieceType.EP) > 0)
{ /* EnPassant */
Position.PM ^= part | dest;
Position.P0 ^= part | dest;
Position.P0 ^= dest >> 8; //delete the captured pawn
Position.EnPassant = 8;
}
else
{
//TODO: move.IsCapture
if ((moveType & PieceType.CAPTURE) > 0)
{
/* Delete the captured piece */
Position.P0 &= ~dest;
Position.P1 &= ~dest;
Position.P2 &= ~dest;
}
if ((moveType & PieceType.PROMO) > 0)
{
int promotion = MovePromotion(move);
Position.PM ^= part | dest;
Position.P0 ^= part;
Position.P0 |= (ulong)(promotion & 1) << to;
Position.P1 |= (ulong)((promotion >> 1) & 1) << to;
Position.P2 |= (ulong)(promotion >> 2) << to;
Position.EnPassant = 8; /* clear enpassant */
}
else /* capture or push */
{
Position.PM ^= part | dest;
Position.P0 ^= part | dest;
Position.EnPassant = 8; /* clear enpassant */
if (to == MoveFrom(move) + 16 && (EnPassantM[to & 0x07] & Pawns(ref Position) & Opposing(ref Position)) > 0)
Position.EnPassant = (byte)(to & 0x07); /* save enpassant column */
}
if ((moveType & PieceType.CAPTURE) > 0)
{
if (to == 63) ResetCastleSO(ref Position); /* captured the opponent king side rook */
else if (to == 56) ResetCastleLO(ref Position); /* captured the opponent quuen side rook */
}
}
ChangeSide(ref Position);
break;
case PieceType.KNIGHT:
case PieceType.BISHOP:
case PieceType.ROOK:
case PieceType.QUEEN:
if ((moveType & PieceType.CAPTURE) > 0)
{
/* Delete the captured piece */
Position.P0 &= ~dest;
Position.P1 &= ~dest;
Position.P2 &= ~dest;
}
Position.PM ^= part | dest;
//TODO: handle N, B, R & Q seperately?
Position.P0 ^= ((moveType & 1) > 0) ? part | dest : 0;
Position.P1 ^= ((moveType & 2) > 0) ? part | dest : 0;
Position.P2 ^= ((moveType & 4) > 0) ? part | dest : 0;
Position.EnPassant = 8;
if ((moveType & PieceType.PIECE_MASK) == PieceType.ROOK)
{
if (MoveFrom(move) == 7)
ResetCastleSM(ref Position); //king side rook moved
else if (MoveFrom(move) == 0)
ResetCastleLM(ref Position); // queen side rook moved
}
if ((moveType & PieceType.CAPTURE) > 0)
{
if (to == 63) ResetCastleSO(ref Position); /* captured the opponent king side rook */
else if (to == 56) ResetCastleLO(ref Position); /* captured the opponent quuen side rook */
}
ChangeSide(ref Position);
break;
case PieceType.KING:
if ((moveType & PieceType.CAPTURE) > 0)
{
/* Delete the captured piece */
Position.P0 &= ~dest;
Position.P1 &= ~dest;
Position.P2 &= ~dest;
}
Position.PM ^= part | dest;
Position.P1 ^= part | dest;
Position.P2 ^= part | dest;
ResetCastleSM(ref Position); /* update the castle rights */
ResetCastleLM(ref Position);
Position.EnPassant = 8;
if ((moveType & PieceType.CAPTURE) > 0)
{
if (to == 63)
ResetCastleSO(ref Position); /* captured the opponent king side rook */
else if (to == 56)
ResetCastleLO(ref Position); /* captured the opponent quuen side rook */
}
else if ((moveType & PieceType.CASTLE) > 0)
{
if (to == 6)
{
Position.PM ^= 0x00000000000000A0UL;
Position.P2 ^= 0x00000000000000A0UL;
} /* short castling */
else
{
Position.PM ^= 0x0000000000000009UL;
Position.P2 ^= 0x0000000000000009UL;
} /* long castling */
}
ChangeSide(ref Position);
break;
}
}
private static void LoadPosition(string fen, ref TBoard pos)
{
/* Clear the board */
pos.P0 = pos.P1 = pos.P2 = pos.PM = 0;
pos.EnPassant = 8;
pos.STM = WHITE;
pos.CastleFlags = 0;
/* translate the fen to the relative position */
byte pieceside = WHITE;
ulong piece = (ulong)PieceType.PAWN;
byte sidetomove = WHITE;
int square = 0;
int cursor;
for (cursor = 0; fen[cursor] != ' '; cursor++)
{
char cur = fen[cursor];
if (cur >= '1' && cur <= '8')
square += cur - '0';
else if (cur != '/')
{
int bit = OppSq(square);
if (cur == 'p') { piece = (ulong)PieceType.PAWN; pieceside = BLACK; }
else if (cur == 'n') { piece = (ulong)PieceType.KNIGHT; pieceside = BLACK; }
else if (cur == 'b') { piece = (ulong)PieceType.BISHOP; pieceside = BLACK; }
else if (cur == 'r') { piece = (ulong)PieceType.ROOK; pieceside = BLACK; }
else if (cur == 'q') { piece = (ulong)PieceType.QUEEN; pieceside = BLACK; }
else if (cur == 'k') { piece = (ulong)PieceType.KING; pieceside = BLACK; }
else if (cur == 'P') { piece = (ulong)PieceType.PAWN; pieceside = WHITE; }
else if (cur == 'N') { piece = (ulong)PieceType.KNIGHT; pieceside = WHITE; }
else if (cur == 'B') { piece = (ulong)PieceType.BISHOP; pieceside = WHITE; }
else if (cur == 'R') { piece = (ulong)PieceType.ROOK; pieceside = WHITE; }
else if (cur == 'Q') { piece = (ulong)PieceType.QUEEN; pieceside = WHITE; }
else if (cur == 'K') { piece = (ulong)PieceType.KING; pieceside = WHITE; }
pos.P0 |= (piece & 1) << bit; //001
pos.P1 |= ((piece >> 1) & 1) << bit; //010
pos.P2 |= (piece >> 2) << bit; //100
if (pieceside == WHITE)
{
pos.PM |= (1UL << bit);
piece |= BLACK;
}
square++;
}
}
cursor++; /* read the side to move */
if (fen[cursor] == 'w')
sidetomove = WHITE;
else if (fen[cursor] == 'b')
sidetomove = BLACK;
cursor += 2;
if (fen[cursor] != '-') /* read the castle rights */
{
for (; fen[cursor] != ' '; cursor++)
{
char cur = fen[cursor];
if (cur == 'K') pos.CastleFlags |= 0x02;
else if (cur == 'Q') pos.CastleFlags |= 0x01;
else if (cur == 'k') pos.CastleFlags |= 0x20;
else if (cur == 'q') pos.CastleFlags |= 0x10;
}
cursor++;
}
else cursor += 2;
if (fen[cursor] != '-') /* read the enpassant column */
{
pos.EnPassant = (byte)(fen[cursor] - 'a');
//cursor++;
}
if (sidetomove == BLACK)
ChangeSide(ref pos);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static long Perft(int depth, ref TBoard Position, ref TBoard[] Game, int[][] MovesLists)
{
long total = 0;
int index = 0;
var moveList = MovesLists[depth];
GenerateCapture(moveList, ref index, ref Position);
GenerateQuiets(moveList, ref index, ref Position);
for (int i = 0; i < index; i++)
{
if (Illegal(moveList[i], ref Position))
continue;
if (depth > 1)
{
Make(moveList[i], ref Position, ref Game);
total += Perft(depth - 1, ref Position, ref Game, MovesLists);
Position = Game[--iPosition];
}
else
total++;
}
return total;
}
struct PerftResult
{
public double Duration;
public long Nodes;
public PerftResult(double t, long n)
{
Duration = t;
Nodes = n;
}
public static PerftResult operator +(PerftResult a, PerftResult b) => new(a.Duration + b.Duration, a.Nodes + b.Nodes);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static PerftResult TestPerft(string fen, int depth, int expectedResult, ref TBoard Position, ref TBoard[] Game, int[][] MovesLists)
{
LoadPosition(fen, ref Position);
//PrintPosition(Game[Position]);
long t0 = Stopwatch.GetTimestamp();
long count = Perft(depth, ref Position, ref Game, MovesLists);
long t1 = Stopwatch.GetTimestamp();
double dt = (t1 - t0) / (double)Stopwatch.Frequency;
double ms = (1000 * dt);
if (expectedResult != count)
{
Console.WriteLine($"ERROR in Perft({fen}, {depth})");
Console.WriteLine($"Computed result: {count}");
Console.WriteLine($"Expected result: {expectedResult}");
}
else
Console.WriteLine($"OK! {(int)ms}ms, {(int)(count / ms)}K NPS");
return new PerftResult(dt, count);
}
static void Main(string[] args)
{
TBoard[] Game = new TBoard[MAX_PLY];
TBoard position = new TBoard();
int[][] MovesLists = new int[MAX_PLY][];
for (int i = 0; i < MAX_PLY; i++)
MovesLists[i] = new int[225];
Console.WriteLine("QBB Perft in C#");
Console.WriteLine("https://github.com/lithander/QBB-Perft/tree/v1.4");
Console.WriteLine();
PerftResult accu = TestPerft("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1", 6, 119060324, ref position, ref Game, MovesLists); //Start Position
accu += TestPerft("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", 5, 193690690, ref position, ref Game, MovesLists);
accu += TestPerft("8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1", 7, 178633661, ref position, ref Game, MovesLists);
accu += TestPerft("r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1", 6, 706045033, ref position, ref Game, MovesLists);
accu += TestPerft("rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6", 3, 53392, ref position, ref Game, MovesLists);
accu += TestPerft("r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10", 5, 164075551, ref position, ref Game, MovesLists);
Console.WriteLine();
Console.WriteLine($"Total: {accu.Nodes} Nodes, {(int)(1000 * accu.Duration)}ms, {(int)(accu.Nodes / accu.Duration / 1000)}K NPS");
Console.WriteLine("Press any key to quit");//stop command prompt from closing automatically on windows
Console.ReadKey();
}
//**** Debug Helpers not in the original C code
private static void PrintPosition(TBoard pos, ref TBoard Position)
{
PrintBB(pos.PM, "PM");
PrintBB(pos.P0, "P0");
PrintBB(pos.P1, "P1");
PrintBB(pos.P2, "P2");
Console.WriteLine("- - - -");
PrintBB(Pawns(ref Position), "Pawns");
PrintBB(Knights(ref Position), "Knights");
PrintBB(Bishops(ref Position), "Bishops");
PrintBB(Rooks(ref Position), "Roosk");
PrintBB(Queens(ref Position), "Queens");
PrintBB(Kings(ref Position), "Kings");
Console.WriteLine($"CastleFlags: {pos.CastleFlags}"); /* ..sl..SL short long opponent SHORT LONG side to move */
Console.WriteLine($"EnPassant column: {pos.EnPassant} (8 if not set)");
Console.WriteLine($"SideToMove: {pos.STM}"); /* side to move */
Console.WriteLine();
}
static void PrintBB(ulong bb, string label)
{
if (label != null)
Console.WriteLine(label);
Console.WriteLine(Convert.ToString((long)bb, 16).PadLeft(16, '0'));
Console.WriteLine("----------------");
byte[] bbBytes = BitConverter.GetBytes(bb);
Array.Reverse(bbBytes);
foreach (byte bbByte in bbBytes)
{
string line = Convert.ToString(bbByte, 2).PadLeft(8, '0');
line = line.Replace('1', 'X');
line = line.Replace('0', '.');
var chars = line.ToCharArray();
Array.Reverse(chars);
Console.WriteLine(string.Join(' ', chars));
}
Console.WriteLine();
}
private static long Divide(int depth, ref TBoard Position, ref TBoard[] Game, int[][] MovesLists)
{
long total = 0;
int index = 0;
var moveList = MovesLists[depth];
GenerateCapture(moveList, ref index, ref Position);
GenerateQuiets(moveList, ref index, ref Position);
for (int i = 0; i < index; i++)
{
if (Illegal(moveList[i], ref Position))
continue;
long nodes = 1;
if (depth > 1)
{
Make(moveList[i], ref Position, ref Game);
nodes = Perft(depth - 1, ref Position, ref Game, MovesLists);
Position = Game[--iPosition];
}
total += nodes;
Console.WriteLine($" {MoveToStr(moveList[i], Position.STM)}: {nodes:N0}");
}
return total;
}
}
}-
mvanthoor
- Posts: 1784
- Joined: Wed Jul 03, 2019 4:42 pm
- Location: Netherlands
- Full name: Marcel Vanthoor
-
Joost Buijs
- Posts: 1632
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Why C++ instead of C#?
I've modified the C version a little bit so that it will run under C++ with MSVC and Clang.
For timing it now uses the C++ <chrono> library.
On my 10980XE the speed compiled with Clang12 is as follows:
With PGO it can probably be optimized even further, I haven't tried yet.
For timing it now uses the C++ <chrono> library.
Code: Select all
/*
This perft implementation is based on QBBEngine by Fabio Gobbato
Some parts of this source call gcc intrinsic functions. If you are not using gcc you need to
change them with the functions of your compiler.
*/
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>
#include <chrono>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#define WHITE 0
#define BLACK 8
#define MAX_PLY 32
/* define the piece type: empty, pawn, knight, bishop, rook, queen, king */
enum : int { EMPTY, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING };
typedef int TPieceType;
/* define the move type, for example
KING|CASTLE is a castle move
PAWN|CAPTURE|EP is an enpassant move
PAWN|PROMO|CAPTURE is a promotion with a capture */
enum : int { CASTLE = 0x40, PROMO = 0x20, EP = 0x10, CAPTURE = 0x08 };
typedef int TMoveType;
/* bitboard types */
typedef uint64_t TBB;
/* move structure */
typedef union
{
struct {
uint8_t MoveType;
uint8_t From;
uint8_t To;
uint8_t Prom;
};
unsigned int Move;
}TMove;
/* structure for a capture, it needs the Eval field for MVV/LVA ordering */
typedef struct
{
TMove Move;
//int Eval;
} TMoveEval;
/*
Board structure definition
PM,P0,P1,P2 are the 4 bitboards that contain the whole board
PM is the bitboard with the side to move pieces
P0,P1 and P2: with these bitboards you can obtain every type of pieces and every pieces combinations.
*/
typedef struct
{
TBB PM;
TBB P0;
TBB P1;
TBB P2;
uint8_t CastleFlags; /* ..sl..SL short long opponent SHORT LONG side to move */
uint8_t EnPassant; /* enpassant column, =8 if not set */
uint8_t STM; /* side to move */
} TBoard;
/*
Into Game are saved all the positions from the last 50 move counter reset
Position is the pointer to the last position of the game
*/
TBoard Game[MAX_PLY];
TBoard* Position;
/* array of bitboards that contains all the knight destination for every square */
const TBB KnightDest[64] = { 0x0000000000020400ULL,0x0000000000050800ULL,0x00000000000a1100ULL,0x0000000000142200ULL,
0x0000000000284400ULL,0x0000000000508800ULL,0x0000000000a01000ULL,0x0000000000402000ULL,
0x0000000002040004ULL,0x0000000005080008ULL,0x000000000a110011ULL,0x0000000014220022ULL,
0x0000000028440044ULL,0x0000000050880088ULL,0x00000000a0100010ULL,0x0000000040200020ULL,
0x0000000204000402ULL,0x0000000508000805ULL,0x0000000a1100110aULL,0x0000001422002214ULL,
0x0000002844004428ULL,0x0000005088008850ULL,0x000000a0100010a0ULL,0x0000004020002040ULL,
0x0000020400040200ULL,0x0000050800080500ULL,0x00000a1100110a00ULL,0x0000142200221400ULL,
0x0000284400442800ULL,0x0000508800885000ULL,0x0000a0100010a000ULL,0x0000402000204000ULL,
0x0002040004020000ULL,0x0005080008050000ULL,0x000a1100110a0000ULL,0x0014220022140000ULL,
0x0028440044280000ULL,0x0050880088500000ULL,0x00a0100010a00000ULL,0x0040200020400000ULL,
0x0204000402000000ULL,0x0508000805000000ULL,0x0a1100110a000000ULL,0x1422002214000000ULL,
0x2844004428000000ULL,0x5088008850000000ULL,0xa0100010a0000000ULL,0x4020002040000000ULL,
0x0400040200000000ULL,0x0800080500000000ULL,0x1100110a00000000ULL,0x2200221400000000ULL,
0x4400442800000000ULL,0x8800885000000000ULL,0x100010a000000000ULL,0x2000204000000000ULL,
0x0004020000000000ULL,0x0008050000000000ULL,0x00110a0000000000ULL,0x0022140000000000ULL,
0x0044280000000000ULL,0x0088500000000000ULL,0x0010a00000000000ULL,0x0020400000000000ULL };
/* The same for the king */
const TBB KingDest[64] = { 0x0000000000000302ULL,0x0000000000000705ULL,0x0000000000000e0aULL,0x0000000000001c14ULL,
0x0000000000003828ULL,0x0000000000007050ULL,0x000000000000e0a0ULL,0x000000000000c040ULL,
0x0000000000030203ULL,0x0000000000070507ULL,0x00000000000e0a0eULL,0x00000000001c141cULL,
0x0000000000382838ULL,0x0000000000705070ULL,0x0000000000e0a0e0ULL,0x0000000000c040c0ULL,
0x0000000003020300ULL,0x0000000007050700ULL,0x000000000e0a0e00ULL,0x000000001c141c00ULL,
0x0000000038283800ULL,0x0000000070507000ULL,0x00000000e0a0e000ULL,0x00000000c040c000ULL,
0x0000000302030000ULL,0x0000000705070000ULL,0x0000000e0a0e0000ULL,0x0000001c141c0000ULL,
0x0000003828380000ULL,0x0000007050700000ULL,0x000000e0a0e00000ULL,0x000000c040c00000ULL,
0x0000030203000000ULL,0x0000070507000000ULL,0x00000e0a0e000000ULL,0x00001c141c000000ULL,
0x0000382838000000ULL,0x0000705070000000ULL,0x0000e0a0e0000000ULL,0x0000c040c0000000ULL,
0x0003020300000000ULL,0x0007050700000000ULL,0x000e0a0e00000000ULL,0x001c141c00000000ULL,
0x0038283800000000ULL,0x0070507000000000ULL,0x00e0a0e000000000ULL,0x00c040c000000000ULL,
0x0302030000000000ULL,0x0705070000000000ULL,0x0e0a0e0000000000ULL,0x1c141c0000000000ULL,
0x3828380000000000ULL,0x7050700000000000ULL,0xe0a0e00000000000ULL,0xc040c00000000000ULL,
0x0203000000000000ULL,0x0507000000000000ULL,0x0a0e000000000000ULL,0x141c000000000000ULL,
0x2838000000000000ULL,0x5070000000000000ULL,0xa0e0000000000000ULL,0x40c0000000000000ULL };
/* masks for finding the pawns that can capture with an enpassant (in move generation) */
const TBB EnPassant[8] = {
0x0000000200000000ULL,0x0000000500000000ULL,0x0000000A00000000ULL,0x0000001400000000ULL,
0x0000002800000000ULL,0x0000005000000000ULL,0x000000A000000000ULL,0x0000004000000000ULL
};
/* masks for finding the pawns that can capture with an enpassant (in make move) */
const TBB EnPassantM[8] = {
0x0000000002000000ULL,0x0000000005000000ULL,0x000000000A000000ULL,0x0000000014000000ULL,
0x0000000028000000ULL,0x0000000050000000ULL,0x00000000A0000000ULL,0x0000000040000000ULL
};
/*
reverse a bitboard:
A bitboard is an array of byte: Byte0,Byte1,Byte2,Byte3,Byte4,Byte5,Byte6,Byte7
after this function the bitboard will be: Byte7,Byte6,Byte5,Byte4,Byte3,Byte2,Byte1,Byte0
The board is saved always with the side to move in the low significant bits of the bitboard, so this function
is used to change the side to move
*/
#if defined(_MSC_VER)
#define RevBB(bb) (_byteswap_uint64(bb))
/* return the index of the most significant bit of the bitboard, bb must always be !=0 */
#define MSB(bb) (0x3F ^ _lzcnt_u64(bb))
/* return the index of the least significant bit of the bitboard, bb must always be !=0 */
#define LSB(bb) (_tzcnt_u64(bb))
/* extract the least significant bit of the bitboard */
#define ExtractLSB(bb) (_blsi_u64(bb))
/* reset the least significant bit of bb */
#define ClearLSB(bb) (_blsr_u64(bb))
/* return the number of bits sets of a bitboard */
#define PopCount(bb) (_popcnt_u64(bb))
#else
#define RevBB(bb) (__builtin_bswap64(bb))
/* return the index of the most significant bit of the bitboard, bb must always be !=0 */
#define MSB(bb) (0x3F ^ __builtin_clzll(bb))
/* return the index of the least significant bit of the bitboard, bb must always be !=0 */
#define LSB(bb) (__builtin_ctzll(bb))
/* extract the least significant bit of the bitboard */
#define ExtractLSB(bb) ((bb)&(-(bb)))
/* reset the least significant bit of bb */
#define ClearLSB(bb) ((bb)&((bb)-1))
/* return the number of bits sets of a bitboard */
#define PopCount(bb) (__builtin_popcountll(bb))
#endif
/* Macro to check and reset the castle rights:
CastleSM: short castling side to move
CastleLM: long castling side to move
CastleSO: short castling opponent
CastleLO: long castling opponent
*/
#define CastleSM (Position->CastleFlags&0x02)
#define CastleLM (Position->CastleFlags&0x01)
#define CastleSO (Position->CastleFlags&0x20)
#define CastleLO (Position->CastleFlags&0x10)
#define ResetCastleSM (Position->CastleFlags&=0xFD)
#define ResetCastleLM (Position->CastleFlags&=0xFE)
#define ResetCastleSO (Position->CastleFlags&=0xDF)
#define ResetCastleLO (Position->CastleFlags&=0xEF)
/* these Macros are used to calculate the bitboard of a particular kind of piece
P2 P1 P0
0 0 0 empty
0 0 1 pawn
0 1 0 knight
0 1 1 bishop
1 0 0 rook
1 0 1 queen
1 1 0 king
*/
#define Occupation (Position->P0 | Position->P1 | Position->P2) /* board occupation */
#define Pawns (Position->P0 & ~Position->P1 & ~Position->P2) /* all the pawns on the board */
#define Knights (~Position->P0 & Position->P1 & ~Position->P2)
#define Bishops (Position->P0 & Position->P1)
#define Rooks (~Position->P0 & ~Position->P1 & Position->P2)
#define Queens (Position->P0 & Position->P2)
#define Kings (Position->P1 & Position->P2) /* a bitboard with the 2 kings */
/* get the piece type giving the square */
#define Piece(sq) (((Position->P2>>(sq))&1)<<2 | ((Position->P1>>(sq))&1)<<1 | ((Position->P0>>(sq))&1))
/* calculate the square related to the opponent */
#define OppSq(sp) ((sp)^0x38)
/* Absolute Square, we need this macro to return the move in long algebric notation */
#define AbsSq(sq,col) ((col)==WHITE ? (sq):OppSq(sq))
/* get the corresponding string to the given move */
static inline void MoveToStr(char* strmove, TMove move, uint8_t tomove)
{
const char promo[7] = "\0\0nbrq";
strmove[0] = 'a' + AbsSq(move.From, tomove) % 8;
strmove[1] = '1' + AbsSq(move.From, tomove) / 8;
strmove[2] = 'a' + AbsSq(move.To, tomove) % 8;
strmove[3] = '1' + AbsSq(move.To, tomove) / 8;
strmove[4] = promo[move.Prom];
strmove[5] = '\0';
}
/*
The board is always saved with the side to move in the lower part of the bitboards to use the same generation and
make for the Black and the White side.
This needs the inversion of the 4 bitboards, roll the Castle rights and update the side to move.
*/
#define ChangeSide \
do{ \
Position->PM^=Occupation; /* update the side to move pieces */\
Position->PM=RevBB(Position->PM);\
Position->P0=RevBB(Position->P0);\
Position->P1=RevBB(Position->P1);\
Position->P2=RevBB(Position->P2);/* reverse the board */\
Position->CastleFlags=(Position->CastleFlags>>4)|(Position->CastleFlags<<4);/* roll the castle rights */\
Position->STM ^= BLACK; /* change the side to move */\
}while(0)
/* return the bitboard with the rook destinations */
static inline TBB GenRook(uint64_t sq, TBB occupation)
{
TBB piece = 1ULL << sq;
occupation ^= piece; /* remove the selected piece from the occupation */
TBB piecesup = (0x0101010101010101ULL << sq) & (occupation | 0xFF00000000000000ULL); /* find the pieces up */
TBB piecesdo = (0x8080808080808080ULL >> (63 - sq)) & (occupation | 0x00000000000000FFULL); /* find the pieces down */
TBB piecesri = (0x00000000000000FFULL << sq) & (occupation | 0x8080808080808080ULL); /* find pieces on the right */
TBB piecesle = (0xFF00000000000000ULL >> (63 - sq)) & (occupation | 0x0101010101010101ULL); /* find pieces on the left */
return (((0x8080808080808080ULL >> (63 - LSB(piecesup))) & (0x0101010101010101ULL << MSB(piecesdo))) |
((0xFF00000000000000ULL >> (63 - LSB(piecesri))) & (0x00000000000000FFULL << MSB(piecesle)))) ^ piece;
/* From every direction find the first piece and from that piece put a mask in the opposite direction.
Put togheter all the 4 masks and remove the moving piece */
}
/* return the bitboard with the bishops destinations */
static inline TBB GenBishop(uint64_t sq, TBB occupation)
{ /* it's the same as the rook */
TBB piece = 1ULL << sq;
occupation ^= piece;
TBB piecesup = (0x8040201008040201ULL << sq) & (occupation | 0xFF80808080808080ULL);
TBB piecesdo = (0x8040201008040201ULL >> (63 - sq)) & (occupation | 0x01010101010101FFULL);
TBB piecesle = (0x8102040810204081ULL << sq) & (occupation | 0xFF01010101010101ULL);
TBB piecesri = (0x8102040810204081ULL >> (63 - sq)) & (occupation | 0x80808080808080FFULL);
return (((0x8040201008040201ULL >> (63 - LSB(piecesup))) & (0x8040201008040201ULL << MSB(piecesdo))) |
((0x8102040810204081ULL >> (63 - LSB(piecesle))) & (0x8102040810204081ULL << MSB(piecesri)))) ^ piece;
}
/* return the bitboard with pieces of the same type */
static inline TBB BBPieces(TPieceType piece)
{
switch (piece) // find the bb with the pieces of the same type
{
case PAWN: return Pawns;
case KNIGHT: return Knights;
case BISHOP: return Bishops;
case ROOK: return Rooks;
case QUEEN: return Queens;
case KING: return Kings;
}
return 0;
}
/* return the bitboard with the destinations of a piece in a square (exept for pawns) */
static inline TBB BBDestinations(TPieceType piece, uint64_t sq, TBB occupation)
{
switch (piece) // generate the destination squares of the piece
{
case KNIGHT: return KnightDest[sq];
case BISHOP: return GenBishop(sq, occupation);
case ROOK: return GenRook(sq, occupation);
case QUEEN: return GenRook(sq, occupation) | GenBishop(sq, occupation);
case KING: return KingDest[sq];
}
return 0;
}
/* try the move and see if the king is in check. If so return the attacking pieces, if not return 0 */
static inline TBB Illegal(TMove move)
{
TBB From, To;
From = 1ULL << move.From;
To = 1ULL << move.To;
TBB occupation, opposing;
occupation = Occupation;
opposing = Position->PM ^ occupation;
TBB newoccupation, newopposing;
TBB king;
uint64_t kingsq;
newoccupation = (occupation ^ From) | To;
newopposing = opposing & ~To;
if ((move.MoveType & 0x07) == KING)
{
king = To;
kingsq = move.To;
}
else
{
king = Kings & Position->PM;
kingsq = LSB(king);
if (move.MoveType & EP) { newopposing ^= To >> 8; newoccupation ^= To >> 8; }
}
return (((KnightDest[kingsq] & Knights) |
(GenRook(kingsq, newoccupation) & (Rooks | Queens)) |
(GenBishop(kingsq, newoccupation) & (Bishops | Queens)) |
((((king << 9) & 0xFEFEFEFEFEFEFEFEULL) | ((king << 7) & 0x7F7F7F7F7F7F7F7FULL)) & Pawns) |
(KingDest[kingsq] & Kings)) & newopposing);
}
/* Generate all pseudo-legal quiet moves */
static inline TMove* GenerateQuiets(TMove* const quiets)
{
TBB occupation, opposing;
occupation = Occupation;
opposing = occupation ^ Position->PM;
TMove* pquiets = quiets;
for (TPieceType piece = KING; piece >= KNIGHT; piece--) // generate moves from king to knight
{
// generate moves for every piece of the same type of the side to move
for (TBB pieces = BBPieces(piece) & Position->PM; pieces; pieces = ClearLSB(pieces))
{
uint64_t sq = LSB(pieces);
// for every destinations on a free square generate a move
for (TBB destinations = ~occupation & BBDestinations(piece, sq, occupation); destinations; destinations = ClearLSB(destinations))
{
pquiets->MoveType = piece;
pquiets->From = sq;
pquiets->To = LSB(destinations);
pquiets->Prom = EMPTY;
pquiets++;
}
}
}
/* one pawns push */
TBB push1 = (((Pawns & Position->PM) << 8) & ~occupation) & 0x00FFFFFFFFFFFFFFULL;
for (TBB pieces = push1; pieces; pieces = ClearLSB(pieces))
{
pquiets->MoveType = PAWN;
pquiets->To = LSB(pieces);
pquiets->From = pquiets->To - 8;
pquiets->Prom = EMPTY;
pquiets++;
}
/* double pawns pushes */
for (TBB push2 = (push1 << 8) & ~occupation & 0x00000000FF000000ULL; push2; push2 = ClearLSB(push2))
{
pquiets->MoveType = PAWN;
pquiets->To = LSB(push2);
pquiets->From = pquiets->To - 16;
pquiets->Prom = EMPTY;
pquiets++;
}
/* check if long castling is possible */
if (CastleLM && !(occupation & 0x0EULL))
{
TBB roo, bis;
roo = ExtractLSB(0x1010101010101000ULL & occupation); /* column e */
roo |= ExtractLSB(0x0808080808080800ULL & occupation); /*column d */
roo |= ExtractLSB(0x0404040404040400ULL & occupation); /*column c */
roo |= ExtractLSB(0x00000000000000E0ULL & occupation); /* row 1 */
bis = ExtractLSB(0x0000000102040800ULL & occupation); /*antidiag from e1/e8 */
bis |= ExtractLSB(0x0000000001020400ULL & occupation); /*antidiag from d1/d8 */
bis |= ExtractLSB(0x0000000000010200ULL & occupation); /*antidiag from c1/c8 */
bis |= ExtractLSB(0x0000000080402000ULL & occupation); /*diag from e1/e8 */
bis |= ExtractLSB(0x0000008040201000ULL & occupation); /*diag from d1/d8 */
bis |= ExtractLSB(0x0000804020100800ULL & occupation); /*diag from c1/c8 */
if (!(((roo & (Rooks | Queens)) | (bis & (Bishops | Queens)) | (0x00000000003E7700ULL & Knights) |
(0x0000000000003E00ULL & Pawns) | (Kings & 0x0000000000000600ULL)) & opposing))
{ /* check if c1/c8 d1/d8 e1/e8 are not attacked */
pquiets->MoveType = KING | CASTLE;
pquiets->From = 4;
pquiets->To = 2;
pquiets->Prom = EMPTY;
pquiets++;
}
}
/* check if short castling is possible */
if (CastleSM && !(occupation & 0x60ULL))
{
TBB roo, bis;
roo = ExtractLSB(0x1010101010101000ULL & occupation); /* column e */
roo |= ExtractLSB(0x2020202020202000ULL & occupation); /* column f */
roo |= ExtractLSB(0x4040404040404000ULL & occupation); /* column g */
roo |= 1ULL << MSB(0x000000000000000FULL & (occupation | 0x1ULL));/* row 1 */
bis = ExtractLSB(0x0000000102040800ULL & occupation); /* antidiag from e1/e8 */
bis |= ExtractLSB(0x0000010204081000ULL & occupation); /*antidiag from f1/f8 */
bis |= ExtractLSB(0x0001020408102000ULL & occupation); /*antidiag from g1/g8 */
bis |= ExtractLSB(0x0000000080402000ULL & occupation); /*diag from e1/e8 */
bis |= ExtractLSB(0x0000000000804000ULL & occupation); /*diag from f1/f8 */
bis |= 0x0000000000008000ULL; /*diag from g1/g8 */
if (!(((roo & (Rooks | Queens)) | (bis & (Bishops | Queens)) | (0x0000000000F8DC00ULL & Knights) |
(0x000000000000F800ULL & Pawns) | (Kings & 0x0000000000004000ULL)) & opposing))
{ /* check if e1/e8 f1/f8 g1/g8 are not attacked */
pquiets->MoveType = KING | CASTLE;
pquiets->From = 4;
pquiets->To = 6;
pquiets->Prom = EMPTY;
pquiets++;
}
}
return pquiets;
}
/* Generate all pseudo-legal capture and promotions */
static inline TMoveEval* GenerateCapture(TMoveEval* const capture)
{
TBB opposing, occupation;
occupation = Occupation;
opposing = Position->PM ^ occupation;
TMoveEval* pcapture = capture;
for (TPieceType piece = KING; piece >= KNIGHT; piece--) // generate moves from king to knight
{
// generate moves for every piece of the same type of the side to move
for (TBB pieces = BBPieces(piece) & Position->PM; pieces; pieces = ClearLSB(pieces))
{
uint64_t sq = LSB(pieces);
// for every destinations on an opponent pieces generate a move
for (TBB destinations = opposing & BBDestinations(piece, sq, occupation); destinations; destinations = ClearLSB(destinations))
{
pcapture->Move.MoveType = piece | CAPTURE;
pcapture->Move.From = sq;
pcapture->Move.To = LSB(destinations);
pcapture->Move.Prom = EMPTY;
//pcapture->Eval = (Piece(LSB(destinations))<<4)|(KING-piece);
pcapture++;
}
}
}
/* Generate pawns right captures */
TBB pieces = Pawns & Position->PM;
for (TBB captureri = (pieces << 9) & 0x00FEFEFEFEFEFEFEULL & opposing; captureri; captureri = ClearLSB(captureri))
{
pcapture->Move.MoveType = PAWN | CAPTURE;
pcapture->Move.To = LSB(captureri);
pcapture->Move.From = pcapture->Move.To - 9;
pcapture->Move.Prom = EMPTY;
//pcapture->Eval = (Piece(LSB(captureri))<<4)|(KING-PAWN);
pcapture++;
}
/* Generate pawns left captures */
for (TBB capturele = (pieces << 7) & 0x007F7F7F7F7F7F7FULL & opposing; capturele; capturele = ClearLSB(capturele))
{
pcapture->Move.MoveType = PAWN | CAPTURE;
pcapture->Move.To = LSB(capturele);
pcapture->Move.From = pcapture->Move.To - 7;
pcapture->Move.Prom = EMPTY;
//pcapture->Eval = (Piece(LSB(capturele))<<4)|(KING-PAWN);
pcapture++;
}
/* Generate pawns promotions */
if (pieces & 0x00FF000000000000ULL)
{
/* promotions with left capture */
for (TBB promo = (pieces << 9) & 0xFE00000000000000ULL & opposing; promo; promo = ClearLSB(promo))
{
TMove move;
move.MoveType = PAWN | PROMO | CAPTURE;
move.To = LSB(promo);
move.From = move.To - 9;
move.Prom = QUEEN;
pcapture->Move = move;
//pcapture->Eval = (QUEEN<<4)|(KING-PAWN);
pcapture++;
for (TPieceType piece = ROOK; piece >= KNIGHT; piece--) /* generate underpromotions */
{
move.Prom = piece;
pcapture->Move = move;
//pcapture->Eval = piece-ROOK-1; /* keep behind the other captures-promotions */
pcapture++;
}
}
/* promotions with right capture */
for (TBB promo = (pieces << 7) & 0x7F00000000000000ULL & opposing; promo; promo = ClearLSB(promo))
{
TMove move;
move.MoveType = PAWN | PROMO | CAPTURE;
move.To = LSB(promo);
move.From = move.To - 7;
move.Prom = QUEEN;
pcapture->Move = move;
//pcapture->Eval = (QUEEN<<4)|(KING-PAWN);
pcapture++;
for (TPieceType piece = ROOK; piece >= KNIGHT; piece--) /* generate underpromotions */
{
move.Prom = piece;
pcapture->Move = move;
//pcapture->Eval = piece-ROOK-1; /* keep behind the other captures-promotions */
pcapture++;
}
}
/* no capture promotions */
for (TBB promo = ((pieces << 8) & ~occupation) & 0xFF00000000000000ULL; promo; promo = ClearLSB(promo))
{
TMove move;
move.MoveType = PAWN | PROMO;
move.To = LSB(promo);
move.From = move.To - 8;
move.Prom = QUEEN;
pcapture->Move = move;
//pcapture->Eval = (QUEEN<<4)|(KING-PAWN);
pcapture++;
for (TPieceType piece = ROOK; piece >= KNIGHT; piece--) /* generate underpromotions */
{
move.Prom = piece;
pcapture->Move = move;
//pcapture->Eval = piece-ROOK-1; /* keep behind the other captures-promotions */
pcapture++;
}
}
}
if (Position->EnPassant != 8)
{ /* Generate EnPassant captures */
for (TBB enpassant = pieces & EnPassant[Position->EnPassant]; enpassant; enpassant = ClearLSB(enpassant))
{
pcapture->Move.MoveType = PAWN | EP | CAPTURE;
pcapture->Move.From = LSB(enpassant);
pcapture->Move.To = 40 + Position->EnPassant;
pcapture->Move.Prom = EMPTY;
//pcapture->Eval = (PAWN<<4)|(KING-PAWN);
pcapture++;
}
}
return pcapture;
}
/* Make the move */
static inline void Make(TMove move)
{
Position++;
*Position = *(Position - 1); /* copy the previous position into the last one */
TBB part = 1ULL << move.From;
TBB dest = 1ULL << move.To;
switch (move.MoveType & 0x07)
{
case PAWN:
if (move.MoveType & EP)
{ /* EnPassant */
Position->PM ^= part | dest;
Position->P0 ^= part | dest;
Position->P0 ^= dest >> 8; /* delete the captured pawn */
Position->EnPassant = 8;
}
else
{
if (move.MoveType & CAPTURE)
{ /* Delete the captured piece */
Position->P0 &= ~dest;
Position->P1 &= ~dest;
Position->P2 &= ~dest;
}
if (move.MoveType & PROMO)
{
Position->PM ^= part | dest;
Position->P0 ^= part;
Position->P0 |= (TBB)(move.Prom & 1) << (move.To);
Position->P1 |= (TBB)(((move.Prom) >> 1) & 1) << (move.To);
Position->P2 |= (TBB)((move.Prom) >> 2) << (move.To);
Position->EnPassant = 8; /* clear enpassant */
}
else /* capture or push */
{
Position->PM ^= part | dest;
Position->P0 ^= part | dest;
Position->EnPassant = 8; /* clear enpassant */
if (move.To == move.From + 16 && EnPassantM[move.To & 0x07] & Pawns & (Position->PM ^ (Occupation)))
Position->EnPassant = move.To & 0x07; /* save enpassant column */
}
if (move.MoveType & CAPTURE)
{
if (move.To == 63) ResetCastleSO; /* captured the opponent king side rook */
else if (move.To == 56) ResetCastleLO; /* captured the opponent quuen side rook */
}
}
ChangeSide;
break;
case KNIGHT:
case BISHOP:
case ROOK:
case QUEEN:
if (move.MoveType & CAPTURE)
{
Position->P0 &= ~dest;
Position->P1 &= ~dest;
Position->P2 &= ~dest;
}
Position->PM ^= part | dest;
Position->P0 ^= (move.MoveType & 1) ? part | dest : 0;
Position->P1 ^= (move.MoveType & 2) ? part | dest : 0;
Position->P2 ^= (move.MoveType & 4) ? part | dest : 0;
Position->EnPassant = 8;
if ((move.MoveType & 0x7) == ROOK) /* update the castle rights */
{
if (move.From == 7) ResetCastleSM;
else if (move.From == 0) ResetCastleLM;
}
if (move.MoveType & CAPTURE) /* update the castle rights */
{
if (move.To == 63) ResetCastleSO;
else if (move.To == 56) ResetCastleLO;
}
ChangeSide;
break;
case KING:
if (move.MoveType & CAPTURE)
{
Position->P0 &= ~dest;
Position->P1 &= ~dest;
Position->P2 &= ~dest;
}
Position->PM ^= part | dest;
Position->P1 ^= part | dest;
Position->P2 ^= part | dest;
ResetCastleSM; /* update the castle rights */
ResetCastleLM;
Position->EnPassant = 8;
if (move.MoveType & CAPTURE)
{
if (CastleSO && move.To == 63) ResetCastleSO;
else if (CastleLO && move.To == 56) ResetCastleLO;
}
else if (move.MoveType & CASTLE)
{
if (move.To == 6) { Position->PM ^= 0x00000000000000A0ULL; Position->P2 ^= 0x00000000000000A0ULL; } /* short castling */
else { Position->P2 ^= 0x0000000000000009ULL; Position->PM ^= 0x0000000000000009ULL; } /* long castling */
}
ChangeSide;
default: break;
}
}
/*
Load a position starting from a fen and a list of moves.
This function doesn't check the correctness of the fen and the moves sent.
*/
static void LoadPosition(const char* fen, char* moves)
{
/* Clear the board */
Position = Game;
Position->P0 = Position->P1 = Position->P2 = Position->PM = 0;
Position->EnPassant = 8;
Position->STM = WHITE;
Position->CastleFlags = 0;
/* translate the fen to the relative position */
uint8_t pieceside = WHITE;
uint8_t piece = PAWN;
uint8_t sidetomove = WHITE;
uint64_t square = 0;
const char* cursor;
for (cursor = fen; *cursor != ' '; cursor++)
{
if (*cursor >= '1' && *cursor <= '8') square += *cursor - '0';
else if (*cursor == '/') continue;
else
{
uint64_t pos = OppSq(square);
if (*cursor == 'p') { piece = PAWN; pieceside = BLACK; }
else if (*cursor == 'n') { piece = KNIGHT; pieceside = BLACK; }
else if (*cursor == 'b') { piece = BISHOP; pieceside = BLACK; }
else if (*cursor == 'r') { piece = ROOK; pieceside = BLACK; }
else if (*cursor == 'q') { piece = QUEEN; pieceside = BLACK; }
else if (*cursor == 'k') { piece = KING; pieceside = BLACK; }
else if (*cursor == 'P') { piece = PAWN; pieceside = WHITE; }
else if (*cursor == 'N') { piece = KNIGHT; pieceside = WHITE; }
else if (*cursor == 'B') { piece = BISHOP; pieceside = WHITE; }
else if (*cursor == 'R') { piece = ROOK; pieceside = WHITE; }
else if (*cursor == 'Q') { piece = QUEEN; pieceside = WHITE; }
else if (*cursor == 'K') { piece = KING; pieceside = WHITE; }
Position->P0 |= ((uint64_t)piece & 1) << pos;
Position->P1 |= ((uint64_t)(piece >> 1) & 1) << pos;
Position->P2 |= ((uint64_t)piece >> 2) << pos;
if (pieceside == WHITE) { Position->PM |= 1ULL << pos; piece |= BLACK; }
square++;
}
}
cursor++; /* read the side to move */
if (*cursor == 'w') sidetomove = WHITE;
else if (*cursor == 'b') sidetomove = BLACK;
cursor += 2;
if (*cursor != '-') /* read the castle rights */
{
for (; *cursor != ' '; cursor++)
{
if (*cursor == 'K') Position->CastleFlags |= 0x02;
else if (*cursor == 'Q') Position->CastleFlags |= 0x01;
else if (*cursor == 'k') Position->CastleFlags |= 0x20;
else if (*cursor == 'q') Position->CastleFlags |= 0x10;
}
cursor++;
}
else cursor += 2;
if (*cursor != '-') /* read the enpassant column */
{
Position->EnPassant = *cursor - 'a';
//cursor++;
}
if (sidetomove == BLACK) ChangeSide;
}
/* Check the correctness of the move generator with the Perft function */
static int64_t Perft(int depth)
{
TMove quiets[256];
TMoveEval capture[64];
TMove move;
move.Move = 0;
int64_t tot = 0;
for (TMoveEval* pcapture = GenerateCapture(capture); pcapture > capture; pcapture--)
{
move = (pcapture - 1)->Move;
if (Illegal(move)) continue;
if (depth > 1)
{
Make(move);
tot += Perft(depth - 1);
Position--;
}
else tot++;
}
for (TMove* pquiets = GenerateQuiets(quiets); pquiets > quiets; pquiets--)
{
move = *(pquiets - 1);
if (Illegal(move)) continue;
if (depth > 1)
{
Make(move);
tot += Perft(depth - 1);
Position--;
}
else tot++;
}
return tot;
}
/* Run the Perft with this 6 test positions */
static void TestPerft(void)
{
struct {
char fen[200];
int depth;
int64_t count;
}Test[] = { {"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1",6,119060324},
{"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1",5,193690690},
{"8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1", 7,178633661},
{"r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1",6,706045033},
{"rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 6",3,53392},
{"r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10",5,164075551} };
for (unsigned int i = 0; i < (sizeof Test) / (sizeof(Test[0])); i++)
{
LoadPosition(Test[i].fen, (char*)"");
std::chrono::high_resolution_clock::time_point begin, end;
begin = std::chrono::high_resolution_clock::now();
int64_t perft = Perft(Test[i].depth);
end = std::chrono::high_resolution_clock::now();
printf("Expected: %lld Computed: %lld \r\n", Test[i].count, perft);
double t_diff = std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count();
printf("%0.3f ms passed\r\n", t_diff * 1000);
double knps = (double)Test[i].count / t_diff;
printf("%0.3f knps\r\n", knps / 1000);
printf("\r\n");
}
exit(0);
}
int main(int argc, char* argv[])
{
printf("QBB Perft in C++\r\n");
TestPerft();
return 0;
}
Code: Select all
QBB Perft in C++
Expected: 119060324 Computed: 119060324
1852.069 ms passed
64285.047 knps
Expected: 193690690 Computed: 193690690
2581.513 ms passed
75029.925 knps
Expected: 178633661 Computed: 178633661
2973.357 ms passed
60078.115 knps
Expected: 706045033 Computed: 706045033
9913.451 ms passed
71220.915 knps
Expected: 53392 Computed: 53392
0.935 ms passed
57128.183 knps
Expected: 164075551 Computed: 164075551
2221.293 ms passed
73864.891 knps