前回のTransposition Table編に続きます。
前回はTransposition Table実装をgpt-oss頼りに行ったという話で、当然ながら結構効果的なものでした。
ただ、Python実装なのでStockfishのような特殊なメモリ管理をしていないという話でしたが、この部分もgpt-ossに詳しく聞くことができました。
以下の回答が結構驚きです。
Stichfish準拠のTTとC++標準のunordered_mapのパフォーマンス比較として、ベンチマークプログラムとベンチマーク結果を出力してくれました。
以下、少し修正して動くようになったプログラムです。
#include <chrono>
#include <random>
#include <unordered_map>
#include <cstring>
#include <immintrin.h> // for _mm_clflush (optional)
using Key = uint64_t;
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
// ---- TT の最小実装 -------------------------------------------------
constexpr size_t ClusterSize = 4; // 4‑way
struct TTEntry {
uint16_t move;
uint8_t depth;
uint8_t genBound; // 2bit bound + 6bit generation
uint16_t key16;
};
struct TTCluster { TTEntry e[ClusterSize]; };
class SimpleTT {
size_t mask; // (clusterCount-1)
uint8_t generation = 0;
public:
explicit SimpleTT(size_t mb) {
size_t clusters = (mb * 1024 * 1024) / sizeof(TTCluster);
// 2 のべき乗に丸める
clusters = 1ULL << (63 - __builtin_clzll(clusters));
table.resize(clusters);
mask = clusters - 1;
}
// プローブだけ。ヒットしたらエントリへのポインタ、外れたら nullptr
TTEntry* probe(Key k) {
size_t idx = (k >> 16) & mask;
uint16_t k16 = uint16_t(k >> 48);
TTCluster& cl = table[idx];
for (int i = 0; i < ClusterSize; ++i)
if (cl.e[i].key16 == k16) return &cl.e[i];
// 置換エントリを探す（最古・浅いもの）
TTEntry* victim = &cl.e[0];
for (int i = 1; i < ClusterSize; ++i) {
TTEntry* e = &cl.e[i];
bool older = (e->genBound & 0x3F) < (victim->genBound & 0x3F);
bool shallower = (e->depth < victim->depth) &&
*1;
if (older || shallower) victim = e;
}
// クリアして返す
std::memset(victim, 0, sizeof(TTEntry));
victim->key16 = k16;
victim->genBound = generation; // generation だけ設定
return victim;
}
void incGen() { generation = (generation + 1) & 0x3F; }
};
// ---- ベンチマーク ---------------------------------------------------
int main() {
const size_t N = 1'000'000; // キー数
std::mt19937_64 rng(0xDEADBEEF);
for (auto &k : keys) k = rng();
// 1. TT
SimpleTT tt(64); // 64 MiB ≈ 1M エントリ
for (Key k : keys) tt.probe(k); // 予め全エントリを登録
auto t0 = std::chrono::high_resolution_clock::now();
uint64_t dummy = 0;
Key k = keys[i % N];
TTEntry* e = tt.probe(k);
dummy += e->key16; // 防止最適化
}
auto t1 = std::chrono::high_resolution_clock::now();
double ttTime = std::chrono::duration<double>(t1 - t0).count();
// 2. unordered_map
std::unordered_map<Key, uint16_t> umap;
umap.reserve(N * 2);
for (Key k : keys) umap.emplace(k, 0);
t0 = std::chrono::high_resolution_clock::now();
Key k = keys[i % N];
dummy += umap[k]; // 同様に dummy で最適化防止
}
t1 = std::chrono::high_resolution_clock::now();
double umapTime = std::chrono::duration<double>(t1 - t0).count();
printf("unordered_map: %.3f s (%.1f ns/op)\n", umapTime,
printf("dummy=%llu\n", (unsigned long long)dummy);
return 0;
}
LLMが吐くベンチマーク結果はもちろんいい加減なものですが、ベンチマークプログラムは少し修正しただけで意味のある動作をしており、3倍近い速度差が得られました。
それにしても他分野に比較して異常とも思えるほどStockfishには詳しいようです。
---
おまけ：
Go言語実装しているエンジン（俗称：地ビール）にも以前からTT実装してありましたが、独自実装から部分的にStockfish準拠にしたものに変更したものを作成しました。
全体のベンチマークにはあまり影響がないようですが、バージョン0.13としてそのうちFloodgateデビューすると思います。
*1:e->genBound & 0x3F) == (victim->genBound & 0x3F
