如题,大一新生,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;
}
那么这个递归函数就完全没有用了。