Source of ハッシュテーブル hash-table

  # ハッシュテーブル

ハッシュテーブルは、キーから高速に値を引くためのデータ構造である。
将棋AIでは主に[置換表](/shogi/shogiwiki/search/transposition-table/)として使われるが、
評価や持ち駒構成などの補助表にも応用される。

## 概要

ハッシュテーブルでは、

- キー
  ある対象を識別する値
- ハッシュ関数
  キーを配列添字へ写す関数
- バケットまたはエントリ
  実際に値を保存する場所

を組み合わせて高速な参照を行う。

探索では、

- 局面
- 材料構成
- pawn / 歩構造

などをキーにして、すでに計算した結果を再利用する。

## 探索での主な使い道

### 置換表

もっとも重要なのが[置換表](/shogi/shogiwiki/search/transposition-table/)である。
[ゾブリストハッシュ](/shogi/shogiwiki/search/zobrist-hashing/)などの局面キーを使って、

- スコア
- 深さ
- bound 種別
- 最善手

を保存する。

### 評価ハッシュ

[評価関数](/shogi/shogiwiki/search/evaluation-function/)が高価な場合は、
評価結果だけを保存するハッシュテーブルを持つこともある。

### 材料・構造ハッシュ

チェスでは material hash や pawn hash が有名だが、
将棋でも持ち駒や駒組みのまとまりに対して補助表を持つ発想は応用できる。

## 実装例

```cpp
struct HashEntry {
    uint64_t key;
    int value;
};

HashEntry table[TABLE_SIZE];

HashEntry* probe(uint64_t key) {
    return &table[key % TABLE_SIZE];
}
```

実戦的には、

- 1 バケットに複数エントリを持つ
- 深い情報を優先して残す
- 世代管理を入れる

といった工夫が入る。

## 衝突

ハッシュテーブルでは、異なるキーが同じ場所へ落ちる衝突が起こる。
そのため、

- key を本体にも保存して照合する
- cluster で複数候補を持つ
- 置換戦略を決める

といった設計が必要になる。

## 将棋AIでの位置づけ

将棋AIでは分岐数が大きく、同じ種類の計算を何度も行いやすい。
そのためハッシュテーブルは、単なる高速化ではなく探索全体の基盤といえる。

## 注意点

- サイズが小さいと衝突が増えて効果が落ちる
- 大きすぎるとメモリ帯域やキャッシュ効率が悪化する
- 並列探索では共有時の競合や NUMA も問題になる

## 関連項目

- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [ゾブリストハッシュ](/shogi/shogiwiki/search/zobrist-hashing/)
- [並列探索](/shogi/shogiwiki/search/parallel-search/)
- [評価関数](/shogi/shogiwiki/search/evaluation-function/)

## 参考にしたホームページ

- [Chessprogramming Wiki: HASH Table](https://www.chessprogramming.org/Hash_Table)
- [Chessprogramming Wiki: Transposition Table](https://www.chessprogramming.org/Transposition_Table)
- [Chessprogramming Wiki: Material HASH Table](https://www.chessprogramming.org/Material_Hash_Table)
ハッシュテーブル hash-table hash-table
