人工智能 |
您所在的位置：网站首页 › 博弈树的基本构成要素 › 人工智能 |
人工智能
|
一、概述
博弈的概念 博弈是一类具有智能行为的竞争活动，如下棋、战争等。 博弈的类型 双人完备信息博弈：两位选手（例如MAX和MIN ）对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。机遇性博弈：存在不可预测性的博弈，例如掷币等。博弈树 若把双人完备信息博弈过程用图表示出来，就得到一棵与/或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走步的结点称为MAX结点，下一步该MIN走步的结点称为MIN 结点。 博弈树的特点 博弈的初始状态是初始结点；博弈树中的“或”结点和“与”结点是逐层交替出现的；整个博弈过程始终站在某一方的立场上，例如MAX方。所有能使自己一方获胜的终局都是本原问题，相应的结点是可解结点；所有使对方获胜的终局都是不可解结点。 二、极大极小过程（1）算法思想 极大极小过程用当前正在考察的结点生成一棵部分博弈树，并利用估价函数f(n)对叶结点进行静态估值。 求叶结点的值 对MAX有利的结点，其估价函数取正值对MIN有利的结点，其估价函数取负值使双方均等的结点，其估价函数取接近于0的值。求非叶结点的值： 必须从叶结点开始向上倒退。其倒退方法是： 对于MAX结点，由于MAX 方总是选择估值最大的走步，因此，MAX结点的倒退值应该取其后继结点估值的最大值。对于MIN结点，由于MIN方总是选择使估值最小的走步，因此MIN结点的倒推值应取其后继结点估值的最小值。这样一步一步的计算倒推值，直至求出初始结点的倒推值为止。这一过程称为极大极小过程。（2）极大极小过程实例 （1）算法思想 极大极小过程是先生成与/或树，然后再计算各结点的估值，这种生成结点和计算估值相分离的方式，需生成规定深度内的所有结点，搜索效率较低。如果能边生成结点边对结点估值，并剪去一些没用的分枝，这种技术被称为α-β剪枝。 剪枝方法 MAX结点（或结点）的α值为当前子结点的最大倒推值；MIN结点（与结点）的β值为当前子结点的最小倒推值；α-β剪枝的规则如下： β剪枝： 任何MAX结点n的α值大于或等于它先辈结点的β值，则n 以下的分枝可停止搜索，并令结点n的倒推值为α。这种剪枝称为β剪枝。α剪枝： 任何MIN结点n的β值小于或等于它先辈结点的α值，则n 以下的分枝可停止搜索，并令结点n的倒推值为β。这种剪枝称为α剪枝。（2）α-β剪枝实例
1. 剪枝1： 详解： 由F、G的倒推值可推出结点C的倒推值≥4 ，再由C可推出结点A的倒推值≤4，即A的β值为4。另外，由结点P、Q推出的结点I的倒推值为5，因此D的倒推值 ≥5，即D的α值为5。此时，D的其它子结点的倒推值无论是多少都不能使D及A的倒推值减少或增大，所以D的其他分枝被减去，并可确定A的倒推值为4 。 3. 其它剪枝（省略） |
α剪枝： MIN结点G的β值(=4)，结点G不可能让先辈结点C的α值增大，则G以下的分枝可停止搜索，并令结点n的倒推值为β(=5）大于它先辈结点A的β值（=5）。这种剪枝称为β剪枝。【本文地址】