組合せ爆発とは
組合せ爆発とは、問題が少し大きくなるだけで、調べるべき場合の数が爆発的に増えてしまう現象のことです。たとえばチェスや将棋で「この先の指し手をすべて読む」としても、手数が伸びるごとに枝分かれが膨れ上がり、あっという間に天文学的な数になります。AIが「すべてを順に試す（総当たり）」だけでは賢く動けない理由が、ここにあるのです。
英語表記：combinatorial explosion
なぜ総当たりが通じなくなるのか
増え方が「かけ算」になるのが、爆発の正体です。二つの選択肢を20回くり返すだけで、その組み合わせは約100万通り。30回なら約10億通りにまで膨らみます。現実の問題はもっと枝が多いため、選択肢をすべて試す方法はすぐに破綻してしまうわけです。そこでAIは、見込みのありそうな手だけを優先して深く読むヒューリスティック（経験則）や、明らかに無駄な枝を切り落とす工夫を使います。A*探索のような賢い探し方が生まれた背景には、この組合せ爆発という壁がありました。
Topicチェスの対局は、宇宙の原子より多い？
1950年、情報理論の父と呼ばれるクロード・シャノンが、チェスでありうる対局の総数を見積もりました。その数、およそ10の120乗通り。これは観測できる宇宙にある原子の数（およそ10の80乗個といわれます）よりも、けた違いに多い数です。どんなに速いコンピュータを使っても、すべてを読み切ることはできません。だからこそチェスや囲碁のAIは「全部読む」のをあきらめ、読む手をうまく絞る方向へ進化してきたのですね。
関連用語
組合せ爆発に関するよくある質問
- 組合せ爆発が起きると、なぜAIにとって問題なのですか？
- 候補の数が現実的に計算しきれないほど増え、すべてを順に試す「総当たり」が使えなくなるためです。そこでAIは、見込みの高い選択肢だけを優先して調べる工夫で対処します。
- 組合せ爆発は、身近な例だとどんな場面で起きますか？
- 配送ルートの最適化や時間割づくりのように、組み合わせの数が選択肢とともに急増する問題で起きます。立ち寄り先が一つ増えるだけで経路の候補が一気に膨らむのが典型例です。
