棋盘游戏的获胜策略 - 搜索算法

Question

我正在寻找一种可能有效的算法，用于检测在一个19x19的五子棋游戏中“胜利”的情况。当其中一名玩家成功地在水平、对角线或垂直方向上连成五颗棋子，且不再多于五颗时，就会出现胜利的情况。

我可以轻松地访问以下数据：

- 存储在2D数组（也可以是JSON对象）中的双方玩家的先前移动（"棋子"），使用变量"B"和"W"来区分彼此。 - "坐标"的输入移动（move.x，move.y）， - 每个玩家的移动次数。

我正在使用JavaScript进行操作，但任何不使用底层（如内存分配）或更高级别（Python）数组操作的解决方案都可以。

我已经找到了类似的问题（在井字游戏中检测胜利），但给出的解决方案仅适用于小型棋盘（5x5等）。

- wildcard

---

“在井字棋游戏中检测获胜”问题的答案实际上非常适合您的问题。” - Glenner003

Answer 1

以下是通俗易懂的解决方案，没有过多循环（只提供伪代码，如果需要更多解释，请告诉我）：

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

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

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

我还假设该数组由“b”、“w”和“x”填充，分别表示黑子、白子和空方块。

我的解决方案有点分而治之，所以我将其分成了以下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中使用。

对角线

再次，我们想重用'testRows'函数。例如这样的对角线：

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个位置。现在只需要转置，我们就可以回到测试水平的问题上了。您需要对另一条方向的对角线执行相同的操作，但这次将行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})/);

- David Tang

Answer 2

即使这个问题已经很老了，但我想提供我的答案，因为我今天深入研究了这个问题，并以一种更加高效的方式解决了它。

我使用位棋盘来表示我的领域，这在大多数棋类游戏和引擎（如国际象棋引擎）中都很常见，因为它非常高效。

您可以使用位运算符完成此游戏中所需的所有操作。

一个位只能有两种状态（0和1），但我们需要三种状态，例如p1，p2或empty。为了解决这个问题，我们将使用两个棋盘，每个玩家一个。

另一个问题是五子棋有很多领域（19x19），而没有数字类型具有足够多的位来表示领域。我们将使用数字数组来表示每条线路，并仅使用其前15位lsb。

垂直行

玩家1的简化版棋盘可能如下所示

000000
101100
001000
011000
000000

假设我们想要检测连续的3个数字。我们取前三行（0-2行）并查看它们。

000000
001100
101000

使用 &（AND）运算符，您可以检查每行中是否存在1。

var result = field[player][0] & field[player][1] & field[player][2];

在这种情况下，结果将为0，表示没有获胜者。让我们继续...下一步是取行1-3。

101100
001000
011000

应用AND操作，我们将得到001000。我们不需要关心这是什么数字，只需要知道它是否为0（result != 0）。

水平行

现在我们可以检测垂直行了。要检测水平行，我们需要再保存两个棋盘，每个玩家一个。但是我们需要反转x和y轴。然后我们可以再次进行相同的检查以检测水平线。你的数组将会是：

//[player][hORv][rows]
var field[2][2][19];

对角线 :)

当然，最棘手的部分是对角线，但是通过一个简单的技巧，您可以进行与上面相同的检查。这是一个简单的棋盘：

000000
010000
001000
000100
000000

基本上，我们与上述相同，但在此之前，我们需要移动行。假设我们在第1-3行。

010000
001000
000100

第一行保持不变。然后您将第二行向左移动一个位置，第三行向左移动两个位置。

var r0 = field[0][0][i];
var r1 = field[0][0][i+1] << 1;
var r2 = field[0][0][i+2] << 2;

你将会获得什么：

010000
010000
010000

申请并且您就可以获得胜利检测。要获取另一个对角线方向，只需再次执行相同的步骤，但是不是向左移动 <<，而是向右移动 >>。

希望这可以帮助到某些人。

- Dominic

Answer 3

未经测试：

int left = max(0, move.x-5), right = min(width-1, move.x+5), top = max(0, move.y-5), bottom = min(width-1, move.y+5);    
// check the primary diagonal (top-left to bottom-right)
for (int x = left, y = top; x <= right && y <= bottom; x++, y++) {
    for (int count = 0; x <= right && y <= bottom && stones[x][y] == lastPlayer; x++, y++, count++) {
        if (count >= 5) return true;
    }
}
// check the secondary diagonal (top-right to bottom-left)
// ...
// check the horizontal
// ...
// check the vertical
// ...
return false;

或者，如果您不喜欢嵌套循环（未经测试）：

// check the primary diagonal (top-left to bottom-right)
int count = 0, maxCount = 0;
for (int x = left, y = top; x <= right && y <= bottom; x++, y++) {
    if (count < 5) {
        count = stones[x][y] == lastPlayer ? count + 1 : 0;
    } else {
        return true;
    }
}

- Lie Ryan

---

这些并没有处理“不超过5个”的规则。 - Adam Norberg

@Adam Norberg：添加这个很容易。"不超过5个"的规则意味着实际上是六个棋子连成一排，形如B-B-B-B-B-(W/)或W-W-W-W-W-(B/)。 - Lie Ryan