我该使用哪个算法来为AI决定井字棋游戏中的“最佳移动”？

Question

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

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

- praveen chettypally

---

http://imgs.xkcd.com/comics/tic_tac_toe.png - Mooing Duck

虽然维基百科的答案可能足够好，但我在下面添加了一个算法，通过检查所有可能的移动并对它们进行评分来找出每个给定棋盘的最佳移动。 - Ben Carp

我问过自己类似的问题：http://blog.maxant.co.uk/pebble/2018/04/07/1523086680000.html - Ant Kutschera

这里有一个非常 直观的答案。 - rbinnun

Answer 1

来自维基百科的完美游戏策略（每次赢或打平）似乎是简单明了的伪代码：

来自维基百科（井字棋策略）的引用

如果玩家每回合都按照Newell和Simon的1972年井字棋程序中使用的以下列表中的第一个可用移动进行游戏，则可以玩出完美的井字棋（赢或至少平局）。

1. 胜利：如果您有两个相邻的棋子，下一步落子在这两个棋子间的空位上，以获得三连胜。

2. 阻止对手获胜：如果对手有两个相邻的棋子，下一步落子在这两个棋子间的空位上，以阻止对手获胜。

3. 叉：创造一个使您可以有两种方式获胜的机会。

4. 阻止对手叉：

   选项1：创建两个相邻的棋子，迫使对手进行防守，只要这不会导致对手叉或获胜。例如，如果“X”占据了一个角，“O”占据了中心，“X”也占据了对角线的另一个角，“O”必须不下角，才能获胜。（在这种情况下下角会为“X”创造叉来获胜。）

   选项2：如果存在一种情况使对手可以叉，就阻止这个叉。

5. 中心：下在中心的位置。

6. 对角线上的空位：如果对手占据了一个角落，下在对角线上相对的角落。

7. 空角落：下在一个空的角落上。

8. 空边：下在一条空边上。

可以采用暴力方式来识别"fork"情况，如建议所说。

注意：追求“完美”的对手是一种不错的练习，但最终不值得与之“对弈”。但是，您可以改变上述优先级，赋予对手个性特征的弱点。

- bkane

---

你如何建议实现策略中的分叉部分？ - Andrew Szeto

你的意思是：唯一的胜利之策就是不去参与。 - tooleb

一个中心叉岔不是比其他叉岔更有价值吗？ - Daniel Kobe

@Nick，“自己尝试”在这里没有任何关于如何找到反例的信息，有点无用。例如，是否存在一种通过此策略可达的配置，在此情况下遵循（6）而不是（7）会创建一个失败的游戏？发布更多关于您的反例的信息将会很有帮助。 - djechlin

Answer 2

你需要的是极小化极大算法，或者稍微复杂一些的alpha-beta剪枝算法，无论是井字棋还是更难的象棋都需要这个。对于井字棋这样搜索空间较小的游戏，普通的朴素极小化算法就足够了。

简而言之，你要做的不是寻找对你来说最好结果的移动，而是寻找最坏结果尽可能好的移动。如果你假设你的对手正在最优地玩耍，你必须假定他们会采取对你最糟糕的移动，因此你必须采取最小化他们最大利益的移动。

- Arachnid

---

这里缺少一个至关重要的信息：要最大化的是评估函数的值，该函数假定为任何（虚拟的，但通过放置下一个棋子尤其容易到达的）棋盘位置返回数值。像（中心区域的棋子价值100分，角落30分，边5分）这样便宜的东西可能会起作用，但缺乏上述高级信息，如现有对、现有叉等。因此，这不是我的首选。 - guidot

井字棋的搜索空间非常小，你的评估函数很简单：如果游戏处于获胜状态，则为正无穷；如果游戏处于失败状态，则为负无穷；如果是平局，则为零。 - Nick Johnson

