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

[学生A]

こんばんは、また学生Aです。
今回は、オセロの評価関数について質問したいと思います。

先程の探索関数を使って、盤面を評価してみました。
評価のルールは
①その盤面でそのターンの色の石が置ける場所の数・・・value1（大きければ評価高）
②その盤面になるために置いた石、によってひっくり返された石の周りの空白の数の合計・・・value2（小さければ評価高）
③確定石の数（近似値：四端のマスに石が置いてあったら、そのマスから縦横に何個石が続いているか）・・・value3（大きければ評価高）

とし、

コード:

l*value1 + m*value2 +n*value2

で決定するとします。（l,n>0 , m<0）

valueごとの効果を確認したいため、一旦一つのvalueだけ有効にしてみたりしました。
しかし、例えばvalue2だけを有効にした場合、COMはできるだけひっくり返す石の周りに空白が出来ないように打って欲しいのですが、
まったく関係の無いところに打ってしまいます。それもそのはず、debug関数で最終的なhyoukatiを出力してみると、ほぼ全てのマスが同じ評価値なのです。
（頭で計算すると、違う値になるはずなのですが・・・）
なぜこのような値になってしまうのでしょうか。

------------------------------------------------------------------------
ソースはこちらです↓
http://www1.axfc.net/uploader/Sc/so/256515.zip&key=otl

[softya（ソフト屋)]

こちらの続きですね？
http://dixq.net/forum/viewtopic.php?f=3&t=8910

申し訳ないですが、tansaku（）で行われていることが良く分かりません。
あとprintfしてみましたが、value1とvalue2は異常値らしきものは見当たりません。
なので、tansaku（）の解説、コメントの付与、あと分かりにくい一文字変数をやめて意味のある名前をつけて頂けますでしょうか。

[学生A]

softya(ソフト屋)さん、毎回返信ありがとうございます。

＞こちらの続きですね？
＞viewtopic.php?f=3&t=8910
はい。そちらの続きになります。

＞申し訳ないですが、tansaku（）で行われていることが良く分かりません。
＞あとprintfしてみましたが、value1とvalue2は異常値らしきものは見当たりません。
＞なので、tansaku（）の解説、コメントの付与、あと分かりにくい一文字変数をやめて意味のある名前をつけて頂けますでしょうか。
申し訳ありません。tansaku関数とhyouka関数の説明をほぼ一対一で書きました。変数名も若干変えました。
関数の解説は、computer.hを参照してください。
コードは以下になります。（tansaku関数の第二引数の名前が変わっているので、computer.hの方も変えて使用してください。）

コード:

/* 探索関数（深さ優先探索）n手探索する。 */
int tansaku(int n,int first_n) {
	int min=1000,max=-1000,i; 
	int value; /* 評価値（石を置いてみた後の手が相手（＝Not COM）の場合子節点の評価値のうち最大の値、COMの場合、子節点の評価値のうち最小の値を入れる） */
	bool iscomturn; /* 石を置いてみた後、COMのターンである場合はTRUE、そうでない場合はFALSE */

	if (n == 0) { /* 残りの探索の深さが0だったらその盤面の評価値を返す */
		return hyouka();
	}

	int putable[60]; /* 今の盤面で置けるマスのインデックスを格納する配列 */
	int k=update_putable(&putable[0]); /* 置けるマスのインデックス格納＆その個数取得 */
	if (k==0) {return hyouka();} /* もう置けない場合は、n=0の時と同じ処理 */
	for(i=0;i<k;i++) { /* 全ての手に対して */
		flip(&com_ban[0],com_now_turn,putable[i],TRUE); /* 石を置いてみる（com_banが更新される） */
		com_now_turn=3-com_now_turn; /* 置いたので、ターン変更 */
		value = tansaku(n-1,first_n); /* 置いた盤面で、この関数を呼ぶ(再帰)first_nはそのまま渡す */
		iscomturn=com_now_turn==com_turn; /* これからよく使うので、置いてみた後のターンがCOMであるかを調べて格納 */
		if (!iscomturn && value>max) { /* 石を置いてみた後の手が相手（＝Not COM）の場合は子節点の評価値のうち最大の値をvalueに格納 */
			max=value;
		}
		if (!iscomturn && n==first_n){ /* 石を置いてみた後の手が相手（＝Not COM）の場合で、この関数が始めに呼ばれた場合 */
			hyoukati[putable[i]]=max; /* 評価値配列に書き込み */
		}
		if (iscomturn && value<min) { /* 石を置いてみた後の手がCOMの場合は子節点の評価値のうち最小の値をvalueに格納 */
			min=value;
		}
		if (iscomturn && n==first_n) { /* 石を置いてみた後の手がCOMの場合で、この関数が始めに呼ばれた場合 */
			hyoukati[putable[i]]=min; /* 評価値配列に書き込み */
		}
		undo(); /* 次の手を調べるために、置いてみた手をもとに戻す */
		com_now_turn=3-com_now_turn; /* undoしたので、ターン変更 */
	}
	if (!iscomturn) { /* 石を置いてみた後の手が相手（＝Not COM）の場合はmaxを返す */
		return max;
	}
	if (iscomturn) { /* 石を置いてみた後の手が自分の場合はminを返す */
		return min;
	}
	return 0; /* ダミー */
}

