7

我需要知道在棋盘游戏中检测获胜棋步的最佳方法。源代码无所谓，我只需要一个例子或者我可以开始的东西。

我唯一能想到的就是使用循环并测试玩家每一个动作的每个方向，例如连续搜索五个。有没有更快更有效的方法？

4

6 回答 6

9

真正简单的解决方案是从最后一步进行检查......显然，没有任何先前的动作可以赢得比赛，或者你不会在这里......所以你只需要检查是否有 5 (或许多）在刚刚放置的移动周围的行/列/对角线中。

例如，如果棋盘看起来像这样，并且 X 标记最近的移动：

.............
.............
.............
.............
.....X.......
.............
.............
.............
.............
.............

您不需要检查“C”范围之外的任何内容：

.C...C...C...
..C..C..C....
...C.C.C.....
....CCC......
.CCCCXCCCC...
....CCC......
...C.C.C.....
..C..C..C....
.C...C...C...
.............

这有帮助吗？（看起来您可能在原始问题中暗示了这一点，但我不确定。）

除此之外，简单的循环将成为你最好的朋友。您可能可以进行一些微优化，但是（取决于您的实际应用程序在做什么）这可能不值得。

需要注意的一件事是，你不能从最近的移动中向任何方向跳出 5 来连续寻找那么多，因为这个移动可能处于连胜的中间。所以我会做类似的事情

From the new move
    left = how many in a row we have to the left of the lastest move
    right = how many in a row we have to the right of the latest move
    if (left + right + 1 >= 5) then you have a winner

    up = how many in a row we have above the latest move
    down = how many in a row we have below the latest move
    if (up + down + 1 >= 5) then you have a winner

    // repeat for both diagonal directions.
于 2010-04-19T19:47:10.883 回答
7

Noughts and crosses 是一个巧妙的编程挑战，因为有很多数学技巧可以用来简化问题。

Noughts 和 crosss 通常是 3×3 网格。如果您为网格中的每个位置分配一个从 1 到 9 的数字（不按数字顺序），您可以排列数字，使每个水平、垂直和对角线行加起来为 15

+----+----+----+
| 4  | 3  | 8  |
|    |    |    |
+----+----+----+
| 9  | 5  | 1  |
|    |    |    |
+----+----+----+
| 2  | 7  | 6  |
|    |    |    |
+----+----+----+

为什么有用？如果您可以选择属于“O”或“X”的任意三个方格，并且这三个方格的总和为 15，则您知道该玩家赢得了游戏。

于 2011-04-11T13:03:41.480 回答
2

考虑 3X3 板

令 X = 1 令 O = -1，空格由零表示。

因此，如果顶行看起来像这样 [X][X][X]，则总和为 3，因此是胜利 [O][O][O]，总和为 -3，因此是另一个胜利。

[X][X][ ]是2，因此如果是X转，他可以通过移动到空白处获胜，否则O必须阻止。

[X][O][X] 为 1，因此没有获胜。

在 3x3 棋盘中，有 8 个位置需要评估。

在 NXN 中，数字变大了，但想法保持不变

如果 N=8 并且一行或一列的总和为 7，那么您知道在该行/列上 X 有一个获胜的举动

这种方法在我高中时很有效。

最好的祝愿

邪恶的

于 2010-04-19T20:50:23.617 回答
1

我不知道有比循环更好的方法，但是板子太小了，非常微不足道。

一点 Python 伪代码：

def get_winner(board):
    if board[0][0] != EMPTY and board[0][0] == board[1][1] == board[2][2]:
        return board[0][0]
    if board[2][0] != EMPTY and board[2][0] == board[1][1] == board[0][2]:
        return board[2][0]
    for i in xrange(3):
        if board[i][0] != EMPTY and board[i][0] == board[i][1] == board[i][2]:
            return board[i][0]
        if board[0][i] != EMPTY and board[0][i] == board[1][i] == board[2][i]:
            return board[0][i]
于 2010-04-19T19:40:25.623 回答
0

有更有效的方法，但只有当您将此游戏扩展为更大、更大的棋盘配置时，它们才真正重要。例如，如果您将 noughts 和 crosss 分组存储在定向对象中（例如，存储对角线配置），您可以按具有 length 的那些排序winLength-1，并且仅针对这些分组测试新移动。您节省了一些迭代，但您必须在内存中维护大量额外信息。

于 2010-04-19T19:40:53.107 回答
0

这是一个代表性的问题。如何存放游戏板？现在跳出框框思考；你还能怎么储存它？例如，您可以将棋盘表示为一对位图 - 一个用于 noughts，一个用于 crosss - 然后进行数字模式匹配以检测获胜条件。

于 2010-04-19T19:43:08.643 回答