计算游戏“GO”的分数

Question

有没有人知道如何以编程方式计算Go游戏中的分数？ 我有一个19x19的数组，这个数组的每个元素可以是0（空点），1（黑色石头）或2（白色石头）。我不明白我如何检查该区域属于任何颜色。

Answer 1

这是一个不平凡的问题，因为通常Go游戏会在玩家完成必要的所有动作之前结束，以明确游戏的“真实”分数/值。有时候，假设一个玩家未达到最佳状态（例如，让对手完成一套在对手领土内有生命的宝石，即使可能杀死一组宝石），游戏的价值也会不同。计算原始未入侵区域相当明显，只需通过棋盘边缘或一种颜色的棋子检查每个可能的方向组合（正面和负面的水平和垂直）中的每个空间是否“切断”。您可以通过从空白处开始宽度优先搜索来更高效地执行此操作，并且可以跟踪处理过程中遇到的哪些颜色（不会从占用的斑点遍历BFS），并且一旦找不到更多的空白斑点，那么如果发现的彩色片都是一种颜色，那么发现的所有空白区都属于该颜色，否则它们不属于任何人。然后继续广度优先搜索与下一个未被发现的空白点，删除所有以前探索的空白点。但是，如果对手在已经建立的领土上有一块棋子，那么在计算领土时理想情况下应该忽略这块棋子，事实上甚至被视为被俘。如果显而易见的是，如果玩家在没有犯错的情况下玩出一组对手的棋子，那么他们最终会被抓住。如果两个球员都有一组棋子与另一个棋子相邻，那么情况就更加微妙了，这样棋子就具有了“相互的生命”，即如果一个棋手试图做出努力杀死对方的棋子，那么对手将能够杀死原始棋手的棋子，反之亦然。