爱恩斯坦棋算法设计与分析

《爱恩斯坦棋算法设计与分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、信息技术信息爱恩斯坦棋算法设计与分析李占宇李淑琴顾磊史玉峰周文敏摘荽爱恩斯坦棋作为一个在中国刚刚兴起不久的计算机博弈比赛项目，其算法的研究还相对较少。本文就如何在棋局中能够摆脱随机性的影响，让程序做出正确的选择做了分析实现了，基于枚举的贪心算法和进攻策略，。，并给出局面评估的方法实践表明该算法是有效的关键词算法博弈策略权值计算机博弈是人工智能领域一个极其重要且爱恩斯坦棋简介最具挑战性的研宄方向之一工智能中涉及的各，人爱恩斯坦棋由发明于年，法都二个相当新的棋类游戏’目前是国际计算机奥林匹，克大赛竞赛项目’并于年首次作为我国大学生⑶十算机博弈大赛的竞赛项目：。爱恩斯坦棋规则为棋盘为

2、的方格形棋盘’方格为棋位’工！果，世。在过去的半个世纪里界各地的学者花费了大！左上角为红方出发区，量；右下角为蓝方出发区如图的心血对计算机博弈中的、国际象棋、中—所不；国象棋、、五子棋围棋等棋类进行研宄，涌现出大量、八…私红蓝方各有枚方块形棋子，分别标有数“廿”，令人震惊的成果’如年深蓝战胜卡斯帕罗…—字。开局时双方棋子在出发区的棋位可以随意夫的比赛就在全世界范围内引发了震动，其他很多棋挪抽摆放⑶航轮流賺子，然后走动与肝显示数棋国象等的字相对应的棋子。如果相对应的棋子已从棋盘上移法研究较多爱恩甘斯坦棋作为一，个刚刚兴起不久的出，便可走动大于或小于此数字的并与此数字最接—、、…棋

3、类游戏其计，算机博弈算法的研宄还相对较少。，■■棋及比平⑷红方棋子走动方向为向右、向下、向右下，台正肝龍腿册籠贿算奴’真敏走格；鼓辭走动純触左、向上、研宄还不多。本文正是对爱恩斯坦棋计算机博弈技术一―“向左上一，每次走动格；的讲探索如果在棋子走动的目标棋位上有棋子，则要将该棋子从棋盘上移出（吃掉）。有时吃掉本方棋子北京信息科技大学计算机学院一种策略项目基金，因为可以增加其它棋子走动的机会与：市教委教育也是”教学本科生科研训练项目、北京信息科技大学灵活性；年大学生科技创新计划项目经费资助（率先到达对方出发区角点或将对方棋子全信息技术丨暹息化一一部吃掉的方获胜；对角线是指个的矩阵中

4、从左下角到右上，没有和棋。对弈结果只有胜负；角的连线，超时判负每盘每方用时分钟；每轮双基于枚举的贪心算法一，轮流先手（甲方四五盘先手，乙下面对周围的棋子数目（方对阵最多盘，，这四种情况方二三六七盘先手），两盘中间不休息，先胜盘为进行具体分析。胜方。若周围棋子数目为，直接向斜上方走此种情况最简单。若周围棋子数目为卿分舰下种情况：蓝—““一图爱恩斯坦棋比赛平台由于爱恩斯坦棋走每步棋之前都需要擁子以■■■确定走动的棋子的编号，随机性对棋局的影响很大。廿蓝本文力睡造个算法以减少由于醒子的数不同从而给棋局带来的不利影响，增加其有利的影响，使棋局向着尽可能使我方获胜的方向发展。一“””爱恩

5、斯坦棋之贪心策略…，“本文主要采用枚举和贪心策略。枚举是对我方蓝红蓝蓝方）棋子周围的棋子数目进行枚举，然后对枚举的各种情况运用贪心思想进行分析讨论，然后确定走法以（达到最优策略。图周围棋子数目为】的种情况定义周围棋子数指蓝方某个棋子左边，左上方和正上方的棋子数对于这种情况有不同的处理方式：情况如图所示，如果红方（敌方）只目之和：。例如爱恩斯坦棋棋盘布局如图所示，一枚棋子了选定的棋子为那么它周围的棋子数目为’则吃之’因为这样就获胜了，不防称。剩一即左方和正上方。这种措施为绝杀；红方不止枚棋子且没有过副对角线就不吃，此时吃了红旗子反而会增加红方（地方）、棋子的灵活性，也会增加本方棋

6、子推进的步数不防称为延迟一；红方（敌方）不止枚棋子且己经过副对角线就吃之，因为此时蓝方本方必须保护好自己的本营，所以采取的策略是吃掉，不防称为固守。情况如图所示，，直接走斜线因为这样速度最快，不防将这种措施称为急进。图爱恩斯坦棋某个棋盘布局情况：如图所示，如果红方（敌方）只一枚棋子了一定义副对角线剩，则吃之；如果红方不止枚棋子这■年第期信息技术与信息枚蓝色棋子过了副对角线，主要采取保护这枚蓝色棋种情况；如果周围有两个棋子同色即两个蓝色棋子一子生存下来的措施，因为此时红方大本营不远了，且同色或两个红色棋子同色，则各有三种情况，和在，此时将绕过这枚红色棋起总共种情况为了降低对方棋子

7、的灵活性。子，即只走左方或者上方，不吃对角线的红棋子，不实际实现策略是将这种情况浓缩为以下六种分防将这种措施称为暗渡比较这枚蓝色别为；暗渡策略通过：（其中代表本位置有棋子）棋子左方和上方的位置对这两个位置能构成威胁的红情况红红情况红蓝红；色棋子的数目来实现。哪方威胁棋子数目少就走哪边，情况红蓝蓝；情况蓝红若威胁棋子数目一样，则选择走距离红方（敌方）本情况蓝蓝蓝；情况蓝蓝红；营近的方位一。如果红方不止枚棋子且这枚我方蓝色这六种情况每种情况的具体实现和周围棋子数目棋子没有过副对角线那么为了保护蓝