TIM Labs

2015年10月アーカイブ

先日、情報処理学会から、「コンピュータ将棋プロジェクトの終了宣言」が出された。将棋プログラムの能力がプロ棋士の能力を超えたと統計的に判断でき、当初の目的を終えたので、プロを超すのを目指すよりも、今までの研究で得られた技術を他へ活かして行くということだ。

さて、ここで紹介しているモンテカルロ木探索は囲碁で使われているアルゴリズムなのだが、囲碁はまだまだプロには及ばない。でも、アマの有段者並にはなっており、これからはプロ棋士に勝つという点では、囲碁に注目が集まってくると思われる。
私も囲碁をやるのだが、最近の囲碁ソフトは強くなって勝てなくなった。ハンデなしで初めはリードしていても、1局ミスなしで打ち切るのは難しい。


さて、前回の続きを行う。

モンテカルロ木探索は、木を再帰的に探索するので、再帰呼出しになっている。これは、一般の木に対する処理を行う場合と基本的には何ら変わらない。
木あるいは部分木に対して、再帰的にモンテカルロ木探索を行うとはどいういうことが考えていこう。

前回最後に示したメソッド playouttree( Node node ) を以下に示す。

	// 指定されたノードに対して、モンテカルロ木のプレイアウトを1回再帰的に行う。
	void	playouttree( Node node ) {

		// 札の移動
		if( node.childcnt==0 ) {		// 子がいない
			if( node.playcount+1>=EXPANDCOUNT ) {	// 展開
				makeMoveBranch( node );
			} else {
				double sc = simpleplayout();		// 単純プレイアウト
				node.addSuccess(sc);
			}
		} else {
			Node selectednode = null;			// 最良ノード
			
			if( node.childmovetype ) {			// 札移動の場合
				double	max = -1;
				for( Node nd : node.children ) {
					if( nd==null )
						continue;
					if( max < nd.success ) {
						max = nd.success;
						selectednode = nd;
					}
				}
			} else {					// 手札オープンの場合
				int  r = rnd.nextInt(tefudalen);
				int  t = tefuda[r];
				selectednode = node.children[t];
				if( selectednode==null )
					selectednode = makeOpenBranch( node, new Move(t) );
			}
			
			selectednode.move.exec();		// 選んだ枝に対する札の移動を行う
			
			playouttree(selectednode);
		}
	}

このメソッドが、このモンテカルロ木探索の中核であり、これを理解してしまえば、後は枝葉と思って構わない。

木(部分木)は、その根のノードで指定できる。この根ノードを引数とするplayouttreeメソッドを用意した。

最初に行っているのは、子ノードがない場合の処理である。
ノードが持てるプレイアウトの最大数(閾値)が EXPANDCOUNTに入っているので、閾値を超えた場合には makeMoveBranch()により子ノードを作る。詳細は後述。


まだプレイアウトの閾値に達していない場合には、プレイアウトを行い、成功か失敗を1か0で得る。
そして、その結果をノードに反映するのだが、今のnodeだけではなく、親ノードを次々とたどって、親のノードが持っている成功率も書き換える必要がある。
これをnode.addSuccess(sc)で行っているのだが、これも後述し、肝心な部分を先に説明する。

else 以下のブロックは、子ノードが存在し、いずれかの子ノードを選択する場合である。
最終的に選択される最良ノードのための変数を selectednode とし、最初null を入れている。
子ノードは、札移動と手札オープンの2種類のいずれかに別れる。

まず、札移動の場合、子ノードの中から、一番成功率の高いノードを selectednodeとしている。

手札オープンの場合、乱数を使って手札のうちの1枚を選び、札の数を求める。
札の数に対する子ノードが既にあれば、それを selectednodeとし、もしまだその数に対する子ノードが存在しなければ、子ノードを作成し、生成された子ノードをselectednodeとする。

これで、札移動の場合でも、手札オープンの場合でも、子ノードが選択できた。
盤面の札移動または手札オープンを実際に行うのが、selectednode.move.exec()である。

