让计算机永远不会丢失在Tic-Tac-Toe

Question

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

我读过有关minimax算法的内容,但我不明白.如何使用此算法使计算机能够赢或赢但永不丢失？

Answer 1

解决这类问题的方法是探索可能的未来.通常(对于国际象棋或选秀AI)你会考虑未来一定数量的前进,但因为tic tac toe游戏太短,你可以探索到游戏结束.

概念实施

所以你创建了一个分支结构:

• 人工智能想象自己做出一切合法的举动
• 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移动都会调用这个函数)并且不会返回未来将采用的路径(我们无法知道用户是否会以最佳方式进行播放以便这样做信息是无用的),但它总会选择朝着人工智能的最佳未来迈进的方向.

对更大问题的考虑

在这种情况下,你探索到游戏的结尾,很明显哪个最好的未来是(赢,输或抽),但如果你只是(例如)未来的五个动作,你会必须找到一些方法来确定; 在国际象棋或草稿中,单位得分是最简单的方法,单位位置是有用的增强.