C# Performance

[Richard Allbert]

the board structure and extension methods

Code: Select all

public partial class Board
{       
	public int sideToMove = Colour.Light;
	public int enPassantSqaure = Squares.OffBoard;
	public int currentSearchPly = 0;
	public int currentHalfMoveCount = 0;
	public int currentFiftyMoveRule = 0;
	public int currentCastlePermission = 0;

	// New piece list implementation
	public int[] boardPieces = new int[BoardConstants.BoardSquareCount];
	public int[] pceLst = new int[BoardConstants.PieceListMaxSize];
	public int[] pceCount = new int[Pieces.PieceTotal];

	public Board()
	{
		this.ClearBoard();
	}     
}	

#region Add piece to board


	public static void AddPieceToBoard(this Board board, int pce, int square)
	{
		board.boardPieces[square] = pce;
		AddPieceToList(board, pce, square);
	}

	public static void AddPieceToList(Board board, int pce, int square)
	{
	 
		int newIndex = board.pceCount[pce] + BoardConstants.StartIndex[pce];

		board.pceLst[newIndex] = square;
		board.pceCount[pce]++;
	}        

	#endregion

	#region remove Piece from board

	public static void RemovePieceFromBoard(this Board board, int square)
	{
	  
		RemoveFromPieceList(board, board.GetPiece(square), square);
		board.boardPieces[square] = Pieces.NoPiece;
	}

	private static void RemoveFromPieceList(Board board, int pce, int square)
	{
	 
		int start = BoardConstants.StartIndex[pce];
		int end = (start + board.pceCount[pce]) - 1;
		int index = start;
		for &#40;index = start; index <= end; ++index&#41;
		&#123;
			if &#40;board.pceLst&#91;index&#93; == square&#41; break;
		&#125;

		if &#40;index != end&#41;
		&#123;
			board.pceLst&#91;index&#93; = board.pceLst&#91;end&#93;;
		&#125;

		board.pceLst&#91;end&#93; = Squares.OffBoard;
		board.pceCount&#91;pce&#93;--;
	&#125;

	#endregion

	#region move Piece on board

	public static void MovePieceOnBoard&#40;this Board board, int fromsq, int tosq&#41;
	&#123;
	 
		MovePieceOnList&#40;board, board.GetPiece&#40;fromsq&#41;, fromsq, tosq&#41;;
		
		board.boardPieces&#91;tosq&#93; = board.GetPiece&#40;fromsq&#41;;
		board.boardPieces&#91;fromsq&#93; = Pieces.NoPiece;

	&#125;

	private static void MovePieceOnList&#40;Board board, int pce, int fromsq, int tosq&#41;
	&#123;         
		int start = BoardConstants.StartIndex&#91;pce&#93;;
		int end = &#40;start + board.pceCount&#91;pce&#93;) - 1;

		int index = start;
		for &#40;index = start; index <= end; ++index&#41;
		&#123;
			if &#40;board.pceLst&#91;index&#93; == fromsq&#41;
			&#123;
				board.pceLst&#91;index&#93; = tosq;
			&#125;
		&#125;
	&#125;       

	#endregion

	#region get piece, square

	public static int GetPiece&#40;this Board board, int sq&#41;
	&#123;
		return board.boardPieces&#91;sq&#93;;
	&#125;

	public static int GetSquare&#40;this Board board, int pceIndex&#41;
	&#123;
		return board.pceLst&#91;pceIndex&#93;;
	&#125;

	#endregion

and that's pretty much it!

Thanks for the help and interest

Richard

[Richard Allbert]

Uh oh,

Just had a thought as to what will be a major cause of slow down.

In the move generator, when generating sliding and non sliding moves, arguments such as Pieces.BDirections are arrays.

If I don't specify to pass by reference using the ref keyword, these will be copied into the function, I think. Ouch.

If so, that will be a big slow down.

I'm not at my PC now, but will test this asap.

Richard

[gladius]

The reference to the array is passed by value when using no modifiers.

The array lives on the heap, and can't be passed by value, so you are safe

[Richard Allbert]

Yes, unfortunately, I just read the same on msdn

[Sven]

Hi Richard,

within AttackedByDark()/AttackedByLight() you are using an uncommon algorithm: you are going through all enemy piece lists, trying to find attacks from enemy pieces to the target square. The most common algorithm is different in that you start at the target square and watch out for enemy attacks in all directions from there, by assuming a "super piece" on the target square and taking all "outgoing" attacks of that super piece as "incoming" to the target square. That will save quite a lot of unnecessary work.

For knights and king this is not immediately obvious with your mailbox board (and in fact you might even take a hybrid approach by searching for knight and king attacks the way you do it now) but for sliders and pawns it should be a significant improvement to start at the target square since the effort for that is never bigger than the effort to find "outgoing" attacks for one queen and one pawn.

Testing for attacks to the target square of a castling rook (F1, D1, F8, D8) might even be done a tiny bit cheaper by writing specialized functions. For instance, for F1 you would only need these:
- attack by black queen or bishop on diagonals A6-E2 or G2-H3
- attack by black queen or rook on file F
- attack by black knight on D2/E3/G3/H2
- attack by black pawn on E2/G2
- attack by black king on G2 (everything else would already have been an illegal position before)
I don't know how big the speedup will be, if any, considering that castling availability is statistically rare so this code is rarely used. But at least it should be somehow measureable as long as AttackedByDark() etc. are very expensive operations.


A minor issue: MovePieceOnList(): in my opinion this function is missing a "break" for the "board.pceLst[index] == fromsq" case (fromsq should be unique in the piece list)


When making a move, you always check for "enemy king in check" immediately. This can be improved significantly by asking if the move you just made might really have been illegal. With normal pseudo-legal move generation, it is possible to restrict the set of potentially illegal moves like this:

1) check evasions,
2) king moves (including castles),
3) ep captures,
4) moves of pinned pieces (or weaker: moves of potentially pinned pieces).

