1.概述:
博弈是一类具有智能行为的竞争活动,如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈,就是两位选手对垒,轮流走步,每一方不仅知道对方已经走过的棋步,而且还能估计出对方未来的走步。对弈的结果是一方赢,另一方输,或者是双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈是指存在不可预测性的博弈,如掷币等。
2.特点:
若把双人完备信息博弈过程用图表示出来,就得到一棵与/或树,这种与/或树被称为博弈树。在博弈树中,那些下一步该MAX走步的节点称为MAX节点,下一步该MIN走步的节点称为MIN节点。
博弈树具有如下特点:
(1)博弈的初始状态是初始节点;
(2)博弈树中的“或”节点和“与”节点逐层交替出现的;
(3)整个博弈过程始终站在某一方的立场上,例如MAX方。所有能使自己一方获胜的终局都是本原问题,相应的节点是可解节点;所有使对方获胜的终局都是不可解节点。
3.极大极小过程
对简单的博弈问题,可生成整个博弈树,找到必胜的策略。但对于复杂的博弈问题,不可能生成整个搜索树,如国际象棋,大约有10120个节点。一 种可行的方法是用当前正在考察的节点生成一棵部分博弈树,并利用估价函数f(n)对叶节点进行静态估值。一般来说,那些对MAX有利的节点,其估价函数取正值;那些对MIN有利的节点,其估价函数取负值;那些使双方均等的节点,其估价函数取接近于0的值。
为了计算非叶节点的值,必须从叶节点开始向上倒退。其倒退方法是:对于MAX节点,由于MAX方总是选择估值最大的走步,因此,MAX节点的倒退值应该取其后继节点估值的最大值。
则其第一者走棋后的博弈树为:
4. a-β剪枝
极大极小过程是先生成与/或树,然后再计算各节点的估值,这种生成节点和计算估值相分离的搜索方式,需要生成规定深度内的所有节点,因此搜索效率较低。如果能边生成节点边对节点估值,并剪去一些没用的分枝,这种技术被称为a-β剪枝。
a-β剪枝的方法如下:
(1) MAX节点(或节点)的a值为当前子节点的最大倒推值。
(2) MIN节点(与节点)的β值为当前子节点的最小倒推值。
a-p剪枝的规则如下:
(1)任何MAX节点n的a值大于或等于它先辈节点的值,则n以下的分枝可停止搜索,并令节点n的倒推值为a。这种剪枝称为剪枝。
(2)任何MIN节点n的a值小于或等于它先辈节点的a值,则n以下的分枝可停止搜索,并令节点n的倒推值为。这种剪枝称为a剪枝。
下面来看一个a-β剪枝的具体例子,如下图所示。其中最下面一层端节点旁边的数字是假设的估值。在该图中,L、M、N的估值推出节点F的到推值为4,即F的p值为4,由此可推出节点C的到推值>4。