TIM Labs
最近、Pythonが流行っている。以前はコンテンツの扱いに優れているとかで流行ったようだが、今は人工知能関連で流行っているようだ。
といっても、Python自体はAI関連の処理をどんどんできるほど高速な処理系ではない。
実はいくつかの拡張モジュールが用意されていて、それを使うことで高速性が要求されるAIを実装可能にしている。
その1つというか、ベースになっているのがNumpyで、配列が導入され、かつ計算処理でよく出てくる処理が一発でできるようになっている。
今回は、その一端をちょこっと紹介しておこうと思う。

しかし、こういう新しい分野は、なかなか日本語の情報が出てこなかったり、古い情報だったりするので、そういうことに煩わされないためには、はじめから英語で読んでしまったほうが楽になる。それに、しっかりしたドキュメントが無料で入手できる可能性も高くなる。
それで見つけたのが、これ。 Scipy Lecture Notes 2015 Edition

ScipyLectureNote.png
Numpy, Scipy, プロッティングなどまとめて書かれていて、360ページ以上ある。

そのなかのNumpyのところを読んでいたら、練習問題に素数を求めるのがあったので、その解説を元に書いてみた(prime.py)。

import sys
import numpy as np
np.set_printoptions(threshold=np.inf)   # 配列の ... 表示を抑制
N = int(sys.argv[1])+1                  # 引数の上限値を含める
is_prime = np.ones((N,), dtype=bool)
is_prime[:2]=0
N_max = int(np.sqrt(N))
for j in range(2,N_max):
    if(is_prime[j]):
        is_prime[j*j::j] = False        # 素数jの間隔で消していく
primes = np.arange(N)[is_prime]
print(primes,'\ncount:',primes.size)
コマンドレベルから直接実行してみた。引数に、調べる上限数を指定する。

$ python prime.py 1000
[  2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61
  67  71  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151
 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251
 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359
 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463
 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593
 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701
 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827
 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953
 961 967 971 977 983 991 997] 
count: 169
もし、printoptionsの指定がないと、
# np.set_printoptions(threshold=np.inf)   # 配列の ... 表示を抑制
こんな風になってしまう。
$ python prime.py 1000
[  2   3   5 ..., 983 991 997] 
count: 169
つまり、長い大量の情報は、 ... に置き換えてコンパクトに表示してくれる。 これが、大きなお世話になることも多々ある。

一番Numpy的な個所は、コメントに「素数jの間隔で消していく」と書いたところ。普通だったらループを回るところだが、Numpyでは、素数jの間隔で配列要素の値を書き換えることができる。このおかげで、ループ1階層分の時間短縮ができているとも言える。

巷では「ズンドコキヨシ」というプログラミング課題が流行っているらしい。そりゃなんぞや、というところだが、要点としては《「ズン」「ドコ」のいずれかをランダムで出力し続け、「ズン」「ズン」「ズン」「ズン」「ドコ」の配列が出たら「キ・ヨ・シ!」と出力して終了するプログラムを作成せよ》ということになるだろうか。既に多くの方が挑戦しているようで、以下にまとめられている。

ズンドコキヨシまとめ

すっかり波には乗り遅れている感じではあるが、それはともかくとしてもプログラミング課題としてとてもセンスが良い。ざっと思いつくプログラミング上のポイントは

  • 文字列出力
  • 乱数利用
  • 状態管理
  • 繰り返し、およびその中断

あたりだろうか。ツボを押さえたとても良い課題である。

というわけで、是非やってみたい。そう、敢えて、「手続き型」 Haskell で。

と、こんな表題で書くからには当然、「等価ではないこともある」と言いたいわけだが、その前に一般的な話をおさらいしておこう。

Ruby では表題の通り、 method1 { |e| e.method2 }method1(&:method2) は基本的に等価だとされる。こんな感じだ:

