关于井字游戏的建议

Question

我正在设计 Tic-Tac-Toe 游戏的实施策略。由于这是我的第一个游戏实现，我有点困惑，需要一些一般性的指导。

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

有人可以建议我如何设计游戏的逻辑吗？

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;
}

这是我的结果，它与 tic-tac-toe 维基百科页面上的数据相匹配：

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

Answer 2

由于井字游戏的状态空间很小，您可以存储所有可能的最终游戏位置，并使用旋转，但我认为您想得太多了。

不要为游戏板存储 3x3 数组，而是使用 7x7 数组，最里面的 3x3 为游戏板。每个方块至少应该有三个可以代表的值 - 例如 PLAYER_1、PLAYER_2 和 NONE。最初，所有值都应设置为 NONE。然后，在每个玩家移动之后，检查被选择用于三连的方格周围；上面 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 * * * * * * *

例如，如果第一个玩家在 tic-tac-toe 棋盘上移动到 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），则游戏以胜利结束。否则，如果所有方格都被占据，则游戏为平局。

我过去曾在其他类似游戏中使用过它，效果非常好。

Answer 3

考虑用整数表示棋盘。

-1 = X
 0 = empty
 1 = O

现在，将 8 种可能性（3 个上下、3 个左右、2 个对角线）中每一种的方块值相加。

如果总和为 3，则 O 获胜
如果总和为 -3，则 X 获胜；

如果总和为 2，则 O 在这些位置之一有获胜的棋步
如果总和 i -2，则 X 在这些位置之一有获胜的举动。

人工智能可以使用它作为决策的基础。一步向前看就足以永不失败。

如果人工智能开始游戏，最好的棋步是角球。如果对手未能占据中心，则 AI 获胜。如果他确实占据了中心，那么人工智能要么获胜，要么平局。

Answer 4

我没有迭代某些东西，而是只写了 8 种组合。

我的评估函数执行以下操作：如果 A 是移动的一侧，并且 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;
}

Answer 5

如果您玩的是广义的 NXN 井字棋，那么显式存储并与解决方案进行比较并不是最有效的，但由于它就像小棋盘，并且只有 8 个这样的组合，因此显式存储这样的解决方案没有任何问题。

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

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

比较 3x3 状态数组，这些数组是不同的，因此这种方法需要超过 8 个最终状态，

我猜你保留了类似 gameState 3x3 数组的东西，其中有 Blank=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 放在顶部，并设置为任何相关方块的值。不过没必要，获胜者显然是最近的一步！

我认为编写井字棋的部分可能是你觉得最具挑战性的部分，但人工智能会不会太难。编写一个不会输的人工智能并不是太困难，但也不是那么简单（至少总是能打平）。如果你想要一个相对较好的人工智能，偶尔会失败，你需要添加一些随机性或其他东西。

Answer 6

就人工智能而言，实现井字游戏可能是最简单的问题
和搜索空间。

关键是用 Minimax 解决问题，迭代加深深度优先搜索 和 Alpha-beta 剪枝算法。

这是我用 Python 实现的游戏实现，只有大约 200 行代码，并且能够玩人与人、人与计算机和计算机与计算机游戏。它还保留了导致最佳移动的深度和达到/修剪的节点数量的统计数据。

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