tic-tac-toe - 让电脑在井字游戏中永远不会输

Question

我正在为 C 开发一个简单的井字游戏代码。我已经完成了大部分代码，但我希望 AI 永远不会输。

我已阅读有关极小极大算法的信息，但我不明白。如何使用此算法使计算机能够赢或平局但永远不会输？

Answer 1

解决这类问题的方法之一是探索可能的未来。通常（对于国际象棋或选秀 AI）您会考虑未来一定数量的移动，但由于井字游戏非常短，您可以探索到游戏结束。

概念实现

因此，您创建了一个分支结构：

• 人工智能想象自己做出每一个合法的举动
• 他们的人工智能想象用户在每次合法移动后做出他们可以做出的每一个合法移动
• 然后人工智能想象它接下来的每一个合法动作
• 等等

然后，从分支最多的一端（时间最远）开始，轮到它的玩家（AI 或用户）在每个分支点选择最适合它的未来（赢、输或平）。然后它交给树上更高的玩家（更接近现在）；每次为假想轮到的玩家选择最好的未来，直到最后你处于第一个分支点，AI 可以看到未来的输、平和赢。它选择它获胜的未来（或者如果无法抽签）。

实际执行

请注意，从概念上讲，这是正在发生的事情，但没有必要创建整个树，然后像这样判断它。尽管树会及时到达最远的时间点并随后进行选择，但您也可以轻松地工作。

在这里，这种方法可以很好地与递归函数配合使用。函数的每一级都会轮询它的所有分支；将可能的未来传递给他们并返回 -1,0,+1；在每一点为当前玩家选择最好的分数。高层在实际上不知道每个未来如何发展的情况下选择了这一举措，也不知道他们的表现如何。

伪代码

我假设在这个伪代码中 +1 是 AI 获胜，0 是绘图，-1 是用户失败

determineNextMove(currentStateOfBoard)
    currentBestMove= null
    currentBestScore= - veryLargeNumber

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , AI’sMove)
        if score>currentBestScore
            currentBestMove=legalMove
            currentBestScore=score
        end
    end

    make currentBestMove

end

getFutureScoreOfMove(stateOfBoard, playersTurn)

    if no LegalMoves
       return 1 if AI wins, 0 if draw, -1 if user wins
    end


    if playersTurn=AI’sTurn
        currentBestScore= - veryLargeNumber //this is the worst case for AI
    else
        currentBestScore= + veryLargeNumber //this is the worst case for Player
    end

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , INVERT playersTurn)
        if playersTurn ==AI’sTurn AND score>currentBestScore //AI wants positive score
           currentBestScore=score
        end
        if playersTurn ==Users’sTurn AND score<currentBestScore //user wants negative score
           currentBestScore=score
        end

     end

     return currentBestScore
end

这个伪代码不关心起始板是什么（你调用这个函数，每次 AI 随着当前板移动）并且不返回未来会走什么路径（我们不知道用户是否会以最佳方式玩，所以这个信息是无用的），但它总是会选择走向人工智能最佳未来的行动。

对更大问题的考虑

在这种情况下，你探索到游戏的最后，很明显最好的未来是（赢、输或平），但如果你（例如）未来只走五步，你会必须找到某种方法来确定；在国际象棋或草稿中，棋子得分是最简单的方法，棋子位置是一种有用的增强。

Answer 2

大约5年前我一直在做这样的事情。我做了一个研究。tic tac toe用不了多久，您只需要为前两三个动作准备图案。

您需要检查如何玩：

1. 电脑先启动。
2. 玩家首先开始。

有 9 个不同的起始位置：

但实际上只有 3 个是不同的（其他是旋转的）。所以在那之后你会看到在一些特定的动作之后应该做什么，我认为在这种情况下你不需要任何算法，因为tic tac toe结束是由第一步决定的。因此，在这种情况下，您将需要一些if-elseorswitch语句和random生成器。

Answer 3

tic tac toe属于一组游戏，如果你知道怎么玩就不会丢失，所以对于这样的游戏你不需要使用树和修改排序算法。要编写这样的算法，您只需要几个函数：

1. CanIWin()检查计算机是否连续有 2 个并且可能获胜。
2. ShouldIBlock()检查玩家是否连续没有 2 个并且需要阻止它。

这两个函数必须按此顺序调用，如果它返回，true您需要赢或不让玩家赢。

之后，您需要为移动进行其他计算。

一种独特的情况是计算机开始游戏时。您需要选择属于最多不同方向的单元格（其中有 8 个 - 3 个水平、垂直和 2 个对角线）。在这样的算法中，计算机总是会选择中心，因为它有 4 个方向，你应该增加选择次优选项的可能性，以使游戏更具吸引力。

因此，当您遇到必须移动电路板和计算机的某些选定部分的情况时，您需要对每个空闲单元格进行评级。（如果第一个或第二个函数返回true，你必须在到达这个地方之前采取行动！！！）。因此，要对单元格进行评分，您需要计算每个单元格上剩下多少个开放方向，还需要至少阻止一个对手方向。

之后，您将有几个可能的单元格来标记。因此，您需要检查必要的移动顺序，因为您将有几个选择，并且其中一个可能会导致您失败。所以之后你就已经设置好了，你可以随机选择移动，或者选择得分最高的一个。

正如文章开头所说，我不得不说类似的话。更大的游戏没有完美的策略，可以说国际象棋很大程度上基于模式，但也基于前瞻性思维策略（因为这样的事情是使用patricia trie）。所以总而言之，你不需要复杂的算法，只需要几个函数来计算你的收益和对手的损失。

Answer 4

制作一个辅助程序来预测用户可以获胜的案例。然后你可以说你的人工智能来做用户必须做的事情才能获胜。