[1,2,3].map { |e| e.to_s } # => ["1", "2", "3"]
[1,2,3].map(&:to_s)        # => ["1", "2", "3"]

どちらの書き方が良いのか、というのは人やプロジェクトなどによりけりではあるが、後者のメリットのひとつとして「ブロック内の変数を命名しなくて良い」というものがある。我々ソフトウェアエンジニアにとって命名とは一般的に重労働であり、その労働力はできればもっと重要な箇所で使いたい。そんなわけで我々としてはできれば後者の記法を利用していきたいわけである。

ところが表題の通り、この二つは必ずしも同じ挙動になるとは限らない。実際に二つほど発見したので紹介しよう。

世はまさにJavascriptフレームワーク戦国時代。 新たなJSフレームワークが登場したと思えば、1年後にはオワコンとか言われていたりする、恐ろしい世界です。

React.js が流行ったと思えば、ReactはViewしか面倒見てくれないからFlux 入れようとか、 いやFluxちょっと使いにくいから Fluxxor 入れたほうが、いや Flummox の方がよさそうとか、redux だとか、もうわけわからん状態です。

実案件では今は Marionette.js を使っているんですが、そのことをフロントエンドエンジニア(jsの達人)の方に話したら、Backbone (Marionette) とかオワコンですよみたいな感じに言われたのが、ちょっとショックでした。

Javascriptフレームワークが乱立している世の中ですが、数あるフレームワークの中で人気を誇っているのがAngularとReactだと(私は)思っています。そのAngularの次期バージョンであるAngular2 のBeta版がついに登場したので、今回から数回にわたってAngular2を触ってみたいと思います。

なおAngular2はBeta版(2.0.0-beta.0)を利用していますが、今後大きな変更が入りサンプルコードが動かなくなる恐れがあります。

今回の目標

Angular2を開発できる環境を構築 & Angular2をとりあえず動かしてみる

モンテカルロ木探索では、プレイアウトするノードを選ぶ工夫をしていた。
なので、ここでは、プレイアウトするノードを選ぶ工夫を一切止めるとどうなるか試してみよう。

つまり、どの葉ノードも同じプレイアウト回数にするとどうなるだろうか。
ルートノードから指定レベルだけ木を展開し、その末端の全ての葉ノードについて、同じ回数だけプレイアウトしてみよう。
つまり、次図のようなことを試してみよう。

lab-calc15-1.png


そのために、親ノードと、木を展開する高さ(level)を与えると、子ノードの中で一番成功率の高いノードを親のメンバー変数bestにセットするようにした。

もちろん、このメソッドは、再帰的に呼ばれるようになっている。この、再帰的に行えるということは非常に有利な点である。 モンテカルロ木探索では、それまでの成功率が複雑に影響していたのだが、この単細胞モンテカルロ木探索(これは勝手に命名したものである。正式の言い方があるかも知れない)では、つねに一定回数のプレイアウトしかしないので、ノードの成功率や試行回数などを記録しておく必要もなければ、プレイアウトが終わったノードは除去してもかまわない、とてもメモリにやさしい方法である。

では、プログラムの修正部分を示す。

まず、この単細胞モンテカルロ木探索の核となる再帰的に調べるメソッドを示す。

	// 現在の盤面から指定レベル下の葉ノードで、指定回数playoutする
	void	simpletree( Node parent, int level ) {
		Stock	stock = new Stock();

		if( level == 0 ) {	// 指定回数のプレイアウトを行い、成功率を設定し、終了
			double	successsum = 0.0;
			for( int i=0; i<PLAYOUTCOUNT; ++i ) {
				successsum += simpleplayout();
				stock.restore();
			}
			parent.success = successsum / PLAYOUTCOUNT;
			return;
		}

		ArrayList<Move> list = getAllTefudas();
		boolean	istefuda = list.size()>0;
		if( list.size()==0 )
			list = getAllMoves();

		if( list.size()==0 ) {
			parent.success = restcount==0 ? 1.0 : 0.0;
			return;
		}
		parent.moves = list.size()==0 ? null : list;

		double	sumsuccess = 0.0;
		double	maxsuccess = -1;
		Node	bestnode = null;
		for( Move mv : list ) {
			Node nd = new Node( parent, mv );
			mv.exec();
			simpletree( nd, level-1 );
			if( istefuda ) {
				sumsuccess += nd.success;
			} else {
				if( nd.success > maxsuccess ) {
					maxsuccess = nd.success;
					bestnode = nd;
				}
			}
			stock.restore();
		}
		if( istefuda ) {
			parent.success = sumsuccess/list.size();
		} else {
			parent.success = maxsuccess;
			parent.best = bestnode;
		}
	}

