/*
 * 使用鍵盤的上下左右鍵移動(dòng)棋盤，空格鍵表示下棋，ESC鍵退出程序
 */
#include <stdio.h>
#include <stdlib.h>
#include <bios.h>
#include <graphics.h>
#include<malloc.h>
/*
 * 對(duì)應(yīng)鍵盤鍵的十六進(jìn)制數(shù)字
 */
#define ESC 0x11b
#define UP 0x4800
#define DOWN 0x5000
#define LEFT 0x4b00
#define RIGHT 0x4d00
#define BLANK 0x3920

#define PLAYER1 1
#define PLAYER2 2
#define COMPUTER 2
#define LENGTH 15
#define SEARCH_DEEP 2
/*
 * 用來(lái)在函數(shù)can_expand()查找可以擴(kuò)展的節(jié)點(diǎn)步長(zhǎng)
 */
#define STEP 1

/************全局變量定義***************/
int       x1 = 240,
        y1 = 240,
        oldx = 240,
        oldy = 240;
int       key_mode;
int       key_net;
int       step_sum = 0;
int       chessman[LENGTH][LENGTH];
int       depth = 2; /* 搜索的深度 */
int       a = 0,
        b = 0;
int       flag_run;
int       win_flag = 0;


typedef struct five_chess *point;
struct five_chess {
  int       x;
  int       y;
  int       layer;
  double     value;
  double     score;
  int       chess[LENGTH][LENGTH];
  int       record[LENGTH][LENGTH];
} A;

int       stack_deep0 = 0;
point      stack_c[10];
point      close[600];

void
push(point s0)
{
  if (stack_deep0 < 10)
 stack_c[stack_deep0++] = s0;
}

point
top()
{
  if (stack_deep0 > 0)
 return stack_c[stack_deep0 - 1];
  /*else return 一個(gè)什么樣的東西?*/
}

void
pop()
{
  if (stack_deep0 > 0)
 stack_deep0--;
}

int
is_empty()
{
  if (stack_deep0 != 0)
 return 1;
  else
 return 0;
}

 

/************函數(shù)的聲明**************/
void      five();
void      show();
int       win_or_not(int x0, int y0, int who,
   int chessman[LENGTH][LENGTH], int a);
void      set_chessman();
void      print_result();
/************評(píng)價(jià)函數(shù)部分************/
double     score_row(int i, int j, int chessman[LENGTH][LENGTH]);
double     score_col(int i, int j, int chessman[LENGTH][LENGTH]);
double     score_diag_45(int i, int j, int chessman[LENGTH][LENGTH]);
double     score_diag_135(int i, int j, int chessman[LENGTH][LENGTH]);
double     total_score(int who_running, int chessman[LENGTH][LENGTH]);
double     score(int chessman[LENGTH][LENGTH]);
int       rowdt(int i, int j, int chessman[LENGTH][LENGTH]);
int       coldt(int i, int j, int chessman[LENGTH][LENGTH]);
int       diadt(int i, int j, int chessman[LENGTH][LENGTH]);
int       vdiadt(int i, int j, int chessman[LENGTH][LENGTH]);
int       can_expand(int i, int j, int chessman[LENGTH][LENGTH]);
void     copy(point s1, point s0);

int
POW(int s, int t)
{
  int       sum = s,
          i;
  if (t <= 0)
 return 1;
  for (i = 0; i < t; i++)
 sum *= sum;
  return sum;

}


/*
 * 定義computer先手
 */
