5

我正在为井字游戏设计我的实施策略。由于这是我的第一个游戏实现，我有点困惑，需要一些通用指针。

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

谁能建议我如何设计游戏的逻辑？

4

6 回答 6

11

不用担心效率。我写了一个回溯解决方案，只有 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
于 2010-11-14T06:38:49.603 回答
5

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

不要为游戏板存储 3x3 数组，而是使用 7x7 数组，最里面的 3x3 用于游戏板。您应该至少具有每个正方形可以表示的三个值 - 类似于PLAYER_1,PLAYER_2和NONE。最初，所有值都应设置为NONE。然后，在每个玩家移动之后，检查被选为 3-in-a-row 的方格周围的所有区域；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），则游戏以胜利结束。否则，如果所有方格都被占用，则游戏为平局。

我过去曾将其用于其他类似的游戏，并且效果很好。

于 2010-11-14T01:56:57.770 回答
4

考虑用整数表示棋盘。

-1 = X
 0 = empty
 1 = O

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

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

如果总和为 2，则 O 在这些位置之一中获胜如果总和 i -2，则 X 在这些位置之一中获胜。

人工智能可以将其用作决策的基础。向前看就足以永远不会失败。

如果 AI 开始游戏，最好的移动是角球。如果对手未能占据中心位置，则 AI 获胜。如果他确实占据了中心，那么 AI 要么获胜，要么平局。

于 2012-12-16T19:51:38.693 回答
3

我没有迭代一些东西，而是写了 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;
}
于 2011-08-07T16:18:17.990 回答
2

如果您正在玩通用的 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 设置为顶部，并设置为任何相关方格的值。不应该是必要的，赢家显然是最近的举动！

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

于 2010-11-14T02:01:48.633 回答
0

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

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

这是我用 Python实现的游戏，它只有大约 200 行代码，并且能够以Human vs. Human、Human vs. Computer和Computer vs. Computer. 它还保留有关深度和达到/修剪的节点数量的统计信息，以达到最佳移动。

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

于 2019-04-05T21:09:10.307 回答