/* 評価関数（メイン）com_banを評価する。*/
int hyouka() {
	int value1=0,value2=0,value3=0; /* それぞれ、自分の着手可能手数（自分が石を置けるマスの数がいくつあるか）、
									開放度（ひっくり返した石の周りの空白の数）、確定石の数（もう絶対にひっくり返らない石の数）の近似値 */
	int i,j;
	
	/* この盤面での置ける場所を調べる */
	int putable[60];
	value1=update_putable(&putable[0]); /* value1に、この盤面でcom_now_turnが置ける場所の総数を代入 */

	/* 直前に置いた石でひっくり返る石の周りの空白マスを調べる */
	/* まず、この盤面になる前にひっくり返った石のインデックスをスタックから参照する（取り出さない！） */
	int n,m,s=sp; /* n=ひっくり返った石の数 m=一手前に置いた石のマスのインデックス s=スタックの添字（ローカル変数） */
	n=stack[--s]; /* ひっくり返った石の数を格納 */
	m=stack[--s]; /* 一手前に置いた石の場所を求める */
	while(n-->0) { /* ひっくり返した石の数だけループ */
		value2+=blank_around(stack[--s]%100); /* その石のインデックスを求め、blank_around関数に渡し、周りの空白の数を調べて合計する */
	}
	value2=-value2; /* 少なければ少ないほど良い。 */

	
	/* 確定石を求める(近似値/四端から何個石が続いているか) */
	int start[4]={11,18,81,88};
	int dir[4]={-1,-10,1,10};
	for(i=0;i<4;i++) { /* 四つの端のマスについて */
		if (com_ban[start[i]] == com_now_turn) { /* そのマスに自分の石があれば */
			for(j=0;j<4;j++) { /* 上下左右の四つの方向に対して */
				while(com_ban[start[i]+dir[j]] == com_now_turn) { /* 調べるマスに自分の石があれば */
					start[i]+=dir[j]; /* start[i]をdir[j]だけずらして */
					value3++; /* value3を一つ増やす */
				}
			}
		}
	}

	//return value1*3+value2*2+value3;
	return value2;
}

tansaku関数内のundoの位置がオリジナルと変わっていますが、よく考えたらこちらの配置のほうが正しいと思い、訂正させていただきました。
すると、多少挙動が変わったものの、期待する動作ではありませんでした。期待する動作を具体的に書くと
①黒(4,3)に置く
②白(3,3)に置く
③黒(3,4)に置く
④白(3,5)に置く
⑤黒(5,6)に置く
⑥白(5,3)に置く
です。最後の⑥が中割りと呼ばれる手で、これはオセロでは強力な手らしいです。しかし、COMが中割りをしてくれません（涙）
お願いします。

------------------------------------------------------------
com_ban配列やstackの仕様は以下の画像をご覧ください。

[box]

コード:

	if (!iscomturn) { /* 石を置いてみた後の手が相手（＝Not COM）の場合はmaxを返す */
		return max;
	}
	if (iscomturn) { /* 石を置いてみた後の手が自分の場合はminを返す */
		return min;
	}
	return 0; /* ダミー */

まあ本題とは全く関係ない些末な話ですが、当方としてはダミー値なんて使わずに
（コンパイラーによっては return 0; を通らないっていう警告が出るはず）

コード:

    return iscomturn ? min : max;

なんて書くのが好きです。

[softya（ソフト屋)]

すいません明日またコメントします。

[softya（ソフト屋)]

