将棋ソフトの思考法 αβ法

シェアする

  • このエントリーをはてなブックマークに追加

アイドルマスターシンデレラガールズ スターライトステージ(デレステ)に最近登場した、喜多見柚ちゃんという女の子がかわいいです。

ノーマルのイラストだけ見ればツンとしてそうな雰囲気ですが、実際はいたずら好きでお茶目な女の子で、舌を出して笑っているのが非常にかわいいですね。アイドルトピックスの一コママンガの柚ちゃんかわいい。

それはさておき、前回、ミニマックス法という、将棋ソフトの先読み方法について書きましたが、実はそれには無駄があります。

無駄を減らす手段である「枝刈り」の方法として、「αβ法」という探索方法があるので、その解説をしますが、その前に用語の意味を書いておきます。

グラフ:いくつかの点と2点を結ぶいくつかの線分で構成された図形。ネットワークのようなもの。

ノード:グラフの点(将棋の例では局面)

辺・枝:グラフの2つのノードを結ぶ線分(将棋の例では指し手)

パス(path)・経路:あるノードから別のノードへ、辺のみを通って移動する経路

閉路:あるノードから、同じ辺を2回通らずに元のノードに戻ってくる経路。つまり輪っか。

木・木構造:すべての2点を結ぶパスが存在し、閉路が存在しないグラフ。基本的に、1つのノードを根ノードとして、そこから派生的に広がる樹形図として書かれる。

ゲーム木:特定局面から始め、一手先の局面全体へと枝を伸ばして広げていった樹形図

子ノード:木における、あるノードの、一つ下の階層のノード(ゲーム木なら、一手先の局面たち)

親ノード:木における、あるノードの、一つ上の階層のノード(ゲーム木なら、一手前の局面)。かならず親は一つ。

根ノード:親が存在しないノード

葉ノード:子が存在しないノード

ミニマックス木:ミニマックス探索に用いられる木。すべてのノードは、MAXノードとMINノードに分類される。

MAXノード:ミニマックス木における、子ノードの値の最大値を取ってくるノード。評価値を最大化するノードなので、前回・今回の例では先手番の局面。

MINノード:ミニマックス木における、子ノードの値の最小値を取ってくるノード。評価値を最小化するノードなので、前回・今回の例では後手番の局面。

以上が大体の用語です。では本題に入りましょう。

無駄な手を読まない枝刈り「αβ法」

ミニマックス法の手順を見てみましょう。

minimax2

再帰による実装では、まず、局面アの評価値を求めるために、局面イの評価値を求めます。そのために、まず局面オの評価値を求めます。

局面オの評価値を求めるために、局面サの評価値を計算して、+100を得ます。また、局面シの評価値も計算して、+50を得ます。そして両者を比べます。局面オは先手番なので、大きい方の+100を採用します。

局面イの評価値を知るために、次は局面カの評価値を求めて、局面オの評価値+100と比較して、局面イは後手番なので小さい方を採用します。

局面カの評価値を求めるために、局面スの評価値を計算し、+300を得ます。また、局面セの評価値を計算し、+150を得ます。これを比較して、先手番の局面カの評価値は、大きい方の+300になります。

そして、局面オ、カの評価値+100と+300を比較して、後手番の局面イの評価値は小さい方の+100になります。

さて、ここに無駄があります。

局面スの評価値+300を得た時点で、局面カの評価値は+300以上と決まります。局面カは先手番、すなわちMAXノードなので、局面スの評価値が+300以下なら、局面カの評価値は+300になり、局面スの評価値が+300より大きければ、局面カの評価値にそちらが採用されます。

一方、同じ理屈で、局面オの評価値+100を得た時点で、局面イの評価値は+100以下だと決まっていたのです。(局面イはMINノードなので)

つまり、局面イの評価値は最終的に「+100と[+300以上]の小さい方」となります。したがって、局面セの評価値が+10000だろうが-10000だろうが、局面イの評価値は+100と決まっており、局面セの評価値を計算するのは無駄なのです。

より一般的な言い方をすると、局面イはMINノードなので、局面オの評価値が分かった瞬間に「局面イの評価値の上限は+100」となります。(局面オの評価値が分かる前は、上限は+∞となります。実装上は、+100000などの大きな値にしたり、INT_MAXなどの定数を使うことになるでしょう。)

局面カの評価値を計算するときに、この「上限+100」という情報を渡すのです。

そして、局面スの評価値+300が分かった瞬間、今度は「局面カの評価値の下限は+300」となります。

