在学习算法极大极小 (修剪阿尔法 – 公测) 征询他的许多文章，感觉您的帖子 QUANG怀尔德的BLOG 相对简单和详细. 我们感谢文章的作者，并要求被引用的作者, 参考你的文章的内容.

在一场比赛中，两个人把其作为国际象棋的国家, 棋, 卡洛,… 游戏中有一个开始，每一个国家的举动将改变当前状态到新的状态. 本场比赛将在一定规定结束, ，一个游戏，这将导致状态反映一个胜利者或者其中两个球员不能发挥他们的举动的状态, 我把它称为和平标志状态. 我们试图分析是否从某种状态会导致玩家将有条件赢得双方球员都在同一水平.

这样的游戏可以用一棵树来表示, 所谓树游戏. 树的每个节点代表一个国家. 根节点代表的游戏状态的开始. 每个叶节点代表了游戏的最终状态 (获奖或空调). 如果状态x由子节点n表示n表示水的结果的最新状态可以从状态x.

例 3-5: 在跳棋游戏 9 伞. 两个人翻至X或O-. 这些谁去都 3 车排队 (横, 纵, 斜) 获奖者. 如果每个细胞类型还没有定论，这两位球员配合. 这个游戏的一部分由后的树表示:

在游戏中树, 叶节点阴影的背景，有时边界来区分与其它节点. 我们可以分配一个值，每个叶结点，以反映获胜的状态或画球员. 这样的叶节点分配了以下值:

· 1 如果在那个车手已经赢得了X,

· -1 如果人们去那里，失去了X

· 0 如果两个玩家有狄更斯.

因此，在任何状态, 轮到他, X车手会选择导致一个国家的最大价值一招 (在这种情况下， 1). 我们说X移动选择MAX, X选择的节点从他的动作被称为按钮MAX. 反过来O型会选择导致一个国家与最小值一招 (在这种情况下， -1, 那么X将失去等等Ø胜). 我们说选择的最低输出动作, Ø选择的节点从他的动作被称为节点MIN. 难道两名球员轮流他们的国家应该在树上游戏关卡以及MAX和MIN几个luanphien. 树游戏，所以也被称为树MIN-MAX. 我们可以提供在树节点的处理规则，以反映现状的两名球员或赢得和平和可能性胜.

如果一个节点是叶节点，那么它的值是分配给该按钮的值. 相反, MAX按钮，如果按钮其子项的所有值的最大值，其值. 如果按钮按钮分钟，然后它的值是所有孩子的对待它的最小值.

这种处理规则类似于算术表达式树规则, 这里所不同的是操作者是最大或最小函数采用与每个按钮可以有更多的孩子. 因此，我们可以利用这项技术来治疗回溯树节点游戏.

要安装一些假设，我们有以下几点:

· 我们学校 信息 给出的值.
· 常量 2 和 -2 分别最大和每个节点的最小值.
· 一个变种 Ç 烧焦确定值X或O按钮去.
· 另一种类型 指针 宣布以适当的方式来表示在树中的节点反映的发挥状态.
· 我们有一个函数 nutLa() 以确定是否一个节点是叶节点或不?
· 颚 最大和最小 分别取两个值中的最大值和最小值.

算法完备集的树木游戏
颚 VAL q按键和进入一个字符c返回节点的值.

如果q是叶节点，其返回值已被分配给叶节点. 相反，一个价值，我们给Q值是暂时的 -2 或 2 根据q是X或O按钮和Q的审查. 一旦q的值，将复位VAL = 2V以下(VAL,该) 如果q是X按钮和值=分钟(VAL,该) 如果q O按钮. 当所有的孩子们在Q val的Q值暂时成为其价值.

{Ham tra ve gia tri trang thai khi dung minmax - thuat toan minmax}
function val(var q: pointer; c: char; Vp: item): item;
var
	i: integer;
begin
	if (nutLa(q)) then      {Neu la nut la thi lay ngay KQ gia tri cua nut do}
        begin
                {writeln(q^.lab,'->>> ', q^.info);}
                val:= q^.info;
        end
	else
	begin
		for i:= 1 to q^.numChild do   {Duyet cac nut con cua q}
		begin
			if c = 'X' then       {Neu dang la luot X}
			begin
				q^.info:= max(q^.info, val(q^.child[i], 'O', q^.info));
				{writeln(q^.lab,'->>> ', q^.info);}
				val := q^.info;
            end
			else                    {Nguoc lai la luot O}
			begin
				q^.info:= min(q^.info, val(q^.child[i], 'X', q^.info));
				{writeln(q^.lab,'->>> ', q^.info);}
				val := q^.info;
				break;
			end;
		end;
	end;
end;

适用于一般的树T已安装:

procedure catTia(var T: pointer);  {Dua thuat toan vao cay}
var
	p: pointer;
	i: integer;
begin
	if T <> nil then
	begin
		T^.info := val (T, 'X', T^.info);
	end;
end;

完整的程序，你可以看到 这里

阅读更多: 一般的树