in check detection: "Square attacked by" vs "Attack and defend maps"

[pedrojdm2021]

Hello again guys, i hope all of you are doing very well, in about a month ago i finished my first version of my C# chess engine, i managed to make it run at about ~800.000 NPS of AI search speed, that is a pretty decent speed, but i want more

One of the things that the DotTrace profiler that points on most heavy use is the "in_check" detection, it consist on tracing some rays from the king square to the opponent pieces based on piece type, it reuses the pre-calculated piece move bitboards that it's used for move generation, it works really great but it seems that is very expensive, that is the "square attacked by":
https://www.chessprogramming.org/Square ... ck_by_Side

that in check detection is used each time inside each negamax node, and also to validate legal moves for each make_move call. so you can imagine that is heavy use of that function

so i did some research and i found that we can "cache" the attacks on each square:
https://www.chessprogramming.org/Attack ... l_Approach

have any of you implemented that approarch? or any of you have compared it to the "square attacked by" approarch? if yes, they perform better ? or any of you know a better solution?

[amanjpro]

Hello again guys, i hope all of you are doing very well, in about a month ago i finished my first version of my C# chess engine, i managed to make it run at about ~800.000 NPS of AI search speed, that is a pretty decent speed, but i want more

One of the things that the DotTrace profiler that points on most heavy use is the "in_check" detection, it consist on tracing some rays from the king square to the opponent pieces based on piece type, it reuses the pre-calculated piece move bitboards that it's used for move generation, it works really great but it seems that is very expensive, that is the "square attacked by":
https://www.chessprogramming.org/Square ... ck_by_Side

that in check detection is used each time inside each negamax node, and also to validate legal moves for each make_move call. so you can imagine that is heavy use of that function

so i did some research and i found that we can "cache" the attacks on each square:
https://www.chessprogramming.org/Attack ... l_Approach

have any of you implemented that approarch? or any of you have compared it to the "square attacked by" approarch? if yes, they perform better ? or any of you know a better solution?

You can simply call the function once to check move legality and store the result in a variable in the position object to be reused in the negamax method... Just make sure you keep the variable properly updated during make/unmake moves


Here is how I do it:
https://github.com/amanjpro/zahak/blob/ ... on.go#L211

[ZirconiumX]

I really like attack tables, but the question is how much information you want to store in them. Dorpsgek uses a piece-set per square of the board for 256 bytes in total; HGM's mailbox trials engine uses a piece-set per piece of the board, along with other information like distance to next piece in a direction; Rookie uses a 16-bit bit-set with one bit for an attack in each direction; Rebel/Pro Deo uses an 8-bit count of attacks to square.

In terms of information density, Rookie's approach is probably best, but I like being able to look up the squares of attacking pieces in a piece list.

[pedrojdm2021]

I really like attack tables, but the question is how much information you want to store in them. Dorpsgek uses a piece-set per square of the board for 256 bytes in total; HGM's mailbox trials engine uses a piece-set per piece of the board, along with other information like distance to next piece in a direction; Rookie uses a 16-bit bit-set with one bit for an attack in each direction; Rebel/Pro Deo uses an 8-bit count of attacks to square.

In terms of information density, Rookie's approach is probably best, but I like being able to look up the squares of attacking pieces in a piece list.

Hi, sorry for the late reply after many weeks, i was so busy, i did just that, i did exactly the "Classical Approach" from chess programming wiki.

i made some early tests on the aprox. performance and the performance was much worse than the "Square attacked by"
the main reason is the need for the "update" attack maps

I was doing something like in the make move function:

Code: Select all

ulong attacks_from,attacks_to,attacks_mask;

switch(moved_piece)
{
	...
	case bishop:
	
	 attacks_from = GetBishopAttacks(sq_from, total_occupancy);
	 attacks_to = GetBishopAttacks(sq_to, total_occupancy);
	 
	 attacks_mask = attacks_from & ~attacks_to; // determinate the squares that needs to be removed
	 while(attacks_mask)
	 {
	 	// remove each bit from the attacks_mask
	 	attacks_table[getLS1BIndex(attacks_mask)] &= ~(1ul << square_from);
	 	attacks_mask = RemoveLS1B(attacks_mask);
	 }
	 
	 
	 attacks_mask = ~attacks_from & attacks_to; // determinate the squares that needs to be added
	 while(attacks_mask)
	 {
	 	// set each bit from the new wanted attacks
	 	attacks_table[getLS1BIndex(attacks_mask)] |= (1ul << square_from);
	 	attacks_mask = RemoveLS1B(attacks_mask);
	 }
	 
	
	break;
}

And i did the opposite for the UnMakeMove, the problem is that it is worse than my "SquareAttackedBy" Implementation:

