xxxasdfghjk999のブログ

iroiro

3種のオセロAI

プログラミング備忘録

前作ったオセロのAIとかにちょっと改良を加えてみました
ソースは続きから

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<unistd.h>
enum type{black,white,space};
enum type board[8][8];
enum type user;
enum type com;
enum type tend(enum type);
int ReverseStone(int,int,enum type,enum type[][8]);
void copyboard(enum type[][8],enum type[][8]);
void ShowBoard();
enum type tend(enum type t)
{
  if(t==black)
    return white;
  else
    return black;
}
int maxv(int v[])
{
  int i,m=-10;
  for(i=0;i<64;i++)
    if(v[i] > m)
      m = v[i];
  return m;
}
int maxxy(int n[][8],int v[],int *x,int *y)
{
  int r,i,j,value=-8,c=0;
  for(j=0;j<8;j++)
    for(i=0;i<8;i++)
      if(n[j][i] > value && v[i+j*8]){
        value = n[j][i];
        *x = i;
        *y = j;
      }
  r = rand() % 8;
  for(j=0;;j++)
    for(i=0;i<8;i++)
      if(n[j%8][i] == value)
        if(r == c++){
          *x = i;
          *y = j % 8;
          return value;
        }
  return value;
}

void CPU_fixed(enum type turn)
{
  enum type b[8][8],u[8][8],t=tend(turn);
  int vect[2][64],x,y,v;
  int sub[8][8];
  copyboard(b,board);
  int i,j,k,l,dep;
  for(j=0;j<8;j++)
    for(i=0;i<8;i++){
        vect[0][i+j*8] = ReverseStone(i,j,turn,b);
        copyboard(u,b);
        for(k=0;k<8;k++)
          for(l=0;l<8;l++){
            if(vect[1][l+k*8] = ReverseStone(l,k,t,u))
              copyboard(u,b);
          }
        sub[j][i] = vect[0][i+j*8] - maxv(vect[1]);
        copyboard(b,board);
    }
  v = maxxy(sub,vect[0],&x,&y);
  ReverseStone(x,y,turn,board);
  ShowBoard();
  printf("your turn(%d,%d)\n",x,y);
}

void CPU_monkey(enum type turn)
{
  int x,y;
  while(!ReverseStone(x = rand()%8,y = rand()%8,turn,board));
  ShowBoard();
  printf("your turn(%d,%d)\n",x,y);
}

void ShowBoard()
{
  int i,j;
  printf(" 一二三四五六七八\n");
  for(j=0;j<8;j++){
    printf("%d",j+1);
      for(i=0;i<8;i++){
        switch(board[j][i]){
        case space:
          printf("・");
          break;
        case black:
          printf("○");
          break;
        case white:
          printf("●");
          break;
        }
      }
    printf("\n");
    }
  printf("\n");
}
void copyboard(enum type a[][8],enum type b[][8])
{
  int i,j;
  for(j=0;j<8;j++)
    for(i=0;i<8;i++)
      a[j][i] = b[j][i];
}

void CPU(enum type turn)
{
  enum type b[8][8];
  int c,i,j,max=0,v[8][8];
  for(j=0;j<8;j++)
    for(i=0;i<8;i++){
      copyboard(b,board);
      v[j][i] = ReverseStone(i,j,turn,b);
    }
  for(j=0;j<8;j++)
    for(i=0;i<8;i++)
      if(max < v[j][i])
        max = v[j][i];
  while(1){
  for(j=0;j<8;j++)
    for(i=0;i<8;i++){
      if(v[j][i] == max)
        if(rand() % 8 == 0){
          if(!(c = ReverseStone(i,j,turn,board)))
            printf("CPU : う～ん、パス！ｗ\n");
          //ShowBoard();
          //if(c)
            //printf("CPU : Your Turn... !!! (with putting stone on (%d,%d)\n",i+1,j+1);

          return;
        }
    }
  }
}

void PutStone(enum type turn)
{
  int x,y;
  if(turn == user){
    printf("Now is your turn !!\n");
    do{
      scanf("%d %d",&x,&y);
      x--;
      y--;
      if(!ReverseStone(x,y,turn,board))
        printf("Youcan't put stone there !!\n");
      else
        break;
    }while(1);
    ShowBoard();
    printf("You : I set Stone (%d,%d) !! Turn End !!\n",x+1,y+1);
  }else{
    CPU_fixed(turn);
  }

}
int CheckBoard()
{
  int i,j;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++){
      if(board[i][j] == space)
        return 0;

    }
  return 1;
}
int SkipJudge(enum type turn)
{
  int i,j;
  enum type b[8][8];
  copyboard(b,board);
  for(j=0;j<8;j++)
    for(i=0;i<8;i++){
      if(ReverseStone(i,j,turn,b))
        return 0;
      copyboard(b,board);
    }
  return 1;
}
enum type JudgeGame()
{
  int i,j,w=0,b=0;
  for(j=0;j<8;j++)
    for(i=0;i<8;i++)
      if(board[j][i] == white)
        w++;
      else if(board[j][i] == black)
        b++;
  if(w > b)
    return white;
  if(w < b)
    return black;
  else
    return space;
}
void EndGame()
{
  int b=0,w=0,i,j;
  enum type win = JudgeGame();
  printf("Game Maker : 結果発表～～～～！！！\n");
  if(win == space){
    printf("Game Maker : Draw !!!!!\n");
    return;
  }
  if(user == black){
    if(win == user)
      printf("Game Maker : Player , WIN !!!!\n");
    else{
      printf("Game Maker : Player , LOSE ↓↓\n");
    }
  }else if(user == white){
    if(win == user)
      printf("Game Maker : Player , WIN !!!!\n");
    else{
      printf("Game Maker : Player, LOSE ↓↓\n");
    }
    printf("We wait for your next challenge !!!\n");
    printf("------END-------");
  }
}