point
expand(point s0)
{
  int       flag;
  int       i,
          j;
  point      new_chess = (point) malloc(sizeof(struct five_chess));
/*************************這里出錯(cuò)***********************************/
  for (i = 0; i < LENGTH; i++)
 for (j = 0; j < LENGTH; j++)
   new_chess->chess[i][j] = s0->chess[i][j];

  for (i = 0; i < LENGTH; i++)
 for (j = 0; j < LENGTH; j++)
   new_chess->record[i][j] = s0->chess[i][j];

/*************************這里出錯(cuò)***********************************/
  if (s0->layer % 2 == 0)
 flag = COMPUTER;
  else
 flag = PLAYER1;


  for (i = 0; i < LENGTH; i++)
 for (j = 0; j < LENGTH; j++) {

   if (s0->record[i][j])             /*如果有棋子*/
 continue;
   if (can_expand(i, j, s0->chess) == 0)  /*如果有棋子，而且沿水平，樹(shù)直，左上—右下，右上—左下，四個(gè)方向可以擴(kuò)展*/
 continue;
   s0->record[i][j] = flag;
   new_chess->chess[i][j] = flag;
   new_chess->layer = s0->layer + 1;
   new_chess->x = i;
   new_chess->y = j;
   new_chess->record[i][j] = flag;
   return new_chess;
 }
  /*
   * for(i=5;i<10;i++) for(j=5;j<10;j++){ if(s0->record[i][j]) continue;
   * if(can_expand(i,j,s0->chess)==0) continue; s0->record[i][j]=flag;
   * new_chess->x=i; new_chess->y=j; new_chess->record[i][j]=flag;
   * new_chess->layer=s0->layer+1; new_chess->chess[i][j]=flag ; return
   * new_chess; } for(i=2;i<12;i++) for(j=2;j<12;j++){
   * if(i>4&&i<10&&j>4&&j<10) continue; if(s0->record[i][j]) continue;
   * if(can_expand(i,j,s0->chess)==0) continue; s0->record[i][j]=flag;
   * new_chess->x=i; new_chess->y=j; new_chess->record[i][j]=flag;
   * new_chess->layer=s0->layer+1; new_chess->chess[i][j]=flag; return
   * new_chess;
   * 
   * } for(i=0;i<LENGTH;i++) for(j=0;j<LENGTH;j++){
   * if(i>1&&i<12&&j>1&&j<12) continue; if(s0->record[i][j]) continue;
   * if(can_expand(i,j,s0->chess)==0) continue; s0->record[i][j]=flag;
   * new_chess->chess[i][j]=flag; new_chess->layer=s0->layer+1;
   * new_chess->x=i; new_chess->y=j; new_chess->record[i][j]=flag; return 
   * new_chess; } 
   */
  new_chess->layer = -1;
  return new_chess;
}

 

void
computer()
{
  int       i,
          j,
          k,
          num = 0;
  int       break_now = 0;
  int       break_then = 0;
  int       go_on = 0;
  point     s0 = NULL,
          s1 = NULL,
          s2 = NULL,
          max_chess = NULL;
  point     temps = NULL,
          s01;
  /*
   * 堆棧的初始化
   */
  stack_deep0 = 0;
  s0 = malloc(sizeof(struct five_chess));
  for (i = 0; i < 600; i++)              /*為什么是600*/
 close[i] = NULL;                 /*close是一個(gè)point 數(shù)組*/
  close[num++] = s0;
  for (i = 0; i < LENGTH; i++)
 for (j = 0; j < LENGTH; j++) {
   s0->chess[i][j] = chessman[i][j];
   s0->record[i][j] = chessman[i][j];
 }
  s0->layer = 0;
  s0->value = -3000000;
  s0->score = -3000000;
  push(s0);
  while (is_empty() != 0) {        /*看是棧否為空*/
 s01 = top();                  /*如果不是空*/
 s1 = expand(s01);             /*從棧頂開(kāi)始展開(kāi)*/
 close[num++] = s1;
 if (s1->layer == -1) {
   pop();
   continue;
 }
 go_on =
   win_or_not((s1->x + 1) * 30, (s1->y + 1) * 30, 2, s1->chess,
     1);
 if (go_on == 2) {
   a = (s1->x + 1) * 30;
   b = (s1->y + 1) * 30;
   break_then = 1;
   break;
 }
 go_on =
   win_or_not((s1->x + 1) * 30, (s1->y + 1) * 30, 1, s1->chess,
     1);
 if (go_on == 1) {
   a = (s1->x + 1) * 30;
   b = (s1->y + 1) * 30;
   break_then = 1;
   break;
 }
 s1->value = 30000;
 push(s1);
 while (1) {
   s1 = top();
   s2 = expand(s1);
   if (s2->layer == -1) {
 pop();
 if (s1->value > top()->value) {
   top()->value = s1->value;
   max_chess = s1;
 }
 free(s2);
 break;
   }/*end of if*/
   s2->score = score(s2->chess);
   temps = top();
   if (s2->score < temps->value)
 temps->value = s2->score;
   free(s2);
 }/*end of whiile(1) */
  }
  if (break_then == 0) {
 for (i = 0; i < LENGTH; i++) {
   for (j = 0; j < LENGTH; j++)
 if (max_chess->chess[i][j] != chessman[i][j]) {
   a = i * 30 + 30;
   b = j * 30 + 30;
   break_now = 1;
   break;
 }
   if (break_now == 1)
 break;
 }
  }
  for (i = 0; i < 600; i++) {
 if (close[i] == NULL)
   continue;
 free(close[i]);
  }

}