Code: Select all

  [MethodImpl(MethodImplOptions.AggressiveInlining)]
  public ulong GetAttackersForSquare(byte _square, byte _player) 
  {
            byte adversary = (byte)(_player ^ 1);
            ulong op_pawns,op_knights,op_rooks,op_bishops,occ,op_queens;
            occ = bitboards[_player] | bitboards[adversary];
            op_queens = (bitboards[adversary] & bitboards[ChessPiece.Queen]);
            (op_bishops,op_rooks) = (op_queens,op_queens);
            op_bishops |= bitboards[adversary] & bitboards[ChessPiece.Bishop];
            op_rooks |= bitboards[adversary] & bitboards[ChessPiece.Rook];
            op_pawns = bitboards[adversary] & bitboards[ChessPiece.Pawn];
            op_knights = bitboards[adversary] & bitboards[ChessPiece.Knight];

            return (GetBishopMoves(_square, occ) & op_bishops) | 
                   (GetRookMoves(_square, occ) & op_rooks) |
                   (GetPawnAttacks(_square, _player) & op_pawns) |
                   (GetKnightMoves(_square) & op_knights); 
 }

The perft in startposition with SquareAttackedBy at depth of 5 (4M of moves) was:
~580ms

with that attacks map:
~980ms !!

the most branchless and loop free implementation that i've found is the "square attacked by"

or anyone else have found another idea of keeping some sort of attack maps with a good performance? i am thinking to switch to a fully legal move generator to see if speed improves so i don't need to call unamakeMove each illegal move anymore...

[Chessnut1071]

Hello again guys, i hope all of you are doing very well, in about a month ago i finished my first version of my C# chess engine, i managed to make it run at about ~800.000 NPS of AI search speed, that is a pretty decent speed, but i want more

One of the things that the DotTrace profiler that points on most heavy use is the "in_check" detection, it consist on tracing some rays from the king square to the opponent pieces based on piece type, it reuses the pre-calculated piece move bitboards that it's used for move generation, it works really great but it seems that is very expensive, that is the "square attacked by":
https://www.chessprogramming.org/Square ... ck_by_Side

that in check detection is used each time inside each negamax node, and also to validate legal moves for each make_move call. so you can imagine that is heavy use of that function

so i did some research and i found that we can "cache" the attacks on each square:
https://www.chessprogramming.org/Attack ... l_Approach

have any of you implemented that approarch? or any of you have compared it to the "square attacked by" approarch? if yes, they perform better ? or any of you know a better solution?

There is two different answers to that question, depending on your objective. The maximum information requires both. For example, if you want to calculate check, discovered check and pinned moves, you need attack tables and the check matrix pre computed. Be prepared for a significant drop in speed to include discovered check, unless you can find a very efficient algorithm that doesn't require soo much lookup.

[pedrojdm2021]

Hello again guys, i hope all of you are doing very well, in about a month ago i finished my first version of my C# chess engine, i managed to make it run at about ~800.000 NPS of AI search speed, that is a pretty decent speed, but i want more

One of the things that the DotTrace profiler that points on most heavy use is the "in_check" detection, it consist on tracing some rays from the king square to the opponent pieces based on piece type, it reuses the pre-calculated piece move bitboards that it's used for move generation, it works really great but it seems that is very expensive, that is the "square attacked by":
https://www.chessprogramming.org/Square ... ck_by_Side

that in check detection is used each time inside each negamax node, and also to validate legal moves for each make_move call. so you can imagine that is heavy use of that function

so i did some research and i found that we can "cache" the attacks on each square:
https://www.chessprogramming.org/Attack ... l_Approach

have any of you implemented that approarch? or any of you have compared it to the "square attacked by" approarch? if yes, they perform better ? or any of you know a better solution?

There is two different answers to that question, depending on your objective. The maximum information requires both. For example, if you want to calculate check, discovered check and pinned moves, you need attack tables and the check matrix pre computed. Be prepared for a significant drop in speed to include discovered check, unless you can find a very efficient algorithm that doesn't require soo much lookup.

I understand, and yes, after a lot of researching and some comparation that i did in other engines, i found that "square attacked by" seems the best approarch that delivers the maximun speed.

The square attack tables requires updates and that is much more expensive than the bitwise operations that is done with the "square attacked by" solution, and as you said, a discovered check for a legal move generator is a big slowdown, so i think i will keep the "square attacked by" implementation for check detection / square attacked.

The thing that i need to improve is the number of nodes searched in a search, my engine currently in the "kiwipete" position on depth 9 search around 2 million nodes while other engines for that depth searches only between 450.000! or even less! so that's something clearly wrong in transposition tables or negamax algorithm.

i have to say that i clearly have a lot of agressive pruning right there, i have PVS , Null move pruning, LMR, even frutility pruning, so is not lack of features