それで、最後に、選んだノードに対して再帰的に playouttree()を呼び出している。



次に、このメソッドを利用して、現在の盤面から、次の一手を選ぶメソッドを示す。このとき、引数にプレイアウト回数を与える。1手プレイする度に、このメソッドを呼び出し、指定した回数だけプレイアウトを行っている。

	// 現在の盤面から 指定回数playout し、打つ手を選択する
	Move	playouttree( int playoutcount ) {		
		if( tefudatop == 0 ) {
			if( tefudalen>0 ) {	// 手札をオープンする 
				int  r = rnd.nextInt(tefudalen);
				int  t = tefuda[r];
				Move mv = new Move(t);
				return	mv;
			}
		}
		
		// 次の手がないなら、手札をめくる。
		ArrayList list = getAllMoves();		
		if( list.size()==0 ) {		// 打つ手がない
			return	null;
		} if( list.size()==1 ) {		// 打つ手は1手のみ
			Move mv = list.get(0);
			return	mv;
		}

		Node root = new Node();
		Stock	stock = new Stock();
		while( root.playcount < playoutcount ) {
			playouttree(root);	// 再帰的にモンテカルロ木ツリーを1回プレイアウトする
			stock.restore();
		}

		// 一番プレイアウトされた手を選ぶ
		int		maxcount = -1;
		Node	maxnd = null;
		if( root.childcnt > 0 ) {
			for( Node nd : root.children ) {
				if( nd == null )
					continue;
				if( nd.playcount > maxcount ) {
					maxcount = nd.playcount;
					maxnd = nd;
				}
			}
		}
		
		currentsuccess = root.success;
		
		stock.restore();

		if( maxnd == null )
			return	null;

		return	maxnd.move;
	}

本メソッドは、どう札を動かしたら良いかを求めている。

最初は、手札のトップが表になっていないとき、手札を1枚めくるというMoveを作って、それをreturnする。

次に、getAllMoves()で、次に打つことができる手の全リストを求め、手が無いときはnullを返し、次の手が1つしかない場合にはその1つだけだった手を返し、そうでない、つまり複数の可能性がある場合だけ次の手をどれにするか調べている。

whileのところで、playoutcount だけループしている。ここで、ルートノードに対するプレイアウトを延々と行って、モンテカルロ木がループするに従って成長していく。

次の一手を選択するのに、ルートの直下のノードの中で、一番成功率の高いのを選ぶと思うだろうが、モンテカルロ木選択では、そうはしない。もっとも多い回数プレイアウトされたノードを選ぶ。

ノードが決まれば、そのノードにMoveが付属しているので、それを返す。
Currentsuccessは、ゲーム進行中に成功率がどのように変化するかを表示(print)させるために用意しているだけで、プログラムの動きには関係ない。


以上の2つのplayouttreeにより、ゲームが実行できる。
原始モンテカルロ計算にあったonegame() において、単なるモンテカルロをモンテカルロ木探索に置き換えるだけである。なお、playoutcount は、プログラム起動時に値が決まるものとする。

	int	onegame() {
		initialize();
		
		for(;;) {
			opentefuda();
			
			// Move mv = primalMonteCarlo();
			Move mv = playouttree(playoutcount);

			if( mv==null )
				break;
			mv.exec();
		}
		
		return	restcount;
	}

以上で、モンテカルロ木探索の基本部分が終了である。
先を急いだので、説明を略した部分があるので、次回はそのあたりの説明を行う。

モンテカルロ木探索では、いわゆる「木」を用いる。木は、ノードの集まりで、親子関係があり、1つのノードに対して複数の子ノードがぶら下がる。

まず、用意したNodeクラスを見てみよう。

class Node {
		Node	parent = null;		// 親

		boolean childmovetype;	// true: 札移動タイプ	false:手札オープン
		Node	children[] = null;	// 子ノードはまとめて作られる
		int	childcnt = 0;		// 子ノードの個数

		Move	move = null;		// 手

		int	playcount = 0;		// このノードを起点にplayoutした回数

		double	successsum = 0.0;	// 成功合計
		double	success = 0.0;		// 成功率 = successsum / playcount
	}

