G検定（ジェネラリスト検定） 人工知能とその動向 練習問題 第8問: 2人が交互に手を指すゲームの探索で使われるMini-Max法とαβ法の説明として、最も適切なものはどれか。

正解: 1. αβ法は、Mini-Max法と同じ評価値を求めながら、最善の手順に関わらないと分かった枝の評価を省いて探索量を減らす

肢1が正解です。Poole・Mackworthの教科書（第3版）は、Mini-Max法の探索木のうち、最適な手順に含まれないと示せる部分は刈り込めるとし、αβ法はαとβの値を渡しながら深さ優先で探索して枝を刈る方法だと説明しています。刈り込んでも、根の評価値はMini-Max法で木全体を調べたときと同じになります。肢2は、αβ法が別の手を選ぶとしている点が誤りです。肢3は逆で、自分（MAX）は評価値が最大の手を、相手（MIN）は最小の手を選ぶと仮定します。肢4について、同書は刈り込める量は子を調べる順番に左右され、MAXでは値の高い子、MINでは値の低い子を先に調べるとよく効くとしています。実際の多くのゲームではαβ法でも木全体を調べきれず、途中の局面を評価関数で見積もります。

関連キーワード: Mini-Max法・αβ法・探索木