java对Tic-Tac-Toe的建议

Question

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

现在，Tic Tac Toe中获胜组合的总数是8。目前，我计划将这些获胜的组合存储在一个数组中。一旦最终用户做出了至少3个动作，我将通过比较玩家当前使用的位置与此阵列来检查玩家是否赢得了游戏。然而，我相信这不是一个有效的方法来检查球员是否有一个胜利的组合

有谁能建议我如何着手设计游戏的逻辑吗

Answer 1

就人工智能而言，实现Tic-Tac-Toe游戏可能是最简单的问题 和搜索空间

关键是用Minimax、Iterative deepening Depth-first search和Alpha-beta pruning算法来解决这个问题

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

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

Answer 2

考虑用整数表示板。

-1 = X
 0 = empty
 1 = O

现在，将8种可能性（3种向上和向下、3种向左和向右、2种对角线）的平方值相加

如果总数是3，O赢 如果总和是-3，X赢

如果总和是2，那么O在其中一个位置有一个获胜的移动 如果总和i-2，那么X在其中一个位置有一个获胜的移动

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

如果AI开始游戏，最好的动作是角球。如果对手未能占据中心，AI获胜。如果他真的占据了中锋，那么AI要么获胜，要么平局

Answer 3

由于tic-tac-toe的状态空间非常小，你可以存储所有可能的游戏结束位置，并使用旋转，但我认为你有点想过头了

不要为游戏板存储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 * * * * * * *

例如，如果第一个玩家移动到tic tac趾板上的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，因此它们永远不会触发获胜条件

如果其中任何一个都匹配相同的玩家值（例如，第一个玩家的玩家值为1），则游戏以胜利结束。否则，如果所有的方块都被占据，这场比赛就是平局

在过去，我曾在其他类似的游戏中使用过这个功能，效果非常好

Answer 4

如果你玩的是广义的N X N tic tac toe游戏，那么显式存储和比较解决方案并不是最有效的，但是因为它像一个小棋盘，并且只有8个这样的组合，所以像这样显式存储解决方案没有什么错

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

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

比较3x3状态阵列，这些是不同的，因此该方法需要8个以上的端状态

我想你保留了一个类似游戏状态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=顶部留空，并设置为任何相关方块的值。不必了，获胜者显然是最近的一步

我认为写tic-tac-toe最具挑战性但又不太难的部分是AI。写一个不会输的人工智能并不太难，但也不是很简单（至少可以勉强平局）。如果你想要一个相对较好的人工智能，能够偶尔丢失，你需要添加一些随机性或其他东西

Answer 5

我没有迭代，而是写了8个组合

我的评估函数执行以下操作：如果一方要移动&；如果在所有组合中的一个组合中有两个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 6

不要担心效率。我写了一个回溯解决方案，只有549945个可能的游戏状态。在我的笔记本电脑上运行这些程序只需不到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