tic-tac-toe - 使计算机永远不会在井字游戏中迷路

Question

我正在为C的Tic Tac Toe代码编写一个简单的游戏。我已经完成了大部分代码，但是我希望AI永不丢失。

我已经阅读了有关minimax算法的信息，但我不理解。如何使用此算法使计算机获胜或平局，但永不丢失？

Answer 1

解决此类问题的方法是探索可能的 future 之一。通常(对于国际象棋或制图AI)，您会认为 future 有一定的涨幅，但由于井字游戏太短了，您可以探索到游戏结束。

概念实现

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

AI想象自己会采取一切合法行动

他们想象的AI是用户在每次合法举动之后可以做出的每个合法举动

然后，AI想象其接下来的每个合法举动

等。

然后，从最分支的一端(时间最远的一端)出发，轮到其的玩家(AI或用户)在每个分支点上选择哪个最适合其 future (赢，输或平)。然后将它移交给树上更高的玩家(更接近当前位置)；每次为假想转折点为的玩家选择最佳的 future ，直到最后您到达AI的第一个分支点，AI都可以看到朝着它输，赢和赢的 future 。它选择一个获胜的 future (或如果没有可用的平局)。

实际执行

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

在这里，这种方法与递归函数很好地结合使用。该函数的每个级别都会轮询其所有分支。将可能的 future 传递给他们，并返回-1,0，+ 1；在每个点上为当前玩家选择最佳得分 。高层选择移动时并不实际知道每个 future 的表现如何，以及他们的表现如何。

伪代码

我假设在此伪代码中+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每次移动时都会调用此功能)，并且不会返回 future 的发展方向(我们不知道用户是否会玩得尽善尽美，信息是没有用的)，但它始终会选择朝着AI的最佳 future 发展的方向。

较大问题的注意事项

在这种情况下，您探索游戏的结尾时，很明显，最好的 future 是(赢，输或平)，但是如果您仅(例如)走五步，那您将必须找到确定这一点的方法；在国际象棋或跳棋中，计件分数是最简单的方法，而计件位置是一种有用的增强方法。