/**********************************************************/
void
main()
{
  int       key;
  int       play_with_who = 1;

  printf("1.Play with human\n2.Play with computer\nPlease choice: ");
  scanf("%d", &play_with_who);
 
  five();              /*顯示棋盤*/
  show();

  if (play_with_who == 1) {   /*人與人玩*/
 while (1) {  /*設(shè)置人與人玩的界面*/
   settextstyle(0, 0, 2);
   if ((step_sum + 1) % 2) {
 setcolor(1);
 outtextxy(500, 180, "Player2");
 setcolor(4);
 outtextxy(500, 180, "Player1");
   } else {
 setcolor(1);
 outtextxy(500, 180, "Player1");
 setcolor(10);
 outtextxy(500, 180, "Player2");
   }


   if (bioskey(1))
 /*
  * 按了一次鍵盤那么就true，執(zhí)行下面代碼，這是bios。h
  */
   {
 key = bioskey(0);
 /*
  * 返回一個(gè)鍵盤值，如沒(méi)有按鍵，則一直等待
  */
 switch (key) {
 case ESC:
   exit(0);
 case LEFT:
   if (x1 > 30) {
  x1 -= 30;
  show();   /*顯示方框*/
   }
   break;
 case UP:
   if (y1 > 30) {
  y1 -= 30;
  show();
   }
   break;
 case RIGHT:
   if (x1 < 450) {
  x1 += 30;
  show();
   }
   break;
 case DOWN:
   if (y1 < 450) {
  y1 += 30;
  show();
   }
   break;
 case BLANK:         /*按下空格鍵后放置棋子*/
   {
  if (chessman[x1 / 30][y1 / 30])
    break;       /*如果當(dāng)前位置有棋子，不能放置，退出*/
  step_sum++;    /*如果沒(méi)有棋子，下一步誰(shuí)走加1*/
  /*
  * P1 設(shè)置棋子
  */
  if (step_sum % 2) {
    setcolor(15);  /*畫(huà)棋子*/
    setfillstyle(SOLID_FILL, 15); /* 封閉圖形，進(jìn)行實(shí)體填充*/
    circle(x1, y1, 10);      /*畫(huà)圓*/
    floodfill(x1, y1, 15);    /*填充圓*/
    chessman[x1 / 30][y1 / 30] = PLAYER1;        /*設(shè)置棋盤狀態(tài)*/
    win_flag = win_or_not(x1, y1, 1, chessman, 0);   /*分析游戲是否結(jié)束,誰(shuí)勝誰(shuí)敗*/
    if (win_flag == 1)
  outtextxy(480, 240, "P1 Win");
    else if (win_flag == 3)
  outtextxy(480, 240, "DOGFALL");
    if (win_flag != 0) {           /*如果沒(méi)人勝，游戲繼續(xù)*/
  while (bioskey(1) == 0);
  closegraph();            /*what this mean?*/
    }
  } else { /* P2 設(shè)置棋子 */

    setcolor(12);            
    setfillstyle(SOLID_FILL, 12);
    circle(x1, y1, 10);
    floodfill(x1, y1, 12);
    chessman[x1 / 30][y1 / 30] = PLAYER2;
    win_flag = win_or_not(x1, y1, 2, chessman, 0);
    if (win_flag == 2)
  outtextxy(480, 240, "P2 Win");
    else if (win_flag == 3)
  outtextxy(480, 240, "DOGFALL");
    if (win_flag != 0) {
  while (bioskey(1) == 0);
  closegraph();
    }
  }

 

   }
   break;
 }
   }
 }
  } else {
 chessman[7][7] = COMPUTER;       /*人和電腦玩,電腦先走一步*/      
 setcolor(12);
 setfillstyle(SOLID_FILL, 12);
 circle(240, 240, 10);
 floodfill(240, 240, 12);
 flag_run = 0;          /*有什么用?*/
 step_sum++;          /*下一步誰(shuí)走？*/
 while (1) {
   while (1) {
 if (flag_run == 1)
   break;
 if (bioskey(1)) {
   key = bioskey(0);
   /*
    * 返回一個(gè)鍵盤值，如沒(méi)有按鍵，則一直等待
    */
   switch (key) {

   case ESC:
  exit(0);
   case LEFT:
  if (x1 > 30) {
    x1 -= 30;
    show();
  }
  break;
   case UP:
  if (y1 > 30) {
    y1 -= 30;
    show();
  }
  break;
   case RIGHT:
  if (x1 < 450) {
    x1 += 30;
    show();
  }
  break;
   case DOWN:
  if (y1 < 450) {
    y1 += 30;
    show();
  }
  break;
   case BLANK:
  {
    if (chessman[x1 / 30 - 1][y1 / 30 - 1])
  break;                             /*有棋子了不走*/

    setcolor(15);
    setfillstyle(SOLID_FILL, 15); /* 封閉圖形，進(jìn)行實(shí)體填充 
     */
    circle(x1, y1, 10);
    floodfill(x1, y1, 15);               /*畫(huà)棋子*/
    chessman[x1 / 30 - 1][y1 / 30 - 1] = PLAYER1;

    flag_run = 1;                 /*有什么用?*/
    step_sum++;                 /*下一步誰(shuí)走*/
    win_flag = win_or_not(x1, y1, 1, chessman, 0);  /*誰(shuí)勝誰(shuí)負(fù)*/
    if (win_flag == 1)
  outtextxy(480, 240, "P1 Win");
    else if (win_flag == 3)
  outtextxy(480, 240, "DOGFALL");
    if (win_flag != 0) {
  while (bioskey(1) == 0);                 /*沒(méi)有人勝則繼續(xù)等待下棋*/
  closegraph();
    }

  }
   } /* switch */

 }

   }
   computer();                      /*調(diào)用智能體*/
   /*
   * a,b存放的是現(xiàn)在電腦準(zhǔn)備下的位置
   * 返回一個(gè)a,b的結(jié)構(gòu)體不是更好，用全局變量不爽啊
   * struct {
   *     int a;
   *     int b;
   * }
   */

   setcolor(12);
   setfillstyle(SOLID_FILL, 12);
   circle(a, b, 10);
   floodfill(a, b, 12);
   chessman[a / 30 - 1][b / 30 - 1] = COMPUTER;
   flag_run = 0;
   step_sum++;
   win_flag = win_or_not(a, b, 2, chessman, 0);
   if (win_flag == 2)
 outtextxy(480, 240, "ComputerWin");
   else if (win_flag == 3)
 outtextxy(480, 240, "DOGFALL");
   if (win_flag != 0) {
 while (bioskey(1) == 0);
 closegraph();
   }

 

 

 }
  }

}
void
five()
{
  int       i,
          j;
  /*
   * 畫(huà)棋盤的過(guò)程
   */
  int       gdriver = DETECT,
          gmode;
  registerbgidriver(EGAVGA_driver);
  initgraph(&gdriver, &gmode, " ");
  /*
   * 對(duì)顯示適配器進(jìn)行配置
   */
  setbkcolor(1);

  for (i = 0; i < 30; i++) {
 setcolor((i >= 2) ? 9 : i);
 rectangle(i, i, 479 - i, 479 - i); /* 畫(huà)矩形邊框 */
  }
  /*
   * 畫(huà)棋盤
   */
  for (i = 1; i < 14; i++)
 for (j = 1; j < 14; j++) {
   setcolor(14);
   line(30 + 30 * i, 30, 30 + 30 * i, 449);
   line(30, 30 + 30 * i, 449, 30 + 30 * i);
 }
  /*
   * 畫(huà)整個(gè)圖的邊框
   */
  for (i = 0; i < 15; i++) {
 setcolor(i);
 rectangle(i, i, 640 - i, 480 - i);
 line(480 - i, 15, 480 - i, 465);
  }
  /*
   * 輸出屏幕右側(cè)的信息
   */
  setcolor(4);
  settextstyle(0, 0, 2);
  outtextxy(500, 45, "GOBANG");
  setcolor(10);
  settextstyle(0, 0, 1);
  outtextxy(500, 90, "Designed By");
  outtextxy(514, 118, "Ye Binbin");
  outtextxy(480, 140, "from class A of CS");


}

