资源描述：
《机器博弈搜索技术分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、学术研讨机器博弈搜索技术分析王赠凯,吕维先(中国地质大学信息工程学院,湖北武汉430074)摘要:计算机博弈是人工智能领域最具挑战性的研究方向之一,机器博弈的核心思想实际上就是博弈树节点的估值过程和对博弈树搜索过程的结合。分析了现今主流的几种机器博弈搜索算法及其优缺点。关键字:机器博弈;博弈树;博弈搜索算法;alpha-beta搜索中图分类号:TP311文献标识码:A文章编号:1672-7800(2007)02-0026-02博弈研究的热点。可以判断节点C的值应小于等于16(取1博弈树极小值);而节点A的值为节点
2、Max(B,2基本搜索算法甲乙双方进行对弈,假定轮到甲走棋,C),为18,也就是说不再需要估算节点C甲可以有若干种走法;对于甲的任一种走2.1极大极小值算法的其他子节点如E、F的值就可以得出父法,乙也可以有与之相对的若干种走法;命名两个博弈者为MAX和MIN。目标节点A的值了。这样将节点D的后继兄对乙的任一走法甲又有若干种与之对应是为MAX寻找最佳走步。假设MAX先移弟节点减去的方法称为alpha剪枝。的走法,如此往复。显然,可以构造一棵博动,然后两个博弈者轮流移动。深度为偶图2右半部所示极大极小树的片断,弈树(
3、图1),将所有的走法罗列出来。博弈数的节点对应于MAX下一步移动的位节点B的估值为8,节点D的估值为18,树的根节点是当前时刻的棋局,它的儿子置,称为MAX(取值大于0)节点;深度为由此可以判断节点C的值应大于等于18节点是假设再行棋一步以后的各种棋局,奇数的节点对应于MIN下一步移动的位(取极大值);而节点A的值为节点Min孙子节点是从儿子节点的棋局再行棋一置,称为MIN(取值小于0)节点。如果MAX(B,C),为8。也就是说不再需要求节点C步的各种棋局,以此类推,直到可以分出在端节点之间进行选择,就会选择具有
4、最的其他子节点如E、F的值就可以得出父胜负的棋局。整棵博弈树体系非常庞大,大估值的节点。所以MIN端节点的父节节点A的值了。这样将节点D的后继兄且不同的棋类有所不同,分支因子大的如点(MAX节点)所赋的倒推值等于端节点弟节点减去的方法称为beta剪枝。围棋的博弈树显然要比分支因子小的如估值中的最大值。另一方面,若MIN在端节国际象棋的博弈树要大得多。点之间进行选择,那么会选择具有最小估值的节点。所以,MAX端节点的父辈节点(MIN节点)所赋的倒推值等于端节点估值中的最小值。在所有端节点的各个父辈节点都已赋好倒推值
5、之后,再向上倒推另一级的值,仍然假设MAX总是选择具有最大倒推值的节点,而MIN总是选择具有图2剪枝最小倒推值的节点。与极大极小值算法相比,alpha-beta图1博弈树示例2.2alpha-beta剪枝算法剪枝算法通常用较少的搜索就能找到最在极大极小搜索过程中,遍历了整棵博弈程序的任务就是对博弈树进行佳节点,但它对于节点的排列非常敏感。博弈树,每个节点都访问了一次,这样做搜索以找出当前的最佳走步。在这个过程对于同一层上的节点,如果节点的排列顺的缺点是效率低下。与之相比,alpha-beta中,最为重要的是搜索算
6、法,高效的搜索序是从最差到最好,可以使实际搜索的博剪枝算法就高效得多。算法可以保证用尽量少的时间和空间损弈树达到最小树;否则,就可能要搜索整图2左半部所示极大极小树的片断,耗来达到寻找高价值的走步,这正是机器棵的博弈树。节点B的值为18,节点D的值为16,由此作者简介:王赠凯(1980-),男,中国地质大学信息工程学院硕士研究生,研究方向为人工智能;吕维先(1947-),中国地质大学信息工程学院教授,研究方向为软件工程和人工智能。26软件导刊·2007·2月号学术研讨intalphabetaTT(intdepth
7、,intalpha,intalphabeta(inti,intalpha,intbeta);3优化的搜索算法beta)//分析第i层3.1渴望搜索{SaveBestAction();//保存最佳节点在alpha-beta剪枝过程中,初始的搜value=LookupTT(depth,index);i++;索窗口往往是从-∞(初始的alpha值)到+∞//查询置换表}(初始的beta值),在搜索进行中再不断缩if(valueisvalid)DoBestAction();小窗口,加大剪枝效果。returnvalue;/
8、/采用最佳行动渴望搜索就是渴望从一开始就使用Searchwithalphabeta...}小的窗口,从而在搜索初起,就可以进行StoreToTT();//记录到置换表中尤其在关键的开局和残局阶段,由于大量的剪枝。初始窗口的选定很重要,如果returnvalue;分支较少,迭代深化算法可以进行较深层所要寻找的走步就在这个窗口内,搜索便}次的搜索。可以继续进行。如果第一步搜索
