新規作成 | 一覧 | RSS | FrontPage | 検索 | 更新履歴

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

差分表示


神待ち少女を助けられるのは貴方しかいません。是非近所でうろうろしている少女を助けてあげてください。http://www.reinbow-now.info/
[[前向き枝刈]]は、見込みのなさそうな手を試行しない=読まないことで、少ない手を読むことで全体の速度をあげる方法であるが、後ろ向き枝刈は、[[MinMax]]と同じ結果を得られる程度に、局面の評価値などを参考に枝刈りをする手法である。

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


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

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

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