ノードは、カードに対して操作をすることにより盤面が変化する度に作られるのだが、盤面情報自体は含んでいない。これは、盤面の状態はカードの動きを木の枝にそって順番にたどることで確実に求められるので、ノード自身には盤面状態を保持しない。
ノード自身はそれほどメモリを食わないが、盤面データは「計算」という規模の小さなゲームでもそこそこ食ってしまう。もし、盤面データがノード毎に用意されていると、メモリの大部分は盤面ということになる。盤面を保持していること自体、とくにメリットはないので、Nodeの要素には入れていない。

ノードには、カードの移動に伴ってできたものと、カード(手札)をめくってできた2種類があり、この2つのノードを区別しなければいけない。
どうしても2種類のノードをきちんと区別したい(行儀よくやりたい)場合には、Nodeを継承したMoveNodeとOpenNodeというクラスを作ると良いのだが、ここではこのまま話を進める。

ここでは、Node自身のノードタイプではなく、子ノードのタイプをchildmovetypeに保持している。
子ノードはない場合もあり、1個以上の場合がある。子ノードへのリンクの配列と、子ノードの個数を持っている。 Javaでは、配列のサイズを別に保持する必要はないのだが、特殊な使い方をするため、わざわざ子ノードの個数を保持している。子ノードの個数はないプログラムも可能なのだが、そのままにしておく。

子ノードがカードの移動のとき、getAllMoves()で与えられる全ての移動に対する子ノードを用意する。このときは、子ノードの配列には全ての移動に対して1つずつノードが生成され、子ノードの個数(=全ての移動の個数)も保持する。

子ノードが手札をめくるとき、表になったカードの数字を配列の添字として使うと楽になるので、常に要素数13+1の配列を用意し、残り手札の中にある数字に対してだけノードを用意する。このときの子ノードは、残り手札を見て一気に作るのではなくて、モンテカルロ木の成長過程で、手札をめくった時に必要なら子ノードを作る。
早めにちゃんと準備するのではなく、必要になったときに初めてつくるというとても怠惰な方式を選んでいる。いわゆるlazyな方法を選んでいるのだが、これは木が無駄に大きくならないようにするためである。実際に対応するコードが出た時に再度説明を加えよう。

moveという移動内容を示すMoveオブジェクトを保持している。このmoveに対応する移動を行った結果、現在のノードができたということを示す。

モンテカルロ木探索なので、プレイアウトの回数を保持している。詳しい説明は後述する。プレイアウトしたときの成功/失敗に関するデータを保持するため、successsumとsuccessが存在する。successsumは、計算の都合で入っている補助的なものである。
モンテカルロ木探索でとても重要なのが成功率successであるが、詳細はプログラムコードとともに徐々に説明していく。


ノード間の関係は次図のようになる。○はノードを示し、□はノードの中の移動(Move)を示している

lab-calc7-1.png

手札移動を行うと、手札のトップの札がなくなるので、まだ手札が存在するかぎり手札を1枚めくらないといけない。そのとき、一気に子ノードがいっぱいできている。 この木を管理するためのコードを書き加え、さらに木の一番下の端ノード(葉ノード)それぞれでプレイアウトを行うとモンテカルロ木探索が行われる。

Nodeクラスのメンバーを示したが、つぎにコンストラクタを考えよう。

引数なしのデフォルトと、親ノードとカード移動を与える場合の2つのコンストラクタを用意した。

		Node( Node pr, Move mv ) {
			parent = pr;
			++parent.childcnt;
			move = mv;
		}

		Node() {
		}

さて、モンテカルロ木をプレイアウトしながら成長させることで、次の最善手を見つけようというのがモンテカルロ木探索である。

最初は、原始モンテカルロ木探索と同じで、ルートの直下に次に可能な手に対応したノードを生成し、各ノードに対してプレイアウトをどんどんやっていく。このとき、各ノードで行うプレイアウトの上限値(閾値)を決めておき、それを超えるとそのノードのプレイアウト結果は捨てて、下位のノードを作ってそちらに対してプレイアウトを行う。こうすると、もとのノードにはプレイアウトがなくなったが、その下位ノードのプレイアウト回数の合計は1回増えることになる。

