极小极大搜索算法中的无限循环 netlogo

Question

我正在尝试为井字游戏编写一个简单的极小极大搜索算法，o 玩家由用户控制，但 x 玩家由极小极大算法控制。尽管我设置了深度限制让它停止，但它仍然无限循环。

这是极小极大过程的代码：

to-report minimax [board]
  ifelse (has-any-player-won? (evaluate board)) or (not moves-left? board)
  [
    report (list -1 -1 calculate-utility (evaluate board) 0)
  ]
  [
    report max-value board 0 10
  ]
  report (list -1 -1)
end

to-report min-value [board depth limit]

  let result [-1 -1 1000]

  ifelse (has-any-player-won? (evaluate board)) or (not moves-left? board)
  [
    report (list -1 -1 calculate-utility (evaluate board) depth)
  ]
  [
    let best 1000

    ifelse (depth = limit)
    [
      set result (list -1 -1 best)
      report result
    ]
    [
      foreach (find-empty-spaces board)
      [ space ->
        let tempBoard replace-in-board (item 0 space) (item 1 space) board "o"
        let temp max-value tempBoard (depth + 1) limit
        let score (item 2 temp)
        if score > best
        [
          set best score
          set result (list (list (item 0 space) (item 1 space)) best)
        ]
      ]
      report result
    ]
  ]
end


to-report max-value [board depth limit]
  let result [-1 -1 -1000]

  ifelse (has-any-player-won? (evaluate board)) or (not moves-left? board)
  [
    report (list -1 -1 calculate-utility (evaluate board) depth)
  ]
  [
    let best -1000
    
    ifelse (depth = limit)
    [
      set result (list -1 -1 best)
      report result
    ]
    [
      foreach (find-empty-spaces board)
      [ space ->
        let tempBoard replace-in-board (item 0 space) (item 1 space) board "x"
        let temp min-value tempBoard (depth + 1) limit
        let score (item 2 temp)
        if score < best
        [
          set best score
          set result (list (list (item 0 space) (item 1 space)) best)
        ]
      ]
      report result
    ]
  ]
end

board

变量是一个二维列表，用于存储

x

、

o

或

_

的字符串（表示空白）。

evaluate-board

返回 10 或 -10，具体取决于

x

或

o

分别获胜。

如果

calculate-utility

，则 

score - depth

返回

score = 10

；如果

score + depth

，则返回 

score = -10

我认为问题可能与我如何返回带有最佳移动坐标和分数或深度限制的列表有关。当达到深度限制时，我想停止极小极大搜索并返回当前的最佳选项。但是，看起来即使被击中，它也会继续寻找。

...empty spaces: [[0 1] [0 2] [1 2] [2 2]]
score: -1000
depth hit, returning best
call max value
empty spaces: [[0 1] [0 2] [1 2] [2 2]]
score: -1000
depth hit, returning best
call max value...

从这个输出来看，它似乎没有移动更多的空间，而且分数也没有改变。分数确实偶尔会改变，我可以看到像 0、1 和 -2 这样的值。

任何帮助使其发挥作用的帮助将不胜感激。

Answer 1

你能发布完整的代码吗？