简介这是一份面向计算机相关专业学生与C初学者的课程设计资源围绕亚马逊棋Amazons这一双人对弈策略游戏展开帮助读者理解棋盘状态表示、走子与射箭规则、合法移动判定等核心逻辑并完成从命令行交互到图形界面的完整实现。压缩包共91个文件约40.07MB包含4个cpp源文件与5个头文件构成的核心代码配套png截图、doc实验报告与程序框图、md说明文档以及pdb、dll、obj、exe等编译调试产物和Makefile构建脚本另附LICENSE与ReadMe目录结构清晰便于按模块查阅。资源中整理了实验报告、程序框图与多份说明文档读者可据此梳理数据结构设计、类封装、游戏逻辑、错误处理及DFS/BFS搜索算法等关键知识点并参考GUI相关头文件与界面截图理解交互实现。目前已有442人学习适合需要完成同类大作业或想通过实战提升C编程与算法设计能力的读者参考。1. 亚马逊棋到底难在哪一个 10×10 棋盘上的搜索与评估博弈亚马逊棋Game of the Amazons是 1988 年由 Walter Zamkauskas 发明的一款双人完全信息博弈规则简单到三句话就能讲完10×10 棋盘每方四枚棋子每回合先走一步棋、再在棋盘上射一箭封锁一个格子谁先无路可走谁输。但就是这三句话让它在 C 博弈程序圈子里成了公认的硬骨头——分支因子开局约 2176中局动辄上万比国际象棋高出两三个数量级。很多用 C 写棋类 AI 的人第一次跑亚马逊棋的朴素极大极小搜索会发现连三层都搜不完就卡死了。这篇笔记就围绕「基于 C 实现亚马逊棋」这个目标把棋盘表示、走法生成、搜索剪枝、局面评估这条完整链路拆开讲清楚适合已经会写 C、想拿一个真实博弈项目练搜索算法的开发者也适合正在做课程设计或想找一个能写进简历的 C 项目的同学。2. 棋盘表示与走法生成先把数据结构选对2.1 为什么用一维数组而不是二维数组亚马逊棋棋盘固定 10×10共 100 格。新手最容易上手的是int board[10][10]但真写下去就会发现两个问题一是走法生成时到处写xdx, ydy的边界判断代码又长又容易漏二是缓存局部性差搜索时频繁访问二维数组的行指针性能吃亏。我一般直接用一维数组int board[100]坐标(r, c)映射到索引r * 10 c。这样做的直接好处是方向向量可以预计算成索引偏移量走法生成变成纯加法边界判断只需要在偏移表里提前剔除越界的偏移。#include array #include vector #include cstdint constexpr int N 10; constexpr int CELLS N * N; // 0 空, 1 黑棋, 2 白棋, 3 被箭封锁 using Board std::arrayuint8_t, CELLS; // 八个方向上下左右 四个对角 constexpr int DR[8] {-1, -1, -1, 0, 0, 1, 1, 1}; constexpr int DC[8] {-1, 0, 1, -1, 1, -1, 0, 1}; inline int idx(int r, int c) { return r * N c; } inline int rowOf(int i) { return i / N; } inline int colOf(int i) { return i % N; }这段代码里Board用uint8_t而不是int是因为 100 个格子用int占 400 字节用uint8_t只占 100 字节搜索时拷贝和缓存都更友好。方向向量拆成DR/DC两个数组而不是结构体数组是为了让编译器更容易做向量化。idx和rowOf/colOf声明为inline避免在热路径上产生函数调用开销。2.2 走法生成一步棋加一箭亚马逊棋的一步完整走法由三部分组成起点、落点、射箭点。起点必须是己方棋子落点和射箭点都必须是空格且路径上不能有阻挡。走法生成的核心就是沿八个方向做射线扫描。struct Move { int from; // 起点索引 int to; // 落点索引 int arrow; // 射箭点索引 }; // 生成某一枚棋子的所有走法 void genMovesFrom(const Board b, int from, std::vectorMove out) { int r0 rowOf(from), c0 colOf(from); for (int d 0; d 8; d) { int r r0 DR[d], c c0 DC[d]; // 沿方向一直走直到越界或遇到非空格 while (r 0 r N c 0 c N b[idx(r, c)] 0) { int to idx(r, c); // 落点确定后从落点再向八个方向射箭 for (int e 0; e 8; e) { int rr r DR[e], cc c DC[e]; while (rr 0 rr N cc 0 cc N b[idx(rr, cc)] 0) { out.push_back({from, to, idx(rr, cc)}); rr DR[e]; cc DC[e]; } } r DR[d]; c DC[d]; } } }逻辑上分两层循环外层沿棋子能走的方向扫描落点内层从每个落点再沿八个方向扫描射箭点。参数上要注意b[idx(r,c)] 0这个判断同时承担了「空格」和「未越界」两个语义因为越界在 while 条件里已经拦掉了。这个实现是朴素版本实测开局单方走法数在 2000 上下中局能到 8000 以上所以后面搜索必须剪枝否则根本跑不动。提示走法生成是热点函数先用-O2编译再用perf或gprof确认它占的时间比例。如果超过 60%优先优化这里而不是搜索本身。2.3 用位棋盘做加速的取舍一维数组够用但如果你想把搜索深度再往上推位棋盘bitboard是绕不开的。100 格用两个uint64_t表示走法生成变成位运算和查表。代价是实现复杂度陡增调试难度也大。我的建议是先用一维数组把整条链路跑通确认搜索和评估逻辑正确再考虑换位棋盘。很多项目死在「一上来就位棋盘结果 bug 找不到项目烂尾」。3. 搜索算法从朴素极大极小到带置换表的 Alpha-Beta3.1 朴素极大极小为什么在亚马逊棋上不可行极大极小搜索的复杂度是 O(b^d)b 是分支因子d 是深度。亚马逊棋开局 b≈2176搜三层就是 2176³ ≈ 10^10 个节点就算每个节点只花 10 纳秒也要 100 秒。这还没算评估函数的时间。所以朴素极大极小在亚马逊棋上连三层都跑不完必须上 Alpha-Beta 剪枝。Alpha-Beta 在理想情况下能把有效分支因子降到约 √b也就是 2176 变成 46 左右三层只要 10^5 个节点瞬间就能跑完。但理想情况要求走法排序完美实际中要靠启发式排序逼近。3.2 Alpha-Beta 的 C 实现骨架constexpr int INF 1e9; // alpha: 当前能保证的下界, beta: 对手能保证的上界 int alphaBeta(Board b, int depth, int alpha, int beta, int side) { if (depth 0) return evaluate(b, side); std::vectorMove moves; generateAllMoves(b, side, moves); if (moves.empty()) { // 无路可走当前方输 return -INF (MAX_DEPTH - depth); } orderMoves(b, moves); // 启发式排序关键 int best -INF; for (const Move m : moves) { Board nb b; applyMove(nb, m, side); int score -alphaBeta(nb, depth - 1, -beta, -alpha, 3 - side); if (score best) best score; if (score alpha) alpha score; if (alpha beta) break; // 剪枝 } return best; }几个关键点-INF (MAX_DEPTH - depth)这个写法是为了让「更快输」和「更慢输」有区分搜索会倾向于拖延失败实战中能多撑几步等对手犯错。orderMoves是性能命门排序好坏直接决定剪枝效率。applyMove里拷贝整个Board是有成本的如果性能不够可以改成「落子-撤销」的就地修改模式。3.3 走法排序让剪枝真正生效的三个启发走法排序的目标是把最可能好的走法排前面。亚马逊棋上我一般用三个启发叠加第一历史启发history heuristic。维护一张history[from][to]表每次某个走法引发剪枝就加分排序时按分数降序。这个实现简单效果稳定。第二杀手走法killer moves。同一层里如果某个走法刚引发过剪枝它在本层其他节点也很可能好用优先尝试。第三射箭点启发。射箭点越靠近棋盘中心、越能分割对手棋子连通性价值越高。可以预计算一张「射箭价值表」排序时加权。int historyScore[CELLS][CELLS] {0}; void orderMoves(const Board b, std::vectorMove moves) { std::sort(moves.begin(), moves.end(), [](const Move a, const Move c) { int sa historyScore[a.from][a.to] arrowBonus(a.arrow); int sc historyScore[c.from][c.to] arrowBonus(c.arrow); return sa sc; }); }arrowBonus可以简单用「到棋盘中心的曼哈顿距离取负」越靠中心分越高。参数上历史表和射箭加权的比例需要调我一般让历史分占主导射箭分做微调比例大概 10:1。3.4 置换表用 Zobrist 哈希避免重复搜索亚马逊棋中不同走法顺序可能到达同一局面置换表能把重复局面的搜索结果缓存下来。核心是 Zobrist 哈希给每个格子的每种状态黑、白、箭分配一个随机数局面哈希就是所有格子随机数的异或。uint64_t zobrist[CELLS][4]; // 4 种状态空、黑、白、箭 uint64_t hashBoard(const Board b) { uint64_t h 0; for (int i 0; i CELLS; i) h ^ zobrist[i][b[i]]; return h; }zobrist表在程序启动时用固定种子初始化保证可复现。置换表用哈希表实现存深度、分数、标志位精确值/下界/上界。注意置换表要限制大小否则内存吃光一般 2^20 到 2^24 条目之间。4. 局面评估亚马逊棋的评估函数怎么写才不玄学4.1 评估函数的三个核心维度亚马逊棋没有吃子评估函数不能像国际象棋那样算子力。我一般从三个维度打分一是机动性mobility即己方所有棋子的合法走法总数减去对手的二是区域控制territory用洪水填充算双方棋子能到达的区域大小三是连通性己方四枚棋子之间的可达性被分割开通常意味着劣势。机动性最好算走法生成时顺便统计即可。区域控制用 BFS 从每枚棋子出发标记能到达的空格统计数量。连通性可以用并查集或多次 BFS 判断。int evaluate(const Board b, int side) { int myMob countMobility(b, side); int opMob countMobility(b, 3 - side); int myTer countTerritory(b, side); int opTer countTerritory(b, 3 - side); // 权重需要调下面是一组实测可用的起点 return 3 * (myMob - opMob) 5 * (myTer - opTer); }权重 3 和 5 不是拍脑袋是我在若干局自我对弈里调出来的起点。机动性变化快但噪声大区域控制变化慢但更能反映长期优劣所以区域权重更高。实际项目里应该写一个自动调参脚本用自我对弈的胜负结果做梯度估计。4.2 洪水填充算区域控制的实现int countTerritory(const Board b, int side) { std::arraybool, CELLS vis{}; std::vectorint stack; for (int i 0; i CELLS; i) { if (b[i] side) { vis[i] true; stack.push_back(i); } } int cnt 0; while (!stack.empty()) { int cur stack.back(); stack.pop_back(); int r rowOf(cur), c colOf(cur); for (int d 0; d 8; d) { int rr r DR[d], cc c DC[d]; if (rr 0 || rr N || cc 0 || cc N) continue; int ni idx(rr, cc); if (vis[ni] || b[ni] ! 0) continue; vis[ni] true; cnt; stack.push_back(ni); } } return cnt; }这里用显式栈而不是递归避免深递归爆栈。vis数组每次调用都清零如果评估调用频繁可以考虑用「时间戳」技巧用一个全局递增的stampvis里存上次访问的时间戳省掉清零开销。4.3 评估函数的常见误用最常见的误用是把评估函数写得太重。有人把区域控制、连通性、中心控制、边界控制全塞进去每个节点算几十微秒结果搜索深度上不去整体棋力反而下降。经验是评估函数单次调用控制在 1 微秒以内宁可评估粗糙一点也要保证搜索深度。亚马逊棋里深度带来的收益远大于评估精度。另一个误用是权重不调。评估函数里的权重必须用数据调不能凭感觉。我一般跑 200 局自我对弈用逻辑回归或简单的网格搜索找一组相对优的权重。5. 避坑与排查亚马逊棋 C 实现里最容易翻车的五件事5.1 走法生成漏掉射箭点导致 AI 下棋「不封路」现象AI 能正常走棋但从不主动封锁对手棋力极低。原因走法生成里只生成了落点射箭点用了固定值或漏了内层循环。解决写一个单元测试对空棋盘统计单枚棋子的走法数理论值应该是 8 个方向落点乘以每个落点的射箭数之和对不上就说明生成逻辑有 bug。5.2 Alpha-Beta 剪枝后分数异常AI 走「自杀步」现象AI 偶尔走出明显送死的棋。原因Alpha-Beta 里alpha和beta的取负写错或者剪枝条件写成alpha beta而不是alpha beta。解决先用深度 1、2 的小搜索对比朴素极大极小和 Alpha-Beta 的结果两者必须完全一致不一致就是剪枝写错了。5.3 置换表哈希冲突导致搜索结果错乱现象AI 棋力时好时坏同一局面两次搜索结果不同。原因置换表只存了哈希没存校验或者哈希表覆盖策略有 bug。解决置换表条目里加一个 32 位的校验值命中时先比对校验值再使用。另外置换表大小要是 2 的幂索引用位与而不是取模。5.4 递归搜索爆栈现象程序跑一会儿直接崩溃没有报错。原因搜索深度大时递归层数太深默认栈空间不够。解决把搜索深度限制在合理范围一般 6 到 8 层或者把递归改成显式栈的迭代版本。Linux 下可以用ulimit -s调大栈空间但治本还是控制深度。5.5 评估函数符号搞反AI 帮对手下棋现象AI 棋力为负越搜越差。原因评估函数返回的是「当前方视角」还是「固定一方视角」没统一取负时符号错了。解决明确规定evaluate返回当前行棋方的视角分数搜索里取负逻辑就统一了。写个测试空棋盘双方评估应该接近对称。6. 进阶技巧用迭代加深加时间控制把棋力再推一档前面几章把亚马逊棋的 C 实现链路走通了但要让程序在实战里稳定发挥还得加迭代加深和时间控制。迭代加深的思路是从深度 1 开始搜搜完深度 1 搜深度 2一直往上加直到时间用完。好处是每一层的搜索结果可以用来排序下一层的走法剪枝效率大幅提升而且随时中断都能拿到一个可用的走法。Move searchWithTimeLimit(Board b, int side, int timeMs) { auto start std::chrono::steady_clock::now(); Move best{}; for (int depth 1; depth MAX_DEPTH; depth) { auto elapsed std::chrono::duration_caststd::chrono::milliseconds( std::chrono::steady_clock::now() - start).count(); if (elapsed timeMs * 0.5) break; // 预留一半时间给下一层 Move cur alphaBetaRoot(b, depth, side); best cur; } return best; }关键参数是那个0.5的系数。如果上一层已经用了一半时间下一层大概率搜不完不如直接停。这个系数可以根据实测调整我一般用 0.4 到 0.6 之间。时间控制之外还有一个容易被忽略的技巧开局库。亚马逊棋开局走法高度重复把常见开局的前几步存成表程序启动直接查表既省时间又避免开局阶段评估函数不准导致的昏招。开局库不用大几百个局面就够用。验证棋力最直接的方法是自我对弈。写一个脚本让新旧两个版本各执黑执白对弈 100 局统计胜率。胜率超过 55% 才算真的有提升低于这个数可能是噪声。我自己的习惯是每次改完搜索或评估先跑 20 局快速对弈看有没有明显退化确认没崩再跑 100 局正式验证。这套流程帮我省了很多次「改完感觉变强了实际是玄学」的后悔药。希望帮到你。本文还有配套的精品资源点击获取
基于C++实现亚马逊棋：从棋盘表示到Alpha-Beta搜索与评估
简介这是一份面向计算机相关专业学生与C初学者的课程设计资源围绕亚马逊棋Amazons这一双人对弈策略游戏展开帮助读者理解棋盘状态表示、走子与射箭规则、合法移动判定等核心逻辑并完成从命令行交互到图形界面的完整实现。压缩包共91个文件约40.07MB包含4个cpp源文件与5个头文件构成的核心代码配套png截图、doc实验报告与程序框图、md说明文档以及pdb、dll、obj、exe等编译调试产物和Makefile构建脚本另附LICENSE与ReadMe目录结构清晰便于按模块查阅。资源中整理了实验报告、程序框图与多份说明文档读者可据此梳理数据结构设计、类封装、游戏逻辑、错误处理及DFS/BFS搜索算法等关键知识点并参考GUI相关头文件与界面截图理解交互实现。目前已有442人学习适合需要完成同类大作业或想通过实战提升C编程与算法设计能力的读者参考。1. 亚马逊棋到底难在哪一个 10×10 棋盘上的搜索与评估博弈亚马逊棋Game of the Amazons是 1988 年由 Walter Zamkauskas 发明的一款双人完全信息博弈规则简单到三句话就能讲完10×10 棋盘每方四枚棋子每回合先走一步棋、再在棋盘上射一箭封锁一个格子谁先无路可走谁输。但就是这三句话让它在 C 博弈程序圈子里成了公认的硬骨头——分支因子开局约 2176中局动辄上万比国际象棋高出两三个数量级。很多用 C 写棋类 AI 的人第一次跑亚马逊棋的朴素极大极小搜索会发现连三层都搜不完就卡死了。这篇笔记就围绕「基于 C 实现亚马逊棋」这个目标把棋盘表示、走法生成、搜索剪枝、局面评估这条完整链路拆开讲清楚适合已经会写 C、想拿一个真实博弈项目练搜索算法的开发者也适合正在做课程设计或想找一个能写进简历的 C 项目的同学。2. 棋盘表示与走法生成先把数据结构选对2.1 为什么用一维数组而不是二维数组亚马逊棋棋盘固定 10×10共 100 格。新手最容易上手的是int board[10][10]但真写下去就会发现两个问题一是走法生成时到处写xdx, ydy的边界判断代码又长又容易漏二是缓存局部性差搜索时频繁访问二维数组的行指针性能吃亏。我一般直接用一维数组int board[100]坐标(r, c)映射到索引r * 10 c。这样做的直接好处是方向向量可以预计算成索引偏移量走法生成变成纯加法边界判断只需要在偏移表里提前剔除越界的偏移。#include array #include vector #include cstdint constexpr int N 10; constexpr int CELLS N * N; // 0 空, 1 黑棋, 2 白棋, 3 被箭封锁 using Board std::arrayuint8_t, CELLS; // 八个方向上下左右 四个对角 constexpr int DR[8] {-1, -1, -1, 0, 0, 1, 1, 1}; constexpr int DC[8] {-1, 0, 1, -1, 1, -1, 0, 1}; inline int idx(int r, int c) { return r * N c; } inline int rowOf(int i) { return i / N; } inline int colOf(int i) { return i % N; }这段代码里Board用uint8_t而不是int是因为 100 个格子用int占 400 字节用uint8_t只占 100 字节搜索时拷贝和缓存都更友好。方向向量拆成DR/DC两个数组而不是结构体数组是为了让编译器更容易做向量化。idx和rowOf/colOf声明为inline避免在热路径上产生函数调用开销。2.2 走法生成一步棋加一箭亚马逊棋的一步完整走法由三部分组成起点、落点、射箭点。起点必须是己方棋子落点和射箭点都必须是空格且路径上不能有阻挡。走法生成的核心就是沿八个方向做射线扫描。struct Move { int from; // 起点索引 int to; // 落点索引 int arrow; // 射箭点索引 }; // 生成某一枚棋子的所有走法 void genMovesFrom(const Board b, int from, std::vectorMove out) { int r0 rowOf(from), c0 colOf(from); for (int d 0; d 8; d) { int r r0 DR[d], c c0 DC[d]; // 沿方向一直走直到越界或遇到非空格 while (r 0 r N c 0 c N b[idx(r, c)] 0) { int to idx(r, c); // 落点确定后从落点再向八个方向射箭 for (int e 0; e 8; e) { int rr r DR[e], cc c DC[e]; while (rr 0 rr N cc 0 cc N b[idx(rr, cc)] 0) { out.push_back({from, to, idx(rr, cc)}); rr DR[e]; cc DC[e]; } } r DR[d]; c DC[d]; } } }逻辑上分两层循环外层沿棋子能走的方向扫描落点内层从每个落点再沿八个方向扫描射箭点。参数上要注意b[idx(r,c)] 0这个判断同时承担了「空格」和「未越界」两个语义因为越界在 while 条件里已经拦掉了。这个实现是朴素版本实测开局单方走法数在 2000 上下中局能到 8000 以上所以后面搜索必须剪枝否则根本跑不动。提示走法生成是热点函数先用-O2编译再用perf或gprof确认它占的时间比例。如果超过 60%优先优化这里而不是搜索本身。2.3 用位棋盘做加速的取舍一维数组够用但如果你想把搜索深度再往上推位棋盘bitboard是绕不开的。100 格用两个uint64_t表示走法生成变成位运算和查表。代价是实现复杂度陡增调试难度也大。我的建议是先用一维数组把整条链路跑通确认搜索和评估逻辑正确再考虑换位棋盘。很多项目死在「一上来就位棋盘结果 bug 找不到项目烂尾」。3. 搜索算法从朴素极大极小到带置换表的 Alpha-Beta3.1 朴素极大极小为什么在亚马逊棋上不可行极大极小搜索的复杂度是 O(b^d)b 是分支因子d 是深度。亚马逊棋开局 b≈2176搜三层就是 2176³ ≈ 10^10 个节点就算每个节点只花 10 纳秒也要 100 秒。这还没算评估函数的时间。所以朴素极大极小在亚马逊棋上连三层都跑不完必须上 Alpha-Beta 剪枝。Alpha-Beta 在理想情况下能把有效分支因子降到约 √b也就是 2176 变成 46 左右三层只要 10^5 个节点瞬间就能跑完。但理想情况要求走法排序完美实际中要靠启发式排序逼近。3.2 Alpha-Beta 的 C 实现骨架constexpr int INF 1e9; // alpha: 当前能保证的下界, beta: 对手能保证的上界 int alphaBeta(Board b, int depth, int alpha, int beta, int side) { if (depth 0) return evaluate(b, side); std::vectorMove moves; generateAllMoves(b, side, moves); if (moves.empty()) { // 无路可走当前方输 return -INF (MAX_DEPTH - depth); } orderMoves(b, moves); // 启发式排序关键 int best -INF; for (const Move m : moves) { Board nb b; applyMove(nb, m, side); int score -alphaBeta(nb, depth - 1, -beta, -alpha, 3 - side); if (score best) best score; if (score alpha) alpha score; if (alpha beta) break; // 剪枝 } return best; }几个关键点-INF (MAX_DEPTH - depth)这个写法是为了让「更快输」和「更慢输」有区分搜索会倾向于拖延失败实战中能多撑几步等对手犯错。orderMoves是性能命门排序好坏直接决定剪枝效率。applyMove里拷贝整个Board是有成本的如果性能不够可以改成「落子-撤销」的就地修改模式。3.3 走法排序让剪枝真正生效的三个启发走法排序的目标是把最可能好的走法排前面。亚马逊棋上我一般用三个启发叠加第一历史启发history heuristic。维护一张history[from][to]表每次某个走法引发剪枝就加分排序时按分数降序。这个实现简单效果稳定。第二杀手走法killer moves。同一层里如果某个走法刚引发过剪枝它在本层其他节点也很可能好用优先尝试。第三射箭点启发。射箭点越靠近棋盘中心、越能分割对手棋子连通性价值越高。可以预计算一张「射箭价值表」排序时加权。int historyScore[CELLS][CELLS] {0}; void orderMoves(const Board b, std::vectorMove moves) { std::sort(moves.begin(), moves.end(), [](const Move a, const Move c) { int sa historyScore[a.from][a.to] arrowBonus(a.arrow); int sc historyScore[c.from][c.to] arrowBonus(c.arrow); return sa sc; }); }arrowBonus可以简单用「到棋盘中心的曼哈顿距离取负」越靠中心分越高。参数上历史表和射箭加权的比例需要调我一般让历史分占主导射箭分做微调比例大概 10:1。3.4 置换表用 Zobrist 哈希避免重复搜索亚马逊棋中不同走法顺序可能到达同一局面置换表能把重复局面的搜索结果缓存下来。核心是 Zobrist 哈希给每个格子的每种状态黑、白、箭分配一个随机数局面哈希就是所有格子随机数的异或。uint64_t zobrist[CELLS][4]; // 4 种状态空、黑、白、箭 uint64_t hashBoard(const Board b) { uint64_t h 0; for (int i 0; i CELLS; i) h ^ zobrist[i][b[i]]; return h; }zobrist表在程序启动时用固定种子初始化保证可复现。置换表用哈希表实现存深度、分数、标志位精确值/下界/上界。注意置换表要限制大小否则内存吃光一般 2^20 到 2^24 条目之间。4. 局面评估亚马逊棋的评估函数怎么写才不玄学4.1 评估函数的三个核心维度亚马逊棋没有吃子评估函数不能像国际象棋那样算子力。我一般从三个维度打分一是机动性mobility即己方所有棋子的合法走法总数减去对手的二是区域控制territory用洪水填充算双方棋子能到达的区域大小三是连通性己方四枚棋子之间的可达性被分割开通常意味着劣势。机动性最好算走法生成时顺便统计即可。区域控制用 BFS 从每枚棋子出发标记能到达的空格统计数量。连通性可以用并查集或多次 BFS 判断。int evaluate(const Board b, int side) { int myMob countMobility(b, side); int opMob countMobility(b, 3 - side); int myTer countTerritory(b, side); int opTer countTerritory(b, 3 - side); // 权重需要调下面是一组实测可用的起点 return 3 * (myMob - opMob) 5 * (myTer - opTer); }权重 3 和 5 不是拍脑袋是我在若干局自我对弈里调出来的起点。机动性变化快但噪声大区域控制变化慢但更能反映长期优劣所以区域权重更高。实际项目里应该写一个自动调参脚本用自我对弈的胜负结果做梯度估计。4.2 洪水填充算区域控制的实现int countTerritory(const Board b, int side) { std::arraybool, CELLS vis{}; std::vectorint stack; for (int i 0; i CELLS; i) { if (b[i] side) { vis[i] true; stack.push_back(i); } } int cnt 0; while (!stack.empty()) { int cur stack.back(); stack.pop_back(); int r rowOf(cur), c colOf(cur); for (int d 0; d 8; d) { int rr r DR[d], cc c DC[d]; if (rr 0 || rr N || cc 0 || cc N) continue; int ni idx(rr, cc); if (vis[ni] || b[ni] ! 0) continue; vis[ni] true; cnt; stack.push_back(ni); } } return cnt; }这里用显式栈而不是递归避免深递归爆栈。vis数组每次调用都清零如果评估调用频繁可以考虑用「时间戳」技巧用一个全局递增的stampvis里存上次访问的时间戳省掉清零开销。4.3 评估函数的常见误用最常见的误用是把评估函数写得太重。有人把区域控制、连通性、中心控制、边界控制全塞进去每个节点算几十微秒结果搜索深度上不去整体棋力反而下降。经验是评估函数单次调用控制在 1 微秒以内宁可评估粗糙一点也要保证搜索深度。亚马逊棋里深度带来的收益远大于评估精度。另一个误用是权重不调。评估函数里的权重必须用数据调不能凭感觉。我一般跑 200 局自我对弈用逻辑回归或简单的网格搜索找一组相对优的权重。5. 避坑与排查亚马逊棋 C 实现里最容易翻车的五件事5.1 走法生成漏掉射箭点导致 AI 下棋「不封路」现象AI 能正常走棋但从不主动封锁对手棋力极低。原因走法生成里只生成了落点射箭点用了固定值或漏了内层循环。解决写一个单元测试对空棋盘统计单枚棋子的走法数理论值应该是 8 个方向落点乘以每个落点的射箭数之和对不上就说明生成逻辑有 bug。5.2 Alpha-Beta 剪枝后分数异常AI 走「自杀步」现象AI 偶尔走出明显送死的棋。原因Alpha-Beta 里alpha和beta的取负写错或者剪枝条件写成alpha beta而不是alpha beta。解决先用深度 1、2 的小搜索对比朴素极大极小和 Alpha-Beta 的结果两者必须完全一致不一致就是剪枝写错了。5.3 置换表哈希冲突导致搜索结果错乱现象AI 棋力时好时坏同一局面两次搜索结果不同。原因置换表只存了哈希没存校验或者哈希表覆盖策略有 bug。解决置换表条目里加一个 32 位的校验值命中时先比对校验值再使用。另外置换表大小要是 2 的幂索引用位与而不是取模。5.4 递归搜索爆栈现象程序跑一会儿直接崩溃没有报错。原因搜索深度大时递归层数太深默认栈空间不够。解决把搜索深度限制在合理范围一般 6 到 8 层或者把递归改成显式栈的迭代版本。Linux 下可以用ulimit -s调大栈空间但治本还是控制深度。5.5 评估函数符号搞反AI 帮对手下棋现象AI 棋力为负越搜越差。原因评估函数返回的是「当前方视角」还是「固定一方视角」没统一取负时符号错了。解决明确规定evaluate返回当前行棋方的视角分数搜索里取负逻辑就统一了。写个测试空棋盘双方评估应该接近对称。6. 进阶技巧用迭代加深加时间控制把棋力再推一档前面几章把亚马逊棋的 C 实现链路走通了但要让程序在实战里稳定发挥还得加迭代加深和时间控制。迭代加深的思路是从深度 1 开始搜搜完深度 1 搜深度 2一直往上加直到时间用完。好处是每一层的搜索结果可以用来排序下一层的走法剪枝效率大幅提升而且随时中断都能拿到一个可用的走法。Move searchWithTimeLimit(Board b, int side, int timeMs) { auto start std::chrono::steady_clock::now(); Move best{}; for (int depth 1; depth MAX_DEPTH; depth) { auto elapsed std::chrono::duration_caststd::chrono::milliseconds( std::chrono::steady_clock::now() - start).count(); if (elapsed timeMs * 0.5) break; // 预留一半时间给下一层 Move cur alphaBetaRoot(b, depth, side); best cur; } return best; }关键参数是那个0.5的系数。如果上一层已经用了一半时间下一层大概率搜不完不如直接停。这个系数可以根据实测调整我一般用 0.4 到 0.6 之间。时间控制之外还有一个容易被忽略的技巧开局库。亚马逊棋开局走法高度重复把常见开局的前几步存成表程序启动直接查表既省时间又避免开局阶段评估函数不准导致的昏招。开局库不用大几百个局面就够用。验证棋力最直接的方法是自我对弈。写一个脚本让新旧两个版本各执黑执白对弈 100 局统计胜率。胜率超过 55% 才算真的有提升低于这个数可能是噪声。我自己的习惯是每次改完搜索或评估先跑 20 局快速对弈看有没有明显退化确认没崩再跑 100 局正式验证。这套流程帮我省了很多次「改完感觉变强了实际是玄学」的后悔药。希望帮到你。本文还有配套的精品资源点击获取