lab-calc7-2.png

プレイアウト回数をどんどん増加していくと、閾値を超えるノードができることで下位ノードを作ることになり、これで木が成長していく。
つまり、プレイアウトする毎に木を成長させるので、原始モンテカルロの場合と違い、木の成長を意識したプレイアウトメソッドを用意しないといけない。

	void	playouttree( Node node )

ノードを与えて、そのノードで示される部分木に対してプレイアウトを1回追加することを行うことになるが、この説明がモンテカルロ木探索の最も重要な部分になり、とても長くなるので、次回以降で説明する。

原始的なモンテカルロ探索を示したが、これは成功率が1%にも満たないものである。

もっと高い成功率を求めて、囲碁プログラミングで使われだした「モンテカルロ木探索」を、「計算」でも使えないか試してみよう。

ゲームやパズルでは、状況を分析するために、現在の盤面をルート(根)とする木を作るのが一般的である。

3手先までの木を作るとこんな感じになる。

lab-calc6-1.png

これは標準的な木で、一番下の葉のところでプレイアウトして、それぞれの成功確率を計算し、上に遡りながら一番良い手を選ぶというやり方があるが、ここではそれは説明しない。

枝の伸ばしについて、どの場合も同じ割合で伸ばしているが、これで良いのだろうか?

囲碁や将棋を考えてみれば分かるが、これはと思う枝はどんどん深く読んでいくが、これは論外だなというのはさっさと切り捨ててしまう。つまり、こんな感じの木ではなく、特定のところが深く探求され、かなり「いびつな木」が出来上がっている筈だ。それをこれから説明していこうと思う。

モンテカルロ木検索がどのようなアルゴリズムであるかについては、色々なところに説明があるので、ここに説明を長々と書くよりも、良さそうな情報源を紹介する方が役に立つし、こちらは楽なので、紹介するに留める。


モンテカルロ木関連情報


『コンピュータ囲碁におけるモンテカルロ法〜理論編』美添一樹(pdf)

とても丁寧な説明なので、十分理解できると思う。ただ、囲碁に偏った説明が多くなっているが、元々囲碁で使われだしたので、当然囲碁を使って説明が進む。とくに囲碁を理解していなくても大丈夫なのだが、囲碁の説明部分を十分に理解したい場合は、この際囲碁をマスターしてしまおう。

理論的な基礎は、このPDFだけで十分ではないかと思う。というか、それくらいしか読まずに「計算」に適用してみようという大胆なことをやっているのが実情である。

これで書ける「囲碁講習会」全4回@電気通信大学

こちらは、2015年夏に電気通信大学で行われた囲碁プログラミングの講習会で、
実践編2 UCTアルゴリズムで打つ』の中で説明されている。

実際に強いプログラムを作っている人が、囲碁プログラミング初心者向けに、多数のソースコードを用意し、実際の動きを体験させる講習会で、ビデオ、資料も充実しているので、とても参考になった。

ビデオはとても長い。1本約3時間であるが、十分に見る価値がある。

JavaScript でオセロを実装する(モンテカルロ木探索AI)

こちらは、本ブログのもので、囲碁ではなくオセロで試みた例になっている。


「囲碁」と「計算」での相違点

モンテカルロ木探索を使うのだが、ほとんどの説明は囲碁の場合であるが、計算にそのまま適用できない部分がある。
まず、囲碁は、「二人完全情報ゲーム」であり、計算は「一人不完全情報ゲーム」である。 これから、2つの相違点があることが分かる。

二人 vs 一人

二人での対戦型では、プレイヤーが替わる度に盤面評価が逆になる。 自分に良い手は相手にとっては不都合であり、 相手の良い手は自分にとって不都合である。 つまり、一手打つ度に、評価を反転しなくてはならなくて、 そのために、Min-Max法とかαβ法とかいろいろ工夫されている。

