starting pos, move count, test pass

4 files changed, 409 insertions, 61 deletions

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 <assert.h>
 
@@ -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(&copy, 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(&copy, 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(&copy, 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 <stdbool.h>
-#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 <assert.h>
 #include <stdlib.h>
 
-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() {