/*
 * 移動(dòng)光標(biāo)
 */
void
show()
{
  setcolor(1);

  if (oldx < 450) {
 if (oldy > 30)
   line(oldx + 7, oldy - 15, oldx + 15, oldy - 15);
 if (oldy > 30)
   line(oldx + 15, oldy - 15, oldx + 15, oldy - 7);
 if (oldy < 450)
   line(oldx + 15, oldy + 7, oldx + 15, oldy + 15);
 if (oldy < 450)
   line(oldx + 15, oldy + 15, oldx + 7, oldy + 15);
  }
  if (oldx > 30) {
 if (oldy < 450)
   line(oldx - 7, oldy + 15, oldx - 15, oldy + 15);
 if (oldy < 450)
   line(oldx - 15, oldy + 15, oldx - 15, oldy + 7);
 if (oldy > 30)
   line(oldx - 15, oldy - 7, oldx - 15, oldy - 15);
 if (oldy > 30)
   line(oldx - 15, oldy - 15, oldx - 7, oldy - 15);
  }
  setcolor(12);
  if (x1 < 450) {
 if (y1 > 30)
   line(x1 + 7, y1 - 15, x1 + 15, y1 - 15);
 if (y1 > 30)
   line(x1 + 15, y1 - 15, x1 + 15, y1 - 7);
 if (y1 < 450)
   line(x1 + 15, y1 + 7, x1 + 15, y1 + 15);
 if (y1 < 450)
   line(x1 + 15, y1 + 15, x1 + 7, y1 + 15);
  }

  if (x1 > 30) {
 if (y1 < 450)
   line(x1 - 7, y1 + 15, x1 - 15, y1 + 15);
 if (y1 < 450)
   line(x1 - 15, y1 + 15, x1 - 15, y1 + 7);
 if (y1 > 30)
   line(x1 - 15, y1 - 7, x1 - 15, y1 - 15);
 if (y1 > 30)
   line(x1 - 15, y1 - 15, x1 - 7, y1 - 15);
  }
  oldx = x1;
  oldy = y1;

}

 

