編集(管理者用) | 差分 | 新規作成 | 一覧 | RSS | FrontPage | 検索 | 更新履歴

後ろ向き枝刈 - [[前向き枝刈]]は、見込みのなさそうな手を試行しない=読まないことで、少ない手を読むことで全体の速度をあげる方法であるが、後ろ向き枝刈は、[[MinMax]]と同じ結果を得られる程度に、局面の評価値などを参考に枝刈りをする手法である。

前向き枝刈?は、見込みのなさそうな手を試行しない=読まないことで、少ない手を読むことで全体の速度をあげる方法であるが、後ろ向き枝刈は、MinMaxと同じ結果を得られる程度に、局面の評価値などを参考に枝刈りをする手法である。

例えば、αβ法による枝刈りでは、MinMaxと全く結果が同じであることが保障される。

例えば、FutilityCutとして知られる手法には、以下のようなものがある。 葉に近いノードでは、適切に設定された幅(例えば、静止探索で行われる最大の駒得、評価値の変化)を加えた場合でも、α値を超えない・またはβ値を超えることが分かっているならば、完全に安全に枝刈りを行うことが出来る。ただし、この幅に関しては、あまりに大きくすると、効率があがらないため、少しの危険(完全なMinMax値を得られない可能性)は覚悟の上で、幅を小さめにとることもある。

なお、前向き枝刈を全く行わないプログラムは、一般に全幅探索?と呼ばれるが、後ろ向き枝刈りを全く行わないわけではない。

全幅探索を行う将棋プログラムとして、最も知名度が高いのはBonanzaだと思われるが、Bonanzaにも、αβ法FutilityCutNullMoveなどの手法は取り入れられている。