棋盘游戏共赢 - 搜索算法 [英] board game win situation - searching algorithm

问题描述

我在寻找可能有效的算法来检测双赢的局面在五子棋（五在一个排）的比赛，打了一个19×19板。双赢的局面发生时的球员之一设法得到五个NO在连续五个多石头（横向，斜向或垂直）。

I'm looking for possibly efficient algorithm to detect "win" situation in a gomoku (five-in-a-row) game, played on a 19x19 board. Win situation happens when one of the players manages to get five and NO MORE than five "stones" in a row (horizontal, diagonal or vertical).

我有以下的数据方便：

• previous移动双方球员存储在一个二维数组（石头）（可能还JSON符号的对象），用变量B和W来彼此，
差异玩家 进入的举动
• 在坐标（move.x，move.y），
• 的动作每名球员做了一些

• previous moves ("stones") of both players stored in a 2d array (can be also json notation object), with variables "B" and "W" to difference players from each other,
• "coordinates" of the incoming move (move.x, move.y),
• number of moves each player did

我在做这在JavaScript，但不使用低级别的东西，如内存分配，也没有更高级别的（蟒蛇）数组操作的任何解决方案，将是一件好事。

I'm doing it in javascript, but any solution that doesn't use low-level stuff like memory allocation nor higher-level (python) array operations would be good.

我发现similiar问题（检测获胜的比赛中零和十字架），但由于存在只是指小板（5×5等）的解决方案。

I've found similiar question ( Detect winning game in nought and crosses ), but solutions given there only refer to small boards (5x5 etc).

推荐答案

一个简单易懂，无需过多的循环液（仅提供伪code，让我知道如果你需要更多的解释）：

A simple to understand solution without excessive loops (only pseudocode provided, let me know if you need more explanation):

我假设你的2-D阵列运行是这样的：

I assume your 2-d array runs like this:

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

即。内部阵列重新present板的水平行。

I.e. the inner arrays represent the horizontal rows of the board.

我还假设数组填充由B，W和X，再presenting黑片，白片，空方块，分别为。

I also assume that the array is populated by "b", "w", and "x", representing black pieces, white pieces, and empty squares, respectively.

我的解决办法是有点分而治之，所以我把它分成以下3例。忍耐一下，它可能看起来更复杂不是简单地运行多个嵌套循环在第一，但这个概念很容易理解，阅读，并与正确的方法，很简单的code。

My solution is somewhat divide-and-conquer, so I've divided it into the 3 cases below. Bear with me, it may seem more complex than simply running multiple nested loops at first, but the concept is easy to understand, read, and with the right approach, quite simple to code.

让我们首先考虑的检测共赢只有当行水平的情况 - 这是最简单的。首先，加入一行到一个字符串，使用类似板[0]。加入（）。做到这一点的每一行。你最终得到一个这样的数组：

Let's first consider the case of detecting a win situation ONLY if the line is horizontal - this is the easiest. First, join a row into a single string, using something like board[0].join(""). Do this for each row. You end up with an array like this:

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

现在加入这个数组，但插入元素之间的X来分隔每一行： rows.join（X）

Now join THIS array, but inserting an "x" between elements to separate each row: rows.join("x").

现在你有一个长字符串再presenting你的董事会，这是简单地将一个正则表达式来找到连续的W或b正是5长的问题： superString.test （/（B {5,5}）|（W ​​{5,5}）/）。如果测试返回真你有一个双赢的局面。如果不是，让我们进入到垂直线。

Now you have one long string representing your board, and it's simply a matter of applying a regexp to find consecutive "w" or "b" of exactly 5 length: superString.test(/(b{5,5})|(w{5,5})/). If the test returns true you have a win situation. If not, let's move on to vertical lines.

您想重用上面的code，所以创建一个函数 testRows 吧。测试的垂直线是完全一样的过程，但要置董事会，使行成为列，列将成为行。然后，你将相同的 testRows 功能。移调可以通过复制值到一个新的2-D阵列来实现，也可以通过写简单的 getCol 的功能和使用中的 testRows 。

You want to reuse the above code, so create a function testRows for it. Testing for vertical lines is exactly the same process, but you want to transpose the board, so that rows become columns and columns become rows. Then you apply the same testRows function. Transposing can be done by copying values into a new 2-d array, or by writing a simple getCol function and using that within testRows.

此外，我们要重用`testRows功能。对角线像这样的：

Again, we want to reuse the `testRows' function. A diagonal such as this:

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

可以转换为一个垂直像这样：

Can be converted to a vertical such as this:

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

通过由我位置移一行我。现在，它的转置的问题，我们回到了测试的水平线。你需要的对角线是走另外一条路做同样的，但时移一行我按长度 - 1 - 我的位置，或在您的情况下， 18 - 我位置

By shifting row i by i positions. Now it's a matter of transposing and we are back at testing for horizontals. You'll need to do the same for diagonals that go the other way, but this time shift row i by length - 1 - i positions, or in your case, 18 - i positions.

作为一个侧面说明，我的解决方案能很好地适应函数式编程，这意味着它可以很容易地codeD，如果你和你的函数式编程工具，尽管它是没有必要的。我建议使用 underscore.js 因为它很可能你会需要像地图，减少，在许多不同的游戏算法过滤器。比如，我在测试横线部分可以写在一行中的JavaScript与使用地图：

As a side note, my solution fits nicely with functional programming, which means that it can be quite easily coded if you have functional programming tools with you, though it's not necessary. I recommend using underscore.js as it's quite likely you'll need basic tools like map, reduce and filter in many different game algorithms. For example, my section on testing horizontal lines can be written in one line of javascript with the use of map:

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

这篇关于棋盘游戏共赢 - 搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！