我可以使用什么井字棋游戏算法来确定“最佳动作”？ 对于人工智能？

Question

在井字棋实现中，我认为具有挑战性的部分是确定机器要采取的最佳动作。

可以追求哪些算法？ 我正在研究从简单到复杂的实现。 我将如何解决这部分问题？

Answer 1

生成每个可能的棋盘并根据稍后在树中进一步生成的棋盘对其进行评分的强力方法不需要太多内存，特别是当您认识到 90 度棋盘旋转是多余的（就像垂直翻转一样），水平轴和对角轴。

一旦达到这一点，树形图中就会有不到 1k 的数据来描述结果，这也是计算机的最佳移动方式。

-亚当

Answer 2

由于您只处理可能位置的 3x3 矩阵，因此只需编写对所有可能性的搜索就非常容易，而不会增加您的计算能力。 对于每个开放空间，计算标记该空间后的所有可能结果（我想说，递归地），然后使用最有可能获胜的举动。

优化这个确实是浪费精力。 虽然一些简单的可能是：

• 首先检查可能的胜利
  另一队，阻止第一队
  你发现（如果有 2 个游戏
  无论如何）。
• 如果中心开放，请始终占据中心
  （并且之前的规则没有
  候选人）。
• 在双方之前进行角球（再次，
  如果前面的规则为空）

Answer 3

井字棋的典型算法应如下所示：

Board：代表棋盘的九元素向量。 我们存储2（表示
空白）、3（表示 X）或 5（表示 O）。
回合：一个整数，指示将要进行的游戏的哪一步。
第一步将用 1 表示，最后一步将用 9 表示。

算法

主要算法使用三个函数。

Make2：如果棋盘的中心方块为空白，即 board[5]=2，则返回 5。 否则，此函数返回任何非角正方形（2、4、6或8）。

Posswin(p)：如果玩家p在下一步行动中无法获胜，则返回0； 否则，它返回构成获胜棋步的方格数。 该功能将使程序既能获胜又能阻止对手获胜。 该函数通过检查每一行、每一列和对角线来运行。 通过将整行（或列或对角线）的每个方格的值相乘，可以检查获胜的可能性。 如果乘积为 18 (3 x 3 x 2)，则 X 获胜。 如果产品是 50 (5 x 5 x 2)，那么 O 可以获胜。 如果找到获胜行（列或对角线），则可以确定其中的空白方块，并通过该函数返回该方块的编号。

Go (n)：在 n 格内移动。 如果 Turn 为奇数，则此过程将 board [n] 设置为 3；如果 Turn 为偶数，则将 board [n] 设置为 5。 它还逐一递增。

该算法对每一步都有一个内置策略。 它使奇数
如果下X就走，如果下O就走偶数。

Turn = 1    Go(1)   (upper left corner).
Turn = 2    If Board[5] is blank, Go(5), else Go(1).
Turn = 3    If Board[9] is blank, Go(9), else Go(3).
Turn = 4    If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5    if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6    If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7    If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8    if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9    Same as Turn=7.

我用过。 让我知道你们的感受。

Answer 4

您可以让 AI 在一些示例游戏中自行玩耍以供学习。 使用监督学习算法来帮助它前进。

Answer 5

不使用比赛场地的尝试。

1. 如果没有，就赢（你的双倍）
2. ，不要输（对手的双倍），
3. 如果没有，你是否已经有叉子（有双倍）
4. 如果没有，如果对手有叉子
   1. 在阻塞点中搜索可能的双倍和分叉（最终获胜）
   2. 如果不在阻塞点中寻找叉子（这给了对手最大的失败可能性）
   3. 如果不只堵点（不丢）
5. 如果不搜索双倍并且分叉（最终胜利），
6. 如果不搜索，则仅搜索给对手最大失败可能性的分叉
7. ，如果不搜索，则仅搜索双倍（
8. 如果不是死胡同），平局，随机。
9. 如果没有（这意味着你的第一步）
   1. 如果这是游戏的第一步；
      1. 给对手最大的输球可能性（算法结果只产生角球，给对手7个输分的可能性）
      2. 或者只是随意地打破无聊。
   2. 如果这是游戏的第二步；
      1. 只找到不丢失的点（提供更多选择）
      2. 或者找到此列表中最有可能获胜的点（这可能很无聊，因为它只会导致所有角点或相邻角点或中心）

