ブルートフォースとは

ブルートフォースは、英語で「力ずく」という意味です。答えの候補を、賢い絞り込みをせずに片端から試していく方法を指します。日本語では「総当たり」「しらみつぶし」とも呼ばれます。

強み

すべての候補を漏れなく調べるので、候補の数が有限なら、解があれば必ず見つかります。最短の手順や最善の手のように、最もよい答えを確実に求めたいときにも使えます。手順が単純で、問題についての特別な知識がいらない点も利点です。幅優先探索や深さ優先探索で探索木を最後までたどるのも、この考え方にもとづいています。

弱点は組合せ爆発

調べる候補の数は、問題が大きくなると急激に増えます。1つの局面で選べる手がb通りで、d手先まで読むなら、手順の数はbのd乗です。手が30通りで10手先なら、約5.9×10の14乗通りになります。クロード・シャノンは1950年の論文で、チェスの初期局面から考えられる手順の数を10の120乗程度と見積もりました。このように候補が爆発的に増えて調べきれなくなる現象を、組合せ爆発と呼びます。

総当たりを避ける工夫

そこで、ゲームや探索の研究では、調べる範囲を減らす方法が考えられてきました。

• αβ法：Mini-Max法と同じ結果を保ったまま、結果に影響しない枝を刈り込みます。
• 評価関数：先読みを途中で打ち切り、局面のよしあしを数値で見積もります。
• モンテカルロ法：ランダムな試行を多数繰り返し、その結果から手のよしあしを推定します。

1997年にチェスの世界チャンピオンに勝ったIBMのディープブルーも、専用のハードウェアで膨大な局面を調べました。ただし、枝刈りや評価関数と組み合わせており、終局までのすべての手順を調べたわけではありません。

なお、情報セキュリティの分野では、パスワードを総当たりで試す攻撃をブルートフォース攻撃と呼びます。

覚え方

「確実だが、数が増えると終わらない」のがブルートフォースです。