（计算机软件与理论专业论文）竞争环境下基于知识的决策方法.pdf

竞争环境下基于知识的决策方法 专业：计算机软件与理论 硕士生：程丽明 指导教师：周青副教授 摘要 决策问题是当前计算机科学中相当流行的研究方向，并且在实际中有着很重 要的应用。现在的决策系统大部分是依赖于搜索来完成，受计算机运行速度的影 响较大。当今决策问题的解决方法主要是对竞争经验的储存应用。我们的决策系 统是基于竞争环境下运用现有知识而作出决策的一阶逻辑系统。我们主要是利用 知识集对当前环境进行分析以找出所有可能采取的行为，并对之产生的结果进行 比较，从而选择最能取得胜利的行为。以往的基于搜索的决策系统相比，我们研 究的决策系统是基于现有知识和当前环境信息而作出决策。这种决策方法更为合 理：它更加接近人类思维，所作出的决策与当前的竞争领域和竞争者密切相关。 在本文中，我们首先对环境和系统的基本概念进行了说明和定义，随后引入 我们竞争环境下基于知识的决策系统的基本概念，并对之严格定义。最后我们给 出了我们竞争环境下基于知识的决策系统的算法。其问我们列举了大量的竞争环 境的例子对定义和算法进行了解释说明，以便理解。 关键词：状态，环境，知识，行为，支持度 k n o w l e d g eb a s e dd e c i s i o nm a m n gi nc o m p e t i t i v ee n v i r o n m e n t m a j o r ：c o m p u t e rs o f t w a r ea n dt h o e r y n a m e ：l i m i n gc h e n g s u p e r v i s o r ：q i n gz h o u a b s t r a c t i nt h i sp a p e r , w ed i s c u s st h ed e c i s i o n - m a k i n g , w h i c hi sb a s e do nc u r r e n t k n o w l e d g ei nac o m p e t i t i v ee n v i r o n m e n t a l s ow eb u i l taf i r s to r d e rl o g i c a ls y s t e mt o i m p l e m e n to u rd e c i s i o n - m a k i n gs y s t e m u n l i k et h eo t h e rd e c i s i o n m a k i n gs y s t e m s p e o p l em a d e ，w ej u s tu s e “c u r r e n t ”k n o w l e d g e ，w h i c hi sd e p e n d e do nt h ec o m p e t i t i o n w ee n g a g ei n ，t oc h o o s et h eb e s ts t e pw ew i l ld oa tt h en e x t ；a n dt h i ss y s t e mi sd e s i g n t ob ea p p l i e di nac o m p e t i t i v ee n v i r o n m e n t ( 1 i k eg a m e so rf i n a n c e ) m a i n l y a n dt h i s s y s t e mm o r ea p p r o a c ht oh u m a nb e h a v i o r f i r s tw ed e f i n et h eu n i v e r s a ln o t i o n si nf i r s to r d e rd e c i s i o n - m a k i n gl o g i c a ls y s t e m ， l i k ek n o w l e d g e ，e n v i r o n m e n t a l s ow ea d dt h et w os p e c i a ls t a t e s ( w o na n dl o s t ) a n d t w o s p e c i a lq u a n t i f i c a t i o ns t a n d a r d s ( a d v a n t a g e a n d d i s a d v a n t a g e ) i n t h e d e c i s i o n - m a k i n gs y s t e mw em a d e a n df i n a l l yo u ra l g o r i t h m sa r ep u tf o r w a r d s a l s o w ei l l u s t m t es o m ee x a m p l e st om a k et h er e a d e r sm o r ec l e a ra b o u to u rs y s t e m ，w h i c h i sa p p l i e di nac o m p e t i t i v ee n v i r o n m e n t k e y w o r d s ：s t a t e ，e n v i r o n m e n t ，k n o w l e d g e ，a c t i o n ，s u p p o r t i n g d e g r e e i i 1 1背景介绍 第1 章引言 决策问题是当前计算机科学中相当流行的研究方向，有着重要的地位。决策 方法一般是依赖于搜索，所以决策系统的速度受计算机运行速度的影响较大。而 当今大多数决策方法是应用储存的竞争经验来作出决策。 决策问题涉及到数理逻辑，人工智能等方面。目前的决策问题是在计算机 科学领域相当流行。当前的决策问题主要有两种解决方法：一种是传统的使用搜 索的方法来实现；另外一种是用人工智能的方式来完成。前一种是主要是依靠搜 索算法来完成，依靠计算机计算将来若干步所有的可能结果，然后再分析选出( 即 做出决策) ，如击败国际象棋师的i b m “深蓝”( “深蓝 在匡f 际象棋大赛中与卡斯 帕罗夫大师交手，它的原理也就是搜索算法。) ；另外一种是利用人工智能相关知 识来完成的。 1 2当前利用人工智能完成决策的主要方法 利用人工智能相关知识来完成的决策解决方法主要有遗传算法，基因算法， 竞争学习方法，用模式识别方法，用启发式算法，神经网络学习方法及以上算法 的组合，等等。 1 2 1遗传算法 由计算机来来模似多个竞争对手进行多次竞争，每次竞争时留下最优秀的竞 争者。最终留下若干个优胜者，记录学习这些优胜者的比赛记录。 在文献f l 】中，a l e x a n d r am a r k ，b e r n h a r ds e n d h o f t 和h e i k ow e r s i n g 运用 了遗传算法的思路来解决决策问题，再加入了学习方法后构成了一个大致的决策 系统。他们将这个决策系统用于在竞争环境中：学习对手立即作出的策略和环境 的变化以作出最优决策。事实证明，这种系统在即时游戏中的表现比其他决策系 统要优秀的多。 1 2 2基因算法 同多个对手竞争，从竞争经验中学习自身优秀的决策，以作为提高决策准确 的方法。 在文献【2 】中，c h u e n - t s a is u n 和m i n g - d aw u 运用类似负反馈的机制将g a 搜索思想稍加改善，并运用到游戏o t h e l l o 中。并且用实验证明，这种方法比传 统的g a 算法更为优秀。 1 2 3竞争学习方法 同多个对手竞争，从竞争经验中学习对手优秀的决策，以作为提高决策准确 的方法。 其中的代表之是文献【3 ，文中x a v i e r m 6 n a g e 和b e r n a d e t t e 提出了可能的 n 元簇贡献( c l u s t e r i n gn - t u p l e so f p o s s i b i l i t yd i s t r i b u t i o n s ) ，这一概念，其基本原 理是基于神精网络的竞争学习方法。每一种“簇”代表了一个原型，也就是相同的 例子。于是他们在系列例子中找到这一种“簇”，将之保存起来。并且在接下来 的竞争中，不断的保存新的“簇”，就这样得到了n 个原型。 1 2 4用模式识别方法 其中有针对个人和多人的模式识别方法。针对个人模式识别方法是将个人 的模式( 如遇到相同的模式，个人会作出相同的反应) 储存起来。当与此人竞争 时，以此估计对手可能的反应，以之为根据来作出决策。而多人的模式识别方法 是将多个竞争者的模式储存起来以作为竞争时的模式参考。其中，模式识别也可 用于考虑作出决策时的选择答案。 这种决策系统的典型代表是文献 7 】，文中s t e v e nw a l c z a k 使用了“p a t e n ” ( 模) 这个概念。以国际象棋为例，在竞争中某个特定的人类通常对特定棋局会 作出相似的反应，他将这种特定棋局定义为“p a t t e r n ”，并将之连同相应的反应存 入计算机中，然后在竞争中对识别出“p a t t e m ”作出相应的对策( 作出反应动作或 是预测对手将采取的行为) 。采用这种决策方法，他大大降低了对决策树的分析。 1 2 5用启发式方法 用启发式方法减少计算机的搜索量，提高搜索的步数，优化决策。 文献 1 1 】介绍了一个运用节点的新概念：用节点来选择有效的决策点。而这 些节点是一条计算并且体现主要输入参数的直线。这就意味着在这条直线上的决 策与针对主要输入参数而进行的决策相同。因此，通过在这些节点上的决策，我 们能推导出最终的决策结果。以上的发现能显著的降低我们的搜索空间。同时它 也运用实验加以证明这种方法的有效性。 1 2 ，6以上两种或多种的综合应用 大多数文章都是以上两种或是多种方法的综合运用。 1 3简述本文内容，意义及结构 以上是现在决策方法的大致走向。但是他们都存在着一些局限性：一些人将 精力集中于搜索算法：另外的一些人使用人工智能的方式来解决。但是遗憾的是， 没有人将精力放在利用当前环境下现有的知识来解决决策问题。 所以我们提出了一个新的决策系统竞争环境下基于知识的决策系统来 解决这些问题。与其他的决策系统不同的是，我们利用“现有的知识”来做出决策。 而这些“知识是与我们所处的竞争环境密切相关的。我们利用这些知识推测出目 前可以作出的选择，并对之进行分析，最后选取最能达到我们期待环境的行为。 这种决策系统能避免做出直接的错误决定( 而其他的决策系统往往在这一步有重 大缺陷) 。我们的基于知识的决策系统主要是运用于竞争环境下的，它主要是依 赖于“知识集”( 也就是我们所掌握的与竞争种类相关的信息) ，而不是搜索。也 就是说，我们的基于知识的决策系统有更加广大的应用，而不仅仅是停留在对抗 游戏领域。在本文我们列举的大量例子中，大家可以看到我们的基于知识的决策 系统与其他决策系统相比有着更多的优越性。 在这篇文章里，我们主要讨论了基于现在知识的用于竞争环境中的决策问 题。同时我们也建立了一个一阶逻辑系统来实现我们的决策系统。我们首先定义 了我们决策系统中最基本的的定义，然后我们引入了环境和知识集这两个特别的 概念，然后定义了我们决策的重要参数a d v 和d s v 。这四个概念是我们决策系统 中最重要的概念。这篇文章给出了决策问题的一个新的解决方案，同时也对所提 出的技术和结果的有效性和局限性进行了评价，同时也适当地引用和介绍了与之 相关的历史文献。 在本文中，我们将如下组织我们的结构：在第一部分内( 前言) ，我们主要 回顾了前人所做的有关决策方面的工作，我们将这些工作分类，并且同我们的工 作相比较。在第二部分，我们向读者列出了我们的工作：我们首先介绍一阶逻辑 系统中最基本的概念( 状态和环境) ，随后定义了赢和输；然后我们定义了行为 和路径；接着是行为结果的定义：在结出算法之前我们定义了a d v 和d s v ；之后 列出了支持度的计算公式；最后我们给出算法来向读者显示我们的决策系统。同 时我们列举了大量的生活，商业例子来说明我们的决策系统。在算法之后我们还 将我们的决策系统运用于一个真实的竞争例子( 田忌赛马) 之中。通过与以往传 统的决策过程的比较，大家可以更加清楚的看出我们决策系统与其他决策系统相 比所具有的优越性。在文章的最后一章中，我们对全文进行了概括总结，同时指 出了我们基于知识的用于竞争环境的决策系统能适用的广阔领域：总述了基于知 识的用于竞争环境的决策系统的优越性，并提出了其中的可继续研究的方向。 第2 章基于知识的决策系统的概念和定义 2 1基于知识的决策系统的环境的基本概念和定义 我们所做的基于知识的决策系统是要应用于竞争环境下的，以下是我们对于 竞争环境的基本概念的定义。设t 表示为一个固定的一阶逻辑系统，而l 是它 的语言。 我们假定环境是由状态所组成以下是我们的定义： 定义2 - 1 ：一个状态s t a t e 是l 的闭公式而环境e n v i r o n m e n t 是l 的一个闭公 式的有穷集合我们认为环境e n v i r o n m e n t 是不冲突的。 一个状态描述了竞争环境的一个信息，而环境是由我们所在的竞争环境中所 有的状态组成的环境是我们所做的基于知识的决策系统所需要的所有关于竞争 环境的信息。 例2 - 1 ：以五予棋为例，我们进行分析。为了便于分析，我们将五子棋的棋盘大 小和规则进行简化。设我们的五子棋是一个8 乘8 的一个棋盘，只要五子连成一 线，即为胜。 图2 - 1 所示的是一个五子棋的对奕环境。+ 代表着我们所用的黑子，而o 代 表着我们对手所用的白子。我们能根据定义列出这个竞争环境下的状态。为了节 省空间，我们仅列出以下状态： abc defg h o o + o 图2 1 目前的一个五子棋对奕环境 s t a t e , = b 2 ( b )s t a t e l = c 3 ( b )s t a t e = d 4 ( b ) s t a t e3 = e 2 ( w ) s t a t e , = e 3 ( w ) s t a t e s = a i ( e ) e n v i r o n m e n t = s t a t e l ) = s t a t e 1us t a t e us t a t eus t a t eus t a t e 5u = b 2 ( b ) ，c 3 ( b ) ，d 4 ( b ) ，e 2 ( w ) ，e 3 ( w ) ，a i ( e ) ) 其中b e ( b ) 这种形式表示着：b 2 是表示为棋盘上的位置，而括号中的b 表示着 这个位置放的是黑子，若括号里的是w 表示着是这个位置放的的白子，但若 括号里的是e ，则代表着这个位置是空的，可以放入任何棋子。 我们参与竞争的最终目的是获胜，要作出决策，首先必须知道赢和输的标准， 所以我们进行如下定义： 定义2 2 ：一个赢w o n 或是一个输l o s t 都是一个环境。赢w o n 是我们所想要达 到的环境，而输l o s t 是我们所想要避免达到的环境。 一个赢w o n 或是一个输都是l 的一个闭公式的有穷集合。一个赢w o n 或 是一个输l o s t 都是由些状态s t a t e s 组成。如果环境e n v i r o n m e n t 为赢w o n ( 或 是输l o s t ) ，我们就可以认为我们赢w o n 了( 或是输l o s t 了) 所以赢w o n 是我 们所期待的环境，而输l o s t 是我们所想要尽可能避免的环境。但并不是所有的 竞争环境都是一个的局面：竞争者必须有一个是赢的，或是输的。有可能是大家 都是赢的，或者大家都是输的。总而言之，我们的赢w o n 并不一定与其他人的 输l o s t 相关。这只是我们认为赢w o n ( 或是输l o s t ) 的标准而已。 例2 - 2 ：让我们再看看上面五子棋的例子。从我们定义的规则中，我们可以得到 如下的赢w o n 和输l o s t 的定义： w a n f = a i ( b ) ，b 2 ( b ) ，c 3 ( b ) ，d 4 ( b ) ，e s ( b ) ) ab cdefg h 1 + 2 水 3 + 4 + 5 + 6 7 8 图2 - 2 一个五子棋黑方赢的环境w o n l w o n z = b 2 ( b ) ，c 3 ( b ) ，d 4 ( b ) ，e 5 ( b ) ，g 6 ( b ) a b c d efgh 图2 3 个五子棋黑方赢的环境、v o n 2 abc de fg h lo 2o 3o 4o 5o 6 8 图2 - 4 一个五子棋黑方输的环境l o s t i 在我们开始其他内容之前，我们应先对竞争环境下参与者进行定义： 定义2 3 ：竞赛者p l a y e r 是能改变环境的人，而竞争者c o m p e t i t o r 是我们以外的 所有竞赛者 竞争者c o m p e t i t o r 可能我们在竞争环境下环境e n v i r o n m e n t 的变化做出反 应。需要注意的是在这个竞争环境中我们可能有不止一个的竞争者c o m p e t i t o r 。 例2 3 ：我们举个田忌赛马的例子。田忌与齐王赛马，田忌( 我们表示为t j ) 有上，中，下三种马( 我们分别表示为a l ，a 2 ，a 3 ) 。而齐王( 我们表示为q w ) 也有上，中，下三种马( 我们分别表示为b i ，b 2 ，b 3 ) 。若将马的实力由高到 低分为6 个等级( 从6 到1 ) ，则田忌的马分别是5 ，3 ，1 ；而齐王的马分别是6 ， 4 ，2 。现知道齐王的马的出场顺序为b 1 ，b 2 ，b 3 。若我们为田忌赛马，应该如 何决策才能胜出齐王( 胜利条件为三局两胜) 。 由以上例子，我们可以得出； p l a y e r = t juq wc o m p e t i t o r = q w s t a t e l = a 1 ( 5 ) ，s t a t e 2 = a 2 ( 3 ) ，s t a t e 3 = a 3 ( 1 ) ，s t a t e 4 _ b 1 ( 6 ) ，s t a t e 6 ；b 2 ( 4 ) ，s t a t e s = b 3 ( 2 ) 以上6 个类似的式子，其中a l ( 5 ) 这科- 形式表示着：a 1 是表示为田忌的上马， 而括号表示这匹马的实力。 s t a t e 产t j ( o ) ，s t a t e 8 = q w ( o ) 以上2 个类似的式子，其中t j ( o ) 这种形式表示着：t j 是表示为田忌，而括号表 示t j f o ) 的所胜局数。 s t a t e 9 = r o u n d l ( o ) ，s t a t e i o = r o u n d 2 ( 0 ) ，s t a t e l l = r o u n d 3 ( 0 ) r o u n d l ，r o u n d 2 ，r o u n d 3 分别表示我们的马的的出场次序，括号内为马的代号， 0 为暂时没有安排，而r o u n d 0 1 ，r o u n d 0 2 ，r o u n d 0 3 ( s t a t e s t a t e t 3 ，s t a t e l ) 对应的代表齐王马的的出场次序。 e n v i r o n m e n t = s t a t e l ，s t a t e 2 ，s t a t e 3 ，s t a t e 4 ，s t a t e s ，s t a t e 6 ，s t a t e 7 ，s t a t e 8 ， s t a t e 日，s t a t e l o ，s t a t e l l ，s t a t e l 2 ，s t a t e l 3 ，s t a t e l ) w o n = ft j ( 2 ) ，t j ( 3 ) ，q w ( o ) ，q w ( 1 ) ) l o s t = t j ( o ) ，t j ( 1 ) ，q w ( 2 ) ，q w ( 3 ) 定义2 - 4 ：一个行为a c t i o n 是由一个竞赛者p l a y e r 次做出的有穷的状态改变 的序列，形如p i 号q ，p j 弓q j ，- ，p n 考q 。 说明：行为a c t i o n s 是个函数，它描述了在我们所在的竞争环境中由个竞赛 者p l a y e r 一次做出的所有能执行的行为。它表示了一个竞争者c o m p e t i t o r 所执 行行为对环境中的某些状态s t a t e s 的有序的改变情况( 依次改变了n 个状态 s t a t e s ) 。 例2 - 4 ：我们再来看看去麦当劳吃快餐的例子。设可乐( 以c o k e 表示) 为4 元， 薯条( 以c h i p s 表示) 为5 元，个巨无霸( 以b i g 表示) 为1 0 元，设现在可 以花费的钱( 以m o n e y 表示) 为2 0 元，则我们可以作以下行为： a c t i o n l = c o k e ( 0 ) j c o k e ( 2 ) ，m o n e y ( 2 0 ) 弓m o n e y ( 1 2 ) ) a c t i o n 22 b i g ( o ) = b i g ( 1 ) ，m o n e y ( 2 0 ) 弓m o n e “1 。) ) a c t i o n 32 b i g ( o ) 号b i g ( 1 ) ，m o n e y ( 1 2 ) = m o n e y ( 2 ) ) 说明：其中c o k e ( a ) ，b i g ，c h i p s ( c ) 表示我们已买的可乐数量为a ，巨无霸数 量为b ，薯条的数量为c ；而m o n e y ( n ) 表示我们还有n 元。 例2 - 5 ：现有6 个石子。兰个人( a ，b ，c ) 轮流拿，我们( a ) 先拿。有规定 一次一人最多拿2 个，但不可不拿，最后一个取石子的人为输家。问如何决策? 首先，我们认为环境e n v i r o n m e n t = a ( 0 ) ，b ( 0 ) ，c ( 0 ) ，n u m ( 6 ) ) 。其中n u m 是没有拿走的石予数。a ( n ) 代表着a 拿了的石子总数为n 。b ( n ) ，c ( n ) 的情况与 a ( n ) 类似。已知我们先拿，则有以下可能的行为： a c f i o n l = a ( o ) j a ( 2 ) ，n u m ( 6 ) = n u m ( 4 ) ) a c t i o n 2 = ( b ( 0 ) 专b ( 2 ) ，n u m ( 4 ) 习n u m ( 2 ) ) a c t i o n l 是a 可能的一种行为，而a c t i o n 2 是紧接a 作出后a c t i o n l ，b 可能的 种行为。 定义2 5 ：路径p a t h 是行为a c t i o n s 的个序列并且有p a t h = a l b j a t p ? 证 一肛i n i - 。其中我们约定旺i 是我们所执行的行为a c t i o n ，亿是竞争者 c o m p e t i t o r s 所执行的行为a c t i o n 。 说明：路径p a t h 是对竞争环境下一个可能的竞争过程的描述。如果没有一个竞 赛者p l a y 在我们做出某个行为a c t i o n 之后作出任何行为a c t i o n ，那么我们就把 他所对应的行为a c t i o n 表示为空集( ) ) 。为了说明方便，以下如不经特殊说明， 我们用q i 表示我们所执行的行为a c t i o n ，而用仇表示其他竞争者c o m p e t i t o r s 所执行的行为a c t i o n 。 例2 - 6 ：如田忌赛马，有如下可能行为a c t i o n ： 旺2r o u n d l ( o ) r o u n d l ( a 1 ) 吼2r o u n d 0 1 ( o ) j r o t m d 0 1 ( b 1 ) 任1 = r o u n d 2 ( o ) ：，r o t m d 2 ( a 3 ) 而有可能p a t h l = u ，p l ，n l 这表示为田忌先出最好的马，接着齐王也出他最好的马，然后田忌再出最差的马。 这也是一种可能的比赛过程。 当我们做出一个行为a c t i o n 之后，就对状态s t a t e 进行了改变，从而改变了 环境e n v i r o n m e n t 。现在我们可以看到行为结果c o n s e q u e n c e _ o f _ a c t i o n 是现有 的环境e n v i r o n m e n t 被行为a c t i o n 所改变后的新环境e n v i r o n m e n t 。于是我们 可以引入以下定义。 定义2 6 ：记算符的表达式 ，t ；2 e n v i r o n m e n t p i uq i = ( e n v i r o n m e n t 一 p 1 ) u q l ) 一 p 2 u q 2 ) ， 公式( 2 1 ) 其中i = 2 定义2 7 ：记算符f 和算符g 的表达式f o g ( x )= g ( f ( x ) ) 公式( 2 2 ) 定义2 - 8 ：c o n s e q u e n c e o f _ a c t i o n ( e ) = e n v i r o n m e n t - p i uq ， j 公式( 2 3 ) 其中a c t i o n = p f ：，q l ，p i ：q i ，p n j q 。 说明：行为结果c o n s e q u e n c e _ o f _ a c t i o n 是在现有的环境e n v i r o n m e n t 下，我们 做出行为a c t i o n 而改变了其中某些状态的新环境e n v i r o n m e n t 。 例2 - 7 ：接着例2 5 分析： 若一开始就我们作a c t i o n l ，则有： c o n s e q u e n c eo fa c t i o n l ( e ) = e n v i r o n m e n t - - a ( 0 ) ，n u m ( 6 ) u a ( 2 ) ，n u m ( 4 ) 若对手b 作行为a c t i o n 2 ，则有作所有竞争者c o m p e t i t o r s 所执行的行为结果： c o n s e q u e n c e _ o fa c t i o n 2 ( e ) = e n v i r o n m e n t - - b ( o ) ，n u m ( 4 ) u b ( 2 ) ，n u m ( 2 ) 2 2基于知识的决策系统的基本概念和定义 在竞争决策中，我们常常会有这样的情况，在当前环境下有一条路径，如果 执行了路径上所有的行为，我们就能取胜；相同的我们常常会有这样的情况，在 当前环境下有一条路径，如果执行了路径上所有的行为，我们就会遇到失败。所 以我们对这两种特殊的路径加以定义： 定义2 - 9 ：若路径p ( p = 8 - 6 一s j 6 。) 满足 c o n s e q u e n c e _ o f a c t i o n l o c o n s e q u e n c eo fa c t i o n 2 0 o c o n s e q u e n c eo fa c t i o n i o o c o n s e q u e n e e _ o f a c t i o n n = w o n ，则p 称为致胜路径w i n n i u g p a t h ； 若路径p 满足 c o n s e q u e n c eo fa c t i o n l o c o n s e q u e n c e o f _ a c t i o n 2 0 o c o n s e q u e n c eo fa e t i o n i 。o c o n s c q n e n e eo fa c t i o n n = l o s t ，则p 称为致输路径l o s i n g p a t h 。 说明：致胜路径w i n n i n g p a t h 是种路径p a t h 。在当前的环境e n v i r o n m e n t 下， 如果该路径p a t h 被执行，那么最终的环境为赢w o n 。 致输路径l o s i n g p a t h 是一种路径p a t h 。在当前的环境e n v i r o n m e n t 下，如果该 路径p a t h 被执行，那么最终的环境为输l o s t 。 在竞争中我们也会碰到这样的情况：在当前的环境中，无论对手采取什么行 为，我们都可以采取相应的行为而取胜；或者是无论我们采取什么样的行为，对 手都能采取相应的行为而导致我们失败。那么这就引入了我们对这两种特殊环境 的定义： 定义2 1 0 ：如果在当前的环境e n v i r o n m e n t 下，存在着行为咖，并且对于任何 的i ( i - - o ，1 ，n ) ，无论竞争者采用任何b i ，我们都可以找到相应的毗使得 a o p 。旺，p i 啦p 。是一条致胜路径；那么我们称这种环境为致胜位置 w i n n i n g p o s i t i o n 。 如果在当前的环境e n v i r o n m e n t 下，存在着行为咖，并且对于任何的i ( i = 0 ，l ，n ) ，无论我们采用任何旺j ，竞争者都可以找到相应的p j 使得 a o p ，n ，b m f t 一p 。旺。是一条致输路径；那么我们称这种环境为致败位置 l o s i 目i g p o s i t i o n 。 说明：无论是致胜位置w i n n i n g p o s i t i o n 还是致败位置l o s i n g p o s i t i o n 都是l 的 有限公式集他们都是状态集，也都是一种环境e n v i r o n m e n t 。对于致胜位置 w i n n i n g e o s i t i o n 而言，如果每一步我们都选择正确的行为，我们就能获得胜利： 同样的，对于致败位置l o s i n g p o s i t i o n 而言，如果每一步对手都选择正确的行为， 我们就难免失败。 例2 8 ：致胜位置 以五子棋为例，对图2 s 分析： ab cdefg h o o + o 图2 5 致胜位置w i n n i n g p o s i t i o n 示意图 因为我们有p a t h = 程，b 1 ，q i 其中n = f e 5 ( e ) je 5 ( b ) ) c o n s e q u e n c e _ o - a c t i o n ( a ) = e n v i r o n m e n t - - e 5 ( e ) ) u e 5 ( b ) ) a b cdefg h o o + o 图2 6p a t h = 也的示意图 若p ，= a i ( e ) = 争a 】( w ) ，则我们可以做行为旺，= e 5 ( e ) 号e s ( b ) ) ，使得 - 1 3 - ， 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 c o n s e q u e n c e o fa c t i o n n o c o n s e q u e n c eo fa c t i o n p ，o c o n s c q u e n c eo f _ a c t i o n a = c o n s e q u e n c eo f a c t i o n a - - a 1 ( e ) u a i ( w ) - - e s ( e ) u e 5 0 3 ) 所以我们有： e n v i o r n m e n t = w o n 如下图( 图2 7 所示) a b c defgh lo 2 3 4 5 6 7 8 o + o + o 图2 7p a t h = 旺，p 1 ，旺t 的示意图 若p ，= f 6 ( e ) 寺f 6 ( w ) ) ，则我们可以做行为- = a 1 ( e ) 寺a i ( b ) ) ，使得 c o n s e q u e n c e _ o f a c t i o n o c o n s e q u e n e eo fa c t i o n p o c o n s e q u e n e eo fa c t i o n a = c o n s e q u e n c e o f _ a c t i o n n f 6 ( e ) uf 6 ( w ) - - a i ( e ) ua 1 ( b ) 所以我们有： e n v i o r n m e n t = w o n 如下图( 图2 8 所示) 1 4 - ab cdefg h l + 2 + o 3 + o 4 + o 6 o 7 8 图2 8p a t h = ，肛，伍，的示意图 其他pz 的情况下，只要我们做出扭，= a 1 ( e ) - - - - - o a ( b ) ) 或任，= f f 6 ( e ) 号f o ( b ) ) 即可。这样在图所示的环境下，我们就一定能获胜。 例2 - 9 ：致输路径 在以下图图2 9 所示的环境中，我们也有致输路径p a t h = m l i n 2 m 3 m 4 m l = a i ( e ) 号a k b ) a b c d efgh 1 2 + o 3 + 0 4 + o 5 6 7 8 图2 9 致输路径p a t h = m i r a 2 m 3 n 1 4 中m l 作用示意图 m 2 ； f i ( e ) = f i ( u ，) a b c d efg h 1 4 o o + o + 0 图2 1 0 致输路径p a t h = m 1 f i l l 2 m 3 m 4m i m 2 作用示意图 1 1 1 3 = g l ( e ) 辛g 1 ( b ) j abcdefg h 图2 i i 致输路径p a t h = m j m 2 m 3 i n 4m l m 21 1 1 3 作用示意图 1 6 ， 2 3 4 5 6 7 8 + o o 0 0 ， 2 3 4 5 6 7 8 m 4 = f 5 ( e ) 弓f s ( w ) ) ab l 2 3 4 5 6 7 8 c d ef o 0 o + o o 图- t - 二致输路径p a t h = m l m 2 m 3 m 4m l m 2m 3 她作用示意图 c o n s e q u e n c eo fa c t i o n a o c o n s e q n c n c eo fa c t i o n p o c o n s e q u e n c eo fa c t i o n n 。 l o s t 从现实生活中可以知道，任何行为的产生都是需要一定的条件的，我们在判 断在当前的环境下是否能作出某一行为，就必然需要知道这一行为的前提条件： 定义2 。i l ：若条件1 l r - 。e n v i o r n m c n ，则可执行行为a c t i o n 。其中v 是状态s t a t e s 的集合，则我们称v 是行为a c t i o n 的前提条件p r e c o n d i t i o n o f a c t i o n ，记为u p n a c t i o n 。 说明：要注意的是某个行为的前提条件可能不止一个。平e n v i o r n m e n t 表明环 境e n v i o r n m c n t 满足行为a c t i o n 的前提条件p r e c o n d i t i o n 。此时竞赛者p l a y e r 就能在当前的环境e n v i o r n m e n t 下作出该行为a c t i o n 。 定义2 1 2 ：行为b 是合理的行为r e a s o n a b l ea c t i o n 当仅当rn b 且r e n v i o r n m e n t 。 我们把合理的行为r e a s o n a b l e a c t i o n 的集合称为是当前环境e n v i r o n m e n t 下可 选择行为s e l e c ta c t i o n 。 说明：r _ c e n v i o r n m e n t 是指环境e n v i o r n m e n t 满足行为a c t i o n 的前提条件 p r e c o n d i “o n 。 第3 章竞争环境下基于知识的决策系统的基本构思 以上是我们的外部环境和我们系统内的环境的描述。现在我们开始介绍我们 的系统，以及我们基于知识的决策系统中所需要的一些概念和定义。 我们的决策系统是一阶逻辑系统。根据以上的定义，我们现在可以基本描述 出一个竞争环境，以及进行决策所需的前提条件( 知识k n o w l e d g e ) 。 从以往的竞争经验知识来看我们可以得到这样的结论：在我们当前的位置 上( 环境) ，通过采取某些适当的行为而赢w o n 的方法越多( 用我们以上的定义 而言就是通向致胜位置的路径越多) ，那么我们越有可能到达赢的状态。同样的， 如果在当前的位置上( 环境) ，由于采取某些特定的行动而输l o s t 的方法越多( 用 我们以上的定义而言就是通向致输位置的路径越多) ，那么我们越有可能到达输 的状态。那么这种输和赢的“可能”成了我们衡量动作结果好坏的标准，也成为 我们决策系统中的重要参数。于是我们定量的用a d v 和d s v 来定量的描述这些 可能性： 定义3 1 ：若在当前环境e 中存在一条路径通向致胜位置，贝称为有一个a d v 。 若在当前环境e 中存在一条路径通向致输位置，则称为有个d s v 。 说明：若在当前环境e 中存在一条路径p a t h 使得这条路径上所有的行为被执行 后环境是w o n 或是w i n n i n g p o s i t i o n ，则称为有一个a d v 。 若在当前环境e 中存在一条路径p a t h i 使得这条路径上所有的行为被执行后环境 是l o s t 或l o s i n g p o s i t i o n ，则称为有一个d s v 。而在当前环境e 是否存在一条路 径p 通向致胜位置，或是存在一条路径p 通向致输位置，这是可以由算法计算 得出的( 我们将在下一章列出算法以证明) 。 现在，我们对基于知识的决策系统所需的所有定义，命题和基本的原理都作 了说明。我们基于知识的决策系统所要做的就是分析当前的环境，寻找所有可以 执行的行为，并对其中的合理行为逐一进行判断：如果这个合理行为的行为结果 是赢或者这个合理行为的行为结果是致胜位置，我们则采取这个行为；相对的， 如果这个合理行为的行为结果是输或者这个合理行为的行为结果是致输位置，我 们则不考虑这个行为；否则，我们就得进一步分析采取哪一个行为后是否能更有 可能赢，以使我们的决策结果鼹优化。然而我们应该如何分析采取某个行为后能 更有可能赢昵? 正如前面所述，我们的决策系统要做出决策，除了所需要知道当前的环境以 外还需要相关的知识来进行决策。现在我们大致的总结出了一些知识，并且把 这些知识大致分为五类，由此定义知识集这一概念。因为我们仅仅对评估算法的 可行性进行理论上的讨论，所以在这里可以假设这个知识集是完备的，也就是说 它涵盖了所有的我们需要的知识。其中，主要由以上五类知识组成： 定义3 - 2 ：知识k n o w l e d g e 是l 中公式的有限集，称为系统的知识集： k n o w l e d g e 中有四类知识： 1 ) 第一类知识集k 1 r = q l , q 2 - - , q 。j ，其中r 表示一个函数，p 为系统的个无变元公式，函数值 为一个系统状态集合 q l ，q 2 ，q m ，它包括公式p 在某个环境中成立所需要的最小 状态集合：如果此环境中缺乏此公式成立所需要的状态，则函数值为g ；包括关 于基本要求集的所有知识 2 )第二类知识集k 2 行为的前提条件t ( a c t i o n ) = ( r ig r 2 ，r m ) 其中甲( a c t i o n ) 表示一个函数，a c t i o n 为系统的一个行为标识。甲( a c t i o n ) 的 函数值为一个无变元公式集合m ，r 2 ，r m ) ，它包括所有行为a c t i o n 运行需要的前 提条件，r l r 2 ，r m 为系统中的无变元公式 3 ) 第三类知识集k 3 行为 a c t i o n = p j d q l ，p i o q i ，p n d q n a c t i o n 为个函数，其中p j 和q ，都是状态s t a t e ，p i 称为动作的前驱状态，q i 称 为动作的后驱状态( 动作结果) 。p i u q i 表示环境中的状态从p t 改变成q i 。 4 )第四类知识集k 4 赢w o n ，输l o s t 一个赢w o n 或是一个输l o s t 都是一个环境。当e = w o n 时表示是我们达到了想 要达到的环境，而e = l o s t 表示我们已到达想要避免达到的环境。 说明：我们用k 来表示知识k n