0 0,() 亚马逊棋机器博弈系统中评估函数的研究 郭琴琴, 李淑琴, 包华 GUO Qinqin, LI Shuqin, BAO Hua 北京信息科技大学研究生部计算机学院北京 0 Department of Graduate, Beijing Information Science & Technology University, Beijing 0, China GUO Qinqin, LI Shuqin, BAO Hua. Research on evaluation function computer game of Amazon. Computer Engineering and Applications, 0, ():0-. Abstract:Computer Game is the research carrier of artificial intelligence field. Amazon, as a quite new game, it is very suitable for the research of Computer Game. This paper, using Amazon s game system as an experimental platform, does research on the evaluation function which is one of the key technologies of Computer Game. Based on territory, position, mobility, the three main features of Amazon s assessment, and according to the Amazon game s different charactoristics in Opening, Middlegame, Endgame, the paper analyses the evaluation factors importance level and weight value in the various stages, then gets an evaluation function in form of stages. The experimental results show the evaluation function is feasible and effective. Key words:computer Game; Amazon game; evaluation function; game stage 摘要 : 机器博弈是人工智能学科研究的载体, 亚马逊棋作为一个相对较新的博弈棋种, 走棋特点介于围棋和象棋之间, 非常适合用来进行机器博弈研究 以亚马逊棋博弈系统为实验平台, 对机器博弈中的关键技术之一 评估函数进行了研究 以 territory position mobility 三个主要评估特征为基础, 根据亚马逊棋在开局 中局以及残局三个不同阶段的棋局特点, 分析了不同阶段中各评估因子的重要程度以及权重取值, 最后得到一个分阶段的评估函数 通过实验结果可知, 提出的棋局评估函数是可行并且有效的 关键词 : 计算机博弈 ; 亚马逊棋 ; 评估函数 ; 比赛阶段文献标识码 :A 中图分类号 :TP doi:./j.issn.0-.-0 引言博弈游戏是一种人类复杂逻辑思维活动的反映 机器博弈研究的主要内容是让计算机拥有人的思维去进行博弈游戏, 它的研究既简单方便 经济适 [] 用, 又包含丰富的内涵, 变化无穷的逻辑思维 所以就像果蝇被遗传学视为最理想的遗传学研究载体一样, 机器博弈也被称为人工智能学科研究的载体 一个完整的机器博弈系统主要包括棋局表示, 着法生成器, 搜索引擎以及评估函数 棋局表示是指对比赛过程中形成的棋局的描述, 主要内容包括棋子 空格 箭 走棋 ; 着法生成器的作用是在已形成 的棋局下生成可行的着法, 这一部分的内容包括对下棋规则的描述并根据规则生成所有可行着法, 着法生成器是搜索对象的产生器 搜索引擎的目标是在可行着法中搜索最优着法, 这是机器博弈的核心部分, 是模拟人类思维的最佳体现 评估函数是用来对棋局进行评估的, 是搜索算法的前提, 评估函数的好坏直接影响搜索结果的准确性 为了提高亚马逊棋机器博弈系统的性能, 本文从改进评估函数入手, 通过对亚马逊棋中 territory position mobility 三个主要评估特征的计算分析, 改进了 mobility 评估特征的计算方法, 并且根据阶段特 基金项目 : 北京信息科技大学 0 年研究生优质课程建设项目 ; 北京市属市管高等学校人才强教计划资助项目 (No.PHR00) 作者简介 : 郭琴琴 ( ), 女, 硕士研究生, 主要研究领域为人工智能, 机器博弈 ; 李淑琴 ( ), 女, 博士, 教授 ; 包华 ( ), 男, 硕士研究生 E-mail:guoqinqin@.com 收稿日期 :0-0- 修回日期 :0--0 文章编号 :0-(0)-000-0
郭琴琴, 李淑琴, 包华 : 亚马逊棋机器博弈系统中评估函数的研究 0,() 点分阶段地设计三个评估特征的权重, 得到一个改 进的分阶段的亚马逊棋评估函数, 最后通过实验结 果验证了本文改进的评估函数有效地提高了博弈系 统的性能 亚马逊棋简介以及研究现状. 亚马逊棋简介 亚马逊棋是由阿根廷沃尔特 Zamkauskas 于 年发明的双人抽象策略游戏, 是圈地游戏家族中的 一员, 和国际象棋是远亲 亚马逊棋的棋盘由 n n ( 比赛时 ) 的格子组成, 对弈双方各有 个皇后, 棋盘初始摆放位置如图 所示, 横坐标由 个大写 英文字母 A~J 表示, 竖坐标由阿拉伯数字 ~ 表 示 当轮到一方走棋时, 该方只能且必须移动属于 它的四个皇后中的一个, 每一个着法分两步完成, 第 一步是移动皇后, 与国际象棋中皇后的走法相同, 可 以在八个方向上任意行走, 但不能穿过阻碍 ( 包括皇 后和箭 ); 第二步是放箭设障碍, 在第一步移动完成 后, 在移动棋子的当前位置释放一个箭, 箭的释放方 法与棋子的移动方法相同, 参见图, 白方棋子的着 法 :(,D) (,D) (,B), 从 (,D) (,D), 是完 图 亚马逊棋的初始棋盘 图 亚马逊棋的走棋规则 成第一步移动皇后 ; 第二步 (,D) (,B) 是放箭设 障碍, 箭用黑色方格表示 在比赛的整个过程中, 双 方棋子按照下棋规则可以移动, 但是箭一旦被设置 在某处就不能再移动 当某方四个皇后均不能再移 动时, 则表示该方已经输掉了比赛. 亚马逊棋棋局评估研究现状 在机器博弈系统中, 搜索算法直接影响博弈系 统的性能 评估函数又是搜索算法的基础, 要进一 步提高搜索结果的准确性, 除了提高搜索算法的搜 索能力之外, 更要完善评估函数 本文的主要工作 就是对亚马逊棋评估函数的改进 通过亚马逊棋的下棋规则可以看到, 在亚马逊 棋博弈中, 博弈一方的最终目的是用本方的棋子以 及箭将对方的棋子堵死, 使其不能移动, 由此产生了 两种走棋策略 思路一是堵策略, 即将对方棋子堵 死在有限的区域里面, 让对方无棋可下, 这种策略进 攻性强 ; 思路二是占领土策略, 我方棋子自行为自己 圈定一个较大的领地, 在这个领地里, 对方棋子无法 入侵, 而我方棋子却有很大的自由活动范围, 当对方 棋子在域外未能占领足够大的领地时, 也会因无棋 可下而输掉比赛, 这种策略注重防守 这两种走棋策略思想体现在评估函数中, 可以 用两个评估特征表示, 一个是占领地的特征 territory, 另外一个是灵活度特征 mobility 关于这两个特征 在 Jens.Lieberum [] [] 以及乔治 黄鸿的文章中有很详 [] 尽的介绍 Jens.Lieberum 在他的文章中还考虑了 皇后及箭的位置 position 对局面的影响, 并提出一个 可以描述比赛进度的计算公式 w, 最后给出基于比赛 进度 w 的评估函数, 评估因子的权重系数是由一系列 与 w 相关的权重函数组成 按照 Jens.Lieberum 的方 法, 必须设计 个恰当的函数来作为相应评估因子的 权重系数 现实中要优化这 个权重函数是很困难 的, 而且描述比赛阶段的 w 并不是一个万能的公式, 它只适用于某些博弈系统下的棋局特点, 不能通用 在所有的博弈系统中 亚马逊棋机器博弈系统评估函数的设计 在分析亚马逊棋博弈整个过程后, 作者认为可 以将亚马逊棋比赛过程划分成三个阶段, 开局 中局 以及残局, 划分根据及划分方法请详见参考文献 [] 然后根据在不同的阶段, 领地 territory 位置 position 灵活性 mobility 这三个特征对棋局的评估所起的作 用即重要程度不同, 设计出一个分阶段的评估函数 : value = a t + b t + c p + d p + e m ()
0,() 其中 t t 为 territory 特征值, 分别代表双方基于 Queen 以及 King 走法的对空格的控制权的评估值 ;p p 为位置 position 特征值, 分别表示双方基于 Queen 以 及 King 走法相对空格的位置优劣的评估值 ;m 是双 方棋子的灵活性评估值 ;a b c d e 为相应的权重 值 下面叙述这些值的计算方法. territory 特征值的计算 参照文献 [], 对 territory 特征值的计算涉及两种 走棋方式, 一个是 Queen 走法, 另外一个是 King 走 法 Queen 走法是指移动的八个方向上只要没有跨 越障碍 ( 障碍包括棋子和箭 ) 就可以移动 ; 而 King 走 法是指一次移动距离是, 也就是只能走步到相邻的 空格 QueenMove 值代表对于一个空格 ( 即没有棋 子和箭 ), 某方的四个棋子通过 Queen 的走法走到此 空格最少需要移动多少步 ;KingMove 值表示对于某 一个空格, 某方的四个棋子通过 King 的走法走到此 空格最少需要移动多少步 如图 图 所示, 图 左 上方 (,A) 空格内左上角的数值 表示白方通过 Queen 走法最少需要 步可以到达此处, 右下角的数 值 表示黑方需要 步, 同样在图 中该空格中的数 值 和 表示 King 走法时的情况 图 KingMove 计算 图 QueenMove 计算 如上所述, 通过计算每一空格的 QueenMove 和 KingMove 值, 大体可以看出棋局的优劣 当白方棋 子比黑方棋子用更少的步数到达某一空格时, 认为 白方控制了这个空格, 这样通过对全局每一个空格 的计算, 可以算出每方控制的空格数目, 从而大体确 定局势的优劣 下面给出计算公式 : t i = åδ(d i (A) D (A)) i (i= 或 ) () a ì0 (D ï (A) = i D i (A) = ) Δ(D i (A) D (A))= ïk (D i í (A) = i D i (A) < ) ï (D (A) < i D(A)) i ï î- (D (A) > i D(A)) i A 代表当前棋局中未被占领的空格,i 取 表示基 于 Queen 走法, 取 表示基于 King 走法,D i (A) D i (A) 的值分别表示白方 黑方到空格 A 的 QueenMove 及 KingMove 值 在第二种情形下,D i (A) = D i (A) < 时, 对该空格 A 的控制权由先走棋那一方决定,k 代表的 是先行方的优势大小, 取值范围大于 - 小于, 当先 行方是白方时,k 取大于 0, 否则小于 0 计算结果 t i 表示分别采用 QueenMove 或 KingMove 时, 白方和黑 方对所有空格占有情况的综合评估得分. position 特征值的计算 从 t i 计算公式可以得知基于 territory 的评估仅仅 反映了双方对空格的控制权归属, 但未能反映对空 格的控制权差值大小以及控制权差值大小所反映的 位置特征 实际上双方对一空格控制权的差值能反 映出一方是否具有地理位置的优势 距离空格较近 一方控制权大, 而距离空格较远的一方控制权小, 处 于地理位置上的劣势 同样地, 这种地理位置优劣 评估即对于 position 特征值的计算也涉及 Queen 和 King 两种走步方式, 可以利用 territory 特征评估中使 用的 QueenMove 和 KingMove 参照文献 [],position 特征值 P i 计算公式为 : p = å( -D (A) - -D (A) ) () A p = åmin( max(- (D (A) - D (A))/)) () A 在公式 () 中,P 值以 Queen 走步方式体现双方 棋子在控制空格 A 上的位置优劣 当 D (A) - D (A) 的值越大时, 相应的 -D (A) - -D (A) 值也相应大 P 值 以 king 走步方式体现双方棋子在控制空格 A 上的位 置优劣 从公式 () 可知只有 D (A) - D (A) 绝对值 大于等于 时, 对该空格的控制权的位置优势值才能 取得
郭琴琴, 李淑琴, 包华 : 亚马逊棋机器博弈系统中评估函数的研究 0,(). mobility 灵活度特征值的计算 在文献 [] 中灵活度是用来衡量棋子向相邻八个 方向移动的灵活性大小的 棋盘中的每个空格和棋 子都有一个灵活度值, 棋子灵活度的计算依赖于棋 子可达空格的灵活度 图 中空格内的值代表该空 格的灵活度值, 而棋子皇后左上角的数字则表示该 棋子在此棋局下的灵活度数值 空格的灵活度值为 与该空格相邻的空格数 例如 : 图 中左上角 (,A) 空格因为有 个相邻空格, 所以该空格的灵活度值为 棋子的灵活度值则与棋子采用 Queen 走法一步之内 能到达的空格的灵活度值有关 下面是某个棋子 a 灵活度值的计算方法 : 步骤 计算棋盘中所有空格的灵活度值 步骤 记录棋子 a 采用 Queen 走法时一步之内 能到达的空格 步骤 对步骤 记录的每个空格, 计算空格的灵 活度值除以棋子 a 采用 King 走法到达该空格的步数 的值, 然后将这些值累加, 即得到当前棋子 a 的灵活度 例如对于图 中位于左上角 (,D) 位置的白色棋 子, 它的灵活度计算公式为 :F(a)=/+/+/+/+ /+/+/+/+/+/ 按照以上算法, 可以计算出双方所有棋子的灵 活度, 再根据公式 (), 就可以对整个棋局上双方棋 子灵活度态势做出评估 m = åf(w) - åf(b) () w b 其中 w b 分别表示黑白双方的棋子,F(w) F(b) 分别 表示白方及黑方棋子的灵活度 如果 m>0 时, 表示 该棋局中白方棋子灵活度大 ; 当 m<0 时, 表示黑方棋 子灵活度大 0 0 图 灵活度计算 这种通过计算棋子周围可达空格的灵活度, 将 这些空格灵活度的累加值作为棋子灵活度的计算方 法首先要对棋盘中每个空格计算灵活度, 每个空格 灵活度的求取也要通过棋盘的扫描, 这个过程消耗的时间太多, 在限制时间的比赛条件下, 机器博弈系统会因为在评估函数消耗时间过大而导致最后搜索结果的不理想, 一个好的评估函数不仅要保证评估结果的准确性还要考虑评估的时间消耗 灵活度评估是为了保证棋子有着法可走而不被过早堵死, 基于这个思想, 文本提出一个更简单更省时的计算方法, 即统计当前棋局双方棋子可行着法数目, 将一方的可行着法数目作为该方的灵活度 不管是文献 [] 中描述的灵活度评估方法还是本文新提出的计算方法, 都存在这样一个问题 : 开局阶段, 经灵活度评估, 一方的灵活度值比对方的灵活度要高很多, 但是却出现了该方某个棋子过早被堵死的情形 为解决这个问题, 本文在计算灵活度值的同时还计算了一个最小灵活度值并将该值加到灵活度评估特征里面, 这个最小灵活度值是指一方四个棋子中的可行着法数目最小的那个值 加了这个值的灵活度评估可以防止一方某个棋子过早堵死的情形. 系数在比赛阶段中的重要性分析以上 t t p p m 这五个评估因子都是针对棋局某一方面特征的评估, 而亚马逊棋棋局特点在不同比赛阶段差异很大, 所以五个评估因子的权重的取值不能固定不变而应该是随着比赛阶段而改变 t 在整个比赛过程中的作用是越来越大, 特别是进入中局 残局阶段 在比赛初期, 走步比较少, 设置的箭也相对应较少, 双方棋子对棋盘上空格的控制权还是比较均等的, 所以 t 评估作用相对比较小, 但随着比赛逐渐进入中局 残局阶段, 每一个空格的控制权在哪一方越来越明显, 而且进入残局阶段后, 整个棋盘被划分成彼此独立的小区域, 每个空格都只被一方棋子控制, 这时候 t 的评估作用最大 所以 t 评估因子的权重在开局最小, 中局变大, 残局取最大 t 在整个比赛过程中的作用越来越小, 而进入残局阶段后, 作用几乎为零 虽然 t 和 t 都是对空格控制权的评估, 但是因为评估时基于的走步方式不一样, 他们在各阶段的重要性也不一样 t 基于 King 走法的评估, 这个评估值的作用是保证我方棋子在附近的区域圈地并防止对方棋子进攻我方棋子附近的领地, 在开局阶段时这点非常重要, 所以在 t 的评估值在开局阶段比 t 更重要, 而进入残局阶段, 任何一块空格领域只被一方棋子占领, 领地也被圈分完, 也不存在阻止对方棋子进攻的问题 所以 t 评估因子的权重取值应是开局阶段最大, 中局次之,
0,() 残局时权重可以取很小或者忽略 c 和 c 的作用也体现在开局阶段,c 和 c 是基于双方棋子相对目标空格位置的评估, 涉及到棋子的分布状况, 棋子的分布状况只有在开局阶段比较重要, 这个时候比赛双方棋子要尽量在整个棋盘上均匀分布, 实验发现当他们的权重大的时候, 整个棋盘上的棋子分布比较均匀 在残局, 棋局分布已成定局, 不用考虑棋子位置的分布情况, 所以残局不用考虑这个评估因子 m 在比赛整个过程中的重要性也越来越小 通过灵活度因子的分析知,mobility 评估因子在比赛初期作用最大 一般情况下, 一个棋子在比赛过程中越早被堵死, 对该方越不利 在到了中后局, 已过了布局阶段, 棋子的分布已成明朗, 棋子的灵活度对于棋局的影响越来越小了 所以 m 评估因子的权重在开局最大, 中局次之, 残局不考虑灵活度了 评估函数的算法实现本文亚马逊棋的评估函数的计算算法为 : 假设我方为白方, 输入当前棋局 ( 用一个 的二维数组表示 ) 具体算法如下: 步骤 对棋盘上的每个空格计算 QueenMove KingMove 值 步骤 对棋盘上的每个棋子计算 mobility 值 步骤 按照计算公式 ()()()() 分别求出 t t p p m 值 步骤 根据公式 () 计算 value 值 当 value>0 时, 表示该棋局对我方有利 ; 当 value<0 时, 表示对黑方有利, 值越大代表优势越大 具体实现, 设置前 0 步为开局阶段,~ 为中局阶段 0 步以后为终局阶段 通过实验得到各阶段评估因子的权重取值如表 所示 表 评估特征评估因子权重系数开局阶段中局残局 评估因子权重系数取值 Territory Position t t p p a 0. 0.0 0.0 b 0. 0. 0. c 0. 0.0 0.0 d 0. 0.0 0.0 Mobility m e 0.0 0.0 0.00 将该评估函数应用到一个性能稳定的亚马逊棋博弈系统中, 取名为 分阶段评估函数, 分别将它与未考虑阶段特点的系统, 这里称为 原始固定权重评估, 以及文献 [] 中使用的 w 阶段描述, 这里称为 含 w 描述评估函数 的系统进行对弈, 每对程序分先手 和后手, 每次对弈 0 局, 考虑到对弈时间因素, 根据每步走棋时间 T 取值得到以下对弈结果 ( 表 ~ 表 ) 实验结果表明, 分阶段评估函数的博弈系统要优于原始权重评估及含 w 描述评估函数的系统, 评估时间越短, 使用分阶段的评估函数, 系统性能相对后两者优势更大 实验还统计了使用三种不同评估函数的系统在搜索时间 T 内评估的平均节点数目以及搜索深度, 发现使用本文提出的评估函数的系统评估的节点数目最大并且博弈树搜索深度更大, 这是导致 分阶段评估函数 性能优于其他两个系统的根本原因 表 实验结果 (T=0 s) 先手 VS 后手原始固定权重评估 VS 分阶段评估函数分阶段评估函数 VS 原始固定权重评估含 w 描述评估函数 VS 分阶段的评估函数分阶段的评估函数 VS 含 w 描述评估函数 表 实验结果 (T=0 s) 先手 VS 后手 原始固定权重评估 VS 分阶段评估函数 分阶段评估函数 VS 原始固定权重评估 含 w 描述评估函数 VS 分阶段的评估函数 分阶段的评估函数 VS 含 w 描述评估函数 表 实验结果 (T= s) 先手 VS 后手 原始固定权重评估 VS 分阶段评估函数 分阶段评估函数 VS 原始固定权重评估 含 w 描述评估函数 VS 分阶段的评估函数 分阶段的评估函数 VS 含 w 描述评估函数 结论本文以 territory,position,mobility 为主要特征, 结合亚马逊棋的阶段特点, 设计并实现了一个分阶段的评估函数, 虽然通过实验验证了本文提出的评估函数是可行的, 并且一定程度上能提高亚马逊棋的博弈系统的性能, 但是许多参数来自实验值, 还需进一步优化 下一步拟采用机器学习方法, 进行评估因子权重取值问题的研究, 另外除了考虑上面三个主要特征外, 评估函数还将考虑加入新的评估特征 参考文献 : [] 徐心和, 徐长明. 计算机博弈原理与方法学概述 [C]// 中国人工智能进展,00:-. [] Lieberum J.An evaluation function for the game of amazons[j].theoretical Computer Science,00,(): 0-. ( 下转 页 )