井字棋建议

Question

我正在设计井字棋游戏的实现策略。由于这是我第一次实现游戏，我有点困惑，需要一些指导。

现在，井字棋中获胜组合的总数为8。目前，我的计划是将这些获胜组合存储在一个数组中。一旦最终用户至少移动了3次，我就会开始检查玩家是否赢得了游戏，通过将玩家使用的当前位置与该数组进行比较。然而，我确信这不是检查玩家是否有获胜组合的有效方法。

请问有人能够建议我如何设计游戏逻辑吗？

- name_masked

Answer 1

不用担心效率问题。我写了一个回溯解法，只有549,945种可能的游戏状态。在我的笔记本电脑上运行这些状态只需要不到0.25秒。以下是我的逻辑来判断游戏是否结束——显然并不是很高效，但这并不重要：

private boolean isWinningMove(int row, int col) {
    int piece = board[row][col];

    // check current row
    boolean w = true;
    for (int x = 0; x < 3; x++) { w = w && (board[row][x] == piece); }
    if (w) { return true; }

    // check current column
    w = true;
    for (int x = 0; x < 3; x++) { w = w && (board[x][col] == piece); }
    if (w) { return true; }

    // check 0,0 diagonal
    w = true;
    for (int x = 0; x < 3; x++) { w = w && (board[x][x] == piece); }
    if (w) { return true; }

    // check 0,2 diagonal
    w = true;
    for (int x = 0; x < 3; x++) { w = w && (board[x][2 - x] == piece); }
    return w;
}

这是我的结果，与井字棋的维基百科页面上的数据相符：

Moves Simulated: 549945
Draws=46080   Player1-Wins=131184   Player2-Wins=77904
Perfect Strategy Implies: Always a tie.

Games won in 0 moves? 0
Games won in 1 moves? 0
Games won in 2 moves? 0
Games won in 3 moves? 0
Games won in 4 moves? 0
Games won in 5 moves? 1440
Games won in 6 moves? 5328
Games won in 7 moves? 47952
Games won in 8 moves? 72576
Games won in 9 moves? 81792

- Julius Musseau

---

最多有9！种状态，即362880种（实际上会更少，因为其中许多状态在最后一步之前就达到了获胜条件）。不确定您是如何得到549945个状态的。 - Mark Peters

回溯树的大小为549,945 - 它包括所有正在进行的游戏。 - Julius Musseau

Answer 2

由于井字棋的状态空间非常小，您可以存储所有可能的最终游戏位置，并使用旋转，但我认为您有点过于深思熟虑。

不要为游戏板存储3x3数组，而是使用7x7数组，其中内部最小的3x3用于游戏板。每个方格应该至少有三个值表示——类似于PLAYER_1、PLAYER_2和NONE。最初，所有值都应设置为NONE。然后，在每个玩家的移动之后，检查所选方格周围的所有内容，以获得3连胜；2个以上，2个以下，2个左侧，2个右侧，2个左上角，2个右下角，2个右上角，2个左下角。

为什么是7x7数组？使用7x7数组，您可以安全地从3x3区域中的任何方格搜索所有方向，而无需使用if语句来查看是否正在走出数组的边缘。棋盘将如下所示：

  0 1 2 3 4 5 6
0 * * * * * * *
1 * * * * * * *
2 * * * * * * *
3 * * * * * * *
4 * * * * * * *
5 * * * * * * *
6 * * * * * * *

例如，如果第一个玩家在井字棋板上移动到0,0，则与在7x7板上移动到2,2相同。当进行移动时，您需要检查2,2周围的所有内容，以查看是否有三个相同值的方格。

• 以上：2,0和2,1和2,2
• 以下：2,2和2,3和2,4
• 左侧：0,2和1,2和2,2
• 右侧：2,2和2,3和2,4
• 左上角：0,0和1,1和2,2
• 右上角：2,2和3,1和4,0
• 左下角：0,4和1,3和2,2
• 右下角：2,2和3,3和4,4

由于3x3板周围的方格带始终具有值NONE，因此它们永远不会触发获胜条件。

如果其中任何一个与同一玩家值（例如第一个玩家的PLAYER_1）匹配，则游戏已经结束并获胜。否则，如果所有方格都被占用，则游戏为平局。

我之前在其他类似的游戏中使用过这个方法，效果非常好。

- Shaggy Frog

---

我不理解需要7x7数组的原因。您能否详细说明一下？另外，我对以下陈述不太清楚：“检查所选择的正方形周围是否有3个连续的格子；2个在上面，2个在下面，2个在左边，2个在右边，2个在左上角，2个在右下角，2个在右上角，2个在左下角。”谢谢。 - name_masked

