极小化极大算法是基于决策树和搜索的智能系统中的典型算法，可用于指导井字棋、黑白棋、五子棋等经典完全信息零和博弈。虽在学生时代学习过极小化极大算法，但时过境迁，思量该算法的来龙去脉已然如雾里探花水中望月。近来自学人工智能算法，恰好又一次接触到了该算法，也算与其有缘，理应将其悉数记下。下文将以井字棋为例详细说明该算法原理。
2. 博弈树 2.1 井字棋井字棋(Tic-Tac-Toe)是由两个玩家轮流在3X3的格子上标记自己符号（圈或者叉）的游戏，最先以横、直、斜连成一线则获胜，如下图所示。
2.2 博弈树构建以完全信息零和游戏“井字棋”为例，将每一个局面均视为一棵树上一个节点，每一个动作视为树上的边，因此“井字棋”游戏可以被完全展开成一棵树。一局游戏的发展过程是博弈树从根节点到叶结点的一条路径。井字棋的博弈树最高有9层，如下图所示（井字棋博弈树前3层）。
3. 估值函数估值函数使用来给每一个局面给出一个估值，用判断博弈树中当前局面的形势。在传统的棋类游戏智能系统中，估值函数一般是人为指定的，对棋类游戏智能的水平有决定性作用。 估值函数的形式不是固定的，它的输入一般是一个局面的信息，输出是一个表明相应局面好坏程度的数值。为了说明极小化极大算法，