とりあえず、アルゴリズムをちゃんと理解してませんが何か評価値を代入している部分が少ない気はします。
こちらでも外部公開変数やら関数が曖昧なので、ごちゃごちゃしていて分かりづらいので整理して考えてみますが、そちらでもmin,maxの代入条件とかprintfを駆使して追いかけてみてください。調べられるのは夜になります。

[softya（ソフト屋)]

モジュール構造的には色々問題を感じるのですが手直ししてみました。
外部公開不要なものはファイル内参照に切り替えてあります。

コード:

/* computer.h */
extern int stack[1000]; /* 盤をもとに戻す用 */
extern int sp; /* stackの操作する位置を記憶する用変数 */

コード:

/* computer.cpp */

#include <stdio.h>
#include "Gloval.h"
#include "computer.h"

int stack[1000]; /* 盤をもとに戻す用 */
int sp; /* stackの操作する位置を記憶する用変数 */

static int com_turn; /* コンピューターのターン */
//static int now_turn; /* 今のターン（コンピューター用） */
/* グローバル変数宣言 */
static int com_ban[100]; /* コンピューター用の盤 */
static int hyoukati[100]; /* 最終的な評価値 */

/* 関数プロトタイプ宣言 */

static void init_hyoukati(); /* 評価値を初期化 */
static void debug(char *s);/* デバッグ用関数(評価値出力) */
static void undo(); /* 盤面をもとに戻す */

static int update_putable(int *p,int turn); /* 置けるマスを調べてputableに代入 */
static void computer_think_main(int n,int turn);/* コンピューターの思考 */
static int tansaku(int n,int p,int turn);/* 探索関数（深さ優先探索）n手探索する。 */
static int hyouka(int now_turn);/* 評価関数（メイン）com_banを評価する。*/
static int blank_around(int m);/* 指定したマスの周りの空きマスの数を返す */

/* 評価値を初期化 */
static void init_hyoukati(){
	int i;

	for(i=0;i<100;i++) {
		hyoukati[i]=-1000;
	}
}

/*
置けるマスを調べてputableに代入(返り値＝置けるマスの数)
int *p…int putable[60]へのポインタ
int now_turn 置く石
*/
static int update_putable(int *p,int now_turn){
	int i,k=0;

	for(i=0;i<60;i++) {
		*(p+i)=-1;
	}

	for(i=0;i<100;i++) {
		if (flip(&com_ban[0],now_turn,i,FALSE) != 0) {
			*(p+k++)=i;
		}
	}
	return k;
}

/* デバッグ用関数（評価値出力） */
static void debug(char *s){
	int i;
	static int k=0;
	k++;
	printf("[%d]:%s",k,s);
	for(i=0;i<100;i++) {
		if (i%10==0) {printf("\n");}
		printf("%d,",hyoukati[i]);
	}
	printf("\n");
}

/* 盤面の状態を一つ前に戻す関数 */
static void undo(){
	int n;
	n=stack[--sp];
	com_ban[(stack[--sp])%100]=BLANK; /* 一手前に置いたマスを空白に */

	/* n個ひっくり返した分を相手の色にする */
	while(n-->0) {
		sp--;
		com_ban[stack[sp]%100]=stack[sp]/100;
	}
}

/*	外部公開関数
コンピューターの思考のメイン。hyoukatiに最終的な評価値を代入
int n…探索する深さ
*/
int computer_think(int *b,int ct,int n) {
	int i,j,ret,com_ban_first[100],max=-100;

	/* 引数の情報をコンピューター用変数に格納 */
	for(i=0;i<10;i++) {
		for(j=0;j<10;j++) {
			com_ban[i*10+j]=*(b+i*10+j);
			com_ban_first[i*10+j]=*(b+i*10+j);
		}
	}
	com_turn=ct;

	/* コンピューター関連の変数を初期化 */
	//now_turn=ct;
	sp=0;
	for(i=0;i<1000;i++) {
		stack[i]=-1;
	}

	/* 評価値決定 */
	computer_think_main(n,ct);
	debug("a");

	for(i=0;i<100;i++) {
		if (hyoukati[i]>max && flip(&com_ban_first[0],ct,i,FALSE)!=0) {
			ret=i;
			max=hyoukati[i];
		}
	}

	return ret;
}

