MiniMax法のコードが分からない

質問

こんにちは。
前回では、MiniMax法がよくわからないと説明をしたのすが、Ｃのコード自体がよく分からない
のでまた質問させていただきました。
自分は今、オセロゲームを制作しています。

http://hp.vector.co.jp/authors/VA015468/platina/algo/2_2.html

このサイトにあるコードなのですが

int mm_max(int t) /* 自局面の節点 tは葉局面までの手数 */
{
int max = -N; /* Nは十分大きな値 */
int v;

if(t == 0)
return (現在の局面の評価値);

for(最初の子節点の手; 未評価の子節点がある; 次の子節点に移る){
局面に子節点の手を打つ;
v = mm_min(t-1, alpha, beta);
局面を元に戻す;
if(v > max)
max = v;
}

return max;
}

mm_min(int t) /* 自局面の節点 tは葉局面までの手数 */
{
int min = -N; /* Nは十分大きな値 */
int v;

if(t == 0)
return (現在の局面の評価値);

for(最初の子節点の手; 未評価の子節点がある; 次の子節点に移る){

局面に子節点の手を打つ;
v = mm_max(t-1);
局面を元に戻す;
if(v < min)
min = v;
}

return min;
}

return (現在の局面の評価値);
とあるのですが現在の局面の評価値というのは一体どういうものなんでしょうか？

最初の子節点の手; 未評価の子節点がある; 次の子節点に移る
とありますが、　まず一手置いた場所を保存しておき、未評価の子節点を探すみたいですが、どのようになるのかうまく想像できません。

　 局面に子節点の手を打つ;　というのは子節点というものにすでに置く座標の値があるんでしょうか？

　　局面を元にもどす。　というのはどういう意味でしょうか？
すこしづつ子節点を戻していくということなんでしょうか？

　　よろしくお願いします。

回答No.2

salsberry · ベストアンサー

続き。

> 最初の子節点の手; 未評価の子節点がある; 次の子節点に移る
> とありますが、

for文の文法は分かっていますか?

> 局面に子節点の手を打つ;　というのは子節点というものにすでに置く座標の値があるんでしょうか？

実際には、現在石が置かれていない座標を一つ一つ「ここに黒(あるいは白)の石を置けるか？」とチェックして行って、置ける場所が見つかったらそこに石を置くという手順になるでしょう。もちろん、それを効率化する余地はあります(効率化すれば、同じ時間内に読める手数が増えます)。

> 局面を元にもどす。　というのはどういう意味でしょうか？

mm_max()の中だったらmm_min()を呼ぶ前に一手打ちますよね。mm_min()から戻ってきたら、その一手を打つ前の状態に戻すということです。
たとえば、mm_max()が呼ばれたときにゲーム開始から30手打ち終わった局面だったとします。「局面に子節点の手を打つ;」で31手目の候補手の一つを打ちます。mm_min()から戻ってきたら、盤上の石の状態を30手目まで終わった状態に戻すのです。この作業を全ての候補手に対して繰り返すのが前出のfor文です。
mm_max()から呼ばれたmm_min()では、32手目の候補手を一つ打ってはmm_max()を呼び、mm_max()から戻ってきたら31手目まで打たれた状態に戻すということを繰り返します。

最後に、再帰呼び出しって理解していますか? 質問にあるプログラムはmm_min()がmm_max()を呼び、mm_max()がmm_min()を呼ぶという構造になっています。これは再帰呼び出しの中でも相互再帰と呼ばれるものです。
再帰呼び出しは一度理解すれば便利で強力ですが、なかなか理解できない人もいるので。

お礼

二度目の回答　ありがとうございます。
子節点の部分の構成をよく理解したいと思います。

回答No.1

salsberry

> 現在の局面の評価値というのは一体どういうものなんでしょうか？

ここで言う「現在」とは、X手先まで石を置いた状態のことです。その局面が自分にとってどれくらい有利/不利かを表す点数をつけます。
X手より先を読むことはしないので、その局面での石の配置だけから計算します。前の質問にもキーワードとして出てきている静的評価というやつです。
たとえば、「白と黒の石の数の差」とか「角を取れていると有利」とか、そういうことを点数化します。ゲームの序盤と終盤ではその評価方法も違ってくるでしょう。

オセロゲームのプログラムは基本的にどれもミニマックス法(その改良型のα-β法)を使って書かれているので、プログラムの強弱は何手先まで読めるかと、静的評価関数のセンスによって決まります。どんな評価関数が正解ということはないので、自分が「こうだ」と思う評価関数を作って試行錯誤してください。

お礼

回答ありがとうございます。
静的評価関数が重要なんですね。