I am creating my own bitboard chess engine in C#. I am trying to optimize my make move, unmake move, and move generating functions to get a good fast base. My C# skills are average and got some tips from articles, forums and videos on how to increase performance.
If you have any advice on how I can make it faster then I would appreciate any advice highly. These functions are run millions of times due to the nature of negamax algorithm so any millisecond that can be saved will result in great increase overall.
Sorry if this is not how you do it here, and please let me know if you need any more information. The relevant code with variable declarations can be found below.
public ulong[][] pieces;
public ulong[] occupancy;
public ulong occupancyAll;
public ulong enPassant;
public ulong castling;
public int colorToMove;
public int movesCount;
public int halfMoveClock;
public int nullMoves;
public int[] PSTValuesOpening;
public int[] PSTValuesEnding;
public int currentGamePhase;
public List<int> capturedPieces;
public List<int> promotedPieces;
public List<ulong> castlings;
public List<ulong> zobristKeys;
public List<ulong> enPassants;
public List<int> halfMoveClockList;
public ulong zobristKey;
public Move[] possibleMoves;
public int movesAdded;
public string stalemateReason;
public int[] kingPositions;
public BoardState()
{
// Init bitboards
pieces = new ulong[2][];
pieces[Color.White] = new ulong[6];
pieces[Color.Black] = new ulong[6];
occupancy = new ulong[2];
// Init lists
PSTValuesOpening = new int[2];
PSTValuesEnding = new int[2];
capturedPieces = new List<int>();
promotedPieces = new List<int>();
castlings = new List<ulong>();
zobristKeys = new List<ulong>();
enPassants = new List<ulong>();
halfMoveClockList = new List<int>();
// Init other variables
currentGamePhase = 0;
kingPositions = new int[2];
}
// -----------------------------------------------------------------------------------
// ###################################################################################
// GENERATE MOVES
// ###################################################################################
// -----------------------------------------------------------------------------------
public Move[] GetAllMoves()
{
// Clear list of moves
possibleMoves = new Move[GameConstants.maxMovesInAPosition];
movesAdded = 0;
GetQuietMoves(false);
GetCaptureMoves(false);
return possibleMoves;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void AddAllTargetSquares(byte fromSquare, ulong targets, byte piece, MoveFlags flag)
{
for (; targets != 0; targets = GeneralBitOperations.PopLSB(targets))
{
AddMoveToPossibleMoves(fromSquare, (byte)GeneralBitOperations.GetLSBIndex(targets), piece, (byte)flag);
}
}
public Move[] GetQuietMoves(bool justQuiets)
{
// Clear list of moves if we should just get the quiet moves
if (justQuiets)
{
possibleMoves = new Move[GameConstants.maxMovesInAPosition];
movesAdded = 0;
}
// ##############################################################
// -------------- Go through all pieces ------------------------
// ##############################################################
byte fromSquare;
// Pawns
int direction = colorToMove == Color.White ? -8 : 8;
for (ulong pieceBB = pieces[colorToMove][Piece.Pawn]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
// Check that square is empty in front of pawn
if ((Pawns.QuietMasksOneStep[colorToMove][fromSquare] & occupancyAll) == 0)
{
// One step moves
// Check if from square is on a promoting row
if ((GameConstants.fromPromotionRows[colorToMove] & (1ul << fromSquare)) != 0)
{
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare + direction), Piece.Pawn, (byte)MoveFlags.PromotionKnight);
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare + direction), Piece.Pawn, (byte)MoveFlags.PromotionBishop);
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare + direction), Piece.Pawn, (byte)MoveFlags.PromotionRook);
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare + direction), Piece.Pawn, (byte)MoveFlags.PromotionQueen);
}
// Else a normal one step move
else
{
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare + direction), Piece.Pawn, (byte)MoveFlags.Quiet);
}
// Two step moves, if pawn is on start row and no pawns on end square
if ((GameConstants.pawnStartRow[colorToMove] & (1ul << fromSquare)) != 0)
{
if ((Pawns.QuietMasksTwoStep[colorToMove][fromSquare] & occupancyAll) == 0)
{
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare + 2 * direction), Piece.Pawn, (byte)MoveFlags.DoublePawnPush);
}
}
}
}
// Knights
for (ulong pieceBB = pieces[colorToMove][Piece.Knight]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
AddAllTargetSquares(fromSquare, Knights.AttackMasks[fromSquare] & ~occupancyAll, Piece.Knight, MoveFlags.Quiet);
}
// Bishops
for (ulong pieceBB = pieces[colorToMove][Piece.Bishop]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
AddAllTargetSquares(fromSquare, Bishops.GetAttacks(fromSquare, occupancyAll) & ~occupancyAll, Piece.Bishop, MoveFlags.Quiet);
}
// Rooks
for (ulong pieceBB = pieces[colorToMove][Piece.Rook]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
AddAllTargetSquares(fromSquare, Rooks.GetAttacks(fromSquare, occupancyAll) & ~occupancyAll, Piece.Rook, MoveFlags.Quiet);
}
// Queens
for (ulong pieceBB = pieces[colorToMove][Piece.Queen]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
AddAllTargetSquares(fromSquare, Queens.GetAttacks(fromSquare, occupancyAll) & ~occupancyAll, Piece.Queen, MoveFlags.Quiet);
}
// Kings
fromSquare = (byte)kingPositions[colorToMove];
AddAllTargetSquares(fromSquare, Kings.AttackMasks[fromSquare] & ~occupancyAll, Piece.King, MoveFlags.Quiet);
// Castling
// White side
if (colorToMove == Color.White)
{
// King side
if (Kings.WhiteCanCastleKingSide(this, colorToMove))
{
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare + 2), Piece.King, (byte)MoveFlags.Castle);
}
// Queen side
if (Kings.WhiteCanCastleQueenSide(this, colorToMove))
{
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare - 2), Piece.King, (byte)MoveFlags.Castle);
}
}
// Black side
else
{
// King side
if (Kings.BlackCanCastleKingSide(this, colorToMove))
{
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare + 2), Piece.King, (byte)MoveFlags.Castle);
}
// Queen side
if (Kings.BlackCanCastleQueenSide(this, colorToMove))
{
AddMoveToPossibleMoves(fromSquare, (byte)(fromSquare - 2), Piece.King, (byte)MoveFlags.Castle);
}
}
return possibleMoves;
}
public Move[] GetCaptureMoves(bool justCaptures)
{
// Clear list of moves if we should just get capturing moves
if (justCaptures)
{
possibleMoves = new Move[GameConstants.maxMovesInAPosition];
movesAdded = 0;
}
// ##############################################################
// -------------- Go through all pieces ------------------------
// ##############################################################
byte fromSquare;
// Pawns
for (ulong pieceBB = pieces[colorToMove][Piece.Pawn]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
ulong targets = Pawns.AttackMasks[colorToMove][fromSquare] & occupancy[Color.Invert(colorToMove)];
// Check for promotions
if ((GameConstants.fromPromotionRows[colorToMove] & (1ul << fromSquare)) != 0)
{
AddAllTargetSquares(fromSquare, targets, Piece.Pawn, MoveFlags.PromotionKnightCapture);
AddAllTargetSquares(fromSquare, targets, Piece.Pawn, MoveFlags.PromotionBishopCapture);
AddAllTargetSquares(fromSquare, targets, Piece.Pawn, MoveFlags.PromotionRookCapture);
AddAllTargetSquares(fromSquare, targets, Piece.Pawn, MoveFlags.PromotionQueenCapture);
}
else
{
AddAllTargetSquares(fromSquare, targets, Piece.Pawn, MoveFlags.Capture);
}
// Enpassant
if (enPassant != 0)
{
ulong epAttacks = Pawns.AttackMasks[colorToMove][fromSquare] & enPassant;
if (epAttacks != 0)
{
byte toSquare = (byte)GeneralBitOperations.GetLSBIndex(epAttacks);
AddMoveToPossibleMoves(fromSquare, toSquare, Piece.Pawn, (byte)MoveFlags.EnPassant);
}
}
}
// Knights
for (ulong pieceBB = pieces[colorToMove][Piece.Knight]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
AddAllTargetSquares(fromSquare, Knights.AttackMasks[fromSquare] & occupancy[Color.Invert(colorToMove)], Piece.Knight, MoveFlags.Capture);
}
// Bishops
for (ulong pieceBB = pieces[colorToMove][Piece.Bishop]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
AddAllTargetSquares(fromSquare, Bishops.GetAttacks(fromSquare, occupancyAll) & occupancy[Color.Invert(colorToMove)], Piece.Bishop, MoveFlags.Capture);
}
// Rooks
for (ulong pieceBB = pieces[colorToMove][Piece.Rook]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
AddAllTargetSquares(fromSquare, Rooks.GetAttacks(fromSquare, occupancyAll) & occupancy[Color.Invert(colorToMove)], Piece.Rook, MoveFlags.Capture);
}
// Queens
for (ulong pieceBB = pieces[colorToMove][Piece.Queen]; pieceBB != 0; pieceBB = GeneralBitOperations.PopLSB(pieceBB))
{
fromSquare = (byte)GeneralBitOperations.GetLSBIndex(pieceBB);
AddAllTargetSquares(fromSquare, Queens.GetAttacks(fromSquare, occupancyAll) & occupancy[Color.Invert(colorToMove)], Piece.Queen, MoveFlags.Capture);
}
// Kings
fromSquare = (byte)kingPositions[colorToMove];
AddAllTargetSquares(fromSquare, Kings.AttackMasks[fromSquare] & occupancy[Color.Invert(colorToMove)], Piece.King, MoveFlags.Capture);
return possibleMoves;
}
// -----------------------------------------------------------------------------------
// ###################################################################################
// MAKE AND UNMAKE MOVES
// ###################################################################################
// -----------------------------------------------------------------------------------
public bool MakeMove(Move move)
{
// Increase counters
if (colorToMove == Color.White) movesCount++;
// Add variables that can't be tracked in any other way to lists
castlings.Add(castling);
zobristKeys.Add(zobristKey);
enPassants.Add(enPassant);
halfMoveClockList.Add(halfMoveClock);
// Update king position
if (move.pieceMoved == Piece.King)
{
kingPositions[colorToMove] = move.toSquare;
}
// Increase halfmove clock, resets to 0 further down if applicable
halfMoveClock++;
// Check if enpassant is possible and if so disable it
if (enPassant != 0)
{
int enPassantRank = GeneralBitOperations.BitScan(enPassant) % 8;
zobristKey = Zobrist.ToggleEnPassant(zobristKey, enPassantRank);
enPassant = 0;
}
// ------------------------------------------------------
// Check for different move types
// ------------------------------------------------------
// Quiet moves that are not double pushes
if (MoveFunctions.IsQuiet(move.flag))
{
MovePiece(colorToMove, move.pieceMoved, move.fromSquare, move.toSquare);
zobristKey = Zobrist.MovePiece(zobristKey, colorToMove, move.pieceMoved, move.fromSquare, move.toSquare);
// Reset halfmove clock if pawn move
if (move.pieceMoved == Piece.Pawn) halfMoveClock = 0;
}
// Double pawn pushes
else if (MoveFunctions.IsDoublePawnPush(move.flag))
{
// Reset halfmove clock
halfMoveClock = 0;
// Move piece
MovePiece(colorToMove, move.pieceMoved, move.fromSquare, move.toSquare);
zobristKey = Zobrist.MovePiece(zobristKey, colorToMove, move.pieceMoved, move.fromSquare, move.toSquare);
// Enable enpassant
ulong epSquare = colorToMove == Color.White ? 1ul << move.toSquare + 8 : 1ul << move.toSquare - 8;
enPassant |= epSquare;
zobristKey = Zobrist.ToggleEnPassant(zobristKey, GeneralBitOperations.BitScan(epSquare) % 8);
}
// Enpassant moves
else if (MoveFunctions.IsEnPassant(move.flag))
{
// Find enemy pawn (which is not on the toSquare)
int enemyPieceSquare = colorToMove == Color.White ? move.toSquare + 8 : move.toSquare - 8;
int capturedPiece = Piece.Pawn;
capturedPieces.Add(capturedPiece);
// Move own pawn and remove enemy pawn
MovePiece(colorToMove, move.pieceMoved, move.fromSquare, move.toSquare);
zobristKey = Zobrist.MovePiece(zobristKey, colorToMove, move.pieceMoved, move.fromSquare, move.toSquare);
RemovePiece(Color.Invert(colorToMove), capturedPiece, enemyPieceSquare);
zobristKey = Zobrist.AddOrRemovePiece(zobristKey, Color.Invert(colorToMove), capturedPiece, enemyPieceSquare);
}
// Capture moves
else if (MoveFunctions.IsCapture(move.flag))
{
// Reset halfmove clock
halfMoveClock = 0;
// Remove captured piece from its square and add it to list of captured pieces
int capturedPiece = MoveFunctions.GetCapturedPiece(pieces[Color.Invert(colorToMove)], move.toSquare);
RemovePiece(Color.Invert(colorToMove), capturedPiece, move.toSquare);
zobristKey = Zobrist.AddOrRemovePiece(zobristKey, Color.Invert(colorToMove), capturedPiece, move.toSquare);
capturedPieces.Add(capturedPiece);
// Check for promotion captures and if so move in special way
if (MoveFunctions.IsPromotion(move.flag))
{
// Find the piece that we should promote to
int promotionPiece = GetPromotionPiece(move.flag);
// Remove pawn from square and add the promoted piece instead
RemovePiece(colorToMove, move.pieceMoved, move.fromSquare);
zobristKey = Zobrist.AddOrRemovePiece(zobristKey, colorToMove, move.pieceMoved, move.fromSquare);
AddPiece(colorToMove, promotionPiece, move.toSquare);
zobristKey = Zobrist.AddOrRemovePiece(zobristKey, colorToMove, promotionPiece, move.toSquare);
// Add to list of promoted pieces
promotedPieces.Add(promotionPiece);
}
// If not it is a normal capture
else
{
// Move the piece as normal
MovePiece(colorToMove, move.pieceMoved, move.fromSquare, move.toSquare);
zobristKey = Zobrist.MovePiece(zobristKey, colorToMove, move.pieceMoved, move.fromSquare, move.toSquare);
}
}
// Castling moves
else if (MoveFunctions.IsCastling(move.flag))
{
// Reset halfmove clock
halfMoveClock = 0;
// Get from and to square for the rook
int rookFromSquare = GameConstants.rookCastling[move.toSquare][0];
int rookToSquare = GameConstants.rookCastling[move.toSquare][1];
// Move rook and king to the correct places
MovePiece(colorToMove, Piece.King, move.fromSquare, move.toSquare);
MovePiece(colorToMove, Piece.Rook, rookFromSquare, rookToSquare);
zobristKey = Zobrist.MovePiece(zobristKey, colorToMove, Piece.King, move.fromSquare, move.toSquare);
zobristKey = Zobrist.MovePiece(zobristKey, colorToMove, Piece.Rook, rookFromSquare, rookToSquare);
}
// Normal promotion moves that are not captures
else if (MoveFunctions.IsPromotion(move.flag))
{
// Get what piece was promoted
int promotionPiece = GetPromotionPiece(move.flag);
// Remove pawn from square and add promoted piece on toSquare
RemovePiece(colorToMove, Piece.Pawn, move.fromSquare);
zobristKey = Zobrist.AddOrRemovePiece(zobristKey, colorToMove, move.pieceMoved, move.fromSquare);
AddPiece(colorToMove, promotionPiece, move.toSquare);
zobristKey = Zobrist.AddOrRemovePiece(zobristKey, colorToMove, move.pieceMoved, move.toSquare);
// Add piece to list
promotedPieces.Add(promotionPiece);
}
// If castling rights, check and remove the correct ones
if (castling != 0)
{
ulong updateMask = GameConstants.updateCastlingRights[move.fromSquare] & GameConstants.updateCastlingRights[move.toSquare];
castling &= updateMask;
zobristKey = Zobrist.AddOrRemoveCastlingRights(zobristKey, updateMask);
}
// Check if move is legal (king is not under attack after move is done)
if (!IsSquareAttacked(colorToMove, kingPositions[colorToMove]))
{
// Change turns
colorToMove = Color.Invert(colorToMove);
zobristKey = Zobrist.ChangeSide(zobristKey);
return true;
}
// If not, then unmake the move and return false
else
{
// Change turns
colorToMove = Color.Invert(colorToMove);
zobristKey = Zobrist.ChangeSide(zobristKey);
UnmakeMove(move);
return false;
}
}
public void UnmakeMove(Move move)
{
// Change turn
colorToMove = Color.Invert(colorToMove);
// Update king position
if (move.pieceMoved == Piece.King)
{
kingPositions[colorToMove] = move.fromSquare;
}
// Cache last indices
int lastIndexCaptured = capturedPieces.Count - 1;
int lastIndexPromoted = promotedPieces.Count - 1;
int lastIndexHalfMoveClock = halfMoveClockList.Count - 1;
int lastIndexZobristKeys = zobristKeys.Count - 1;
int lastIndexCastlings = castlings.Count - 1;
int lastIndexEnPassants = enPassants.Count - 1;
// Handle different move types
if (MoveFunctions.IsQuiet(move.flag) || MoveFunctions.IsDoublePawnPush(move.flag))
{
MovePiece(colorToMove, move.pieceMoved, move.toSquare, move.fromSquare);
}
else if (MoveFunctions.IsEnPassant(move.flag))
{
int enemyColor = Color.Invert(colorToMove);
int enemyPieceField = colorToMove == Color.White ? (move.toSquare + 8) : (move.toSquare - 8);
int capturedPiece = capturedPieces[lastIndexCaptured];
MovePiece(colorToMove, Piece.Pawn, move.toSquare, move.fromSquare);
AddPiece(Color.Invert(colorToMove), capturedPiece, enemyPieceField);
// Remove last captured piece directly
capturedPieces.RemoveAt(lastIndexCaptured);
}
else if (MoveFunctions.IsCapture(move.flag))
{
int enemyColor = Color.Invert(colorToMove);
int capturedPiece = capturedPieces[lastIndexCaptured];
// Capturing promotion
if (MoveFunctions.IsPromotion(move.flag))
{
int promotedPiece = promotedPieces[lastIndexPromoted];
promotedPieces.RemoveAt(lastIndexPromoted);
RemovePiece(colorToMove, promotedPiece, move.toSquare);
AddPiece(colorToMove, Piece.Pawn, move.fromSquare);
}
else
{
MovePiece(colorToMove, move.pieceMoved, move.toSquare, move.fromSquare);
}
AddPiece(enemyColor, capturedPiece, move.toSquare);
// Remove last captured piece directly
capturedPieces.RemoveAt(lastIndexCaptured);
}
else if (MoveFunctions.IsCastling(move.flag))
{
// Get from and to square for the rook
int rookFromSquare = GameConstants.rookCastling[move.toSquare][0];
int rookToSquare = GameConstants.rookCastling[move.toSquare][1];
// Move rook and king to the correct places
MovePiece(colorToMove, Piece.King, move.toSquare, move.fromSquare);
MovePiece(colorToMove, Piece.Rook, rookToSquare, rookFromSquare);
}
else if (MoveFunctions.IsPromotion(move.flag))
{
int promotedPiece = promotedPieces[lastIndexPromoted];
promotedPieces.RemoveAt(lastIndexPromoted);
RemovePiece(colorToMove, promotedPiece, move.toSquare);
AddPiece(colorToMove, Piece.Pawn, move.fromSquare);
}
// Update with latest move variables
halfMoveClock = halfMoveClockList[lastIndexHalfMoveClock];
zobristKey = zobristKeys[lastIndexZobristKeys];
castling = castlings[lastIndexCastlings];
enPassant = enPassants[lastIndexEnPassants];
// Remove from lists directly
halfMoveClockList.RemoveAt(lastIndexHalfMoveClock);
zobristKeys.RemoveAt(lastIndexZobristKeys);
castlings.RemoveAt(lastIndexCastlings);
enPassants.RemoveAt(lastIndexEnPassants);
// Decrease moves count if white to move
if (colorToMove == Color.White) movesCount--;
}
how [one does] it herethere is guidance: How do I ask a Good Question?, How to get the best value out of Code Review - Asking Questions \$\endgroup\$