/* コンピューターの思考のメイン */
/* now_turn ＣＰＵのコマ	 */
static void computer_think_main(int n,int now_turn) {
	init_hyoukati();
	tansaku(n,n,now_turn);
}

/*
探索関数。深さ優先探索。
n=0の時、評価関数を呼んで値を返す。
n>0の時、置ける場所を調べてそれぞれについてこの関数を呼び、それぞれについて評価値を返す
int n…残りの探索の深さ
int p…探索を呼び出し始めのn
返り値：評価値(int)
*/

static int tansaku(int n,int first_n,int now_turn) {
    int min=1000,max=-1000,i; 
    int value; /* 評価値（石を置いてみた後の手が相手（＝Not COM）の場合子節点の評価値のうち最大の値、COMの場合、子節点の評価値のうち最小の値を入れる） */
	int rev_turn = 3-now_turn;	//逆側の手。
    bool iscomturn = (rev_turn==com_turn); /* 逆側の手がCOMターンか？ 石を置いてみた後、COMのターンである場合はTRUE、そうでない場合はFALSE */
 
    if (n == 0) { /* 残りの探索の深さが0だったらその盤面の評価値を返す */
        return hyouka(now_turn);
    }
 
    int putable[60]; /* 今の盤面で置けるマスのインデックスを格納する配列 */
    int k=update_putable(&putable[0],now_turn); /* 置けるマスのインデックス格納＆その個数取得 */
//    printf( "置ける場所の数=%d 深さ=%d\n", k ,n );
    if (k==0) {return hyouka(now_turn);} /* もう置けない場合は、n=0の時と同じ処理 */
        
    for(i=0;i<k;i++) { /* 全ての手に対して */
        flip(&com_ban[0],now_turn,putable[i],TRUE); /* 石を置いてみる（com_banが更新される） */
        
        value = tansaku(n-1,first_n,rev_turn); /* 置いた盤面で、この関数を呼ぶ(再帰)first_nはそのまま渡す */
        
        if( !iscomturn ) {
			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 );
        	}
        } else {
			if (value<min) { /* 石を置いてみた後の手がCOMの場合は子節点の評価値のうち最小の値をvalueに格納 */
	            min=value;
    	    }
    	    if (n==first_n) { /* 石を置いてみた後の手がCOMの場合で、この関数が始めに呼ばれた場合 */	//この条件を満たす可能性はあるのか？
        	    hyoukati[putable[i]]=min; /* 評価値配列に書き込み */
			    printf( "hyoukati[%d]=%d(min)\n", putable[i] ,min );
			}
        }
        undo(); /* 次の手を調べるために、置いてみた手をもとに戻す */
    }
    if (!iscomturn) { /* 石を置いてみた後の手が相手（＝Not COM）の場合はmaxを返す */
        return max;
    } else {
        return min;
    }
}
 

/*
評価関数（メイン）com_banを評価する。
返り値：盤面(com_ban)の評価値（高ければCOMに有利、低ければCOMに不利）(int)
*/
static int hyouka(int now_turn) {
    int value1=0,value2=0,value3=0; /* それぞれ、自分の着手可能手数（自分が石を置けるマスの数がいくつあるか）、
                                    開放度（ひっくり返した石の周りの空白の数）、確定石の数（もう絶対にひっくり返らない石の数）の近似値 */
    int i,j;
    
    /* この盤面での置ける場所を調べる */
    int putable[60];
    value1=update_putable(&putable[0],now_turn); /* value1に、この盤面でnow_turnが置ける場所の総数を代入 */
 
    /* 直前に置いた石でひっくり返る石の周りの空白マスを調べる */
    /* まず、この盤面になる前にひっくり返った石のインデックスをスタックから参照する（取り出さない！） */
    int n,m,s=sp; /* n=ひっくり返った石の数 m=一手前に置いた石のマスのインデックス s=スタックの添字（ローカル変数） */
    n=stack[--s]; /* ひっくり返った石の数を格納 */
    m=stack[--s]; /* 一手前に置いた石の場所を求める */
    while(n-->0) { /* ひっくり返した石の数だけループ */
        value2+=blank_around(stack[--s]%100); /* その石のインデックスを求め、blank_around関数に渡し、周りの空白の数を調べて合計する */
    }
    value2=-value2; /* 少なければ少ないほど良い。 */
 
    
    /* 確定石を求める(近似値/四端から何個石が続いているか) */
    int start[4]={11,18,81,88};
    int dir[4]={-1,-10,1,10};
    for(i=0;i<4;i++) { /* 四つの端のマスについて */
        if (com_ban[start[i]] == now_turn) { /* そのマスに自分の石があれば */
            for(j=0;j<4;j++) { /* 上下左右の四つの方向に対して */
                while(com_ban[start[i]+dir[j]] == now_turn) { /* 調べるマスに自分の石があれば */
                    start[i]+=dir[j]; /* start[i]をdir[j]だけずらして */
                    value3++; /* value3を一つ増やす */
                }
            }
        }
    }
 
    //return value1*3+value2*2+value3;
//	printf( "value2=%d\n", value2 );
	return value2;
}

