αβ探索

作田 誠

目次

1  αβ探索

二人完全情報ゲームで利用されるαβ探索のアルゴリズムについて学習する。

1.1 基本的なαβ探索

αβ探索は、ミニマックス探索に 探索下限値 α と 探索上限値 β を導入して、無駄な探索を省いた探索法である。

固定深さまで一律に探索する基本的なαβ探索は以下の再帰的アルゴリズムで記述できる。自分の番の探索「MAX節点探索」と相手の番の探索「MIN節点探索」とが交互に呼び合う形となる。

リスト1  基本的なαβ探索

整数型  MAX節点探索 ( 残り深さ, 現在局面, α, β ) {

    「残り深さ」が 0 なら {
        「現在局面」を評価関数によって評価した値を返す
    }

    「現在局面」で可能な着手をすべて生成

    可能着手数が 0 (末端節点) なら {
        「現在局面」を評価関数によって評価した値を返す
    }

    m = α

    すべての可能着手について {

        「現在局面」を着手によって一手進める

        value = MIN節点探索(「残り深さ」- 1, 現在局面, m, β)

        もし value > m または 第一候補着手 なら {
            最善着手列として記録
        }
        もし value > m なら {
            m = value
            もし m が β 以上なら {
                着手によって進んだ「現在局面」を一手戻す
                m を返り値として戻る /* β-cut */
            }
        }

        着手によって進んだ「現在局面」を一手戻す
    }

    m を返り値として戻る
}


整数型  MIN節点探索 ( 残り深さ, 現在局面, α, β ) {

    「残り深さ」が 0 なら {
        「現在局面」を評価関数によって評価した値を返す
    }

    「現在局面」で可能な着手をすべて生成

    可能着手数が 0 (末端節点) なら {
        「現在局面」を評価関数によって評価した値を返す
    }

    m = β;

    すべての可能着手について {

        「現在局面」を着手によって一手進める

        value = MAX節点探索(「残り深さ」- 1, 現在局面, α, m)

        もし value < m または 第一候補着手 なら {
            最善着手列として記録
        }
        もし value < m なら {
            m = value;
            もし m が α 以下なら {
                着手によって進んだ「現在局面」を一手戻す
                m を返り値として戻る /* α-cut */
            }
        }

        着手によって進んだ「現在局面」を一手戻す
    }

    m を返り値として戻る
}

上のリストのαβ探索を使ってある局面の着手を選択させる場合、以下のように下限値αを -∞ 上限値βを +∞ で「MAX節点探索」を呼べばよい。なお、プログラム上では ∞ ではなく、ゲーム途中の局面の評価関数の値にならないような非常に大きい値とすればよい。また「探索深さ」で調べるミニマックス木の深さを指定する。

        r = MAX節点探索( 探索深さ, 局面, -∞, ∞ );

返り値に探索の結果判明した最善の評価値が戻される。 最善手については、何か着手を表す変数を用意し格納する。または、配列を用意して最善着手列を記録する。

上のリストのαβ探索の場合、評価関数はMAX側 (探索開始局面での手番側) の有利がプラスになるようなものでなければならない。

1.2 negamax探索

αβ探索で対象としているゲームは、一方が勝ちで他方が負けになる二人ゼロ和ゲームと言われるものである。 このとき、評価関数を手番が反対だと値のプラスマイナスが反転するようにして、個々の局面における手番側の有利をプラスとするように作ることができる。

      評価関数(自分側から見たとき) + 評価関数(相手側から見たとき) = 0

  つまり、

      評価関数(自分側から見たとき) = - 評価関数(相手側から見たとき)
      評価関数(相手側から見たとき) = - 評価関数(自分側から見たとき)

このような評価関数を使うと「MAX節点探索」と「MIN節点探索」を一つにまとめることができる。 これはαβ探索の一種で negamax探索 と言われる。

固定深さまで一律に探索する基本的な negamax探索 は以下の再帰的アルゴリズムで記述できる。negamaxの再帰呼び出しにおいて、パラメータ (a, b)に符号を反転した値を渡し、返り値の符号を反転して利用していることに注意されたい。

リスト2  negamax探索

整数型  negamax( 残り深さ, 現在局面, a, b ) {

    「残り深さ」が 0 なら {
        「現在局面」を評価関数によって評価した値を返す
    }

    「現在局面」で可能な着手をすべて生成

    可能着手数が 0 (末端節点) なら {
        「現在局面」を評価関数によって評価した値を返す
    }

    m = a

    すべての可能着手について {

        「現在局面」を着手によって一手進める

        value = -negamax(「残り深さ」- 1, 現在局面, -b, -m)

        もし value > m または 第一候補着手 なら {
            最善着手列として記録
        }
        もし value > m なら {
            m = value
            もし m が b 以上なら {
                着手によって進んだ「現在局面」を一手戻す
                m を返り値として戻る /* β-cut または α-cut */
            }
        }

        着手によって進んだ「現在局面」を一手戻す
    }

    m を返り値として戻る
}

このneagmax探索では処理内容や変数の意味がMAX節点とMIN節点で下表のように異なることに注意。

negamaxでのMAX節点とMIN節点の違い
節点(a, b)評価値大小関係カット
MAX節点
(自分の番)
(α, β)そのままそのままβカット
MIN節点
(相手の番)
(-β, -α)プラスマイナス反転逆転αカット


