javascript - 查看棋盘游戏棋子是否已被捕获的逻辑(go)

Question

我正在开发棋盘游戏围棋的在线版本，这是一种日本游戏，玩家轮流将棋子放在网格上。当一名玩家的棋子被对手包围时，它们就会被摧毁。

这是我无法理解如何编程的逻辑。到目前为止，我已经制作了 2 个玩家的网格，其中所有石子的放置都存储在一个数组中。我将在此处添加一张图片，使其更加清晰

正如你所看到的，网格显示黑色有 2 个白色棋子包围，在这种情况下它们应该被摧毁，注意它可以是任意数量的包围棋子，但在这种情况下是 2 个。

在右侧，您还可以看到石头阵列，我将用它们来检查玩家是否已被包围。我尝试编写一些 pysudo 代码，但它变得一团糟并且过于复杂，这个任务真的那么复杂吗？我将如何做到这一点背后的任何建议或逻辑都会被采纳，所以如果网上有人做了类似的事情，那也会很好。我什至不确定像我所做的那样创建一个数组最终是最好的方法，所以如果有更好的方法请告诉我

Answer 1

我会推荐一种不同的数据模型——本质上是一个二维数组，分别保存值 0、+1 和 -1，分别表示空、黑色和白色。出于算法的目的，请维护“有自由”的 bool 值并行数组。

您的算法需要多次扫描棋盘。在扫描之前，当且仅当该位置被占用时，将位置的“具有自由”标志设置为 false。在每次扫描中，找到所有“has liberty”为 true 的单元格，并将左侧、右侧、顶部和底部的单元格标记为“has liberty”；如果该位置已被占用，则将此标记限制在相同颜色的相邻位置。当扫描后板上没有任何变化时，您就完成了。此时，所有带有“有自由”的假棋子都会被捕获并应该被移除。

这是一个简单、低效的算法。 GNU go 等围棋引擎拥有更复杂的算法，包括跟踪相连棋子的“链”或“组”及其自由数，然后在下棋时更新这些棋子。如果您打算编写一个围棋程序，当您读取不同的序列时，您将进行数千或数百万次这种计算，因此这种优化将变得至关重要。

请注意，您需要针对“ko”的情况以及类似的情况进行特殊的套管处理，在这种情况下，一颗棋子在看似“被捕获”的位置下棋，但由于它本身吃掉了其他棋子而得以幸存。 。如果只是简单地将取寇的棋子放在棋盘上，运行上面的算法，那么被取子和刚下的棋子都会被认为是吃子，这是错误的。因此，您需要为最近的棋子提供一个棋盘级变量，并考虑该棋子始终处于“有自由”状态，并具有适当的逻辑来处理非法移动。