反復深化法
概念とその効果
様々な探索法において、どの深さまで探索するかは非常に難しい問題になります。 もし探索が浅すぎると本当の最善手を見つける前に指し手を決定してしまうし、 もし探索が深すぎると探索している最中に時間切れになってしまいます。 また、探索する深さが一定だと地平線効果が問題になってきます。 反復深化法を用いれば、これらの問題を効率的に解決することができます。反復深化法の考え方は、まずは探索する深さを1として探索し、 次に深さを2として探索し…というように少しずつ探索する深さを深くしていきます。
深さn-1で探索した後深さnで探索するなら、 深さn-1を2回探索することになって探索する時間が無駄になる気がします。 ところが、深さnの探索を深さn-1での探索結果で良いとされた着手から行うようにすると、 枝刈りが多く発生し、結果として探索時間の短縮につながります。 また、深さnを探索中に探索を中断されても深さn-1での最善手は分かっているため、 最善手を見逃す可能性も小さくなります。
動きの例
ここではαβ法に反復深化法を組み込んだ例を取り上げます。 まずは、深さ1として探索を行います。 現在は自分の手番なので、最も大きい値(6)を採用します。
| 自分の手番 | 6 | ||||||||||||||||
 |
 |
 |
|||||||||||||||
| 相手の手番 | -1 | -5 | 6 | ||||||||||||||
次に、深さ2として探索を行います。 探索を行うのは深さ1での最善手(右端)から行い、 その結果、ルートの仮評価が4になります。
| 自分の手番(α=4) | 4 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | ？ | ？ | 4 | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | 8 | 4 | ||||||||||||||
次に左端の手を探索します。 ここでは、葉ノードにおいて-2という値が出た時点でα刈りが行われます。
| 自分の手番(α=4) | 4 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | ？ | 4 | ||||||||||||||
|
|
|
|
|
|
||||||||||||
| 自分の手番 | 5 | -2 | ？ | 5 | 8 | 4 | |||||||||||
最後に真中の手を探索します。 ここでは葉ノードにおいて1という値が出た時点でα刈りが行われます。
| 自分の手番(α=4) | 4 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | 1 | 4 | ||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||
| 自分の手番 | 5 | -2 | ？ | 1 | ？ | ？ | 5 | 8 | 4 | ||||||||
以上のように、αβ法だけのときより多く枝刈りがされていることが分かります。
