問題 No.137
チェスや将棋などのゲーム木探索において、すべての分岐を網羅的に計算すると計算量が爆発してしまう。これを防ぐため、スコアが最大のものを選ぶ過程で、すでに判明しているスコアよりも明らかに小さいノードが出現した時点で、その先につながるノードの探索を途中で省略・カットする効率的なアルゴリズムを何というか。
【正解の解説】
アルファカット
αβ法における探索過程で、評価値がすでに見つかっているものよりも悪い場合に探索を切り上げるための判断基準の一つです。
スポンサーリンク
【その他の選択肢の解説】
ベータカット
αβ法における探索過程で、相手にとって都合の悪い選択肢が出た場合に探索を切り上げるための判断基準の一つです。
ヒューリスティック探索
経験則に基づいて効率的に解を探そうとする手法全般の総称です。
モンテカルロ木探索
ランダムな試行を繰り返すことで、どの手が有利かを統計的に推定するゲームAIの手法です。