极小化极大算法或Alpha-Beta算法肯定不是追求这种简单游戏的第一个想法（这限制了原始答案的价值）。然而，如果您这样做（也许是为了进行更复杂的游戏，如五子棋），则需要一个评估函数。对于给定的算法，只有在它产生任何中间位置的结果时，这样的函数才是明智的，建议使用（非常通用的）函数仅适用于已完成的游戏，有助于选择最终的获胜信息。 - guidot

相反地，使用全有或全无评估函数的极小化极大算法或Alpha-Beta剪枝算法适用于任何你想要彻底搜索的游戏。Alpha-Beta剪枝算法能够大幅减少搜索空间，相较于暴力搜索而言；而极小化极大算法只是一种合理的搜索游戏树并找到最佳可行动作的方式。 - Nick Johnson

我同意从第二句开始。你对穷举搜索的描述似乎是，直到游戏结束才能进行分析。对于许多非平凡的游戏来说，这有点过于乐观了。在这种（普遍）情况下，需要对中间位置进行评估，因为其返回值是mini-maxing的比较值（请参见维基百科，alpha-beta-pruning图表中节点中的数字）。欢迎提供实质性的参考资料（而不是一般性的评论）来证明这一点。 - guidot

Answer 3

使用暴力方法生成每个可能的棋盘，并根据它所产生的后续棋盘进行评分，这种方法不需要太多的内存，特别是一旦您认识到90度的棋盘旋转是冗余的，以及关于垂直、水平和对角线轴的翻转。

一旦达到此点，树形图中描述结果和计算机的最佳移动的数据少于1k。

-Adam

- Adam Davis

---

如果你想要变得非常复杂... ;-) 采用暴力方法可能比我的弱鸡排名想法更好，尽管实现起来有点困难。 - Daniel Spiewak

Answer 4

由于您只需要处理可能位置的3x3矩阵，因此很容易通过搜索所有可能性来计算而不会过度消耗计算机资源。对于每个空格，在标记该空格后计算所有可能的结果（递归），然后使用具有最多获胜可能性的移动。

实际上，优化这将是一种浪费精力的行为。尽管有些简单的方法可能是：

• 首先检查对手可能获胜的位置，然后阻止您发现的第一个位置（如果有2个，则游戏已经结束）。
• 如果中心空着（且前面的规则没有候选项），则始终占据中心位置。
• 在前面的规则为空的情况下，优先选择角落而非边缘。

- Bill James

---

从人类的角度来看，从P1开始往往更容易获胜。你的对手错误地认为，由于你没有占据中心，也许他们也不应该占据中心，出于某种原因。 - djechlin

Answer 5

一个典型的井字棋算法应该长这样：

棋盘：一个包含9个元素的向量，表示棋盘。我们存储2（表示空格）、3（表示X）或5（表示O）。

回合：一个整数，表示即将进行的游戏步骤。第一步为1，最后一步为9。

算法

主要算法使用了三个函数。

Make2：如果棋盘中心的方块为空格（即board[5]=2），则返回5。否则，此函数返回任何一个非角落方块(2, 4, 6 or 8)。

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

Go(n)：在第n个方格中进行移动。如果回合是奇数，则将棋盘[n]设置为3，如果回合是偶数，则设置为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.

我已经使用过它，让我知道你们的感受。

- Kaushik

Answer 6

你可以让人工智能在一些示例游戏中自行进行比赛以进行学习。使用监督式学习算法，以协助其学习。

- J.J.

Answer 7

不使用游戏场的尝试。

1. 赢(你的双倍分数)
2. 如果不行，不输给对手的双倍分数
3. 如果还不行，你已经有了一个叉子(两个双倍分数)
4. 如果还不行，如果对手有叉子
   
   1. 在阻挡点中搜索可能的双倍和叉子(最终获胜)
   2. 如果没有，在阻挡点中搜索叉子(这会给对手带来最多的失利可能性)
   3. 如果还不行，只能选择阻挡点(不输)
