（计算机应用技术专业论文）基于状态演算的通用游戏系统的研究与设计.pdfVIP

独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已注明引用的内容以外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果，也不包含为获得江苏大学或其他教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均己 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：衫扬奶 伽1 1 年占月2 ；日 学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、 缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致， 允许论文被查阅和借阅，同时授权中国科学技术信息研究所将本论文编入中国 学位论文全文数据库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂 志社将本论文编入中国优秀博硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密。 学位论文作者签名：匆扔岛 沙1 1 年舌月；日 指导教师签名：甸一啦 厶f f 年月23 日 江苏大学硕士学位论文 摘要 通用游戏是人工智能最具挑战性研究领域之一。近年来得到快速的发展，在 军事行动、电子商务、商业流程管理等方面有巨大实用价值。通用游戏的目的在 于设计一个只接收游戏的游戏规则即可以高效的进行游戏的系统。这需要多种人 工智能技术，例如知识表示，自动推理，搜索和机器学习等。 状态演算是对流演算的改进，为行动推理中框架问题提出了一种自然有效的 解决方案，具有更广泛的适用范围。本文基于状态演算，围绕行动推理和通用游 戏进行研究，主要工作如下： ( 1 ) 提出了一种基于状态演算的通用游戏的自动推理方法。引入状态演算对 通用游戏进行自动推理，获得当前状态下的可执行动作集合，根据动作的效应进 行状态更新获得下一状态。 ( 2 ) 设计并实现了基于状态演算的通用游戏原型系统s t e x p i a y e r 。通用游 戏原型系统s t e x p i a y e r 以状态演算进行自动推理，用最小最大算法搜索最优动 作。原型系统在功能层次上分为通信模块、信息整理模块、自动推理模块和决策 支持模块。 ( 3 ) 对s t e x p i a y e r 进行通用游戏测试，选择包括单人开关游戏、双人井字 棋游戏等各2 种单人双人游戏进行测试，实验结果验证了s t e x p i a y e r 能够高效 的进行各种通用游戏。 关键词：流演算，状态演算，通用游戏，自动推理，s t e x p i a y e r 原型系统 a b s t r a c t g e n e r a lg a m ep l a y i n gi so n eo ft h em o s tc h a l l e n g i n gb r a n c h e s o fa ia n d d e v e l o p e df a s ti nr e c e n ty e a r s i th a sg r e a tu t i l i t y v a l u ei nm i l i t a r ya c t i o n ；e l e c t r o n i c c o m m e r c ea n db u s i n e s sp r o c e s sm a n a g e m e n t g e n e r a lg a m ep l a y i n g i st h ea r to f d e s i g n i n gs y s t e m st h a ta r ec a p a b l eo fp l a y i n gg a m e so f aw i d ev a r i e t yb yb e i n gt o l d n o t h i n gb u tt h er u l e so ft h eg a m e t h i sr e q u i r e sm a n ya it e c h n o l o g i e s ，s u c h a s k n o w l e d g er e p r e s e n t a t i o n ；a u t o m a t i cr e a s o n ；s e a r c ha n d m a c h i n el e a m i n g s t a t ec a l c u l u si st h ei m p r o v e m e n tt of l u e n tc a l c u l u sw h i c hp r o p o s e sa n a t u r a l l y w a vt os 0 1 v et h ef r a m ep r o b l e mo ft h ea c t i o nr e a s o n i n gh a sa w i d e ra p p l i c a t i o n f o r a c t i o nr e a s o n i n g 。an e wr e a s o n i n gm e t h o dw a sp r o p o s e dt og e n e r a lg a m ep l a y i n g ， w h i c hi n t r o d u c e st h es t a t ec a l c u l u st og e n e r a lg a m ep l a y i n g t h em a i nw o r k o ft h e p a p e r i ss t a r t e da sf o l l o w s ： ( 1 ) an e wm e t h o dt or e a s o n i n gi ng e n e r a lg a m ep l a y i n gi s p r o p o s e d s t a t e c a l c u l u si si n t r o d u c e dt og e n e r a lg a m ep l a y i n g a si t sr e a s o n i n gp a r t ，t og e tt h ep o s s l b l e a c t i o ns e t so ft h ec u r r e n ts t a t e ，t ou p d a t ec u r r e n t s t a t ea c c o r d i n gt ot h ee f f e c to f a l r e a d yd o n ea c t i o n ( 2 ) ag e n e r a lg a m ep l a y i n gp r o t o s y s t e ms t e x p l a y e rw h i c hb a s e d o ns t a t e c a l c u l u si sd e s i g n e da n di m p l e m e n t e d s t a t ec a l c u l u si s u s e dt od ot h ea u t o m a t i c r e a s o n i n ga n dt h em i n i m a xa l g r i t h o mi s u s e dt os e a r c ht h eb e s tm o v e s t e x p i a y e r c o n s i s t so ff o u rf u n c t i o n a lm o d u l e s ：c o m m u n i c a t i o np a r t ；i n f o r m a t i o nc l a s s i f yp a r t ； a u t o m a t i cr e a s o n i n gp a r ta n ds t r a t e g i cs u p p o r tp a r t f 3 ) s t e x p l a y e ri se s t i m a t e db yg e n e r a lg a m e sa n ds h o w st h ee f f i c i e n c y t w o d i f f e r e t a to n e p l a y e ra n d t w op l a y e rg a m e sa r ec h o o s ei n c l u d i n go n ep l a y e rc 0 1 n sg a m e ； t w op l a y e rt i c t a c t o eg a m e f i n a l l yt h er e l a t e dw o r ki sc o m p a r e d k e y w o r d s ：f l u e n tc a l c u l u s ，s t a t ec a l c u l u s ，g e n e r a lg a m ep l a y i n g ；a u t o m a t i c r e a s o n i n g ， s t e x p l a y e rs y s t e mm o d e l l i 目录 第一章绪论一1 1 1 人工智能与游戏1 1 2 通用游戏概述一2 1 2 1 通用游戏系统组成2 1 f 2 2 通用游戏描述语言4 1 2 3 通用游戏中的自动推理6 1 2 4 通用游戏中的搜索技术7 1 2 5 基于流演算的通用游戏玩家系统简介9 1 3 论文主要研究内容9 第二章状态演算“ 2 1 状态演算的基本概念1 l 2 1 1 流、流集合和流集合公理1 l 2 1 2 状态和状态公式1 2 2 1 3 动作和情景一13 2 2 状态知识和更新1 3 2 2 1 状态知识1 3 2 2 2 动作的前提条件和状态知识更新一1 4 2 3 状态演算的推理机制1 5 2 4 状态演算解释器s t e x 1 6 2 4 1s t e x 程序的基本框架16 2 4 2 基本s t e x 语言1 6 2 5 本章小结1 8 第三章基于状态演算的通用游戏玩家系统的自动推理分析与原型系统设计1 9 3 1 引入状态演算的可行性研究1 9 3 2 通用游戏系统的自动推理分析1 9 3 3 基于状态演算的通用游戏玩家系统的原型系统设计2 0 3 3 1 通用游戏玩家原型系统的设计思路2 0 3 3 2 通用游戏玩家原型系统的层次设计2 1 i i i 江苏大学硕士学位论文 3 3 3 通用游戏玩家原型系统的功能模块设计j 2 2 3 4 本章小结2 3 第四章基于状态演算的通用游戏玩家原型系统的实现一2 4 4 1 系统开发环境简介2 4 4 2 通信模块的实现2 4 4 3 信息整理模块的实现2 6 4 3 1g d l 解析器2 6 4 3 2g d l 译成器3 0 4 4 自动推理模块的实现3 1 4 4 1 中间语言的接收和处理31 4 4 2 自动推理控制部分的实现3 2 4 5 决策支持模块的实现3 3 4 5 1m i n i m a x 算法3 3 4 5 2 决策支持模块和自动推理模块之间的通信3 6 4 6 系统运行过程分析3 7 4 7 相关工作3 8 4 8 本章小结3 9 第五章运行实例与分析4 0 5 1 游戏样本的选择4 0 5 2 单人游戏运行实例与分析4 0 5 3 双人游戏运行实例与分析4 3 5 4 本章小结4 6 第六章总结与展望4 7 6 1 本文工作总结4 7 6 2 进一步工作4 7 参考文献4 9 致谢5 3 在读期间所发表论文：5 4 i v 江苏大学硕士学位论文 第一章绪论 本章首先介绍了人工智能与游戏，人工智能领域理论与技术在游戏中的应 用；然后介绍了通用游戏理论的定义及其在国内外的研究现状和发展趋势；接着 又介绍了流演算理论及基于流演算的通用游戏玩家系统；最后概述了本论文的主 要工作及论文结构安排。 1 1 人工智能与游戏 人工智能的一些早期应用集中在游戏和通用问题求解策略上。1 9 5 0 年， c l a u d es h a n n o n 提出国际象棋游戏在本质上是一个搜索问题，事实证明了 s h a n n o n 观点的正确性i lj 。早期的人工智能研究员认为如果计算机能够解决复杂 问题，那么就可以依此建立智能机器。此时游戏做为智能算法和智能决策技术的 改进和提高的测试平台。 早在上世纪5 0 年代，英国牛津大学的研究员就开发出了游戏程序，1 9 5 2 年 c h r i s t o p h e rs t r a c h e y 开发了一个还算不错的西洋跳棋游戏程序；d i e t r i c hp r i n z 开 发的国际象棋游戏程序可以搜索千计的棋子的可能走法，但是就这个时期的计算 机而言，这需要大量的时问因而行棋的速度非常慢。1 9 6 2 年，运行在i b m7 0 1 上的国际象棋游戏程序打败了美国前康涅狄格州国际象棋冠军，程序的开发者 a r t h u rs a m v e l 首次利用演化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 的方法得到学习型游 戏程序。 近年来，随着计算机性能的提高和搜索算法的不断改进，以搜索算法为瓶颈 的古典游戏如以上所提到的国际象棋、西洋跳棋等游戏程序已经走向成熟。1 9 9 2 年，b a r n e yp e l l 提出了m e t a g a m e 2 4 1 ，b a r n e yp e l l 认为游戏程序对游戏的分析是 游戏程序设计中最艰巨的任务，而设计者们越俎代庖的避开了这个难题。b a r n e y p e l l 将人工智能在游戏中的应用拓展到了更宽泛的领域。b a r n e yp e l l 设想 m e t a g a m e 程序将游戏规则作为输入，其中游戏规则用预先定义的固定类表示， m e t a g a m e 程序间通过载入一个个的新游戏互相间进行比赛。根据程序的整体表 现给出评价，并根据比赛的经验改进m e t a g a m e 程序。游戏程序要具备对游戏规 江苏大学硕士学位论文 则的分析能力势必用到除了智能搜索算法以外的人工智能技术，如知识表示，自 动推理和机器学习等。 1 2 通用游戏概述 通用游戏【5 j 的目的在于设计一个只接收游戏的游戏规则即可以高效的进行 游戏的系统。由于事先对游戏的特征一无所知，通用游戏系统只能依靠自己的智 能，这种智能是真正的智能，它不依赖于编程者的智能。这使得通用游戏系统的 设计更具挑战性。为推动通用游戏的发展，自2 0 0 5 年起，美国人工智能协会 ( a a a i ) 在其年会期问都会举行国际性的通用游戏比赛1 6 1 ，比赛不仅产生了优 秀的通用游戏玩家系统如f l u x p l a y e r i7 j 及c a d i a p l a y e r l 8 】等，更是通用游戏爱好者 经验与智慧交流的盛会。2 0 0 9 年7 月a a a i 与通用游戏研究会( g e n e r a li n t e l l i g e n c e i ng a m ep l a y i n ga g e n t s ) 合作举办了0 9 年的通用游戏比赛。 1 2 1 通用游戏系统组成 如图1 1 所示，通用游戏系统有两大部分组成，游戏总控( g a m em a s t e r ) 部分和游戏玩家系统部分。游戏总控部分根据游戏规则中所需玩家数量分配玩家 进行游戏，游戏进行时为维持游戏的进行必须根据玩家反馈的动作进行游戏的状 态更新，将动作存入可执行动作序列，并将更新的状态发送至其他玩家，根据游 戏规则的规定实时检查游戏的结果以确定游戏的胜出者。游戏总控部分由三部分 构成：游戏信息数据库( a r c a d e ) ，游戏编辑器( g a m ee d i t o o f f f l 游戏管理器( g a m e m a n a g e r ) 1 6 。其中a r c a d e 是存有游戏、游戏玩家和比赛的信息的数据库，游戏 编辑器协助游戏爱好者创造和分析游戏，游戏管理器负责比赛时游戏的进行。 图1 1 通用游戏系统基本组成结构 2 江苏大学硕士学位论文 游戏总控部分通过建立与游戏玩家地址端口的t c p i p 连接向其发布消息， 游戏玩家响应游戏总控部分的请求，因而在网络模型中，游戏玩家和总控部分分 别扮演服务器和客户端的角色。在通信时必须遵从如下通信协议： 控制部分的消息形式为： h e a d e r c o n t e n t 标准的h t t p 消息头为 p o s t h t t p i 0 a c c e p t ：t e x t d e l i m s e n d e r ：g a m e n a s t e r r e c e i v e r ： c o n t e n t - t y p e ：t e x t a c l c o n t e n t l e n g t h ： 游戏开始信息的形式为： ( s t a r t ) 其中m a t c hi d 为游戏的名字；r o l e 为接收到信息的玩家在游戏中的角 色；g a m ed e s c r i p t i o n 代表描述游戏的公理集合；s t a r l 仰l a y c l o c k 表 示游戏开始前的准备时间和每轮的限制时间。 玩家对游戏开始信息的回复为r e a d y 。当游戏玩家准备好时回复r e a d y ； 如果在开始准备时间结束后玩家没有回复，游戏总控部分强行进行游戏。 游戏进行中的每一轮，总控部分发送消息形式为 ( p l a y ) p r i o rm o v e s 为上一轮中所有玩家的动作集合，顺序与游戏规则中给出的 玩家角色顺序一致，首轮中值为”n i l ，。 p l a y 的回复为m o v e ，即玩家选择的动作。 游戏结束消息s t o p 的形式如下： ( s t o p ) s t o p 消息的回复是”d o n e ”。 一个游戏玩家系统必须具备通讯功能、推理能力和赢得游戏的策略。通讯功 能即和游戏总控部分进行游戏信息交互的能力。根据游戏规则提取出可执行动作 和初始状态，依据当前状态和游戏的结束状态条件进行判断并根据游戏的目标要 求指导游戏搜索算法的搜索。游戏玩家系统的设计者可以利用各种可能的方法使 3 江苏大学硕士学位论文 系统拥有更好的决策支持部分来赢得游戏。决策支持部分与自动推理部分分工明 确又紧密合作。这两个部分的信息交互是通用游戏玩家系统自动推理和高效搜索 的前提。 1 2 2 通用游戏描述语言 一个包涵”个角色的通用游戏的各组成部分如下： p 状态集合； a 17 0 4 n 一对应于胛个游戏玩家的动作集合； 三l ，三n 一其中，l i c - - , 4 i x s ，合法关系语句； u ：s x a i x x a n p 更新函数； s i 小游戏初始状态；t _ c s - 终止状态； g l ，g n 一其中g i c s x l n , 目标关系语句一 美国斯坦福大学的s t a n f o r dl o g i cg r o u p 为通用游戏比赛制订了游戏规则的 规范化描述游戏描述语言( g a m ed e s c r i p t i o nl a n g u a g e ) g d l l l 0 】。g d l 是 d a t a l o g i 1 语言的一种变体因而可以描述游戏的逻辑规则。d a t a l o g 语言由两种基 本原子关系原子和算术原子组成。关系通过元数固定的谓词表示，关系原子 是由谓词及其参数组成，通常称为原子。算数原子为两个算数表达式的比较，其 值为布尔值。d a t a l o g 中规则的形式为：办 = 6 l 八八b 。，其中，头部h 是一个关 系原子； _ 读作弧矿右边为子目标b ，组成的规则体。b j 可以是关系原子，也可 以是算数原子。子目标之间用逻辑运算符a n d 连接，且子目标前面可以有选择的 增加取反逻辑运算符n o t 。 g d l 在d a t a l o g 的基础上建立起来，在相等关系和函数常量的表示上做了微 小的改变，为保证语义的有限性，对递归增加了约束：d a t a l o g 中使用= 和表示 项a 和b 的相等关系，g d l 仅通过关系谓词d i s t i n c t 表示关系，对于具有= 关 系的x 和y ，可以通过构造规则用】，代替规则中x 的所有出现表示；在d a t a l o g 词汇和项的定义上分别增加了函数常量及其元数和刀元函数常量作用于刀个项的 表述；对d a t a l o g 规则增加了递归约束。 定义l( 递归约束) ：为规则的集合，令g 为的依赖图。假设包涵 规则p ( h ，t n ) = b l 八八q ( v l ，v k ) a b m 4 江苏大学硕士学位论文 其中，g 出现在g 中关于p 的坏中。 1 ，q ，或者巧是约束，v i e 1 1 , - - - , ，n ) ，或 者3 ie 1 ，朋) b i = r ( ，b ，) ，其中厂不出现关于p 的坏中。 下面给出增加了递归约束规则的d a t a l o g 规则： 定义2 ( 规则) ：d a t a l o g 规则的形式为h = b i 八a b 。 其中，h 为原子语句，6 i 为原予语句或原子语句的否定语句，规则满足上述 递归约束规则。 g d l 以k i f t 9 】格式进行书写。在k i f 中，变量以? 丌头，操作符以前缀形式写 在语句的前面。例如： x 写作? x ； 坟a ，x ，g ( h ( c ，y ) ，e ) ) 写作( fa9 x ( g ( hc ? y ) e ) ) t r u e ( c e l l ( 1 ，l ，x ) ) 写作( t r u e ( c e l l1 17 x ) ) - , t r u e ( c e l l ( 1 ，l ，x ) ) 写作( n o t ( t r u e ( c e l l1 17 x ) ) ) p ( x ) ：= q ( x ) 八_ 1 r ( x ) 写作( = ( p ? x ) ( q ? x ) ( n o t ( r ? x ) ) ) g d l 的关键词有：r o l e 1 ，i n i g l ，l e g a l 2 ，t r u e 1 ，d o e s 2 ，n e x t 1 ，g o a l 2 ， t e r m i n a i 0 和d i s t i n c t 2 ，g d l 是可以根据需要自定义关键词的丌放式语言，但对 所有游戏来说上述九个基本的关键词是固定不变的。游戏设计者可以利用这些关 键词以及游戏自身需要自定义关键词进行游戏规则的描述。g d l 关键词的基本 语义如表1 1 ： 表1 1g d l 关键词及其语义 r o l e ( r )游戏玩家r i n i t ( f )f 在初始状态成立 l e g a l ( r ，m ) 存当前状杰r - - f 以执行动作m t r u e ( f )f 在当前状态成立 d o e s ( r ，m )r 执行动作m n e x t ( f )f 在下一状态成立 g o a l ( r ，n )当前状态一卜- r 得到n 分 t e r m in a l 当前状态是结束状态 d i s t i n c t ( x ，y )变量x 的值不等于变量y 的值 例如在在3 x 3 双人井字棋游戏中，游戏规则的g d l 释义如下：r o l e ( x ) ：游戏 玩家x ；( i n i t ( c e l l21b ) ) ：游戏的初始状态中单元格( 2 ，1 ) 是空的；( t r e e ( c e l l2lb ) ) ： 单元格( 2 ，1 ) 在当前状态下是空的；( d o s ex ( m a r k21 ) ) ：玩家x 在单元格( 2 ，1 ) 做上 标记；( n e x t ( c o n t r o l 功) ：玩家x 获得下状态的游戏控制权；( o 。流变量通常m y g 等表示，可以带有上下标。状态演算中 的流包括封闭流、和非封闭流。非封闭流又包括带存在量词的非封闭流和带全称 量词的非封闭流。 ( 2 ) 流集合 流集合是集合元素为流的集合，通常用z 表示流集合变量，可以带有上下标。 流集合由下列规则递归构成： 空集合。是流集合，称为空流集合，即不含任何流的流集合。 若是流，则仍是流集合。 若z l 、z 2 是流集合，则z l k - ) z 2 是流集合。 由上述规则经有限步所构造的流集合形如z i = 斩，五) ，其中颤l i 是状态； 若z i 、龟是状态，则z lu z 2 是状态。 状态分为已知状态、未知状态和不完全状态。设正、负已知流集合z 匕 研，磊) 、产 g l ，勘) ，其中瓜1 i u n i o n ( z n ， f i ，z n l ) ，s u b t r a c t ( z p ，【f 】，z p l ) ，z 1 = z ； fi = n ( f ) ，a b o l i s h ( fl ， z p ，z n ，z 】， z pl ，z n t ，zh ) ，u n i o n ( z n t ，【f 】，z n1 ) ) ， m i n u s ( z p l ，z n l ，z i 】，f s ， z p 2 ，z n 2 ，z 2 1 ) 其中，变量p e f f 代表j 下物理效应和正认识效应，通过谓词p l u s 3 将其添加 到状态中，n e f f 表示负物理效应和负认知效应，通过谓词m i n u s 3 将其从状态 中去掉。谓词p l u s 一( z 1 ，l + ，z 2 ) 中的z 1 表示更新前的状态，l + 表示正物理效应和 正认知效应集合( 简称正效应集合) ，z 2 表示更新后的状态；谓词 m i n u s _ ( z 1 ，l - ，z 2 ) 中的l - 表示负物理效应和负认知效应集合( 简称负效应集合) 。 谓词a b o l i s h ( f , z p ，z n ，z 】， z p l ，z n l ，z 1 】) 的作用是，若流f 与j 下流集合z p ( 或负流集 合z n ) 中的元素能够合一时，则从z p ( 或z n ) 中将所有能与流f 合一的元素删除， 然后再利用约束a b o l i s h 2 和a b o l o s h e d 2 将约束库中与流f 相关的约束( 即h o l d s 、 n o th o l d s 、a l lh o l d s 、a l ln o th o l d s 或o r 除。h o l d s ) 册1 2 5 本章小结 本章主要介绍了状态演算的基本理论及其实现语言s t e x 。在基本理论方面 主要介绍了状态演算的基本概念、状态知识及其更新和状态演算的推理机制；在 s t e x 方面主要介绍了s t e x 程序的框架结构，基本s t e x 语言。通过本章可以 基本了解状态演算的特点及作用，为通用游戏系统的自动推理奠定了理论基础。 1 8 第三章基于状态演算的通用游戏玩家系统的自动推理分析 与原型系统设计 3 1 引入状态演算的可行性研究 通用游戏系统接收游戏规则并翻译成自身系统识别的语言符号系统，在规定 的有限时间内根据策略做出最优选择以达到赢得游戏的目的。这就要求通用游戏 系统必须具备对游戏系统知识自动推理的能力，即能根据游戏动态环境的改变而 及时的更新自己的知识库，为策略选择提供知识支持。 游戏的规则描述包括游戏的初始状态、游戏的可执行条件、游戏的目标值和 游戏结束状态。其中游戏的可执行条件包括游戏的事实部分和规则部分。游戏的 事实部分可以看作是对游戏执行环境的事实性描述如棋盘类游戏的棋盘信息，游 戏的规则部分则是对游戏的可执行动作进行判断的依据。根据游戏的初始状态结 合游戏的事实部分，根据游戏的规则部分并依据游戏的目标值和游戏的结束状态 对游戏的可执行动作进行推理。这符合利用状态演算解释器s t e x 进行逻辑推理 的要求。状态演算解释器s t e x 推理的核心即为根据推理问题的初始状态结合推 理问题给出的描述推理问题的常识知识，利用前提条件公理和状态知识更新公理 对所推理问题进行推理，求出所推理问题的所有可执行动作的过程。 因此本文对行动推理形式化系统一状态演算进行深入研究，通过对游戏规则 和状态演算推理对应部分的转换，实现利用状态演算进行通用游戏系统自动推理 的功能。借助状态演算高效的推理机制提高了通用游戏系统的自动推理能力，为 决策的选择提供了有力支持，提高了通用游戏系统的整体能力。 3 2 通用游戏系统的自动推理分析 通用游戏描述语言g d l 具有一定的逻辑性，用通用游戏描述语言表示的游 戏规则也就具有一定的逻辑性。为进行自动推理，游戏规则必须具备对游戏的初 始状态、游戏的前提条件和游戏的状态知识更新以及游戏的目标状态和结束状态 的描述。根据游戏的目标状态和游戏的结束状态，依据游戏的初始状态，借助游 1 9 江苏大学硕士学位论文 戏的前提条件和游戏的状念知识更新条件完成游戏的自动推理。由于游戏的复杂 性，对游戏的推理分两步走：首先利用逻辑推理系统推理出游戏的可执行动作集 合并完成对游戏的状念更新和游戏下一状态的计算。其次依据上一步得到的可执 行动作集合利用智能搜索算法做进一步的搜索，得到最优动作做为返回动作。本 文将这两部分分别作为游戏系统的两个紧密联系的功能模块，称第一部分为游戏 的自动推理模块，第二部分为游戏的决策支持模块，在第四章中给出各个模块的 具体实现。 本文通过定义状态演算与通用游戏描述语言的部分关键词相应的谓词，以便 于利用状态演算和游戏信息中提取的游戏规则信息进行游戏规则的自动推理。利 用状态演算实现对游戏状态信息的更新和计算出游戏的下一状态。为了充分体现 最优原则，利用逻辑语言实现逻辑推理和面向对象语言实现游戏的搜索。本文利 用基于逻辑语言p r o l o g 的状态演算进行逻辑推理，利用面向对象语言j a v a 实现 的智能搜索算法进行搜索。e c l p s 。提供的p r o l o g 语言与j a v a 语言的接口 j a v a e c l 7 p s 8 接口，为游戏的自动推理部分和决策选择部分进行信息交流提供了 可能。 3 3 基于状态演算的通用游戏玩家系统的原型系统设计 3 3 1 通用游戏玩家原型系统的设计思路 为使通用游戏系统体现一定的通用智能，本文沿用了切实可行的通用游戏系 统的理论框架【眩】。状态演算在描述动态变化世界和通用游戏系统自动推理方面 的能力比较强大，在上一章节中我们已经实现了将状态演算作为通用游戏系统智 能推理这部分的功能。但是，要构造出具有通用智能的通用游戏原型系统，至少 还应考虑以下问题： 首先是转换问题，即如何把通用游戏描述语言转换为状态演算可以识别的符 号语言，并保证这种转换的有效性，反之亦然。状态演算作为刻画动态系统变化 规律的一种形式化工具，对动态变化世界进行了形式化描述，如h o l d ( a 歹) 表示流 a 在状态z 中成立。通用游戏描述语言对游戏的游戏规则进行了逻辑性的描述， 使游戏规则易于进行逻辑推理。基于游戏描述语言的简单性，易于和其他逻辑语 2 0 言进行转换，使通用游戏系统使用已经发展成熟的逻辑推理系统变得可能。因此， 在通用游戏系统中增加一个转换模块是十分必要而且可行的。 其次是通用游戏系统与游戏总控部分进行通信的问题，即通用游戏系统如何 获取游戏的规则、游戏丌始时问以及单步游戏的时间要求，并可及时正确的获取 游戏环境的动态变化信息以便做出f 确决策。如双人游戏中，在单步游戏规定的 时问要求内游戏双方根据对方上步游戏回应做出策略规划得到本步的游戏回应。 为及时获得动态信息，需要游戏系统与游戏总控部分之间的通信及时而准确。由 于对游戏信息的获取都与通用游戏系统和外界的通信有关，故将其归结为通用游 戏原型系统的通信模块。 3 3 2 通用游戏玩家原型系统的层次设计 如图3 1 所示，按照各层次的功能，将通用游戏原型系统分为三层，分别为 信息层、转换层和智能层。 游戏总控部分 ( ) 遗镪模块 彳产 t 芝， 信息整理模块 型黯 i 自动推理i 决策支持 模块模块 信息层 $ 转换层 $ 智能层 图3 1 通用游戏原型系统设计 ( 1 ) 信息层 信息层是通用游戏系统与游戏总控部分连接的桥梁，位于通用游戏原型系统 的最外层。借助信息层通用游戏系统可以获取游戏环境动态变化信息，为游戏的 正确进行提供了可能和保证。该层主要包括信息输出和信息接收两个功能模块。 ( 2 ) 转换层 转换层处于通用游戏原型系统的中间层，起着承上启下的作用，其主要职责 是将信息层接收到的游戏信息进行翻译处理，转换成通用游戏系统推理模块认知 的语言信息；同时对智能层推理出的游戏回应动作等信息进行分析，转换成由游 戏规则描述语言表示的信息。转换层包括游戏规则描述语言的翻译器和解析器两 2 1 江苏大学硕士学位论文 个功能模块。 ( 3 ) 智能层 智能层赋予通用游戏系统一定的通用智能，使通用游戏系统具备了进行通用 游戏的能力，是通用游戏原型系统的核心部分。智能层由自动推理模块和决策支 持模块两部分组成，是通用游戏系统进行逻辑思考的智囊团。 3 - 3 3 通用游戏玩家原型系统的功能模块设计 通过分析通用游戏玩家原型系统的设计思路和层次关系，本：爷给出了基于状 态演算的通用游戏玩家系统的功能模块示意图，如图3 2 所示。原型系统从总体 上分为四个功能模块，即通信模块、信息整理模块、自动推理模块和决策支持模 块。其中通信模块有消息接收、发送以及对接受的消息进行分类和回复的功能； 信息整理模块负责语言之f h j 的转换和初始化s t e x ；自动推理模块和决策支持模 块同属于智能层，为玩家系统提供智能支持；时问控制器贯穿于系统之中，与四 大模块紧密结合，为系统提供了统一的时间控制，为在规定时间内完成规定的任 务提供了可能。 圃 消 馓形雕崮 息 自蔓彰 预 爿蔓圉 处 理 时念器矽决臀块 图3 2 系统结构示意图 ( 1 ) 通信模块 通过建立s o c k e t 套接字监听当前主机与目标端i s l 3 8 1 。监听到目标端口发送 的请求消息时，接收消息并将消息进行预处理。监听到目标端口发送的请求消息 时，接收消息并将消息传送至信息整理模块进行解析后对消息进行分类处理并回 复。循环执行直到满足循环预设的中断条件满足时，结束循环，关闭s o c k e t 套接 字。 江苏大学硕士学位论文 消息的预处理包括在消息中提取出消息的正文部分，消息的正文分为三类： 游戏开始消息、游戏进行时的消息和游戏结束消息；获取当前时间并将其设定为 消息的接收时间；将提取的消息正文和获取的消息接收时f j 4 # 送给信息整理模块 做进一步的处理；对当前主机的回应消息进行“加密”后，将消息发送出去。 ( 2 ) 信息整理模块 g d l 解析器将接收到的预处理消息根据消息的种类分别做进一步解析：游 戏丌始消息中包涵游戏的游戏规则，g d l 解析器将游戏的游戏规则转换为将作 为游戏基础知识的e c l l p s 。解释器识别的p r o l o g 字符串；游戏接收到的消息种类 进一步细分为：游戏开始命令消息、游戏首次进行消息、游戏继续进行消息和游 戏结束消息和游戏应急消息。g d l 解析器按照消息的类型将其转换为s t e x 字 符串。 g d l 译成器主要用于将智能推理结果转换为g d l 语句以便进行消息的发 送。转换进行之前进行错误判断，以防将错误信息转换发送出去。 ( 3 ) 自动推理模块 自动推理模块实现根据游戏的规则进行推理，对游戏的状态进行更新的功 能。根据游戏的初始状态以及动作的可执行条件，对当前状态可执行动作进行推 理获得当前状态的可执行动作集合。在游戏进行中完成游戏系统的状态更新。 ( 4 ) 决策支持模块 决策支持模块辅助自动推理模块做出最佳选择。本模块由采用了0 【一p 剪枝技 术的m i n i m a x 搜索算法构成。搜索算法进行中，根据自动推理模块的推理获得 搜索过程中的后继状态及后继状态下的可执行动作，并依此进行进一步搜索。 3 4 本章小结 本章给出了基于状态演算的通用游戏玩家系统的自动推理分析与原型系统 的设计。首先给出了引入状态演算的可行性研究，然后对通用游戏的自动推理予 以分析，最后给出了基于状态演算的通用游戏原型系统的设计的思路和层次以及 功能模块设计。 江苏大学硕士学位论文 第四章基于状态演算的通用游戏玩家原型系统的实现 4 1 系统开发环境简介 本系统开发环境包括：在w i n d o w sx p 系统上安装v m w a r e 虚拟机5 0 ，在 虚拟机上安装l i n u x 操作系统r e dh a t 9 0 ，j a v a 开发工具包j d k l 6 ，i d e 工具为 e c l i p s e 3 0 。此外，系统还用到了一些其他开发工具： ( 1 ) e c l 7 p s 8 e c l p s 。是一个基于约束逻辑程序范式的软件系统，主要解决了基于约束逻 辑程序的商业开发和部署，比如规划，调度，资源配置，时间表及运输等领域。 ( 2 ) g a m e c o n t r o l l e r 本地游戏模拟控制器 g a m e c o n t r o l l e r 是通用游戏网站提供的免费的本地游戏控制器，是模拟的游 戏总控部分，由j a v a 编写而成。 本文使用e c l p s 8 和j a v a 实现通用游戏玩家系统。给出第三章中系统的各 功能模块的实现。 4 2 通信模块的实现 利用e c l p s 。的内部谓词h t t ps e r v e r 1 和h t t p实现通信模块和游戏总 控部分的通信功能。h t 和, s e 谓r v 词e r 通2 t p过创建一个绑定并监听s e r v e r 1h t t p s e r v e r 2 当前主机和所给端口的套接字接口；接收游戏控制器端口发送的请求消息s ，通 过代码行2 中谓词r e q u e s t _ r e c p 5 分离出消息的正文部分存储在o b