そして、1ゲームを行うメソッドonegameから呼び出す。

	int	onegame() {
		initialize();

		int	step = 0;
		currentsuccess = 0.0;

		for(;;) {
			if( tefudatop == 0 )
				opentefuda();

			Node	root = new Node();
			simpletree( root, DEPTH );
			if( root.moves.size() == 0 )
				break;

			Node	nd = root.best;
			currentsuccess = nd.success;
			nd.move.exec();
			++step;
		}

		return	restcount;
	}

モンテカルロ木探索に比べると非常に単純になるのだが、これでも高い成功率が得られるのであろうか?

レベル	幅	成功率
4	20	60/100	0.600
5	20	72/100	0.720
6	20	83/100	0.830
7	20	82/100	0.820
7	50	90/100	0.900
8	2	82/100	0.820
8	20	46/52	0.885
9	3	43/50	0.860
9	5	92/100	0.920

この結果から分かることは、

  • 木の高さを増やす
  • 幅(葉ノードでのプレイアウト回数)を増やす
の2点である。いずれも増加させると、計算時間が掛かるようになる。幅の方は単に正比例する程度であるが、高さを増やすと、計算時間は指数関数的に増加してしまう。
結論として、単細胞モンテカルロ木探索でも、どうやら成功率90%くらいは達成することが分かったが、モンテカルロ木探索に比較して、やや成功率が落ちている。
単細胞モンテカルロ木探索の最大のメリットは、とにかくメモリを食わないことである。性能は、モンテカルロ木探索よりやや劣るが、予想以上の結果が出た。
ということは、このような不完全情報ゲームに対してモンテカルロ木探索を行った場合、不完全な部分がかなり支配的ならば、単細胞モンテカルロ木探索でも良いかも知れない。

さらに

ひとり遊び「計算」には、さらに難易度を上げた遊び方がある。

  • コンピュータ:最初に台札を全然出さない。
  • 超人:台札の山を3つにする。

コンピュータはやや難しくなる程度だが、超人は一気に難しくなる。
ここで紹介したモンテカルロ木探索でも、それらについて、ある程度の成功率を出すことができたが、技術的に特別なことは何もしていないので省略する。


おわりに

とらんぷの一人遊び「計算」について、できるだけ安直に成功率の高い方法を検討しようということで、モンテカルロ木探索を行い、さらに単細胞モンテカルロ木探索なるものまで試した。
面倒でも良いから、もっと高い成功率を得たいと思った人は、あれこれ試してい欲しい。頑張れば99%以上の成功率が得られることは、第2回(9月16日公開)に書いていたので、それを参考にさらに研究を進めることも可能と思われる。
この連載は、コンピュータ囲碁の世界で有名になったモンテカルロ木探索を、別の世界でも効果があるのかどうかを試すことであった。結論は、まずまずの成果だった。めでたし、めでたしということで、連載を終了とする。

まず最初に、プレイアウト回数を100万回にした場合の結果を示す。

	プレイアウト回数=100万、UCB定数=0.5, 閾値=5 で 94/100

プレイアウト回数を増やすと、成功率が着々と上昇し、90%を超えることができた。
といっても、たった100回しかゲームが行われていないので、甚だ精度が心もとない。本当なら1万ゲームくらいやり成功率を求めるべきなのだが、時間がかかるのでやめた。
それでも、100万回やれば成功率は9割を超えると言えるだろう。


さて、今回は、いままでのパラメータとは違う種類のパラメータをでっちあげ、有効性を調べてみよう。
プレイアウトが終わったときの2つの場合を示すので、この差について考えてみよう。

Hand:     _ : 
Table:  K  K  7(T)  K 
[1]  
[2]  
[3]  
[4]  TK

Hand:     _ : 
Table:  6(7)  9(J)  2(5)  7(J) 
[1]  JJAJ65K
[2]  AJ7T8
[3]  4TKK795T8
[4]  2K9Q

現状では、プレイアウトの結果の成功率の値は、1.0(成功) と0.0(失敗)しかない。 この事について考えてみる。

上の2つの場合、屑札として残ったカード枚数は、2枚と25枚である。一方は、成功まであと一歩の状態であるが、もう一方はどうにもならない大失敗である。この差をなんとかしようというのが今回のテーマである。
プレイアウトが終わったとき、屑札の山に1枚でも少ないほうが成功に近いと考えてみよう。

残り枚数1はありえない。理由の説明は省略するの、考えて欲しい。

それで、残り枚数に応じて成功率が変わるグラフを作ってみた。左側は従来のもので、右側が今回考えたものである。

lab-calc13-1.png

残り枚数が2枚、10枚、20枚となった場合、これら3つの状態の成功率をどれも0.0にするのではなく、それぞれ0.2, 0.05, 0.02 とかにできないであろうか。
それで、右グラフのような結果を出すメソッドを用意した。引数として、残り枚数を与えると、それに応じた妥当な成功率を返してくる。

グラフ中の縦軸のbは、残り枚数が2枚の時の成功率で、プログラム中ではBADMAXとなっている。

	// 残り札数から成功率を見積もる
	double	resttoSuccessRate( int r ) {
		if( r <= 1 )
			return	1.0;
		int failnum = (int)(MAXCOUNT*0.5);
		if( r > failnum )
			return	0.0;
		double sc = (1.0-(double)(r-2)/failnum);
		sc = BADMAX * sc * sc;
		return	sc;
	}

計算は相当いい加減にしているが、右図のような傾向があれば良い。もっと頑張りたい人は、自分で工夫して、素晴らしい結果になったら、ぜひ教えて欲しい。

このメソッドを simpleplayoutの最後で呼び出すようにすれば、修正はおしまいである。

	double	simpleplayout() {

		for(;;) {
			opentefuda();		//	手札をめくる

			ArrayList<Move>	list  = getAllMoves();		// 札の移動を考える
			if( list.size() == 0 )
				break;
	
			Move	mv = selectRandomly(list);
			mv.exec();
		}

		//	return	restcount==0 ? 1.0 : 0.0;
		return	resttoSuccessRate(restcount);
	}

では、この残り枚数を考慮した成功率に変更した場合の効果について調べてみよう。

条件:プレイアウト回数=10000, UCB定数=0.5, 閾値=5, ゲーム数=100

BADMAX	成功率/100
	0.00		56
	0.01		57
	0.02		57
	0.03		55
	0.04		55
	0.05		60
	0.06		57
	0.07		58
	0.08		59
	0.09		60
	0.1		53
	0.2		54
	0.5		51

この表を見ると、BADMAXが0.05〜0.09あたりがやや成功率が高くなる傾向がみられる。
といっても、100回程度の試行では誤差の方が大きい。

