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

对于节点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

对于节点B = min(4,6)= 4
对于节点C = min(-3，7)=-3

对于节点A max(4，-3)= 4

Mini-Max算法的属性:

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

(bm)。

minimax算法的局限性: