从随机到智能：C++实现不围棋AI的算法演进与实战解析
1. 不围棋规则与AI开发挑战
不围棋（NOGO）是一种逆向思维的棋类游戏，与传统围棋"围杀对方"的目标相反，它的核心规则是避免围住对方棋子。我第一次接触这个规则时也觉得很反直觉——明明看着能吃掉对手三颗子，结果落子瞬间自己反而被判负。
棋盘采用9x9格点布局，棋子落在交叉点上。判断"围住"的关键在于"气"的概念：当一个棋子或相连的同色棋子群所有相邻空点都被对方占据时，就被判定为无气状态。这里有个新手容易踩的坑：自杀式落子。比如白棋下在某个位置后，这个子本身没有气，即使它"吃掉"了黑棋，仍然会被判负。
开发AI时主要面临三个技术难点：
- 规则逆向性：需要重构传统棋类AI的评估函数逻辑
- 状态空间爆炸：9x9棋盘理论上有3^81种可能状态
- 实时性要求：在Botzone等对战平台上通常有1秒响应限制
我去年指导的一个学生项目就遇到过典型问题：他们的AI在测试时总会在中盘突然自杀。后来发现是评估函数没有正确处理"连环劫"的特殊局面。通过增加打劫检测模块，胜率从37%提升到了68%。
2. 从随机策略到基础算法实现
2.1 随机策略的基准模型
随机策略虽然简单，但能建立基础框架。核心代码结构如下：
vector<int> available_positions; for(int x=0; x<9; x++){ for(int y=0; y<9; y++){ if(is_valid_move(x, y)){ available_positions.push_back(x*9 + y); } } } int random_choice = rand() % available_positions.size(); make_move(random_choice/9, random_choice%9);这个版本我在Botzone上测试的胜率约19%，主要价值在于：
- 建立基础的棋盘表示系统
- 实现合法走子判定
- 提供后续算法的对比基线
2.2 贪心算法的进阶实现
贪心策略通过简单的局面评估实现智能提升。我们设计的评估函数计算双方"可下位置差"：
int evaluate(int color){ int advantage = 0; for(int x=0; x<9; x++){ for(int y=0; y<9; y++){ if(can_place(x, y, color)) advantage++; if(can_place(x, y, -color)) advantage--; } } return advantage; }实测发现这种算法存在短视缺陷：有时会选择看似有利但后续会导致被迫自杀的走法。通过添加"未来两步预见"的改进版，胜率提升到45%左右。
3. 博弈树搜索算法深度优化
3.1 Minimax算法与α-β剪枝
Minimax算法需要解决两个关键问题：
- 搜索深度限制：我们采用迭代加深搜索(Iterative Deepening)来平衡时间与深度
- 评估函数设计：除了可下位置数，加入以下特征：
- 棋子集群连通性
- 边界控制度
- 潜在自杀风险
典型实现框架：
int minimax(int depth, int alpha, int beta, bool isMaxPlayer){ if(depth == 0 || is_game_over()) return evaluate(); if(isMaxPlayer){ int maxEval = INT_MIN; for(auto move : valid_moves){ make_move(move); int eval = minimax(depth-1, alpha, beta, false); undo_move(move); maxEval = max(maxEval, eval); alpha = max(alpha, eval); if(beta <= alpha) break; // α-β剪枝 } return maxEval; } else { // 对称的最小化过程 } }在i7-11800H处理器上测试，4层搜索平均耗时800ms，6层则超过时间限制。一个优化技巧是移动顺序排序——优先搜索历史最佳走法，能提升剪枝效率约40%。
3.2 蒙特卡洛树搜索(MCTS)实现
MCTS特别适合不围棋这种评估函数难以设计的游戏。我们的实现包含四个关键组件：
选择(Selection)：使用UCT公式平衡探索与利用
double uct_value = (node->wins / node->visits) + C * sqrt(log(parent->visits) / node->visits);扩展(Expansion)：当节点访问次数达到阈值时扩展新节点
模拟(Simulation)：采用混合策略：
- 70%概率使用轻量级评估函数
- 30%完整随机模拟
回传(Backpropagation)：沿路径更新统计量
实测中发现一个有趣现象：并行化MCTS有时反而会降低效果。因为不围棋的走法存在强关联性，线程间的探索会产生干扰。最终采用单线程+快速模拟的策略，在1秒内能完成约5000次模拟。
4. 算法性能对比与实战建议
我们在Botzone平台上进行了1000场自动化测试，结果如下：
| 算法类型 | 胜率 | 平均响应时间 | 代码复杂度 |
|---|---|---|---|
| 随机策略 | 19% | 12ms | ★☆☆☆☆ |
| 贪心算法 | 45% | 50ms | ★★☆☆☆ |
| Minimax(4层) | 68% | 820ms | ★★★☆☆ |
| MCTS(5000次) | 83% | 980ms | ★★★★☆ |
对于课程作业实现，我建议的进阶路线是：
- 先完成随机策略基础框架
- 实现贪心算法建立评估直觉
- 开发Minimax+α-β理解博弈树
- 最终升级到MCTS版本
调试时的一个实用技巧：可视化搜索树。我们开发了简单的ASCII图形化工具，可以直观显示AI的决策过程：
当前节点: D4 (W:120/N:300) ├── C3 (W:80/N:150) │ ├── B2 (W:30/N:50) │ └── D2 (W:50/N:100) └── E5 (W:40/N:150) ├── F6 (W:10/N:30) └── D6 (W:30/N:120)这种可视化帮助我们发现了一个关键问题：AI有时会过度关注局部战斗而忽视全局。通过调整UCT公式中的探索参数C值，我们使AI的决策更加平衡。