javascript - 棋盘游戏获胜情况 - 搜索算法

Question

我正在寻找可能有效的算法来检测在 19x19 棋盘上玩的五子棋(五连胜)游戏中的“获胜”情况。当其中一名玩家设法连续获得五颗且不超过五颗“石头”(水平、对 Angular 或垂直)时，就会发生获胜情况。

我可以轻松访问以下数据:

• 存储在二维数组(也可以是 json 符号对象)中的两个玩家之前的移动(“石头”)，变量“B”和“W”来区分玩家，
• 传入移动的“坐标”(move.x，move.y)，
• 每个玩家的 Action 数

我是用 javascript 做的，但任何不使用低级内容(如内存分配)或高级(python)数组操作的解决方案都是好的。

我发现了类似的问题(Detect winning game in nought and crosses)，但那里给出的解决方案仅适用于小板(5x5 等)。

Answer 1

没有过多循环的简单易懂的解决方案(仅提供伪代码，如果您需要更多解释，请告诉我):

我假设你的二维数组是这样运行的:

board = [
   [...],
   [...],
   [...],
   ...
];

即内部数组代表棋盘的水平行。

我还假设数组由“b”、“w”和“x”填充，分别代表黑色 block 、白色 block 和空方 block 。

我的解决方案有点分而治之，所以我将其分为以下 3 种情况。请耐心等待，一开始它看起来可能比简单地运行多个嵌套循环更复杂，但这个概念很容易理解和阅读，并且使用正确的方法，代码也非常简单。

水平线

让我们首先考虑仅当线是水平的情况下检测获胜情况的情况 - 这是最简单的。首先，使用类似 board[0].join("") 的方法将一行连接成一个字符串。对每一行执行此操作。你最终得到这样一个数组:

rows = [
   "bxwwwbx...",
   "xxxwbxx...",
   "wwbbbbx...",
   ...
]

现在加入这个数组，但在元素之间插入一个“x”来分隔每一行:rows.join("x")。

现在您有一个代表您的棋盘的长字符串，只需应用正则表达式来查找长度正好为 5 的连续“w”或“b”:superString.test(/(b{5, 5})|(w{5,5})/)。如果测试返回 true，那么您就赢了。如果没有，让我们转到垂直线。

垂直线

你想重用上面的代码，所以为它创建一个函数testRows。测试垂直线的过程完全相同，但您要转置 板，以便行变为列，列变为行。然后应用相同的 testRows 函数。转置可以通过将值复制到一个新的二维数组中来完成，或者通过编写一个简单的 getCol 函数并在 testRows 中使用它来完成。

对 Angular 线

同样，我们要重用 `testRows' 函数。像这样的对 Angular 线:

b x x x x
x b x x x
x x b x x
x x x b x
x x x x b

可以转换成这样的垂直:

b x x x x
b x x x
b x x
b x
b

通过将 i 行移动 i 位置。现在是移调的问题，我们又回到了水平测试。您需要对相反方向的对 Angular 线执行相同的操作，但这次将行 i 移动 length - 1 - i 位置，或者在您的情况下，18 - i 个位置。

函数式javascript

附带说明一下，我的解决方案非常适合函数式编程，这意味着如果您有函数式编程工具，可以很容易地对其进行编码，尽管这不是必需的。我建议使用 underscore.js因为在许多不同的游戏算法中，您很可能需要基本工具，例如 map、reduce 和 filter。例如，我关于测试水平线的部分可以使用 map 用一行 javascript 编写:

_(board).map(function (row) {return row.join("")}).join("x").test(/(b{5,5})|(w{5,5})/);