組合せ爆発とは

組合せ爆発は、探索・推論の研究で、すべてを調べ尽くす方法の限界として早くから意識されてきました。

なぜ急に増えるのか

1回の選択にb通りの選択肢があり、それをd回続けると、選び方の組合せはbのd乗通りになります。毎回10通りの選択肢がある場合、5手先までなら10万通りですが、10手先までなら100億通りです。手数が2倍になっただけで、候補は10万倍に増えます。n個のものを並べる順番を決める問題では、候補はnの階乗通りになります。囲碁の19路盤では、ルール上ありうる局面の数だけで約2.1×10の170乗あると計算されています。

計算機を速くしても解決しない

計算速度を10倍にしても、毎回10通りの選択肢がある例なら、同じ時間で読める手数は1手増えるだけです。

AI研究の歴史との関係

第1次AIブームの探索・推論は、迷路やパズルのようなトイ・プロブレムは解けても、現実の複雑な問題では候補が膨大になって行き詰まりました。1973年に英国で公表されたライトヒル報告は、AI研究で期待外れが続いた一般的な原因として、組合せ爆発の影響を十分に認識していなかったことを挙げています。

対処の工夫

すべてを調べる代わりに、範囲を絞る方法が発展しました。結果に影響しない枝を省くαβ法、経験則（ヒューリスティック）で有望な候補から調べる方法、ランダムな試行の勝率で局面を評価するモンテカルロ法などです。

似た言葉との違い

次元の呪いは、特徴量の次元が増えると必要なデータ量や計算量が急増することです。フレーム問題は、無数の事柄から関係のあることだけを選び出す難しさを指します。組合せ爆発は探索で調べる候補が増える話、次元の呪いは学習に必要なデータが増える話、フレーム問題は何を考えるべきかを決められない話です。

覚え方

「選択肢が掛け算で増え、計算機の速さでは追いつかない」と覚えます。