void
set_chessman()
{
  /*
   * 棋子有三種狀態(tài)，0是未初始狀態(tài)，1是控制方棋子，2是對(duì)方棋子 
   */
  int       i,
          j;
  for (i = 0; i < 15; i++)
 for (j = 0; j < 15; j++)
   chessman[i][j] = 0;
}


/*
 * 0表示沒(méi)有贏，1表示p1勝利，2表示p2勝利，3表示平局
 */
int
win_or_not(int x0, int y0, int who, int chessman[LENGTH][LENGTH], int a)
{
  int       i = x0 / 30 - 1,
          j = y0 / 30 - 1;
  int       who_run = who;
  int       line_sum = -1;
  int       tmp_i = i,
          tmp_j = j;
  int       c;
  if (a == 1) {
 /*
 * 測(cè)試第一層擴(kuò)展是否滿足贏的條件
 */
 c = chessman[i][j];
 chessman[i][j] = who_run;
  }


  while (1) {  /* 查找共行的棋子是否連接了五個(gè) */
 while (tmp_i >= 0 && line_sum != 4) {
   if (chessman[tmp_i--][j] == who_run)
 line_sum++;
   else
 break;
 }
 if (line_sum == 4)
   line_sum++;
 tmp_i = i;
 while (tmp_i <= 15 && line_sum != 5) {
   if (chessman[tmp_i++][j] == who_run)
 line_sum++;
   else
 break;
 }
 if (line_sum == 5) {
   if (a == 1)
 chessman[i][j] = c;
   return who_run;
 }
 line_sum = -1;
 tmp_i = i;
 break;

  }
  while (1) {  /* 查找共列的棋子是否連接了五個(gè) */
 while (tmp_j >= 0 && line_sum != 4) {
   if (chessman[i][tmp_j--] == who_run)
 line_sum++;
   else
 break;
 }
 if (line_sum == 4)
   line_sum++;
 tmp_j = j;
 while (tmp_j <= 15 && line_sum != 5) {
   if (chessman[i][tmp_j++] == who_run)
 line_sum++;
   else
 break;
 }
 if (line_sum == 5) {
   if (a == 1)
 chessman[i][j] = c;
   return who_run;
 }
 line_sum = -1;
 tmp_j = j;
 break;

  }
  while (1) {  /* 查找上對(duì)角線上是否連接了五個(gè) */
 while (line_sum != 4 && tmp_i <= 15 && tmp_j >= 0) {
   if (chessman[tmp_i++][tmp_j--] == who_run)
 line_sum++;
   else
 break;
 }
 tmp_i = i;
 tmp_j = j;
 if (line_sum == 4)
   line_sum++;
 while (line_sum != 5 && tmp_i >= 0 && tmp_j <= 15) {
   if (chessman[tmp_i--][tmp_j++] == who_run)
 line_sum++;
   else
 break;
 }
 if (line_sum == 5) {
   if (a == 1)
 chessman[i][j] = c;
   return who_run;
 }
 tmp_i = i;
 tmp_j = j;
 line_sum = -1;
 break;
  }
  while (1) {  /* 查找下對(duì)角線上是否連接了五個(gè) */
 while (line_sum != 4 && tmp_i >= 0 && tmp_j >= 0) {
   if (chessman[tmp_i--][tmp_j--] == who_run)
 line_sum++;
   else
 break;
 }
 tmp_i = i;
 tmp_j = j;
 if (line_sum == 4)
   line_sum++;
 while (line_sum != 5 && tmp_i <= 15 && tmp_j <= 15) {
   if (chessman[tmp_i++][tmp_j++] == who_run)
 line_sum++;
   else
 break;
 }
 if (line_sum == 5) {
   if (a == 1)
 chessman[i][j] = c;
   return who_run;
 }
 break;
  }
  if (step_sum == 225) {
 if (a == 1)
   chessman[i][j] = c;
 return 3;
  }
  if (a == 1)
 chessman[i][j] = c;
  return 0;

}

 

