From 1a52152852ff29c727673fc80e8bf8eca5ed6365 Mon Sep 17 00:00:00 2001 From: Aargh Rai Date: Thu, 16 Jul 2026 14:08:24 +0530 Subject: starting pos, move count, test pass --- src/engine/moves.c | 250 +++++++++++++++++++++++++++++++++++++--------- src/engine/moves/attack.c | 154 ++++++++++++++++++++++++++++ src/engine/moves/king.c | 47 ++++++++- src/engine/moves/vec.c | 19 ++-- 4 files changed, 409 insertions(+), 61 deletions(-) create mode 100644 src/engine/moves/attack.c (limited to 'src/engine') diff --git a/src/engine/moves.c b/src/engine/moves.c index 05278a5..beaf8a6 100644 --- a/src/engine/moves.c +++ b/src/engine/moves.c @@ -2,12 +2,15 @@ #include "bitboard.h" #include "moves/vec.c" -#include "moves/king.c" #include "moves/knight.c" #include "moves/pawn.c" #include "moves/rook.c" #include "moves/bishop.c" #include "moves/queen.c" +#include "moves/attack.c" +#ifndef TEST_MOD +#include "moves/king.c" +#endif #include @@ -20,6 +23,45 @@ void get_moves(moves_t* moves, position_t position) { get_queen_moves(moves, position); } +void get_legal_moves(moves_t* moves, position_t position) { + get_moves(moves, position); + + u8 opponent = position.turn == WHITE_TURN ? BLACK_TURN : WHITE_TURN; + int write = 0; + for (int read = 0; read < moves->length; read++) { + move_t m = moves->moves[read]; + + if (m.flags & MOVE_SHORT_CASTLE) { + int king_sq = position.turn == WHITE_TURN ? 4 : 60; + int pass_sq = position.turn == WHITE_TURN ? 5 : 61; + if (square_attacked(position, king_sq, opponent)) continue; + if (square_attacked(position, pass_sq, opponent)) continue; + } + if (m.flags & MOVE_LONG_CASTLE) { + int king_sq = position.turn == WHITE_TURN ? 4 : 60; + int pass_sq = position.turn == WHITE_TURN ? 3 : 59; + if (square_attacked(position, king_sq, opponent)) continue; + if (square_attacked(position, pass_sq, opponent)) continue; + } + + position_t copy = position; + position_make_move(©, m); + + bitboard_t friendly_king; + if (position.turn == WHITE_TURN) { + friendly_king = copy.bitboards[WHITE_KING]; + } else { + friendly_king = copy.bitboards[BLACK_KING]; + } + int king_square = __builtin_ctzll(friendly_king); + + if (!square_attacked(copy, king_square, opponent)) { + moves->moves[write++] = m; + } + } + moves->length = write; +} + int find_piece_on_square(position_t* p, int square) { if ((p->bitboards[WHITE_KING] >> square) & 1) return WHITE_KING; if ((p->bitboards[WHITE_QUEEN] >> square) & 1) return WHITE_QUEEN; @@ -36,83 +78,193 @@ int find_piece_on_square(position_t* p, int square) { assert(0); } -void position_make_move(position_t* position, move_t* move) { - if (move->flags & MOVE_LONG_CASTLE) { +void position_make_move(position_t* position, move_t move) { + position->passantable_file = 0; + + if (move.flags & MOVE_LONG_CASTLE) { if (position->turn == WHITE_TURN) { - assert(position->bitboards[WHITE_KING] == 16); - assert((position->bitboards[WHITE_ROOK] >> 0) & 1); - - position->bitboards[WHITE_KING] = 2; - position->bitboards[WHITE_ROOK] += 3; - } else if (position->turn == BLACK_TURN) { - assert(position->bitboards[BLACK_KING] == 1152921504606846976ULL); - assert((position->bitboards[BLACK_ROOK] >> 56) & 1); - - position->bitboards[BLACK_KING] = 144115188075855872ULL; - position->bitboards[WHITE_ROOK] &= ~((bitboard_t)1 << 56); - position->bitboards[WHITE_ROOK] |= (bitboard_t)1 << 58; + position->bitboards[WHITE_KING] = (bitboard_t)1 << 2; + position->bitboards[WHITE_ROOK] &= ~((bitboard_t)1 << 0); + position->bitboards[WHITE_ROOK] |= (bitboard_t)1 << 3; + } else { + position->bitboards[BLACK_KING] = (bitboard_t)1 << 58; + position->bitboards[BLACK_ROOK] &= ~((bitboard_t)1 << 56); + position->bitboards[BLACK_ROOK] |= (bitboard_t)1 << 59; } + position->turn = !position->turn; return; } - if (move->flags & MOVE_SHORT_CASTLE) { + if (move.flags & MOVE_SHORT_CASTLE) { if (position->turn == WHITE_TURN) { - assert(position->bitboards[WHITE_KING] == 16); - assert((position->bitboards[WHITE_ROOK] >> 7) & 1); - - position->bitboards[WHITE_KING] = 64; + position->bitboards[WHITE_KING] = (bitboard_t)1 << 6; position->bitboards[WHITE_ROOK] &= ~((bitboard_t)1 << 7); position->bitboards[WHITE_ROOK] |= (bitboard_t)1 << 5; - } else if (position->turn == BLACK_TURN) { - assert(position->bitboards[BLACK_KING] == 1152921504606846976ULL); - assert((position->bitboards[BLACK_ROOK] >> 63) & 1); - - position->bitboards[WHITE_KING] = 4611686018427387904ULL; - position->bitboards[WHITE_ROOK] &= ~((bitboard_t)1 << 63); - position->bitboards[WHITE_ROOK] |= (bitboard_t)1 << 61; + } else { + position->bitboards[BLACK_KING] = (bitboard_t)1 << 62; + position->bitboards[BLACK_ROOK] &= ~((bitboard_t)1 << 63); + position->bitboards[BLACK_ROOK] |= (bitboard_t)1 << 61; } + position->turn = !position->turn; return; } - int piece_type = find_piece_on_square(position, move->from); - position->bitboards[piece_type] &= ~(1 << move->from); - if (move->flags & MOVE_PROMOTE_Q) { + int piece_type = find_piece_on_square(position, move.from); + position->bitboards[piece_type] &= ~((bitboard_t)1 << move.from); + + if (position->turn == BLACK_TURN) position->fullmove_clock++; + if (piece_type == WHITE_PAWN || piece_type == BLACK_PAWN) { + position->halfmove_clock = 0; + } else { + position->halfmove_clock++; + } + + if (position->castling > 0) { + if (piece_type == WHITE_ROOK) { + if (move.from == 7) { + position->castling &= ~WHITE_SHORT_CASTLE; + } else if (move.from == 0) { + position->castling &= ~WHITE_LONG_CASTLE; + } + } else if (piece_type == BLACK_ROOK) { + if (move.from == 63) { + position->castling &= ~BLACK_SHORT_CASTLE; + } else if (move.from == 56) { + position->castling &= ~BLACK_LONG_CASTLE; + } + } else if (piece_type == WHITE_KING) { + position->castling &= ~(WHITE_SHORT_CASTLE | WHITE_LONG_CASTLE); + } else if (piece_type == BLACK_KING) { + position->castling &= ~(BLACK_SHORT_CASTLE | BLACK_LONG_CASTLE); + } + } + + if (move.flags & MOVE_PROMOTE_Q) { int q_type = position->turn == WHITE_TURN ? WHITE_QUEEN : BLACK_QUEEN; - position->bitboards[q_type] |= 1 << move->to; + position->bitboards[q_type] |= (bitboard_t)1 << move.to; + position->turn = !position->turn; return; } - if (move->flags & MOVE_PROMOTE_R) { + if (move.flags & MOVE_PROMOTE_R) { int q_type = position->turn == WHITE_TURN ? WHITE_ROOK : BLACK_ROOK; - position->bitboards[q_type] |= 1 << move->to; + position->bitboards[q_type] |= (bitboard_t)1 << move.to; + position->turn = !position->turn; return; } - if (move->flags & MOVE_PROMOTE_B) { + if (move.flags & MOVE_PROMOTE_B) { int q_type = position->turn == WHITE_TURN ? WHITE_BISHOP : BLACK_BISHOP; - position->bitboards[q_type] |= 1 << move->to; + position->bitboards[q_type] |= (bitboard_t)1 << move.to; + position->turn = !position->turn; return; } - if (move->flags & MOVE_PROMOTE_N) { + if (move.flags & MOVE_PROMOTE_N) { int q_type = position->turn == WHITE_TURN ? WHITE_KNIGHT : BLACK_KNIGHT; - position->bitboards[q_type] |= 1 << move->to; + position->bitboards[q_type] |= (bitboard_t)1 << move.to; + position->turn = !position->turn; return; } - if (move->flags & MOVE_EN_PASSANT) { + if (move.flags & MOVE_EN_PASSANT) { int target_sqr; - if (position->turn == WHITE_TURN) target_sqr = move->to - 8; - else target_sqr = move->to + 8; + if (position->turn == WHITE_TURN) target_sqr = move.to - 8; + else target_sqr = move.to + 8; int to_remove_piece_type = find_piece_on_square(position, target_sqr); - position->bitboards[piece_type] |= 1 << move->to; - position->bitboards[to_remove_piece_type] &= ~(1 << target_sqr); + position->bitboards[piece_type] |= (bitboard_t)1 << move.to; + position->bitboards[to_remove_piece_type] &= ~((bitboard_t)1 << target_sqr); + position->turn = !position->turn; return; } - if (move->flags & MOVE_CAPTURE) { - int to_remove_piece_type = find_piece_on_square(position, move->to); - position->bitboards[to_remove_piece_type] &= ~(1 << move->to); + if (move.flags & MOVE_CAPTURE) { + int to_remove_piece_type = find_piece_on_square(position, move.to); + position->bitboards[to_remove_piece_type] &= ~((bitboard_t)1 << move.to); + + if (to_remove_piece_type == WHITE_ROOK) { + if (move.to == 7) position->castling &= ~WHITE_SHORT_CASTLE; + else if (move.to == 0) position->castling &= ~WHITE_LONG_CASTLE; + } else if (to_remove_piece_type == BLACK_ROOK) { + if (move.to == 63) position->castling &= ~BLACK_SHORT_CASTLE; + else if (move.to == 56) position->castling &= ~BLACK_LONG_CASTLE; + } } - // i can't put this above the find_piece_on_square function, because there - // is a possibility that piece_type would resolve to the piece that is being - // moved, which would mess with the ~(1 << to_sqr) - position->bitboards[piece_type] |= 1 << move->to; + if (piece_type == WHITE_PAWN && move.from / 8 == 1 && move.to / 8 == 3) { + position->passantable_file = (move.from % 8) + 1; + } else if (piece_type == BLACK_PAWN && move.from / 8 == 6 && move.to / 8 == 4) { + position->passantable_file = (move.from % 8) + 1; + } + + position->bitboards[piece_type] |= (bitboard_t)1 << move.to; + position->turn = !position->turn; +} + +#ifdef TEST_MOD +#include "fen.h" + +int count_positions(position_t position, int depth) { + if (depth == 0) return 1; + moves_t moves; + moves_init(&moves); + get_legal_moves(&moves, position); + int count = 0; + for (int i = 0; i < moves.length; i++) { + position_t copy = position; + position_make_move(©, moves.moves[i]); + count += count_positions(copy, depth - 1); + } + moves_deinit(moves); + return count; } + +void perft_divide(position_t position, int depth) { + if (depth == 0) return; + moves_t moves; + moves_init(&moves); + get_legal_moves(&moves, position); + for (int i = 0; i < moves.length; i++) { + position_t copy = position; + position_make_move(©, moves.moves[i]); + int c = count_positions(copy, depth - 1); + printf(" %c%d%c%d: %d\n", + 'a' + (moves.moves[i].from % 8), 1 + (moves.moves[i].from / 8), + 'a' + (moves.moves[i].to % 8), 1 + (moves.moves[i].to / 8), c); + } + moves_deinit(moves); +} + +// https://www.chessprogramming.org/Perft_Results#Initial_Position +bool test_perft_starting_position() { + position_t position = load_fen( + "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" + ).position; + int d; + d = count_positions(position, 0); printf("d0: %d\n", d); if (d != 1) return false; + d = count_positions(position, 1); printf("d1: %d\n", d); if (d != 20) return false; + d = count_positions(position, 2); printf("d2: %d\n", d); if (d != 400) return false; + d = count_positions(position, 3); printf("d3: %d\n", d); if (d != 8902) return false; + d = count_positions(position, 4); printf("d4: %d\n", d); if (d != 197281) return false; + + position_t castle_pos = load_fen( + "r3k2r/8/8/8/8/8/8/R3K2R w KQkq - 0 1" + ).position; + int cp = count_positions(castle_pos, 1); + printf("R3K2R d1: %d (expected 26)\n", cp); + + d = count_positions(position, 5); printf("d5: %d\n", d); if (d != 4865609) return false; + return true; +} + +bool test_perft_kiwipete_position() { + position_t position = load_fen( + "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" + ).position; + int d; + d = count_positions(position, 1); printf("d0: %d\n", d); if (d != 48) return false; + d = count_positions(position, 2); printf("d1: %d\n", d); if (d != 2039) return false; + d = count_positions(position, 3); printf("d2: %d\n", d); if (d != 97862) return false; + d = count_positions(position, 4); printf("d3: %d\n", d); if (d != 4085603) return false; + d = count_positions(position, 5); printf("d4: %d\n", d); if (d != 193690690) return false; + d = count_positions(position, 6); printf("d5: %d\n", d); if (d != 8031647685) return false; + return true; +} + +#endif // TEST_MOD diff --git a/src/engine/moves/attack.c b/src/engine/moves/attack.c new file mode 100644 index 0000000..e4923ea --- /dev/null +++ b/src/engine/moves/attack.c @@ -0,0 +1,154 @@ +#define MOVES_INTERNAL +#include "engine/moves.h" + +static bool pawn_attacks_square(position_t position, square_t square, u8 by_color) { + bitboard_t enemy_pawns; + if (by_color == WHITE_TURN) { + enemy_pawns = position.bitboards[WHITE_PAWN]; + if (square < 8) return false; + bitboard_t nw = (square % 8 == 7) ? 0 : (enemy_pawns >> (square - 7)); + bitboard_t ne = (square % 8 == 0) ? 0 : (enemy_pawns >> (square - 9)); + return (nw | ne) & 1; + } else { + enemy_pawns = position.bitboards[BLACK_PAWN]; + if (square > 54) return false; + bitboard_t se = (square % 8 == 0) ? 0 : (enemy_pawns >> (square + 7)); + bitboard_t sw = (square % 8 == 7) ? 0 : (enemy_pawns >> (square + 9)); + return (se | sw) & 1; + } +} + +static bool knight_attacks_square(position_t position, square_t square, u8 by_color) { + bitboard_t enemy_knights = (by_color == WHITE_TURN) + ? position.bitboards[WHITE_KNIGHT] + : position.bitboards[BLACK_KNIGHT]; + return knight_moves[square] & enemy_knights; +} + +static bool king_attacks_square(position_t position, square_t square, u8 by_color) { + bitboard_t enemy_king = (by_color == WHITE_TURN) + ? position.bitboards[WHITE_KING] + : position.bitboards[BLACK_KING]; + bitboard_t movement; + if (square >= 10) { + movement = 920078ULL << (square - 10); + } else { + movement = 920078ULL >> -(square - 10); + } + if ((bitboard_t)1 << square & BITMASK_FILE_A) { + movement &= BITMASK_FILE_A | BITMASK_FILE_B; + } else if ((bitboard_t)1 << square & BITMASK_FILE_H) { + movement &= BITMASK_FILE_G | BITMASK_FILE_H; + } + return movement & enemy_king; +} + +static bool sliding_attacks_square( + position_t position, + square_t square, + u8 by_color, + bool check_rook, + bool check_bishop +) { + bitboard_t all_occupied = whites(position) | blacks(position); + int rank = square / 8; + int file = square % 8; + + bitboard_t enemy_rooks = (by_color == WHITE_TURN) ? position.bitboards[WHITE_ROOK] : position.bitboards[BLACK_ROOK]; + bitboard_t enemy_bishops = (by_color == WHITE_TURN) ? position.bitboards[WHITE_BISHOP] : position.bitboards[BLACK_BISHOP]; + bitboard_t enemy_queens = (by_color == WHITE_TURN) ? position.bitboards[WHITE_QUEEN] : position.bitboards[BLACK_QUEEN]; + + if (check_rook) { + bitboard_t rook_like = enemy_rooks | enemy_queens; + + int r, idx; + r = rank + 1; + while (r < 8) { + idx = r * 8 + file; + if ((all_occupied >> idx) & 1) { + if ((rook_like >> idx) & 1) return true; + break; + } + r++; + } + r = rank - 1; + while (r >= 0) { + idx = r * 8 + file; + if ((all_occupied >> idx) & 1) { + if ((rook_like >> idx) & 1) return true; + break; + } + r--; + } + int f = file + 1; + while (f < 8) { + idx = rank * 8 + f; + if ((all_occupied >> idx) & 1) { + if ((rook_like >> idx) & 1) return true; + break; + } + f++; + } + f = file - 1; + while (f >= 0) { + idx = rank * 8 + f; + if ((all_occupied >> idx) & 1) { + if ((rook_like >> idx) & 1) return true; + break; + } + f--; + } + } + + if (check_bishop) { + bitboard_t bishop_like = enemy_bishops | enemy_queens; + + int r, f, idx; + r = rank + 1; f = file + 1; + while (r < 8 && f < 8) { + idx = r * 8 + f; + if ((all_occupied >> idx) & 1) { + if ((bishop_like >> idx) & 1) return true; + break; + } + r++; f++; + } + r = rank - 1; f = file - 1; + while (r >= 0 && f >= 0) { + idx = r * 8 + f; + if ((all_occupied >> idx) & 1) { + if ((bishop_like >> idx) & 1) return true; + break; + } + r--; f--; + } + r = rank - 1; f = file + 1; + while (r >= 0 && f < 8) { + idx = r * 8 + f; + if ((all_occupied >> idx) & 1) { + if ((bishop_like >> idx) & 1) return true; + break; + } + r--; f++; + } + r = rank + 1; f = file - 1; + while (r < 8 && f >= 0) { + idx = r * 8 + f; + if ((all_occupied >> idx) & 1) { + if ((bishop_like >> idx) & 1) return true; + break; + } + r++; f--; + } + } + + return false; +} + +bool square_attacked(position_t position, square_t square, u8 by_color) { + if (pawn_attacks_square(position, square, by_color)) return true; + if (knight_attacks_square(position, square, by_color)) return true; + if (king_attacks_square(position, square, by_color)) return true; + if (sliding_attacks_square(position, square, by_color, true, true)) return true; + return false; +} diff --git a/src/engine/moves/king.c b/src/engine/moves/king.c index 706cf9c..98c6ab9 100644 --- a/src/engine/moves/king.c +++ b/src/engine/moves/king.c @@ -42,15 +42,51 @@ void get_king_moves(moves_t* moves, position_t position) { .flags = ((enemy_pieces >> to) & 1) ? MOVE_CAPTURE : 0, ); } + + bitboard_t all_occupied = friendly_pieces | enemy_pieces; + if (position.turn == WHITE_TURN) { + if ((position.castling & WHITE_SHORT_CASTLE) && + king_square == 4 && + !((all_occupied >> 5) & 1) && + !((all_occupied >> 6) & 1)) + { + add_move(moves, 4, 6, .flags = MOVE_SHORT_CASTLE); + } + if ((position.castling & WHITE_LONG_CASTLE) && + king_square == 4 && + !((all_occupied >> 3) & 1) && + !((all_occupied >> 2) & 1) && + !((all_occupied >> 1) & 1)) + { + add_move(moves, 4, 2, .flags = MOVE_LONG_CASTLE); + } + } else { + if ((position.castling & BLACK_SHORT_CASTLE) && + king_square == 60 && + !((all_occupied >> 61) & 1) && + !((all_occupied >> 62) & 1)) + { + add_move(moves, 60, 62, .flags = MOVE_SHORT_CASTLE); + } + if ((position.castling & BLACK_LONG_CASTLE) && + king_square == 60 && + !((all_occupied >> 59) & 1) && + !((all_occupied >> 58) & 1) && + !((all_occupied >> 57) & 1)) + { + add_move(moves, 60, 58, .flags = MOVE_LONG_CASTLE); + } + } } #ifdef TEST_MOD #include -#include "vec.c" bool test_white_king_corners() { - moves_t moves = moves_init(); + moves_t moves; + moves_init(&moves); position_t p = {0}; + p.bitboards[BLACK_KING] = 100; p.bitboards[WHITE_KING] = 1; p.turn = WHITE_TURN; get_king_moves(&moves, p); @@ -82,12 +118,16 @@ bool test_white_king_corners() { if (moves.moves[2].from != 56) return false; if (moves.moves[2].to != 57) return false; + moves_deinit(moves); return true; } bool test_black_king_corners() { - moves_t moves = moves_init(); + moves_t moves; + moves_init(&moves); + position_t p = {0}; + p.bitboards[WHITE_KING] = 100; p.bitboards[BLACK_KING] = 1; p.turn = BLACK_TURN; get_king_moves(&moves, p); @@ -119,6 +159,7 @@ bool test_black_king_corners() { if (moves.moves[2].from != 56) return false; if (moves.moves[2].to != 57) return false; + moves_deinit(moves); return true; } #endif diff --git a/src/engine/moves/vec.c b/src/engine/moves/vec.c index b5cbb6f..6da3eb9 100644 --- a/src/engine/moves/vec.c +++ b/src/engine/moves/vec.c @@ -3,17 +3,18 @@ #include #include -moves_t moves_init() { - return moves_init_wcapacity(16); +void moves_init(moves_t *moves) { + return moves_init_wcapacity(moves, 16); } -moves_t moves_init_wcapacity(u32 capacity) { - move_t* moves = malloc(capacity * sizeof(*moves)); - return (moves_t) { - .moves = moves, - .capacity = capacity, - .length = 0, - }; +void moves_deinit(moves_t moves) { + free(moves.moves); +} + +void moves_init_wcapacity(moves_t *moves, u32 capacity) { + moves->moves = malloc(capacity * sizeof(*moves)); + moves->length = 0; + moves->capacity = capacity; } moves_t moves_empty() { -- cgit v1.2.3