//
// movegen.hpp
// fornax3
//
// Created by Anders on 17/12/2020.
//
#ifndef movegen_hpp
#define movegen_hpp
#include <assert.h>
#include <stdio.h>
#include "../board.h"
#include "../bits.h"
#include "../move.h"
#include "oracle.hpp"
template<direction dir>
static constexpr bits64 movegen_find_muggles(bits64 bits) {
switch (dir) {
case N: case E: case NW: case NE:
return oracle_get_slide<dir>(bits_get_trailing(bits | BB_MSB));
case W: case SW: case S: case SE: {
return oracle_get_slide<dir>(bits_get_leading(bits | BB_LSB));
}
}
}
template<direction dir>
static constexpr bits64 movegen_muggle_slide(square sq, bits64 occupants) {
bits64 ray = oracle_get_slide<dir>(sq);
bits64 raymask = occupants & ray;
bits64 blocker_ray = movegen_find_muggles<dir>(raymask);
return ray ^ blocker_ray;
}
template <piecetype type>
static constexpr bits64 movegen_get_attacks(square sq, bits64 occupants) {
switch (type) {
case KING:
return oracle_get_king_attacks(sq);
case KNIGHT:
return oracle_get_knight_attacks(sq);
case BISHOP:
return movegen_muggle_slide<NE>(sq, occupants)
| movegen_muggle_slide<SE>(sq, occupants)
| movegen_muggle_slide<SW>(sq, occupants)
| movegen_muggle_slide<NW>(sq, occupants);
case ROOK:
return movegen_muggle_slide<N>(sq, occupants)
| movegen_muggle_slide<E>(sq, occupants)
| movegen_muggle_slide<S>(sq, occupants)
| movegen_muggle_slide<W>(sq, occupants);
case QUEEN:
return movegen_muggle_slide<NE>(sq, occupants)
| movegen_muggle_slide<SE>(sq, occupants)
| movegen_muggle_slide<SW>(sq, occupants)
| movegen_muggle_slide<NW>(sq, occupants)
| movegen_muggle_slide<N>(sq, occupants)
| movegen_muggle_slide<E>(sq, occupants)
| movegen_muggle_slide<S>(sq, occupants)
| movegen_muggle_slide<W>(sq, occupants);
default:
assert(false);
return 0;
}
}
static inline bits64 movegen_get_attacksf(piecetype type, square sq, bits64 occupants) {
switch (type) {
case KING: return movegen_get_attacks<KING>(sq, occupants);
case KNIGHT: return movegen_get_attacks<KNIGHT>(sq, occupants);
case BISHOP: return movegen_get_attacks<BISHOP>(sq, occupants);
case ROOK: return movegen_get_attacks<ROOK>(sq, occupants);
case QUEEN: return movegen_get_attacks<QUEEN>(sq, occupants);
default: assert(false);
}
return 0;
}
template <color active>
static constexpr bits64 movegen_get_pawn_attack_mask(bits64 o_pawns) {
bits64 up = bits_shift<active ? S : N>(o_pawns);
bits64 east = (bits_shift_guarded<W>(up));
bits64 west = (bits_shift_guarded<E>(up));
return east | west;
}
template <piecetype type, color active>
static constexpr bits64 movegen_get_attackmask(bits64 pieces, bits64 occupants) {
bits64 attacks = 0;
while (pieces) {
square sq = bits_pop_trailing(&pieces);
attacks |= movegen_get_attacks<type>(sq, occupants);
}
return attacks;
}
template <piecetype type>
static constexpr void movegen_add_attacks(evalmove **cursor, bits64 pieces, bits64 occupants, bits64 legal) {
while (pieces) {
square origin = bits_pop_trailing(&pieces);
bits64 attacks = movegen_get_attacks<type>(origin, occupants) & legal;
while (attacks) {
square dest = bits_pop_trailing(&attacks);
*(*cursor)++ = MOVE_CREATE(origin, dest);
}
}
}
static constexpr void movegen_add_pawn_promotions(evalmove **cursor, move m) {
*(*cursor)++ = MOVE_ADD_PROMOTION(m, QUEEN);
*(*cursor)++ = MOVE_ADD_PROMOTION(m, KNIGHT);
*(*cursor)++ = MOVE_ADD_PROMOTION(m, ROOK);
*(*cursor)++ = MOVE_ADD_PROMOTION(m, BISHOP);
}
template <color active>
static constexpr void movegen_add_pawn_pushes(evalmove **cursor, bits64 a_pawns, bits64 occupants, bits64 o_checkers) {
constexpr int8_t modifier = active ? -8 : 8;
constexpr int8_t doublemodifier = active ? -16 : 16;
constexpr square promotionrank = active ? 1 : 6;
constexpr bits64 double_push_rank = active ? BB_RANK7 : BB_RANK2;
bits64 shifted = bits_shift<active ? N : S>(~occupants);
bits64 push = a_pawns & shifted;
bits64 doublepush = push & bits_shift<active ? N : S>(shifted) & double_push_rank;
if (o_checkers) {
bits64 o_checkers_shifted = bits_shift<active ? N : S>(o_checkers);
bits64 o_checkers_shifted2 = bits_shift<active ? N : S>(o_checkers_shifted);
push &= o_checkers_shifted;
doublepush &= o_checkers_shifted2;
}
while (doublepush) {
square origin = bits_pop_trailing(&doublepush);
square dest = (square) (origin + doublemodifier);
*(*cursor)++ = MOVE_CREATE(origin, dest);
}
while (push) {
square origin = bits_pop_trailing(&push);
square dest = (square) (origin + modifier);
move pawn_push = MOVE_CREATE(origin, dest);
if (SQUARE_Y(origin) == promotionrank) movegen_add_pawn_promotions(cursor, pawn_push);
else *(*cursor)++ = pawn_push;
}
}
template <color active>
static constexpr void movegen_add_unquiet_pawn_promotions(evalmove **cursor, bits64 a_pawns, bits64 occupants) {
constexpr int8_t modifier = active ? -8 : 8;
constexpr bits64 promo_starting_rank = active ? BB_RANK2 : BB_RANK7;
bits64 shifted = bits_shift<active ? N : S>(~occupants);
bits64 push = a_pawns & shifted & promo_starting_rank;
while (push) {
square origin = bits_pop_trailing(&push);
square dest = (square) (origin + modifier);
move promo = MOVE_CREATE(origin, dest);
*(*cursor)++ = MOVE_ADD_PROMOTION(promo, QUEEN);
*(*cursor)++ = MOVE_ADD_PROMOTION(promo, KNIGHT);
}
}
template <color active, bool go_east = true, bool go_west = true>
static constexpr void movegen_add_pawn_captures(evalmove **cursor, bits64 a_pawns, bits64 o_occupants) {
constexpr int8_t eastmodifier = active ? -7 : 9;
constexpr int8_t westmodifier = active ? -9 : 7;
constexpr square promotionrank = active ? 1 : 6;
bits64 up = bits_shift<active ? N : S>(o_occupants);
if (go_east) {
bits64 east = a_pawns & (bits_shift_guarded<W>(up));
while (east) {
square origin = bits_pop_trailing(&east);
square dest = (square) (origin + eastmodifier);
move push = MOVE_CREATE(origin, dest);
if (SQUARE_Y(origin) == promotionrank) movegen_add_pawn_promotions(cursor, push);
else *(*cursor)++ = push;
}
}
if (go_west) {
bits64 west = a_pawns & (bits_shift_guarded<E>(up));
while (west) {
square origin = bits_pop_trailing(&west);
square dest = (square) (origin + westmodifier);
move push = MOVE_CREATE(origin, dest);
if (SQUARE_Y(origin) == promotionrank) movegen_add_pawn_promotions(cursor, push);
else *(*cursor)++ = push;
}
}
}
template<direction dir>
static constexpr void movegen_add_pinned_slides(evalmove **cursor, bits64 pinned, bits64 occupants, bits64 illegal) {
constexpr direction opp = dir_opposite<dir>();
while (pinned) {
square origin = bits_pop_trailing(&pinned);
bits64 attacks = (movegen_muggle_slide<dir>(origin, occupants) | movegen_muggle_slide<opp>(origin, occupants)) & illegal;
while (attacks) {
square dest = bits_pop_trailing(&attacks);
*(*cursor)++ = MOVE_CREATE(origin, dest);
}
}
}
template<direction dir>
static constexpr bits64 movegen_get_sliding_checker(square kingsquare,
bits64 occupants,
bits64 o_sliders) {
bits64 ray = oracle_get_slide<dir>(kingsquare);
bits64 next_ray_targets = ray & occupants;
if (!next_ray_targets) return 0;
square popential_checker = bits_pop_directional<dir>(&next_ray_targets);
if (BITS_TEST(o_sliders, popential_checker)) {
/*also include squares between king and checker, which can be blocked*/
return movegen_muggle_slide<dir>(kingsquare, o_sliders);
}
return 0;
}
template<direction dir>
static constexpr bits64 movegen_find_pinned(square kingsquare,
bits64 occupants,
bits64 a_occupants,
bits64 o_sliders) {
bits64 ray = oracle_get_slide<dir>(kingsquare);
bits64 next_ray_targets = ray & occupants;
if (BITS_COUNT(next_ray_targets) < 2) return 0;
square pin_candidate_square = bits_pop_directional<dir>(&next_ray_targets);
assert(next_ray_targets);
square pinner_candidate_square = bits_pop_directional<dir>(&next_ray_targets);
bits64 pincandidate = BITS_FROM_SQUARE(pin_candidate_square) & a_occupants;
return pincandidate * BITS_TEST(o_sliders, pinner_candidate_square);
}
static constexpr bits64 movegen_get_pinned(const Board* board, color col) {
color opp = COLOR_OPPOSITE(col);
const Side* a_side = &board->side[col];
const bits64 a_occupants = a_side->piecemask;
square a_kingsquare = bits_get_trailing(a_side->pieces[KING]);
const Side* o_side = &board->side[opp];
const bits64 o_bishops = o_side->pieces[BISHOP] | o_side->pieces[QUEEN];
const bits64 o_rooks = o_side->pieces[ROOK] | o_side->pieces[QUEEN];
const bits64 occupants = a_side->piecemask | o_side->piecemask;
return movegen_find_pinned<N>(a_kingsquare, occupants, a_occupants, o_rooks)
| movegen_find_pinned<E>(a_kingsquare, occupants, a_occupants, o_rooks)
| movegen_find_pinned<S>(a_kingsquare, occupants, a_occupants, o_rooks)
| movegen_find_pinned<W>(a_kingsquare, occupants, a_occupants, o_rooks)
| movegen_find_pinned<NE>(a_kingsquare, occupants, a_occupants, o_bishops)
| movegen_find_pinned<SE>(a_kingsquare, occupants, a_occupants, o_bishops)
| movegen_find_pinned<SW>(a_kingsquare, occupants, a_occupants, o_bishops)
| movegen_find_pinned<NW>(a_kingsquare, occupants, a_occupants, o_bishops);
}
static constexpr int movegen_get_check_count(square a_kingsquare, const Side* o_side, piecetype* checker) {
int checks = 0;
for (int i = 0; i < o_side->attackmapsize; ++ i) {
const Attackmap* curr = &o_side->attackkmaps[i];
bool is_check = BITS_TEST(curr->bits, a_kingsquare);
if (is_check) {
*checker = curr->piece;
checks++;
}
}
return checks;
}
template <color active>
static void movegen_add_castling(evalmove **cursor, bits64 castlingrights, bits64 occupants, bits64 danger) {
if (!castlingrights) return;
if (active == WHITE) {
bits64 situation = occupants | (danger & ~BITS_FROM_SQUARE(1));
bits64 wcq = (situation & BB_REQUIRED_EMPTY_WCQ) | (BB_RIGHTS_WCQ & castlingrights);
if (wcq == BB_RIGHTS_WCQ) *(*cursor)++ = MOVE_WCQ;
bits64 wck = (situation & BB_REQUIRED_EMPTY_WCK) | (BB_RIGHTS_WCK & castlingrights);
if (wck == BB_RIGHTS_WCK) *(*cursor)++ = MOVE_WCK;
}
else {
bits64 situation = occupants | (danger & ~BITS_FROM_SQUARE(57));
bits64 bcq = (situation & BB_REQUIRED_EMPTY_BCQ) | (BB_RIGHTS_BCQ & castlingrights);
if (bcq == BB_RIGHTS_BCQ) *(*cursor)++ = MOVE_BCQ;
bits64 bck = (situation & BB_REQUIRED_EMPTY_BCK) | (BB_RIGHTS_BCK & castlingrights);
if (bck == BB_RIGHTS_BCK) *(*cursor)++ = MOVE_BCK;
}
}
template <color active, bool generatequiet = true>
static uint8_t movegen_generate(const Board* board, evalmove moves[128]) {
constexpr color opp = COLOR_OPPOSITE(active);
evalmove *cursor = moves;
const Plyinfo *info = board_get_currinfo(board);
const Side* a_side = &board->side[active];
const bits64* a_pieces = a_side->pieces;
const bits64 a_king = a_pieces[KING];
const bits64 a_knights = a_pieces[KNIGHT];
const bits64 a_bishops = a_pieces[BISHOP] | a_pieces[QUEEN];
const bits64 a_rooks = a_pieces[ROOK] | a_pieces[QUEEN];
const bits64 a_pawns = a_pieces[PAWN];
const bits64 a_occupants = a_side->piecemask;
const Side* o_side = &board->side[opp];
const bits64* o_pieces = o_side->pieces;
const bits64 o_knights = o_pieces[KNIGHT];
const bits64 o_bishops = o_pieces[BISHOP] | o_pieces[QUEEN];
const bits64 o_rooks = o_pieces[ROOK] | o_pieces[QUEEN];
const bits64 o_pawns = o_pieces[PAWN];
const bits64 o_occupants = o_side->piecemask;
const bits64 occupants = a_occupants | o_occupants;
bits64 enpassant = info->enpassant;
square a_kingsquare = bits_get_trailing(a_king);
bits64 a_king_danger = o_side->attackmask;
bits64 pins[8] = {
movegen_find_pinned<N>(a_kingsquare, occupants, a_occupants, o_rooks),
movegen_find_pinned<E>(a_kingsquare, occupants, a_occupants, o_rooks),
movegen_find_pinned<S>(a_kingsquare, occupants, a_occupants, o_rooks),
movegen_find_pinned<W>(a_kingsquare, occupants, a_occupants, o_rooks),
movegen_find_pinned<NE>(a_kingsquare, occupants, a_occupants, o_bishops),
movegen_find_pinned<SE>(a_kingsquare, occupants, a_occupants, o_bishops),
movegen_find_pinned<SW>(a_kingsquare, occupants, a_occupants, o_bishops),
movegen_find_pinned<NW>(a_kingsquare, occupants, a_occupants, o_bishops)
};
const bits64 pins_total = pins[N] | pins[E] | pins[S] | pins[W] | pins[NE] | pins[SE] | pins[SW] | pins[NW];
piecetype checker = piecetype::NONE;
int check_count = movegen_get_check_count(a_kingsquare, o_side, &checker);
if (check_count == 1) {
bits64 o_checker_kill_or_block_map = 0;
switch (checker) {
case QUEEN:o_checker_kill_or_block_map =
movegen_get_sliding_checker<NE>(a_kingsquare, occupants, o_bishops)
| movegen_get_sliding_checker<SE>(a_kingsquare, occupants, o_bishops)
| movegen_get_sliding_checker<SW>(a_kingsquare, occupants, o_bishops)
| movegen_get_sliding_checker<NW>(a_kingsquare, occupants, o_bishops)
| movegen_get_sliding_checker<N>(a_kingsquare, occupants, o_rooks)
| movegen_get_sliding_checker<E>(a_kingsquare, occupants, o_rooks)
| movegen_get_sliding_checker<S>(a_kingsquare, occupants, o_rooks)
| movegen_get_sliding_checker<W>(a_kingsquare, occupants, o_rooks); break;
case ROOK: o_checker_kill_or_block_map |=
movegen_get_sliding_checker<N>(a_kingsquare, occupants, o_rooks)
| movegen_get_sliding_checker<E>(a_kingsquare, occupants, o_rooks)
| movegen_get_sliding_checker<S>(a_kingsquare, occupants, o_rooks)
| movegen_get_sliding_checker<W>(a_kingsquare, occupants, o_rooks); break;
case BISHOP: o_checker_kill_or_block_map =
movegen_get_sliding_checker<NE>(a_kingsquare, occupants, o_bishops)
| movegen_get_sliding_checker<SE>(a_kingsquare, occupants, o_bishops)
| movegen_get_sliding_checker<SW>(a_kingsquare, occupants, o_bishops)
| movegen_get_sliding_checker<NW>(a_kingsquare, occupants, o_bishops); break;
case KNIGHT: o_checker_kill_or_block_map =
movegen_get_attackmask<KNIGHT, active>(a_king, occupants) & o_knights; break;
case PAWN: o_checker_kill_or_block_map =
movegen_get_pawn_attack_mask<active>(a_king) & o_pawns; break;
default:
assert(false);
}
bits64 enpassant_checker = bits_shift<active ? S : N>(o_checker_kill_or_block_map) & enpassant;
movegen_add_pawn_captures<active>(&cursor, a_pawns & ~pins_total, (o_occupants & o_checker_kill_or_block_map) | enpassant_checker);
movegen_add_pawn_pushes<active>(&cursor, a_pawns & ~pins_total, occupants, o_checker_kill_or_block_map);
movegen_add_attacks<KNIGHT>(&cursor, a_knights & ~pins_total, occupants, o_checker_kill_or_block_map);
movegen_add_attacks<BISHOP>(&cursor, a_bishops & ~pins_total, occupants, o_checker_kill_or_block_map);
movegen_add_attacks<ROOK>(&cursor, a_rooks & ~pins_total, occupants, o_checker_kill_or_block_map);
movegen_add_attacks<KING>(&cursor, a_king, occupants, ~(a_king_danger | a_occupants));
}
else if (check_count == 0) {
bits64 legaldestinations = generatequiet ? ~a_occupants : o_occupants;
/* moves allowed for pinned pieces */
bits64 pawn_pinsE = active ? pins[SE] : pins[NE];
bits64 pawn_pinsW = active ? pins[SW] : pins[NW];
movegen_add_pawn_captures<active, true, false>(&cursor, a_pawns & pawn_pinsE, o_occupants | enpassant);
movegen_add_pawn_captures<active, false, true>(&cursor, a_pawns & pawn_pinsW, o_occupants | enpassant);
if (generatequiet) movegen_add_pawn_pushes<active>(&cursor, a_pawns & (pins[S] | pins[N]), occupants, 0);
movegen_add_pinned_slides<NE>(&cursor, a_bishops & (pins[NE] | pins[SW]), occupants, legaldestinations);
movegen_add_pinned_slides<SE>(&cursor, a_bishops & (pins[SE] | pins[NW]), occupants, legaldestinations);
movegen_add_pinned_slides<N>(&cursor, a_rooks & (pins[N] | pins[S]), occupants, legaldestinations);
movegen_add_pinned_slides<E>(&cursor, a_rooks & (pins[E] | pins[W]), occupants, legaldestinations);
/* special check for horizontal rook attack on king during en passant capture */
if (enpassant) {
bits64 occupants_ep = occupants ^ bits_shift<active ? N : S>(enpassant);
bits64 pins_ep = movegen_find_pinned<E>(a_kingsquare, occupants_ep, a_occupants, o_rooks)
| movegen_find_pinned<W>(a_kingsquare, occupants_ep, a_occupants, o_rooks);
/* if so do not allow en passant captures */
if ((pins_total | pins_ep) != pins_total) enpassant = 0;
}
/* moves allowed for all non-pinned pieces */
movegen_add_pawn_captures<active>(&cursor, a_pawns & ~pins_total, o_occupants | enpassant);
if (generatequiet) movegen_add_pawn_pushes<active>(&cursor, a_pawns & ~pins_total, occupants, 0);
else movegen_add_unquiet_pawn_promotions<active>(&cursor, a_pawns & ~pins_total, occupants);
movegen_add_attacks<KNIGHT>(&cursor, a_knights & ~pins_total, occupants, legaldestinations);
movegen_add_attacks<BISHOP>(&cursor, a_bishops & ~pins_total, occupants, legaldestinations);
movegen_add_attacks<ROOK>(&cursor, a_rooks & ~pins_total, occupants, legaldestinations);
if (generatequiet) movegen_add_castling<active>(&cursor, info->castlingrights, occupants, a_king_danger);
movegen_add_attacks<KING>(&cursor, a_king, occupants, ~a_king_danger & legaldestinations);
}
else {
assert(check_count == 2);
movegen_add_attacks<KING>(&cursor, a_king, occupants, ~(a_king_danger | a_occupants));
}
return (uint8_t) (cursor - moves);
}
static inline uint8_t movegen_generatef(const Board* board, evalmove moves[128]) {
return board->active
? movegen_generate<BLACK>(board, moves)
: movegen_generate<WHITE>(board, moves);
}
#endif /* movegen_hpp */