double
score_row(int i, int j, int chessman[LENGTH][LENGTH])
{
  int       sum_chessmen = 0;
  double     score = 0;
  int       mid_j;
  int       who_running = chessman[i][j];
  if (j == LENGTH) {
 while (chessman[i][j] == who_running) {
   j--;
   sum_chessmen++;
 }
 if (sum_chessmen >= 5)
   score = 200000;
 else {
   if (chessman[i][j] == 0) /* 沒(méi)有下子,活的情況 */
 score = 2000 / POW(10, 4 - sum_chessmen);
   else
 score = 0; /* 死的情況 */
 }
  } else {
 while (chessman[i][j] == who_running && j != LENGTH) {
   j++;
   sum_chessmen++;
 }
 mid_j = j;
 j = j - sum_chessmen - 1;
 while (chessman[i][j] == who_running && j != -1) {
   j--;
   sum_chessmen++;
 }
 if (j >= 0 && mid_j < LENGTH) {
   if (chessman[i][j] == 0 && chessman[i][mid_j] == 0)
 score = 18000 / POW(50, 4 - sum_chessmen);
   else if ((chessman[i][j] != 0 && chessman[i][mid_j] == 0)
    || (chessman[i][j] == 0 && chessman[i][mid_j] != 0))
 score = 2000 / POW(10, 4 - sum_chessmen);
   else
 score = 0;
 }
 if (j < 0 && mid_j < LENGTH) {
   if (chessman[i][mid_j] == 0)
 score = 2000 / POW(10, 4 - sum_chessmen);
   else
 score = 0;
 }
 if (j >= 0 && mid_j >= LENGTH) {
   if (chessman[i][j] == 0)
 score = 2000 / POW(10, 4 - sum_chessmen);
   else
 score = 0;
 }
 if (j < 0 && mid_j >= LENGTH)
   score = 0;
  }
  return score;
}

