人工知能に深く考えさせるには、手抜きが必要です。もっといえば、「どうでもいいこと」を人工知能に考えさせないことです。

 前回は、将棋プログラムの先読みを盤面の全探索で行うアルゴリズムを説明しました。今回は全探索でなく、不要な探索を途中で打ち切る方法を見ていきます。これはゲーム木の探索を途中で打ち切り、ゲーム木の枝を刈ることになるので、「枝刈り」と呼ばれています。

評価関数と先読み、枝刈りの適用範囲は広い

 探索の枝刈りを説明する前に、将棋の思考プログラムの全体像をおさらいしましょう。盤面の評価関数、評価関数を使った先読み、そして今回見ていく枝刈りなどのゲーム理論を、人工知能のどこに、どのように適用するかをもう一度見ていきます。

 評価関数、先読み、枝刈りといったゲーム理論の技術は、とても適用範囲の広い技術です。もちろん、囲碁やリバーシなど、将棋と同じ「二人零和有限確定完全情報ゲーム」に適用できますが、二人でなくても、ゼロサムでなくても、乱数などを使っていても、評価関数や先読みの技術は使えます。

 例えば、相手の手の内が見えない麻雀でもポーカーでも使えます。それだけではなく、経済や政治など各種の意思決定システムから、分析・評価システムまで、幅広く使える技術です。いずれも、人工知能の大きな仕事の一つである「探索」における強い武器になります。

 経済や政治などの意思決定システムで使う場合、評価関数は現在の状況を全ての要因から分析するのではなく、制限された情報から分析することになります。先読みは、時間とともに変化する値を予測するときに使います。ただし、評価関数はより複雑になり、先読みもミニマックス法ではなく、もっと複雑な戦略を持った先読みになります。

 これから見ていく枝刈りももっとヒューリスティックス(経験や直感に基づく判断)を使ったものになるでしょう。図1にその様子を示します。

図1●評価関数と先読みの適用範囲
図1●評価関数と先読みの適用範囲
[画像のクリックで拡大表示]

 このように、評価関数、先読み、枝刈りは適用範囲の広い技術で、将棋を媒介としてこれらを学ぶのは重要です。是非、これらを学び、そして親しんでください。

効率的な探索のための枝刈りとは

 枝刈りとは、ミニマックス法で全探索するゲーム木の一部の枝を刈る(その探索を止める)ことです。

 枝刈りには、ミニマックス法と同じ結果になることを保証する安全な「後ろ向き枝刈り」と、ミニマックス法と違う結果になるかもしれない近似解を与える「前向き枝刈り」があります。前向きは少し危険な香りがしますね。

 後ろ向き枝刈りは、先読みの最終手から後ろ向きに前の手に戻って、並んでいる次の兄弟枝の枝刈りをすることから、この名前が付いています。前向き枝刈りは、ある手を指した時点の情報だけで、それ以降の探索を打ち切るので、このように呼ばれています。

 全探索では、あまりにも探索数が増え過ぎてしまうので、深い先読みができません。特に将棋の場合、着手可能な手のほとんどは悪手です。人間の思考は、悪手を読まない判断を一瞬で行うというより、その手を指すという想像もしていないでしょう。人工知能においても、全ての手を読むのはあまりにも非効率的です。後ろ向き枝刈りはもちろん、前向き枝刈りも駆使し、大量の枝を切り落とす必要があります。