前言

五子棋规则简单，却是研究博弈程序的好样本：状态空间远大于井字棋，又不像围棋那样难以评估。一个能下得像样的五子棋 AI，通常由三块拼成——局面表示、评估函数、搜索算法。三者缺一不可：没有评估函数，搜索无从比较叶子节点的好坏；没有搜索，评估函数只能看到眼前一步；局面表示则决定了前两者的效率上限。

初学者常见的误解是把 AI 等同于「找到一步好棋的规则表」，比如「对方有三连就堵」。这种写法在开局还能应付，一旦进入复杂的攻防就会顾此失彼，因为它没有「我走这一步之后，对方会怎么应」的概念。另一类误解是认为搜索越深越强——在没有剪枝的情况下，深度每加一层，节点数按分支因子指数增长，程序会先卡死，而不是先变强。

本文按「评估 → 搜索 → 工程取舍」的顺序讲清楚这套结构，并给出一份完整、可逐行推演的 C++17 示例。示例刻意做得克制：评估函数只认连续棋型和开放端，搜索用极小极大加 alpha-beta 剪枝。真正比赛级的引擎还会用到棋型表、置换表、VCF/VCT 算杀等技巧，本文只在最后一节点到。

一、局面表示

棋盘用 15×15 的二维数组表示，0表示空点，1表示黑，2表示白。用3 - player就能得到对手的编号，省掉一个分支。

// 适用于 C++17
constexpr int kSize = 15;
using Board = std::array<std::array<int, kSize>, kSize>;

选择固定大小的std::array而不是std::vector，是因为棋盘尺寸固定，没有堆开销，拷贝也便宜——搜索过程中需要频繁做「落子 / 撤销」，值语义的定长数组最方便。代价是棋盘大小写死在编译期。

局面之外还需要一个「轮到谁走」的信息。本文的实现把它作为参数turn传递，而不是塞进棋盘结构里，这样棋盘本身保持纯粹，搜索函数也不必关心历史。

二、评估函数：棋型比棋子数量重要

评估函数要做的事是：给一个静态局面打分，分数越高表示对某一方越有利。

最粗糙的做法是数棋子：黑子数减白子数。这个评估几乎没用——五子棋的胜负取决于连成五个，而不是谁的子多。正确的方式是按「棋型」打分，棋型由两个因素决定：连续同色子的长度，以及两端是否为空（称为「开放端」）。

把这些棋型映射成分数，就得到了评估函数的核心。分数之间要保持量级差异：活四必须远高于活三，否则搜索会为了几个活三放弃一个必胜的活四。下面的权重只是示例，实际引擎会通过自对弈或人工调参得到更细的表，这里不给出任何「调到这个数就最强」的结论。

需要强调的是，这个简化评估函数只识别连续棋型，不识别「跳三」「跳四」这类中间有空隙的形状。真实引擎会用模式串匹配或者按方向预计算棋型表来处理，本文的版本会在正文里明确说明这一局限。

三、搜索：极小极大与 alpha-beta 剪枝

3.1 极小极大

把「我走一步、对手走一步」展开成一棵树。叶子节点用评估函数打分；轮到我的节点取子节点的最大值（max 层），轮到对手的节点取最小值（min 层）。这就是极小极大（minimax）。

深度为 d、分支因子为 b 的树有 b 的 d 次方个叶子。15×15 的棋盘上，合法空点接近 225 个，即便只考虑已有棋子附近的点，分支因子也常常在几十的量级，所以不做任何裁剪的搜索走不了几步。

3.2 alpha-beta 剪枝

alpha 记录 max 层当前能保证的下界，beta 记录 min 层当前能保证的上界。当某个节点出现alpha >= beta时，说明这个分支的结果不可能影响祖先节点的选择，可以直接剪掉。

剪枝的效果强烈依赖走法顺序：先搜到好棋，alpha/beta 窗口收窄得快，剪掉的分支就多。理想顺序下，同样的深度只需大约开方量级的节点；最坏顺序下则退化成完整搜索。这就是为什么工程实现里都要做走法排序，而本文为了代码简洁只做了「按邻域生成候选点」这一层过滤。

3.3 终局处理

搜索里必须显式判断「这一步是否直接成五」。如果只依赖评估函数，评估函数给出的「五连」分数和真正的胜负之间还隔着一层，搜索可能为了追求更高的静态分而错过必胜手。正确做法是落子后立刻检查五连，命中就返回一个带深度修正的大分数——越早取胜分数越高，这样 AI 不会在稳赢的局面里绕圈子。

四、工程上的取舍

• 
  
• 候选点生成：只考虑距离已有棋子两格以内的空点。这既符合五子棋的直观（远离战场的点没有意义），也把分支因子从两百多降到几十。
• 
  
