计算机博弈算法初步.pptx

《计算机博弈算法初步.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机博弈算法初步名词解释完备信息动态博弈：是指博弈中信息是完全的，是指每一参与者都拥有所有其他参与者的特征、策略，后动者可以观察到前者的行动，了解前者行动的所有信息。m,n,k游戏：是指m行n列，轮流下子，连成k个棋子判胜。只有先手必胜和平局两种结果。零和博弈：与非零和博弈相对，是博弈论的一个概念，属非合作博弈。指参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为“零”，双方不存在合作的可能。博弈树博弈树是指由于动态博弈参与者的行动有先后次序，因此可以依次将参与者的行动

2、展开成一个树状图形。博弈树的特点：(1)博弈的初始格局是初始节点。(2)在博弈树中，"或"节点和"与"节点是逐层交替出现的。自己一方扩展的节点之间是"或"关系，对方扩展的节点之间是"与"关系。双方轮流地扩展节点。(3)所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。所有的算法都将基于博弈树上进行讲解博弈树实例根节点：面临选择的当前局面。点节点：不为结束，下面仍有分支的节点叶节点：计算结束，没有分支的节点。绘制博弈树对于一个剪刀石头布游戏，我们将规则更改。令甲方先出手，在

3、这之后，乙方再出手。假设我们扮演的是乙方，并且用数字1/0/-1来代表我方胜利/平局/失败。则下图为这个游戏的博弈树。博弈树的复杂度一颗完整博弈树的规模是相当可观的天文数字。中国象棋完整博弈树的节点数高达10^150，据说地球上全部原子的数目也才有10^132。显然是无法全部展开和进行遍历搜索。即使选用搜索速率为1M节点/s的计算机系统，日夜不停地搜索100年，也才只能搜索9层。还达不到一般象棋大师的水平。即或是最简单的牛角棋，如果将博弈树展开15层，还不将无意义的循环走棋的节点计算在内，那有效博弈树的总节点数还接近7

4、50万个。需要特别注意的是博弈树不同于一般的搜索树，它是由对弈双方共同产生的一种“变性”搜索树。香农(ClaudeShannon)教授早在1950年就提出了“极大-极小算法”（MinimaxAlgorithm），奠定了计算机博弈的理论基础。博弈树的复杂度极大极小思想(Minimax)极小极大思想是指：始终站在博弈一方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这一方（即有利于另一方）的给予一个较低的价值分数，双方优劣不明显的局面给予一个中间价值分数。在博弈一方行棋的时候，选择价值极大的儿子节点走

5、步，其对手方行棋则选择价值极小的儿子节点走步。这就是一个极大极小过程。极小极大值是发展博弈理论的“关键基石”，这是因为博弈论中最基本的概念——扩展形式、纯战略、战略形式、随机化、效用函数等都是因极小极大值理论的研究而被引伸出来的，现代博弈理论中的最基本概念“古诺——纳什均衡”也是极小极大值理论的派生物。极大极小思想(Minimax)Minimax算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。由于对弈双方都很理智，都想赢棋，在考虑着法的时候

6、都尽量想让棋局朝着自己的方面转化，所以在同一颗博弈树上，在不同的层面上就要有不同的选择标准。这也就是称之为“变性”搜索树原由。在我方层节点的着法选择是要在其全部子节点中找到评估值最大的一个，即实行“Max搜索”。而在对方层节点的着法选择则是在其全部子节点中要找到评估值最小的一个，即实行“Min搜索”。极大极小的数学意义通过极大极小方法，可以在数学上证明一个游戏先手必胜。如刚才改良过的剪刀石头布游戏。极大极小的数学意义每一个节点的值由他的子节点中的极值决定。而取极大或极小值取决于博弈者。利用递归的方式实现伪代码：Func

7、tionNodeValue(node)//求输入的node节点的值{if(isleaf_node)//如果是叶节点returnleaf_node_value;//则返回叶节点的值else//如果不是叶节点returnMinimax(NodeValue(next_node));//再次调用}井字棋：策略最佳井字棋，英文名叫Tic-Tac-Toe，是一种在3*3格子上进行的连珠游戏，和五子棋比较类似，由于棋盘一般不画边框，格线排成井字故得名。游戏需要的工具仅为纸和笔，然后由分别代表O和X的两个游戏者轮流在格子里留下标记（一

8、般来说先手者为X）那么，为了保证我们的策略最佳，什么地方才是最好的选择？井字棋：策略最佳井字棋是一个先手必胜游戏。游戏开始后，先占上一个角（比如左下角），那么对方总共有五种本质不同的应对策略：占据靠近你的那条边，占据靠近你的那个角，占据远离你的那条边，占据远离你的那个角（即对角），以及占据正中央的位置。但是，在这五种策略中，前面四