Minimax解释“傻瓜”

我很新的算法，我试图理解最小极小，我读了很多文章，但我仍然无法得到如何实现它到井字游戏python游戏。你可以试着用一些伪代码或python代码尽可能简单地向我解释一下吗？Minimax解释“傻瓜”

我只需要了解它是如何工作的。我读了很多关于这方面的内容，并且我理解了基本内容，但是我仍然无法知道它是如何返回移动的。

如果你可以请不要链接我的教程和样本像（http://en.literateprograms.org/Tic_Tac_Toe_(Python）），我知道他们很好，但我只需要一个白痴的解释。

感谢您的时间:)

2012-05-16 Edoardo Sparkon Dominici

正在做作业吗？ – Jordan

我仍然在高中......我为激情学习:) –

“minimax”的想法是，在双人游戏中，一个玩家试图最大化某种形式的分数，另一个玩家试图将其最小化。例如，在Tic-Tac-Toe中，X的胜利可以被评为+1，而O的胜利被评为-1。 X会成为最大的球员，试图最大限度地提高最终得分，并且O会成为最小球员，试图最小化最终得分。

X被称为最大玩家，因为当它是X的移动时，X需要选择一个移动来最大化移动后的结果。当O球员时，O需要选择一个移动，使移动后的结果最小化。这些规则以递归方式应用，例如如果只有三个棋盘位置开放，X的最佳表现就是促使O选择一个价值尽可能高的最小值移动的棋子。

换言之，在博弈论极小极大值V为一个板位置B定义为

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的最优策略是总是从乙移动到Bi使得V（Bi）最大，即对应于博弈理论值V（B），对于O，类似地，选择最小后继位置。

但是，这通常不可能在象棋这样的游戏中计算，因为为了计算游戏理论值需要枚举整个游戏树直到最终位置，并且该树通常是非常大的。因此，一种标准的方法就是设置一个“评估函数”，将棋盘位置映射到希望与游戏理论值相关的分数。例如。在国际象棋程序中，评估函数倾向于给予材料优势的积极分数，开放列等。最小化算法，它们使评估函数分数最小化，而不是实际（未计算）的棋盘位置的博弈理论值。

minimax的一个重要的标准优化是“alpha-beta修剪”。它给出了与minimax搜索相同的结果，但速度更快。 Minimax也可以按照“negamax”进行铸造，其中每个搜索级别的分数符号都被颠倒过来。这只是一种实现超级极小的替代方式，但是可以统一处理玩家。其他游戏树搜索方法包括迭代加深，证明号码搜索等。

来源

2012-05-17 15:29:14

感谢您花时间解释这一点，我搜索了一会儿才找到这篇文章，它有助于了解minimax – Rick

极小是探索在两个玩家的游戏潜在的移动交替轮流空间的一种方式。你试图赢得胜利，而你的对手正试图阻止你赢。

一个关键的直觉是，如果它现在轮到你了，那么保证你获胜的两步移动序列没有用，因为你的对手不会与你合作。你试图做出让你获胜的机会最大化的动作，并且你的对手进行动作可以最大限度地减少获胜的机会。

由于这个原因，探索你对你造成伤害的移动分支并不是很有用，或者移动你的对手使得对你有好处。

来源

2012-05-16 22:22:25 recursive

好的......但是我怎样才能将它应用在一个tic tac toe游戏中呢？ –

Minimax解释“傻瓜”

回答

相关问题