/*
指定したマスの周りの空きマスの数
int m…指定するマスのインデックス
返り値：指定したマスの周りの空きマスの数
*/
static int blank_around(int m) {
	int n=0;
	if (com_ban[m-11] == BLANK) {n++;}
	if (com_ban[m-10] == BLANK) {n++;}
	if (com_ban[m-9] == BLANK) {n++;}
	if (com_ban[m-1] == BLANK) {n++;}
	if (com_ban[m+1] == BLANK) {n++;}
	if (com_ban[m+9] == BLANK) {n++;}
	if (com_ban[m+10] == BLANK) {n++;}
	if (com_ban[m+11] == BLANK) {n++;}
	return n;
}

ポイントとしてはcom_now_turnをグローバル変数から引数に変えた事です。
あとtansakuのプログラム構造がシンプルになるように組み替えました。
その過程で生じた疑問ですが、if( iscomturn && (n==first_n) ) {ってありるのでしょうか？　絶対通らない気がするのですか？

それと⑥白(5,3)に置くの問題ですが、評価値が

1 2 3 4 5 6 7 8
1××××××××
2××××××××
3××○○○×××
4××●●○×××
5×××●●●××
6××××××××
7××××××××
8××××××××
　　　●5-4○　　　
hyoukati[42]=-8(max)
hyoukati[52]=-8(max)
hyoukati[53]=-8(max)
hyoukati[63]=-7(max)
hyoukati[64]=-7(max)
hyoukati[65]=-7(max)
hyoukati[66]=-7(max)
hyoukati[67]=-7(max)

と-７で同じ値が並ぶので、最初の6 3になるのでは？
ここを追うのはご本人にお任せします。

[学生A]

返信遅くなり申し訳ありません。
＞boxさん
ありがとうございます。スマートに書くことができました！

＞softya（ソフト屋）さん
まだ、解決してないのですが、現状報告をします。
まず、評価関数自体の認識が間違っていました。
探索した結果を決定するのに、Mini-max法を使用しているのですが、
これはいずれの盤面（ターン）に於いても「COMから見た」評価値を使用しなければなりませんでした。

そこで、とりあえず、value1を求める際、update_putable関数に渡す第二引数をnow_turnからcom_turn（固定）に変えました。
しかし、そこからが問題で、value2を求める際、常にCOMから見た評価値にするにはどのようにすればいいのでしょうか。
とりあえず、hyouka関数のvalue2を決定するところを
[code]
if (now_turn == 3-com_turn) {value2=-value2;} /* 自分（COM）のターンならば少なければ少ないほど良い。 */
[/code]
とやってみましたが、あっているかどうかはかなり怪しいです。実際、思い通りには動作していません。
ここで、hyouka関数の返り値をvalue2からvalue1にすると、中割りっぽいことはしてくるようになりました。（角を一切考慮しないので弱いですが。。。）
value1とvalue2はよく考えたら同じ系統の評価値なので、value2は考慮しなくてもいいかな、と思い始めましたｗ

また、確かに「石を置いてみた後の手がCOMの場合で、この関数が始めに呼ばれた場合」というのはありえませんね。
関数の呼び始めはかならずCOMのターンから始まるので、ここは要りませんでした。指摘ありがとうございます。

＞評価値が-7と同じ値が並ぶ問題
これは、そもそも5つのマスが-7と同じ値になってしまうことが問題です。
評価値が本当にこのような値ならばこの動作には文句は無いのですが、その評価値そのものに文句がある状況です。

---------------------------------------------------------------------
現在のソースはこちらです。
http://www1.axfc.net/uploader/Sc/so/257833.zip&key=otl
（value3もアルゴリズムにバグがあったので直しました。）

[softya（ソフト屋)]