しかし、今回は一人ゲームなので、常に自分の手番である。なので、可能な手から一番良い手を選ぶだけでよいので、この点ではとても簡単になる。

完全情報 vs 不完全情報

囲碁は、全ての情報が完全に見えているゲームである。偶然が入る余地はなくて、強い人と弱い人が対戦すると強い人が勝ってしまう。つまり、偶然勝てるなど、ないのである。

しかし、計算は手札を一枚ずつめくってプレイしていくが、どの数字が出てくるかはプレイヤが決めることができない。残りの手札の中のどれかが出てくるのだが、それ以上は決めようがなく、実際には乱数を使って残り手札の中からランダムに選んでおり、不完全情報ゲームになってしまう。

不完全情報ゲームになるのだが、カードをめくる部分なので、最大1〜13通りしかありえない。この不完全な部分も木に組み込むことになる。プレイヤに選択権がある場合は最適な手を選べば良いだけだが、不完全な部分に対して予測を立てる必要があり、そこで枝分かれが増えるために木が横に広がってしまう。

というのが基本的な相違点である。


今日はここまでとし、次回からは、以上を考慮に入れて、ソースコードレベルで実装していく。

前回でとても馬鹿なプレイアウトをしたときの成功率を実験する準備ができたので、実行してみた。
10000回やっても、まったく成功しないので、一気に1000000000回、つまり10億回実行してみた。
その結果、533回成功した。

成功率 = 533/1000000000=1/1876173


ということで、とても低い成功率。200万分の1よりやや良い程度と思われるが、ほとんど成功しないプレイ方法である。


原始モンテカルロ計算

このデタラメにプレイするどうしようもないメソッドを活用して、なんとか賢くプレイするプログラムを作ろうというのが目的であった。
それで、デタラメという言葉で最初に思いつくのが、モンテカルロ法だ。カードを動かすときに、このデタラメプレイアウトを利用して、可能な手の中から一番成功確率の高い手を選ぶというのを毎回行うと賢いプレイにならないだろうか。
図で示すと、次図のようになる。次図の場合、成功率が2/3になった手を選ぶ。

lab-calc5-1.pngこれを実現するために、1回のゲームに対応するメソッドonegameを以下のように書き換えた。
	int	onegame() {
		initialize();
		
		for(;;) {
			opentefuda();
			
			Move mv = primalMonteCarlo();
			if( mv==null )
				break;
			mv.exec();
		}
		
		return	restcount;
	}
forループの中は、まず手札をめくり、そのあと原始モンテカルロメソッド primalMonteCarloを呼び出している。これを呼べば、実行すべきカードの動きを返してくれるので、それを実行するだけだ。

原始モンテカルロ計算のメソッドが以下である。ほとんどの場合、うまく行かないので、ちょっとだけ工夫してある。
	Move	primalMonteCarlo() {
		Move	mv=null;
		
		ArrayList<Move> list = getAllMoves();
		
		int	sz = list.size();
		if( sz==0 )
			return	null;
		if( sz==1 )
			return list.get(0);

		Stock	stock = new Stock();
		double	maxsum = -1.0;
		for( Move m : list ) {
			double	sum = 0.0;
			for( int i=0; i<PLAYOUTCOUNT; ++i ) {
				sum += simpleplayout();
				stock.restore();
			}
			if( sum > maxsum ) {
				maxsum = sum;
				mv = m;
			}
			if( maxsum==0.0 ) {
				PLAYOUTCOUNT = selectRandomly(list);
			}
		}

		return	mv;
	}

最初に、可能なMoveをlistに集め、要素が0個、1個の場合の処理を行う。
2個以上の場合、それぞれのカード移動に対してPLAYOUTCOUNT 回だけプレイアウトを行い、成功率を加算している。なので、実際の成功率は、sum/PLAYOUTCOUNT なのだが、どのカード移動についても同じ回数だけ実行されるので、PLAYOUTCOUNTで割るのは省略した。全てのカード移動に対して、もっとも成功率が高い場合の移動がmvに入れたのだが、実はとても問題がある。

