我正在为标准8*8的跳棋游戏编写AI。该状态由表示棋盘上棋子的坐标列表的“镜头”来表示。我试图按照以下伪代码执行Min-Max搜索。
function minimax(position, depth, maximizingPlayer)
if depth == 0 or game over in position
return static evaluation of position
if maximizingPlayer
maxEval = -infinity
for each child of position
eval = minimax(child, depth-1, False)
maxEval = max(maxEval, eval)
return maxEval
else
minEval = +infinity
for each child of position
eval = minimax(child, depth-1, true)
minEval = min(minEval, eval)
return minEval
据我理解,在我的情况下,
position
指的是GameState
。因此在我的程序中,我希望调用minimax
函数来处理GameState
的所有子节点,每个子节点只是应用了一个移动后得到的GameState
。最终,当深度为0时,我将返回一个已编写好的函数计算出的启发式值。我遇到的问题是如何迭代每个移动后可能产生的GameState
。我有一个函数可以计算从特定GameState
可以进行的所有可能移动,但我卡在了如何迭代所有这些移动上,以及如何针对每个移动调用经过新移动后的GameState
的minimax
函数。回到伪代码,我知道
child
将是一个函数调用applyMove
,它接受一个移动和当前GameState
,并返回一个具有新位置的状态。每个“child”将是不同的GameState
,是由不同的移动产生的。我对Haskell很陌生,我知道我可能需要使用fold。但我不知道如何编写它,并且很难找到与我的情况相符的示例。非常感谢任何建议或提示。移动列表将类似于
[[(1,2),(2,3)],[(3,6),(2,7)]]
,GameState
的child
将是应用移动后的GameState
,例如:applyMove [(1,2),(2,3)] gameState
。
maximumBy snd
或其他替代maximum
的方法即可。 - amalloyapplyMove pos
改为(flip applyMove pos)
以保持相同的类型。我认为我的顺序更好,因为它更适合你通常会做的部分应用程序(即,在同一棋盘上应用多个不同的动作)。你的版本使得在许多不同的棋盘上应用相同的动作变得容易,这似乎不太常见。然而,这是一个非常微妙的差别,并且也有支持你的类型更好的论点。 - amalloynegate . negate . negate ... . eval
延迟计算。此外,我认为maximum . map negate
可以被negate . minimum
替换,这应该只执行一次否定。 - chi