• 走法排序：按「落子后己方棋型分 + 阻断对方棋型分」排序，能让 alpha-beta 更早剪枝。本文代码留了注释位置，没有实现。
• 
  
• 置换表：把「局面哈希 → 搜索结果」缓存起来，避免重复计算。需要 Zobrist 哈希，属于进阶内容。
• 
  
• 算杀：VCF（连续冲四取胜）和 VCT（连续活三取胜）是独立的深度优先搜索，和主搜索分开跑。
• 
  
• 时间控制：迭代加深，从深度 2 开始逐层加深，超时即停。
• 
  

这些都不是银弹，每一项都有实现和调参成本。本文的示例定位是「结构完整、逻辑自洽」，不是「能打赢人」。

五、完整示例

// 适用于 C++17
#include <algorithm>
#include <array>
#include <cstddef>
#include <iostream>
#include <limits>
#include <vector>

constexpr int kSize = 15;
constexpr int kWin = 1000000;
using Board = std::array<std::array<int, kSize>, kSize>;

struct Point {
int row;
int col;
};

bool inBounds(int r, int c) {
return r >= 0 && r < kSize && c >= 0 && c < kSize;
}

// 连续 len 子、open 个开放端对应的分数
int runScore(int len, int openEnds) {
if (len >= 5) return kWin;
if (openEnds == 0) return 0;
switch (len) {
case 4: return openEnds == 2 ? 100000 : 10000;
case 3: return openEnds == 2 ? 8000 : 800;
case 2: return openEnds == 2 ? 500 : 50;
case 1: return openEnds == 2 ? 10 : 1;
default: return 0;
}
}

// 对一条线，计算 player 一方的棋型总分
int scoreFor(const std::vector<int>& line, int player) {
const int n = static_cast<int>(line.size());
int total = 0;
int i = 0;
while (i < n) {
if (line[i] != player) { ++i; continue; }
int j = i;
while (j < n && line[j] == player) ++j;
const int len = j - i;
int openEnds = 0;
if (i > 0 && line[i - 1] == 0) ++openEnds;
if (j < n && line[j] == 0) ++openEnds;
total += runScore(len, openEnds);
i = j;
}
return total;
}

// 全盘评估：己方分减去对方分
int evaluate(const Board& b, int me) {
const int opp = 3 - me;
int myScore = 0;
int oppScore = 0;
static const int dr[4] = {0, 1, 1, 1};
static const int dc[4] = {1, 0, 1, -1};
std::vector<int> line;
line.reserve(kSize);

for (int d = 0; d < 4; ++d) {
for (int r = 0; r < kSize; ++r) {
for (int c = 0; c < kSize; ++c) {
// 只从线段起点开始扫描，避免重复
if (inBounds(r - dr[d], c - dc[d])) continue;
line.clear();
int rr = r;
int cc = c;
while (inBounds(rr, cc)) {
line.push_back(b[rr][cc]);
rr += dr[d];
cc += dc[d];
}
if (line.size() >= 5) {
myScore += scoreFor(line, me);
oppScore += scoreFor(line, opp);
}
}
}
}
return myScore - oppScore;
}

// 判断刚落下的子是否连成五
bool wins(const Board& b, int r, int c, int player) {
static const int dr[4] = {0, 1, 1, 1};
static const int dc[4] = {1, 0, 1, -1};
for (int d = 0; d < 4; ++d) {
int count = 1;
for (int sign = -1; sign <= 1; sign += 2) {
int rr = r + dr[d] * sign;
int cc = c + dc[d] * sign;
while (inBounds(rr, cc) && b[rr][cc] == player) {
++count;
rr += dr[d] * sign;
cc += dc[d] * sign;
}
}
if (count >= 5) return true;
}
return false;
}

// 只在已有棋子周围两格内找候选点
std::vector<Point> candidates(const Board& b) {
std::vector<Point> moves;
bool hasStone = false;
for (int r = 0; r < kSize; ++r) {
for (int c = 0; c < kSize; ++c) {
if (b[r][c] != 0) hasStone = true;
}
}
if (!hasStone) return {{kSize / 2, kSize / 2}};

for (int r = 0; r < kSize; ++r) {
for (int c = 0; c < kSize; ++c) {
if (b[r][c] != 0) continue;
bool near = false;
for (int dr = -2; dr <= 2 && !near; ++dr) {
for (int dc = -2; dc <= 2 && !near; ++dc) {
if (inBounds(r + dr, c + dc) && b[r + dr][c + dc] != 0) {
near = true;
}
}
}
if (near) moves.push_back({r, c});
}
}
return moves;
}