int play()
{
  int s=0;
  enum type t = black;
  while(1){
  PutStone(t);
  if(CheckBoard(t))
    break;
  t = tend(t);
  if(SkipJudge(t)){
    t = tend(t);
    if(SkipJudge(t))
      break;
  }
  }
  EndGame();
}

int CPUvs()
{
  int u,c;
  for(u=0;u<8;u++)
    for(c=0;c<8;c++)
      board[u][c] = space;
  srand((unsigned)time(NULL));
  board[3][3] = board[4][4] = white;
  board[3][4] = board[4][3] = black;
  enum type t = black;
  user = black;
  com = white;
  while(1){
    //sleep(1)
    switch(t){
    case black:
      CPU_monkey(t);
      break;
    case white:
      CPU_fixed(t);
      break;
    }
    if(CheckBoard())
      break;
    t = tend(t);
    if(SkipJudge(t)){
      t = tend(t);
    if(SkipJudge(t))
      break;
    }
  }
  //printf("----終戦----\n");
}

void SetBoard(){
  int u,c;
  for(u=0;u<8;u++)
    for(c=0;c<8;c++)
      board[u][c] = space;
  srand((unsigned)time(NULL));
  board[3][3] = board[4][4] = white;
  board[3][4] = board[4][3] = black;
  printf("Dice was thrown !!\n");
  do{
  printf("Your number is %d !\n",u = rand() %6 +1);
  printf("Com number is %d !\n",c = rand() %6 +1);
  }while(u == c);
  printf("So %s get first move!!\n",u > c ? "user" : "com");
  printf("Ready...Fight!!\n");
  if(u > c){
    user = black;
    com = white;
  }else{
    user = white;
    com = black;
  }
}
int main(int argc,char* argv[])
{
  int i,b=0,w=0,d=0,j;
  if(argc > 1){
    for(i=0;i<500;i++){
    CPUvs();
    if(j = JudgeGame() == white)
      w++;
    else if(j == black)
      b++;
    else
      d++;
    }
    printf("White Win = %d\n",w);
    printf("Black Win = %d\n",b);
    printf("Draw = %d\n",d);
  }
  else{
  SetBoard();
  ShowBoard();
  play();
  }
}

int ReverseStone(int x,int y,enum type turn,enum type board[8][8])
{
  int s,t,p,q,num=0;
  //横
  if(board[y][x] != space)
    return 0;
  for(t=y-1;t<=y+1;t++)
    for(s=x-1;s<=x+1;s++){
      if(s<0 || s>7 || t<0 || t>7)
        continue;
      p = s;
      q = t;
      if(y-1 == q){
        if(p == x-1){
          if(board[y-1][x-1] != turn && board[y-1][x-1] != space){
            while(board[q][p] != turn && board[q][p] != space)
              if(q-1 >= 0 && p-1 >= 0){
                q--;
                p--;
              }else
                break;
            if(board[q][p] == turn){
              while(++q<=y-1 && ++p<=x-1){
                num++;
                board[q][p] = turn;
              }
            }
          }
        }else if(p == x){
          if(board[y-1][x] != turn && board[y-1][x] != space){
            while(board[q][p] != turn && board[q][p] != space)
              if(q-1 >= 0){
                q--;
              }else
                break;
            if(board[q][p] == turn){
              while(++q<=y-1){
                num++;
                board[q][p] = turn;
              }
            }
          }
        }else if(p== x+1){
          if(board[y-1][x+1] != turn && board[y-1][x+1] != space){
            while(board[q][p] != turn && board[q][p] != space)
              if(q-1 >= 0 && p+1 <= 7){
                q--;
                p++;
              }else
                break;
            if(board[q][p] == turn){
              while(++q<=y-1 && --p>=x+1){
                num++;
                board[q][p] = turn;
              }
            }
          }
        }
        }else if(y == q){
        if(p == x-1){
          if(board[y][x-1] != turn && board[y][x-1] != space){
            while(board[q][p] != turn && board[q][p] != space)
              if(p-1 >= 0){
                p--;
              }else
                break;
            if(board[q][p] == turn){
              while(++p<=x-1){
                num++;
                board[q][p] = turn;
              }
            }
          }
        }else if(p== x)
          continue;
        else if(p == x+1){
          if(board[y][x+1] != turn && board[y][x+1] != space){
            while(board[q][p] != turn && board[q][p] != space)
              if(p+1 <= 7){
                p++;
              }else
                break;
            if(board[q][p] == turn){
              while(--p>=x+1){
                num++;
                board[q][p] = turn;
              }
            }
          }
        }
      }else if(q == y+1){
        if(p == x-1){
          if(board[y+1][x-1] != turn && board[y+1][x-1] != space){
            while(board[q][p] != turn && board[q][p] != space)
              if(q+1 <= 7 && p-1 >= 0){
                q++;
                p--;
              }else
                break;
            if(board[q][p] == turn){
              while(--q>=y+1 && ++p<=x-1){
                num++;
                board[q][p] = turn;
              }
            }
          }
        }else if(p == x){
           if(board[y+1][x] != turn && board[y+1][x] != space){
            while(board[q][p] != turn && board[q][p] != space)
              if(q+1 <= 7){
                q++;
              }else
                break;
            if(board[q][p] == turn){
              while(--q>=y+1){
                num++;
                board[q][p] = turn;
              }
            }
          }
        }else if(p == x+1)
          if(board[y+1][x+1] != turn && board[y+1][x+1] != space){
            while(board[q][p] != turn && board[q][p] != space)
              if(q+1 <= 7 && p+1 <= 7){
                q++;
                p++;
              }else
                break;
            if(board[q][p] == turn){
              while(--q>=y+1 && --p>=x+1){
                num++;
                board[q][p] = turn;
              }
            }
          }
      }
    }
  if(num)
    board[y][x] = turn;
      return num;
}