プレイアウトsimpleplayoutはとても成功率が低く、1.0になるのは200万分の1程度で、それ以外は0.0となる。そのため、PLAYOUTCOUNTが200万分の1に比べて少ない場合は、maxsumは0.0のままである。このままだと、ほぼ確実に最初の要素がmvになってしまう。

それで、そういう不都合な場合、list中の要素の1つをランダムに選ぶことにした。したがって、プレイが始まって糖分の間は、プレイアウトが無効になって、単にランダムに選ぶのと同じになる。
ということは、このやり方では、成功率はまったく上昇せず、延々と無駄にプレイアウトするので、時間だけ掛かる最悪な状態になる。

次手についてプレイアウトをそれぞれ100回、そしてゲームを100,000回実行してみたが、結果は哀れな状態になった。成功率0、つまり一度も成功することがない。プレイアウト回数、ゲーム回数をもっと増やせば、そのうち0ではなくなるだろうが、測定不能くらい低い成功率である。ということで、これ以上努力するのは止めよう。

さて、どうしようか?

ここで、モンテカルロ木探索の話を持ち出すのが普通だろうが、その前にひと工夫してみよう。
そのまえに、どうして失敗してしまうのか、実際のカードの重なり方の失敗方法を見てみよう。    そのために、現在の盤面の状態をプリントアウトするメソッドを用意した。

Hand:     2 : QQJT56489TAQKAJ3457589TJQKA83456789T
Table:  2(3)  2(4)  6(9)  4(8) 
[1]  6J7
[2]  9K
[3]  23
[4]  7K
Handが手札で、トップだけを:の前に書いている。:の後ろは残りの手札を示しているだけである。
Tableは台札を示し、()内は次における数札を示す。

これを見ると、2や6という絶対台札に出せるカードがあるのに、その上にカードが載せられ、身動きできなくなって自滅の道を進んでいることが分かる。[2]の屑札の一番下に9があるが、Kが上に置かれて使えなくなっている。

この、どうしようもないカードの動きを超簡単なプログラムの変更で何とかできないだろうか?
	ArrayList<Move> getAllMoves() {
		ArrayList<Move> list = new ArrayList<Move>();

		for( int k=0; k<KUZUNUM; ++k ) {	// 屑札移動を集める
			for( int d=0; d<DAINUM; ++d ) {
				Move nx = nextKuzufudaDaifuda( k, d );
				if( nx != null )
					list.add(nx);
			}
		}
		
		if( tefudatop == 0 )				// 手札終了チェック
			return	list;
		
		for( int d=0; d<DAINUM; ++d ) {		// 手札台札を集める
			Move nx = nextTefudaDaifuda(d);
			if( nx != null )
				list.add(nx);
		}

		if( list.size() > 0 )			// 台札に載せるのを優先
			return	list;

		for( int k=0; k<KUZUNUM; ++k ) {	// 手札屑札を集める
			Move nx = new Move( MoveType.手札屑札, tefudatop, k, 0 );
			list.add(nx);
		}

		return	list;
	}
まず、これに差し替えて、前と同じように初期状態からプレイアウトしたときの成功率を求めてみる。
同様に10億回実行すると、494回成功した。
前回533回、今回494回の成功なので、何も考えない方が良いという結果が出た。
といっても、この程度の差なので、誤差範囲に入る。
さて、この変更は無意味だったのだろうか。

あまり早く結論を出してはいけない。原始モンテカルロでも試してみた。
前と同じ条件(次の各手に対するプレイアウト100回、ゲーム回数100,000回)で試してみた。
すると、158回成功したので、

成功率 158/100000 = 1/633

何も考えない初手からのプレイアウトの成功率1/1876173と比べると、2964倍成功率が上昇したことになる。一気に上昇したとはいえ、それでも成功率はまだ0.158%に過ぎない。

さて、次はどういう改善をしようか。
そろそろタイトルにしてるモンテカルロ木の話を始めようかな。

このアーカイブについて

このページには、2015年10月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2015年9月です。

次のアーカイブは2015年11月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。