探索中国象棋机器博弈数据结构设计与搜索算法研究

《探索中国象棋机器博弈数据结构设计与搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西安理工大学硕士学位论文中国象棋机器博弈数据结构设计与搜索算法研究姓名：谢国申请学位级别：硕士专业：控制理论与控制工程指导教师：钱富才20080301摘要论文题目：中国象棋机器博弈数据结构设计与搜索算法研究学科专业：控制理论与控制工程研究生：谢国指导导师：钱富才教授要签名：人工智能(舢)是计算机知识、心理学和哲学等知识的综合体现。中国象棋的计算机博弈属于人工智能的研究范畴。目前黑白棋、五子棋、国际象棋等棋类的计算机博弈已经取得了成功，而博弈树更为庞大的中国象棋计算机博弈尚处于萌芽阶段。本课题结合在中国象棋机器博弈方面的实践经验

2、，对中国象棋计算机博弈做了详细的分析和研究，主要做了以下工作：首先，设计了中国象棋计算机博弈软件的数据结构，对马和象的着法生成采用模版匹配法，并且根据路向行向比特向量对车、炮等棋子的着法生成采用预置表法。由于采用模版匹配法和预置表法省去了棋子边界的判断，并且利用查询代替搜索，提高了着法生成的速度，进而提高了整个博弈树的搜索效率，该部分的工作是整个程序的基础。另外，研究了博弈树的搜索算法。在alpha．beta搜索算法的基础上，采用极小窗口(PVS)、置换表启发、历史表启发、静态启发等启发算法，有效的提高了搜索的效率；采用静态搜

3、索、选择性延伸等手段，避免了在叶子节点由于棋子交换、将军等因素导致的估值剧烈波动而带来的评估风险；采用空着前向裁剪(NULLMOVE)使得搜索深度在原来基础上增加了2～3层，并且完善了空着前向裁剪的条件判断，使得采用该方法更稳定。最后，简要描述了棋局的评估要点。对各种算法编程实现，实践结果表明了算法可行性，并表现出了良好的性能。关键词：中国象棋；人机博弈；博弈树搜索；评估函数ABSTRACr——————————————————————————————————————————一一_Title：DATASTRUCTUREDESIG

4、NANDGAME．TREESEARCHALGORITHMRESEARCHFORCHINESECHESSCOMPUTERGAMEMajor．-ControlTheoryandControlEngineeringName：GUOXIESupervisor：Prof．FucaiQIANAbstractSignature：氏j易舀”ArtificialIntelligence㈣isthesynthesisofcomputerknowledge，psychologyandphilosophy．Chinesechesscomputerga

5、mebelongstothefieldofartificialintelligenceresearch．Now,peoplehaveobtainedSuccessinOthello，Gobang，chesswithcomputergame，however-Chinesechesscomputergamewhichhashugersearching．tree，isstillattheinitialStage．BasedonpracticalexperienceinChinesechesscomputergame，thefollo

6、wingworkhasmainlvbeendoneinthisPaper：Firstly,thesoftwaredatastructureofChinesechesscomputergameisdesigned．ThetemplatematchingmethodisusedforKnightandElephantmove．generation，andprefab“catedtablewhichbasedonBitrankandBitfileisusedforthemove．generationofRook，Cannon．Paw

7、nandSOon·Andbecausethemethodsoftemplatematchingandprefabricatedtableareneedlessontheborderjudgementandthegame—treesearchisreplacedbytable．querybytheseways，thespeedofmove。generationisincreased，andthentherateofgame．treesearchisenhancedSecondly,theresearchaboutgame—tre

8、esearchinghasbeendone．PVS(MinimalWindowSearch)，whichisderivedfromalpha—betasearch，isusedtoincreaSestherateofp11Ining；Inordertoadjustsearch