struct vectorっていうのでx,y座標を管理していたんですけど、必要性を感じなかったので使わないようにしました
てきとうなコマンドライン入力でCPUバトルができる機能は健在です

三種のAI部分

void CPU(enum type turn)
{
  enum type b[8][8];
  int c,i,j,max=0,v[8][8];
  for(j=0;j<8;j++)
    for(i=0;i<8;i++){
      copyboard(b,board);
      v[j][i] = ReverseStone(i,j,turn,b);
    }
  for(j=0;j<8;j++)
    for(i=0;i<8;i++)
      if(max < v[j][i])
        max = v[j][i];
  while(1){
  for(j=0;j<8;j++)
    for(i=0;i<8;i++){
      if(v[j][i] == max)
        if(rand() % 8 == 0){
          if(!(c = ReverseStone(i,j,turn,board)))
            printf("CPU : う～ん、パス！ｗ\n");
          ShowBoard();
          if(c)
            printf("CPU : Your Turn... !!! (with putting stone on (%d,%d)\n",i+1,j+1);

          return;
        }
    }
  }
}

void CPU_monkey(enum type turn)
{
  int x,y;
  while(!ReverseStone(x = rand()%8,y = rand()%8,turn,board));
  ShowBoard();
  printf("your turn(%d,%d)\n",x,y);
}

void CPU_fixed(enum type turn)
{
  enum type b[8][8],u[8][8],t=tend(turn);
  int vect[2][64],x,y,v;
  int sub[8][8];
  copyboard(b,board);
  int i,j,k,l,dep;
  for(j=0;j<8;j++)
    for(i=0;i<8;i++){
        vect[0][i+j*8] = ReverseStone(i,j,turn,b);
        copyboard(u,b);
        for(k=0;k<8;k++)
          for(l=0;l<8;l++){
            if(vect[1][l+k*8] = ReverseStone(l,k,t,u))
              copyboard(u,b);
          }
        sub[j][i] = vect[0][i+j*8] - maxv(vect[1]);
        copyboard(b,board);
    }
  v = maxxy(sub,vect[0],&x,&y);
  ReverseStone(x,y,turn,board);
  ShowBoard();
  printf("your turn(%d,%d)\n",x,y);
}

上のCPUは前と仕様を変えてないです。

CPU_monkeyというのは名前の通り猿です。
適当に盤に石を打ち、ルール上置くことができる場所におけるまで繰り返し適当に盤に石をうち続けるだけのAIです。期待値的には64回の計算で1回以上は打てるので、計算速度的にはあまり問題はなかったです。

CPU_fixedが一応今回の目玉です。
といっても、ミニマックス法を拙く実装しただけです...。
（自分がある場所に打ったときにひっくり返せる石の数）と、（その後に相手が打つときにひっくり返される石の数の最大値）　の差がもっとも大きいところに石を打つようにしています。評価する数値としてひっくり返せる石の数を採用したのですが、実際は石を打つことができる座標(x,y)自体を評価関数として比較することが多いみたいです。

CPU対戦の実行結果例(5000回の対戦を設定しました)

White Win = 3714
Black Win = 1286
Draw = 0
(White = CPU_fixed)
(black = CPU_monkey)

White Win = 3772
Black Win = 1228
Draw = 0
(White = CPU)
(black = CPU_monkey)

AIの強さはやはりという感じですが、CPU_monkeyでもそこそこ勝てるのは意外ですね