これはいずれの盤面（ターン）に於いても「COMから見た」評価値を使用しなければなりませんでした。

これはなにか違う気が？
MAX時はコマを置いた時のＣＯＭから見た評価値の最大を選んで、ＭＩＮ時はコマを置いた時のプレーヤーから見た評価値の最低を選ぶんだと思いますよ。ＣＯＭが最大限に得をしてプレイヤーが損する場所を選ばないと賢い思考とは言えませんからね。

[学生A]

＞MAX時はコマを置いた時のＣＯＭから見た評価値の最大を選んで、ＭＩＮ時はコマを置いた時のプレーヤーから見た評価値の最低を選ぶんだと思いますよ。ＣＯＭが最大限に得をしてプレイヤーが損する場所を選ばないと賢い思考とは言えませんからね。

そうですか？私はその逆だと思います。
「ＭＩＮ時はコマを置いた時のプレーヤーから見た評価値の最低を選ぶ」　としたら、プレイヤーが一番弱い手を打つと仮定して探索を進めることになります。
しかし、本当に強いCPUというのは、プレイヤーが一番強い手を打つと仮定して、それでも勝てるCPUではないでしょうか。

http://hp.vector.co.jp/authors/VA015468 ... o/2_1.html
や
http://hp.vector.co.jp/authors/VA015468 ... o/2_2.html
を参考にして作っていますが、
＞図で葉に書かれている数字は、その局面での評価値をあらわします。
＞（高い方が自分にとって有利だとみなす）
などの記述から、私は常に自分（＝コンピューター）についての評価値を求めるものだと思っています。

う～ん、混乱してきました（汗

[softya（ソフト屋)]

あっ、確かにプレーヤーの手で逆に書いてますね私。失礼しました。
ＣＯＭもプレーヤーも最大限良い所に打たないといけません。
ただし、　MIN-MAX法という言葉に惑わされずその点だけに注目すれば良いのではないでしょうか？

hyouka()で常にcom_turnでひっくり返す箇所を調べるのではなく、now_turnでやらないと正しい動作はしないと思います。
→途中の動作を盤面表示するようにしてSleepで速度を落として表示させてみると分かると思います。

[学生A]

softya（ソフト屋)さん、返信ありがとうございます。
今日は時間がないので、明日詳しく返信したいところですが、
合宿のため、一週間ほど返信できません。
また返信できるときに返信します。

[softya（ソフト屋)]

いえいえ、お気になさらずに時間の取れたときにお気軽にどうぞ。
なにか気ずたことがあったら追加で書き込んでおきます。

[探索経験者]

こんばんは、通りすがりの者です。
こういう探索プログラムを書いた事があるので、若干修正点を・・

コード:

        value = tansaku(n-1,first_n,rev_turn); /* 置いた盤面で、この関数を呼ぶ(再帰)first_nはそのまま渡す */
        
        if( !iscomturn ) {
            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 );
            }
        } else {
            if (value<min) { /* 石を置いてみた後の手がCOMの場合は子節点の評価値のうち最小の値をvalueに格納 */
                min=value;
            }
            if (n==first_n) { /* 石を置いてみた後の手がCOMの場合で、この関数が始めに呼ばれた場合 */   //この条件を満たす可能性はあるのか？
                hyoukati[putable[i]]=min; /* 評価値配列に書き込み */
                printf( "hyoukati[%d]=%d(min)\n", putable[i] ,min );
            }
        }

min-max法の教科書に載っている図式をそのままプログラムにすると確かにこんな感じになるのかもしれませんが、要は

コード:

        value = -tansaku(n-1,first_n,rev_turn);  // 　　******　評価値を反転する　******
         if( value>max) { // 石を置いてみた後の手の評価値のうち最大の値をmaxに格納 
              max=value;
            if(n==first_n){ /* 石を置いてみた後の手が相手（＝Not COM）の場合で、この関数が始めに呼ばれた場合 */
                hyoukati[putable[i]]=max; /* 評価値配列に書き込み */
                printf( "hyoukati[%d]=%d(max)\n", putable[i] ,max );
            }
         }

