c言語でのMiniMax法の実装について教えてください!!

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
kaps24
記事: 1
登録日時: 9年前

c言語でのMiniMax法の実装について教えてください!!

#1

投稿記事 by kaps24 » 9年前

C言語をはじめて5ヶ月ほどの初心者です。
現在、オセロを作ろうとしているのですが、コンピュータのAI部分がうまくいきません。
MiniMax法で最善手を選ばせようとしています。再帰を使ったMiniMax法の実装方法の解答やヒント、なんでもいいんで教えてください。
よろしくお願いします。

以下、製作途中のコードです。

コード:

#include<stdio.h>
#include<time.h>
#define swap(a,b) {a += b; b = a - b; a -= b;}
#define DEPTH 6
#define O -1//番兵
#define N 0 //何も置かれていない場所
#define P 1 //石を置ける場所
#define B 2 //黒石
#define W 3 //白石

void com_stone(int board[], int stone, int depth);
int MiniMax(int board[], int stone, int depth);
int evalue(int board[], int stone, int turn);
int com_calc(int board[], int stone, int turn);

int board1[90];
int board2[90];
int board3[90];
int board4[90];
int board5[90];
int board6[90];

int turn_judge(void)
{
  int i = rand() % 2;

  if(i == 0)
    printf("\nあなたは先攻(黒)です.\n\n");
  else
    printf("\nあなたは後攻(白)です.\n\n");

  return i;
}

int put_stone(int board[], int turn, int stone)
{
  int i, pass_cnt = 0;
  char eng[2], enter[2];
  int num;

  for(i = 9; i < 80; i++)
    if(board[i] == P)
      pass_cnt++;

  if(turn == 0){
    printf("\nあなたのターンです.\n");

    if(pass_cnt == 0){
      printf("\a置ける場所がありません!!\n\n");
      return 0;
    }
    else
      printf("石を置く場所を選んでください.\n");
    do{
      printf("英字 :"); fgets(eng, 2, stdin);
      printf("数字 :"); scanf("%d", &num); fgets(enter, 2, stdin);
      putchar('\n');
    }while(board[eng[0]-88 + (num-1)*9] != P);

    return eng[0]-88 + (num-1)*9;
  }

  if(turn == 1){
    printf("\nコンピュータのターンです.\n");

    if(pass_cnt == 0){
      printf("\a置ける場所がありません!!\n\n");
      return 0;
    }
    else
      return com_calc(board, stone, turn);
  }
}

void reflect(int board[], int stone, int xy)
{
  int vec[8] = {-10, -9, -8, -1, 1, 8, 9, 10};
  int i, j, k, l;
  int ok = 0;

  //黒石のターン
  if(stone == 0){
    board[xy] = B;
    for(k = 0; k < 8; k++){
      if(xy + vec[k] > 0 && xy + vec[k] < 89)
	if(board[xy + vec[k]] == W)
	  for(l = vec[k]; xy+l > 0, xy+l < 89; l += vec[k]){
	    if(board[xy + l] == W)
	      ;
	    else if(board[xy + l] == N || board[xy + l] == P || board[xy + l] == O)
	      break;
	    else if(board[xy + l] == B){
	      ok++;
	      break;
	    }
	  }

      if(ok){
	for(l = vec[k]; xy+l > 0, xy+l < 89; l += vec[k]){
	  if(board[xy + l] == B || board[xy + l] == O)
	    break;
	  else
	    board[xy + l] = B;
	}
	ok = 0;
      }
    }
  }

  //白石のターン
  if(stone == 1){
    board[xy] = W;
    for(k = 0; k < 8; k++){
      if(xy + vec[k] > 0 && xy + vec[k] < 89)
	if(board[xy + vec[k]] == B)
	  for(l = vec[k]; xy+l > 0, xy+l < 89; l += vec[k]){
	    if(board[xy + l] == B)
	      ;
	    else if(board[xy + l] == N || board[xy + l] == P || board[xy + l] == O)
	      break;
	    else if(board[xy + l] == W){
	      ok++;
	      break;
	    }
	  }

      if(ok){
	for(l = vec[k]; xy+l > 0, xy+l < 89; l += vec[k]){
	  if(board[xy + l] == W || board[xy + l] == O)
	    break;
	  else
	    board[xy + l] = W;
	}
	ok = 0;
      }
    }
  }
}

  //石が置ける場所にマーク
void point(int board[], int stone)
{
  int i, j, l, k;
  //走査方向
  int vec[8] = {-10, -9, -8, -1, 1, 8, 9, 10};

  //黒石のターン
  if(stone == 0){
    for(i = 9; i < 80; i++){
      if(board[i] == N)
	for(k = 0; k < 8; k++){
	  if(i + vec[k] > 0 && i + vec[k] < 89)
	    if(board[i + vec[k]] == W)
	      for(l = vec[k]; i+l > 0, i+l < 89; l += vec[k]){
		if(board[i+l] == W)
		  ;
		else if(board[i+l] == N || board[i+l] == P || board[i+l] == O)
		  break;
		else if(board[i+l] == B)
		  board[i] = P;
	      }
	}
    }
  }

  //白石のターン
  if(stone == 1){
    for(i = 9; i < 80; i++){
      if(board[i] == N)
	for(k = 0; k < 8; k++){
	  if(i + vec[k] > 0 && i + vec[k] < 89)
	    if(board[i + vec[k]] == B)
	      for(l = vec[k]; i+l > 0, i+l < 89; l += vec[k]){
		if(board[i+l] == B)
		  ;
		else if(board[i+l] == N || board[i+l] == P || board[i+l] == O)
		  break;
		else if(board[i+l] == W)
		  board[i] = P;
	      }
	}
    }
  }
}

