枝刈り
探索止め
枝刈りとは、ミニマックス法で全探索するゲーム木の一部の枝を刈る（その探索を止める）ことです。
枝刈りには、ミニマックス法と同じ結果になることを保証する安全な「後ろ向き枝刈り」と、ミニマックス法と違う結果になるかもしれない近似解を与える「前向き枝刈り」があります。前向きは少し危険な香りがしますね。
後ろ向き枝刈りは、先読みの最終手から後ろ向きに前の手に戻って、並んでいる次の兄弟枝の枝刈りをすることから、この名前が付いています。前向き枝刈りは、ある手を指した時点の情報だけで、それ以降の探索を打ち切るので、このように呼ばれています。
全探索では、あまりにも探索数が増え過ぎてしまうので、深い先読みができません。特に将棋の場合、着手可能な手のほとんどは悪手です。人間の思考は、悪手を読まない判断を一瞬で行うというより、その手を指すという想像もしていないでしょう。人工知能においても、全ての手を読むのはあまりにも非効率的です。後ろ向き枝刈りはもちろん、前向き枝刈りも駆使し、大量の枝を切り落とす必要があります。
人工知能にムダな思考をさせない「枝刈り」の妙技