用C手搓一个能下赢你的五子棋AI从零实现博弈树与α-β剪枝五子棋作为一款规则简单却变化无穷的策略游戏一直是人工智能入门的经典练手项目。本文将带你用C从零构建一个具备业余段位水平的五子棋AI核心在于理解博弈树搜索与α-β剪枝这对黄金组合。不同于单纯讲解算法理论我们将采用问题驱动代码实战的方式在解决实际对弈问题的过程中掌握这些关键技术。1. 环境准备与基础架构1.1 项目初始化首先创建标准的C项目结构建议使用支持C17的编译器如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::arraystd::arrayint, 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::arraystd::pairint, 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::vectorstd::unique_ptrGameNode 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::vectorMove 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_uniqueGameNode(new_board, !node-is_max_player, move)); } }3. α-β剪枝优化3.1 算法原理α-β剪枝通过记录当前搜索路径的最佳值提前终止对不利分支的搜索节点类型α值含义β值含义剪枝条件MAX节点当前路径下限父节点β值当前α ≥ 父节点βMIN节点父节点α值当前路径上限当前β ≤ 父节点α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 性能对比测试在不同搜索深度下α-β剪枝能显著减少需要评估的节点数搜索深度普通节点数α-β剪枝后节点数剪枝率3~50,000~10,00080%5~2,000,000~200,00090%7~100,000,000~5,000,00095%4. 局面评估函数设计4.1 棋型识别与评分五子棋的胜负关键在于识别各种棋型组合。我们定义五元组连续5个点的评分规则int evaluate_pattern(const std::string pattern, int player) { static const std::unordered_mapstd::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 评估函数优化技巧增量计算每次落子后只更新受影响的行列/对角线模式缓存预计算常见棋型的得分对称性利用旋转/镜像棋局可复用评估结果// 增量评估示例更新某一行 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_uniqueGameNode(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 性能优化技巧迭代加深先浅层搜索快速响应后台继续深层搜索多线程并行不同分支分配到不同线程开局库记忆常见开局模式置换表缓存已评估的棋局// 简单的多线程搜索示例 std::vectorstd::futureint 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 启发式搜索策略杀手启发优先尝试历史表现好的走法历史表记录各位置的历史得分静态搜索对关键局面延长搜索深度6.2 机器学习增强神经网络评估用CNN替代手工评估函数强化学习通过自我对弈提升策略蒙特卡洛树搜索结合随机模拟与树搜索6.3 工程实践建议使用位棋盘用64位整数压缩表示棋盘状态Zobrist哈希快速计算棋局哈希值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的魅力所在。