我对算法很陌生,我试图理解极小极大,我读了很多文章,但我仍然无法在python中实现它如何实现它的tic-tac-toe游戏.您可以尝试使用一些伪代码或一些python代码尽可能简单地向我解释吗？
我只需要了解它是如何工作的.我读了很多关于这个的东西,我理解基本的,但我仍然无法得到它如何回归.
如果你可以请不要链接我的教程和样本(http://en.literateprograms.org/Tic_Tac_Toe_(Python)),我知道它们很好,但我只需要一个白痴的解释.
感谢您的时间 :)
"极小极大"的想法是,在一个双人游戏中,一个玩家试图最大化某种形式的分数,另一个玩家试图最小化它.例如,在Tic-Tac-Toe中,X的胜利可能被评为+1,而O的胜利被评为-1.X将是最大的玩家,试图最大化最终得分而O将是最小玩家,试图最小化最终得分.
X被称为最大玩家,因为当X移动时,X需要选择一个移动,以便在移动后最大化结果.当O队员,O需要选择一个移动,在移动后最小化结果.这些规则递归应用,使得例如,如果只有三个仓板开打,X的最好的戏是迫使O操作选择,其值是尽可能高的最低值的举动之一.
换句话说,板位置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的最优策略是总是从乙移动到碧使得V(Bi)的是最大的,即对应于gametheoretic值V(B),和为O,类似地,选择一个最小后继位置.
然而,这通常不可能在像国际象棋这样的游戏中计算,因为为了计算游戏理论值,需要计算整个游戏树直到最终位置并且该树通常非常大.因此,一种标准的方法是投入一个"评估函数",它将棋盘位置映射到有希望与游戏理论值相关的分数.例如,在国际象棋程序中,评估函数倾向于给出物质优势,开放列等的正分数.最小极大算法它们最小化评估函数得分而不是板位置的实际(不可计算的)游戏理论值.
对minimax的重要标准优化是"alpha-beta修剪".它提供与minimax搜索相同的结果,但速度更快.Minimax也可以用"negamax"表示,其中得分的符号在每个搜索级别都反转.它只是实现minimax的另一种方式,但是以统一的方式处理玩家.其他游戏树搜索方法包括迭代加深,证明号搜索等.