我正在为C的Tic Tac Toe代码编写一个简单的游戏。我已经完成了大部分代码,但是我希望AI永不丢失。
我已经阅读了有关minimax算法的信息,但我不理解。如何使用此算法使计算机获胜或平局,但永不丢失?
最佳答案
解决此类问题的方法是探索可能的 future 之一。通常(对于国际象棋或制图AI),您会认为 future 有一定的涨幅,但由于井字游戏太短了,您可以探索到游戏结束。
概念实现
因此,您创建了一个分支结构:
然后,从最分支的一端(时间最远的一端)出发,轮到其的玩家(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 是(赢,输或平),但是如果您仅(例如)走五步,那您将必须找到确定这一点的方法;在国际象棋或跳棋中,计件分数是最简单的方法,而计件位置是一种有用的增强方法。
关于tic-tac-toe - 使计算机永远不会在井字游戏中迷路,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17907255/