さて、モンテカルロ木探索はどうだったであろうか。
UCBにより、急に成功率が上昇したのであるが、成功率を非常に高くしようとすると、かなり大変である。
UCBの有無は成功率に著しい差が出るが、その他のパラメータの影響はさほどでもない。
パラメータをごちゃごちゃイジるよりも、プレイアウト回数を増やす方が確実に成功率が上がる。
しかし、このアルゴリズムにも根本的な欠陥がある。それは、序盤がとても下手なことである。中盤以降は極めて正確に最適に近い手、成功する手を選択しているようであるが、序盤は判断するに十分な統計的データが得られないので、良い手を打てないでいる。

これの対策をしようとすると、しっかり機械学習させるとか、屑札の山のカードの連鎖具合をしっかり調べるなどを行わなければいけなくなり、モンテカルロ木探索でお手軽に賢くするという趣旨から外れてしまうので、そのあたりまでは深入りしない。 もし、そのあたりで良い結果が出たら、連絡して欲しい。うまくやれば、99%以上の成功率が出ることがわかっているのだが、なんかスマートな、lazyな方法があれば素晴らしいことである。

さて、これで終わろうかと思ったが、次回は、ここまで説明してきたモンテカルロ木探索とは違う単純な方法で高い成功率を出すことにチャレンジしてみようと思う。
そんな方法は果たしてあるのだろうか?

「体系的に学ぶ 安全なWebアプリケーションの作り方」について

体系的に学ぶ 安全なWebアプリケーションの作り方」(通称徳丸本)はWebアプリケーションの脆弱性や攻撃技法とその対策についての定番中の定番と言える書籍です。

「体系的に学ぶ 安全なWebアプリケーションの作り方」表紙

書籍には付録としてVMWareのディスクイメージを収録したCD-ROMが付属し、仮想環境で脆弱性を試すことができます。

また、電子版ではディスクイメージのダウンロードURLが記載されています。

Webアプリケーション開発にMacを使っていて、VMWareではなくVirtualBoxやVagrantを使っている人も多いのではないでしょうか?

ここではOS XでVagrantを使って通称徳丸本の仮想環境を動かす方法を解説します。

前回、プレイアウト回数を1000にすることで、そこそこ成功することが確認できた。

それで、まず、プレイアウト回数を変更することで、成功率がどのように変わるか、100ゲームのシミュレーションをしてみた。 UCB定数=0.5, 閾値5, ゲーム数100としている。

UCB定数=0.5, 閾値5, ゲーム数100としている。

プレイアウト回数 成功数/100
	1000		17
	2000		28
	5000		40
	10000		53
	15000		59
	20000		65
	30000		72
	40000		69
	50000		77
	100000		80
	200000		86

それぞれのプレイアウト回数にて、100回ゲームしているだけなので、かなり誤差を含むのだが、傾向ははっきり読み取れる。つまり、プレイアウト回数を増やすと、成功率は上がるようだ。プレイアウト回数が10000以下では着実に成功率が上昇するのだが、20000を超えるあたりからプレイアウト回数の上昇が成功率の上昇にすこししか効かなくなってくる。そして、プレイアウト回数が3万回を超えたあたりから、効果はとても僅かなものになっている。

プレイアウト回数を10万回以上にすると、成功率が80%を超えるようだ。この調子だと、100万回プレイアウトすると、成功率90%の可能性もありそうだ。でも、やめておく。プレイアウト回数の上昇は有効なことが分かったが、限界もあるようだ。とりあえず、プレイアウト回数を増やしてテストするのはこのあたりで止めておく。なにしろ、プレイアウト回数を増やすと計算時間がかかってやってられないのである。


前回、モンテカルロ木探索のキモであるUCBの計算式を示した。

lab-calc10-2.png

この中に定数があるのだが、いままではとりあえず0.5で試してきた。このUCB定数を変更すると「計算」の成功率がどのように変わるかをじっくり調べてみよう。時間節約のため、プレイアウト回数を10000回で行った。

	UCB定数		成功数/100
	0.0		0
	0.0000001	30
	0.000001	21
	0.00001		18
	0.0001		25
	0.001		31
	0.005		32
	0.01		39
	0.05		45
	0.1		54
	0.2		53
	0.5		52
	1.0		53
	10.0		51 

