宋英健，侯荣旭，孙嘉荣，史广阔

（沈阳工程学院 信息学院，辽宁 沈阳 110136）

计算机博弈是研究人工智能领域的一个重要分支，同时也是各个科研领域方面重点研究的对象，其目的是构建一个具有AI智能的算法，使之可以像人类选手一样进行对战、博弈［1］。计算机博弈程序一般由评估函数与优化搜索算法两部分组成，同时配有棋局评估、法生成、开局库与残局库开发、博弈树搜索、系统测试及参数优化等核心技术要点［2］。

1 爱恩斯坦棋介绍

爱恩斯坦棋是2004 年由德国人英戈·阿尔托夫发明的一种双人非完备信息类博弈游戏。棋盘为5×5 的方格形棋盘，每一个方格代表一个棋位，棋盘的左上角为红方棋子位置，棋盘的右下角为蓝方棋子位置；双方共持有6 枚棋子，棋子序号为1～6，顺序在双方出发区棋位可以无序任意放置；对局开始由红方先抛出骰子，移动棋子的标号与骰子点数相对应，如果棋盘中不存在与骰子点数相对应的棋子，则可以顺着点数向上或者向下查找，选择与之最相近的点数，移动该枚棋子；双方移动规则为红方只能移动目标棋子朝右方、下方、斜下方移动，蓝方只能移动目标棋子朝左方、上方、斜上方移动；在棋子移动的目标棋位上如有棋子(不论敌我)，则移动本方棋子来覆盖该枚棋子，被覆盖的棋子从棋盘中移除。胜利的条件有两种，分别为移动到对方对角点和全歼对方棋子，爱恩斯坦棋无平局出现。

2 算法设计

对于构建一个计算机博弈算法，估值函数与搜索算法是不可或缺的。……