// 极小极大 + alpha-beta；me 是 AI 一方，turn 是当前行棋方
int search(Board& b, int depth, int alpha, int beta, int me, int turn) {
const std::vector<Point> moves = candidates(b);
if (moves.empty() || depth == 0) return evaluate(b, me);

if (turn == me) {
int best = -2 * kWin;
for (const Point& p : moves) {
b[p.row][p.col] = turn;
int score;
if (wins(b, p.row, p.col, turn)) {
score = kWin + depth; // 越早取胜分数越高
} else {
score = search(b, depth - 1, alpha, beta, me, 3 - turn);
}
b[p.row][p.col] = 0; // 必须撤销
if (score > best) best = score;
if (best > alpha) alpha = best;
if (alpha >= beta) break;
}
return best;
}

int best = 2 * kWin;
for (const Point& p : moves) {
b[p.row][p.col] = turn;
int score;
if (wins(b, p.row, p.col, turn)) {
score = -kWin - depth; // 越晚失败越好
} else {
score = search(b, depth - 1, alpha, beta, me, 3 - turn);
}
b[p.row][p.col] = 0;
if (score < best) best = score;
if (best < beta) beta = best;
if (alpha >= beta) break;
}
return best;
}

Point chooseMove(Board& b, int me, int depth) {
const std::vector<Point> moves = candidates(b);
Point bestMove = moves.front();
int bestScore = -2 * kWin;
for (const Point& p : moves) {
b[p.row][p.col] = me;
int score;
if (wins(b, p.row, p.col, me)) {
score = kWin + depth;
} else {
score = search(b, depth - 1, -2 * kWin, 2 * kWin, me, 3 - me);
}
b[p.row][p.col] = 0;
if (score > bestScore) {
bestScore = score;
bestMove = p;
}
}
return bestMove;
}

int main() {
Board b{};
b[7][7] = 1;
b[7][8] = 2;
b[6][7] = 1;
b[8][8] = 2;

const Point p = chooseMove(b, 2, 4);
std::cout << "white plays: " << p.row << ", " << p.col << '\n';
return 0;
}

这段代码的关键在于「落子—递归—撤销」三件套严格配对。b[p.row][p.col] = 0;必须放在读取score之后、任何break或return之前，否则棋盘会残留上一层搜索落下的子，后面所有评估都会基于一个错误的局面。

kWin是一百万，评估函数里多个棋型相加可能超过它。本实现用kWin + depth这种明显高于任何静态分的值标记胜局，就是为了让「真实的五连」与「评估出来的高分」不会混淆。

常见坑点

1. 评估函数只数棋子

❌score = count(black) - count(white);✅ 按连续长度和开放端给棋型打分，再求双方分差

子多不代表优势。五子棋的核心是「形成不可阻挡的连子」，一个活四远比十个散子有用。

2. 搜索中忘记撤销落子

❌b[r][c] = turn; int s = search(...); return s;✅b[r][c] = turn; int s = search(...); b[r][c] = 0; return s;

漏掉撤销，后续分支会在被污染的局面上下棋，结果既不是搜索树的真实值，也难以复现。

3. alpha-beta 不更新窗口

❌ 递归时始终传alpha、beta的初始值，只在最后取 min/max ✅ 每次更新alpha = std::max(alpha, best)、beta = std::min(beta, best)，并在alpha >= beta时 break

不更新窗口，剪枝条件永远不会成立，算法退化成完整的极小极大，白白多算几倍节点。

4. 只看评估分，不判五连

❌ 叶子节点只返回evaluate(...)，从不显式检查wins✅ 落子后立即判断五连，命中返回带深度修正的大分数

评估函数的分数是「启发式」的，不能保证必胜手一定得分最高。终局判断必须是精确的。

5. 候选点铺满整个棋盘

❌ 对 225 个空点全部展开 ✅ 只保留距已有棋子两格以内的空点，并按威胁排序

分支因子直接决定搜索规模。把远离战场的点排除掉，是无损的剪枝（对实战几乎没有影响），收益却很直接。

6. 评估函数只算一方

❌return myScore;✅return myScore - oppScore;

只算己方分，AI 会看不见对手的活四，出现「自己冲四、对手已经成五」的荒唐走法。零和博弈的评估必须是相对的。

7. 用rand()处理随机性

❌srand(time(nullptr)); int k = rand() % n;✅std::mt19937 gen(std::random_device{}()); std::uniform_int_distribution<int> dist(0, n - 1);

rand()的质量和范围由实现决定，RAND_MAX可能只有 32767，取模还会引入偏差。C++11 起的<random>提供了明确的算法和分布。

总结

五子棋 AI 的骨架其实只有一句话：用评估函数给静态局面打分，用搜索把「对手会怎么应」考虑进来，用剪枝把指数爆炸压到可接受的范围。评估函数决定「看得准不准」，搜索决定「看得远不远」，剪枝决定「来不来得及」。三者里最容易写错的是评估的对称性和搜索的状态撤销——这两处一旦出错，程序不会崩溃，只会安静地下出莫名其妙的棋，所以调试时要拿小棋盘和固定局面逐步核对。