algorithm - 实现极小极大算法

Question

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

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

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

我希望 MakeBestMove 返回最佳着法，我的 MiniMax 函数返回 boardState 的分数。

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

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

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

代码行为问题: 1. MakeBestMove中没有正确返回bestMove 2. 虽然 Minimax 函数似乎通过递归迭代不同的终端 boardStates 来正确运行，但 MakeBestMove 不会阻止“O”的移动，但会在它离开一个移动时采取获胜的移动。

我希望我的代码如何表现:1. 对 boardState 正确评分的能力(我相信我已经在做了。)2. 如果 boardState 是终端，或者如果没有更多的移动(我正在做)，则能够返回该分数3. 能够使用该分数做出最佳移动选择(这就是问题所在)

编辑 我想添加在我的程序中进行的调用的“遍历”，以防您想通过 Visual Studio 运行我的代码并对其进行测试。

在 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。