C++实现围棋游戏：从数据结构到DFS算法实战

1. 项目概述为什么用C写一个简单的围棋游戏如果你学过C并且已经厌倦了在控制台里打印“Hello World”或者写一些简单的计算器那么用C来开发一个简单的围棋游戏会是一个绝佳的练手项目。这听起来可能有点唬人毕竟围棋规则复杂AI更是深不可测。但别担心我们这里谈的“简单”指的是一个具备完整棋盘交互、基础规则判定如气、提子的本地双人对战程序不涉及任何网络功能和AI算法。它的核心价值在于能让你把C里那些看似枯燥的语法——类与对象、STL容器、算法逻辑——在一个有趣且有明确目标的场景里串联起来真正理解面向对象编程和状态管理。为什么是C而不是Python或者Unity对于学习底层逻辑和控制力来说C是无可替代的。用C从头构建意味着你需要亲自管理棋盘这个“二维世界”里的每一个状态设计棋子如何落下如何判断一片棋子的生死气。这个过程会强迫你思考数据结构和算法效率比如用std::vector还是原生数组表示棋盘如何递归遍历一片相连的棋子。当你用几十行代码实现“提子”逻辑并看到棋子从棋盘上消失时那种对程序掌控感的理解是使用现成游戏引擎很难获得的。这个项目适合谁主要面向有一定C基础了解类、STL、基本指针概念的初学者或希望巩固中级知识的开发者。它不像大型游戏引擎项目那样需要庞大的前置知识目标明确每一步都有可视化的反馈成就感来得非常直接。最终你将得到一个运行在控制台或简单图形界面如SFML下的、可以两人轮流落子、自动提子、判定基本禁着点的围棋程序。接下来我们就从零开始拆解这个项目的每一个核心环节。2. 核心设计思路与架构规划在动手写代码之前花点时间规划整体架构至关重要。一个混乱的结构会让后续添加功能比如悔棋、存盘变得举步维艰。我们的核心设计目标是清晰的数据层、独立的规则逻辑、可替换的交互界面。2.1 核心数据结构选型如何表示棋盘与棋子棋盘本质上是一个19x19标准尺寸的网格每个交叉点有三种状态空、黑子、白子。最直观的表示方法是一个二维数组。在C中我们有几种选择原生二维数组int board[19][19];。简单直接但大小固定传递时需要小心指针和数组衰减问题。std::vectorstd::vectorint动态二维向量。更灵活内存自动管理但访问效率稍低于原生数组且每行是一个独立的vector对象。一维数组模拟二维int board[19*19];通过board[row * 19 col]访问。内存连续缓存友好效率高但可读性稍差。对于这个规模的固定棋盘我推荐使用原生二维数组并将其封装在一个类内部。理由很简单性能足够好代码直观且棋盘尺寸在游戏生命周期内不会改变。我们将使用枚举来定义格子状态比直接用0,1,2更清晰。// 定义棋子颜色 enum class Piece { EMPTY, BLACK, WHITE }; class Board { private: static const int BOARD_SIZE 19; Piece grid[BOARD_SIZE][BOARD_SIZE]; // 核心棋盘数据 // ... 其他成员 };2.2 面向对象的核心类设计我们将系统划分为几个核心类遵循单一职责原则Board棋盘类核心数据持有者。负责存储棋盘状态提供落子、查询某位置状态、获取棋盘副本用于规则检查而不修改原棋盘等基础接口。它不应该包含复杂的规则逻辑。GameRule规则类规则引擎。这是大脑依赖Board提供的数据进行所有逻辑判断。核心功能包括bool isLegalMove(int x, int y, Piece color)判断落子是否合法是否在棋盘内、是否为空位、是否违反禁着点规则等。std::vectorstd::pairint, int getGroupAndLiberties(int x, int y)找到(x,y)处棋子所属的连通块并计算其“气”相邻的空位。这是判断生死和提子的基础。void removeDeadGroup(int x, int y)移除一块无气的死子。Game游戏主控类协调者。它拥有一个Board实例和一个GameRule实例。控制游戏流程当前轮到谁、处理玩家输入、调用规则类判断、更新棋盘状态、判断终局条件等。Renderer渲染器接口/类负责显示。为了保持核心逻辑的纯净我们将显示部分抽象出来。可以有一个控制台渲染器用字符,X,O画棋盘未来也可以轻松替换为SFML或Qt图形渲染器。这种设计的优势在于高内聚、低耦合。规则变了只改GameRule。想换图形界面实现一个新的Renderer。棋盘数据结构想优化主要改动集中在Board内部。这对于学习和后续扩展都非常友好。2.3 游戏主循环逻辑游戏的核心是一个循环直到对局结束。每一轮循环包括渲染清屏通过Renderer绘制当前棋盘和状态信息如“当前黑方落子”。输入获取当前玩家输入的坐标。在控制台版本中这可能是像“H8”这样的字母数字组合需要解析为数组索引(7,7)。验证Game将坐标和玩家颜色传递给GameRule::isLegalMove进行验证。执行如果合法Game调用Board::placePiece落子。提子检查落子后需要检查新落子周围对方棋子的块是否无气如果有则调用GameRule::removeDeadGroup提走。同时也要检查本方棋子因为落子可能填满自己的气属于自杀通常是非法的但需结合规则细节。切换玩家回合交替。终局判断通常需要双方连续Pass才判定终局我们可以用一个consecutivePasses计数器来实现。这个清晰的流程就是Game::run()方法的主要内容。3. 核心算法深度解析如何判断“气”与“提子”这是围棋程序最核心、也最具挑战性的部分。规则的所有复杂性几乎都源于“气”的概念。我们需要实现一个算法能够找到棋盘上任意位置棋子所属的连通块并准确计算出这个块还有多少口“气”。3.1 连通块搜索算法深度优先搜索DFS围棋棋盘可以看作一个无向图每个棋子是一个节点与它上下左右四个方向的同色棋子有边相连。寻找连通块就是一个图遍历问题。深度优先搜索DFS在这里非常合适它实现简单逻辑直观。我们为GameRule类实现一个私有方法dfsFindGroup// 辅助函数深度优先搜索寻找同色连通块 void GameRule::dfsFindGroup(int x, int y, Piece color, std::vectorstd::pairint, int group, bool visited[][BOARD_SIZE]) { // 边界检查、颜色检查、访问标记检查 if (x 0 || x BOARD_SIZE || y 0 || y BOARD_SIZE) return; if (board.getPieceAt(x, y) ! color) return; if (visited[x][y]) return; // 标记为已访问并加入当前块 visited[x][y] true; group.push_back({x, y}); // 递归搜索四个方向 dfsFindGroup(x - 1, y, color, group, visited); // 上 dfsFindGroup(x 1, y, color, group, visited); // 下 dfsFindGroup(x, y - 1, color, group, visited); // 左 dfsFindGroup(x, y 1, color, group, visited); // 右 }这个函数会从起始点(x,y)开始“钻”到底把所有连在一起的同色棋子坐标收集到group向量中。实操心得这里visited数组必须作为参数传递或定义为类成员以确保在递归过程中共享访问状态。直接在每个递归调用里创建局部数组是行不通的会导致重复访问和栈溢出。另一种更C的方式是使用std::unordered_set来存储已访问的坐标点但用二维数组在性能上通常更优。3.2 “气”的计算与生死判定找到一块棋后如何计算它的“气”气就是与这块棋中任意一颗棋子相邻的空交叉点。注意是“相邻”而不是“相连”。计算逻辑可以在DFS过程中同步进行也可以遍历找到的连通块来计算。后者更清晰// 计算一个棋子连通块的气相邻的空位 std::vectorstd::pairint, int GameRule::getLiberties(const std::vectorstd::pairint, int group) { std::vectorstd::pairint, int liberties; bool libertyVisited[BOARD_SIZE][BOARD_SIZE] {{false}}; // 避免重复计数同一个空位 for (const auto pos : group) { int x pos.first, y pos.second; // 检查四个方向的邻居 int directions[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (auto dir : directions) { int nx x dir[0]; int ny y dir[1]; if (nx 0 nx BOARD_SIZE ny 0 ny BOARD_SIZE) { if (board.getPieceAt(nx, ny) Piece::EMPTY !libertyVisited[nx][ny]) { liberties.push_back({nx, ny}); libertyVisited[nx][ny] true; } } } } return liberties; // 返回所有唯一的气的位置 }生死判定就变得极其简单如果liberties为空向量则该块棋为死棋需要被提走。这就是removeDeadGroup方法的理论基础传入一块棋的坐标向量将其中所有棋子在棋盘上设为EMPTY。3.3 禁着点Ko Rule与自杀规则的处理围棋有特殊的禁着点规则最常见的是“劫争”Ko。简单来说你不能立即落子去提回对方刚提掉你一颗子后形成的那个形状因为会导致无限循环。实现一个完整的劫争规则需要记录上一步的棋盘状态比较复杂。在初级版本中我们可以选择暂时不实现劫争或者实现一个简化的“全局棋盘状态重复禁止”规则即不允许落子后使棋盘状态与之前任何一步相同但这会误杀一些合理的循环局面。更基础且必须实现的是自杀规则落子后如果该子所在的本方连通块没有气且没有提掉任何对方棋子则此着法非法。我们的isLegalMove函数逻辑顺序应该是位置是否为空且在棋盘内临时落子在一个棋盘副本上放下这颗子。检查这颗子是否直接提掉了对方的棋子即检查新子周围对方棋块的气。如果提掉了对方棋子则着法合法即使本方新块可能无气但因为提子了所以是合法的。如果没有提掉任何对方棋子则检查新子所在的本方棋块是否有气。无气则为非法自杀。注意事项第2步的“临时落子”至关重要你不能直接在真实棋盘上尝试因为如果着法非法你需要回滚。这就是为什么GameRule需要能够接收一个棋盘状态通常是Board对象的引用或常量引用来进行计算而不是直接修改游戏主棋盘。这也体现了之前架构设计的优越性。4. 从零开始的完整实现步骤理论说够了我们开始动手。假设你使用VS Code MinGW或Visual Studio作为开发环境。4.1 项目结构与环境搭建首先创建一个项目文件夹例如GoGame。在里面创建以下源文件和头文件GoGame/ ├── main.cpp // 程序入口 ├── Board.h / .cpp ├── GameRule.h / .cpp ├── Game.h / .cpp ├── ConsoleRenderer.h / .cpp // 控制台渲染器 └── common.h // 公共定义如Piece枚举 BOARD_SIZE常量在common.h中定义全局常量// common.h #pragma once #ifndef COMMON_H #define COMMON_H const int BOARD_SIZE 9; // 初学者建议从9路小棋盘开始19路棋盘测试起来太耗时 enum class Piece { EMPTY, BLACK, WHITE }; #endif使用9路棋盘开始开发能极大加快编译-运行-测试的循环速度。功能完善后再改为19路。4.2 Board类的实现Board类是基石必须健壮。// Board.h #pragma once #include common.h #include array class Board { public: Board(); Piece getPieceAt(int x, int y) const; // const方法不修改对象状态 bool placePiece(int x, int y, Piece piece); // 落子返回是否成功 bool isEmptyAt(int x, int y) const; // 提供一个获取棋盘状态拷贝的方法用于规则计算 std::arraystd::arrayPiece, BOARD_SIZE, BOARD_SIZE getGridSnapshot() const; void clear(); // 清空棋盘 private: std::arraystd::arrayPiece, BOARD_SIZE, BOARD_SIZE grid; // 使用std::array更现代安全 };在Board.cpp中实现这些方法。注意边界检查// Board.cpp #include Board.h #include cassert Board::Board() { clear(); } void Board::clear() { for (auto row : grid) { row.fill(Piece::EMPTY); } } Piece Board::getPieceAt(int x, int y) const { // 生产代码应有更优雅的错误处理这里用assert便于调试 assert(x 0 x BOARD_SIZE y 0 y BOARD_SIZE); return grid[x][y]; } bool Board::placePiece(int x, int y, Piece piece) { if (x 0 || x BOARD_SIZE || y 0 || y BOARD_SIZE) { return false; } if (grid[x][y] ! Piece::EMPTY) { return false; } grid[x][y] piece; return true; }使用std::array替代原生数组提供了更好的类型安全和边界意识虽然operator[]仍不检查边界但结合assert或at()方法可以更安全。4.3 GameRule类的实现填充算法骨架这是最复杂的部分。头文件需要设计好接口// GameRule.h #pragma once #include common.h #include Board.h #include vector #include utility // for std::pair class GameRule { public: // 构造函数接收一个棋盘引用规则基于此棋盘进行判断 explicit GameRule(const Board boardRef); // 核心公共接口 bool isLegalMove(int x, int y, Piece color) const; std::vectorstd::pairint, int getGroupAndLiberties(int x, int y) const; // 注意removeDeadGroup 通常不直接公开由Game类在确认后调用Board执行 std::vectorstd::pairint, int findDeadGroup(int x, int y) const; // 找出一块死棋 private: const Board board; // 引用不拥有所有权只是观察者 // 私有DFS递归函数 void dfsFindGroup(int x, int y, Piece color, std::vectorstd::pairint, int group, bool visited[][BOARD_SIZE]) const; // 计算一块棋的气 std::vectorstd::pairint, int getLiberties(const std::vectorstd::pairint, int group) const; };在GameRule.cpp中实现isLegalMove是重中之重。按照之前讨论的逻辑检查坐标是否有效、是否为空。创建棋盘状态的临时拷贝可以通过Board::getGridSnapshot获得或者更优的做法是让GameRule的构造函数接收一个状态快照而非实时棋盘引用。这里为简单起见我们仍用引用但在isLegalMove内部模拟落子时需格外小心。模拟落子。检查是否提吃对方棋子。检查本方棋子是否有气。由于涉及模拟落子一个更清晰的实现是让GameRule的所有方法都基于一个Board的常量引用而isLegalMove返回一个MoveResult结构体其中包含是否合法、以及如果合法需要提掉哪些对方棋子等信息。这样实际的落子和提子操作由Game类根据这个结果来执行逻辑分离得更干净。4.4 ConsoleRenderer与Game主控类的实现ConsoleRenderer负责把抽象的棋盘数据变成人类能看的字符。// ConsoleRenderer.h #pragma once #include Board.h class ConsoleRenderer { public: void render(const Board board, Piece currentPlayer); };实现时可以用‘’表示交叉点‘B’或‘●’表示黑子‘W’或‘○’表示白子。顶部和左边标注行列号1-19或A-T。Game类则串联一切// Game.h #pragma once #include Board.h #include GameRule.h #include ConsoleRenderer.h class Game { public: Game(); void run(); // 主游戏循环 private: Board board; GameRule rule; ConsoleRenderer renderer; Piece currentPlayer; int consecutivePasses; bool gameOver; void switchPlayer(); bool processMove(int x, int y); bool processPass(); void checkGameOver(); };在Game::run()的循环中调用renderer.render(board, currentPlayer)然后等待输入。输入解析可以将“H8”解析为(7,7)如果H是第8列。输入“PASS”则跳过一手。调用processMove处理落子它内部会调用rule.isLegalMove如果合法则更新棋盘并调用rule.findDeadGroup找到需要提掉的棋子通过board.placePiece(..., Piece::EMPTY)提子。4.5 主函数与编译运行main.cpp非常简单#include Game.h int main() { Game goGame; goGame.run(); return 0; }使用CMake或直接命令行编译。例如用gg -stdc17 -o go_game.exe main.cpp Board.cpp GameRule.cpp Game.cpp ConsoleRenderer.cpp然后运行./go_game.exeLinux/macOS或go_game.exeWindows一个简单的双人围棋对弈程序就启动了。5. 常见问题、调试技巧与进阶方向即使按照步骤实现你也一定会遇到各种bug。这里分享一些我踩过的坑和调试技巧。5.1 常见问题速查表问题现象可能原因排查思路落子后程序崩溃段错误数组越界访问。1. 检查所有board[x][y]的访问x,y是否在[0, BOARD_SIZE-1]范围内。2. 在Board::getPieceAt等函数入口添加断言或边界检查并打印日志。3. 检查DFS递归的终止条件确保不会“走”出棋盘。提子逻辑错误不该提的提了该提的没提“气”的计算有误或生死判定逻辑顺序错误。1. 写一个单元测试函数打印出特定棋形下某块棋的“气”的位置肉眼核对。2. 确认isLegalMove中“检查是否提吃对方棋子”的逻辑优先于“检查本方是否有气”。3. 注意“气”的重复计数问题使用visited数组确保每个空位只算一次。自杀规则无效可以下在没气的地方isLegalMove中自杀检查的条件判断有误或临时落子模拟出错。1. 在isLegalMove内部模拟落子后先计算新子周围对方棋块的气如果为0则提吃该着法合法。2. 只有在没有提吃的情况下才去计算新子所在本方棋块的气如果为0则判定为自杀非法。3. 确保模拟落子是在一个独立的棋盘副本上进行的不影响真实棋盘。游戏无法结束或结束条件太容易触发终局判断逻辑有缺陷。标准的终局是双方连续Pass。实现一个consecutivePasses计数器任何一方落子就清零只有双方都Pass才加1。当consecutivePasses 2时判定终局。棋盘显示错乱ConsoleRenderer的行列打印逻辑错误或坐标转换输入解析错误。1. 在render函数里先打印一个固定的简单棋盘如全空测试显示逻辑。2. 将输入的字符串如“H8”和转换后的整数坐标(x,y)打印出来确认对应关系正确。记住数组索引通常从0开始而棋盘坐标从1或A开始。5.2 调试技巧可视化与单元测试对于棋盘游戏最好的调试工具就是可视化。不要只依赖内存中的数据。在关键函数中添加调试打印例如在getLiberties函数里打印出传入的棋块坐标和计算出的气坐标。在isLegalMove里打印出每一步的合法性检查结果。实现一个debugPrintBoard函数接受一个Board或网格状态用简单字符打印出来。在模拟落子前后分别调用它可以清晰看到棋盘状态的变化。编写小型单元测试针对特定棋形测试你的核心算法。例如写一个函数设置一个“叫吃”的棋形对方一块棋只剩一口气然后测试你的findDeadGroup是否能正确找出这块棋。void testCapture() { Board b; // 手动摆一个黑棋包围一颗白棋的棋形 b.placePiece(0, 1, Piece::BLACK); b.placePiece(1, 0, Piece::BLACK); b.placePiece(1, 1, Piece::WHITE); // 这颗白棋只有一口气在(0,0) b.placePiece(1, 2, Piece::BLACK); b.placePiece(2, 1, Piece::BLACK); GameRule rule(b); auto deadGroup rule.findDeadGroup(1, 1); // 应该能找到(1,1)处的白棋 assert(deadGroup.size() 1 deadGroup[0] std::make_pair(1, 1)); std::cout Capture test passed!\n; }5.3 项目进阶方向当基础版本运行稳定后你可以选择以下方向进行深化每个方向都能学到新东西实现图形界面用SFML或SDL2替换ConsoleRenderer。学习如何处理窗口、事件、绘制基本图形圆、线。这会让你的游戏瞬间变得专业。加入存盘/读盘功能将棋盘状态Piece枚举值保存到文件。可以设计简单的文本格式如用.B,W字符也可以学习简单的二进制序列化。这涉及到文件I/O和持久化。实现悔棋Undo这需要你记录每一步的棋盘历史。最简单的是在Game类里用一个std::vectorBoardSnapshot。每走一步合法棋或Pass前将当前棋盘快照压入栈中。悔棋时弹出栈顶并恢复。注意提子的情况也要完整记录。引入简单AI这是一个巨大的跨越。可以从完全随机落子开始。然后实现一个基于规则的AI比如优先占角、守边。再进一步可以尝试实现蒙特卡洛树搜索MCTS的极简版本这是现代围棋AI的基石之一虽然深度不如神经网络但足以在9路棋盘上产生有趣的对抗。完善围棋规则实现真正的劫争Ko规则。这需要记录上一步的棋盘状态或上一步提子后的状态并在isLegalMove中增加检查。还可以尝试实现眼位的判断以及日本规则或中国规则的终局计分。这能让你对围棋规则的理解达到一个新的高度。开发这样一个项目最大的收获不是最终的程序而是这个过程中你被迫去思考、设计、调试和解决问题的完整经历。从数据表示到算法实现从控制台到可能的图形界面每一步都是对C编程能力的扎实锻炼。当你看到两个玩家能在你的程序里进行一场有基本规则约束的围棋对弈时那种成就感远非一个课后习题可比。