2011/01/27
■ 探索の改良
コンピューター将棋の進歩２より次の一手問題第１問で、深さ8固定。
- 枝刈なし
| ノード数 | 静止探索ノード数 | NPS | 総思考時間 |
|---|---|---|---|
| 660919 | 8460594 | 841080.0 | 58.4秒 |
aspiration windowによる反復深化探索、null-move pruning、多重反復深化だけ使用。
- 枝刈あり
| ノード数 | 静止探索ノード数 | NPS | 総思考時間 |
|---|---|---|---|
| 59615 | 485849 | 571765.2 | 3.1秒 |
総思考時間は反復深化探索すべての時間
※NPSには静止探索ノード数も含む
- 枝刈内訳(回数)
| Null-prune | LMR1 | LMR2 | Futility1 | Futility2 | Futility3 |
|---|---|---|---|---|---|
| 2057 | 2461 | 9290 | 42780 | 35465 | 309484 |
どちらも静止探索は最大12段。ただし4段目からは歩を取る成らない手は読まない、深さ8段目からは同〜の手しか読まない。
aspiration windowははじめは歩価値の2/3枚の幅で、feilしたときは桂1枚の幅に広げる。それでもfeilしたときはINFまで広げる。
Null-move pruneはdepthが2以上で行い、depthが6以上でR=3、それ以外R=2。
LMR1はPVノードでdepthが2以上でオーダリング順depth+8手目以上は1手浅く読む。
LMR2は非PVノードでdepthが2以上でオーダリング順depth+4手目以上は1手浅く読む。また、オーダリング14手目以上は2手浅く読む。
LMRは成る手、取る手、王手、キラー手では行わない。
Futility1は非PVノードでdepthが1のとき、手の簡易評価値がalpha以下のときに読まない。
Futility2は非PVノードでdepthが2のとき、手の簡易評価値+マージン(歩2枚分)がalpha以下のときに読まない。
Futility3は静止探索内で手の評価値がalpha以下のときに読まない。
Futility pruneは成る手、取る手、王手、キラー手では行わない。
PVノードでdepthが3以上でハッシュの手が無いときは多重反復深化。
非PVノードでdepthが5以上でハッシュの手が無く、現局面の評価値が桂損未満のときは多重反復深化。
まだまだ調整は必要だ。
