TIM Labs

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

ズンドコキヨシまとめ

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

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

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

というわけで、是非やってみたい。そう、敢えて、「手続き型」 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になり、比較に等号が入ったので、最後が選ばれるようになった結果であろう。

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

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

さて、ひと通り完結するまで、あと少しであるので、完成させ、ちょっと走らせて様子を見てみよう。

実際に新しいノードを付け加える処理を以下に示す。

	// 手札をめくってでた札(数)に対する、新しいノードを1つだけ作る。
	Node	makeOpenBranch( Node parent, Move mv ) {
		int 	i = mv.fudanum;
		Node	nd = parent.children[i];
		if( nd==null ) {
			nd = parent.children[i] = new Node( parent, mv );
			++parent.childcnt;
		}
		
		return	nd;
	}

やってきることは、親と子ノードの関係を調整しているだけであるので、細かい説明は省略する。


もう1つ出てくるのが、Nodeクラスのメンバーメソッド addSuccess( double sr ) である。

		void	addSuccess( double sr ) {
			++playcount;
			successsum += sr;
			success = successsum / playcount;
			recountSuccess();
		}

これは、プレイアウトした結果得られた成功率(1.0または0.0)を木に反映させる。

注目しているノードに関しての処理だけでは不十分で、木を上にたどりながら、プレイアウト回数および成功率を木のルートに至るまで書き換えていかなければならない。
そのために、recountSuccess()を用意した。


成功率の書き換えを次で行っている。

		// 成功率を再帰的に書き換える
		void  recountSuccess() {

			for( Node pr=this; pr!=null; pr=pr.parent) {
				if( pr.childcnt == 0 )
					continue;
				pr.playcount = 0;
				for( Node nd : pr.children )
					if( nd != null )
						pr.playcount += nd.playcount;
				
				if( pr.childmovetype ) {		// 成功率最大を選ぶ
					double	max = -1;
					for( int i=0; i<pr.children.length; ++i ) {
						Node	ch = pr.children[i];
						if( ch==null)
							continue;
						if( ch.success > max ) {
							pr.success = max = ch.success;
						}
					}
					pr.success = max;
				} else {		// 手札をめくる場合	// 成功率は平均となる
					double	ave = 0.0;
					for( Node ch : pr.children ) {
						if( ch==null )
							continue;
						ave += ch.success * ch.playcount / pr.playcount;
					}
					pr.success = ave;
				}
			}
		}

最初のforループを周回する度に、木を1段ずつ上がっていく。

最初のところで、プレイアウト総数の計算を行っている。

次に成功率を求めているのだが、札を移動する場合と、手札をめくる場合に場合分けされている。
札移動の場合には、子のノードの中から、一番高い成功率を親ノードの成功率としている。
手札オープンの場合には、どの手を選ぶかの選択権はなく、神の指示に従うしかないので、子ノード全体の成功率の平均を求めて、親ノードの成功率としている。


さて、これで一応必要なものは準備できたので、実行してみよう。

プレイアウト数を1000回、閾値を5で実行してみた。

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

なぜか[1]の屑札の山だけにたくさんあって、他の屑札の山には何もない。
なぜ?

最初の方も見てみよう。

Hand:     Q : K9JT56789TJQKA23456789TJQKA23456789TJQKA2345678

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

---- game ----  step  2  success= 0.00059
Hand:     4 : K9JT56789TJQKA23456788TJQKA23756789TJQKA23456
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  Q9
[2]  
[3]  
[4]  

---- game ----  step  3  success= 0.00059
Hand:     T : K9JT56789TJQKA234567886JQKA23756789TJQKA2345
Table:  A(2)  4(6)  3(6)  4(8) 
[1]  Q9
[2]  
[3]  
[4]  

---- game ----  step  4  success= 0.00053
Hand:     T : K9JT56789TJQKA234567886JQKA237567895JQKA234
Table:  A(2)  4(6)  3(6)  4(8) 
[1]  Q9T
[2]  
[3]  
[4]  

最初から、ずっと屑札[1]にしか札が積まれていない。
最後の台札の状態

Table:  8(9)  6(8)  9(Q)  J(2) 

を見ると、少しは台札に重ねられているが、手札屑札移動は、手札→屑札[1] に限定されているようだ。

なぜ?
これでは絶対に成功しない。
何か間違えたかな。
...ということで、この原因を次回までに考えよう。

最近のコメント