USB定数は、0.1を超えると、ほとんど変化しないようだ。
0.1を切るとどんどん成功率は下がるのだが、0.0001くらいまで下がると、20〜30%程度の成功率に落ち着いて、0.0にすると成功率も一気に0に落ちる。
これから、USB定数は0.1以上だと何でもよさそうに思える。それで、今後は0.5とすることにしよう。 USB定数の値は木の形や成功率(勝率)など、対象が変われば変わると思われるが、追求はこのあたりでお終いにしておこう。


もう1つのパラメータとして、閾値がある。つまり、葉ノード(末端ノード)に対して、最大何回のプレイアウトを行うかによっても成功率が変わるはずだ。

閾値 成功数/100 1 49 2 50 3 51 4 61 5 56 6 63 7 60 8 54 9 55 10 55 20 55

総試行数(ゲーム数)が100回と少ないのであるが、この表から閾値は4〜7あたりが良い感じである。
これは、プレイアウト回数が10000回で行っのだが、プレイアウト回数が増えると、それに伴って最適な閾値も徐々に増加してくるのではと思うが、あまり急激な変化はないようだ。
さて、閾値1というのは、葉のノード1つについてプレイアウト回数が1回ということである。つまり、10000回プレイアウトしているので、葉ノードが10000個になっているはずである。これは、木が実をたわわにつけるのではく、枝をどんどん伸ばし、先端の葉にたった1つの実をつけた状態である。そんな状態でも、成功率はたいして落ちないのは興味深い。


今回は、モンテカルロ木探索で調整される一般的なパラメータをいろいろいじって効果を見てみた。
それでわかったことは、とにかくプレイアウト回数を増やすのが良いということだ。
つまり、微妙な調整を頑張るよりも、マシンパワーに頼る方が良い結果が出るというよくある面白くない結果になってしまった。
ということで、次回までに、100万回プレイアウトという条件で実験しておこう。
そして、次回は、一般的でないことにも挑戦してみようと思う。

さて、モンテカルロ木探索が紹介されている情報を探すと、UCTアルゴリズムが紹介されている。 より正確に言うと、UCB(Upper Confidence Bound)によって比較するものである。

詳しくは、いくつかリンク先を紹介しておくので、詳細は自分で調べよう。

computer-igo-matsubara.jpg
  1. 「モンテカルロ木探索 並列化、囲碁、マリオAI 」美添一樹
    ちらっと勉強するだけなら、これで十分かな。
  2. これで書ける「コンピュータ囲碁講習会」 動画(電通大・イベント), 資料ページ
    2015年の夏に電気通信大学で行われた講習会。ビデオ、資料、ソースコード一式揃ってあるので、必見。
  3. 「コンピュータ囲碁 モンテカルロ法の理論と実践」松原仁編
    これが一番まとまっているかな。

さて、成功率だけで評価していたのだが、これはうまく行かなかったのだ。
それで、成功率だけでなく、プレイアウト回数が妥当かどうかも含めた評価値を用意する方法が必要だ。

プレイアウト回数が少ないと、たとえば1回だけだとすると、その1回で失敗していると評価値が非常に悪い。でも、実際にはとても成功率が高いのだが、偶然プレイアウトに失敗しているかも知れない。たった1回の失敗で、そのノードが低く評価され、二度とプレイアウトされないのはとてもまずいことだ。
それで、プレイアウト回数が少ないほど評価値が上がり、プレイアウトする確率が高まるべきである。

で、一気に、UCB値なるものの式を示す。要するに、専門書でちょっと勉強してきた。

lab-calc10-2.png

