五子棋机器博弈系统评估函数的设计.pdf

《五子棋机器博弈系统评估函数的设计.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、JournalofComputerApplicationsISSN1001-90812012-07-01计算机应用，2012，32(7):1969－1972，1990CODENJYIIDUhttp://www．joca．cn文章编号:1001－9081(2012)07－1969－04doi:10．3724/SP．J．1087．2012．01969五子棋机器博弈系统评估函数的设计1，212*张明亮，吴俊，李凡长(1．苏州科技学院电子与信息工程学院，江苏苏州215011;2．苏州大学计算机科学与技术学院，江苏苏州215006)(*通信作者电子邮箱lfzh@su

2、da．edu．cn)摘要:针对五子棋机器博弈需借助棋型评估棋局产生的速度瓶颈，提出了棋型识别粒度与搜索深度相关联的多层架构评估函数设计方法。实验证实粗颗粒度估值在深层搜索时整体效率更高;多层次判读棋型能明显加快评估速度;走法生成函数引入快速评估，提前进行博弈树自然剪枝收效显著;非关键棋型依据棋局浮动分值平衡搜索深度，对五子棋亦见成效;以及估值函数针对性地延伸评估来减少地平线效应的开销更少;从而表明估值函数动态评估更加合理。关键词:博弈树;PVS;MTD(f);评估函数;五子棋中图分类号:TP181文献标志码:ADesignofevaluation-func

3、tionforcomputergobanggamesystem1，212*ZHANGMing-liang，WUJun，LIFan-zhang(1．CollegeofElectronicsandInformationEngineering，SuzhouUniversityofScienceandTechnology，SuzhouJiangsu215011，China;2．SchoolofComputerScienceandTechnology，SoochowUniversity，SuzhouJiangsu215006，China)Abstract:Conce

4、rningthespeedbottleneckofthegobangmachinegamewhenrelyingontheconfigurationofthestonestoevaluatethegamestates，thispaperproposedamulti-layerevaluation-functionmethodcombiningidentificationgranularityofthestones'configurationwiththesearchdepth．Theexperimentalresultshaveproved:theover

5、allefficiencyofcoarse-grainedevaluationwashigherwhenthedeep-layersearcheswereprocessing;multi-layerjudgingfortheconfigurationofthestonescouldobviouslyacceleratetheevaluation;ifthemove-generatingfunctionswereintroducedintotherapidevaluation，itwasmoreefficienttoprunecertainbranchesf

6、romgame-treeinadvance;gobanggametreesearchesalsobenefitediffloatingthevaluesofnon-criticalstone'sconfigurationtobalancethesearchdepth．Therefore，dynamicevaluationofevaluation-functionismorereasonable．Keywords:game-tree;PrincipalVariationSearch(PVS);MTD(f);evaluation-function;gobang

7、［12－14］快速地局部增量评估。全局估值的精确度高，也易于动0引言态加深评估等，使用更广泛。时至今日，国际象棋和中国象棋［15－17］机器博弈被喻为人工智能领域的果蝇，多以下棋为例研的机器博弈水平已超越最好的人类选手。五子棋是普究其规律。计算机弈棋系统可分为四部分:知识表示、走法生及程度仅次于国际象棋的棋类游戏，职业棋手人数同样居世成、评估函数和博弈树搜索。vonNeumann和Borel在20世纪界第二，棋盘15×15大小，分职业(“禁手”)规则和业余(无［1－3］20年代提出的极小极大值定理是搜索算法的数学基础;“禁手”)规则两种。无“禁手”五子棋有

8、专业棋手普遍认可的［1］始于20世纪50年代的alpha-beta