VodkaSoul 2017-12-23 12:33 采纳率: 100%
浏览 2088
已采纳

求助!关于棋类AI负极大值AlphaBeta搜索算法问题

如题,大一新生,C语言刚入门,期末项目用C语言编写一个黑白棋AI。
在CSDN上找到不少相关的文章,但是发现用C编写的很少,并且由于刚接触编程,对哈希置换表等高级数据表示方式还难以理解运用。

根据陈小春《PC游戏编程》一书给出的伪代码:

   int  alphabeta(int nPlay,int alpha,int beta)
  {
      if(Game over)
              return eval();   //胜负已分,返回估值
      if(nPlay <=0)
            return eval();   //叶子节点返回估值

     for(each possible move m)   //对每一可能的走法
     {
          make move m;   //产生子节点
          //递归搜索子节点
          score=-alphabeta(nPly-1,-beta,-alpah)
          unmake move m;  //撤销搜索过的子节点
           if(score >= alpha)
                alpha=score;    //保存最大值
           if(alpha>=beta)
                 break;  //beta剪枝
          }
       return alpah;   //返回极大值
   }

改写成:

 int NegaMax(const char map[][SIZE], int row, int col, int side, int depth, int alpha, int beta) {  //负极大值风格AlphaBeta搜索算法
    char mapnow[SIZE][SIZE];
    memcpy(mapnow, map, sizeof(char)*SIZE*SIZE);   //复制棋盘(map是一个全局数组)
    reversi(mapnow, row, col, side);               //模拟落子翻转(黑白棋落子后翻转对方的子)
    if (depth == 0)  //叶子节点
        return evaluation(mapnow, row, col, side);        //evaluation为估值函数,对当前棋面作出估值判断
    if (isGameOver(map, depth))                           //棋局结束返回胜负
        return (Dpieces(map, side) > 0) ? 1 : -1;         //Dpieces为计算双方棋子数之差的函数
    int NowSide = reverse(side);                          //交换下棋方(比如己方为1,对方就为2)
    for (int r = 0; r < SIZE; r++)
        for (int c = 0; c < SIZE; c++)
            if (isValid(mapnow, r, c, NowSide)) {   //遍历棋盘找到可落子点(isValid函数用于判断该点能否落子)
                int score = -NegaMax(mapnow, r, c, NowSide, depth - 1, -beta, -alpha);
                if (score >= alpha)
                    alpha = score;            //找到负极大值
                if (alpha >= beta) break;
            }
    return alpha;                       //返回负极大值
}

引用部分:

 void turn(int side) {    //落子
    cnt_pieces++;
    int row, col, max_value = INT_MIN, max_row, max_col;
    for (row = 0; row < SIZE; row++)
        for (col = 0; col < SIZE; col++)
            if (isValid(map, row, col, side) && NegaMax(map, row, col, side, MaxDepth, INT_MIN, INT_MAX) > max_value) {
                max_value = NegaMax(map, row, col, side, MaxDepth, INT_MIN, INT_MAX);
                max_row = row;
                max_col = col;
            }
    printf("%d %d\n", max_row, max_col);   //用stdout来输出判断
    fflush(stdout);
    reversi(map, max_row, max_col, side);
    }

但是发现最终落子点并不理想,故请教是否这个搜索算法的写法存在问题。

//问题补充
1、不太懂那个AlphaBeta剪枝if(alpha>=beta)break;的逻辑。
由于存在两个for循环,所以我想写两个break,
但假如改写成:

    for (int r = 0; r < SIZE; r++)
    {
        for (int c = 0; c < SIZE; c++)
            if (isValid(mapnow, r, c, NowSide)) {   //遍历棋盘找到可落子点(isValid函数用于判断该点能否落子)
                int score = -NegaMax(mapnow, r, c, NowSide, depth - 1, -beta, -alpha);
                if (score >= alpha)
                    alpha = score;            //找到负极大值
                if (alpha >= beta) break;
            }
        if (alpha >= beta)break;
    }

那么这个递归函数就完全没有用了。

  • 写回答

2条回答

  • 瓦史托德 2017-12-25 01:42
    关注

    以前也写过这个手机五子棋 c/c++的这个还是最简单的了 其他的源码都看不大懂(程序员联合开发网应该蛮多) 最后还是找了个java的应付过去了 不过java的剪的比较多 不然大于3层基本跑不动

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决