diff options
| -rw-r--r-- | include/engine/ttable.h | 15 | ||||
| -rw-r--r-- | src/engine/ttable.c | 165 | ||||
| -rw-r--r-- | tests/generated.c | 18 |
3 files changed, 100 insertions, 98 deletions
diff --git a/include/engine/ttable.h b/include/engine/ttable.h index 8b1938a..e1a10f1 100644 --- a/include/engine/ttable.h +++ b/include/engine/ttable.h @@ -5,9 +5,6 @@ #include "bitboard.h" #include <stdatomic.h> -#define TABLE_BITS 24 -#define TABLE_SIZE (1ULL << TABLE_BITS) -#define TT_MASK (TABLE_SIZE - 1) #define TT_BUCKET_SIZE 4 static struct zobrist_keys { @@ -33,10 +30,13 @@ typedef struct { typedef struct { tentry_t entries[TT_BUCKET_SIZE]; - int items_filled; + // int items_filled; } tbucket_t; -typedef tbucket_t* ttable_t; +typedef struct { + tbucket_t* buckets; + u64 mask; +} ttable_t; struct ttable_insert_args { u64 key; @@ -48,7 +48,10 @@ struct ttable_insert_args { u8 flag; }; -void ttable_init(ttable_t *table); +// if you want size 8, then size_in_binary_log = 3 +// if you want size 4, then size_in_binary_log = 2 +// you are forced to have powers of 2 for size +void ttable_init(ttable_t *table, size_t size_in_binary_log); void ttable_deinit(ttable_t table); void __ttable_insert(ttable_t table, struct ttable_insert_args args); tentry_t *ttable_find(ttable_t table, u64 key); diff --git a/src/engine/ttable.c b/src/engine/ttable.c index 851e389..fc1b6f0 100644 --- a/src/engine/ttable.c +++ b/src/engine/ttable.c @@ -47,21 +47,28 @@ u64 zobrist_hash(position_t position) { return output; } -void ttable_init(ttable_t *table) { - ttable_t output = calloc(TABLE_SIZE, sizeof(tbucket_t)); - memcpy(table, &output, sizeof(output)); +void ttable_init(ttable_t *table, size_t size_in_binary_log) { + assert(size_in_binary_log < 64); + int size = 1ULL << size_in_binary_log; + table->buckets = calloc(size, sizeof(tbucket_t)); + table->mask = size - 1; } void ttable_deinit(ttable_t table) { - free(table); + free(table.buckets); } void __ttable_insert(ttable_t table, struct ttable_insert_args args) { - tbucket_t *bucket = table + (args.key & TT_MASK); + tbucket_t *bucket = table.buckets + (args.key & table.mask); tentry_t *best = bucket->entries; - int count = bucket->items_filled; - for (int i = 1; i < count; i++) { + int ci = 0; + + for (int i = 0; i < TT_BUCKET_SIZE; i++) { + if (atomic_load(&bucket->entries[i].key) == args.key) { + best = bucket->entries + i; + break; + } if (bucket->entries[i].depth >= best->depth) continue; best = bucket->entries + i; } @@ -79,7 +86,7 @@ void __ttable_insert(ttable_t table, struct ttable_insert_args args) { } tentry_t *ttable_find(ttable_t table, u64 key) { - tbucket_t *bucket = table + (key & TT_MASK); + tbucket_t *bucket = table.buckets + (key & table.mask); for (int i = 0; i < TT_BUCKET_SIZE; i++) { if (atomic_load(&(bucket->entries + i)->key) != key) continue; @@ -91,20 +98,19 @@ tentry_t *ttable_find(ttable_t table, u64 key) { #ifdef TEST_MOD -bool test_empty_ttable() { +bool test_ttable_empty() { ttable_t table; - ttable_init(&table); + ttable_init(&table, 4); if (ttable_find(table, 123456789ULL) != NULL) return false; ttable_deinit(table); - return true; } bool test_ttable_insert_and_find() { ttable_t table; - ttable_init(&table); + ttable_init(&table, 4); u64 key = 0x123456789ABCDEF0ULL; ttable_insert(table, .key = key, .depth = 8, .flag = TT_EXACT); @@ -123,7 +129,7 @@ bool test_ttable_insert_and_find() { bool test_ttable_wrong_key() { ttable_t table; - ttable_init(&table); + ttable_init(&table, 4); u64 key = 0x123456789ABCDEF0ULL; ttable_insert(table, .key = key, .depth = 8, .flag = TT_EXACT); @@ -135,7 +141,7 @@ bool test_ttable_wrong_key() { bool test_ttable_update_existing() { ttable_t table; - ttable_init(&table); + ttable_init(&table, 4); u64 key = 987654321ULL; ttable_insert(table, .key = key, .depth = 10, .flag = TT_LOWERBOUND); @@ -151,77 +157,64 @@ bool test_ttable_update_existing() { return true; } -// bool FAH_test_bucket_collision() { -// ttable_t table; -// ttable_init(&table); -// -// -// -// TranspositionTable tt; -// tt_init(&tt, 1); // one bucket -// -// tt_store(&tt, 1, 10, 10, 5, TT_EXACT); -// tt_store(&tt, 2, 20, 20, 5, TT_EXACT); -// tt_store(&tt, 3, 30, 30, 5, TT_EXACT); -// tt_store(&tt, 4, 40, 40, 5, TT_EXACT); -// -// assert(tt_probe(&tt, 1) != NULL); -// assert(tt_probe(&tt, 2) != NULL); -// assert(tt_probe(&tt, 3) != NULL); -// assert(tt_probe(&tt, 4) != NULL); -// -// tt_destroy(&tt); -// } - -// void test_replace_shallowest(void) { -// TranspositionTable tt; -// tt_init(&tt, 1); -// -// tt_store(&tt, 1, 0, 0, 10, TT_EXACT); -// tt_store(&tt, 2, 0, 0, 20, TT_EXACT); -// tt_store(&tt, 3, 0, 0, 30, TT_EXACT); -// tt_store(&tt, 4, 0, 0, 40, TT_EXACT); -// -// // Bucket is full. -// -// tt_store(&tt, 5, 0, 0, 25, TT_EXACT); -// -// assert(tt_probe(&tt, 1) == NULL); -// -// assert(tt_probe(&tt, 2) != NULL); -// assert(tt_probe(&tt, 3) != NULL); -// assert(tt_probe(&tt, 4) != NULL); -// assert(tt_probe(&tt, 5) != NULL); -// -// tt_destroy(&tt); -// } - -// void test_many_entries(void) -// { -// TranspositionTable tt; -// tt_init(&tt, 1 << 16); -// -// for (uint64_t i = 0; i < 50000; i++) -// { -// tt_store(&tt, -// i * 7919, -// i, -// i, -// i % 64, -// TT_EXACT); -// } -// -// for (uint64_t i = 0; i < 50000; i++) -// { -// TTEntry *e = tt_probe(&tt, i * 7919); -// -// if (e) -// { -// assert(e->key == i * 7919); -// } -// } -// -// tt_destroy(&tt); -// } +bool test_bucket_collision() { + ttable_t table; + ttable_init(&table, 2); + + ttable_insert(table, .key = 1, .depth = 10, .flag = TT_EXACT); + ttable_insert(table, .key = 2, .depth = 20, .flag = TT_EXACT); + ttable_insert(table, .key = 3, .depth = 30, .flag = TT_EXACT); + ttable_insert(table, .key = 4, .depth = 40, .flag = TT_EXACT); + + if (ttable_find(table, 1) == NULL) return false; + if (ttable_find(table, 2) == NULL) return false; + if (ttable_find(table, 3) == NULL) return false; + if (ttable_find(table, 4) == NULL) return false; + + ttable_deinit(table); + return true; +} + +bool test_ttable_replace_shallowest() { + ttable_t table; + ttable_init(&table, 0); + + ttable_insert(table, .key = 1, .depth = 10, .flag = TT_EXACT); + ttable_insert(table, .key = 2, .depth = 20, .flag = TT_EXACT); + ttable_insert(table, .key = 3, .depth = 30, .flag = TT_EXACT); + ttable_insert(table, .key = 4, .depth = 40, .flag = TT_EXACT); + + // Bucket is full. + ttable_insert(table, .key = 5, .depth = 25, .flag = TT_EXACT); + + if (ttable_find(table, 1) != NULL) return false; + + if (ttable_find(table, 2) == NULL) return false; + if (ttable_find(table, 3) == NULL) return false; + if (ttable_find(table, 4) == NULL) return false; + if (ttable_find(table, 5) == NULL) return false; + + ttable_deinit(table); + return true; +} + +bool test_ttable_many_entries() { + ttable_t table; + ttable_init(&table, 16); + + for (u64 i = 0; i < 50000; i++) { + ttable_insert(table, .key = i * 7919, .depth = i % 64, .flag = TT_EXACT); + } + + for (u64 i = 0; i < 50000; i++) { + tentry_t *e = ttable_find(table, i * 7919); + + if (e == NULL) continue; + if (e->key != i * 7919) return false; + } + + ttable_deinit(table); + return true; +} #endif diff --git a/tests/generated.c b/tests/generated.c index 7de9c24..a605554 100644 --- a/tests/generated.c +++ b/tests/generated.c @@ -4,15 +4,18 @@ #include "../src/engine/moves/king.c" #include "../src/uci/command.c" -int total_test_count = 14; -bool (*tests[14])(void) = { +int total_test_count = 17; +bool (*tests[17])(void) = { test_fen_no_passant, test_fen_passant, test_starting_position, - test_empty_ttable, + test_ttable_empty, test_ttable_insert_and_find, test_ttable_wrong_key, test_ttable_update_existing, + test_bucket_collision, + test_ttable_replace_shallowest, + test_ttable_many_entries, test_perft_starting_position, test_perft_kiwipete_position, test_perft_position3, @@ -22,15 +25,18 @@ bool (*tests[14])(void) = { test_invalid_cmd_uci_cmd_t, }; -int max_test_name_size = 23; -char test_names[14][100] = { +int max_test_name_size = 25; +char test_names[17][100] = { "fen_no_passant", "fen_passant", "starting_position", - "empty_ttable", + "ttable_empty", "ttable_insert_and_find", "ttable_wrong_key", "ttable_update_existing", + "bucket_collision", + "ttable_replace_shallowest", + "ttable_many_entries", "perft_starting_position", "perft_kiwipete_position", "perft_position3", |