# 反復深化
反復深化は、探索をいきなり深く読むのではなく、浅い深さから順に繰り返し深くしていく手法である。
現在の将棋AIでは、[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)を運用するための基本フレームワークになっている。
## 概要
反復深化では、
1. まず 1 手読みを行う
2. 次に 2 手読みを行う
3. さらに 3 手、4 手と深くしていく
という流れで探索する。
一見すると、同じ局面を何度も読むので無駄が多そうに見える。
しかし実際には、浅い探索で得た情報が次の反復で役立つため、
固定深さを一気に読むより都合がよいことが多い。
## なぜ速くなるのか
反復深化が有利なのは、浅い反復で得た
- [Principal Variation](/shogi/shogiwiki/search/principal-variation/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)の最善手
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)用の履歴情報
が、次の深さで強力な先読み順序になるからである。
とくに[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)は良い手から先に読むほど効率が上がるため、
前の反復の結果をそのまま次の反復に流用できる反復深化は非常に相性がよい。
## 時間管理との関係
反復深化は[時間管理](/shogi/shogiwiki/search/time-management/)にも重要である。
探索途中で時間切れになっても、
直前の反復で求めた最善手が残っているため、
少なくとも「前の深さでは最善だった手」を返せる。
この性質により、実戦エンジンでは探索の打ち切りがしやすい。
## 実装例
```cpp
Move iterativeDeepening(Position root, int maxDepth) {
Move bestMove = MOVE_NONE;
for (int depth = 1; depth <= maxDepth; ++depth) {
SearchResult result = searchRoot(root, depth);
bestMove = result.bestMove;
if (timeUp()) {
break;
}
}
return bestMove;
}
```
実戦的には、`searchRoot` の中で
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)、
[aspiration windows](/shogi/shogiwiki/search/aspiration-windows/)、
[置換表](/shogi/shogiwiki/search/transposition-table/)などを併用する。
## 将棋AIでの位置づけ
反復深化は単なる「何度も読む手法」ではなく、
- 時間切れ耐性
- 手の並べ替え強化
- 置換表利用
- Principal Variation 表示
をまとめて支える枠組みである。
そのため、多くの将棋AIで探索ループの中心に置かれている。
## 注意点
- 反復ごとの再探索があるため、周辺の実装が弱いと無駄が増える
- 置換表や履歴ヒューリスティクが弱いと利点を十分に活かせない
- 時間管理と連動していないと実戦では使いにくい
## 関連項目
- [探索](/shogi/shogiwiki/search/)
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [時間管理](/shogi/shogiwiki/search/time-management/)
## 参考にしたホームページ
- [Chessprogramming Wiki: Iterative Deepening](https://www.chessprogramming.org/Iterative_Deepening)
- [Chessprogramming Wiki: Search](https://www.chessprogramming.org/Search)
- [コンピュータ将棋のアルゴリズム HTML版](http://usapyon.game.coocan.jp/ComShogi/index.html)