gomoku-botzone

概述

概括三件事：棋盘 15×15；规则为一手交换五子棋（Swap-1，见下节）；在评测时限下，步数尚少时采用 Minimax¹，局面更开放后改用 MCTS²。下文按规则、输入、局面表示、两种搜索分节说明。代码中 Self 表己方、Opp 表对方。本仓库从标准输入³ 读整数流；Botzone 官方样例常用单行 JSON⁴ 记录落子，二者 IO 契约不同，在官方环境需在适配层解析并映射坐标后再调用同一决策核心。

实现上，低步数阶段使用带威胁启发的 Minimax，配合迭代加深⁵ 与 α–β 剪枝⁶；高步数阶段在约每步 970ms 内运行 MCTS，子节点以 UCT⁷ 选取，根上取访问次数最多的走法以降低模拟方差。

平台与成绩

对弈与提交依托北京大学 Botzone 在线博弈平台（链接见下）。本人在吉林大学面向该棋类项目的评定中，获得 2023 级第三名。

规则要点（Swap-1）

胜负与标准五子棋相同：横、纵、斜任一线先连成五子即胜；棋盘 15×15。Swap-1 规则要点：黑方落下第一手后，白方可选择是否执行「换手」；若换手，双方所持颜色对调，行棋权仍落在规则意义上的先手方一侧（平台交互中以坐标约定表达）。Botzone 交互中换手可用特殊坐标表示（例如 x、y 均为 -1）；黑方首回合若尚未收到对方落点，请求中亦可出现 {"x":-1,"y":-1}。细则以平台公开说明为准。

评测输入与官方 JSON

数据交换上，官方示例常用单行 JSON，以 requests / responses 数组编码双方历史落子。本仓库 gomoku-swap.cpp 面向本地或自定义判题，从标准输入³ 读整数序列（先读 n，再按分支读坐标）重放局面。语义一致、编码不同：部署到官方环境时在外层做 JSON 解析与坐标转换，还原棋盘后调用同一套决策逻辑。

MCTS 分支末尾追加连续读入，用于消费判题器可能附带的尾部数据，避免 stdin 管道阻塞。

局面表示与威胁启发（Minimax 共用）

局面在四方向（横、纵、两对角）射线上维护局部特征：连续同色长度、端点是否为空、跳子（隔一空位）等。落子或撤销时沿射线增量更新⁸，避免每步全棋盘扫描。

候选点排序使用威胁型启发⁹：WEIGHT、HOPWEIGHT 等表按连子长度与开口赋权，四向合成后对 Move 排序，并辅以距中心次要键，以收缩 Minimax / MCTS 分支宽度。

Minimax 阶段（n 较小）

当已走步数 n 不超过阈值（40）时进入 Minimax 阶段。深度从 2 递增至 DEPTH，每层仅展开启发排序后的前 BREADTH[depth] 个候选。递归中维护 (low, high) 区间，作 α–β 式剪枝⁶。自本回合起用 steady_clock¹⁰ 计时，超过约 970ms 则中止加深，返回当前最优着法。

某候选点四向威胁乘积超过阈值时，可判强必胜或强必防，用于提前截断。

时间上限与 minMax 入口处的判断一致

bool timeout() {
    return duration_cast<milliseconds>(steady_clock::now() - start).count() > 970;
}

深度耗尽、无合法着法或 timeout() 为真时返回；计时与 Minimax 入口共用同一 steady_clock¹⁰ 起点。

MCTS 阶段（n 较大）

当 n 超过阈值后切换为 MCTS。空位集合按 mctsStatus 威胁权重排序；扩展宽度由当前最大威胁 maxw 与深度共同决定：极强威胁时收紧为单线，浅层减少分支，其余按威胁量级分档，以在随机模拟中优先覆盖关键线。

UCT：胜率项 + 探索项（C 为全局常数）

double uct(int col) {
    const int win = col == 0 ? self : opp;
    return (double)win / visit + C * sqrt(log(parent->visit) / visit);
}

下钻时优先扩展未访问子节点；否则在子节点中取 UCT⁷ 最大者（公式见上：利用项 + 探索项）。未至终局则按 width 从 mctsblank 挂子；无可扩或深度耗尽时以随机对局结果为叶估值。回溯时撤销棋盘并回传胜负统计。

扩展阶段：由 maxw、depth 决定 width，再向 mctsblank 挂子（节选）

const LL maxw = mctsblank.begin()->w;
int width = 13;
if (maxw > 1e14) width = 1;
else if (depth < 4) width = 4;
else if (maxw > 5e6) width = 6;
else if (maxw > 6e4) width = 8;
else if (maxw > 8e3) width = 10;
for (const auto& b : mctsblank) {
    if (u->children.size() >= (size_t)width && b.w < maxw / 10) break;
    // new Node → parent / move / first，push_back …
}
// … 叶节点判定、UCT 选子、mctsmodify 递归与回溯略

根结点在时限内反复调用 mctssearch；终局取 visit 最大子节点，以统计稳定决策。

根上：限时循环 + 按 visit 取最优子（节选）

while (!timeout())
    mctssearch(root, 30);
auto best = std::max_element(root->children.begin(), root->children.end(),
    [](Node* a, Node* b) { return a->visit < b->visit; });
// … 写入 BestPos 坐标

开局与换手

在特定开局与输入分支下，若轮到己方且规则允许，可输出 (4,4) 作为首着；若对方首着落在中心邻域内，可输出 (-1,-1) 表示行使 Swap-1 白方换手权。具体条件与坐标判定见源码 main 中对 n 与坐标序列的分支。

工程与性能

工程上采用 mt19937_64 提供可复现的随机性，steady_clock 提供单调计时。源文件使用 GCC pragma 开启 Ofast、栈保护与循环展开等优化，以在评测时限内提高搜索吞吐。本文不涉及任何私人账号或对局标识。

术语与注释

  1. Minimax（极小极大）：假设双方均走最优应对，在博弈树上递归极大／极小化估值，用于比较当前着法的相对优劣。
  2. MCTS（蒙特卡洛树搜索）：在搜索树上迭代选择、扩展、模拟、回传，用大量随机对局的统计近似局面价值。
  3. 标准输入（stdin）：进程从操作系统提供的字节流顺序读入；本实现用整数序列重放盘面。
  4. JSON：文本数据交换格式；Botzone 样例用单行对象内的 requests / responses 数组编码双方历史落子。
  5. 迭代加深：搜索深度由浅到深递增，在固定时间预算内取最后一次加深完成时的最优结论。
  6. α–β 剪枝：在 Minimax 递归中传递值区间，剪掉不可能改变最优走法的子树，减少扩展节点数。
  7. UCT：将平均收益与探索项相加，在子节点选择上平衡「利用已有统计」与「探索访问少的分支」；公式见源码。
  8. 增量更新：落子或撤销时仅沿受影响方向改写局部特征，避免每步扫描全棋盘。
  9. 威胁启发：按连子长度与开口形态查表（WEIGHT / HOPWEIGHT）为候选点赋权，用于排序与限宽。
  10. steady_clock：C++ chrono 提供的单调时钟，适合测量逝去时间，不受系统调时影响。