Only these need the expensive "enemy king in check" test, other moves are legal unless you do something very extraordinary in move generation (which I am sure you don't do after looking into the code you posted). I made this proposal (which I did not invent, of course!) recently in a different thread opened by Folkert van Heusden.

In another recent thread I mentioned that checking for attacks to E1/E8 twice per color within castling move generation can be avoided, i.e. reduced to doing it only once per color, e.g. by introducing some "wereAttacksToE8Tested" flag. When maintaining an inCheck flag which is set at the top of each node (you'll do this anyway in regular search so why not in perft?), the whole "attacks to E1/E8" check can be skipped and replaced by testing the inCheck flag before generating castle moves.


As my last point, your piece list handling looks expensive to me. For instance, RemoveFromPieceList() loops through the list until it finds the slot to be removed. What if you spend a bit more of memory and store the piece list index for each square? This lets you find the right slot for Remove() immediately. Restoring a captured piece's square in the piece list when unmaking a capture move can be improved the same way if you additionally store the piece list index of the captured piece together with other "undo move" related information, like the captured piece type. You can then reinsert the square into the right slot by moving back the square that is currently in that slot beyond the current end of the list (where it came from, since you are unmaking a capture move where you had moved the square from the "end" position to the now empty slot!).

I don't know how much of a speed improvement you will get by implementing that last point about piece lists, which is also the reason why I mention it at the bottom of my post.

Sven

[tttony]

Richard Allbert

Do you have the source to public??

[Richard Allbert]

Hi Sven,

Thanks for the suggestions. In the square attacked testing, I use a pre filled array to check whether a piece is on a diagonal/file/rank
that can attack the king, with the approprtiate bit set for the diagonals/ranks/files. If the bit is set, then I loop to see
if the piece has a clear attack.

Anyway, I tested again from the the r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 position on a spare computer,
to try to keep some stability in the results. The only change I made from the original post was adding the break; you pointed out for MovePieceOnList()

Using total nodes rather than leaf nodes, running perft(5) gave:

1917 knps
2024 knps
1958 knps
2095 knps

1999 knps Average.

[Richard Allbert]

Next I changed the SqIsAttackedBySide() for sliding pieces as follows

Code: Select all

private static bool SlideAttack(Board board, int sqAttacked, int dir, int EnemyColour)
{
	int currSq = sqAttacked + dir;
	int pce = Pieces.NoPiece;

	while ((currSq & 0x88) == 0)
	{
		pce = board.GetPiece(currSq);
		if (pce != Pieces.NoPiece)
		{
			if (Pieces.PieceColourIs(pce) == EnemyColour)
			{
				if (Pieces.PieceSlidesDiag(pce) == true) return true;
			}
			return false;
		}
		currSq += dir;
	}
	return false;
}

private static bool HorizVertAttack(Board board, int sqAttacked, int dir, int EnemyColour)
{
	int currSq = sqAttacked + dir;
	int pce = Pieces.NoPiece;

	while ((currSq & 0x88) == 0)
	{
		pce = board.GetPiece(currSq);
		if (pce != Pieces.NoPiece)
		{
			if (Pieces.PieceColourIs(pce) == EnemyColour)
			{
				if (Pieces.PieceSlidesHorizVert(pce) == true) return true;
			}
			return false;
		}
		currSq += dir;
	}
	return false;
}

And in the AttackedByDark / Light functions,

Code: Select all

// Diagonal
pceStartIndex = 0;
inc = Pieces.BDirections[pceStartIndex++];
while (inc != 0)
{
	if (SlideAttack(board, sq, inc, Colour.Dark) == true) return true;
	inc = Pieces.BDirections[pceStartIndex++];
}

// Horizontal
pceStartIndex = 0;
inc = Pieces.RDirections[pceStartIndex];
while (inc != 0)
{
	if (HorizVertAttack(board, sq, inc, Colour.Dark) == true) return true;
	inc = Pieces.RDirections[pceStartIndex++];
}

PieceSlidesHorizVert(pce) is simple a lookup into an array of true / false values indexed by piece. Same applies for all Pieces.PieceIsSomething(pce).

The results were then:

1825 knps
1802 knps
1799 knps
1793 knps

1804 knps avg

[Richard Allbert]

Then I reset to the original SqIsAttackedBySide(), and changed the Pawn and Knight attacks, removing the piece loop

Code: Select all

 // bP
attackersSq = sq + Squares.dirNE;
if (  ( (attackersSq & 0x88) == 0) && (board.GetPiece(attackersSq) == Pieces.bP))
	return true;
attackersSq = sq + Squares.dirNW;
if (((attackersSq & 0x88) == 0) && (board.GetPiece(attackersSq) == Pieces.bP))
	return true;

// bN

pceStartIndex = 0;
inc = Pieces.NDirections[pceStartIndex++];
attackersSq = sq + inc;
while (inc != 0)
{
	if (((attackersSq & 0x88) == 0) && (board.GetPiece(attackersSq) == Pieces.bN)) return true;
	inc = Pieces.NDirections[pceStartIndex++];
	attackersSq = sq + inc;
}

Results were:

2011 knps
2039 knps
1998 knps
2015 knps

2016 knps avg

[Richard Allbert]

Now a combination of all so the attacked function looks like so:

Code: Select all

private static bool AttackedByLight(int sq, Board board)
{
	int pceStartIndex = 0;
	int deltaFromTo = 0;
	int attackersSq = 0;
	int defSq = 0;
	int inc = 0;

	// wP
	attackersSq = sq + Squares.dirSE;
	if (((attackersSq & 0x88) == 0) && (board.GetPiece(attackersSq) == Pieces.wP))
		return true;
	attackersSq = sq + Squares.dirSW;
	if (((attackersSq & 0x88) == 0) && (board.GetPiece(attackersSq) == Pieces.wP))
		return true;

	// wN

	pceStartIndex = 0;
	inc = Pieces.NDirections[pceStartIndex++];
	attackersSq = sq + inc;
	while (inc != 0)
	{
		if (((attackersSq & 0x88) == 0) && (board.GetPiece(attackersSq) == Pieces.wN)) return true;
		inc = Pieces.NDirections[pceStartIndex++];
		attackersSq = sq + inc;
	}

	// Diagonal
	pceStartIndex = 0;
	inc = Pieces.BDirections[pceStartIndex++];
	while (inc != 0)
	{
		if (SlideAttack(board, sq, inc, Colour.Light) == true) return true;
		inc = Pieces.BDirections[pceStartIndex++];
	}

	// Horizontal
	pceStartIndex = 0;
	inc = Pieces.RDirections[pceStartIndex];
	while (inc != 0)
	{
		if (HorizVertAttack(board, sq, inc, Colour.Light) == true) return true;
		inc = Pieces.RDirections[pceStartIndex++];
	}           

	// wK Assumes one present
	pceStartIndex = BoardConstants.StartIndex[Pieces.wK];
	attackersSq = board.pceLst[pceStartIndex];

	Debug.Assert(attackersSq != Squares.OffBoard);

	deltaFromTo = sq - attackersSq;
	if ((AttackConstants.AttackBitArray[deltaFromTo + AttackConstants.DeltaShift] & AttackConstants.K_Bit) != 0)
	{
		return true;
	}

	return false;
}

Results were:

1881 knps
1726 knps
1791 knps
1818 knps

1804 knps avg

I'll now look at variations on the piece lists, I agree with your point of view. It stemmed from trying to flatten the multi dimensional array,
but your suggestion would involve a lot less looping.

However, it will take me a little longer to implement this as it's quite a major change, so I may not have results today.

Thanks for your help!

mfg

Richard