αβ法 (G検定)

2026年8月12日2026年9月2日

G検定

1. 定義と概要

αβ法（アルファ・ベータ法、alpha-beta pruning）とは、ミニマックス法に基づくゲーム木探索において、最終的な最善手の判断に影響を与えないと判明した枝の探索を打ち切ることで、計算量を削減する手法です。ここでいうミニマックス法とは、自分の得点を最大に、相手の得点を最小にする選択を交互に読んでいく、ゲームの手を決める基本的な探索方法を指します。ゲーム木は、指せる手を枝分かれさせて描いた、次の一手からその先の展開までを表す木の形の図です。

この打ち切りは枝刈り（調べても結論が変わらないと分かった選択肢を、それ以上調べずに切り捨てること）と呼ばれます。枝刈りをしても、ミニマックス法と全く同じ最善手にたどり着く点が特徴で、結論を変えずに計算だけを減らすアルゴリズムといえます。

将棋やチェスのようなボードゲームAIの探索エンジンで長く使われてきた手法です。日本の将棋プログラムBonanza（2005年以降の将棋ソフトに影響を与えた対局プログラム）にも、この手法をベースにした探索エンジンが採用されてきました。

ミニマックス法は、自分の得点を最大化し相手の得点を最小化するという交互の選択を、ゲーム木の末端（葉ノード）まで読み切って最善手を決める手法です。しかし、調べるノードの数は手を読む深さに応じて指数関数的に増えていきます。

すべてのノードを愚直に評価すると計算コストが膨大になるという課題に対し、αβ法は探索の途中で得られた下限（α値）と上限（β値）という2つの目安を使い、それより先を調べても結論が変わらないと分かった枝の計算を省略する仕組みです。この仕組みによって、限られた計算資源や持ち時間の中でも、より深い手までゲーム木を読み進めることが可能になります。

2. 試験対策ポイント

G検定でまず論点になるのは、α値とβ値という2つの指標の役割の違いです。α値は自分の手番（MAXノード。自分の得点を最大にしようとする手番を表す、ゲーム木上の分岐点）でこれまでに見つかった最大のスコアを表し、β値は相手の手番（MINノード。相手の得点を最小にしようとする手番を表す、ゲーム木上の分岐点）で相手が許容できる最小のスコアを表します。

この2つの値を使った枝刈りが、αカットとβカットです。自分の手番で切るものをαカットと呼び、相手の手番で切るものをβカットと呼びます。整理すると、次の対応になります。

項目	αカット	βカット
発生する手番	自分の手番（MAXノード）	相手の手番（MINノード）
基準になる値	α値＝これまでに見つかった最大のスコア	β値＝相手が許容できる最小のスコア
打ち切る枝	α値を下回ると分かった枝	β値を上回ると分かった枝

G検定公式テキストはこの2つを手番の違いで整理しており、どちらの手番のカットかを取り違えないことが重要な論点です。

枝刈りを行っても、ミニマックス法と同じ最善手にたどり着くという前提は、あわせて整理しておきたいところです。αβ法は結論を変えずに計算量だけを減らす手法である点は、取り違えやすい典型です。また、探索する枝の順番によってもカットできる枝の数は変わります。有力な手から先に調べるほど、後続の枝が早期にカットされやすくなるという性質があり、探索の効率は手を調べる順番にも左右されます。

MAXノード、MINノード、評価関数（ある局面がどれくらい有利かを数値で表すための計算式）、深さ優先探索（ある枝を行き止まりまで先に調べ切ってから、次の枝に移る調べ方）は、いずれもαβ法に関わる関連用語です。これらはαβ法の仕組みを説明する一連の用語として、まとめて押さえておきたいところです。これらの用語がそれぞれ何を指すかを整理しておくと、α値とβ値の更新やαカット・βカットの判定を、ゲーム木の図と結びつけて理解しやすくなります。

3. 関連概念との比較・相違点

Mini-Max法との最大の違いは、たどり着く結論ではなく計算量です。Mini-Max法はゲーム木の全ノードを評価するのに対し、αβ法は最終的な結論に影響しない枝を省略する分だけ計算量を抑えられ、同じ最善手に到達します。両者の間には、探索するノードの数という点で明確な差があります。ミニマックス法そのものの読み方や仕組みは別の記事で詳しく扱うため、ここではαβ法が土台にしている手法という位置づけを確認しておきます。

モンテカルロ法（同じ局面から何度もランダムに試合を最後まで進めてみて、勝率の高さで手を選ぶ方法）との違いは、手の選び方のアプローチにあります。αβ法は評価関数とミニマックス法に基づく網羅的な探索で最善手を求めるのに対し、モンテカルロ法は同じ局面からランダムな試行（プレイアウト。局面から終局までを実際に一通り進めてみること）を多数繰り返し、勝率の高さから手を選ぶ統計的な手法です。

評価関数を使って局面を数値評価するか、実際にプレイアウトを繰り返して勝率を数えるかという点で、両者はアプローチの出発点そのものが異なります。ここまでの3つを並べると、最善手の決め方の違いがはっきりします。

手法	最善手の決め方	計算量の特徴
Mini-Max法	ゲーム木の全ノードを評価して決める	全ノードを評価するため計算量が大きい
αβ法	Mini-Max法と同じ網羅的な探索で決める	結論に影響しない枝を省く分だけ少なく済む
モンテカルロ法	ランダムな試行を重ね、勝率の高い手を選ぶ	局面の数値評価ではなく試行の積み重ねに依存する

同じゲームAIの手法でも、計算を減らして深く読む方向と、試行を重ねて勝ちやすさを測る方向という、別々の発想に立っていることが分かります。

αカットとβカットは、枝を切る条件自体は共通していますが、どちらの手番で発生するかによって呼び分けが分かれます。自分の手番（MAXノード）でα値を下回る枝を切るのがαカット、相手の手番（MINノード）でβ値を上回る枝を切るのがβカットという対応関係にあります。この手番とカットの組み合わせを取り違えないことが、比較の中でもとくに重要な論点です。手番が変わるたびに、どちらの値を基準にどちらの枝を切るのかが入れ替わる点に、αβ法の分かりにくさがあります。

4. ビジネス・実務での活用シナリオ

将棋・チェスなどの対局プログラム開発においては、限られた持ち時間の中でより深い手まで読み切るために、αβ法による枝刈りが探索エンジンの基盤として使われてきました。持ち時間という制約の中でどれだけ深く手を読めるかは対局プログラムの強さを左右する要素であり、無駄な枝を省くαβ法の役割は大きいものでした。日本の将棋プログラム「Bonanza」などにも、この枝刈りの仕組みを取り入れた実績があります。

AI人材向けの研修やアルゴリズム学習の教材でも、探索と枝刈りという考え方の基本モデルとしてαβ法が扱われます。計算量を抑えるという発想を学ぶ入門例として位置づけられており、探索という考え方全般の理解にもつながります。

スケジューリングや資源配分のように選択肢が枝分かれする意思決定問題でも、結果に影響しない候補を早期に切り捨てるという枝刈りの発想は、探索を使う他の最適化手法にも援用されています。組合せが膨大になる問題ほど、こうした枝刈りの考え方が計算量の削減に役立つ場面は多くなります。