C++编写四子棋Minimax算法陷入无限循环问题求助

问题根源 #

1. Minimax函数缺少深度为0的终止判断：当前仅当游戏出现胜负或平局时才会终止递归，若设置的搜索深度小于最大可能落子数，深度降到0后没有对应返回逻辑，会继续递归导致depth变为负数，永远无法触发终止条件，最终进入无限递归。
2. bestMove函数调用Minimax时maxim参数传值错误：在bestMove中完成AI落子后，接下来轮到人类玩家（最小化层）走棋，此时调用Minimax的第三个参数应传false，原代码传的是true，导致后续递归一直执行最大化层逻辑，AI连续落子，走棋顺序完全错乱，递归深度远超预期。

修复方案 #

1. 新增深度耗尽终止条件 #

在Minimax函数的终止判断处，增加depth == 0的判断，深度耗尽时直接返回当前局面估值：

pair<bool, char> result = isWinner(grid, aiMark, hMark);
// 新增深度为0的终止判断
if (depth == 0 || result.first != false) { 
    if(result.second == aiMark) { //最大化玩家获胜
        return depth;
    } else if (result.second == hMark) { //最大化玩家落败
        return -depth;
    } else { //平局或深度耗尽无胜负
        return 0;
    }
}

2. 修正bestMove中的Minimax调用参数 #

将bestMove中调用Minimax的第三个参数改为false：

// 原错误写法：int score = minimax(grid, 16, true, aiMark, hMark);
int score = minimax(grid, 16, false, aiMark, hMark);

额外优化说明 #

当前实现的是自由落子的四子连珠规则，若要实现正统四子棋，需修改落子逻辑：遍历每一列，找到该列最底部的空位落子，而非遍历所有棋盘空位。

内容的提问来源于stack exchange，提问作者Edric Antoine