注意：当你有双倍和叉子时，检查你的双倍是否给对手一个双倍。如果给了，检查你的新强制点是否包含在你的叉子列表中。

Answer 6

用数字分数对每个方块进行排名。 如果占据了一个方格，则继续进行下一个选择（按排名降序排列）。 你需要选择一个策略（有两个主要的策略用于第一个策略，三个（我认为）用于第二个策略）。 从技术上讲，您可以对所有策略进行编程，然后随机选择一种。 这将使对手变得更难以预测。

Answer 7

这个答案假设您了解如何实现 P1 的完美算法，并讨论如何在对抗普通人类玩家的条件下取得胜利，因为普通人类玩家比其他人更容易犯一些错误。

如果双方都发挥最佳，比赛当然应该以平局结束。 从人类的角度来看，P1 在角球中获胜的几率要高得多。 无论出于何种心理原因，P2 都会认为在中路比赛并不那么重要，这对他们来说是不幸的，因为这是唯一无法为 P1 创造胜利的反应。

如果P2确实在中心正确阻挡，P1应该打相反的角球，因为无论出于什么心理原因，P2都会更喜欢打角球的对称性，这再次为他们带来了失败的棋盘。

对于 P1 可能采取的任何起始行动，如果随后双方都发挥最佳状态，P2 可能采取的行动将为 P1 创造胜利。 从这个意义上说，P1 可以在任何地方发挥作用。 边缘移动是最弱的，因为对此移动的最大部分可能的反应会产生平局，但仍然有一些反应将为 P1 带来胜利。

根据经验（更准确地说，根据轶事），最佳的 P1 起始动作似乎是第一个角、第二个中心和最后一个边缘。

您可以亲自或通过 GUI 添加的下一个挑战不是显示电路板。 人类绝对可以记住所有状态，但增加的挑战导致人们偏爱对称板，这种板需要更少的努力来记住，从而导致我在第一个分支中概述的错误。

我知道我在聚会上很开心。

Answer 8

对最小最大算法的井字游戏适应

let gameBoard: [
    [null, null, null],
    [null, null, null],
    [null, null, null]
]

const SYMBOLS = {
    X:'X',
    O:'O'
}

const RESULT = {
    INCOMPLETE: "incomplete",
    PLAYER_X_WON: SYMBOLS.x,
    PLAYER_O_WON: SYMBOLS.o,
    tie: "tie"
}

我们需要一个可以检查结果的函数。 该函数将检查连续的字符。 无论棋盘状态如何，结果都是 4 个选项之一：不完整、玩家 X 获胜、玩家 O 获胜或平局。

function checkSuccession (line){
    if (line === SYMBOLS.X.repeat(3)) return SYMBOLS.X
    if (line === SYMBOLS.O.repeat(3)) return SYMBOLS.O
    return false 
}

function getResult(board){

    let result = RESULT.incomplete
    if (moveCount(board)<5){
        return result
    }

    let lines

    //first we check row, then column, then diagonal
    for (var i = 0 ; i<3 ; i++){
        lines.push(board[i].join(''))
    }

    for (var j=0 ; j<3; j++){
        const column = [board[0][j],board[1][j],board[2][j]]
        lines.push(column.join(''))
    }

    const diag1 = [board[0][0],board[1][1],board[2][2]]
    lines.push(diag1.join(''))
    const diag2 = [board[0][2],board[1][1],board[2][0]]
    lines.push(diag2.join(''))
    
    for (i=0 ; i<lines.length ; i++){
        const succession = checkSuccesion(lines[i])
        if(succession){
            return succession
        }
    }

    //Check for tie
    if (moveCount(board)==9){
        return RESULT.tie
    }

    return result
}

