summaryrefslogtreecommitdiff
path: root/src/engine
diff options
context:
space:
mode:
Diffstat (limited to 'src/engine')
-rw-r--r--src/engine/moves.c39
-rw-r--r--src/engine/moves/attack.c92
-rw-r--r--src/engine/moves/bishop.c49
-rw-r--r--src/engine/moves/magic.c204
-rw-r--r--src/engine/moves/queen.c27
-rw-r--r--src/engine/moves/rook.c50
6 files changed, 271 insertions, 190 deletions
diff --git a/src/engine/moves.c b/src/engine/moves.c
index beaf8a6..3aff11e 100644
--- a/src/engine/moves.c
+++ b/src/engine/moves.c
@@ -2,6 +2,7 @@
#include "bitboard.h"
#include "moves/vec.c"
+#include "moves/magic.c"
#include "moves/knight.c"
#include "moves/pawn.c"
#include "moves/rook.c"
@@ -258,12 +259,38 @@ bool test_perft_kiwipete_position() {
"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;
+ d = count_positions(position, 1); printf("d1: %d (expected 48)\n", d); if (d != 48) return false;
+ printf("--- Kiwipete d2 divide ---\n"); perft_divide(position, 2);
+ d = count_positions(position, 2); printf("d2: %d (expected 2039)\n", d); if (d != 2039) return false;
+
+ printf("\n--- Debug: investigate e5g6 ---\n");
+ {
+ moves_t moves;
+ moves_init(&moves);
+ get_legal_moves(&moves, position);
+ for (int i = 0; i < moves.length; i++) {
+ if (moves.moves[i].from == 36 && moves.moves[i].to == 46) {
+ position_t copy = position;
+ position_make_move(&copy, moves.moves[i]);
+ printf("After Nxe5g6, turn=%d, is e8 attacked by white? %d\n",
+ copy.turn, square_attacked(copy, 60, WHITE_TURN));
+ moves_t black_moves;
+ moves_init(&black_moves);
+ get_legal_moves(&black_moves, copy);
+ printf("Black has %d legal moves:\n", black_moves.length);
+ for (int j = 0; j < black_moves.length; j++) {
+ printf(" %c%d%c%d flags=%d\n",
+ 'a' + (black_moves.moves[j].from % 8), 1 + (black_moves.moves[j].from / 8),
+ 'a' + (black_moves.moves[j].to % 8), 1 + (black_moves.moves[j].to / 8),
+ black_moves.moves[j].flags);
+ }
+ moves_deinit(black_moves);
+ break;
+ }
+ }
+ moves_deinit(moves);
+ }
+
return true;
}
diff --git a/src/engine/moves/attack.c b/src/engine/moves/attack.c
index e4923ea..2786ad3 100644
--- a/src/engine/moves/attack.c
+++ b/src/engine/moves/attack.c
@@ -51,95 +51,19 @@ static bool sliding_attacks_square(
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--;
- }
+ bitboard_t rook_like = (by_color == WHITE_TURN)
+ ? (position.bitboards[WHITE_ROOK] | position.bitboards[WHITE_QUEEN])
+ : (position.bitboards[BLACK_ROOK] | position.bitboards[BLACK_QUEEN]);
+ if (get_rook_attacks(square, all_occupied) & rook_like) return true;
}
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--;
- }
+ bitboard_t bishop_like = (by_color == WHITE_TURN)
+ ? (position.bitboards[WHITE_BISHOP] | position.bitboards[WHITE_QUEEN])
+ : (position.bitboards[BLACK_BISHOP] | position.bitboards[BLACK_QUEEN]);
+ if (get_bishop_attacks(square, all_occupied) & bishop_like) return true;
}
return false;
diff --git a/src/engine/moves/bishop.c b/src/engine/moves/bishop.c
index 0bc47f8..a7b2812 100644
--- a/src/engine/moves/bishop.c
+++ b/src/engine/moves/bishop.c
@@ -7,52 +7,15 @@ void __forloop_bishop_moves_gen(
bitboard_t friendly_pieces,
bitboard_t enemy_pieces
) {
+ bitboard_t all_occupied = friendly_pieces | enemy_pieces;
while (friendly_type) {
int from = __builtin_ctzll(friendly_type);
friendly_type &= friendly_type - 1;
-
- int og_rank = from / 8; // range: [0, 7]
- int og_file = from % 8; // range: [0, 7]
- int rank = og_rank + 1, file = og_file + 1, index = rank * 8 + file;
-
- bitboard_t occupied;
- while ((rank < 8 && file < 8) && !occupied_by(friendly_pieces, index)) {
- occupied = occupied_by(enemy_pieces, index);
- add_move(moves, from, index, .flags = occupied ? MOVE_CAPTURE : 0);
- if (occupied) {
- break;
- }
- index = ++rank * 8 + ++file;
- }
-
- rank = og_rank - 1, file = og_file - 1, index = rank * 8 + file;
- while ((rank >= 0 && file >= 0) && !occupied_by(friendly_pieces, index)) {
- occupied = occupied_by(enemy_pieces, index);
- add_move(moves, from, index, .flags = occupied ? MOVE_CAPTURE : 0);
- if (occupied) {
- break;
- }
- index = --rank * 8 + --file;
- }
-
- rank = og_rank - 1, file = og_file + 1, index = rank * 8 + file;
- while ((rank >= 0 && file < 8) && !occupied_by(friendly_pieces, index)) {
- occupied = occupied_by(enemy_pieces, index);
- add_move(moves, from, index, .flags = occupied ? MOVE_CAPTURE : 0);
- if (occupied) {
- break;
- }
- index = --rank * 8 + ++file;
- }
-
- rank = og_rank + 1, file = og_file - 1, index = rank * 8 + file;
- while ((rank < 8 && file >= 0) && !occupied_by(friendly_pieces, index)) {
- occupied = occupied_by(enemy_pieces, index);
- add_move(moves, from, index, .flags = occupied ? MOVE_CAPTURE : 0);
- if (occupied) {
- break;
- }
- index = ++rank * 8 + --file;
+ bitboard_t attacks = get_bishop_attacks(from, all_occupied) & ~friendly_pieces;
+ while (attacks) {
+ int to = __builtin_ctzll(attacks);
+ attacks &= attacks - 1;
+ add_move(moves, from, to, .flags = ((enemy_pieces >> to) & 1) ? MOVE_CAPTURE : 0);
}
}
}
diff --git a/src/engine/moves/magic.c b/src/engine/moves/magic.c
new file mode 100644
index 0000000..43f4a32
--- /dev/null
+++ b/src/engine/moves/magic.c
@@ -0,0 +1,204 @@
+#include "engine/magic.h"
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+static magic_t rook_table[64];
+static magic_t bishop_table[64];
+static bitboard_t *rook_attacks_flat;
+static bitboard_t *bishop_attacks_flat;
+
+static u64 rng_state = 1070399;
+
+static u64 random_u64(void) {
+ rng_state ^= rng_state << 13;
+ rng_state ^= rng_state >> 7;
+ rng_state ^= rng_state << 17;
+ return rng_state;
+}
+
+static u64 random_magic(void) {
+ return random_u64() & random_u64() & random_u64();
+}
+
+static bitboard_t compute_rook_mask(int sq) {
+ bitboard_t mask = 0;
+ int rank = sq / 8, file = sq % 8;
+ for (int r = rank + 1; r < 7; r++) mask |= (bitboard_t)1 << (r * 8 + file);
+ for (int r = rank - 1; r > 0; r--) mask |= (bitboard_t)1 << (r * 8 + file);
+ for (int f = file + 1; f < 7; f++) mask |= (bitboard_t)1 << (rank * 8 + f);
+ for (int f = file - 1; f > 0; f--) mask |= (bitboard_t)1 << (rank * 8 + f);
+ return mask;
+}
+
+static bitboard_t compute_bishop_mask(int sq) {
+ bitboard_t mask = 0;
+ int rank = sq / 8, file = sq % 8;
+ for (int r = rank + 1, f = file + 1; r < 7 && f < 7; r++, f++)
+ mask |= (bitboard_t)1 << (r * 8 + f);
+ for (int r = rank - 1, f = file - 1; r > 0 && f > 0; r--, f--)
+ mask |= (bitboard_t)1 << (r * 8 + f);
+ for (int r = rank - 1, f = file + 1; r > 0 && f < 7; r--, f++)
+ mask |= (bitboard_t)1 << (r * 8 + f);
+ for (int r = rank + 1, f = file - 1; r < 7 && f > 0; r++, f--)
+ mask |= (bitboard_t)1 << (r * 8 + f);
+ return mask;
+}
+
+static bitboard_t compute_rook_attacks_ref(int sq, bitboard_t occ) {
+ bitboard_t attacks = 0;
+ int rank = sq / 8, file = sq % 8;
+ for (int r = rank + 1; r < 8; r++) {
+ bitboard_t b = (bitboard_t)1 << (r * 8 + file);
+ attacks |= b;
+ if (occ & b) break;
+ }
+ for (int r = rank - 1; r >= 0; r--) {
+ bitboard_t b = (bitboard_t)1 << (r * 8 + file);
+ attacks |= b;
+ if (occ & b) break;
+ }
+ for (int f = file + 1; f < 8; f++) {
+ bitboard_t b = (bitboard_t)1 << (rank * 8 + f);
+ attacks |= b;
+ if (occ & b) break;
+ }
+ for (int f = file - 1; f >= 0; f--) {
+ bitboard_t b = (bitboard_t)1 << (rank * 8 + f);
+ attacks |= b;
+ if (occ & b) break;
+ }
+ return attacks;
+}
+
+static bitboard_t compute_bishop_attacks_ref(int sq, bitboard_t occ) {
+ bitboard_t attacks = 0;
+ int rank = sq / 8, file = sq % 8;
+ for (int r = rank + 1, f = file + 1; r < 8 && f < 8; r++, f++) {
+ bitboard_t b = (bitboard_t)1 << (r * 8 + f);
+ attacks |= b;
+ if (occ & b) break;
+ }
+ for (int r = rank - 1, f = file - 1; r >= 0 && f >= 0; r--, f--) {
+ bitboard_t b = (bitboard_t)1 << (r * 8 + f);
+ attacks |= b;
+ if (occ & b) break;
+ }
+ for (int r = rank - 1, f = file + 1; r >= 0 && f < 8; r--, f++) {
+ bitboard_t b = (bitboard_t)1 << (r * 8 + f);
+ attacks |= b;
+ if (occ & b) break;
+ }
+ for (int r = rank + 1, f = file - 1; r < 8 && f >= 0; r++, f--) {
+ bitboard_t b = (bitboard_t)1 << (r * 8 + f);
+ attacks |= b;
+ if (occ & b) break;
+ }
+ return attacks;
+}
+
+static void init_magic_for_square(
+ int sq, magic_t *entry, bool is_bishop,
+ bitboard_t *occs, bitboard_t *atts, bitboard_t *used
+) {
+ int bits = 64 - entry->shift;
+ int count = 1 << bits;
+ bitboard_t mask = entry->mask;
+
+ for (int i = 0; i < count; i++) {
+ occs[i] = 0;
+ bitboard_t m = mask;
+ for (int j = 0; m; j++) {
+ if (i & (1 << j)) {
+ occs[i] |= (bitboard_t)1 << __builtin_ctzll(m);
+ }
+ m &= m - 1;
+ }
+ atts[i] = is_bishop
+ ? compute_bishop_attacks_ref(sq, occs[i])
+ : compute_rook_attacks_ref(sq, occs[i]);
+ }
+
+ for (int tries = 0; tries < 100000000; tries++) {
+ bitboard_t magic = random_magic();
+ if (__builtin_popcountll((magic * mask) & 0xFF00000000000000ULL) < 6)
+ continue;
+
+ memset(used, 0, count * sizeof(bitboard_t));
+ bool fail = false;
+
+ for (int i = 0; i < count && !fail; i++) {
+ int idx = (int)(((occs[i] * magic) >> (64 - bits)) & (count - 1));
+ if (used[idx] == 0) {
+ used[idx] = atts[i];
+ } else if (used[idx] != atts[i]) {
+ fail = true;
+ }
+ }
+
+ if (!fail) {
+ entry->magic = magic;
+ for (int i = 0; i < count; i++) {
+ int idx = (int)(((occs[i] * magic) >> (64 - bits)) & (count - 1));
+ entry->attacks[idx] = atts[i];
+ }
+ return;
+ }
+ }
+
+ assert(0 && "Failed to find magic number");
+}
+
+void magic_init(void) {
+ for (int sq = 0; sq < 64; sq++) {
+ rook_table[sq].mask = compute_rook_mask(sq);
+ rook_table[sq].shift = 64 - __builtin_popcountll(rook_table[sq].mask);
+ bishop_table[sq].mask = compute_bishop_mask(sq);
+ bishop_table[sq].shift = 64 - __builtin_popcountll(bishop_table[sq].mask);
+ }
+
+ int rook_total = 0, bishop_total = 0;
+ for (int sq = 0; sq < 64; sq++) {
+ rook_total += 1 << (64 - rook_table[sq].shift);
+ bishop_total += 1 << (64 - bishop_table[sq].shift);
+ }
+
+ rook_attacks_flat = (bitboard_t*)malloc(rook_total * sizeof(bitboard_t));
+ bishop_attacks_flat = (bitboard_t*)malloc(bishop_total * sizeof(bitboard_t));
+ assert(rook_attacks_flat && bishop_attacks_flat);
+
+ int rook_off = 0, bishop_off = 0;
+ for (int sq = 0; sq < 64; sq++) {
+ rook_table[sq].attacks = rook_attacks_flat + rook_off;
+ rook_off += 1 << (64 - rook_table[sq].shift);
+ bishop_table[sq].attacks = bishop_attacks_flat + bishop_off;
+ bishop_off += 1 << (64 - bishop_table[sq].shift);
+ }
+
+ int max_count = 1 << 12;
+ bitboard_t *occs = (bitboard_t*)malloc(max_count * sizeof(bitboard_t));
+ bitboard_t *atts = (bitboard_t*)malloc(max_count * sizeof(bitboard_t));
+ bitboard_t *used = (bitboard_t*)malloc(max_count * sizeof(bitboard_t));
+ assert(occs && atts && used);
+
+ for (int sq = 0; sq < 64; sq++) {
+ init_magic_for_square(sq, &rook_table[sq], false, occs, atts, used);
+ }
+ for (int sq = 0; sq < 64; sq++) {
+ init_magic_for_square(sq, &bishop_table[sq], true, occs, atts, used);
+ }
+
+ free(occs);
+ free(atts);
+ free(used);
+}
+
+bitboard_t get_rook_attacks(int sq, bitboard_t occ) {
+ magic_t *m = &rook_table[sq];
+ return m->attacks[((occ & m->mask) * m->magic) >> m->shift];
+}
+
+bitboard_t get_bishop_attacks(int sq, bitboard_t occ) {
+ magic_t *m = &bishop_table[sq];
+ return m->attacks[((occ & m->mask) * m->magic) >> m->shift];
+}
diff --git a/src/engine/moves/queen.c b/src/engine/moves/queen.c
index 3e0b8ef..bd3f564 100644
--- a/src/engine/moves/queen.c
+++ b/src/engine/moves/queen.c
@@ -16,17 +16,18 @@ void get_queen_moves(moves_t* moves, position_t position) {
enemy_pieces = whites(position);
friendly_queens = position.bitboards[BLACK_QUEEN];
}
-
- __forloop_rook_moves_gen(
- moves,
- friendly_queens,
- friendly_pieces,
- enemy_pieces
- );
- __forloop_bishop_moves_gen(
- moves,
- friendly_queens,
- friendly_pieces,
- enemy_pieces
- );
+
+ bitboard_t all_occupied = friendly_pieces | enemy_pieces;
+ bitboard_t queens = friendly_queens;
+ while (queens) {
+ int from = __builtin_ctzll(queens);
+ queens &= queens - 1;
+ bitboard_t attacks = (get_rook_attacks(from, all_occupied) |
+ get_bishop_attacks(from, all_occupied)) & ~friendly_pieces;
+ while (attacks) {
+ int to = __builtin_ctzll(attacks);
+ attacks &= attacks - 1;
+ add_move(moves, from, to, .flags = ((enemy_pieces >> to) & 1) ? MOVE_CAPTURE : 0);
+ }
+ }
}
diff --git a/src/engine/moves/rook.c b/src/engine/moves/rook.c
index abbc784..0938de9 100644
--- a/src/engine/moves/rook.c
+++ b/src/engine/moves/rook.c
@@ -7,53 +7,15 @@ void __forloop_rook_moves_gen(
bitboard_t friendly_pieces,
bitboard_t enemy_pieces
) {
+ bitboard_t all_occupied = friendly_pieces | enemy_pieces;
while (friendly_type) {
int from = __builtin_ctzll(friendly_type);
friendly_type &= friendly_type - 1;
-
- int og_rank = from / 8; // range: [0, 7]
- int og_file = from % 8; // range: [0, 7]
- int rank = og_rank + 1, file = og_file, index = rank * 8 + file;
-
-
- bitboard_t occupied;
- while (rank < 8 && !occupied_by(friendly_pieces, index)) {
- occupied = occupied_by(enemy_pieces, index);
- add_move(moves, from, index, .flags = occupied ? MOVE_CAPTURE : 0);
- if (occupied) {
- break;
- }
- index = ++rank * 8 + file;
- }
-
- rank = og_rank - 1, file = og_file, index = rank * 8 + file;
- while (rank >= 0 && !occupied_by(friendly_pieces, index)) {
- occupied = occupied_by(enemy_pieces, index);
- add_move(moves, from, index, .flags = occupied ? MOVE_CAPTURE : 0);
- if (occupied) {
- break;
- }
- index = --rank * 8 + file;
- }
-
- rank = og_rank, file = og_file + 1, index = rank * 8 + file;
- while (file < 8 && !occupied_by(friendly_pieces, index)) {
- occupied = occupied_by(enemy_pieces, index);
- add_move(moves, from, index, .flags = occupied ? MOVE_CAPTURE : 0);
- if (occupied) {
- break;
- }
- index = rank * 8 + ++file;
- }
-
- rank = og_rank, file = og_file - 1, index = rank * 8 + file;
- while (file >= 0 && !occupied_by(friendly_pieces, index)) {
- occupied = occupied_by(enemy_pieces, index);
- add_move(moves, from, index, .flags = occupied ? MOVE_CAPTURE : 0);
- if (occupied) {
- break;
- }
- index = rank * 8 + --file;
+ bitboard_t attacks = get_rook_attacks(from, all_occupied) & ~friendly_pieces;
+ while (attacks) {
+ int to = __builtin_ctzll(attacks);
+ attacks &= attacks - 1;
+ add_move(moves, from, to, .flags = ((enemy_pieces >> to) & 1) ? MOVE_CAPTURE : 0);
}
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2026-08-24 21:40:11 +0000