我为什么认为7x7数组很方便进行了澄清。 - Shaggy Frog

这似乎比仅检查8种可能的组合要复杂得多。您甚至还没有涵盖所有情况（上下各1个，左右各1个等）。这是过度思考的方式。OP的方式是显而易见和直接的方式。 - Mark Peters

是的，我错过了两种情况。然而，这个解决方案适用于任何NxM棋盘，并且在CPU和内存方面非常高效。 - Shaggy Frog

常见的高CPU效率计算井字棋获胜位置？ - Aurelien Ribon

@Aurélien Ribon，一种简单的算法，适用于NxM棋盘。这是一个很好的网站，可以解释这些技术，不是吗？ - Shaggy Frog

Answer 3

考虑用整数表示棋盘。

-1 = X
 0 = empty
 1 = O

现在，对于每个可能性（3个上下，3个左右，2个对角线）计算方块的价值总和。如果总和为3，则O获胜；如果总和为-3，则X获胜。如果总和为2，则O在这些位置中有一步获胜的机会；如果总和为-2，则X在这些位置中有一步获胜的机会。AI可以以此为基础做出决策。只需向前看一步就足以永不失败。如果AI开始游戏，最好的走法是角落。如果对手没有占据中心，AI获胜。如果对手占据了中心，则AI要么获胜，要么平局。

- EvilTeach

Answer 4

我不是在迭代某些东西，而是直接写出了8种组合。

我的评估函数做以下工作：如果A是要移动的一方，并且在所有组合中有两个A元素和一个0（空），那么这就是一个胜利：

boolean player_can_win(int value) { //value is side's element*2
    return board[0] + board[1] + board[2] == value
            || board[3] + board[4] + board[5] == value
            || board[6] + board[7] + board[8] == value
            || board[0] + board[3] + board[6] == value
            || board[1] + board[4] + board[7] == value
            || board[2] + board[5] + board[8] == value
            || board[0] + board[4] + board[8] == value
            || board[2] + board[4] + board[6] == value;
}

- matias

Answer 5

如果你在玩通用的 N X N 井字棋，那么显式存储并与解决方案进行比较并不是最有效的方法，但由于它是如此小的棋盘，只有8个这样的组合，因此像这样显式地存储解决方案没有任何问题。

更大的问题是，根据存储方式，与解决方案无关的空间可能会成为问题。

O - -        - O -
X X X   vs.  X X X
O - O        O - O

比较3x3状态数组，它们是不同的，因此该方法需要超过8个终止状态。

我猜你会保留一个gameState 3x3数组，其中空白=0，X=1，O=2？

除了这些明确的比较，你还可以做一些类似于：

win = false   
// rows/columns
for i in 0,1,2
   if (state[i][0] != BLANK && state[i][0] == state[i][1] == state[i][2]) win = true
          #extensible to NxN - all(j == state[i][0] for j in state[i])
   if (state[0][i] != BLANK && state[0][i] == state[1][i] == state[2][i]) win = true
          #extensible to NxN - all(j == state[0][i] for j in zip(*state)[i])
//diagonals
if (state[0][0] != BLANK && state[0][0] == state[1][1] == state[2][2]) win = true
          #extensible to NxN - all(state[j][j] == state[0][0] for j in range(len(state))
if (state [2][0] != BLANK && state[2][0] == state[1][1] == state[0][2]) win = true

如果您希望将胜者而不是标记存储在win中，那么请在顶部设置win = BLANK，并将其设置为任何涉及的方格的值。然而，这应该是不必要的，因为胜者显然是最近的一步！

我认为您可能会发现写井字游戏中最具挑战性但不太难的部分是AI。编写一个不会输（至少可以强制平局）的AI并不太困难，但也不是完全平凡的事情。如果您想要一个相对不错的AI，它有时会输，您需要添加一些随机因素或其他内容。

- jon_darkstar

---

@Shaggy：这不就是Jon所说的吗？Jon泛指NxN，而你说他所说的对于N=10也是正确的。他所说的哪一部分“不一定正确”？ - Mark Peters

Answer 6

实现井字棋游戏可能是在人工智能和搜索空间方面最简单的问题。

关键是使用极小化极大算法, 迭代加深深度优先搜索和Alpha-beta剪枝算法来解决这个问题。

这是我用Python实现的游戏代码，只有约200行代码，可以进行人类对战、人机对战和机器对战。它还记录了深度和节点数的统计信息，以及达到/剪枝的最佳移动。

我强烈推荐 edX.org 的人工智能课程，它提供了关于当前人工智能主题和解决方案的基础知识。

- Ostati