Page 1 of 1
What is (in your oppinion) the best check validation method?
Posted: Mon Feb 24, 2014 3:56 am
by goodgame0111
I'm currently writing a chess engine, and have been trying to optimize the move generation before I got into the more complicated bits. I'm using bitboards with a piece lookup by square table. For check validation, I'm waiting until after the move has been made, then looking at the attacks on the king (well, the attacks from the kings square, then intersecting with potential attackers). I'm pretty sure this is the easiest method, but it's also the slowest function in my engine (when running perft tests).
What are considered the better alternatives? I've been looking at attack tables, but it seems like that will generate more information than I need. I've also have read that you can track pins on the king, but how many pins would you have to track? Theoretically I would assume it to be 8 possible pins? And on the pin method, what would you do if the king moves? Surely you don't track pins on all possible squares for the king to move to.
Before I write something, I'd like to hear what you guys have to say on the subject.
Thanks.
Re: What is (in your oppinion) the best check validation met
Posted: Mon Feb 24, 2014 7:49 pm
by User923005
It is theoretically possible to have 9 queens, 2 bishops, 2 rooks and 2 knights.
You can update all the pin data during make move/unmake move.
You can precalculate every operation you will need to perform, assuming you use bitmaps.
You can also track battery when you have more than one slider on a ray in the same way.
Question:
Is your engine a bitboard engine or array based?
Re: What is (in your oppinion) the best check validation met
Posted: Tue Feb 25, 2014 2:35 am
by goodgame0111
I'm using magic bitboards at the moment, but I am keeping a piece array for lookups based on square. It's at least theoretically possiblre to have more than 2 bishops/knights/rooks as well, but still only 15 pieces total, which is a definite improvement. I'll take a look into this.
Re: What is (in your oppinion) the best check validation met
Posted: Tue Feb 25, 2014 3:54 am
by hyatt
goodgame0111 wrote:I'm using magic bitboards at the moment, but I am keeping a piece array for lookups based on square. It's at least theoretically possiblre to have more than 2 bishops/knights/rooks as well, but still only 15 pieces total, which is a definite improvement. I'll take a look into this.
The so-called "super-piece" method seems simplest and is what I use. generate bishop attacks from the king square and intersect this bitmap with the opponent bishops/queens. Non-zero = in check. Repeat for rook attacks and opponent rooks/queens. Then knights and pawns are straightforward. I don't know that there is anything faster. Trying to incrementally update this stuff has always been bad for those that tried it (ala' the old Slate/Atkin chess 4.x book chapter). With magic bit boards, it is far faster to generate a new set of attacks than to incrementally update stuff that is not used all the time.
Re: What is (in your oppinion) the best check validation met
Posted: Tue Feb 25, 2014 7:41 am
by ThinkingALot
I think the simplest way is just to call evaluation function for every node. You'd need that anyway for futility pruning.
Re: What is (in your oppinion) the best check validation met
Posted: Tue Feb 25, 2014 6:42 pm
by goodgame0111
hyatt wrote:The so-called "super-piece" method seems simplest and is what I use. generate bishop attacks from the king square and intersect this bitmap with the opponent bishops/queens. Non-zero = in check. Repeat for rook attacks and opponent rooks/queens. Then knights and pawns are straightforward. I don't know that there is anything faster. Trying to incrementally update this stuff has always been bad for those that tried it (ala' the old Slate/Atkin chess 4.x book chapter). With magic bit boards, it is far faster to generate a new set of attacks than to incrementally update stuff that is not used all the time.
This is actually what I'm doing right now, however my board_in_check function is still by a wide margin the slowest function in my engine. Maybe I'm calling it too much (it's also needed for board_valid_check_moves). I've pasted the board_in_check function below.
Code: Select all
int board_in_check(board_t *board, int color) {
bitboard_t combined = board->bitboards[BOARD_COMBINED];
square_t square = magic_get_bit_index(board->bitboards[make_piece(BOARD_KING, color)]); // actually using the
bitboard_t moves;
bitboard_t rook_moves = magic_get_rook_moves(square, combined);
bitboard_t bishop_moves = magic_get_bishop_moves(square, combined);
bitboard_t attackers = (rook_moves & board->bitboards[make_piece(BOARD_ROOK, !color)])|
(bishop_moves & board->bitboards[make_piece(BOARD_BISHOP, !color)])|
((rook_moves|bishop_moves) & board->bitboards[make_piece(BOARD_QUEEN, !color)])|
(magic_get_knight_moves(square) & board->bitboards[make_piece(BOARD_KNIGHT, !color)])|
(magic_get_pawn_moves(square, combined, color) & board->bitboards[make_piece(BOARD_PAWN, !color)]);
if (attackers)
return 1;
return 0;
}
Here's the output from gprof (a performance profiler):
Code: Select all
% cumulative self self total
time seconds seconds calls s/call s/call name
48.14 17.57 17.57 494850364 0.00 0.00 board_in_check
16.01 23.41 5.84 464829466 0.00 0.00 board_set_piece
14.37 28.65 5.24 232411964 0.00 0.00 board_move
9.70 32.19 3.54 5072213 0.00 0.00 board_enumerate_moves
6.14 34.43 2.24 1 2.24 36.13 run_test
3.44 35.69 1.26 808313466 0.00 0.00 magic_get_bit_index
1.10 36.09 0.40 232411964 0.00 0.00 board_copy
This is why I'm planning to do an incremental update. I haven't yet implemented anything, so we'll see how much it helps. As I said, maybe I'm just calling it too much. (Also, I'm pretty surprised to see board_set_piece on there - that's new... I'll have to look into that, but that's besides the point.)
Any advice on how I would get these numbers would be greatly appreciated. I'm doing a make move first, then I determine check for myself (make sure I'm not in check), then I determine check for the opponent (which is only sometimes needed, but it's looked at via a boolean so I always update it inside of board_move.)
Thanks for the answers so far!
Re: What is (in your oppinion) the best check validation met
Posted: Tue Feb 25, 2014 11:11 pm
by HumbleProgrammer
A move generator that I wrote in Java has a special-purpose "test move" function that makes just enough of the move to allow bitboard attacks to be computed. It doesn't change the player, full/half move clocks, castling privileges, or Zobrist hash: all it does is update the piece bitmaps so that occlusion tests are correct. Even pawn promotions are ignored--the pawn is simply left on the first/last rank--because the opponent's attacks don't care what kind of piece is on a square, merely that the square is occupied. I found it more efficient to have a "Board" object that has both an array of squares and an array of bitboards, both of which are updated during normal "make move"/"undo move" processing. For check testing, though, the bitboards array is copied and updated by the "test move" function...then discarded once the KIng's status is established.
Just another thought...
Cheers!
Humble Programmer
,,,^..^,,,
Re: What is (in your oppinion) the best check validation met
Posted: Wed Feb 26, 2014 12:25 am
by goodgame0111
HumbleProgrammer wrote:A move generator that I wrote in Java has a special-purpose "test move" function that makes just enough of the move to allow bitboard attacks to be computed. It doesn't change the player, full/half move clocks, castling privileges, or Zobrist hash: all it does is update the piece bitmaps so that occlusion tests are correct.
That's another good idea. In fact, I'm using something very similar in checking valid castle moves I make a (I call it a) "simple move" with the king, see if he's in check, do it once more, see if he's in check, then I know about checks (still some work to do, though). I never thought about doing exactly the same thing at the beginning of the "real move" function. Also, that has the benefit of being easy to implement. Thanks for the suggestion.
Re: What is (in your oppinion) the best check validation met
Posted: Wed Feb 26, 2014 7:01 pm
by hyatt
goodgame0111 wrote:hyatt wrote:The so-called "super-piece" method seems simplest and is what I use. generate bishop attacks from the king square and intersect this bitmap with the opponent bishops/queens. Non-zero = in check. Repeat for rook attacks and opponent rooks/queens. Then knights and pawns are straightforward. I don't know that there is anything faster. Trying to incrementally update this stuff has always been bad for those that tried it (ala' the old Slate/Atkin chess 4.x book chapter). With magic bit boards, it is far faster to generate a new set of attacks than to incrementally update stuff that is not used all the time.
This is actually what I'm doing right now, however my board_in_check function is still by a wide margin the slowest function in my engine. Maybe I'm calling it too much (it's also needed for board_valid_check_moves). I've pasted the board_in_check function below.
Code: Select all
int board_in_check(board_t *board, int color) {
bitboard_t combined = board->bitboards[BOARD_COMBINED];
square_t square = magic_get_bit_index(board->bitboards[make_piece(BOARD_KING, color)]); // actually using the
bitboard_t moves;
bitboard_t rook_moves = magic_get_rook_moves(square, combined);
bitboard_t bishop_moves = magic_get_bishop_moves(square, combined);
bitboard_t attackers = (rook_moves & board->bitboards[make_piece(BOARD_ROOK, !color)])|
(bishop_moves & board->bitboards[make_piece(BOARD_BISHOP, !color)])|
((rook_moves|bishop_moves) & board->bitboards[make_piece(BOARD_QUEEN, !color)])|
(magic_get_knight_moves(square) & board->bitboards[make_piece(BOARD_KNIGHT, !color)])|
(magic_get_pawn_moves(square, combined, color) & board->bitboards[make_piece(BOARD_PAWN, !color)]);
if (attackers)
return 1;
return 0;
}
Here's the output from gprof (a performance profiler):
Code: Select all
% cumulative self self total
time seconds seconds calls s/call s/call name
48.14 17.57 17.57 494850364 0.00 0.00 board_in_check
16.01 23.41 5.84 464829466 0.00 0.00 board_set_piece
14.37 28.65 5.24 232411964 0.00 0.00 board_move
9.70 32.19 3.54 5072213 0.00 0.00 board_enumerate_moves
6.14 34.43 2.24 1 2.24 36.13 run_test
3.44 35.69 1.26 808313466 0.00 0.00 magic_get_bit_index
1.10 36.09 0.40 232411964 0.00 0.00 board_copy
This is why I'm planning to do an incremental update. I haven't yet implemented anything, so we'll see how much it helps. As I said, maybe I'm just calling it too much. (Also, I'm pretty surprised to see board_set_piece on there - that's new... I'll have to look into that, but that's besides the point.)
Any advice on how I would get these numbers would be greatly appreciated. I'm doing a make move first, then I determine check for myself (make sure I'm not in check), then I determine check for the opponent (which is only sometimes needed, but it's looked at via a boolean so I always update it inside of board_move.)
Thanks for the answers so far!
There's an optimization that will cut that by about 50% for the positions where you are in check.
check each piece type individually and return on the first attack.
I do it like this:
if (rook_attacks & (opponent rooks or queens)) return 1;
if (bishop_attacks & (opponent bishops or queens)) return 1;
if (knight_attacks & opponent knights) return 1;
if (pawn_attacks & opponent pawns) return 1;
return 0.
I don't think that is going to help a lot however, because most of the time you are not in check. Next question is where do you call that from? I do NOT use the in check function in the q-search. Instead, I go to the next ply, capture the king, return and reject that move as illegal. Since most moves are legal, this gets rid of the q-search check calls completely if all you are doing is captures...
That is a BIG savings.
Re: What is (in your oppinion) the best check validation met
Posted: Wed Aug 20, 2014 2:10 pm
by aiavicoli
I know a faster way, based on the same idea.
I found the idea of starting from King and looking backward for piece is a good idea because is fast and easy to develop. That is our base.
However, you don't need to call the routine at any move but only for those moves that potentially can leave your king in check. Bitboard or not.
I'll try to explain better.
In my move generator I keep a flag that tell me if I have to perform a check-validator. Every move has it's flag that I set/unset according to those rules:
If the king is currently in check, then perform the validation to all move, overriding any of the following rules.
While I generate my rook moves, if the rook is neither on the same rank nor on same file of the king then there's no need to validate that move.
If the rook is on the same rank and I'm movin my rook in another square of the same rank than there's no need to validate that move.
The same for file: if the rook is on the same file of my king but the target square is also on the same file then there's no need to validate that move.
This works also for queen moves on ranks and files.
For the bishop's moves, there's no need to validate if neither diagonal nor anti-diagonal of the bishop is not the same diagonal / anti-diagonal of the king.
When bishop and king are on the same diagonal, but the bishop target square is on the same diagonal, there's no need to validate the move.
Again, same for anti-diagonal.
Same for queen moves that are likes rooks+bishops.
Validate pawn moves only if starting square is on the same rank/file/diagonal/anti-diagonal of the king.
Validate all en-passant moves and castling.
Validate all king moves.
Validate knight moves only if the starting square is on the same rank/file/diagonal/anti-diagonal of the king.
When in doubt, validate the move.
With this knowledge you should avoid some unseless check validation.
In my engine, that is array-based, this has speed up the generation of about 10% than validate all moves.