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?
in check detection: "Square attacked by" vs "Attack and defend maps"
Moderators: hgm, Rebel, chrisw
-
- Posts: 157
- Joined: Fri Apr 30, 2021 7:19 am
- Full name: Pedro Duran
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: in check detection: "Square attacked by" vs "Attack and defend maps"
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 movespedrojdm2021 wrote: ↑Wed Aug 04, 2021 7:33 pm 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?
Here is how I do it:
https://github.com/amanjpro/zahak/blob/ ... on.go#L211
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: in check detection: "Square attacked by" vs "Attack and defend maps"
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.
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.
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 157
- Joined: Fri Apr 30, 2021 7:19 am
- Full name: Pedro Duran
Re: in check detection: "Square attacked by" vs "Attack and defend maps"
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.ZirconiumX wrote: ↑Wed Aug 04, 2021 11:04 pm 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.
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;
}
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);
}
~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...
-
- Posts: 313
- Joined: Tue Aug 03, 2021 2:41 pm
- Full name: Bill Beame
Re: in check detection: "Square attacked by" vs "Attack and defend maps"
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 wrote: ↑Wed Aug 04, 2021 7:33 pm 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?
-
- Posts: 157
- Joined: Fri Apr 30, 2021 7:19 am
- Full name: Pedro Duran
Re: in check detection: "Square attacked by" vs "Attack and defend maps"
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.Chessnut1071 wrote: ↑Fri Sep 17, 2021 6:54 amThere 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 wrote: ↑Wed Aug 04, 2021 7:33 pm 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?
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