int main(void)
{
  srand(time(NULL));
  int turn_cnt, stone = 0; //黒白のターンを入れ替える(0=>黒: 1=>白)
  int i, j, line = 1;
  int board[90] = {N};
  int xy, game_cnt = 0, fin_judge;
  int stone_num = 0, siro = 0, kuro = 0;

  //盤面の初期化
  for(i = 0, board[89] = O, board[39] = board[49] = W, board[40] = board[48] = B; i < 9; i++){
    board[i] = O;
    board[81 + i] = O;
    board[8 + i*9] = O;
  }

  turn_cnt = turn_judge();   //先攻、後攻を決める(0=>あなた : 1=>コンピュータ)

  while(1){

    //石が置ける場所にマークを付ける
    point(board, stone);

    //盤面の表示
    printf("    a  b  c  d  e  f  g  h  \n");
    for(i = 0; i < 72; i += 9){
      if(i == 18 || i == 54)
	printf("    ー ー・ー ー ー ー・ー ー\n");
      else
	printf("    ー ー ー ー ー ー ー ー\n");
      for(j = 9; j < 18; j++){
	if((i+j) % 9 == 0)
	  printf(" %d ", line++);
	if(board[i+j] == N)
	  printf("|  ");
	else if(board[i+j] == B)
	  printf("|● ");
	else if(board[i+j] == W)
	  printf("|○ ");
	else if(board[i+j] == P)
	  printf("|・");
	if((i+j) % 9 == 8)
	  printf("|\n");
      }
    }
    printf("    ー ー ー ー ー ー ー ー\n");
    line = 1;
    //表示ここまで

    //まだ置ける場所があるか確認
    for(i = 9; i < 80; i++)
      if(board[i] == N || board[i] == P)
	stone_num++;
    if(stone_num == 0)
      break;
    else
      stone_num = 0;

    //石を置く場所を決める
    xy = put_stone(board, turn_cnt, stone);

    //石を反転
    if(xy != 0)
      reflect(board, stone, xy);

    //マークの初期化
    for(i = 9; i < 80; i++)
      if(board[i] == P)
	board[i] = N;

    turn_cnt = 1 - turn_cnt;
    stone = 1 - stone;
    game_cnt++;

    //パスが2回続いたかの判定
    if(xy == 0){
      if(game_cnt == fin_judge + 1)
	break;
      else
	fin_judge = game_cnt;
    }
  }//while終

  //石数をカウント
  for(i = 9; i < 80; i++){
    if(board[i] == B)
      kuro++;
    else if(board[i] == W)
      siro++;
  }

  if(kuro > siro)
    printf("黒%d石勝ち!!\n", kuro - siro);
  else if(siro > kuro)
    printf("白%d石勝ち!!\n", siro - kuro);
  else
    printf("引き分け!!\n");

  return 0;
}

//未完成
void com_stone(int board[], int stone, int depth)
{
  int i, xy, box[28], c = 0;

  //石が置ける場所にマークを付ける
  point(board, stone);

  //座標を取得
  for(i = 9; i < 80; i++)
    if(board[i] == P)
      box[c++] = i;

  //石を反転
  reflect(board, stone, xy);

  //マークの初期化
  for(i = 9; i < 80; i++)
    if(board[i] == P)
      board[i] = N;

  //番の入れ換え
  stone = 1 - stone;
}

//未完成
int MiniMax(int board[], int stone, int depth)
{
  int i, best;

  if(depth == 0)
    return evalue(board, stone, turn);

  com_stone(board, stone, depth);

}
//盤面評価(仮)
int evalue(int board[], int stone, int turn)
{
  int i;
  int kuro = 0, siro = 0;
  int hyouka[90] = {
    -50,-50,-50,-50,-50,-50,-50,-50,-50,
    30,-12,  0, -1, -1,  0,-12, 30,-50,
    -12,-15, -3, -3, -3, -3,-15,-12,-50,
    0, -3,  0, -1, -1,  0, -3,  0,-50,
    -1, -3, -1, -1, -1, -1, -3, -1,-50,
    -1, -3, -1, -1, -1, -1, -3, -1,-50,
    0, -3,  0, -1, -1,  0, -3,  0,-50,
    -12,-15, -3, -3, -3, -3,-15,-12,-50,
    30,-12,  0, -1, -1,  0,-12, 30,-50,
    -50,-50,-50,-50,-50,-50,-50,-50,-50,
  };

  for(i = 9; i < 80; i++){
    if(board[i] == B)
      kuro += hyouka[i];
    else if(board[i] == W)
      siro += hyouka[i];
  }

  //コンピュータが黒
  if(turn == 1 && stone == 0)
    return kuro - siro;
  else if(turn == 0 && stone == 1)
    return kuro - siro;
  //コンピュータが白
  else if(turn == 1 && stone == 1)
    return siro - kuro;
  else if(turn == 0 && stone == 0)
    return siro - kuro;
}

//コンピュータを管理(未完成)
int com_calc(int board[], int stone, int turn)
{
  MiniMax(board,stone,DEPTH);

  return com1[0][0];
}

“C言語何でも質問掲示板” へ戻る