将棋ソフトの思考法 ミニマックス法

シェアする

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

将棋ソフトが、ある局面の「先手の有利さ」を数値化する「評価関数」を持っていることは前々回触れました。

今回は、重要な「先読み」について解説します。

まず、最初に「ゲーム木」という言葉を紹介します。

将棋などの手番制のゲーム(特に完全情報ゲーム)は、「現在の局面」を元として、全ての「可能な次の手で更新した、一手先の局面」に対して線を伸ばし、さらにそれぞれの一手先局面から全二手先の局面へ……というようにして、局面変化を表す樹形図を書くことができます。これを「ゲーム木」と言います。

ゲーム木探索については、今回書くミニマックス法やそれを改良したαβ法などについて、こちらの本に詳しく書いてあります。

ちなみにこの本には人工知能の基本的な方法の一つである「ニューラルネットワーク」などについても詳しく記載されています。

まあ、とりあえず見てみましょう。

相手の立場に立って考える

先手番の現在の局面アにおいて、先手の最善手を探します。局面アについて次のゲーム木が構成されたとしましょう。(赤が先手番、青が後手番)

minimax1

つまり、局面アにおいて指せる手は3つだけで、それぞれの指し手で移動した先の局面(後手番)を、局面イ、ウ、エとします。局面イ、ウ、エそれぞれにおいて、後手が指せる手は全て2つだけで、それぞれ局面オ~コへ移動できます。さらに局面オ~コで先手の手は全て2つだけで、それぞれの手で局面サ~二へ移動できます。

3手先の局面サ~ニについて、評価関数を用いて評価値を計算したのが図のカッコ内の数字です。いずれも「先手から見た有利さ」です。

ここから、局面イ、ウ、エの評価値を逆算して、最善手を決定します。

興味のある方は、一度自分で考えてみて下さい。

さて、たとえば「ア→イ」の手を指したとしましょう。後手は次に何を指すでしょうか。

先手は自分にとって有利にしたいので、後手が「イ→オ」を指すと先手は必ず「オ→サ」を指します。このとき評価値+100。

一方、後手が「イ→カ」を指すと、先手は必ず「カ→ス」を指します。このとき、評価値は+300。

以上より、「局面オの評価値は実質+100、局面カの評価値は実質+300」となります。

これは先手から見た評価値なので、後手は「イ→オ」を指すべきです。

このとき、「局面イの評価値は実質+100」と決まりました。あくまで「両者が最善手を指す」場合についてですが。

このように考えると、3手目の先手の手は、局面オ~コすべてに対してすぐに判断でき、そこから局面オ~コの実質の評価値が分かります。

局面オ~コの実質の評価値が分かると、そこから局面イ、ウ、エについて後手が指す手が決まり、局面イ、ウ、エの実質の評価値が決まります。

そこから、局面アにおいて先手が指すべき手を判断すれば良いのです。

このように、「先読みする手数を決めて、一番深いところから浅い方へ順に、『先手番なら評価値を最大化する手を、後手番なら評価値を最小化する手を指す』というルールで評価値を更新していく」という方法が先読みの基本的な考え方です。

「先手番で最大化」と「後手番で最小化」が交互に訪れるので「ミニマックス法」と呼ばれています。

「その局面からの最善手」を表す線を赤くして、途中局面の実質の評価値を書いた図を載せます。

minimax2

これは右側(深い方)から更新していきます。先手番なら、一つ深い局面の評価値の内もっとも高いものを、後手番ならもっとも低いものをその局面の評価値とします。

したがって、最善手は「ア→エ」であり、評価値は+120になります。そして予想手は「ア→エ→ケ→テ」と変化していく手順です。

これが、将棋のニコ生中継などで表示される「評価値」と「予想手」の正体です。

さて、ここで、「3手先の局面の内、最も評価値が対局面へ行こうとする」というソフトを考えてみましょう。

今回の場合、最も評価値が高いのは局面スの+300点なので、最初に「ア→イ」を選択します。

しかし、次に後手は+300を許すわけにはいかないので、「イ→オ」を選択するでしょう。したがって、結局行き着くのは局面サの+100点になります。「ア→エ→ケ→テ」の+120点の方が良いですね。

これがいわゆる「勝手読み」です。「相手がこう指したところでこう指せば有利だ!」というように相手の手を自分に有利なように決めつけて、ちゃんとした相手の手を考えずに先読みしようとする考えです。

以上が将棋(あるいはその他の複雑な完全情報ゲーム)のプログラムの思考法です。

が、このミニマックス法は、遅すぎます。無駄が多いからです。

結果的に1本の予想手順が出るだけなのに、こんなに評価値を計算する必要があるのか?

将棋の中盤以降の局面では、平均して70個の合法手があると言われています。つまり、3手先読みで70*70*70=34万3000局面の評価値を計算することに。5手先読みなら70^5=16億8070万局面。

実は、上で示したゲーム木でも、3つ、無駄な計算があるのです。

結果的にミニマックス法と全く同じ結果が得られるのに、ミニマックス法よりも計算回数が少なくて済む方法である「αβ法」については、次回解説します。

最後に、ミニマックス法のアルゴリズムを載せておきます。これは評価関数を計算するだけなので、実際にはこれを呼び出す関数側で指し手を選択します。

再帰的に関数を呼び出し、depthで末端かどうか判断します。上の図では、局面アの段階で、局面イ、ウ、エをboardとして、depthを2として3回この関数を呼んで、得られた結果の中で最も評価値が大きい局面エの+120を基に、指し手「ア→エ」を選ぶことになります。

// ミニマックス法で局面boardの評価値を深さdepthで計算
int EvalMiniMax(Board board, int depth){
	// 末端ならその局面の評価値を返す
	if(depth == 0) return Eval(board);
	
	if(先手番)
	{
		int max = INT_MIN; // 最大値に、int型の最小値を入れる
		foreach(全ての合法手moveに対して)
		{
			/* ここでboardをmoveで更新 */
			eval = EvalMiniMax(board, depth-1)
			if(eval > max)
			{
				max = eval;
			}
			/* 必要ならここでboardのmoveを巻き戻す */
		}
		return eval;
	}
	else // 後手番なら
	{
		int min = INT_MAX; // 最小値に、int型の最大値を入れる
		foreach(全ての合法手moveに対して)
		{
			/* ここでboardをmoveで更新 */
			eval = EvalMiniMax(board, depth-1)
			if(eval < min)
			{
				min = eval;
			}
			/* 必要ならここでboardのmoveを巻き戻す */
		}
		return eval;
	}
}
スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

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

フォローする