I started an engine in C# a while ago - the intention being to making it part of an XNA based game.
I've so far written the board structure and fen parsing. All in all it's in five class libraries with approx 200 unit tests. Progress has been slow, but thorough, after developing an obsession with getting unit tests to pass, and finding that I write 9 / 10 functions with bugs first time.
Also, working with very simple thread and string libraries (compared with C++) has been nice.
I was pretty pleased with progress, until I came to start move generation.
I just can't find a performance friendly way of adding moves to a list - even when declaring the list as an array of move objects, it's 5x (i.e. a lot) slower than the same thing in C++.
Are there some general tips or do's / dont's in C# when dealing with static or dynamic sizes collections of non primitive types?
Also, I've written Lot of functionality using extension methods - is this a bad idea?
Stripped down to its skeleton, the basics of the generation structure are
Code: Select all
public partial class Board
{
public BoardPieceList[] PieceList = new BoardPieceList[Pieces.PieceTotal];
public int[] boardPieces = new int[BoardConstants.BoardSquareCount];
..... }
public partial class BoardPieceList
{
List<int> pieceList;
public List<int> PieceList { get { return pieceList; } }
int lastAliveIndex; // where the last alive piece is in the list (index base is 0 here)
public int LastAliveIndex { get { return lastAliveIndex; } set { lastAliveIndex = value; } }
public const int NoPieces = -1;
// init with piece type and the list size
public BoardPieceList(int listLength)
{
Debug.Assert(listLength >= BoardExtensions.KingLength && listLength <= BoardExtensions.NormalLength);
pieceList = new List<int>(listLength);
InitList(listLength);
}
// add pieces to defined max length, and set the alive index to 0 as no pieces are alive yet, square is offboard
private void InitList(int listLength)
{
Debug.Assert(listLength >= BoardExtensions.KingLength && listLength <= BoardExtensions.NormalLength);
for (int i = 0; i < listLength; ++i)
{
pieceList.Add(Squares.OffBoard);
}
lastAliveIndex = BoardPieceList.NoPieces;
}
public void AddPiece(int sq)
{
Debug.Assert(Squares.SquareOnBoard(sq) == true);
pieceList[++LastAliveIndex] = sq;
Debug.Assert(lastAliveIndex >= 0);
Debug.Assert(lastAliveIndex < pieceList.Count);
}
public void MovePiece(int from, int to)
{
Debug.Assert(Squares.SquareOnBoard(from) == true);
Debug.Assert(Squares.SquareOnBoard(to) == true);
Debug.Assert(lastAliveIndex > BoardPieceList.NoPieces);
for (int index = LastAliveIndex; index >= 0; --index)
{
if (pieceList[index] == from)
{
pieceList[index] = to;
return;
}
}
Debug.Assert(true == false); // reaching here means we didn't find the pce we were moving
}
public void KillPiece(int sq)
{
Debug.Assert(Squares.SquareOnBoard(sq) == true);
Debug.Assert(lastAliveIndex < pieceList.Count);
Debug.Assert(lastAliveIndex > BoardPieceList.NoPieces);
for (int index = LastAliveIndex; index >= 0; --index)
{
if (pieceList[index] == sq)
{
if (index != LastAliveIndex)
{
pieceList[index] = pieceList[LastAliveIndex];
pieceList[LastAliveIndex] = Squares.OffBoard;
}
else
{
pieceList[index] = Squares.OffBoard;
}
lastAliveIndex--;
return;
}
}
Debug.Assert(true == false); // reaching here means we didn't find the pce we were killing
}
public int GetSquare(int pieceIndex)
{
Debug.Assert(pieceIndex >= 0 && pieceIndex <= lastAliveIndex);
return pieceList[pieceIndex];
}
}
public static class BoardExtensions
{
#region Get Piece List Utility
public static int KingLength = 1;
public static int PawnLength = 8;
public static int NormalLength = 10;
public static void InitPieceListArray(this Board board)
{
board.PieceList[Pieces.wP] = new BoardPieceList(PawnLength);
board.PieceList[Pieces.wN] = new BoardPieceList(NormalLength);
board.PieceList[Pieces.wB] = new BoardPieceList(NormalLength);
board.PieceList[Pieces.wR] = new BoardPieceList(NormalLength);
board.PieceList[Pieces.wQ] = new BoardPieceList(NormalLength);
board.PieceList[Pieces.wK] = new BoardPieceList(KingLength);
board.PieceList[Pieces.bP] = new BoardPieceList(PawnLength);
board.PieceList[Pieces.bN] = new BoardPieceList(NormalLength);
board.PieceList[Pieces.bB] = new BoardPieceList(NormalLength);
board.PieceList[Pieces.bR] = new BoardPieceList(NormalLength);
board.PieceList[Pieces.bQ] = new BoardPieceList(NormalLength);
board.PieceList[Pieces.bK] = new BoardPieceList(KingLength);
}
public static BoardPieceList GetPieceList(this Board board, int pce)
{
Debug.Assert(Pieces.PieceIsValid(pce) == true);
return board.PieceList[pce];
}
#endregion
#region Add piece to board
public static void AddPieceToBoard(this Board board, int pce, int square)
{
Debug.Assert(Squares.SquareOnBoard(square) == true);
Debug.Assert(Pieces.PieceIsValid(pce) == true);
board.boardPieces[square] = pce;
AddPieceToList(board, pce, square);
}
public static void AddPieceToList(Board board, int pce, int square)
{
Debug.Assert(Squares.SquareOnBoard(square) == true);
Debug.Assert(Pieces.PieceIsValid(pce) == true);
board.GetPieceList(pce).AddPiece(square);
}
#endregion
#region remove Piece from board
public static void RemovePieceFromBoard(this Board board, int square)
{
Debug.Assert(Squares.SquareOnBoard(square) == true);
Debug.Assert(Pieces.PieceIsValid(board.GetPiece(square)) == true);
RemoveFromPieceList(board, board.GetPiece(square), square);
board.boardPieces[square] = Pieces.NoPiece;
}
private static void RemoveFromPieceList(Board board, int pce, int square)
{
Debug.Assert(Squares.SquareOnBoard(square) == true);
Debug.Assert(Pieces.PieceIsValid(pce) == true);
board.GetPieceList(pce).KillPiece(square);
}
#endregion
#region move Piece on board
public static void MovePieceOnBoard(this Board board, int fromsq, int tosq)
{
Debug.Assert(Squares.SquareOnBoard(fromsq) == true);
Debug.Assert(Squares.SquareOnBoard(tosq) == true);
Debug.Assert(Pieces.PieceIsValid(board.GetPiece(fromsq)) == true);
MovePieceOnList(board, board.GetPiece(fromsq), fromsq, tosq);
board.boardPieces[tosq] = board.GetPiece(fromsq);
board.boardPieces[fromsq] = Squares.OffBoard;
}
private static void MovePieceOnList(Board board, int pce, int fromsq, int tosq)
{
Debug.Assert(Squares.SquareOnBoard(fromsq) == true);
Debug.Assert(Squares.SquareOnBoard(tosq) == true);
Debug.Assert(Pieces.PieceIsValid(pce) == true);
board.GetPieceList(pce).MovePiece(fromsq, tosq);
}
#endregion
#region get piece
public static int GetPiece(this Board board, int sq)
{
return board.boardPieces[sq];
}
#endregion
#region get piece
public static void ClearBoard(this Board board)
{
for (int i = 0; i < BoardConstants.BoardSquareCount; ++i)
{
board.boardPieces[i] = Pieces.NoPiece;
}
board.InitPieceListArray();
board.currentCastlePermission = 0;
board.currentFiftyMoveRule = 0;
board.currentHalfMoveCount = 0;
board.currentSearchPly = 0;
board.enPassantSqaure = Squares.OffBoard;
board.sideToMove = Colour.None;
}
#endregion
}
public class MoveList
{
public Move[] MoveArray = new Move[Moves.MaxMoveListMoves];
public int moveCount = 0;
}
public static class MoveListExtensions
{
public static void AddMove(this MoveList list, Move move)
{
Debug.Assert(list.moveCount < (Moves.MaxMoveListMoves - 1));
list.MoveArray[list.moveCount++] = move;
}
public static Move GetMove(this MoveList list, int index)
{
Debug.Assert(list.moveCount > index && index >= 0);
return list.MoveArray[index];
}
}
public class Move
{
public int from;
public int to;
public int promotedTo;
public int captured;
public int flag;
public Move()
{
from = Squares.OffBoard;
to = Squares.OffBoard;
promotedTo = Pieces.NoPiece;
captured = Pieces.NoPiece;
flag = Moves.FlagNone;
}
public Move(int f, int t, int pr, int ca, int fl)
{
from = f;
to = t;
promotedTo = pr;
captured = ca;
flag = fl;
}
And adding a move in generation...
fromSq = pceList.GetSquare(pceNum);
while (Pieces.MoveDirections[pce, moves] != 0)
{
toSq = Pieces.MoveDirections[pce, moves] + fromSq;
if (CanLandOrTake(board, pce, toSq) == true)
{
moveList.AddMove(new Move(fromSq, toSq, Pieces.NoPiece, board.GetPiece(toSq), Moves.FlagNone));
}
moves++;
}
As a (very unreliable) indicator, I put together the above skeleton in C++ and ran Generate on the starting position for 2000000 loops. This took just over 2s for the C++ program but over 14s for the C#.
Should I be writing all of this as unsafe code, and fixing the arrays in the memory?
Or are my feeling misplaced?
I just don't want to invest a load of time over the next few months with the hard part, only to have something well tested, extensible but dog slow.
Thanks for any tips
Richard
. Shouldn't be 10x though