TIM Labs

2015年9月アーカイブ

前回、「計算」のプレイに必要なデータと基本となるメソッドを紹介した。
今回は、これらを組み合わせて、「計算」を最後までプレイするメソッドを仕上げる。

現状の盤面から始めて、ひたすら何も考えずランダムにプレイするメソッド simpleplayout を用意した。
	double	simpleplayout() {

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

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

		return	restcount==0 ? 1.0 : 0.0;
	}
プレイを続けられる限り永久ループを繰り返し、続けられなくなって抜けたところで、残り枚数を調べ、成功率をdouble(1.0または0.0)で返す。
返り値として、残り枚数やtrue/falseにせず成功率sにしているのは、モンテカルロ木探索で利用することを考えてのことであるが、理由については読み進めば自然に分かると思う。

ループ中では、手札を表にできれば行う。
次に、可能なカードの動きを集め、可能な動きがないとき、ループを終える。
可能な Move があるときは、そのうちの1つの Moveオブジェクトを実行する。

手札のオープンは、まず手札のオープン状態を調べ、オープンしない、できない場合は単に終了する。
そうでないとき、残り手札の中から1枚選び、手札のトップと、手札配列を更新する。
	void    opentefuda() {
		if( tefudatop != 0 || tefudalen <= 0 )
			return;

		// 手札から一枚選ぶ
		int  r = rnd.nextInt(tefudalen);
		tefudatop = tefuda[r];
		tefuda[r] = tefuda[--tefudalen];
	}
可能なカードを動きを全部集めるのが getAllMovesメソッド。
Moveの空リストを作り、屑札台札移動可能な場合をリストに加える。
表の手札がなければそこまで。
次に、手札台札で可能な場合をリストに加える。手札台札移動は常に可能なので、直接Moveオブジェクトを作っている。
	ArrayList getAllMoves() {
		ArrayList list = new ArrayList();

		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);
		}

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

		return	list;
	}
カードの移動Move リストの中から1つだけ選ぶとき、0個、1個と2個以上に分け、2個以上の場合だけ乱数で選んでいる。
	Move	selectRandomly( ArrayList list ) {
		int	sz = list.size();
		if( sz == 0 )
			return	null;
		if( sz == 1 )
			return	list.get(0);
		
		int  r = rnd.nextInt(list.size());
		return	list.get(r);
	}
以上で道具は揃うのだが、初期状態にする initializeが必要である。
読めば分かると思うが、最後に台札の初期化を行っている。 LEADLEVELが台札に最初に何枚乗っていたかを示す。1のとき「計算」になり、0のとき「コンピュータ」になる。2以上にすれば、最初から台札に何枚も重なった状態から始めることができる。
メソッドinitdaifuda(d)は、台札の山をdで指定し、一定間隔開いた数字の札を載せる。札を載せることで、その分手札の山が減るので、その対応もしている。なお、initdaifuda(d)は省略する。
	void    initialize() {
		MAXCOUNT = MAXNUM * DAINUM;

		tefudalen = 0;
		for( int i=0; i<DAINUM; ++i )
			for( int j=1; j<=MAXNUM; ++j ) {
				tefuda[tefudalen++] = j;
			}
		tefudatop = 0;
		
		kuzu	= new int[KUZUNUM][MAXCOUNT];
		kuzulen = new int[KUZUNUM];

		for( int i=0; i<DAINUM; ++i ) {
			daifudatop[i] = 0;
			daifudanext[i] = daifudagap[i];
		}
		
		restcount = MAXCOUNT;
		
		for( int i=0; i<LEADLEVEL; ++i ) {
			for( int d=0; d<DAINUM; ++d ) {
				initdaifuda(d);
			}
		}
	}
ここまで準備ができたら、動かすことができる。
1回だけプレイするのが、 メソッドonegameであり、とても簡単。
	double	onegame() {
		initialize();
		return	simpleplayout();
	}
これを延々と呼びだして、成功回数を計算するメソッドgames()を用意した。
	void games() {
		int	success = 0;
		
		for( int i=0; i<GAMECOUNT; ++i ) {
			
			if( onegame() > 0.5 )
				++success;
		}
		
		System.out.printf("\n\tGame end,\t%d/%d %8.5f\n", 
				success, GAMECOUNT, (double)success/GAMECOUNT );
	}