このとき、「親ノードの評価値の上限+100<自分の評価値の下限+300」という事態が発生します。このことが「この局面には絶対に行き着かない」ということを示しているのです。

したがって、局面カの評価値は、局面セの評価値を計算するまでもなく、+100以上の適当な値を返しておけばいいのです。(実際は、+100をそのまま返すと楽に実装できます。)

無駄な探索を避けるために、このような「MAXノードで最終的に取りうる値の下限」と「MINノードで最終的に取りうる値の上限」を記録しておきます。

「MAXノードの下限」を「α値」、「MINノードの上限」を「β値」と言います。

そして、今回のように、親子ノードで「α>β」というという関係が成立すると、子ノードには絶対にたどり着かないと判断できるのです。(子ノードがMAXノードでもMINノードでも成立します。)

したがって、アルゴリズムは以下のようになります。

// 最初に呼び出すときは、α(MAXノードの下限)は-∞、β(MINノードの上限)は∞として呼ぶ。
int EvalAlphaBeta(Board board, int depth, int alpha, int beta){
	if(depth == 0) return Eval(board); // 葉ノードなら評価値を返す
	if(先手番(MAXノード)なら)
	{
		foreach(全てのの合法手moveに対して)
		{
			/* ここで局面boardを指し手moveで更新する */
			// 子ノードの評価値がα(MAXノードの下限)を超えたら更新
			alpha = max(alpha, EvalAlphaBeta(board));// max(,)は大きい方を選択する関数
			if(alpha >= beta) return beta;// 枝刈り発生(このノードには絶対に辿り着かない)
			/* 必要ならここで局面boardの指し手moveを巻き戻す */
		}
		// 枝刈りが発生しなければ、αが確定値となる
		return alpha;
	}
	else// 後手番(MINノード)なら
	{
		foreach(全てのの合法手moveに対して)
		{
			/* ここで局面boardを指し手moveで更新する */
			// 子ノードの評価値がβ(MINノードの上限)を下回ったら更新
			beta = min(beta, EvalAlphaBeta(board));// min(,)は小さい方を選択する関数
			if(alpha >= beta) return alpha;// 枝刈り発生(このノードには絶対に辿り着かない)
			/* 必要ならここで局面boardの指し手moveを巻き戻す */
		}
		// 枝刈りが発生しなければ、βが確定値となる
		return beta;
	}
}

コードを見て疑問に思うかもしれませんが、あるMAXノードのα値またはMINノードのβ値は、孫ノード(2手先の局面)に使うことができます。

ちょっと説明しましょう。局面ソの子局面である局面Aの評価値が+60だったとしましょう。

alphabeta

局面イの評価値が+100になった瞬間に、局面アのα値が+100になります。β値はINF(とても大きい値)のままです。

このとき、局面ウの評価値を得るために局面キの評価値を計算しようとしますが、初めから局面キのα値(下限値)を+100とできるのです。

α=+100、β=INFが局面ソまで伝わり、局面ソにおいて、子局面Aの評価値が+60になったとします。

すると、局面ソにおいてβ値が+60となり、α(+100)≧β(+60)となるので、局面ソには訪れないことが分かり、局面Bの評価値計算を打ち切ります。なぜこれができるのでしょうか。

仮に、局面タの評価値が+60以下だったとします。このとき、局面キの評価値は+60になります。+60を超える局面が子に無いので。

すると、局面ウはMINノードなので、その評価値の上限(β値)は+60となります。(+60より小さくなることは保証されます。)

すると、局面アにおいて、確実に局面ウには行かなくなります。(局面アはMAXノードなので、すでに+60より大きいことが分かっている局面イへ行く方が良いです。)

そのため、局面ウには訪れず、もちろん局面キには訪れません。

また、仮に、局面タの評価値が+60より大きかったとします。

すると、局面キはMAXノードなので、局面ソには行かず、確実に局面タに行きます。局面ソは訪れません。

以上より、局面タの評価値に関わらず、局面ソには訪れないことが分かりました。ですので、局面Bの評価値は計算する必要が無いのです。

はあ、疲れました。これがαβ法と呼ばれる枝刈り(分岐をカットすることを枝刈りという)手法です。

αβ法は、枝刈りをするものの、確実にミニマックス法と同じ値が得られます。このような枝刈りを「後ろ向き枝刈り」と言います。

それに対して、ミニマックス法と異なる結果になるかもしれないけど計算量は非常に減らせる、という枝刈りを「前向き枝刈り」と言いますが、これは私があまり詳しくありません。

次回は、αβ法の特徴について書いて、指し手生成について触れようと思います。では。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする