gpt4 book ai didi

python - Minimax 解释 "for dummies"

转载 作者:太空狗 更新时间:2023-10-29 18:29:06 27 4
gpt4 key购买 nike

我对算法很陌生,我试图理解 minimax,我阅读了很多文章,但我仍然不知道如何将它实现到 python 中的井字游戏中。你能试着用一些伪代码或一些 python 代码尽可能简单地向我解释它吗?

我只需要了解它是如何工作的。我读了很多关于它的资料,我了解基本知识,但我仍然不明白它是如何还手的。

如果可以,请不要给我链接教程和示例,例如 (http://en.literateprograms.org/Tic_Tac_Toe_(Python)) ,我知道它们很好,但我只需要一个白痴解释。

感谢您的宝贵时间:)

最佳答案

“minimax”的想法是,在两人游戏中,一个玩家试图最大化某种形式的分数,而另一个玩家试图最小化它。例如,在 Tic-Tac-Toe 中,X 的获胜可能记为 +1,O 的获胜记为 -1。 X 将是最大玩家,试图最大化最终得分,而 O 将是最小玩家,试图最小化最终得分。

X 被称为最大玩家,因为当它是 X 的着法时,X 需要选择一个使该着法后的结果最大化的着法。当 O 玩家时,O 需要选择一个移动,使该移动后的结果最小化。这些规则递归应用,例如如果只有三个棋盘位置可供下,X 的最佳下法是迫使 O 选择值(value)尽可能高的最小值着法。

换句话说,棋盘位置 B 的博弈论极小极大值 V 定义为

 V(B) = 1   if X has won in this position
V(B) = -1 if O has won in this position
V(B) = 0 if neither player has won and no more moves are possible (draw)

否则

 V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are
the positions available for X, and it is X's move
V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are
the positions available for O, and it is O's move

X 的最优策略总是从 B 移动到 Bi,使得 V(Bi) 最大,即对应于博弈论值 V(B),对于 O,类似地,选择最小的后继位置。

然而,这在国际象棋等游戏中通常无法计算,因为为了计算博弈论值,需要枚举整个博弈树直到最终位置,而这棵树通常非常大。因此,一种标准方法是创造一个“评估函数”,将棋盘位置映射到希望与博弈论值相关的分数。例如。在国际象棋程序中,评估函数往往会为 Material 优势、开放列等给出正分数。极小极大算法会最小化评估函数分数,而不是棋盘位置的实际(不可计算的)博弈论值。

minimax 的一个重要的标准优化是“alpha-beta 剪枝”。它给出的结果与极小极大搜索相同,但速度更快。 Minimax 也可以根据“negamax”进行转换,其中得分的符号在每个搜索级别都反转。它只是实现 minimax 的另一种方法,但以统一的方式处理玩家。其他博弈树搜索方法包括迭代加深、证明数搜索等。

关于python - Minimax 解释 "for dummies",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10626766/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com