棋盘游戏胜局 - 搜索算法

Question

我正在寻找可能有效的算法来检测在19x19板上玩的gomoku(五行)游戏中的"胜利"情况.胜利的情况发生在其中一个玩家设法获得五个并且连续不超过五个"石头"(水平,对角线或垂直)时.

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

• 存储在二维数组中的两个玩家的先前移动("石头")(也可以是json符号对象),变量"B"和"W"表示彼此不同的玩家,
• 传入移动的"坐标"(move.x,move.y),
• 每个球员的动作次数

我在javascript中这样做,但任何不使用低级内容(如内存分配和高级(python)数组操作)的解决方案都会很好.

我发现了一个类似的问题(检测到赢得的游戏没有和交叉),但那里给出的解决方案只涉及小板(5x5等).

Answer 1

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

我假设您的二维数组运行如下:

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

即内部数组代表电路板的水平行.

我还假设数组由"b","w"和"x"填充,分别代表黑色部分,白色部分和空白正方形.

我的解决方案有点分而治之,所以我将其分为以下3个案例.与我相比,它看起来比简单地运行多个嵌套循环看起来更复杂,但这个概念易于理解,阅读,并且使用正确的方法,编码非常简单.

水平线

让我们首先考虑只有当线是水平时才检测到胜利情况的情况 - 这是最简单的.首先,使用类似的东西将一行连接成一个字符串board[0].join("").为每行执行此操作.你得到一个像这样的数组:

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

现在加入THIS数组,但在元素之间插入一个"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在许多不同的游戏算法.例如,我在测试水平线的部分可以用一行javascript编写,使用map:

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