我们的 getBestMove 函数将接收棋盘的状态以及我们想要确定最佳可能移动的玩家的符号。 我们的函数将使用 getResult 函数检查所有可能的移动。 如果是胜利，则得分为 1。如果是松，得分为 -1，平局得分为 0。如果不确定，我们将使用新状态调用 getBestMove 函数董事会的和相反的符号。 由于下一步是对手的，他的胜利就是当前玩家的失败，得分将被否定。 最后可能的移动得到 1,0 或 -1 的分数，我们可以对移动进行排序，并返回得分最高的移动。

const copyBoard = (board) => board.map( 
    row => row.map( square => square  ) 
)

function getAvailableMoves (board) {
  let availableMoves = []
  for (let row = 0 ; row<3 ; row++){
    for (let column = 0 ; column<3 ; column++){
      if (board[row][column]===null){
        availableMoves.push({row, column})
      }
    }
  }
  return availableMoves
}

function applyMove(board,move, symbol) {
  board[move.row][move.column]= symbol
  return board
}
 
function getBestMove (board, symbol){

    let availableMoves = getAvailableMoves(board)

    let availableMovesAndScores = []

    for (var i=0 ; i<availableMoves.length ; i++){
      let move = availableMoves[i]
      let newBoard = copyBoard(board)
      newBoard = applyMove(newBoard,move, symbol)
      result = getResult(newBoard,symbol).result
      let score
      if (result == RESULT.tie) {score = 0}
      else if (result == symbol) {
        score = 1
      }
      else {
        let otherSymbol = (symbol==SYMBOLS.x)? SYMBOLS.o : SYMBOLS.x
        nextMove = getBestMove(newBoard, otherSymbol)
        score = - (nextMove.score)
      }
      if(score === 1)  // Performance optimization
        return {move, score}
      availableMovesAndScores.push({move, score})
    }

    availableMovesAndScores.sort((moveA, moveB )=>{
        return moveB.score - moveA.score
      })
    return availableMovesAndScores[0]
  }

实际算法，Github，更详细地解释该过程

Answer 9

维基百科中关于玩完美游戏（每次获胜或平局）的策略似乎是简单的伪代码：

引自维基百科（井字游戏#Strategy）< /strong>

如果玩家每回合从以下列表中选择第一个可用的棋步，就可以玩一场完美的井字游戏（获胜或至少平局），如纽厄尔和西蒙 1972 年的井字棋中所使用的那样 - tac-toe 程序。[6]

1. 获胜：如果您连续获得两个，则玩第三个以获得连续三个。

2. 阻挡：如果对手连续有两个，则打第三个来阻挡他们。

3. 分叉：创造一个可以通过两种方式获胜的机会。

4. 阻止对手的分叉：

   选项 1：连续创建两个以强制
   对手进入防守状态，只要
   因为这不会导致他们创造
   叉子或获胜。 例如，如果“X”
   有一个角，“O”有中心，并且
   “X”也有对角，
   “O”不得打角球
   赢。 （在这个位置打一个角
   场景为“X”创建一个分叉
   赢了。）

   选项2：如果有配置
   对手可以分叉、阻止的地方
   那个叉子。

5. 中心：播放中心。

6. 对角：如果对手在角上，则打对面
   角落。

7. 空角：打空角。

8. 空方：打空方。

认识到“分叉”情况是什么样子，可以按照建议以暴力方式完成。

注意：“完美”的对手是一个很好的练习，但最终不值得“对抗”。 但是，您可以更改上述优先级，以赋予对手个性弱点。

Answer 10

您需要的（对于井字游戏或像国际象棋这样更困难的游戏）是minimax算法，或其稍微复杂的变体，alpha-beta 修剪。 不过，对于像井字棋这样搜索空间很小的游戏来说，普通的朴素极小极大值就足够了。

简而言之，你要做的不是寻找对你来说可能有最好结果的走法，而是寻找尽可能最坏结果的走法。 如果你假设你的对手玩得最好，你就必须假设他们会采取对你来说最差的举动，因此你必须采取最小化他们的最大收益的举动。