用C++手搓一个能下赢你的五子棋AI：从零实现博弈树与α-β剪枝

用C++手搓一个能下赢你的五子棋AI：从零实现博弈树与α-β剪枝

五子棋作为一款规则简单却变化无穷的策略游戏，一直是人工智能入门的经典练手项目。本文将带你用C++从零构建一个具备业余段位水平的五子棋AI，核心在于理解博弈树搜索与α-β剪枝这对黄金组合。不同于单纯讲解算法理论，我们将采用"问题驱动+代码实战"的方式，在解决实际对弈问题的过程中掌握这些关键技术。

1. 环境准备与基础架构

1.1 项目初始化

首先创建标准的C++项目结构，建议使用支持C++17的编译器（如GCC 9+或MSVC 2019+）。核心只需要两个头文件：

// config.h #pragma once constexpr int BOARD_SIZE = 15; // 标准五子棋棋盘尺寸 constexpr int WIN_CONDITION = 5; // 五子连珠 // gomoku_ai.h #include <array> #include <vector> #include <memory> class GomokuAI { public: using Board = std::array<std::array<int, BOARD_SIZE>, BOARD_SIZE>; struct Move { int x, y; bool operator==(const Move&) const = default; }; explicit GomokuAI(int search_depth = 3); Move find_best_move(const Board& board); private: int search_depth_; // 后续逐步实现私有方法 };

1.2 棋盘表示与基础操作

采用15×15的二维数组表示棋盘，用-1、0、1分别表示白子、空位、黑子。首先实现几个基础功能：

// 检查给定位置是否在棋盘内 bool is_valid_position(int x, int y) { return x >= 0 && x < BOARD_SIZE && y >= 0 && y < BOARD_SIZE; } // 判断落子后是否形成五连 bool check_win(const Board& board, Move last_move) { constexpr std::array<std::pair<int, int>, 4> directions = { {{1,0}, {0,1}, {1,1}, {1,-1}} // 横、竖、主对角线、副对角线 }; const int player = board[last_move.x][last_move.y]; for (auto [dx, dy] : directions) { int count = 1; for (int step = 1; step < WIN_CONDITION; ++step) { int x = last_move.x + dx * step; int y = last_move.y + dy * step; if (!is_valid_position(x, y) || board[x][y] != player) break; ++count; } // 反向检查 for (int step = 1; step < WIN_CONDITION; ++step) { int x = last_move.x - dx * step; int y = last_move.y - dy * step; if (!is_valid_position(x, y) || board[x][y] != player) break; ++count; } if (count >= WIN_CONDITION) return true; } return false; }

2. 博弈树与极大极小算法

2.1 博弈树节点设计

博弈树的每个节点代表一个棋局状态，需要存储：

• 当前棋盘状态
• 当前玩家（MAX或MIN）
• 可能的子节点（合法落子点）