上のリストのnegamax探索を使ってある局面の着手を選択させる場合、その局面が根節点でありMAX節点となる。従って、以下のように下限値パラメータ a (α に相当) を -∞、上限値パラメータ b (β に相当) を +∞ でnegamax探索を呼べばよい。

        r = negamax( 探索深さ, 局面, -∞, ∞ );

negamax探索は、基本的なαβ探索に比べ記述量が半分になり、コードが重複していないので変更し忘れなどでMAX節点探索とMIN節点探索で食い違いが起こる危険性がないことなどで、利用されることが多い。
ただし、MAX節点とMIN節点で探索コードを少し変更したい場合は逆に面倒になる場合もある。 場合によって、基本的なαβ探索とnegamax探索のどちらかを使い分けた方がよい。


演習13 ミニマックス探索、negamax探索例の問題

以下の問題に答えなさい。

下図の二人ゼロ和確定完全情報ゲームのゲーム木について、ミニマックス探索またはαβ探索を実行する。

一番下段の末端節点にある数値は、A節点のMAX側 (手番側) から見た各節点の評価関数の値を表す。相手側から見た評価関数の値は、絶対値が等しい符号を反転した値となる。

ゲーム木

(1) A節点でミニマックス探索を実行したとき、A節点のMAX側 (手番側) から見た各節点の評価値を示しなさい。
また、A節点で選ばれるのはどの節点か?

解答:
A
B
C
D
E
F
G
H
I
J
選ばれる節点

(2) αβ探索の一種であるnegamax探索を下に示すC言語のコード (リスト2参照) を使って実行する。ただし、以下のような関数を使用するものとする。

関数説明
int
generateMoves( void )
現在探索中の節点の可能着手をすべて生成する。可能着手の数を返す
int
evalPosition( void )
現在探索中の節点を評価関数によって評価し、その節点の手番側から見た評価値を返す
void
makeMove( int i )
現在探索中の節点において i 番目の着手を選択し実行し、先の節点へ進む
void
undoMove( int i )
i 番目の着手を選択し実行した結果先に進んだ節点を元の節点に戻す

なお、ゲーム木の図の各節点において、generateMoves() で求められる各可能着手は各子供節点に向かう枝に対応しており、上図の左側の枝から右側に向けて 0 番から順に番号付けられるものとする。

※ 簡単のため、リスト2に対して以下の簡略化を行っている。

  • 末端節点まで展開して調べる探索のため、negamax関数に「残り深さ」パラメータは渡していないので注意。
  • 節点の状態 (局面) をグローバルにとってあるため、「現在局面」パラメータも渡していない。
  • 最善着手列の記録を行っていない。評価値が求まるだけ。
int negamax( int a, int b ) {
	int numMoves, m, i, value;
	『　　　　　ア　　　　　』
	if ( numMoves == 0 ) { /* 末端節点のとき */
		return 『　　　　　イ　　　　　』
	}
	『　　　　　ウ　　　　　』
	for (i = 0; i < numMoves; i++ ) {
		『　　　　　エ　　　　　』
		value = -negamax(-b, -m);
		if ( value > m ) {
			『　　　　　オ　　　　　』
			if (  『　　　　　カ　　　　　』  ) {
				undoMove(i);
				return m; /* β-cut または α-cut */
			}
		}
		『　　　　　キ　　　　　』
	}
	『　　　　　ク　　　　　』
}

空欄『ア』～『ク』に適切なコードに追加・修正しなさい。

解答:
『ア』
『イ』
『ウ』
『エ』
『オ』
『カ』
『キ』
『ク』

main関数から

	int r;
	r = negamax( -10000, 10000 );

の形で、問題のゲーム木に対してαβ探索を呼び出すとする。(根節点は A で MAX 節点となる)
このとき、節点 C, D, G, M にnegamax関数が来たときの、変数 a, b の値をそれぞれ示しなさい。

解答:
節点ab
C
D
G
M

(3) 上記のαβ探索で、βカットされた結果探索されない節点をすべて列挙するか「なし」と示しなさい。

解答:

(4) 上記のαβ探索で、αカットされた結果探索されない節点をすべて列挙するか「なし」と示しなさい。

解答:

(5) 問題のゲーム木に対して、初期節点をAとして r = negamax( 4, 6 ); の呼び出しをした場合、αカットあるいはβカットでカットされて探索されない節点をすべて列挙するか「なし」と示しなさい。

解答:

(6) 問題のゲーム木に対して、初期節点Aの各子節点 B, C, D に対して1スレッドずつを割り当て、それぞれ negamax(-10000, 10000) の形で並列探索させて、A節点の評価値と選択するべき子節点を求めるとする。このとき、αカットあるいはβカットでカットされて探索されない節点をすべて列挙するか「なし」と示しなさい。

解答:



演習14 negamax探索の実装と実行手順の追跡

Teams授業チームの「共有済み」にある雛型ファイル negamax_proto.c のプログラムは演習13のnegamax探索をC言語で実装したものである。ただし、上記演習と同じ空欄部分が抜いてあるので追加・修正する必要がある。
ダウンロードしファイル名を negamax.c として、抜けている部分を追加・修正してプログラムを完成させ、コンパイル・実行し、出力結果を示しなさい。

なお、このプログラムには、動作を追跡できる表示を行うようにコードが追加してある。


今回の演習ではプログラム出力で答を確認できるが、まとめテストにおいて類題が出題される。その際は、機器含め何も持ち込みできない筆記試験となるので、プログラム動作の詳細を自力で追えるようになっていないといけない。