double
score_col(int i, int j, int chessman[LENGTH][LENGTH])
{
  int       sum_chessmen = 0,
          mid_i;
  double     score = 0;
  int       who_running = chessman[i][j];
  if (i == LENGTH) {
 while (chessman[i][j] == who_running) {
   i--;
   sum_chessmen++;
 }
 if (sum_chessmen >= 5)
   score = 200000;
 if (chessman[i][j] == 0)
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
  } else {
 while (chessman[i][j] == who_running) {
   i++;
   sum_chessmen++;
 }
 mid_i = i;
 if (i == LENGTH || chessman[i][j] != who_running) {
   i = i - sum_chessmen;
   while (chessman[i - 1][j] == who_running) {
 i--;
 sum_chessmen++;
   }
   if (i >= 0) {
 if (chessman[i][j] == 0 && chessman[mid_i][j] == 0)
   score = 18000 / POW(50, 4 - sum_chessmen);
 else if ((chessman[i][j] != 0 && chessman[mid_i][j]) == 0
  || (chessman[i][j] == 0
    && chessman[mid_i][j] != 0))
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   }
   if (i < 0 && mid_i < LENGTH) {
 if (chessman[mid_i][j] == 0)
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   }
   if (i < 0 && mid_i < LENGTH) {
 if (chessman[mid_i][j] == 0)
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   }
   if (i >= 0 && mid_i >= LENGTH) {
 if (chessman[i][j] == 0)
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   }
 }
  }
  return score;
}

double
score_diag_45(int i, int j, int chessman[LENGTH][LENGTH])
{
  int       sum_chessmen = 0;
  double     score = 0;
  int       mid_i,
          mid_j;
  int       who_running = chessman[i][j];
  if (i == LENGTH || j == LENGTH) {
 while (chessman[i][j] == who_running && i > 1 && j > 1) {
   i--;
   j--;
   sum_chessmen++;
 }
 if (sum_chessmen >= 5)
   score = 200000;
 else {
   if (chessman[i][j] == 0)
 score = 2000 / POW(10, 4 - sum_chessmen);
   else
 score = 0;
 }
  } else {
 while (chessman[i][j] == who_running && i <= LENGTH && j <= LENGTH) {
   i++;
   j++;
   sum_chessmen++;
 }
 mid_i = i;
 mid_j = j;
 i = i - sum_chessmen;
 j = j - sum_chessmen;
 while (chessman[i - 1][j - 1] == who_running) {
   i--;
   j--;
   sum_chessmen++;
 }
 if (sum_chessmen >= 5)
   score = 200000;
 if (i >= 0 && j >= 0 && mid_i < LENGTH && mid_j < LENGTH) {
   if (chessman[mid_i][mid_j] == 0 && chessman[i][j] == 0)
 score = 18000 / POW(50, 4 - sum_chessmen);
   else if ((chessman[mid_i][mid_j] == 0 && chessman[i][j] != 0)
    || (chessman[mid_i][mid_j] != 0
  && chessman[i][j] == 0))
 score = 2000 / POW(10, 4 - sum_chessmen);
   else
 score = 0;
 } else {
   if (i >= 0 && j >= 0) {
 if (chessman[i][j] == 0)
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   } else if (mid_i < LENGTH && mid_j < LENGTH) {
 if (chessman[mid_i][mid_j] == 0)
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   } else
 score = 0;
 }
  }
  return score;
}

double
score_diag_135(int i, int j, int chessman[LENGTH][LENGTH])
{
  int       sum_chessmen = 0;
  double     score = 0;
  int       mid_i,
          mid_j;
  int       who_running = chessman[i][j];
  while (chessman[i][j] == who_running && j != -1 && i < LENGTH) {
 i++;
 j--;
 sum_chessmen++;
  }
  mid_i = i;
  mid_j = j;
  j += sum_chessmen;
  i -= sum_chessmen;
  j++;
  i--;
  while (chessman[i][j] == who_running && j != LENGTH) {
 i--;
 j++;
 sum_chessmen++;
  }
  if (sum_chessmen >= 5)
 score = 200000;
  else {
 if (i >= 0 && j < LENGTH && mid_j >= 0 && mid_i < LENGTH) {
   if (chessman[i][j] == 0 && chessman[mid_i][mid_j] == 0)
 score = 18000 / POW(50, 4 - sum_chessmen);
   else {
 if ((chessman[i][j] == 0 && chessman[mid_i][mid_j] != 0)
   || (chessman[i][j] != 0
  && chessman[mid_i][mid_j] == 0))
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   }
 } else {
   if (i >= 0 && j < LENGTH) {
 if (chessman[i][j] == 0)
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   }
   if (mid_j >= 0 && mid_i < LENGTH) {
 if (chessman[mid_i][mid_j] == 0)
   score = 2000 / POW(10, 4 - sum_chessmen);
 else
   score = 0;
   }
 }
  }
  return score;
}

