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

前へ 次へ
このQ&Aのポイント
  • MiniMax法のコードが分からないため、質問させていただきます。
  • 現在の局面の評価値とは何を指すのか疑問です。
  • 子節点の手を打つとは、どのような操作を行うのか理解できていません。
回答を見る
  • ベストアンサー

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 (現在の局面の評価値); とあるのですが現在の局面の評価値というのは一体どういうものなんでしょうか？ 最初の子節点の手; 未評価の子節点がある; 次の子節点に移る とありますが、　まず一手置いた場所を保存しておき、未評価の子節点を探すみたいですが、どのようになるのかうまく想像できません。 　 局面に子節点の手を打つ;　というのは子節点というものにすでに置く座標の値があるんでしょうか？ 　　局面を元にもどす。　というのはどういう意味でしょうか？ すこしづつ子節点を戻していくということなんでしょうか？ 　　よろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
  • salsberry
  • ベストアンサー率69% (495/711)
回答No.2

続き。 > 最初の子節点の手; 未評価の子節点がある; 次の子節点に移る > とありますが、 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()を呼ぶという構造になっています。これは再帰呼び出しの中でも相互再帰と呼ばれるものです。 再帰呼び出しは一度理解すれば便利で強力ですが、なかなか理解できない人もいるので。

DEADSPACE566
質問者

お礼

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

その他の回答 (1)

  • salsberry
  • ベストアンサー率69% (495/711)
回答No.1

> 現在の局面の評価値というのは一体どういうものなんでしょうか？ ここで言う「現在」とは、X手先まで石を置いた状態のことです。その局面が自分にとってどれくらい有利/不利かを表す点数をつけます。 X手より先を読むことはしないので、その局面での石の配置だけから計算します。前の質問にもキーワードとして出てきている静的評価というやつです。 たとえば、「白と黒の石の数の差」とか「角を取れていると有利」とか、そういうことを点数化します。ゲームの序盤と終盤ではその評価方法も違ってくるでしょう。 オセロゲームのプログラムは基本的にどれもミニマックス法(その改良型のα-β法)を使って書かれているので、プログラムの強弱は何手先まで読めるかと、静的評価関数のセンスによって決まります。どんな評価関数が正解ということはないので、自分が「こうだ」と思う評価関数を作って試行錯誤してください。

DEADSPACE566
質問者

