algorithm - 极小极大算法的伪代码

Question

我想得到 minmax 算法的伪代码。我必须制作 2 个函数，def maxAgent(gameState, depth) 和 minAgent。是否有任何机构拥有正确且简单的伪代码。

Answer 1

A 和 B 两个玩家轮流下棋。

我们得到了一个评分函数 f，它评估给定的棋盘位置 P。f(P) 的值越大，A 越好，B 越差(即，f(P) 是对 P 的“好”程度的估计是针对 A 的，无需做任何进一步的前瞻)。

考虑棋盘位置 P。

如果 P 是叶节点(即，P 是获胜位置，或者我们已经尽可能地向前看)，那么我们返回 f(P) 作为该节点的分数。

否则 P 不是叶节点并且有子节点 C1, ..., Cn。我们递归地计算 children 的分数，给出 S1, ..., Sn。

如果 A 在 P 下棋，那么 P 的得分是 max{S1, ..., Sn}，因为 A 总是会最大化他的优势。

如果 B 在 P 下棋，那么 P 的分数是 min{S1, ..., Sn}，因为 B 总是会下棋以最小化 A 的优势。

这应该足以转化为代码。

完成该操作后，请查看 alpha-beta 修剪，它应该(极大地)减少您需要执行的搜索量。 Alpha-beta 修剪基于这样的想法，即如果 A 推断 B 可以发挥作用以迫使 A 的最大优势成为 M，那么考虑任何得分大于 M 的子树就没有意义，因为 B 永远不会允许 A 选择!