AI Mini-Max算法



AI Mini-Max算法

Mini-max算法是一种递归或回溯算法,用于决策和博弈论中。假设对手也在最佳状态下玩耍,它可以为玩家提供最佳移动方式。
Mini-Max算法使用递归来搜索游戏树。
Min-Max算法主要用于AI中的游戏。例如国际象棋,西洋跳棋,井字游戏,围棋以及各种拖车游戏。该算法计算当前状态的极大极小决策。
在这种算法中,两个玩家玩游戏,一个叫做MAX,另一个叫做MIN。
这两个玩家都在与之战斗,因为对手的玩家获得的利益最小,而他们却获得了最大的利益。
游戏的两个玩家都是彼此的对手,其中MAX将选择最大值,而MIN将选择最小值。
minimax算法执行深度优先搜索算法来探索完整的游戏树。
minimax算法一直进行到树的终端节点,然后作为递归回溯树。

MinMax算法的伪代码:

function minimax(node, depth, maximizingPlayer) is
if depth ==0 or node is a terminal node then
return static evaluation of node
if MaximizingPlayer then      // for Maximizer Player
maxEva=-infinity          
 for each child of node do
 eva= minimax(child, depth-1, false)
maxEva= max(maxEva,eva)        //gives Maximum of the values
return maxEva
else                         // for Minimizer player
 minEva= +infinity 
 for each child of node do
 eva= minimax(child, depth-1, true)
 minEva= min(minEva, eva)         //gives minimum of the values
 return minEva
    

初始呼叫:
Minimax(node,3,true)

最小-最大算法:

可以使用示例轻松描述minimax算法的工作。下面我们以代表两人游戏的游戏树为例。
在此示例中,有两个参与者,一个被称为Maximizer,另一个被称为Minimizer。
Maximizer将尝试获得最大可能的得分,而Minimizer将尝试获得最小可能的得分。
此算法应用DFS,因此在此游戏树中,我们必须一直穿过树叶到达终端节点。
在终端节点处,给出了终端值,因此我们将比较这些值并回溯树直到出现初始状态。以下是解决两人游戏树所涉及的主要步骤:

步骤1: : 第一步,算法将生成整个游戏树,并应用效用函数以获取终端状态的效用值。在下面的树图中,让我们以A为树的初始状态。假设最大化器首先旋转,其初始值最差=-infinity,而最小化器接下来旋转,其初始值最差= + infinity。

AI Mini-Max算法_https://bianchenghao6.com_【ai 教程】_第1张

步骤2: 现在,我们首先找到Maximizer的效用值初始值为-∞,因此我们将终端状态下的每个值与Maximizer的初始值进行比较,并确定较高的节点值。它将在所有之间找到最大值。

对于节点D max(-1,--∞)=> max(-1,4)= 4
对于节点E max(2,-∞)=> max(2,6)= 6
对于节点F max(-3,-∞)=> max(-3,-5)=-3
对于节点G max(0,-∞)= max(0,7)= 7
AI Mini-Max算法_https://bianchenghao6.com_【ai 教程】_第2张

步骤3: 下一步,轮到最小化器了,因此它将所有节点值与+∞进行比较,并找到3
rd 层节点值。

对于节点B = min(4,6)= 4
对于节点C = min(-3,7)=-3
AI Mini-Max算法_https://bianchenghao6.com_【ai 教程】_第3张

步骤3: 现在轮到Maximizer了,它将再次选择所有节点的最大值,并找到根节点的最大值。在此游戏树中,只有4层,因此我们可以立即到达根节点,但在实际游戏中,将超过4层。

对于节点A max(4,-3)= 4
AI Mini-Max算法_https://bianchenghao6.com_【ai 教程】_第4张

minimax两人游戏。

Mini-Max算法的属性:

完成-最小-最大算法已完成。肯定会在有限搜索树中找到一个解决方案(如果存在)。
最佳-如果两个对手的比赛都达到最佳,则"最小-最大"算法是最佳的。
时间复杂度-,因为它为游戏树执行了DFS,所以Min-Max算法的时间复杂度为 O(b m ),其中b是游戏树的分支因子,m是树的最大深度。
空间复杂度- Mini-max算法的空间复杂度也与DFS类似,即Dstrong

(bm)。

minimax算法的局限性:

minimax算法的主要缺点是,对于复杂的游戏(例如国际象棋,围棋等),它的运行速度非常慢。游戏类型具有巨大的分支因素,玩家可以选择很多选择。我们可以在下一个主题中讨论的
alpha-beta修剪来改善minimax算法的这一局限性。