あるノードに対して、札移動を行ってできる全子ノードを考えるわけだが、プレイアウト数が少ないほど評価値を高めるには、プレイアウト数を分子に入れるのは直ぐ考えつくだろう。
単純に、 総プレイアウト数/プレイアウト数 とすると、総プレイアウト数が増加したときの効果が出過ぎるので、理工学ではとてもよくやる手である対数を利用する。
そして、この割合の平方根をとって、適当な係数を掛けたものを成功率に加えてUCB値としている。

定数が0だと今まで通り、成功率だけの評価になる。
定数を増やしていくと、成功率よりも既存のプレイアウトの分布を意識するようになる。
実際には定数を適当な値、たとえば0.5あたりに設定して実行すると良いらしい。

なお、この数式のもっと詳しい意味については、論文もいろいろ発表されているので、自分で調べよう。

これに基づき、特定のノードに対するUCBを計算するメソッドを用意した。
といっても、数式そのまんまなので、何の説明も不要だろう。

	double	getUCB() {					// UCB1
		return	success + UCBCONSTANT * Math.sqrt(2.0*Math.log(parent.playcount)/playcount);
	}

前回と同じ void playouttree( Node node ) の中を以下のように書き換え、UCB値の最大になるノードを見つけるようにした。

			if( node.childmovetype ) {		
				// UCB式に従って枝を選択し、playoutを進める
				double	maxucb = -1;
				for( Node nd : node.childrenpre ) {
					if( nd==null )
						continue;
					double ucb = nd.getUCB();
					if( maxucb < ucb ) {
						maxucb = ucb;
						selectednode = nd;
					}
				}
			} else {

同様に、 void makeMoveBranch( Node parent ) の中も変更した。
移動に対する子ノードを用意するメソッドだが、最初に全子ノードについて1度ずつプレイアウトしており、それでも不足の場合に、さらにプレイアウトを増やすとき、どのノードについてプレイアウトするかについて、UCB値を使っている。

		for( ; i<+i ) {
			stock.restore();
			if( list.size()>0 ) {		// 子供がいる場合は、子供のどれかでplayout
				Node maxnd = null;
				double	maxucb = -1.0;
				for( Node nd : parent.children ) {
					double ucb = nd.getUCB();
					if( ucb > maxucb ) {
						maxucb = ucb;
						maxnd = nd;
					}
				}
				maxnd.move.exec();
				double sr = simpleplayout();
				maxnd.addSuccess( sr );
			} else {			// 子供がいない場合は、自身でplayout
				double sr = simpleplayout();
				parent.addSuccess( sr );
			}
		}

UCBへの変更は、たったこれだけで済む。

ということで、早速実行してみよう。
条件は、プレイアウト回数=1000, UCB定数=0.5, 閾値(ノードに対する最大プレイアウト数)=5にて実行してみた。
失敗することも多いのだが、次のように成功することもある。

	Game end, rest=0	1/1  1.00000 
Hand:     _ : 
Table:  K  K  K  K 
[1]  
[2]  
[3]  
[4]  

ということで、 プレイアウト回数=1000, UCB定数=0.5, 閾値=5, ゲーム数=100 で実行してみた。つまり、100回プレイしてみた。

	Game end, rest=16	18/100  0.18000 
Hand:     _ : 
Table:  J(Q)  K  8(J)  7(J) 
[1]  TK7Q95JT2K 
[2]  JA 
[3]  K6 
[4]  A4 
----- FINISHED -----

100回で18回成功した。まあ、走らせる度に成功率は違うのだが、だいたい20%前後である。

とりあえず、ほぼ成功率が0.0%が、UCBを計算に使うことで一気に上昇した。
いままで、ほとんど成功しなかったものが、ある程度成功するようになったので、劇的な進歩である。
まだ何もパラメータを調整していないので、次回以降、そのあたりを調整することで、成功率の上昇に挑戦してみよう。

前回、次図のようになった。

     Game end, rest=32       0/1  0.00000 
Hand:     _ : 
Table:  8(9)  6(8)  9(Q)  J(2) 
[1]  Q9TTKKA5J85JKQ829QA7KA254TJT6937 
[2]  
[3]  
[4]  

札が屑札[1]に延々と重なるが、他の屑札 の山にはさっぱり重ならないことが分かった。

なぜ、こうなってしまうのだろうか。


まず、プレイアウトだけれど、まだ始まったばかりの状態では、成功率は0に限りなく近い。まあ、常に0が出ると仮定しても問題ないくらいだ。

手札をいずれかの屑札の上に重ねるとき、屑札[1]〜屑札[4]のいずれかの山への移動を行うわけだが、プログラムでは[1]から順番に調べるようになっている。
そして、[1]〜[4]のなかで、そのノード(札移動とノードは対応する)の今までの成功率を調べ、成功率が一番高いノードを選び、そのノードに対する盤面の状態からプレイアウトして、成功/失敗をシミュレーションするのであった。

さて、成功率だが、プレイアウトすると、ほぼ確実に、99.99%の率で成功率0.0となるのだった。
また、まだ一度もプレイアウトしていないノードの成功率は0.0 としているので、選ぼうとしている現ノードの直下のノードの成功率はどれも0.0 の筈なのだ。

全て同じ0.0 の成功率のノードの中から比較して一番成功率の高いノードを選択しているのだが、これが結局いつも最初のノードを選ぶことになっているのだ。

lab-calc10-1.png

さて、こうなる部分のソースコードを見てみよう。とくに、カードを移動する場合に、どの移動を選択するかの部分に注目してみよう。
void playouttree( Node node )の中の以下の部分が該当する。

			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 {

条件判断が、if( max < nd.success ) となっているので、最も大きい最初のノードが選ばれる。
これを、次のように変えてみた。

			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 {

不等号に=を加えたのだが、同様の比較が成功率を再帰的に書き換える場所にもあるが、全く同様なので説明を省略する。

さて、これで、結果はどうなるだろうか?
最終結果が次:

         Game end, rest=23       0/1  0.00000
Hand:     _ : 
Table:  3(4)  Q(A)  8(J)  K 
[1]  
[2]  
[3]  
[4]  9TKKJ6T9A8K7A744JJ575Q3

今度は、最後の[4]がゴミ札だらけになったので、想定通りである。
一応、最初のあたりも載せておく。

Hand:     K : 9QJT56789TJQKA23456789TJQKA23456789TJQKA2345678

---- game ----  step  1  success= 0.00000
Hand:     T : 9QJT56789TJQKA234567898JQKA23456789TJQKA234567
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  K
[2]  
[3]  
[4]  

---- game ----  step  2  success= 0.00663
Hand:     3 : 9QJT56789TJQKA234567898JQKA23456789TJQKA27456
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  K
[2]  T
[3]  
[4]  

---- game ----  step  3  success= 0.00000
Hand:     8 : 9QJT56789TJQKA234567698JQKA23456789TJQKA2745
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  K
[2]  T
[3]  3
[4]  

---- game ----  step  4  success= 0.00000
Hand:     Q : 9QJT56789TJ5KA234567698JQKA23456789TJQKA274
Table:  A(2)  2(4)  3(6)  8(Q) 
[1]  K
[2]  T
[3]  3
[4]  

最初は色々な山にバラバラに積まれていくようだが、あるところから最後に固まってしまうみたいだ。
これも、たぶん、どの屑札の山を選んでも成功率が0になり、比較に等号が入ったので、最後が選ばれるようになった結果であろう。

さて、両極端な例が確認できたのであるが、成功率を大いに考慮し、成功率が高いノードでさらにプレイアウトするのはもちんなのだが、成功率が低いとか、まだ一度もプレイアウトされていないノードなども考慮したノード選択をすべきであろう。

というところまで分かったが、実際にはどうすれば良いのだろうか?
何かうまい方法は考案されていないのだろうか?

最近のコメント