实现极小极大算法

Question

我已经在网上搜索了同一领域的伪代码、工作示例、堆栈溢出 problems/solutions，但到目前为止我还没有找到任何有用的东西，所以我在这里伸出援手。

我正在尝试以非常基本的方式在我的 Tic Tac Toe 游戏中实现 Minimax 算法（没有 alpha/beta p运行ing）。让我解释一下我拥有的每个辅助方法，然后如果您需要，我可以分享我的部分实际代码。注意（我在检查终端状态时没有使用深度，只检查获胜或平局。）

首先，我有实用程序 MakeBestMove，它将在计算机移动时调用，然后在 MakeBestMove 中调用 MiniMax，然后 MiniMax 将自行调用，直到 boardState 达到终止状态或没有移动为止。

我希望 MakeBestMove 成为 return 最佳移动，我的 MiniMax 函数成为 return boardState 的分数。

如果您熟悉 MiniMax，当状态为终端时，状态会被计分。我用 -100 表示玩家 O 获胜，100 表示玩家 X 获胜，0 表示平局来计分我的游戏。这是在我的 EvaluateScore 助手中完成的 function.I 也有一个函数可以根据游戏板的当前状态确定可用的动作，以帮助我迭代打开的动作。此外，可能需要注意的是玩家 "X" 始终是人类，而玩家 "O" 始终是计算机。

我正在尝试使用我在 Python 中使用的相同方法通过 F# 实现 MiniMax，理论上它应该可以工作，即使它不忠于 F# 函数范例。

出于某种原因，它的行为与我预期的不同。我花了几个小时检查每一行代码以确保我没有任何奇怪的副作用，但没有取得任何成功。如果有人能指出我正确的方向，我将不胜感激。我知道我写得非常命令，但我确实认为它可以这样工作，但似乎无法弄清楚为什么它不会以及我可能会遗漏什么。任何帮助是极大的赞赏！

代码行为问题： 1. MakeBestMove中的returnbestMove不正确 2. 虽然 Minimax 函数似乎通过递归遍历不同的终端 boardStates 来正确运行，但 MakeBestMove 不会阻止 "O" 的移动，但会在它离开一个移动时采取获胜的移动。

我希望我的代码如何表现： 1. 对 boardState 正确评分的能力（我相信我已经在做了。） 2. 能够 return 如果 boardState 是终端，或者如果没有更多的动作可以采取（我正在做） 3. 能够使用该分数做出最佳着法选择（这就是问题所在）

编辑我想在我的程序中添加一个 'walk through' 调用，以防你想运行我的代码通过 Visual Studio 并进行测试。

In Program.fs 是我的代码开始的地方，当它调用 ComputerPlayerTurn() 然后它将使用 Game.fs，其中 ComputerPlayerTurn() 被调用然后将初始化变量 let mutable computerMove 到 = MakeBestMove(board)。在 MakeBestMove(board) 被调用之后，函数内就是 MiniMax(board) marker 被调用的地方。

以下代码是我发现行为问题的地方：

let rec MiniMax(board) marker = 
    let mutable bestValue = 0
    let mutable board = board
    let mutable moves = GetListOfMoves(board) 
    if GameWon(board) marker = true || GetListOfMoves(board).Count = 0 then
        bestValue <- EvaluateScore(board)
    else
        if marker = "X" then
            bestValue <- -100
            for move in moves do  
                board <- ModifyBoard(board) move marker
                bestValue <- max(MiniMax(board) "O")(bestValue) 
                board <- ModifyBoard(board) move " "
            bestValue <- bestValue
        else 
            bestValue <- 100
            for move in moves do  
                board <- ModifyBoard(board) move marker
                bestValue <- min(MiniMax(board) "X")(bestValue) 
                board <- ModifyBoard(board) move " "
            bestValue <- bestValue
    bestValue

let MakeBestMove (board) marker = 
    let mutable board = board
    let mutable bestMove = 0
    let mutable bestValue = 0
    let mutable bestMoves = ResizeArray<int>()
    let moves = GetListOfMoves(board)
    for move in moves do
        board <- ModifyBoard(board) move marker
        bestValue <- MiniMax(board) "X" 
        board <- ModifyBoard(board) move " "
        if marker = "X" then
            if bestValue = 100 then
                bestMove <- move
            if bestValue > 0 then
                bestMoves.Add(move)
            else if bestValue = 0 then
                bestMoves.Add(move)
        elif marker = "O" then
            if bestValue = -100 then
                bestMove <- move
            if bestValue < 0 then
                bestMoves.Add(move)
            else if bestValue = 0 then
                bestMoves.Add(move)
    if bestMove = 0 && bestMoves.Count > 0 then
        bestMove <- bestMoves.[0]
    elif bestMove <> 0 then
        bestMove <- bestMove
    else
        bestMove <- GetListOfMoves(board).[0]
    bestMove

我的代码在我存储库的 MASTER 分支上 Github：https://github.com/sinnmk/fsharp-tictactoe

Answer 1

问题出在这里：

if ((GameWon(board) marker) = true || (moves.Count = 0)) then

它只考虑 marker 获胜的平局和比赛。它还应该考虑 marker 失败的游戏：

if GameWon board "O" || GameWon board "X" || moves.Count = 0 then

我删除了不必要的括号和条件，例如 = true。

实现极小极大算法

Implement Minimax Algorithm

algorithm

f#

artificial-intelligence

minimax