double
total_score(int who_running, int chessman[LENGTH][LENGTH])
{
  /*
   * 統(tǒng)計(jì)出在該點(diǎn)上的得分,who_running=1表示人的棋子,2為電腦的棋子
   */
  int       i,
          j;
  double     score = 0;
  for (i = 0; i < LENGTH; i++)
 for (j = 0; j < LENGTH; j++) {
   if (chessman[i][j] == who_running) {
 score += score_row(i, j, chessman);
 score += score_col(i, j, chessman);
 score += score_diag_45(i, j, chessman);
 score += score_diag_135(i, j, chessman);
   }
 }
  return score;
}

double
score(int chessman[LENGTH][LENGTH])
{
  /*
   * 計(jì)算最終的得分?jǐn)?shù),分別考慮了在這個(gè)位置放對(duì)方棋子跟自己棋子的綜合
   */
  double     sum1,
            sum2;
  sum1 = total_score(COMPUTER, chessman);
  sum2 = total_score(PLAYER1, chessman);
  return sum1 - sum2;
}

/*
 * 擴(kuò)展-----剪枝過(guò)程
 */

int
rowdt(int i, int j, int chessman[LENGTH][LENGTH])  /*在樹(shù)直方向*/
{
  int       k;
  int       midjl = j - STEP,         /*當(dāng)前棋子的上方*/
          midjr = j + STEP + 1;     /*當(dāng)前棋子的下方棋子的下方??????*/
  if (midjl < 0)                   
 midjl = 0;          
  if (midjr > LENGTH)
 midjr = LENGTH;
  for (k = midjl; k < midjr; k++)       /**/ 
 if (chessman[i][k] != 0)         /*如果有棋子*/
   return 1;
  return 0;
}

int
coldt(int i, int j, int chessman[LENGTH][LENGTH])     /*水平方向*/
{
  int       k;
  int       midil = i + STEP + 1,         /*當(dāng)前的右邊棋子的右一個(gè)*/
          midiu = i - STEP;            /*當(dāng)前棋子的左一個(gè)*/
  if (midiu < 0)
 midiu = 0;
  if (midil > LENGTH)
 midil = LENGTH;
  for (k = midiu; k < midil; k++)
 if (chessman[k][j] != 0)
   return 1;
  return 0;
}

int
diadt(int i, int j, int chessman[LENGTH][LENGTH])   /*右上到左下方向*/
{
  int       k,
          midi,
          midj;
  midi = i;
  midj = j;
  for (k = 0; k < STEP; k++) {
 midi++;
 midj--;
 if (midj < 0 || midi >= LENGTH)
   break;
 if (chessman[midi][midj] != 0)
   return 1;
  }
  for (k = 0; k < STEP; k++) {
 i--;
 j++;
 if (i < 0 || j >= LENGTH)
   break;
 if (chessman[i][j] != 0)
   return 1;
  }
  return 0;
}

int
vdiadt(int i, int j, int chessman[LENGTH][LENGTH])  /*左上到右下方向*/
{
  int       k,
          midi,
          midj;
  midi = i;
  midj = j;
  for (k = 0; k < STEP; k++) {
 midi--;
 midj--;
 if (midi < 0 || midj < 0)
   break;
 if (chessman[midi][midj] != 0)
   return 1;
  }
  for (k = 0; k < STEP; k++) {
 i++;
 j++;
 if (j >= LENGTH || i >= LENGTH)
   break;
 if (chessman[i][j] != 0)
   return 1;
  }
  return 0;
}


int
can_expand(int i, int j, int chessman[LENGTH][LENGTH])
{
  if (rowdt(i, j, chessman))
 return 1;
  if (coldt(i, j, chessman))
 return 1;
  if (diadt(i, j, chessman))
 return 1;
  if (vdiadt(i, j, chessman))
 return 1;
  /*
   * 如果不能擴(kuò)展,返回0
   */
  return 0;
}

/************************************************************/