と得られた評価値の符号を反転させてそれをそのturnの評価値とした方がすっきりします。
また、盤面の評価関数もcomとかmanとか考えるとややこしくなります。そうではなくて、「そのturnの方にとって有利か不利か」を単純に評価値として返します。したがって、評価関数に来たときに黒の番だったら、単純に黒にとって有利であれば高い評価値を、不利であったら低い値(マイナスの評価値)を返します。そうすれば、何手先だろうとcom/man関係なく、すっきりしたプログラムになると思います。
ちなみにmin-max法から更に進展してα-β法という探索方法があります。α-β法はmin-maxで発生する無駄な探索をしないような手法で、こういったゲームではα-β法が一般的に使われます。でも、その前にmin-max法で動きを完成させる必要があるかと思いますので、まず今の方法で動きをおさえておいてください。min-max法ができればα-β法は比較的スムーズに移行できます。

[学生A]

すみません。いろいろと用事が続いて、１週間どころか３週間くらいかかってしまいました。
お二人方がおっしゃるとおり、評価関数をnow_turn基準で考えることにすると、いい感じになりました。
具体的に書くと、深さ「2」の読みで、value1（置ける箇所数）のみを有効にした場合、バリバリ中割りしてくれます。
しかし、深さを「2」以外にすると、中割りとはかなり違う場所に置いてしまいます。（特に奇数の数の読みの場合はひどい）

これは探索がうまく行ってないのか、それとも評価関数が間違っているのか、それともこれが正しい仕様なのか・・・
探索木を全て画面に表示したいところですが、それすらなかなかうまく行かず・・・

＞探索経験者さん
確かに評価値を反転させて常に最高値を選択するというのはシンプルでいいと思います。
しかし、まずは基本のMini-Max法を先に完成させてから、シンプルに書けるところは書いていこうと思います。
α-β法もMini-Max法が完成してから実装してみようと思います。
助言ありがとうございました！

---------------------------------------------------------------------------
現在のソースはこちらです。
http://www1.axfc.net/uploader/Sc/so/264170.zip&key=otl
[変更点]
*評価関数をnow_turn視点で評価するように変更（value1、value2）
*value3の実装の仕方をまた変更（新しく作ったret_sequence関数を８回呼ぶ仕様に変更）

[softya（ソフト屋)]

ネストの深さに関係なく評価値が同じなのが問題かも知れません。

索木を全て画面に表示したいところですが、それすらなかなかうまく行かず・・・

とりあえず全部表示しても見れないので確定した時のネスト毎の評価値を配列にでも保存しておいて、最終確定時に今回の評価値詳細として表示するのはどうでしょうか？

[探索経験者]

>探索木を全て画面に表示したいところですが、それすらなかなかうまく行かず・・・

囲碁や将棋のソフトを作っておられる方のYTree006というソフトがあります。

http://www32.ocn.ne.jp/~yss/ysstree.html

各深さでの探索の手やその評価値をテキスト出力しておけば、自動的にTree表示にしてくれるソフトです。
このソフトを使って手順を解析するというのも手です。
ご参考までに。

[探索経験者]

探索深さが奇数の時と偶数の時で挙動は違ってきます。
最終局面のnow_turnがcom(max局面)の場合はcomは当然「評価関数が最大」になるように動きますが、最終局面のnow_turnがman(min局面)の場合は「評価関数が最少」になるように動きますので、now_turn側が不利になる局面を選ぶことになります。これではちょっと不自然なので、今回のmin-max法では常に最終局面がmax局面となるように深さを奇数or偶数に設定してやる必要があります。
また、最終局面だけでなく途中のmin局面でも当然相手の評価値が最少となる場所を選びます。
今回の評価関数は
　 value=sum_value(now_turn)
みたいになっているので、man側としてはcom側が一番不利になる場所を選びますが、
　　　com側一番不利　→　man側一番有利
とは必ずしも限らないと思います。
例えば中割りする事が有利でcom側がそういう手を選ぶとして、man側としてはcom側の中割りを阻止する事が必ず有利なのでしょうか。自分も中割りしたいと、できればそういった手を選びたいと考えるはずです。従って、片側だけの事を考えた評価関数ですと、深さを深くすればするほどman側は実際とはかけ離れた手順を打つ事になります。
解消するためには、
　 value=sum_value(now_turn)-sum_value(rev_turn)
みたいに相手の立場でも盤面を評価してそのトレードオフの結果を評価関数の評価値とした方がうまくいくと思います。

[学生A]

すみません。このスレッドは長くなってしまったので、
http://dixq.net/forum/viewtopic.php?f=3&t=9118
こちらに移行します。

[学生A]

解決。