struct GameNode { Board board; bool is_max_player; // true为AI(MAX)，false为人类(MIN) Move last_move; int value = is_max_player ? INT_MIN : INT_MAX; std::vector<std::unique_ptr<GameNode>> children; explicit GameNode(Board b, bool max_p, Move m = {-1,-1}) : board(std::move(b)), is_max_player(max_p), last_move(m) {} };

2.2 极大极小算法实现

算法核心是递归地评估所有可能的走法：

int minimax(GameNode* node, int depth) { if (depth == 0 || check_win(node->board, node->last_move)) { return evaluate_board(node->board); } generate_children(node); // 生成所有合法落子 for (auto& child : node->children) { int child_value = minimax(child.get(), depth - 1); if (node->is_max_player) { node->value = std::max(node->value, child_value); } else { node->value = std::min(node->value, child_value); } } return node->value; }

2.3 合法落子生成优化

五子棋的合法落子点不是全棋盘，而是已有棋子周围的空位：

void generate_children(GameNode* node) { std::vector<Move> candidate_moves; int search_radius = 2; // 搜索半径可调整 // 收集已有棋子周围空位 for (int i = 0; i < BOARD_SIZE; ++i) { for (int j = 0; j < BOARD_SIZE; ++j) { if (node->board[i][j] != 0) continue; // 检查周围search_radius范围内是否有棋子 bool near_existing = false; for (int dx = -search_radius; dx <= search_radius; ++dx) { for (int dy = -search_radius; dy <= search_radius; ++dy) { int x = i + dx, y = j + dy; if (is_valid_position(x, y) && node->board[x][y] != 0) { near_existing = true; break; } } if (near_existing) break; } if (near_existing) { candidate_moves.push_back({i, j}); } } } // 特殊处理开局第一步 if (candidate_moves.empty() && node->last_move.x == -1) { candidate_moves.push_back({BOARD_SIZE/2, BOARD_SIZE/2}); // 天元开局 } // 生成子节点 for (auto move : candidate_moves) { auto new_board = node->board; new_board[move.x][move.y] = node->is_max_player ? 1 : -1; node->children.emplace_back( std::make_unique<GameNode>(new_board, !node->is_max_player, move)); } }

3. α-β剪枝优化

3.1 算法原理

α-β剪枝通过记录当前搜索路径的最佳值，提前终止对不利分支的搜索：

3.2 代码实现

在极大极小算法基础上增加α、β参数：

int alphabeta(GameNode* node, int depth, int alpha, int beta) { if (depth == 0 || check_win(node->board, node->last_move)) { return evaluate_board(node->board); } generate_children(node); for (auto& child : node->children) { int child_value = alphabeta(child.get(), depth - 1, alpha, beta); if (node->is_max_player) { alpha = std::max(alpha, child_value); if (alpha >= beta) break; // β剪枝 } else { beta = std::min(beta, child_value); if (beta <= alpha) break; // α剪枝 } } return node->is_max_player ? alpha : beta; }

3.3 性能对比测试

在不同搜索深度下，α-β剪枝能显著减少需要评估的节点数：

4. 局面评估函数设计

4.1 棋型识别与评分

五子棋的胜负关键在于识别各种棋型组合。我们定义五元组（连续5个点）的评分规则：

int evaluate_pattern(const std::string& pattern, int player) { static const std::unordered_map<std::string, int> score_table = { {"11111", 1000000}, // 五连 {"011110", 100000}, // 活四 {"011112", 5000}, // 冲四(需防守) {"211110", 5000}, {"10111", 5000}, // 跳四 {"11011", 5000}, {"011100", 1000}, // 活三 {"001110", 1000}, {"010110", 1000}, {"011010", 1000}, // 更多棋型... }; // 将pattern转换为标准形式（1表示当前玩家，2表示对手） std::string normalized; for (char c : pattern) { if (c == '0') normalized += '0'; else normalized += (c == player + '0') ? '1' : '2'; } // 检查所有可能的5连续子串 int max_score = 0; for (int i = 0; i <= normalized.size() - 5; ++i) { auto it = score_table.find(normalized.substr(i, 5)); if (it != score_table.end()) { max_score = std::max(max_score, it->second); } } return max_score; }

4.2 全局评估函数

综合四个方向（横、竖、对角线）的所有五元组：

int evaluate_board(const Board& board) { int total_score = 0; // 检查所有行 for (int i = 0; i < BOARD_SIZE; ++i) { std::string row; for (int j = 0; j < BOARD_SIZE; ++j) { row += std::to_string(board[i][j] + 1); // -1,0,1 -> 0,1,2 } total_score += evaluate_pattern(row, 1); total_score -= evaluate_pattern(row, -1); } // 检查所有列（类似实现） // 检查主对角线（类似实现） // 检查副对角线（类似实现） return total_score; }

4.3 评估函数优化技巧

1. 增量计算：每次落子后只更新受影响的行列/对角线
2. 模式缓存：预计算常见棋型的得分
3. 对称性利用：旋转/镜像棋局可复用评估结果

// 增量评估示例（更新某一行） void update_row_score(int row, int col, int player) { int start_col = std::max(0, col - 4); int end_col = std::min(BOARD_SIZE - 1, col + 4); std::string segment; for (int j = start_col; j <= end_col; ++j) { segment += std::to_string(board[row][j] + 1); } // 只重新计算受影响的部分 current_score -= old_row_scores[row]; current_score += evaluate_pattern(segment, 1) - evaluate_pattern(segment, -1); old_row_scores[row] = evaluate_pattern(segment, 1) - evaluate_pattern(segment, -1); }

5. 完整AI对弈实现

5.1 主循环与接口

Move GomokuAI::find_best_move(const Board& board) { auto root = std::make_unique<GameNode>(board, true); alphabeta(root.get(), search_depth_, INT_MIN, INT_MAX); // 找出最佳子节点 auto best_it = std::max_element( root->children.begin(), root->children.end(), [](const auto& a, const auto& b) { return a->value < b->value; }); return (*best_it)->last_move; }

5.2 人机对弈示例

void play_human_vs_ai() { GomokuAI ai(4); // 搜索深度4 Board board{}; // 初始空棋盘 while (true) { // AI回合 auto ai_move = ai.find_best_move(board); board[ai_move.x][ai_move.y] = 1; if (check_win(board, ai_move)) { std::cout << "AI wins!\n"; break; } // 人类回合 print_board(board); int x, y; std::cout << "Your move (x y): "; std::cin >> x >> y; board[x][y] = -1; if (check_win(board, {x,y})) { std::cout << "You win!\n"; break; } } }

5.3 性能优化技巧

1. 迭代加深：先浅层搜索快速响应，后台继续深层搜索
2. 多线程并行：不同分支分配到不同线程
3. 开局库：记忆常见开局模式
4. 置换表：缓存已评估的棋局

// 简单的多线程搜索示例 std::vector<std::future<int>> futures; for (auto& child : root->children) { futures.push_back(std::async(std::launch::async, [&] { return alphabeta(child.get(), depth-1, alpha, beta); })); } // 收集结果 for (auto& f : futures) { int val = f.get(); // 更新最佳值... }

6. 进阶优化方向

6.1 启发式搜索策略

1. 杀手启发：优先尝试历史表现好的走法
2. 历史表：记录各位置的历史得分
3. 静态搜索：对关键局面延长搜索深度

6.2 机器学习增强

1. 神经网络评估：用CNN替代手工评估函数
2. 强化学习：通过自我对弈提升策略
3. 蒙特卡洛树搜索：结合随机模拟与树搜索

6.3 工程实践建议

1. 使用位棋盘：用64位整数压缩表示棋盘状态
2. Zobrist哈希：快速计算棋局哈希值
3. SIMD优化：用AVX指令并行评估多个位置

// 位棋盘示例（每棋子用2位表示） uint64_t board_bitmask[2]; // [0]为黑子，[1]为白子 bool is_occupied(int x, int y) { uint64_t mask = 1ULL << (x * BOARD_SIZE + y); return (board_bitmask[0] | board_bitmask[1]) & mask; }

构建五子棋AI的过程就像教计算机下棋——从最基础的规则开始，逐步增加策略深度。当看到AI能够识破你的"三三禁手"时，那种成就感正是编程的乐趣所在。建议从搜索深度3开始，逐步提升难度，同时尝试不同的评估函数设计，你会发现同样的算法框架，不同的评估策略会导致AI风格迥异：有的激进进攻，有的稳健防守。这种差异正是博弈类AI的魅力所在。