From c9d9bddf3df97ef7987c9824747ec1602522b542 Mon Sep 17 00:00:00 2001 From: Aargh Rai Date: Sat, 18 Jul 2026 18:45:15 +0530 Subject: zobrist hashing --- include/bitboard.h | 2 ++ include/engine/magic.h | 1 + include/engine/moves.h | 1 + include/engine/transposition_table.h | 16 +++++++++++++ include/random.h | 10 ++++++++ src/engine.c | 1 + src/engine/moves/magic.c | 14 +----------- src/engine/transposition_table.c | 44 ++++++++++++++++++++++++++++++++++++ src/main.c | 29 ++---------------------- src/random.c | 14 ++++++++++++ tests/main.c | 2 ++ 11 files changed, 94 insertions(+), 40 deletions(-) create mode 100644 include/engine/transposition_table.h create mode 100644 include/random.h create mode 100644 src/engine/transposition_table.c create mode 100644 src/random.c diff --git a/include/bitboard.h b/include/bitboard.h index 3e1118d..b1ddcf0 100644 --- a/include/bitboard.h +++ b/include/bitboard.h @@ -27,11 +27,13 @@ enum { WHITE_LONG_CASTLE = 1 << 1, BLACK_SHORT_CASTLE = 1 << 2, BLACK_LONG_CASTLE = 1 << 3, + CASTLE_COUNT = 4, }; enum { WHITE_TURN, BLACK_TURN, + TURN_COUNT, }; #define BITMASK_RANK_1 255ULL diff --git a/include/engine/magic.h b/include/engine/magic.h index 7f584a9..1c9f303 100644 --- a/include/engine/magic.h +++ b/include/engine/magic.h @@ -3,6 +3,7 @@ #include "ints.h" #include "bitboard.h" +#include "random.h" typedef struct { bitboard_t mask; diff --git a/include/engine/moves.h b/include/engine/moves.h index 755a77a..cd71cdc 100644 --- a/include/engine/moves.h +++ b/include/engine/moves.h @@ -68,6 +68,7 @@ void get_moves(moves_t *moves, position_t position); bool square_attacked(position_t position, square_t square, u8 by_color); void get_legal_moves(moves_t *moves, position_t position); +int find_piece_on_square(position_t* p, int square); #ifdef MOVES_INTERNAL void __forloop_rook_moves_gen( diff --git a/include/engine/transposition_table.h b/include/engine/transposition_table.h new file mode 100644 index 0000000..f06ddbe --- /dev/null +++ b/include/engine/transposition_table.h @@ -0,0 +1,16 @@ +#ifndef TRANSPOSITION_TABLE_H +#define TRANSPOSITION_TABLE_H + +#include "bitboard.h" + +static struct zobrist_keys { + u64 piece[PIECE_TYPE_COUNT][64]; + u64 castle[CASTLE_COUNT]; + u64 turn[TURN_COUNT]; + u64 en_passant[64]; +} zobrist_keys; + +void transposition_table_init(); +u64 zobrist_hash(position_t position); + +#endif // TRANSPOSITION_TABLE_H diff --git a/include/random.h b/include/random.h new file mode 100644 index 0000000..633c015 --- /dev/null +++ b/include/random.h @@ -0,0 +1,10 @@ +#ifndef RANDOM_H +#define RANDOM_H + +#include "ints.h" + +u64 random_u64(); +u64 random_magic(); + +#endif // RANDOM_H + diff --git a/src/engine.c b/src/engine.c index a656a79..dc6940a 100644 --- a/src/engine.c +++ b/src/engine.c @@ -1,3 +1,4 @@ #include "engine/threads.c" #include "engine/thread.c" #include "engine/moves.c" +#include "engine/transposition_table.c" diff --git a/src/engine/moves/magic.c b/src/engine/moves/magic.c index 43f4a32..74b2c72 100644 --- a/src/engine/moves/magic.c +++ b/src/engine/moves/magic.c @@ -1,4 +1,5 @@ #include "engine/magic.h" +#include "random.h" #include #include #include @@ -8,19 +9,6 @@ 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; diff --git a/src/engine/transposition_table.c b/src/engine/transposition_table.c new file mode 100644 index 0000000..1afbc81 --- /dev/null +++ b/src/engine/transposition_table.c @@ -0,0 +1,44 @@ +#include "engine/transposition_table.h" + +void transposition_table_init() { + for (int i = 0; i < PIECE_TYPE_COUNT; i++) { + for (int j = 0; j < 64; j++) { + zobrist_keys.piece[i][j] = random_u64(); + } + } + for (int i = 0; i < CASTLE_COUNT; i++) { + zobrist_keys.castle[i] = random_u64(); + } + for (int i = 0; i < TURN_COUNT; i++) { + zobrist_keys.turn[i] = random_u64(); + } + for (int i = 0; i < 64; i++) { + zobrist_keys.en_passant[i] = random_u64(); + } +} + +u64 zobrist_hash(position_t position) { + u64 output = 0; + for (int i = 0; i < 64; i++) { + int piece_type = find_piece_on_square(&position, i); + output ^= zobrist_keys.piece[piece_type][i]; + } + + if (position.castling & WHITE_SHORT_CASTLE) { + output ^= zobrist_keys.castle[0]; + } + if (position.castling & WHITE_LONG_CASTLE) { + output ^= zobrist_keys.castle[1]; + } + if (position.castling & BLACK_SHORT_CASTLE) { + output ^= zobrist_keys.castle[2]; + } + if (position.castling & BLACK_LONG_CASTLE) { + output ^= zobrist_keys.castle[3]; + } + + output ^= zobrist_keys.turn[position.turn]; + output ^= zobrist_keys.en_passant[position.passantable_file]; + + return output; +} diff --git a/src/main.c b/src/main.c index 511943f..6dd5e13 100644 --- a/src/main.c +++ b/src/main.c @@ -3,7 +3,7 @@ #include #include #include -#include "fcntl.h" +#include #include "ipc/state.h" #include "ipc/threads.h" @@ -49,38 +49,12 @@ skip_refresh: !(is_stop = ipc_state_is_event(&ipc_state, EVENT_ENGINE_STOP)) ); if (is_stop) { - printf("ENDED\n"); threads_cleanup(&engine_threads); ipc_state_set_event(&ipc_state, EVENT_UCI_RUNNING); goto waiting_for_go; } threads_go_loop(&engine_threads); ipc_state_set_event(&ipc_state, EVENT_UCI_RUNNING); - // if (atomic_load(&ipc_state->state.quit)) break; - // if (atomic_load(&ipc_state->state.cleanup)) { - // set_threads(&engine_threads, 0); - // for (int i = 0; i < engine_threads.count; i++) { - // engine_threads.args[i].stop = -1; - // } - // } - // if (atomic_load(&ipc_state->state.go)) { - // printf("going\n"); - // engine_threads.sharing_position = ipc_state->state.position; - // engine_threads.go_args = (struct go_args*)ipc_state->state.go_args; - // set_threads(&engine_threads, ipc_state->state.threads); - // atomic_store(&ipc_state->state.go, 0); - // atomic_store(&ipc_state->state.go_ready_receive, 1); - // } - // if (atomic_load(&ipc_state->state.stop)) { - // printf("stopping\n"); - // send_stop_signal(&engine_threads); - // if (!all_stopped(&engine_threads)) continue; - // set_threads(&engine_threads, 0); - // for (int i = 0; i < engine_threads.count; i++) { - // engine_threads.args[i].stop = -1; - // } - // atomic_store(&ipc_state->state.stop, 0); - // } } ipc_state_deinit(&ipc_state); @@ -91,3 +65,4 @@ skip_refresh: #include "fen.c" #include "bitboard.c" +#include "random.c" diff --git a/src/random.c b/src/random.c new file mode 100644 index 0000000..df55d84 --- /dev/null +++ b/src/random.c @@ -0,0 +1,14 @@ +#include "random.h" + +static u64 rng_state = 1070399; + +u64 random_u64() { + rng_state ^= rng_state << 13; + rng_state ^= rng_state >> 7; + rng_state ^= rng_state << 17; + return rng_state; +} + +u64 random_magic() { + return random_u64() & random_u64() & random_u64(); +} diff --git a/tests/main.c b/tests/main.c index 38eb544..800e80d 100644 --- a/tests/main.c +++ b/tests/main.c @@ -49,3 +49,5 @@ int main() { return return_type; } + +#include "random.c" -- cgit v1.2.3