WOW. I just rewrote this part of my program, and it is now 5 times faster! Big speed improvement. Link to GitHub.Sven wrote:Calling the move generator from the opponent's view to check legality of each single move sounds like a bad idea to me. At most you need to make a move, test whether your king is in check, and unmake the move. And testing whether the king is in check can be done much faster than by generating all enemy moves (simply go to all directions from the king square).
Code: Select all
static function square_is_attacked($enemy_color, $board, $square_to_check) {
$friendly_color = self::invert_color($enemy_color);
if ( self::test_square_threatened_by_sliding_pieces($board, $square_to_check, $friendly_color) ) {
return TRUE;
}
if ( self::test_square_threatened_by_jumping_pieces($board, $square_to_check, $friendly_color) ) {
return TRUE;
}
if ( self::test_square_threatened_by_en_passant($board, $square_to_check, $friendly_color, $enemy_color) ) {
return TRUE;
}
return FALSE;
}
static function test_square_threatened_by_sliding_pieces($board, $square_to_check, $friendly_color) {
foreach ( self::ALL_DIRECTIONS as $direction ) {
for ( $i = 1; $i <= self::MAX_SLIDING_DISTANCE; $i++ ) {
$current_xy = self::DIRECTION_OFFSETS[$direction];
$rank = $square_to_check->rank + $current_xy[0] * $i;
$file = $square_to_check->file + $current_xy[1] * $i;
if ( ! self::square_is_on_board($rank, $file) ) {
// Square is off the board. Stop sliding in this direction.
break;
}
$piece = self::get_piece($rank, $file, $board);
if ( ! $piece ) {
// Square is empty. Continue sliding in this direction.
continue;
}
if ( $piece->color == $friendly_color ) {
// Sliding is blocked by a friendly piece. Stop sliding in this direction.
break;
}
// If this code is reached, piece must be an enemy. No need to double check.
// I could probably structure this to be faster, but I did it this way for readability.
if ( $piece->type == ChessPiece::KING ) {
if ( $i == 1 ) {
return TRUE;
}
} elseif ( $piece->type == ChessPiece::QUEEN ) {
if ( $direction == self::NORTH || $direction == self::SOUTH || $direction == self::EAST || $direction == self::WEST || $direction == self::NORTHEAST || $direction == self::NORTHWEST || $direction == self::SOUTHEAST || $direction == self::SOUTHWEST ) {
return TRUE;
}
} elseif ( $piece->type == ChessPiece::ROOK ) {
if ( $direction == self::NORTH || $direction == self::SOUTH || $direction == self::EAST || $direction == self::WEST ) {
return TRUE;
}
} elseif ( $piece->type == ChessPiece::BISHOP ) {
if ( $direction == self::NORTHEAST || $direction == self::NORTHWEST || $direction == self::SOUTHEAST || $direction == self::SOUTHWEST ) {
return TRUE;
}
} elseif ( $piece->type == ChessPiece::PAWN ) {
if ( $i == 1 ) {
if ( $piece->color == ChessPiece::BLACK ) {
if ( $direction == self::NORTHEAST || $direction == self::NORTHWEST ) {
return TRUE;
}
} elseif ( $piece->color == ChessPiece::WHITE ) {
if ( $direction == self::SOUTHEAST || $direction == self::SOUTHWEST ) {
return TRUE;
}
}
}
}
// If this code has been reached, then there is an enemy piece on this square
// but it is not threatening the test square. Stop sliding in this direction.
break;
}
}
return FALSE;
}
static function test_square_threatened_by_jumping_pieces($board, $square_to_check, $friendly_color) {
foreach ( self::KNIGHT_DIRECTIONS as $oclock ) {
$current_xy = self::OCLOCK_OFFSETS[$oclock];
$rank = $square_to_check->rank + $current_xy[0];
$file = $square_to_check->file + $current_xy[1];
if ( ! self::square_is_on_board($rank, $file) ) {
// Square is off the board. On to the next test square.
continue;
}
$piece = self::get_piece($rank, $file, $board);
if ( ! $piece ) {
// Square is empty. On to the next test square.
continue;
}
if ( $piece->color == $friendly_color ) {
// Square is occupied by a friendly piece. On to the next test square.
continue;
}
// If this code is reached, piece must be an enemy. No need to double check.
if ( $piece->type == ChessPiece::KNIGHT ) {
return TRUE;
}
// If this code has been reached, then there is an enemy piece on this square
// but it is not threatening the test square. On to the next square.
// continue;
}
return FALSE;
}
static function test_square_threatened_by_en_passant($board, $square_to_check, $friendly_color, $enemy_color) {
// Is there an en passant target square?
if ( ! $board->en_passant_target_square ) {
return FALSE;
}
// Does our square to check contain a pawn? (Only pawns can be captured en passant)
$piece_on_square_to_check = self::get_piece($square_to_check->rank, $square_to_check->file, $board);
if ( ! $piece_on_square_to_check ) {
// Sometimes our square to check will contain nothing.
// For example, when checking squares between the rook and king before castling.
return FALSE;
}
if ( ! $piece_on_square_to_check->type == ChessPiece::PAWN ) {
return FALSE;
}
// Is test square next to the en passant target square? Only one square north/south
// of the en passant target square can be threatened.
if ( $friendly_color == ChessPiece::WHITE ) {
$test_square_to_target_square_direction = self::SOUTH;
} elseif ( $friendly_color == ChessPiece::BLACK ) {
$test_square_to_target_square_direction = self::NORTH;
}
$current_xy = self::DIRECTION_OFFSETS[$test_square_to_target_square_direction];
$rank = $square_to_check->rank + $current_xy[0];
$file = $square_to_check->file + $current_xy[1];
if ( ! self::square_is_on_board($rank, $file) ) {
// Potential en passant target square isn't even on the board. Can't be en passant.
return FALSE;
}
$ep_target_square_rank = $board->en_passant_target_square->rank;
$ep_target_square_file = $board->en_passant_target_square->file;
if ( $board->en_passant_target_square->rank != $rank && $board->en_passant_target_square->file != $file ) {
return FALSE;
}
// Finally, is there an enemy pawn to the east or west of our pawn?
// If so, we are threatened by en passant!
$enemy_pawn_directions = array(self::EAST, self::WEST);
foreach ( $enemy_pawn_directions as $direction ) {
$current_xy = self::DIRECTION_OFFSETS[$direction];
$rank = $square_to_check->rank + $current_xy[0];
$file = $square_to_check->file + $current_xy[1];
if ( ! self::square_is_on_board($rank, $file) ) {
// Square is off the board. On to the next check.
break;
}
$piece = self::get_piece($rank, $file, $board);
if ( ! $piece ) {
// Square is empty. On to the next check.
continue;
}
if ( $piece->color == $enemy_color && $piece->type == ChessPiece::PAWN ) {
return TRUE;
}
}
return FALSE;
}
static function square_is_on_board($rank, $file) {
if ( $rank >= 1 && $rank <= 8 && $file >= 1 && $file <= 8 ) {
return TRUE;
} else {
return FALSE;
}
}
static function get_piece($rank, $file, $board) {
if ( $board->board[$rank][$file] ) {
return $board->board[$rank][$file];
} else {
return NULL;
}
}If you have additional ideas to speed up the code or additional feedback, I am happy to hear it. Thanks again for all your help!