ここまでで、実際にプレイアウトすることができる。若干示していないメソッドなどあるが、勝手に加えて動くようにしよう。

さて、これで、どのくらいの成功率になるだろうか?
それは、次回のお楽しみにしよう。

今回から、実際にプログラムの開発を行っていこう。
プログラミング言語はスピードが出る言語でかつそこそこ高機能なら何でも構わないのだが、とりあえずJavaで書くことにした。

今回は、モンテカルロ木探索の有効性を確認するだけなので、ガチガチにコーディング規則に則って書くのはやめて、気楽に書く。動作確認だけなので、GUIは省略し、CUI、それもほとんど出力だけのものにする。

そうなると、プログラムもかなり短くなるはず。Javaなので、当然オブジェクト指向にはなるのだが、いっぱいクラスを作ってということは止めて、一人遊び「計算」のクラス Caliculation を1つだけ用意し、もしクラスにしたいものが発生した場合は、Caliculation内のサブクラスで済ます。

まず、全体で必要な定数を決めておく。


public class Caliculation {

	int		MAXNUM = 13;
	int		KUZUNUM = 4;
	int		DAINUM = 4;
	int		MAXCOUNT = MAXNUM * DAINUM;
大文字にして定数らしさを出しているが、実際に定数にしていないのは、「計算」だけでなく、「コンピュータ」や「超人」さらには、その他のバリエーションにも対応できるようにしたためだ。これらのバリエーションは、コマンド引数で指定することができ、それに従ってこれらの数字を変更してから走らせるためである。

まず、盤面を管理するためのデータを用意する。

lab3-1.png屑札の山はKUZUNUM 個存在し、長さは余裕をもって全カード枚数である MAXCOUNTとしている。
各屑札の山にあるカード枚数も記憶する。
屑札のトップだけが直接参照されるのだが、別に変数を用意することはしない。

手札として、全カード枚数をサイズとする配列 tefuda を用意している。
どんどんカードをめくると手札の枚数が減るが、現在まだ表になっていない手札の枚数をtefudalenとする。
手札のトップは特に重要なので、別の変数 tefudatop を用意する。
手札をめくる行為は、tefudaにある有効なtefudalen枚のカードから1枚を抜いて、tefudatopに移すことである。

台札は、どんどん重ねていくが、トップだけが意味あるので、daifudatopという配列を用意した。
そして、台札はトップ以上に、その上に重ねられる数が重要なので、daifudanextを用意した。
台札に次に重ねられるカードの数字は、台ごとに差が決まっていて、それをdaifudagapに用意した。この値はプログラム実行中に変化することはない。

	// 屑札
	int[][] kuzu 		= new int[KUZUNUM][MAXCOUNT];
	int[] 	kuzulen 	= new int[KUZUNUM];

	// 手札
	int[]	tefuda 	= new int[MAXCOUNT];
	int 	tefudalen;
	int 	tefudatop;

	// 台札
	int[]	daifudatop  = { 0, 0, 0, 0 };	// 台札
	int[]	daifudanext = { 1, 2, 3, 4 };	// 次における札
	int[]	daifudagap  = { 1, 2, 3, 4 };	// 台札の前の数字とのギャップ(固定)
これだけの変数を操作することで、「計算」のカードの動きを全て表せる。
以降の説明では、これらの全カードの状態を「盤面」ということにする。

あと、いくつかの補助的な変数を用意する必要がある。

成功したかどうか、つまり全てのカードが台札に積まれたかどうかの判断が必要なので、まだ積まれていないカードの枚数を示す変数 restcount を用意した。
	int		restcount = MAXCOUNT;
カードの動かし方にはいくつかの種類があり、それを区別するためにenumを使ってみた。
直感的に判りやすいように、4つの動きを漢字で表現してみた。Javaはこういうこともできるということで。
	enum MoveType { 手札, 手札台札, 手札屑札, 屑札台札 };

「計算」では、ランダムな操作が頻繁に出てくるので、乱数を生成するためのRandomオブジェクトを1個用意した。
とりあえず、現時刻で初期化している。
	Random rnd = new Random(System.currentTimeMillis());		// 乱数
このような処理では、乱数は非常に重要で、乱数が乱数になっていないと、良い結果が得られない。
そのため、乱数の使用には最新の注意が必要である。本来なら、メルセンヌ・ツイスタ乱数を使うべきであるが、わかりやすさを優先して(横着をして)標準のもので済ました。

これで、とりあえずデータは揃った。
次に行うべきは、カードの動きを表現することである。 MoveTypeを用意したのだが、それらの4種類の移動タイプがどういうものか、実体を作らないといけない。

移動クラスMove
	class Move {
		MoveType	typ;		// 手札、手札台札, 手札屑札, 屑札台札
		int		fudanum;	// 札番号 1〜K
		int		dainum;		// 台札番号 0〜
		int		kuzunum;	// 屑札番号 0〜
移動が決まれば、現在の盤面は常にわかっているので、カードの番号は必然的に決まるのだが、とりあえず持っておく。しかし、実際に移動を伴わないタイプが「手札」の場合には、札番号だけが肝心な情報である。
これらを同じ Moveにまとめてしまったので、札番号が入っている。
タイプによっては、不要なデータ項目もあるが、これえらをまとめて、1つのオブジェクトで移動を示すことにした。

Moveオブジェクトの生成は2つ、カードの移動を伴う場合と、手札をめくる場合で別々に用意した。
		Move( MoveType tp, int n, int kuzu, int dai ) {
			typ = tp;
			fudanum = n;
			dainum = dai;
			kuzunum = kuzu;
		}