お礼

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

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • int型変数の簡潔なプログラム

    #include<iostream> using namespace std; int main(void){ int max = a; int min = a; if(a > b){ min = b; }else{ max = b; } cout << "小さい方の値は" << min << "です。\n"; cout << "大きい方の値は" << max << "です。\n"; } これの、 　　　int max = a; int min = a; と 　　　 if(a > b){ min = b; }else{ max = b; } が解りません。 何故変数をaからbにチェンジしているのでしょうか 初心者なのでお手柔らかにお願いします。 よろしくお願いします。

  • 再帰

    他の質問と平行してしまい申し訳ありません。再帰について少々おききしたいのですが、 配列の中にある数字の中から最大値と最小値を再帰処理でもとめたいのですが、うまくいきません。 public int minMax(n, array, min, max){　// nは配列のサイズです。 min=max=array[n-1]; if(array[n-2]<min) min=array[n-2]; if(array[n-2]>max) max=array[n-2]; return minMax(n-1,array,min,max); ｝ 最初に比較するために min=max=array[n-1];と初期化したのですが、再帰処理ですからまた同じ初期化をしてしまうことになります。 forループなどを使えるなら初期化だけループの外でやれば済むのですが、再帰だとどのようにすればよいのでしょうか。 宜しくお願いいたします。

  • プログラミング（C言語）についての質問です

    ３つの整数の入力を受け付け、最大と最小を求める関数を作成し得られた結果を表示するプログラミングを作成したつもりなのですが、うまく作動しません。（コンパイルはできますが、結果が無茶苦茶になります。） ご教授宜しくお願いします。 それと、課題文にはポインタを使って最大値と最小値を同時に求めるようにと書いてあったのですが、それもよくわからないです。 今回初めてポインタと配列の受け渡しについて習ったのでよくわかっていない部分も多いと思うのですが、何卒宜しくお願いします。 ちなみに関数の形自体は void minmax(int data[],int *min,int *max){} で決まっています。 #include <stdio.h> void minmax(int data[],int *min,int *max){ int i; *min=*max=data[0]; printf("1st intenger:"); scanf("%d",&data[0]); printf("2st intenger:"); scanf("%d",&data[1]); printf("3st intenger:"); scanf("%d",&data[2]); for(i=1;i<3;i++){ if(*max<data[i]){ *max=data[i]; } if(*min>data[i]){ *min=data[i]; } } } int main(void){ int data[3],min,max; minmax(data,&min,&max); printf("最小値は%dで最大値は%dです",min,max); return 0; }

  • Cのソースコードについて

    以下のソースコードをかきました。 #include<stdio.h> #include<string.h> #define MAX 100005 typedef struct PP { int t; char name[100]; }P; P Q[MAX]; int head, tail, n; void enqueue(P u) { Q[tail] = u; tail = (tail + 1) % MAX; } P dequeue() { P x = Q[head]; head = (head + 1) % MAX; return x; } int min(int a, int b) { return a > b ? a : b; } int main() { int q, sum = 0 , w; scanf("%d %d", &n,&q); for (int i = 1; i <= n; i++){ scanf("%s", Q[i].name); scanf("%d", &Q[i].t); } head = 1; tail = n + 1; P u; while (head != tail) { u = dequeue(); w = min(q, u.t); sum += w; u.t -= w; if (u.t > 0)enqueue(u); else { printf("%s %d", u.name, sum); } } return 0; } これでVisual C++ でコンパイルしたところ特にエラーも起きず問題なく動作しました しかしAOJに提出してみたところコンパイルエラーになってしまい詰んでしまいました どこかダメそうなところがあれば教えてください

  • 正規分布するプログラムを教えてください。

    正規分布する乱数プログラムを作りたいのですが、うまく作れません・・。 プログラムソースは長くなりますので見ていただかなくても結構なのですが、下記のようなプログラムを実行したところ、実行結果下記になり、正規分布にはなりませんでした・・。 色々ネットで調べたものの理解できないのでどなたか教えていただけないでしょうか＞＜ 正規分布を利用して、例えば50～100位の間に分布する乱数を生成したりしたいのです。。。 #include <math.h> #include <time.h> #include <stdlib.h> #include <stdio.h> #define PI 3.14159265358979323846264 double p_nor(){ double rnd,t,u,r1,r2; rnd=rand()%10000/10000.0; t=sqrt(-2.0 * log(1-rnd)); u=2*PI*rnd; r1=t*sin(u); return r1; } int main(){ int i,bunpu[30]={}; double p,min=0,max=0,total=0; srand((unsigned)time(NULL)); for(i=0;i<100000;i++){ p=p_nor(); for(int j=0;j<30;j++){ if(p>-2.0+0.1*j && p<=-1.9+0.1*j) bunpu[j]++; } if(min>p)min=p; if(max<p)max=p; total+=p; } printf("min:%f max%f 平均%f\n",min,max,total/100000); for(int j=0;j<30;j++){ for(i=0;i<bunpu[j]/200;i++){ printf("*"); } printf("\n"); } return 0; } 実行結果 min:-1.711381 max0.803275 平均-0.247841 **************** ************************************ ******************** **************** ************** ************ *********** ********** ********** ********* ********* ******** ******** ******** ******** ******** ******** ******** ************************************* ************************* *********************** *********************** ************************ **************************** ******************************** **************************************************************** ***********

  • フローチャート　

    このプログラムのフローチャートを教えてください １class QNode{ 2 private int min; 3 private int max; 4 private int mid; 5 private int key; 6 private int max2[]; 7 private int[] q; 8 static int k; 9 10 public QNode(int[] c){ 11 q=c; 12 max2=new int[10000]; 13 k=0; 14 } 15 16 public void narabikae(int a,int b){ 17 int tmp=q[a]; 18 q[a]=q[b]; 19 q[b]=tmp; 20 } 21 22 public void quick(int mi,int mx){ 23 24 min=mi; 25 max=mx; 26 max2[k]=mx; 27 28 if(min<max){ 29 mid=(min+max)/2; 30 key=q[mid]; 31 int i=min; 32 int j=max; 33 34 while(true){ 35 while(q[i]<key){ 36 i++; 37 } 38 while(key<q[j]){ 39 j--; 40 } 41 if(j<i) 42 break; 43 44 narabikae(i,j); 45 i++; 46 j--; 47 48 if(j<i) 49 break; 50 } 51 k++; 52 quick(min,j); 53 max=max2[--k]; 54 quick(i,max); 55 } 56 } 57} 58 59public class A1 { 60 61 /** 62 * @param args 63 */ 64 public static void main(String[] args) { 65 66 int[] q={2,8,4,11,15,9,1,13,19}; 67 68 QNode qn=new QNode(q); 69 qn.quick(0,8); 70 71 for(int i=0;i<9;i++){ 72 System.out.print(q[i]+" "); 73 } 74 } 75}

  • ｃプログラム

    次の１０人の身長を入れ、最大と最小を配列を使って求めるプログラムなんですが、この場合だと一人の身長データしか入力できません どのように直せばいいでしょうか？ #include <stdio.h> main () { float h[10],max,min; int i; max=-999; min=999; for(i=0;i<=9;i=i+1){ printf("%d番目の身長を入力してください\n",i+1); scanf("%5.1f",&h[i]); if(h[i]>max){ max=h[i]; } if(h[i]<min){ min=h[i]; } } printf("最大の身長は%5.1f,最小の身長は%5.1fです。\n",max,min); return(0); }

  • javaプログラムについて

    コマンドライン引数から複数の値を受け取り、それらの最大と最小を表示する、というプログラムなのですが。 class Maxmin{ 　　public static void main (String[] args) { 　　　int max=Integer.MIN_VALUE; 　　　int min=Integer.MAX_VALUE; 　　　for (int i=0; i<args.length; i++){ 　　　　int num= Integer.parseInt(args[i]); 　　　　if(num>max) 　　　　max=num; 　　　　if(num<min) 　　　　min=num; 　　　} 　　　System.out.println("最大値は" + max + "です。"); 　　　System.out.println("最小値は" + min + "です。"); 　} } このプログラムでも問題なく表示されるのですが、MIN_VALUEとMAX_VALUEを使用せずに表示する事、と指摘を受けました。自分の中でぱっと思いついたのがこれだったのですが、他にはどのような方法があるのでしょうか？

    • ベストアンサー
    • Java
  • 深さ優先探索について・・・

    ↓の文を参考にして、深さ優先探索のプログラムを書いてみました。 が、自分（初心者）ではできてるように思えたんですが、全然ダメみたいです。 再帰の使い方がよく分かってないというのもあるのですが（すみません）。 もしよろしければアドバイスを頂けませんか？お願いします！ 『・始点(ここでは「1」)を出発して、番号が小さい順に進む位置を調べていき 　行けるところ(辺でつながっていて、まだ未訪問の節点)まで進む。 ・行き場所が無くなったら、行けるところがある節点まで戻っ(再帰をリターンし)　て再び進めるだけ進む。 ・行き場所がなくなったなら終了(再帰からリターン) プログラムの際に節点iから節点jへ進めるか否かは節点と枝の関係を表すテーブル(これを隣接行列と言う)の要素a[i][j]の値が1であり、かつ訪問フラグv[j]が0であった時です。 訪問フラグは初期値に0を入れ(未訪問を表す)、 節点jが訪問されたならv[j]に1を入れます』 #include<stdio.h> int recurse(int i,int j); int main(void){ int recurse(int i,int j); return 0; } int recurse(int i,int j){ int v[j]; int a[i][j]; v[j]=0; v[0]=0; a[i][j]={{0,1,1,0,0,0,0,0}, {1,0,0,1,0,0,0,0}, {1,0,0,1,0,0,0,0}, {0,1,1,0,1,0,0,0}, {0,0,0,1,0,1,0,1}, {0,0,0,0,1,0,1,0}, {0,0,0,0,0,1,0,1}, {0,0,0,0,1,0,1,0}}; for(i=0;i<8;i++){ for(j=0;j<8;j++){ if(a[i][j] == 1 && v[j] == 0){ v[j]=1; printf("%d->%d ",i,j); break; } else return 0; } } return 0; }

  • なんらかの原因でtxtにデータを入力できない

    こんにちは。 Ｃ言語初心者です。 まずこのようなデータを用意しました。 kus1.txt 89 65 37 44 51 30 20 10 そして、このようなプログラムをし、ビルトしました。 #include <stdio.h> #define NUM 8 int main(void) { FILE *fp; int kusa[NUM]; int max,min; int i,k; fp = fopen("kus1.txt","r"); if(fp == NULL){ printf("ファイルオープン失敗\n"); return 1; } for(i=0; i<NUM; i++){ fscanf(fp, "%d", &kusa[i]); } max = kusa[0]; min = kusa[0]; for(k=0; k<NUM; k++){ if(max < kusa[k]) max = kusa[k]; if(min > kusa[k]) min = kusa[k]; printf("NO.%-5d%d\n", k+1, kusa[k]); } printf("最高は%d。\n", max); printf("最低は%d。\n", min); fclose(fp); return 0; } その後、コマンドプロンプトでこれを実行したところ、 ファイルオープン失敗 とでてきました。つまりなんらかの原因で失敗しました。 どうしたら成功できるのでしょうか。教えてください。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する