VodkaSoul
VodkaSoul
采纳率100%
2017-12-23 12:33

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

80
已采纳

如题,大一新生,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条回答

  • u014794644 瓦史托德 4年前

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

    点赞 评论 复制链接分享
  • dabocaiqq dabocaiqq 4年前

    用调试的工具调试下看看是不是哪里错了呢。

    点赞 评论 复制链接分享