★ FEATURED ARTICLE 聊到深度优先搜索很多人第一反应就是二叉树遍历或者迷宫寻路。最近我在完善一个围棋练习模块时发现用DFS实现围棋的吃子判定其实是很合适的入门题目——规则里藏着图连通性问题又不像寻路那样需要一大堆剪枝。我会从围棋里最容易被新手忽略的气讲起把棋盘翻译成图再用Python实现一套能吃子、能判自杀、能处理常见边界情况的代码最后把我实测踩过的坑一并整理出来。如果你刚开始啃DFS想找一个不套模板的实战场景或者正在写围棋对弈逻辑却卡在吃子判定上这组代码应该能给你不少参考。1. 从气到连通块先把吃子问题翻译成DFS能算的东西1.1 围棋里的气其实就是图的邻接空点围棋的气指一颗棋子或一整块同色棋子通过上下左右四条边直接相邻的空交叉点。角上的棋子最少只有2气边上的棋子3气中央的棋子4气。一旦某块棋的所有气都被对手棋子占满这块棋就要被整体提走。听起来很直观但实现时有个容易忽略的点棋盘上同色棋子只要上下左右连在一起就共享同一口气集合不能拆开单独算。这背后的原因是吃子规则针对的不是单颗棋子而是连通块。一块棋里的每个子可能各自挨着不同的空点但只要有任何一个空点与块内任意一颗子相邻这一整块就有气。所以判断吃子本质是判断这个连通块的外部空点集合是否为空。这个外部空点集合放到图论里就是一个连通分量边界上的空点集合。这也是为什么深度优先搜索天然适合这个场景从一颗棋子出发沿着同色棋子一直往下扩展就能把整个连通块完整找出来顺带把边界上的所有空点收进集合。一次遍历既拿到块又拿到气不需要额外的复杂结构。1.2 棋盘到图的映射节点、边和颜色把棋盘想象成一张图每个交叉点是一个节点上下左右四个方向是可能的边。空点、黑子、白子只是节点上的三种状态。同色棋子通过边连成连通块对弈过程中不断有节点从空变成某色也有一整块节点从某色变回空。用一个小局部来说明. X . X X O . X .中间由三颗黑子组成的块是一个连通块。这个块的气是左上、右上、左下、右下四个角上的空点。注意(1,0)位置的黑子虽然靠在白子旁边但白子不是气只是边界真正能决定这块黑棋死活的是那四个空点。对手子不需要遍历但空点必须要记录。在做DFS时规则可以简化成三条邻居是同色棋子继续往这个方向搜索邻居是空点记录为气邻居是对手棋子忽略当作墙。越界的情况同样忽略因为棋盘外的位置不可能是气。用代码实现时只要把这个规则写进搜索循环一条路走到黑再回头就能得到完整的连通块信息。2. 棋盘建模与输入输出约定先定好数据格式再写搜索2.1 棋盘表示二维列表、坐标与颜色常量写围棋逻辑我习惯用二维列表存棋盘board[r][c]表示第r行第c列的状态坐标从0开始。颜色用整数常量EMPTY 0BLACK 1WHITE 2。棋盘大小用全局变量N控制默认9路改成19路时只需要把N换掉。为什么不用一维列表虽然一维也能做坐标转下标需要r * N c在遍历上下左右邻居时稍不留神就会算错二维列表配合生成器写邻居遍历可读性高很多。对于吃子判定这个量级的逻辑性能根本不是瓶颈没必要为了省一点内存牺牲清晰度。还需要一个统一的邻居生成函数。以后不管是在吃子、提子还是判断眼位时都用同一个函数拿合法邻居def neighbors(r, c): for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc r dr, c dc if 0 nr N and 0 nc N: yield nr, nc这个函数的好处是把边界判断集中到一处搜索函数里不会到处都是越界检查。另外坐标的顺序一定不要搞混。我统一用(r, c)r是行c是列。如果你以后要和带图形界面的棋盘对接最好把逻辑层和界面层拆开逻辑层只认二维列表界面层自己负责坐标换算。这样命令行工具、Web后端、本地GUI都能复用同一套吃子逻辑。2.2 气的口径边界、空点和对手棋子的处理规则很多新手写吃子时会先把棋子周围的空点数量一个个数出来再看有没有气。这个思路在单颗棋子时没问题一旦遇到连通块就会漏算或者重复算。为了避免混乱我建议从一开始就用集合来管理气并且定死每个邻居的处理口径邻居状态处理方式同色棋子归入同一个连通块继续DFS空点加入气的集合对手棋子忽略作为边界越界忽略不是气这里最关键的一点是同一个空点可能挨着连通块里的多颗棋子但气只能算一次。举个简单例子两块同色棋子上下相连它们共同左边有一个空点这个空点就是整个块的一口气不能因为有两颗子挨着它就算两口气。用set收集气天然去重后面少踩很多坑。还要把隔着对手子不算气说清楚。对手棋子不是气但它是边界会阻止己方连通块继续扩展。DFS遍历时看到对手棋子不能压栈也不能记为气。你可能会想对手棋子旁边如果有空点要不要算成己方的气不算。气只和己方连通块直接相邻隔着对手子就不算。可以这样理解气的集合就是连通块的一圈外皮只数紧贴连通块的那一圈空点。棋盘上有些空点虽然离得很近但只要中间隔着棋子就不是这一块的气。这个口径一旦定下来DFS函数的结构也就固定了同色就压栈空点就进集合其他情况一律不处理。后面所有边界条件自杀、提子、气变化都基于这个基础搜索展开。3. 用Python实现DFS查气、找连通块、判断提子3.1 核心搜索函数从一颗棋子出发遍历整个连通块核心函数是collect_group输入棋盘、起点坐标和棋子颜色返回两个集合连通块里的所有坐标以及这个连通块的所有气。代码用显式栈模拟递归避免函数调用栈过深def collect_group(board, r, c, color): if board[r][c] ! color: return set(), set() group set() liberties set() stack [(r, c)] while stack: cr, cc stack.pop() if (cr, cc) in group: continue group.add((cr, cc)) for nr, nc in neighbors(cr, cc): val board[nr][nc] if val color and (nr, nc) not in group: stack.append((nr, nc)) elif val EMPTY: liberties.add((nr, nc)) return group, liberties整个逻辑非常直白从起点开始弹出坐标如果不是已经访问过的就加入group然后看四个邻居遇到同色加入栈遇到空点计入气。由于用set存储已访问坐标同一个点不会被重复处理。这也是DFS的标准写法沿着一条分支走到底遇到死路再回到栈里剩下的分支。理论上这一步用BFS也能做队列换成栈而已对于连通块遍历结果完全一样。我这里选DFS是因为它更贴近回溯扩展的直觉而且显式栈写起来比队列还少一个collections.deque的导入。3.2 吃子主流程落子后先数气再决定是否提子有了collect_group吃子主流程apply_move就很清晰了检查落点是否为空临时把棋子放上去遍历落点四个邻居如果是对方棋子就对它所在的连通块做DFS看气是否为0所有无气的对方连通块全部提走对自己刚下的位置再做一次DFS如果己方连通块无气而且本手没有提走任何对方棋子说明这是自杀回滚落子并返回失败。代码def apply_move(board, r, c, color): if not (0 r N and 0 c N): return False if board[r][c] ! EMPTY: return False opponent WHITE if color BLACK else BLACK board[r][c] color captured [] for nr, nc in neighbors(r, c): if board[nr][nc] opponent: group, libs collect_group(board, nr, nc, opponent) if not libs and group not in captured: captured.append(group) for group in captured: remove_group(board, group) _, my_libs collect_group(board, r, c, color) if not my_libs and not captured: board[r][c] EMPTY return False return Trueremove_group就是把集合里的坐标全部置为EMPTYdef remove_group(board, group): for r, c in group: board[r][c] EMPTY这个顺序是吃子判定的命门必须先提对方、再判己方。如果先判断己方有没有气很多提子后自己才有气的合法落子会被误判成禁入点。比如黑棋填进白棋包围圈的空点原本没气但落子后能把外围白棋提掉黑棋立刻获得气这手棋在正式规则里是合法的。3.3 完整可运行的示例代码把上面的函数拼在一起再加一个简单的打印函数就可以跑一个吃子演示。我摆了一个局面三颗白子组成的连通块只剩一个气点黑棋落在这个气点上应该把白棋整块提走。N 9 EMPTY, BLACK, WHITE 0, 1, 2 def neighbors(r, c): for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc r dr, c dc if 0 nr N and 0 nc N: yield nr, nc def collect_group(board, r, c, color): if board[r][c] ! color: return set(), set() group set() liberties set() stack [(r, c)] while stack: cr, cc stack.pop() if (cr, cc) in group: continue group.add((cr, cc)) for nr, nc in neighbors(cr, cc): val board[nr][nc] if val color and (nr, nc) not in group: stack.append((nr, nc)) elif val EMPTY: liberties.add((nr, nc)) return group, liberties def remove_group(board, group): for r, c in group: board[r][c] EMPTY def apply_move(board, r, c, color): if not (0 r N and 0 c N): return False if board[r][c] ! EMPTY: return False opponent WHITE if color BLACK else BLACK board[r][c] color captured [] for nr, nc in neighbors(r, c): if board[nr][nc] opponent: group, libs collect_group(board, nr, nc, opponent) if not libs and group not in captured: captured.append(group) for group in captured: remove_group(board, group) _, my_libs collect_group(board, r, c, color) if not my_libs and not captured: board[r][c] EMPTY return False return True def print_board(board): symbol {EMPTY: ., BLACK: X, WHITE: O} for row in board: print( .join(symbol[val] for val in row)) board [[EMPTY] * N for _ in range(N)] # 白棋三子 board[3][3] WHITE board[3][4] WHITE board[4][3] WHITE # 黑棋包围其他方向 board[2][3] BLACK board[2][4] BLACK board[3][2] BLACK board[3][5] BLACK board[4][4] BLACK board[5][3] BLACK print(落子前) print_board(board) ok apply_move(board, 4, 2, BLACK) print(\n黑棋在(4,2)落子:, 成功白棋被提 if ok else 不合法) print(落子后) print_board(board)运行后能看到中间的三颗白子变成空点(4,2)位置变成黑子。这个演示虽然小但已经覆盖了连通块查找、气的统计、整块提子、落子合法性判断这几条主干逻辑。说实话这段代码把DFS的作用体现得很清楚白棋三子是一个连通块DFS一次遍历就找到了全部三颗白子同时发现它们的气集合只有(4,2)这一个点黑棋一落子气集合法变成空集于是整个块被提掉。中间不需要额外的区域划分也不需要判断哪颗白子先死整块处理正是规则要求。4. 边界条件才是重头戏自杀、提子连锁和劫4.1 自杀落子为什么必须禁止正式围棋规则里落子后如果己方连通块没有气而且不能提掉对方的子这个点叫禁入点不能落子。翻译成代码就是collect_group检查自己刚下的位置my_libs为空且captured为空回滚并返回False。举例来说一块白棋围出一个空点周围完全没有黑子黑棋如果下进去刚落下的那颗黑子旁边全是白棋气为0属于自杀。这时候如果只做落下后看自己有没有气的判断这手棋会被拒绝逻辑是对的。但要注意正式规则里自杀和提子要一起判断如果落子后自己无气但能把周围一块白棋提掉那这手棋合法。因为提掉白棋后空出来的点会变成黑棋的气。先提对方再查己方顺序一错就会把合法对局中的提子变成非法手。4.2 提子后周围棋子的气怎么重算我们目前的实现每次都是实时DFS现算不存在缓存过期的问题所以提子后不需要额外做气刷新。但如果你以后为了提高性能给每个连通块维护一个气集合那提子后的重算就绕不开。提子以后的局部重算并不复杂找到被提掉的每个空点看这四个方向。如果某一方向是黑棋就对这个黑棋连通块重新collect_group覆盖缓存如果某一方向是白棋也同样处理。被提掉的区域原本压着对手棋子的气现在变成了空点这些空点会立刻成为相邻己方棋子或剩余对方棋子的气必须更新。可以理解为每一次提子等于在棋盘上新增了几个空节点空节点会改变附近连通块的边界。实时DFS天然规避了这个维护成本换来的是每次少量重复计算。在9路、13路乃至19路人机对弈场景里这点计算量完全可以接受。4.3 劫争检测最简单可靠的实现思路劫是围棋规则里最容易让代码出问题的部分。完整劫争要判断历史局面是否重复简单模块里其实可以分层处理先做一手劫再考虑升级成历史局面集合。一手劫的检测思路是记住上一手被提掉的那个位置。如果当前落子点正好等于上一手被提位置并且本手也有提子就禁止立即提回。这个规则能挡住最常见的单劫循环代码也不复杂。在实际实现时可以把上一手被提位置存成last_capture None。调用apply_move后如果captured长度为1再更新last_capture。下一手开始时检查落子坐标是否等于last_capture如果等于且本手也有提子就拒绝这手棋。这个判断虽然不能覆盖所有全局同形但挡住最常见的循环劫已经足够。如果之后要处理更复杂的劫争更接近正式规则的做法是历史局面检测每次落子后把棋盘序列化成字符串或元组存进集合如果新盘面在历史中出现过就判定落子非法。代价是要存整局历史落子频率高时内存会上涨。对于吃子模块来说一手劫已经够用。5. 实测中反复踩过的坑递归、重复计数与提子顺序5.1 递归深度会不会爆Python的递归限制够用吗我最早写这个模块时用的是递归DFS看起来更简洁def dfs(board, pos, color, group, libs): ...但写完后总会习惯性想一下最深递归多少层19路棋盘最多361个点默认递归上限1000理论上是安全的。不过要是棋盘扩展得更大或者你在递归函数里又嵌套了其他递归逻辑很容易踩到RecursionError。所以我后来改成显式栈。显式栈没有函数调用深度的问题唯一要注意的是pop后检查是否已访问过。这个改动会让代码稍微长几行但稳定性更好。如果你确实喜欢递归写法也可以在模块开头sys.setrecursionlimit(10000)兜底不过显式栈是更干净的答案。5.2 气重复统计导致假活棋这是我在实际测试中遇到的最典型的逻辑坑。早期版本我用list收集气结果出现一个诡异现象明明棋盘上有一块棋只剩一口气程序却认为它有两气导致该吃掉的子没有被吃掉。原因很简单两个同色棋子横排连在一起白棋把它们的上、下、右三面全部封死左边只剩一个空点。这个空点同时是两个黑子的邻居如果收集气时用list每个黑子各记录一次就会得到2气的错误结果。实际上这个黑块只有一口气白棋落在那个空点上黑块就该被提走。换成set后问题立刻消失。这件事给我的教训是围棋里的气是连通块对外部空点的邻接关系不是棋子与空点的接触次数。凡是算连通块边界属性的场景先想清楚要不要去重。5.3 提子顺序和先提后查的连锁影响另一个常见错误是对多个无气块只提一个。落子可能同时让两个互不相连的对手连通块变成无气比如落在一个关键分割点上左右两块对手棋同时被切断最后一口气。如果循环里提到一块就break另一块会残留下来后续所有气的判断全部错乱。我的处理方式是把所有无气块收集到captured列表最后统一移除。为什么可以统一移除因为提掉对方棋子只会把棋盘上的棋子变成空点不会减少其他对方连通块的气所以先提后提不会影响哪些块没气这个结论。唯一要注意的是如果同一个连通块通过两个方向同时被检查到可能被重复加入列表用group not in captured或者直接维护一个已处理集合就能避免。还有那个先提后查的问题判断己方是否自杀必须在所有提子完成之后。我第一次写反了导致黑棋提子时偶尔被拒绝后来把逻辑顺序调整过来所有测试用例才通过。6. 性能优化与扩展思路从演示代码到可用模块6.1 用visited复用代替频繁新建集合当前实现每次collect_group都会新建两个set。在19路棋盘上单次落子最多会影响落子点周围的几个连通块每次搜索的规模也不会超过整块棋的大小性能完全够。但如果你要做蒙特卡洛模拟或者大量对局推演频繁创建集合确实能感觉到开销。优化的方向是复用visited标记。可以准备一个二维数组再维护一个递增的visit_token搜索时如果访问到已带当前token的坐标就跳过否则打上token。这样不需要每次清空标记数组相当于用递增编号代替清空动作。气的集合还是可以复用同一个set搜索前清空一次即可。这种优化对新手来说不是必须但理解以后再看到为什么搜索函数里有个全局计数器就不会觉得奇怪了。6.2 记录每块棋的气集合落子后增量更新如果想把吃子逻辑做成真正可用的棋盘引擎更工程化的数据结构是给每个连通块维护一个块ID和气集合棋盘格子里记录块ID。每次落子新棋子要么加入相邻的同色块要么新建一个块它占据的空点会从相邻对手块的气集合中移除提子后新增的空点再被加入周围所有块的气集合。好处是单次落子不需要再扫描大片区域只需要处理受影响的那几个块。代价是要小心处理块合并、块分裂后的气集合维护代码复杂度明显上升。对弈程序里只要不是做大规模批量推演实时DFS其实更不容易出错所以我建议先跑通实时版本确认性能和正确性瓶颈后再决定要不要上增量更新。6.3 后续扩展眼位、死活判断、吃子提示吃子判定跑通之后可以很自然地往外扩展。比如吃子提示功能遍历所有空点调用apply_move模拟落子统计返回值里captured的长度就能得到棋盘上所有能吃子的位置。9路棋盘81个空点每手最多81次搜索毫秒级就能出结果给终端用户做提示很合适。再进一步可以做眼位判断和死活判断。眼位判断需要分析空点区域是不是真眼涉及对角线和边角规则比气的搜索复杂一些死活判断则要组合找连通块、找空点区域、试探落子这几个步骤。这些方向的底子都是今天讲的DFS连通块遍历。掌握了吃子判定后续功能更像是搭积木。最后再分享一个调试小技巧写这种棋盘逻辑时只看返回值很难发现问题一定要把棋盘打印成字符画并且在边缘加上行列坐标。我调试提子逻辑时经常先在纸上画出预期棋盘再用代码输出对比很多看似灵异的Bug其实只是坐标差了一行或者空点数重复了。把打印函数写好排查效率能提升一大截。
阅读完成 · 觉得有帮助？
