ページ 11

続・オセロの評価関数について

Posted: 2011年8月20日(土) 01:51
by 学生A
前スレッド(http://dixq.net/forum/viewtopic.php?f=3&t=8920)が長くなってしまったので、こちらのスレッドに移行します。

softya(ソフト屋)さん、探索経験者さん、返信ありがとうございます。
とりあえず、探索木を表示するのは最後の手段ということにします・・・

>とりあえず全部表示しても見れないので確定した時のネスト毎の評価値を配列にでも保存しておいて、最終確定時に今回の評価値詳細として表示するのはどうでしょうか?
主に表示の仕方が難しそうです。ただデーターを羅列するだけなら簡単なのですが、CUIで目で見て一発で分かるというわけには行かなそうです。

探索経験者さんが教えてくださったソフトも良さそうでしたが、
その書式を調べるので一日がかかってしまいそうなのでw
が、いざとなったらこのソフトを使います。ありがとうございました。

では本題に。
>探索経験者さん
なるほど。now_turnだけでなく、rev_turnの評価値も考慮して、その差を利用する、という形ですね。
確かに、自分にとって一番よい手を選んでも、それによって相手も有利になってしまっては困りますね。。
アドバイスありがとうございます。

それをプログラムに組み込んでみました。具体的には、

コード:

return hyouka(now_turn);

コード:

return hyouka(now_turn)-hyouka(rev_turn);
にしました。
が余り動作が変わらなかったので、なぜかなーと思って3日くらい考えてみました。
で出た結論が、「相対的な評価値にしたことによって、探索するときはCOMの場合でもPLAYERの場合でもmax値を採用しなければならなくなった」
というものです。これって正しいでしょうか?

試しにtansaku関数の

コード:

		
		if(!iscomturn) {
			if(value>max) { 
				max=value;
			}
			if(n==first_n){ 
				hyoukati[putable[i]]=max; 
				printf("hyoukati[%d]=%d(max)\n", putable[i] ,max );
			}
		} else {
			if (value<min) { 
				min=value;
			}
		}
		

コード:

		if(value>max) { /* 石を置いてみた後の手が相手(=Not COM)の場合は子節点の評価値のうち最大の値をvalueに格納 */
			max=value;
		}
		if(n==first_n){ /* 石を置いてみた後の手が相手(=Not COM)の場合で、この関数が始めに呼ばれた場合 */
			hyoukati[putable[i]]=max; /* 評価値配列に書き込み */
			printf("hyoukati[%d]=%d(max)\n", putable[i] ,max );
		}
こうして見たところ、出力された評価値がいい感じにばらけていて、またしっかりと中割りしてきます。
がこれが(探索のアルゴリズムから見て)正しい動作かどうかが分かりません。
アドバイスお願いします。

Re: 続・オセロの評価関数について

Posted: 2011年8月20日(土) 01:52
by 学生A
前スレッドにこのスレッドを告知したため、上げ。

Re: 続・オセロの評価関数について

Posted: 2011年8月20日(土) 01:55
by 学生A
現在のコードを貼りつけ忘れていました。。。
http://www1.axfc.net/uploader/Sc/so/266888.zip&key=otl
です。よろしくお願いします。

Re: 続・オセロの評価関数について

Posted: 2011年8月20日(土) 12:16
by softya(ソフト屋)
前のは、とりあえず解決にしておいてくださいね。
学生A さんが書きました:がこれが(探索のアルゴリズムから見て)正しい動作かどうかが分かりません。
探索のアルゴリズムが正解かどうかは、やはり途中の値を見ないと難しいですね。
思考アルゴリズムって評価が難しいんですよ。

ぱっと見た感じではtansaku()で
return hyouka(now_turn)-hyouka(rev_turn);
で同じ深さで両方の評価値を求めているのは意味が無い気がします。

Re: 続・オセロの評価関数について

Posted: 2011年8月20日(土) 17:25
by 学生A
softya(ソフト屋)さん、返信ありがとうございます。
softya(ソフト屋) さんが書きました:前のは、とりあえず解決にしておいてくださいね。
すみません。解決済みにしました。
softya(ソフト屋) さんが書きました:探索のアルゴリズムが正解かどうかは、やはり途中の値を見ないと難しいですね。
やはりそうですか・・・
これ以上改良を加えても、それが正しいかどうかは途中の値を出力しないと判断できませんよね。

どうすれば実装できるかな・・・っとだらだら考えていたら、スタックを使えば比較的簡単にツリーを表現できることに気が付きました。
具体的には、debug_stackをスタック本体、debug_stをスタック参照用の変数とし、

コード:

debug_stack[debug_st++]=1000*(first_n-n+1)+max
または、n==0の時、

コード:

int temp=hyouka(now_turn)-hyouka(rev_turn);
temp+=100;
debug_stack[debug_st++]=1000*(first_n-n+1)+temp;
と記憶しました。
1000*(first_n-n+1)を足している理由は、その評価値がどのくらいの深さなのかを記憶するためで、
tempに100を足している理由は、評価値がマイナスになるときに、前項の「深さ」が崩れないようにする為です。

出力はcomputer_think関数の最後の方に

コード:

	/* 木をtxtに出力 */
	FILE *fp;
	
	fp = fopen( "debug.txt", "a" );
	if( fp == NULL )
	{
		puts( "debug.txtが開けません" );
		return 1;
	}
	fprintf( fp, "[turn:%d]\n",debug_turn);
	for(i=debug_st;i!=-1;i--) {
		int j=debug_stack[i]/1000; /* 空白を入れる回数 */
		if (j!=0) {
			for(int k=0;k<j-1;k++) {
				fprintf( fp, "    ");
			}
			fprintf( fp, "%d\n",(debug_stack[i]%1000)-100);
		}
	}

	fclose( fp );
と書いてみました。これで、
http://www32.ocn.ne.jp/~yss/ysstree.html
こちらのソフトで閲覧する環境が整いました。

早速適当に実行してdebug.txtを見てみると、どうやらmaxを取るという処理はできているようです。
がCUIに表示されるものと比べてみると、n==first_nの時の評価値が食い違っているようです。これが原因なのかもしれません。
何故食い違っているのかは、現在調査中です。。。アドバイス等ありましたら、ご教授ください。

softya(ソフト屋) さんが書きました: ぱっと見た感じではtansaku()で
return hyouka(now_turn)-hyouka(rev_turn);
で同じ深さで両方の評価値を求めているのは意味が無い気がします。
探索経験者さんがおっしゃっていることを基に考えてみたところ、このような結果になりました。
もしかして、now_turnで評価するときに、もう一山深くrev_turnで調べて、その差を利用せよ、という意味なのでしょうか。
そうだとしたら、結構プログラムが複雑になりそうです・・・

--------------------------------------------------------------------------
現在のソースはこちらです。
http://www1.axfc.net/uploader/Sc/so/267052.zip&key=otl

Re: 続・オセロの評価関数について

Posted: 2011年8月20日(土) 17:30
by 学生A
すみません。現在のソースは
http://www1.axfc.net/uploader/Sc/so/267046&key=otl
こちらでした。

Re: 続・オセロの評価関数について

Posted: 2011年8月21日(日) 00:19
by softya(ソフト屋)
学生A さんが書きました:探索経験者さんがおっしゃっていることを基に考えてみたところ、このような結果になりました。
もしかして、now_turnで評価するときに、もう一山深くrev_turnで調べて、その差を利用せよ、という意味なのでしょうか。
そうだとしたら、結構プログラムが複雑になりそうです・・・
これって探索経験者さんのアイデアだったんですね。
私はオセロを極めたことがないので、探索経験者さんの意見のほうが信ぴょう性が高いと思います。
ただ、探索の一番深いところだけチェックしているようですが探索の途中でもやらないと意味が無いのではないでしょうか?

Re: 続・オセロの評価関数について

Posted: 2011年8月21日(日) 15:10
by 探索経験者
>もしかして、now_turnで評価するときに、もう一山深くrev_turnで調べて、その差を利用せよ、という意味なのでしょうか。

すいません、ちょっと混乱させてしまいました。
そこまでは必要ありません。単純にnow_turn側の評価値からrev_turn側の評価値を引くだけでokです。
ただ、正確に言うとご指摘に通り、「もう一山深くrev_turnで調べて・・」がホントはやりたいことです。なぜなら、rev_turn側は次に一手打てる状態だからです。
もちろん実際はそこまで出来ないのでrev_turn側の評価は「一手打っていない」(あるいは「次に一手打てる」)という前提で評価しなければいけません。従ってnow_turn側の評価を若干過少評価する、あるいはrev_turn側を若干過大評価する、みたいにバランスを取ってやる必要があります。
しかし、今の時点ではそこまでまだ必要無いかと思います。

>で出た結論が、「相対的な評価値にしたことによって、探索するときはCOMの場合でもPLAYERの場合でもmax値を採用しなければならなくなった」

ということは無いです。
評価関数を今一度見ていただければお分かり頂けるかと思いますが、
  評価値=hyouka(now_turn)-hyouka(rev_turn);
となっており、min_max法ではこの評価値がそのまま上に上がっていきます。従って、
now_turn(max局面)側はhyouka(now_turn)が大きく、hyouka(rev_turn)を小さくするのがbest
rev_turn(min局面)側はhyouka(now_turn)が小さく、hyouka(rev_turn)を大きくするのがbest
ですので、min-maxの取り方は今で通りでよいはずです。

現時点で気づいた点をご指摘させていただければ、とりあえずmin-maxに戻しした上で、
max側の時に評価関数が呼ばれるように、読み深さを必ず3あるいは奇数に設定してください。
で、その時の評価関数の方ですが、max側がnow_turnとなるように評価してください。
今のままですとnow_turn側がrev_turnとなって評価関数を呼んでしまいます。
  評価値=hyouka(rev_turn)-hyouka(now_turn);
としてみてください(ちょっとややこしくなってきましたが)。

まずは、読み深さを1に設定してcom側が思った所に打つか、評価値は妥当か確認してください。
その後3に設定して動きを確認してみてください。
多分うまくいくと思うのですが・・

Re: 続・オセロの評価関数について

Posted: 2011年8月21日(日) 18:29
by 探索経験者
では、今度はデバックの方法を考えてみます。
スタックという方法を取られたので、それを元にもうちょっと改良をご提案します。
まず、メモリの観点から省メモリというのは望ましい方向ですが、それにより分かりづらくなるのはデバックの観点からみるとイマイチなので、スタックを構造体にしてみます。

コード:

struct {
	int pos;	// 位置
	int value;	// その場所での評価値
	int dep;	// 評価値を得た深さ
	int max_min;	// その時点での最大値あるいは最低値
} debug_stack[30000]; /* デバッグ用スタック */
コメントに書いた通り評価値の他に、評価値が得られた場所、その時の深さ、その時点での評価の最大値(あるいは最小値)を記録します。
一つの面での候補手が最大でも30として、それを深さ3まで探査するとしたら30×30×30=27,000なので一応容量としては30,000としておきます(メモリを全く使わない方法もありますが、見にくくなるので今はこの方法で)。

コード:

//	for(i=0;i<50000;i++) {
//		debug_stack[i]=0;
//	}
スタックの初期化は不要です。

ファイル書き込み部分は、

コード:

	fprintf_s( fp, "[turn:%d]\n",debug_turn);
	for(i=0;i<debug_st;i++) {
		for(int k=0;k<debug_stack[i].dep;k++) {
			fprintf_s( fp, "    ");
		}
		fprintf_s( fp, "深さ:%d 位置:%d 評価値:%d ",debug_stack[i].dep,debug_stack[i].pos,debug_stack[i].value);
		if(debug_stack[i].dep%2==0) fprintf_s( fp, "Min:%d\n",debug_stack[i].max_min);
		else fprintf_s( fp, "Max:%d\n",debug_stack[i].max_min);
	}
の様に、構造体の情報をわかりやすく書き込みます。深さが偶数の時は必ずMin局面なのでdebug_stack.max_minの値はMinとして表示、それ以外はMax局面です。 (ファイルに関する関数はVC++2010対応でfprintf_s等_sの付いた関数を使ってます。)

今度はtansaku()の中で、まず最深部で評価関数を呼ぶ部分は、小細工は不要なのでそのまま返すようにします。
また、この面でのスタック場所を記憶するための変数stackを宣言しておきます。

コード:

	int stack;

	if (n == 0) { /* 残りの探索の深さが0だったらその盤面の評価値を返す */
		int temp=hyouka(rev_turn)-hyouka(now_turn);
//		temp+=100; /* 評価値がマイナスにならないようにする */
//		debug_stack[debug_st++]=1000*(first_n-n+1)+temp;

		return temp;
	}

得られた候補手をそれぞれ探査する部分ですが、//でコメントした部分が変更部分です。
ちょっと分かりづらいかも知れませんが、stackという変数にその局面で記憶すべき場所を深く探査する前に記憶しておきます。
で、再帰から戻って来た時にその場所に評価値などを記録する方法です。

コード:

	for(i=0;i<k;i++) { /* 全ての手に対して */

		flip(&com_ban[0],now_turn,putable[i],TRUE); /* 石を置いてみる(com_banが更新される) */

		stack=debug_st;		// この面での書き込む位置を記憶しておく
		++debug_st;		// 次のスタック値へ

		value = tansaku(n-1,first_n,rev_turn); /* 置いた盤面で、この関数を呼ぶ(再帰)first_nはそのまま渡す */
		
		if(n==first_n){ /* 石を置いてみた後の手が相手(=Not COM)の場合で、この関数が始めに呼ばれた場合 */
			hyoukati[putable[i]]=max; /* 評価値配列に書き込み */
			printf("hyoukati[%d]=%d(max)\n", putable[i] ,(max-100) );
		}

		
		if(!iscomturn) {
			if(value>max) { 
				max=value;
			}
			if(n==first_n){ 
				hyoukati[putable[i]]=max; 
				printf("hyoukati[%d]=%d(max)\n", putable[i] ,max );
			}
			debug_stack[stack].max_min=max;			// 現時点でのMax値をスタックに記録
		} else {
			if (value<min) { 
				min=value;
			}
			debug_stack[stack].max_min=min;			// 現時点でのMin値をスタックに記録
		}
		
		debug_stack[stack].dep=first_n-n+1;	// 深さを記録
		debug_stack[stack].pos=putable[i];	// 位置を記録
		debug_stack[stack].value=value;		// 評価値を記録
		++stack;

		undo(); /* 次の手を調べるために、置いてみた手をもとに戻す */
	}

	/* 今の手が相手(=Not COM)の場合はmaxを返す */
//	debug_stack[debug_st++]=1000*(first_n-n+1)+max;
	return !iscomturn ? max : min;
//	return max;
最後のスタックに関する部分も削除して、returnもmaxあるいはminを返します。
これでYssTreeで見てください。分かり易くなり、デバックもしやすくなるかと思われます。
長文失礼しました。

Re: 続・オセロの評価関数について

Posted: 2011年8月21日(日) 21:19
by 学生A
お二人方、毎回返信ありがとうございます。
softya(ソフト屋) さんが書きました: ただ、探索の一番深いところだけチェックしているようですが探索の途中でもやらないと意味が無いのではないでしょうか?
盤面の評価は探索の最深部の一回だけで、それ以降はMini-Max法で選んでいく、という方針なので、
最深部だけ評価をすれば大丈夫だと思っています。間違っていたらすみません。


探索経験者さん、詳細なご返信ありがとうございます。
とてもわかりやすくて嬉しいのですが、まだ理解しきれていない部分があるので、質問よろしいでしょうか
探索経験者 さんが書きました: 評価関数を今一度見ていただければお分かり頂けるかと思いますが、
  評価値=hyouka(now_turn)-hyouka(rev_turn);
となっており、min_max法ではこの評価値がそのまま上に上がっていきます。従って、
now_turn(max局面)側はhyouka(now_turn)が大きく、hyouka(rev_turn)を小さくするのがbest
rev_turn(min局面)側はhyouka(now_turn)が小さく、hyouka(rev_turn)を大きくするのがbest
ですので、min-maxの取り方は今で通りでよいはずです。
の、now_turn(max局面)についてなのですが、
まず、now_turnはtansaku関数のローカル変数で、
tansaku関数が呼ばれるたびに3-now_turn、つまりrev_turnに変わりますよね。
そうすると、now_turnは必ずしもmax局面にならない、と思うのですが・・・
どうしてそのようになるのでしょうか?

http://hp.vector.co.jp/authors/VA015468 ... o/2_2.html
ここにある通り、COMの局面ではmaxを、PLAYERの局面ではminを選ぶのが、Mini-Max法だと思っています。
なので、max局面はnow_turnでなく、com_turn(固定)である必要があると思います。
今回の場合だと、maxはhyouka(com_turn)-hyouka(3-com_turn)の最大、minはhyouka(com_turn)-hyouka(3-com_turn)の最小を選ぶのが正しいような気がしてきました。

もしかしたら、自分が何か重大な勘違いしている可能性があるので、恥ずかしいのですが、質問させて頂きました。
ご指摘してくださった部分を改良しながら、ご返信をお待ちしております。

Re: 続・オセロの評価関数について

Posted: 2011年8月21日(日) 23:01
by 探索経験者
すいません、ご指摘されて書き方が悪い事に気づきました。
now_turn(max局面)側は・・のnow_turnは最終局面でのnow_turn側、
rev_turn(min局面)側は・・のrev_turnは最終局面でのrev_turn側の事です。分かりにくくてすいません。
学生A さんが書きました:なので、max局面はnow_turnでなく、com_turn(固定)である必要があると思います。
結果的にその通りで、深さ1でcomが打ち(max局面),深さ2でman(min局面),深さ3でcom(max局面)・・となりますので、max局面は常にcom_turn側となります(更にmax局面は常に奇数深さ)。
従って、
学生A さんが書きました:今回の場合だと、maxはhyouka(com_turn)-hyouka(3-com_turn)の最大、minはhyouka(com_turn)-hyouka(3-com_turn)の最小を選ぶのが正しいような気がしてきました。
という認識は正しいです。
now_turnという考えにこだわっているのは今後の拡張性とかを考慮してです。例えば評価関数の
  評価値=hyouka(now_turn)-hyouka(rev_turn);
としておけば、探索深さが奇数であっても偶数であっても実はうまくいきます。
しかし、これを
  評価値=hyouka(com_turn)-hyouka(3-com_turn);
と固定してしまうと奇数深さでしか通用しない評価関数になってしまいます。
それはそれで良いというのでしたら、もちろんそれでもいいのですが。
いずれにしろ、max側はcom側、min側はman側という認識でいれば、考えやすいと思います。

Re: 続・オセロの評価関数について

Posted: 2011年8月22日(月) 00:29
by 学生A
>探索経験者さん
なるほど、最深部でのnow_turnということだったのですね。
納得しました。
探索経験者 さんが書きました:   評価値=hyouka(now_turn)-hyouka(rev_turn);
としておけば、探索深さが奇数であっても偶数であっても実はうまくいきます。
しかし、これを
  評価値=hyouka(com_turn)-hyouka(3-com_turn);
と固定してしまうと奇数深さでしか通用しない評価関数になってしまいます。
それは困りますね。
hyouka(now_turn)-hyouka(rev_turn);を使うことにします。
探索経験者 さんが書きました: 今のままですとnow_turn側がrev_turnとなって評価関数を呼んでしまいます。
  評価値=hyouka(rev_turn)-hyouka(now_turn);
としてみてください(ちょっとややこしくなってきましたが)。
これは、
n==1のとき、最初にtansaku(1,1,com_turn);が呼ばれるが、これで終わりでなく、
tansaku(0,1,rev_turn);が呼ばれてから、評価関数を呼ぶので、rev_turnがnow_turnとなり、
逆にしなければならなくなった。(n=奇数の時も同様)
という認識でよろしいでしょうか。

ありがとうございます。段々探索が分かってきました!

Re: 続・オセロの評価関数について

Posted: 2011年8月22日(月) 21:26
by 探索経験者
学生A さんが書きました: n==1のとき、最初にtansaku(1,1,com_turn);が呼ばれるが、これで終わりでなく、
tansaku(0,1,rev_turn);が呼ばれてから、評価関数を呼ぶので、rev_turnがnow_turnとなり、
逆にしなければならなくなった。(n=奇数の時も同様)
という認識でよろしいでしょうか。
その通りです。ただ、nが偶数、奇数関係なく逆にする必要があります(とにかくその面のそのturn側に立った評価値を返す)。
段々とご理解いただいた様でなによりです。

Re: 続・オセロの評価関数について

Posted: 2011年8月23日(火) 21:11
by 学生A
探索経験者 さんが書きました: その通りです。ただ、nが偶数、奇数関係なく逆にする必要があります(とにかくその面のそのturn側に立った評価値を返す)。
ありがとうございます。確かに、n=偶数の時も
tansaku(2,2,com_turn);→tansaku(1,2,3-com_turn);→tansaku(0,2,com_turn)となるので、3-com_turn、つまりman側に立って評価するために、逆にする必要がありますね。理解しました!

また、探索経験者さんのおっしゃられた様に、プログラムを書き換えてみました。
すると、デバッグの出力も見やすくなり、また処理自体もおそらく正常なものになりました。
ありがとうございます。

その時に2つほど疑問が生じたのですが、

①デバッグ用のスタックに書きこむ部分の、

コード:

        debug_stack[stack].dep=first_n-n+1; // 深さを記録
        debug_stack[stack].pos=putable[i];  // 位置を記録
        debug_stack[stack].value=value;     // 評価値を記録
        ++stack;
の、++stackは何のためにあるのでしょうか。無くても変わらない気がします

②デバッグ用スタックをファイルに書きこむ部分は

コード:

        for(i=0;i<debug_st;i++) {
                (略)
        }
このようになっていますが、なぜ0からdebug_stまでの増分ループなのでしょうか
スタックに最初(0番)に書き込まれるのは、探索の最深部で、順々に記録していき、debug_stには
最浅部の情報が書き込まれるので、debug_stから0までの減分ループでないと正常に出力できない気がします
(が、出力されたものを見ると、この順番で正しいようです。)

以上2点の返信をお待ちしております

ーーーーーーーーーーーーーーーーーーーーーー
現在のソースは
http://www1.axfc.net/uploader/Sc/so/268052.zip&key=otl
です。

Re: 続・オセロの評価関数について

Posted: 2011年8月23日(火) 23:40
by 探索経験者
まず、Ytree用のtxtファイルの大まかな仕様を確認しますと、中身は
深さ1-手A
[tab=30]深さ2-手B
[tab=60]深さ3-手C
[tab=60]深さ3-手D
[tab=60]深さ3-手E
[tab=30]深さ2-手F
[tab=60]深さ3-手G
深さ1-手H
   :

みたいに作る必要があるはずです。
そのために debug_stackの[0]に 深さ1-手A を、[1]に 深さ2-手B を・・と順に記録し、それらの記録が終了した時点で最後に上から吐き出せばokみたいにしてあります(すいません、逆に逆順という発想は無かったです)。
で、 ++stack なのですが・・すいません、要らないですねこれ。失礼しました。
stackにその面に来た時のdebug_stの値を記録して、再帰から戻って来た時に覚えていたその値を使ってdebug_stack[]に記録するという方法です。要するに再帰に入る前に場所を確保しておいて、再帰から戻って来た時にその場所に得られた情報等を記録するというものです。

さて、Min-Max法も大体ご理解頂きデバック環境も整った所で、忘れないうちに今後の課題として気づいた点を申し上げておきます。

1.現在は探索中に石を置けないとなった場合はそこで評価値を得て終わりとしていますが、オセロでは石を置けない状況は2パターンあると思います。空いている場所が無くて置けないパターンと置きたいけど反転できる石が無いために置けないパターンです。
後者の場合は「パス」して相手にターンを渡す事となりますので、update_putable(&putable[0],now_turn)で「置けない」という状態を2つ作る必要があるかと思います。

2.「勝ち」という状態についてですが、オセロでは1石差でも勝ちは勝ちですし、圧倒的な差を付けても勝ちです。現在のプログラムではできるだけ石の多い方(点数が多い方)が良いとしていると思いますので、後者の方式です。
もし、前者の方式をとるのであれば、「勝ち」という概念(要は値なのですが)を入れる必要がありすます。前者の方式の良いところは探索が早く終わるということです。「勝ち」を見つければそれ以上の評価値は無いので以降の探索の必要が無くなります。従って探索の途中で打ち切る事が出来て早く終わります(勝ちを見つけるような終局に近い場面で)。どちらの方式にするかはもちろん製作者の判断です。

以上、既にご自身もご承知とも思いますが、私が見ていて気付いた点でした。
是非がんばって強いオセロゲームを作って下さい。

Re: 続・オセロの評価関数について

Posted: 2011年8月24日(水) 10:33
by 学生A
>探索経験者さん
探索経験者 さんが書きました: stackにその面に来た時のdebug_stの値を記録して、再帰から戻って来た時に覚えていたその値を使ってdebug_stack[]に記録するという方法です。要するに再帰に入る前に場所を確保しておいて、再帰から戻って来た時にその場所に得られた情報等を記録するというものです。
なるほど。stackはローカル変数で、グローバル変数であるdebug_stを増やしながらstackを確保することで、順番に記録していったということですね。

また、debug.txtの出力と、プログラム画面での出力が異なるバグですが、

コード:

	if(n==first_n){ /* 石を置いてみた後の手が相手(=Not COM)の場合で、この関数が始めに呼ばれた場合 */
		hyoukati[putable[i]]=max; /* 評価値配列に書き込み */
		printf("hyoukati[%d]=%d(max)\n", putable[i] ,max ); 
	}
となっていたところを、

コード:

	if(n==first_n){ /* 石を置いてみた後の手が相手(=Not COM)の場合で、この関数が始めに呼ばれた場合 */
		hyoukati[putable[i]]=value; /* 評価値配列に書き込み */
		printf("hyoukati[%d]=%d(min)\n", putable[i] ,value ); 
	}
と修正することで、debug.txtと一致するようになりました。
debug.txtのmin_max値を見ていたら、それとプログラムの表示が一致していたので、このことに気が付きました。ありがとうございます。

当初の問題であった「評価値が正しくない疑惑」が晴れたので、このスレッド及び前スレッドは解決にしたいと思います。が、探索経験者さんが課題を出されたので、それを引き続きこのスレッドで議論しようと思います。
softya(ソフト屋)さん、探索経験者さん、ありがとうございました。

1.について
そうですね。パスのことはまだあまり考えていませんでした。
k==0のときの処理を変えて、

コード:

	if (k==0) { /* 置ける場所がないとき */
		if (update_putable(&putable[0],rev_turn)) { /* 逆の手が置けるかどうかを調べる */
			return tansaku(n-1,first_n,rev_turn); /* 置ける場合は、rev_turnにして探索続行 */
		} else {
			/* もう置けない場合(終局) */
			int black=0,white=0,value;
			count_ban(&com_ban[0],&black,&white); /* 黒の数、白の数を調べてblack,whiteに代入 */
			if (com_turn==BLACK) { /* COMが黒だったら黒-白、白だったら白-黒をvalueとする */
				value=black-white;
			} else {
				value=white-black;
			}
			if (now_turn == 3-com_turn) { /* min盤面の場合、評価値をマイナスにする */
				value=-value;
			}
			return 100*value; /* 強制的に採用させる */
		}
	}
としてみました。が、終局場面を強制的に採用させるのは、必ずしも良い選択肢とは言えないため(他にもっと石差がある終局盤面がある可能性がある)、そこの実装をどうしようか悩んでおります。
また、この変更を加えたプログラムを最後まで実行してみたところ、このルーチンの評価値だと思われる値が全く出力されませんでした。
以上の二点が現在の問題です。

2.について
ご指摘ありがとうございます。
しかし、今回は後者のできるだけ石差をつけて勝つという方針をとらせて頂きます。
ご了承ください。

ーーーーーーーーーーーーーーーーーーーーーーー
現在のソースファイルは
http://www1.axfc.net/uploader/Sc/so/268211.zip&key=otl
です。

Re: 続・オセロの評価関数について

Posted: 2011年8月27日(土) 02:13
by 学生A
こんばんは。

前投稿から、改良を重ね、とりあえず形にはなりました。
http://dixq.net/forum/viewtopic.php?f=78&t=9154
ここからダウンロードできますので、よかったらプレイしてみてください

なお、
学生A さんが書きました: 終局場面を強制的に採用させるのは、必ずしも良い選択肢とは言えないため(他にもっと石差がある終局盤面がある可能性がある)、そこの実装をどうしようか悩んでおります。
この問題については、終盤残り8手くらいになったら、終局まですべて読むことにして解決しました。終盤は評価値が正確(石差を評価値にすれば良い)ので、コンピューターが強くなりがちですね。


遅レスなのですが・・・
探索経験者 さんが書きました: 是非がんばって強いオセロゲームを作って下さい。
はい、頑張ります!