今回紹介するのはStockfish DDの置換表の実装です。
最新のStockfishの実装では置換表の1エントリーがStockfish DDからさらに節約されていますが、ハッシュキーのbit数を減らしてあるのでハッシュ衝突の確率が上がるため一概に良いとは言えません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 |
/* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. Stockfish is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see */ #ifndef TT_H_INCLUDED #define TT_H_INCLUDED #include "misc.h" #include "types.h" /// The TTEntry is the 128 bit transposition table entry, defined as below: // TTEntryは、128bitの置換表上の1エントリーで、以下のように定義されている。 /// /// key: 32 bit // 局面のハッシュキーの上位16bit /// move: 16 bit // 指し手 /// bound type: 8 bit // BOUND_LOWERとかUPPERとか /// generation: 8 bit // 置換表エントリーの世代 /// value: 16 bit // 探索をした結果の評価値 /// depth: 16 bit // そのときの探索深さ /// static value: 16 bit // 静的評価値 /// static margin: 16 bit // ？ 現在、未使用。以前のソースで使ってあった。 struct TTEntry { // このクラスのインスタンスはcallocで確保されるので、コンストラクタが呼び出されることはない。 // TTEntry*を得て、そこに対してsave()などで値を書き込んだりする。 // k : 局面のハッシュキーの上位16bit // v : 探索したときの結果の評価値 // b : BOUND // d : 残り探索depth // m : このnodeのベストの指し手 // g : このentryの世代 // ev : 静的評価値 void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value ev) { key32 = (uint32_t)k; move16 = (uint16_t)m; bound8 = (uint8_t)b; generation8 = (uint8_t)g; value16 = (int16_t)v; depth16 = (int16_t)d; evalValue = (int16_t)ev; } // 世代の設定用 void set_generation(uint8_t g) { generation8 = g; } // --- 以下、getter // 局面のhashkeyの上位32bit uint32_t key() const { return key32; } // 探索残り深さ Depth depth() const { return (Depth)depth16; } // このnodeのベストの指し手 Move move() const { return (Move)move16; } // 探索の結果の評価値 Value value() const { return (Value)value16; } // BOUND_LOWERとかUPPERとか Bound bound() const { return (Bound)bound8; } // 世代(8bit) int generation() const { return (int)generation8; } // このnodeの静的評価値 Value eval_value() const { return (Value)evalValue; } private: // 局面のハッシュキーの上位32bit uint32_t key32; // 指し手16bit uint16_t move16; // BOUNDを表現する1バイト、置換表のentryの世代用カウンター uint8_t bound8, generation8; // 評価値、そのときの探索残り深さ、その局面での静的評価スコア int16_t value16, depth16, evalValue; // これ、ここにダミーの変数ないけど本当に16bit paddingされるの？ // gccでは4の倍数になるようだが、C++的にはアウトでは。 }; /// A TranspositionTable consists of a power of 2 number of clusters and each /// cluster consists of ClusterSize number of TTEntry. Each non-empty entry /// contains information of exactly one position. Size of a cluster shall not be /// bigger than a cache line size. In case it is less, it should be padded to /// guarantee always aligned accesses. // 置換表 // TranspositionTableは、2の累乗のclusterからなる。それぞれのclusterは、 // TTEntry(置換表のエントリーひとつを表す構造体)のClusterSizeの数によって決まる。 // それぞれのclusterはcache lineサイズを上回るべきではない。 // 逆に、それを下回るケースにおいては、alignされたアクセスを常に保証するために // パディングされるべきである。 class TranspositionTable { // 一つのclusterは、16バイト(= sizeof(TTEntry))×ClusterSize = 64バイト。 // Clusterは、rehashのための連続したTTEntryの塊のこと。 static const unsigned ClusterSize = 4; // A cluster is 64 Bytes public: // ToDo : memをコンストラクタでゼロ初期化していないように見えるが.. // globalでしかこのインスタンスを使わないからゼロ初期化されているということを仮定しているのか…。 // なんか危なっかしいコードだな…。 ~TranspositionTable() { free(mem); } // 置換表を新しい探索のために掃除する。(generationを進める) void new_search() { ++generation; } // 置換表を調べる。置換表のエントリーへのポインター(TTEntry*)が返る。 // エントリーが登録されていなければNULLが返る。 const TTEntry* probe(const Key key) const; // TranspositionTable::first_entry()は、与えられた局面(のハッシュキー)に該当する // 置換表上のclusterの最初のエントリーへのポインターを返す。 // 引数として渡されたkey(ハッシュキー)の下位ビットがclusterへのindexとして使われる。 TTEntry* first_entry(const Key key) const; // 置換表上のtteのエントリーの世代を現在の世代(this->generation)にする。 void refresh(const TTEntry* tte) const; // TranspositionTable::set_size()は、置換表のサイズをMB(メガバイト)単位で設定する。 // 置換表は2の累乗のclusterで構成されており、それぞれのclusterはTTEnteryのClusterSizeで決まる。 // (1つのClusterは、TTEntry::ClusterSize×16バイト) void set_size(size_t mbSize); // TranspositionTable::clear()は、ゼロで置換表全体をクリアする。 // テーブルがリサイズされたときや、ユーザーがUCI interface経由でテーブルのクリアを // 要求したときに行われる。 void clear(); // 置換表に値を格納する。 // key : この局面のハッシュキー。 // v : この局面の探索の結果得たスコア // b : このスコアの性質。 // BOUND_NONE → 探索していない(DEPTH_NONE)ときに、最善手か、静的評価スコアだけ置換表に突っ込みたいときに使う。 // BOUND_LOWER → fail-low // BOUND_UPPER → fail-high // BOUND_EXACT → 正確なスコア // d : このスコア・指し手を得たときの残り探索深さ // m : 最善手 // statV : 静的評価(この局面で評価関数を呼び出して得た値) void store(const Key key, Value v, Bound type, Depth d, Move m, Value statV); private: // 置換表のindexのmask用。 // table[hashMask & 局面のhashkey] がその局面の最初のentry // hashMask + 1 が確保されたTTEntryの数 uint32_t hashMask; // 置換表の先頭を示すポインター(確保したメモリを64バイトでアラインしたもの) TTEntry* table; // 置換表のために確保した生のメモリへのポインター。開放するときに必要。 void* mem; // 置換表のEntryの、いま使っている世代。 // これをroot局面が進むごとにインクリメントしていく。 uint8_t generation; // Size must be not bigger than TTEntry::generation8 }; // globalな置換表 extern TranspositionTable TT; /// TranspositionTable::first_entry() returns a pointer to the first entry of /// a cluster given a position. The lowest order bits of the key are used to /// get the index of the cluster. // TranspositionTable::first_entry()は、与えられた局面(のハッシュキー)に該当する // 置換表上のclusterの最初のエントリーへのポインターを返す。 // 引数として渡されたkey(ハッシュキー)の下位ビットがclusterへのindexとして使われる。 inline TTEntry* TranspositionTable::first_entry(const Key key) const { return table + ((uint32_t)key & hashMask); } /// TranspositionTable::refresh() updates the 'generation' value of the TTEntry /// to avoid aging. Normally called after a TT hit. // TranspositionTable::refresh()は、TTEntryが年をとる(世代が進む)のを回避するため // generationの値を更新する。普通、置換表にhitしたあとに呼び出される。 // TranspositionTable::generationの値が引数で指定したTTEntryの世代として設定される。 inline void TranspositionTable::refresh(const TTEntry* tte) const { const_cast } #endif // #ifndef TT_H_INCLUDED |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 |
/* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) Copyright (C) 2008-2013 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. Stockfish is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see */ #include #include #include "bitboard.h" #include "tt.h" // 置換表はglobalに配置。 TranspositionTable TT; // Our global transposition table /// TranspositionTable::set_size() sets the size of the transposition table, /// measured in megabytes. Transposition table consists of a power of 2 number /// of clusters and each cluster consists of ClusterSize number of TTEntry. // TranspositionTable::set_size()は、置換表のサイズをMB(メガバイト)単位で設定する。 // 置換表は2の累乗のclusterで構成されており、それぞれのclusterはTTEnteryのClusterSizeで決まる。 // (1つのClusterは、TTEntry::ClusterSize×16バイト) // mbSizeはClusterSize[GB]までのようだ。ClusterSize = 16だから16GBまで。 void TranspositionTable::set_size(size_t mbSize) { // MB単位で指定してあるので左20回シフト // TTEntryの数が32bitでindexできる範囲を超えているとまずい。 // TTEntryが128bit(16バイト)なので64GBが置換表用のサイズの上限。 // ToDo : このassert本当に要るのか？64GB以上確保できてもいいように思うのだが…。 assert(msb((mbSize << 20) / sizeof(TTEntry)) < 32); // mbSize[MB] / clusterのサイズのうち、最上位の1になっているbit以外は端数とみなして0にした個数だけ // clusterを確保する。 uint32_t size = ClusterSize << msb((mbSize << 20) / sizeof(TTEntry[ClusterSize])); // 現在確保中の置換表用のメモリと等しいならば再確保は行わない if (hashMask == size - ClusterSize) return; // hashMaskは、sizeがClusterSize×010....0bみたいな数なので、ここからClusterSizeを引き算すると // 0011....1bみたいな数になる。これをmaskとして使う。 // 逆に、確保してあるTTEntryの数は、hashMask + ClusterSizeである。 hashMask = size - ClusterSize; // 前回確保していたメモリを開放 free(mem); // 確保しなおす。callocを使ってあるのはゼロクリアするため。 // あと、CACHE_LINE_SIZEは、64。余分に確保して、64でアラインされたアドレスを得るため。 mem = calloc(size * sizeof(TTEntry)+CACHE_LINE_SIZE - 1, 1); if (!mem) { std::cerr << "Failed to allocate " << mbSize << "MB for transposition table." << std::endl; exit(EXIT_FAILURE); } // memから64バイトでアラインされたアドレスを得て、それをtableとして使う。 table = (TTEntry*)((uintptr_t(mem) + CACHE_LINE_SIZE - 1) & ~(CACHE_LINE_SIZE - 1)); } /// TranspositionTable::clear() overwrites the entire transposition table /// with zeroes. It is called whenever the table is resized, or when the /// user asks the program to clear the table (from the UCI interface). // TranspositionTable::clear()は、ゼロで置換表全体をクリアする。 // テーブルがリサイズされたときや、ユーザーがUCI interface経由でテーブルのクリアを // 要求したときに行われる。 void TranspositionTable::clear() { // hashMask + ClusterSizeになっている理由はTranspositionTable::set_sizeにある説明を読むこと。 std::memset(table, 0, (hashMask + ClusterSize) * sizeof(TTEntry)); } /// TranspositionTable::probe() looks up the current position in the /// transposition table. Returns a pointer to the TTEntry or NULL if /// position is not found. // 置換表を調べる。置換表のエントリーへのポインター(TTEntry*)が返る。 // エントリーが登録されていなければNULLが返る。 const TTEntry* TranspositionTable::probe(const Key key) const { // 最初のエントリーを取得 const TTEntry* tte = first_entry(key); // 上位32bitが、置換表に登録されているhashの32bitと一致するのかを確認する。 uint32_t key32 = key >> 32; // ClusterSize分だけrehashされると解釈。 for (unsigned i = 0; i < ClusterSize; ++i, ++tte) if (tte->key() == key32) return tte; // 見つかったならそれを返す。さもなくばnull return nullptr; } /// TranspositionTable::store() writes a new entry containing position key and /// valuable information of current position. The lowest order bits of position /// key are used to decide on which cluster the position will be placed. /// When a new entry is written and there are no empty entries available in cluster, /// it replaces the least valuable of entries. A TTEntry t1 is considered to be /// more valuable than a TTEntry t2 if t1 is from the current search and t2 is from /// a previous search, or if the depth of t1 is bigger than the depth of t2. // TranspositionTable::store()は現在の局面の、局面ハッシュキーと価値のある情報を新しいエントリーに書き込む。 // 局面ハッシュキーの下位のオーダーのbitは、どこにclusterを格納すべきかを決定するのに使われる。 // 新しいエントリーが書き込まれるときに、利用できる空のエントリーがcluster上になければ // もっとも価値の低いエントリーを置き換える。 // ２つのTTEntry t1,t2があるとして、t1が現在の探索で、t2が以前の探索(世代が古い)だとか、 // t1の探索深さのほうがt2の探索深さより深いだとかする場合は、t1のほうがt2より価値があると考えられる。 // 置換表に値を格納する。 // key : この局面のハッシュキー。 // v : この局面の探索の結果得たスコア // b : このスコアの性質。 // BOUND_NONE → 探索していない(DEPTH_NONE)ときに、最善手か、静的評価スコアだけ置換表に突っ込みたいときに使う。 // BOUND_LOWER → fail-low // BOUND_UPPER → fail-high // BOUND_EXACT → 正確なスコア // d : このスコア・指し手を得たときの残り探索深さ // m : 最善手 // statV : 静的評価(この局面で評価関数を呼び出して得た値) void TranspositionTable::store(const Key key, Value v, Bound b, Depth d, Move m, Value statV) { int c1, c2, c3; TTEntry *tte, *replace; // 局面ハッシュキーの上位32bitはcluster(≒置換表のエントリー)のなかで用いる。 // また下位bitをclusterへのindexとして用いる。 uint32_t key32 = key >> 32; // Use the high 32 bits as key inside the cluster // clusterの先頭のTTEntryを得る tte = replace = first_entry(key); // clusterのそれぞれの要素について.. for (unsigned i = 0; i < ClusterSize; ++i, ++tte) { // 空のエントリーもしくはkeyが一致するエントリーであるなら.. // ToDo : これtte->key() == 0なら、空のエントリーという扱いになっているが、 // これ、偶然、keyの上位32bitが0になる場合、空のエントリーとみなされて上書きされてしまうではないのか…。 // レアケースなのでいいのか？ if (!tte->key() || tte->key() == key32) // Empty or overwrite old { // いま、指し手がないならば指し手を何にせよ潰さずに保存しておく。 // ToDo : これ、偶然keyの上位32bitが0な局面が書かれていると、そこのmoveが使われてしまうことになるのでは…。 // ここで非合法手になってしまうのどうなんだろう…。 if (!m) m = tte->move(); // Preserve any existing ttMove // ともかく、空か、この局面用の古いエントリーが見つかったのでそこを使う。 // ToDo : 反復深化では同じエントリーは基本的には以前の残り探索深さより深いはずなので上書きして問題ない..のか..？ // 別経路でこの局面に突入したときに…どうなんだろう…。 // 探索深さが置換表のエントリー上に書かれていた探索深さより浅い探索においては // 値を保存するためにこの関数を呼びださなければいいわけか。 replace = tte; break; } // Implement replace strategy // 一番価値の低いところと置換する // replaceはClusterのなかでいま一番価値が低いとされるTTEntry // これ、都度replace->XXXと比較になっているのが少し気持ち悪いが、綺麗なコードなのでまあいいのか…。 // いま置換予定のentryをreplaceポインターが指しているものとして、 // replaceのgenerationが、現在のgenerationと一致するならば +2 // tteのgenerationが現在のgeneration、もしくはtteがBOUND_EXACTなら-2 // tteの探索深さのほうがreplaceの探索深さより浅いなら +1 c1 = (replace->generation() == generation ? 2 : 0); c2 = (tte->generation() == generation || tte->bound() == BOUND_EXACT ? -2 : 0); c3 = (tte->depth() < replace->depth() ? 1 : 0); if (c1 + c2 + c3 > 0) replace = tte; // ケース1) generationがreplace,tteともに最新である場合。 // replaceのほうが探索深さが同じか浅いならreplace(最初に見つかったほう)を置き換える。 // (なるべく先頭に近いところを置き換えたほうがprobeが早く終るため) // ケース2) generationがreplaceは最新だが、tteがBOUND_EXACTである場合。 // replaceを置き換える。 // ToDo : このロジックどうなん？ // 探索深さが深いほうという重みが低いので、探索深さが深かろうとも、世代が古いと // 上書きされてしまう。探索深さが深いときの重みをもう少し大きくして、また、 // 世代差2までは、加点するなどしてバランスをとったほうがいいのでは…。 } // 置換対象が決まったのでそこに対して値を上書きしてしまう。 // このgenerationは、このTranspositionTableが保持しているメンバー変数。 replace->save(key32, v, b, d, m, generation, statV); } |
いつも参考にさせてもらっています。
bonanzaの置換表ではエントリーを64ビットにパックしていましたが、stockfishではされていないのですね。
以前指し手構造体は一つの変数にパックしたほうがよいという話を見たことがあったのですが、ハッシュエントリーはパックしないほうがいい理由などはあるのでしょうか？
置換表の局所的にアクセスするメモリ、どうせL1/L2 cacheには収まらないのが普通ですから、packして小さなメモリにおさめても、さほど速度には影響せず、また、メモリ自体はいまごろのPCですとふんだんにありますからメモリ使用効率はあまり問題ではなく、unpackに要するコストが増大するのが許せないということですね。lockless hashのようなものを実装するときは、1エントリーが小さいに越したことはないと思いますが、Stockfishではlockless hash採用してませんし…。(他スレッドから壊したい放題！)