		Move( int n ) {
			typ = MoveType.手札;
			fudanum = n;
		}

次に、この Moveサブクラスの中に、実行メソッドを追加する。
		void	exec() {
			switch( typ ) {
			case 手札:
				execTefuda(fudanum);
				break;
			case 手札台札:
				execTefudaDaifuda(dainum);
				break;
			case 手札屑札:
				execTefudaKuzufuda(kuzunum);
				break;
			case 屑札台札:
				execKuzufudaDaifuda(kuzunum,dainum);
			}
		}
これでは、タイプ別に異なるメソッドを実行しているだけに過ぎないのだが、判りやすいからこれでよい。
メソッドexecから呼び出される4つのメソッドは、計算全体のクラス、Calculationのメソッドとして用意してある。

全部説明するのは面倒なので、屑札台札の場合だけを説明する。
	void execKuzufudaDaifuda( int k, int d ) {
		int n =kuzu[k][--kuzulen[k]];
		movetodaifuda( n, d );
	}
屑札の山kから、台札の山dへカードを移す。このメソッドは、必ず移動可能な場合だけ呼ばれるので、エラーチェックはしなくてよい。
まず、指定の屑札の一番上のカードを取り出し、そのカードnを台札の山dへ移すメソッドmovedaifudaを呼び出す。

メソッドmovetodaifudaは、屑札台札の場合だけではなく、手札台札の場合にも共通につかえるので、別メソッドになっている。
	void	movetodaifuda( int n, int daito ) {
		daifudatop[daito] = n;
		--restcount;

		if( n == MAXNUM ) {
			daifudanext[daito] = 0;	// 不可能を設定
			return;
		}

		daifudanext[daito] += daifudagap[daito];
		if( daifudanext[daito] > MAXNUM )
			daifudanext[daito] -= MAXNUM ;
	}
台札にK(MAXNUM)を移動し終えたら、その台札の山は終了するので、次の台札候補を0にしている。
次の台札の計算を最後にやって終わっている。

こんな感じで、札の移動ができる。
そして、これらを組み合わせると、とりあえずでたらめだけれども、プレイすることだできるようになる。
次回は、今回説明したことを組み合わせて、ルールを守る以外でたらめなプレイをする「プレイアウト」なるものを説明する。

前回、ひとり遊び「計算」のルールを説明したが、実際にプレイしたであろうか。


次図に、実際のプレイの終盤の状態を示す。

手札はT10)が見えていて、まだ表になっていな手札が1枚だけ残って、それが4である。


lab2-1.png



この状態から、手札、屑札の全てのカードを、台札の上に全て重ねることができ、成功するのであるが、その順番は分かるであろうか

実際には、成功可能な状態になっているのに、失敗してしまうことが多いであろう。

失敗しないためには、どういう戦略を立てれば良いだろうか。


台札の上に重ねるにに、A−2−3−、2−4−6−、3−6−9−、4−8−Q−の順(正順)に考えるのではなく、次図のように、各台札について逆順列を用意し、屑札の上のカードが、この順序に並ぶようにすると良い。


lab2-2.png

屑札の上に重なったカードは、この逆順にうまくつながっていれば、いくら重なっていても気にする必要はなく、最後はするすると全部取り出せて台札の上に重ねられ成功となる。


次図に、それぞれのカードをどの台札の上に載せることになるのか丸付き数字で示した。丸の中の1〜4は、載せる台札の山の番号を示す。


lab2-3.png

でも、これでは分かりにくいだろうから、この順番に糸が絡むことなく取り出せることを下図に示す。

屑札は、適当に間を開け配置したので、右端から順に取り出し、台札に載せられることが分かりやすくなっただろうか。


lab2-4.png


このように綺麗に最後が片付くためには、そうなるように屑札の上にカードを重ねないといけない。

ここで、最後に一気に取り出せたカードは、どのようにして上手く重なっていたのか、最初の方を見てみよう。


次図が最初の20手までのカードの動きである。丸数字は、手番号を示す。

4手目でQを屑4に出しているが、17手目で台4に重ねることで、屑4にカードが一旦無くなったことを示す。


lab2-5.png

終盤と序盤の屑札を比べると、序盤に屑1〜4に載せられたカードのかなりが最後まで残っていることが分かるだろう。つまり、序盤にしっかり考えて、最後にするすると全て取り出せるように、あるいは取り出せる可能性が高くなるようにどの屑札の上に重ねるかが「計算」の成功率を上げる鍵となる。


野崎昭弘氏の「とらんぷ」に成功率を上げる戦略があったので、紹介しておく。

Kは適当に置くとその下のカードが死んでしまうので、K用の屑札の山を確保しておく。

台札に早く付けられるカードと遅くでないと付けられないカードがある。Aは遅め、Qは2枚が早く残り2枚は遅い、Jはだいたい遅い。この早い遅いを考慮し、早いカード用の屑札の山、遅いカード用の屑札の山を決めておく。


で、そのあとは、上の図で示したように、逆順に繋がるように工夫してどの屑札の山に置くかを決める。その場で直ぐにはつながらないことが多く、今後出てくるカードのことを考えて、後から繋がったり、あるいは台札に出すことも考えて、要するにあらゆる可能性を考えると成功率は上がっていく。


成功率であるが、普通にやる程度ではなかなか50%に達しないと思う。屑札上の繋がりをきちんとメモしながら熟達してくると、8割は行くであろう。


ところで、コンピュータを使って、しっかり調べてプレイすればどこまで成功率が上がるのであろうか。

こういうことは、ネットで調べると直ぐに結果が得られる。便利な時代だ。


カルキュレーション(Wikipedia)

田中哲朗:『部分ゲームの解析結果を用いたカルキュレーションの戦略』情報処理学会論文誌、3064-3073

田中氏のカルキュレーションのページ



田中氏といえばGPS将棋の人というイメージだが、実際にはゲーム情報学の専門家で、幅広い研究で知られている。


計算の成功率は、田中氏の論文によると、99%を確実に超えるようである。

論文をしっかり読んだ訳ではないのだが、いろいろ頑張って高い成功率を達成したようだ。

しかし、今回のモンテカルロ木探索を使った実験とは方針が相容れないので、こういう努力は今回は排除する。

あくまでも、ほとんど成功しない超バカなプログラムを用意し、それをモンテカルロ木探索と組み合わせるとそこそこ高い成功率を出せることを検証する。


計算のバリエーション:

コンピュータ:台札のA,2,3,4は最初から出さず、手札から出てきたときに出す。直ぐに台札に出さなくてもよい。他は計算と同じ。

超人:屑札の山を3つにしたもの。他は計算と同じ。

いずれも、計算よりも難しくなる。とくに超人は難しくなり、本当に超人向きになる。


次回は、ほとんど成功しない馬鹿なプレイヤー・プレイヤについて説明する。




最近、将棋や囲碁のプログラムが非常に強くなった。将棋は機械学習を取り入れるようになったのだが、囲碁は「モンテカルロ木探索」という方法を取り入れて、一気にアマチュア高段者レベルに達した。

難しいと言われる囲碁でこれだけ成果を出した「モンテカルロ木探索」を、別の分野で試し、有効性を検証してみることにした。


ゲームをプログラムにプレイさせるとき、一般にはゲーム木なるものを作り、それぞれの手を選んだ時の勝率を計算し、より勝率の高い手を選ぶことで実現するのが一般的だ。木を完全に展開できる場合、つまり全ての可能性を読み切れる場合はそれでお終いなのだが、ほとんどのゲームは読み切れるほど木が小さくないので、適当なところで盤面を評価し、各葉ノード値とし、それを元に次の一手を選ぶ。このとき、盤面評価の性能が強いか弱いかを決めることになる。


しかし、盤面評価は難しい。この難しい部分を、定石などに基づいてガチにプログラムを組むことが行われていたが、なかなか成果が出ないのが現実である。そこで、当然考えられるのが、盤面評価が面倒なら、面倒なこと自体を放棄しよう。どうせ無駄だ、、、という考えがある。


面倒なプログラムを書くには、対象にしているゲーム(課題)を十分に研究しないといけないが、全部やめてしまうとどうなるか。でも、最後までプレイして、勝ったか負けたか、あるいは成功か失敗かくらい分かれば何とかなるかも知れないではないか。ということで、何の知識も持たない、ただルールを厳守するだけのどうしようもないプレイヤー・プログラムを用意し、これとモンテカルロ木探索を組み合わせて、十分強い、十分賢いプログラムができるかどうか検証してみる。


囲碁は、二人完全情報ゲームである。類似のものとして、オセロがあり、これは本ブロクでも紹介されているので別のことを考える。まず、二人でないゲームとして、一人と多人数という選択肢があるが、一人の方がプログラムが楽そうなので、一人ゲーム、一人遊びを選択する。完全情報ゲームはやめて、不完全情報ゲームを選ぶ。また、はっきり有限手数で終わるものを選ぶ。つまり、一人有限完全情報ゲームでモンテカルロ木探索の有効性を検証する。



さて、利用するひとり遊びは、トランプのひとり遊びの中から「計算」を選んだ。このひとり遊び(ソリティア)は、数学者&コンピュータ研究者として著名な野崎昭弘氏の「とらんぶ」ダイヤモンド社、初版昭和49年により知った。

一度絶版になったが、今は朝日選書として復刊しているようだ。



tramp1.jpg   tramp2.jpg



計算のルール


準備:


ジョーカーを除いた52枚のカードを使用する。ただし、スーツ(種類)は無視する。

A,2,3,4の4枚を取り出し、並べる。これらが台札である。

4つの台札の下に、4つの屑札をおける場所を確保しておく。

のこり48枚のカードは、しっかり切って、重ねて手札とする。


lab1-1.png

各台札の上には、それぞれ最初の台札(1,2,3,4)だけの間隔を開けてカードを重ねることができる。

つまり、次のようになる。Kの次には、A,2,...と繋がると考える。

なお、全ての数字を1文字表示にしたいので、10はTで示している。


lab1-2.png

プレイ:


手札を1枚めくる。

表になった手札は、台札に重ねるか、屑札に重ねることができる。台札に重ねるときは、指定された間隔を保たなければならないが、屑札に重ねるときには、どの屑札でも構わない。

屑札の一番上のカードは、台札にいつでも重ねることができる。もちろ、、指定された間隔を保たないといけないが。

手札を台札か屑札の上に移動し終えると、手札をめくることができる。

以上が、可能なカードの動かし方の全てだ。


lab1-3.png

         ※上図の手札は最初(一番上)の5だけが見えていて、それ以降は本当は見えていない。



目的:


この遊びは、以上のルールに従ってカードを動かし、全てのカードを台札に重ねることができたら成功である。

そのとき、どの台札も、一番上はKになる。



例:


次に、「計算」の最初の方のカードの移動を図で示す。ほとんど台札に重ねられる数字が手札から出てこなかったため、延々と屑札の上に積み重ねている。


最初の方だけ、実際にどのようにプレイが進んでいくかを示す。図についての説明は面倒なので省略するが、分かると思う。


lab1-4.png


今回の説明はここまでにしておく。

まず、この一人遊びを実際にプレイしてみて、自分の頭でどのくらいの成功率になるか確認していただきたい。

もし1割以上の成功率ならば、相当優秀である。

モンテカルロ木探索では、戦略は無視なのだが、次回は「計算」の戦略を紹介する。その戦略を使うと、人手でプレイしても一気に成功率が上昇する。

このアーカイブについて

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

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

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

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