5. 如果还不行，搜索双倍和叉子(最终获胜)
6. 如果还不行，只搜索给对手带来最多失利可能性的叉子
7. 如果还不行，只搜索双倍
8. 如果还不行，那就是死路、平局或随机
9. 如果还不行(这意味着你的第一步)
   
   1. 如果这是游戏的第一步；
      
      1. 让对手有最多的失利可能性(该算法结果仅为角落，给对手7个失利点的可能性)
      2. 或者为了打破乏味，随机选择
   2. 如果这是游戏的第二步；
      
      1. 只找不输的点(提供更多选择)
      2. 或者在此列表中查找具有最佳获胜机会的点(可能会很无聊，因为结果仅为所有角落、相邻角落或中心)

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

- Mesut Ergul

---

实际上我的意思是，尝试不使用博弈树来解决那种决策问题，虽然这是最优解决方案。只是希望能够获得更多的见解。 - Mesut Ergul

Answer 8

对每个方格进行数字评分。如果一个方格已经被占据，就继续选择下一个（按照排名降序排序）。你需要选择一种策略（先手有两种主要策略，后手有三种（我想））。从技术上讲，你可以编写所有的策略，然后随机选择一个。这将使对手更加不可预测。

- Daniel Spiewak

---

P1可以从任何地方开始。如果两个玩家随后采用最佳策略，则P2可以对P1的第一个移动做出回应，从而为P1创造一场获胜的比赛，不论可能的第一步如何。 - djechlin

Answer 9

本答案假定您已经了解如何实现P1的完美算法，并讨论如何在与普通人类玩家的条件下取得胜利，因为他们会比其他人更常犯错误。

当然，如果两个玩家都以最佳方式进行游戏，则游戏应该以平局结束。在人类水平上，P1在角落里玩游戏往往会赢得更多。由于某种心理原因，P2被诱骗认为在中心玩游戏并不那么重要，这对他们来说是不幸的，因为这是唯一不会为P1创造获胜游戏的反应。

如果P2正确地在中心阻止了，P1应该在相反的角落里玩游戏，因为出于某种心理原因，P2会更喜欢玩角落，这又会为他们产生一个输掉的棋盘。

对于P1可能做出的任何起始移动，如果两个玩家此后都以最佳方式进行游戏，P2可能做出的一步移动将为P1创造一个获胜。从这个意义上说，P1可以随便玩。边缘移动是最弱的，因为对这个移动的可能响应的最大分数产生平局，但仍然有响应会为P1创造一个获胜。

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

下一个挑战，你可以通过人工操作或图形用户界面来实现，就是不显示棋盘。人类肯定能记住所有状态，但增加的挑战会导致对称棋盘更受欢迎，因为它们需要记忆的努力较少，从而导致我在第一分支中概述的错误。

我在聚会上非常有趣，我知道。

- djechlin

---

我在派对上也很有趣 - 我们应该聚一下... 因此，我不同意你的说法，即P1在角落里玩游戏会更容易获胜。你有参考资料吗？我的分析显示中心是最好的，尽管这取决于玩家类型：http://blog.maxant.co.uk/pebble/2018/04/07/1523086680000.html - Ant Kutschera

@AntKutschera 没有参考资料，只是个人经验，但我感到自信，因为心理/直觉非常强大，非正统的开局需要非正统的应对。如果玩家出于其他原因有先前的假设或被预先激活了，那么这种策略可能行不通。 - djechlin

Answer 10

一个基于极小化极大算法的井字棋适应版

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

我们需要一个能够检查结果的函数。该函数将检查一系列字符。无论棋盘的状态如何，结果都是以下四个选项之一：不完整、玩家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
}

Our getBestMove function will receive the state of the board, and the symbol of the player for which we want to determine the best possible move. Our function will check all possible moves with the getResult function. If it is a win it will give it a score of 1. if it's a loose it will get a score of -1, a tie will get a score of 0. If it is undetermined we will call the getBestMove function with the new state of the board and the opposite symbol. Since the next move is of the oponent, his victory is the lose of the current player, and the score will be negated. At the end possible move receives a score of either 1,0 or -1, we can sort the moves, and return the move with the highest score.

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, 更详细地解释过程

- Ben Carp