（计算机软件与理论专业论文）竞争领域的决策：形式化建模、支持策略及有效性验证.pdf

中山大学硕士孝位论文： 竞争领域的决燕：形式化建模、支持策喀及有效性验证 竞争领域的决策：形式化建模、支持策略及有效性验证 专业：计算机软件与理论 硕士生：陈立民 指导教师：周青副教授 摘要 竞争领域中的决策问题是人工智能领域长期研究的问题现有的决策方法 仅仅模拟了人类决策的一个方面：人类在自身熟悉的领域中往往可以根据以往的 竞争经验做出迅速、准确的反应这些方法的成功与否依赖于是否有足够数量的 竞争经验以及拥有的竞争经验是否可靠；忽略了推理性知识在决策过程中的应 用 本文对竞争领域的决策问题提出了新的解决方法，并在理论分析和逻辑基 础方面做了一部分工作：建立了竞争领域的概念模型；构造了一种具有动态语义 的形式语言，给出了该模型的形式系统；提出了一种新的决策算法，该算法充分 利用现有的竞争领域的知识来辅助决策；同时这一决策算法是基于一阶逻辑系统 的，因而具有很牢固的理论基础和很强的表达能力，所以具有很广泛的应用范围； 引入了诸如状态、系统描述、转换符、迹、支持度等基本概念；描述了知识库的 主要组成；并在此基础上给出了寻找达赢迹、达输迹、判断致胜位置、致输位置 和计算转换符支持度的算法；最终完成了新的决策算法的整体框架及其一致性定 理的证明 关键词：状态，系统描述，知识，转换符，支持度 第 l 页 ! 坐盔兰堡圭兰丝丝苎： 塞竺塑苎堕壅整：兰苎些塞蔓：童茎丝堕墨童整丝墅堡 d e c i s i o nm a k i n gi nc o m p e t i t i v ed o m a i n s ：f o r m a lm o d e l i n g ， s u p p o s i n gs t r a t e g i e sa n dv a l i d a t i o n m a j o r ：c o m p u t e rs o f t w a r ea n dt h o c r y ， m a s t e rc a n d i d a t e ：c h e nl i - m i n s u p e r v i s o r ：a s s o p r o f z h o uq i n g a b s t r a c t t h i ss c i e n t i f i cd i s s e r t a t i o np r e i 临ag e n e r a ld i s c u s s i o no fd e c i s i o nm a k i n gi n c o m p e t i t i v ed o m a i n s f i r s t l y , an e wf o r m a ll a n g u a g ew i t l ld y n a m i cs e m a n t i c si s i n t r o d u c e dt of o r m u l a t et h ee n v i r o n m e n t sw h e r ec o m p e t i t i o n sh a p p e n ab r i e f a n a l y s i s o nt h em e t h o d o l o g yf o rd e c i s i o nm a k i n gi nc o m p e t i t i v ed o m a i n si sp r e s e n t e d ；t h e na n e wd e c i s i o nm a k i n ga p p r o a c hi si n t r o d u c e d , w h i c hi sb a s e do na na n a l o g u eo ft h e m e t h o d o l o g yo fh u m a nb e i n gf o rd e c i s i o nm a k i n gi nc o m p e t i t i v ed o m a i n sa n db e b u i l tw i t h i nt h ef i r s to r d e rl o g i c s oi th a sas t r o n gl o g i c a lf o u n d a t i o na n di ss i m i l a rt o t h ew a yw em a k ed e c i s i o n si nc o m p e t i t i v ed o m a i n s i ti sb a s e do nt h ek n o w l e d g ei n o u rh a n d s , n o t t r a d i t i o n a l l yo nt h ep a s te x p e r i e n c e si nc o m p e t i t i o n s r e l a t e dn o t i o n s , s u c ha s “s y s t e md e s c r i p t i o n 。 a l t e r , t r a e k c ta 1 ，a l ed e f i n e dt of o r m a l i z et h e c o m p e t i t i v ed o m a i n s a l s on a t u r a lc o n c e p t s 、i i l ”，。l o s 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 f o rd e c i s i o nm a k i n gi nc o m p e t i t i v ed o m a i n sa r ef o r m a l l yd e f i n e d w i t ht h e s et h eb a s i cl l o t i o u st h es u p p o r t i n gd e g r e ef o re n e ha l t e r n a t i v ea v a i l a b l ei na l l e n v i r o n m e n ti s i n t r o d u c e d ，w h i c hp r o v i d e sar e a s o n a b l em e a s n r e m e n t f o ro u r d e c i s i o n s b a s e do ns u c haf o r m u l i z a t i o na ne f f e c t i v ea l g o r i t h mi sg i v e ni nas i m p l e b u ts t i l lc o m p r e h e n s i b l em a n n e r e x a m p l e si nt h i sp a p e rh e l pt h er e a d e r st o c o m p r e h e n do u rd i s c u s s i o n t h el a s tp a r ti sd e v o t e dt ot h ec o n c e r n e dv a l i d a t i o no f t h e p r o p o s a li nt h i sp a p e r k e y w o r d s ：s t a t e 、s y s t e md e s c r i p t i o n 、k n o w l e d g e 、a l t e r 、s u p p o r t i n gd e g r e e 第 1 1 页 串山大学硕士学位论文：竞争领域的决簧：形式他建筷、支持策略及有效性验证 第1 章概述 本章中我们将讨论竞争领域中的决策两透；著绘出这一类橱透镌研究现状 及其不足：亭 在现实魄蛊旋下提i 墼7 一斡基于知臻昀决镱方法的薪慰路：睫螽给 出7 本文的戗静i 2 链；最后通过绘出本文翻余部分的结构结束本章 1 1 研究背景及意义 决策是指在明确问题的基础上，为未来的行动确定目标，并在多个可供选 择的行动方案中选择一个合理方案的分析判断过程它是人们在生活、生产与科 学实践中经常需要做出选择或判断的一种思维活动，是针对某些既定的目标将多 种可能采取的策略加以比较，选定其中最有利于决策者目标实现的策略p 珂 无论日常生活中的个人，还是商业经济或者政府机构活动中的管理者，都不 可避免地要遭遇决策问题。他们经常需要在众多可供选择的方案中择取最有利于 他们目标实现的方案；而且任何个体都存在于一定的环境中，决策者在实现自身 目标的过程中离不开与周围个体的交互，他需要考虑环境中其他个体或者组织的 干扰对于他日标实现的影响。本文中，我们将现实生活中任意一个具有多个个人 或组织的领域称为竞争领域，他们交互活动以期实现各自的目标基于决策的定 义，竞争领域中的方案选择问题就是类典型的决策问题竞争领域的决策问题 大多是半结构化和非结构化的，如何对某些事物进行综合评价，并根据评价结果 制定相应策略、采取进一步的行动，使得我们的决策更合理、更科学一直是人类 思考的问题利用计算机辅助人类的决策也相应地成为计算机科学中一个十分重 要的研究领域 一个好的决策对于个人人生价值的实现、企业竞争力的提高等具有至关重要 的意义我们注意到，以往的决策方法仅仅模拟了人类决策的一个方面：人类在 自身熟悉的领域中往往可以根据以往的竞争经验做出迅速、准确的反应它们的 成功与否往往依赖于是否有足够数量的竞争经验以及拥有的竞争经验是否可靠 当竞争经验不够充分或者不够可靠时，它们给出的结果往往与好的决策有很大差 距根据这样的结果行动，不可避免地会给决策者带来严重的损失也就是说， 第 1 页 中山大学硕士学位论文：竞争颁域的决镱；形式亿建模支持簸略及有效性验证 这类决策方法仅仅着眼于对以往竞争经验的利用，而忽视了推理论性知识在决策 过程中的应用。这类推理性的知识在决策者需要对不熟悉的事物或者环境做出辨 识和反应时，更为重要。 现实竞争中领域知识要比以往的经验更为可靠，因此一个合理的决策方法应 不仅仅局限于以往竞争经验的使用，更重要的是充分利用竞争的领域知识。本文 针对竞争领域的决策问题提出了一种新的解决方法。在给出本文新的决策方法之 前，我们先介绍一下现有的决策支持工具： 1 。2 现有的决策支持工作及其不是 人类一直进行着对决策问题的思考早在二百多年以前，b f r a n l d i n 就根据 人类的决策过程往往会利用各种各样的证据来支持或者否定某一备选方案，提出 了这种综合考虑正、反例来做决策的思路【l 】这种决镱思路模拟了人类的决策过 程：现实中决策者往往是根据收集到的正饲、反例来衡量备选方案的 上世纪七十年代初，s c o t t m o r t o n 提出了决策支持系统( d e c i s i o ns u p p o r t s y s t e m ，d s s ) 的概念。d s s 主要是以模型库系统为主体，通过定量分析进行辅 助决策其模型库中的模型已经由数学模型扩大到数据处理模型、图形模型等多 种形式，可以概括为广义模型。决策支持系统的本质是将多个广义模型有机结合， 起来，对数据库中的数据进行处理而形成决策问题模型决策支持系统的辅助决 策能力从运筹学、管理科学的单模型辅助决策发展到多模型综合决策，使辅助决毒 策能力上了一个新台阶p s l 二十世纪九十年代以来，伴随着互联网的发展，决镶者所处的环境越来越复 杂。关于决策环境的庞夭数据使得决策者在海量数据中提取有助于决策分析的信 息变得困难，数据仓库( d a t aw a r e h o u s e 。d 阡9 的概念就是在这样的背景下提 出的：d 是支持管理决策过程的、面向主题的、集成的、随时间变化的持久的 数据集合嘲d 魄据决策问题的需要汇集大量的数据库，并利用一系列方法。 对它们进行重新组织和提取，通过综合和分析获取为决策服务的有用知识来辅助 决策。 o l 4 e ( o n - l i n e a n a l y t i c a l p r o c e s s i n g ，d 翻p ) 是数据仓库系统的主要应用，它 的概念最早由关系数据库之父e e c o d d 于1 9 9 3 年提出o l a p 侧重决策支持， 第 2 页 中山大学硬士学位论文；竞争领域的决燕：形式化建模、支持簟略及有效性验证 使得数据仓库的用户可以以客户，服务器方式进行复杂计算和操作的多维分析， 并且提供直观易懂的查询结果。根据o l a p 委员会的定义：o l a p 是一种软件技 术，它使分析员、经理和主管人员能够快速地、一致地和交互式地访问来获取并 理解各种可能的信息视图的数据o l a p 虽然能够利用商业指标和维度来模拟现 实世界中的一些问题。为用户提供一个关于数据仓库内数据的多维逻辑视图，使 用户可以方便地进行交互式查询、复杂分析从来帮助用户做出正确的决策；但本 质上o l a p 仅仅是数据和用户之间的信息传递系统，它提高了原本仅仅为用户提 供了简单访问的数据仓库的信息传达能力，是数据仓库的一个补充它使得用户 对数据仓库内的信息进行多维分析，提供给用户有意义的信息显示方式归根结 底，伽仅仅是通过组织数据仓库内的数据响应用户的多维查询，来帮助用户 分析和了解过去决策者从o l a p 查询的回答中推测未来的情况。然后做出决策 通过d “p 查询以了解过去预测来来的决策方法很大程度是依靠数据仓库内数 据的数量和质量 t 随着数据仓库的引入，二十世纪九十年代出现了在数据仓库上进行知识发现 的数据挖掘( d a t am i n i n g ，a d 技术1 4 0 , 4 ”数据挖掘一个知识发现的过程， 它能以一种出人意料的特殊方式帮助决策者理解数据的本质，从原始数据中挖掘 出原本不知道其存在的一些模式和倾向p 】数据挖掘是一个从大量的数据中通过 特定的算法发现人们痦兴趣的潜在有价值知识的过程。这类信息往往仅仅是以关 系或者模式的方式出现譬如超市中有些商品往往会放在彼此靠近的地方，这可 能并不是巧合，而是该超市使用数据挖掘技术发现了这些商品之间的关系 数据挖掘通过在大量的历史数据中发现关系和模式来预测未来以辅助决策， 但它是简单而低效的，特别是考虑到数据挖掘技术只有在存在大量数据可用的情 况下，才会有好的结果。另一要点是数据质量的问题：挖掘“脏”的数据会得到 不准确的发现结果这类方法仅仅是依赖于对历史数据的统计，缺乏利用知识对 现实环境的分析 竞争领域的决策问题在经形式化建模后，往往可以在计算机的帮助下通过进 行盲目搜索或者利用以往经验作为辅助的启发式搜索来解决前者最为成功的饲 子是腿m 。d e e pb l u e ”击败棋王勋驴珊瑚世纪之战f 4 用；而后者则广泛用于各 种基于规则的专家系统中竞争领域的决策技术一直出于不断地发展中，人工智 能技术在d 镕中的应用推动了智能水平的不断提高，机器学习、神经网络、模糊 筻 3 页 中山大学硕士学位论文：竞争领域的决策：形式化建模，支持策略及有效性验证 处理等技术的应用与研究使d s s 向着智能决策支持系统( i n t e l l i g e n c ed e c i s i o n s u p p o r t s y s t e m ，i d s s ) 发展。i d s s i 既可以通过人工智能技术以知识推理形式解决 定性问题的分析，又可以通过综合统计和运筹学解决定量问题的分析通过定性 分析与定量分析的有机结合，提高整个决策支持系统的应用范围和决策水平目 前。应用于决策的人工智能技术主要分为以下几类； i ) 遗传算法( g e n e t i ca l g o r i t h m ) 是由z 正b 砌蒯教授于1 9 7 5 年首先提出的 一类借鉴生物界的进化规律( 适者生存，优胜劣汰遗传机制) 演化而来的随机化 搜索方法它通过选择、交叉和变异等简单的反复操作模拟生物进化过程在每 次反复中，每个模型通过从前一代的模型继承来的特性和其他的模型竞争，只有 最好的预测模型能够保留下来。g a s 的效果很多程度上依赖于能否选择一个合适 的适应函数( f i t n e s s # n e t i o n ) 来指导进化的方向传统的g a s 中用来指导进化方 向的适应函数是固定的，这其实是假定了竞争过程中竞争环境是静止不变的，很 明显这与现实情况不符；而且在一个复杂系统中，也很难选定一个简单而公平的 适应函数基于以上原因，c h u e n - t s a i 砌柳m i n g - d a 讳0 6 】在传统的6 m 中引入动 态的适应函数，当伴随着环境的改变，适应函数不能提供一个满意的进化方向时， 系统就利用过去竞争阶段的经验修改之，使得它具有自适应性实验表明，与传 统的g a s 相比，该方法能提供更好的搜索结果 2 ) 神经网络也有一定的生物学基础，它模拟了人脑的信息处理过程，其结 构由被称为节点的基本处理单元及其连接方式决定神经网络在输入节点接收变 量值或者预测值，神经网络中可以有若干个内部层对预测值进行操作，从一个节 点到另一个节点，直到最终结果在输出结点上表示出来神经网络可以通过根据 学习样本调整节点间连接的强度和权，以增加新的输入下的输出的准确性在数 据是不定形的并且没有任何明显模式的情况下，这类算法很有效【3 】在文献【7 】 中，a l e x a n d r am a r k ，b e r n h a r d s e n d h o f i 王k bw e r s i n g j 重用了进化和学习的思路 来解决即时竞争游戏中的决策问题。在他们给出的决策框架中，利用神经网络表 示竞争对策，使用遗传算法优化网络以得到好的竞争策略。此外，还加入了学习 机制实现根据当前对手的行为调整自身的决策。这样就使得我们可以使用遗传算 法得到一些适合学习的可能决策，然后通过学习过程训练它们以预测对手的可能 行为，得到有利的决策。他们将这个决策系统用于在竞争环境中：通过学习对手 以往的策略和环境的变化以做出最优选择实验表明，该系统在即时游戏中的表 第4页 中山大学颐士学位论文：竞争领域的决簧：形式化建模、主持策略及有效性验证 现比其他决策系统优秀很多 3 ) 机器学习利用以往的竞争经验来预测未知的实例，改进决策质量这类 决策方法模拟了现实生活中人类决策过程所具有的学习进化特性h u l l e r m e i e r , f s 】给出了一种基于案例的决策工具该工具存储关于过去遇到的决策问题及其 解决方案，当遇到新的问题时，某可能的备选方案将通过类似环境下该行为的结 果进行衡量更为常见的是通过大量存储的竞争经验提取出模式( p a t t e r n ) ，以 此作为竞争决策的依据s t e v e n 暇比z 矗在文献【9 忡使用了基于模式的决策方法 他以国际象棋为倒，在游戏中某个特定的对手通常会对特定棋局会做出相似的反 应，他将特定棋局作为“p a t _ t e m ”，并将之连同相应的反应存入计算机中，然后在 竞争中对识别出的 p a l t e r d 做出相应的对策( 做出反应动作或是预测对手将采取 的行为) 这种决策方法，大大降低了游戏过程中决策树的搜索 k a s t e n , e p 正m c k i n l e y , p 置则提出了一个用于自主计算系统( a u t o n o m i c c o m p u t i n gs y s t e m a ) 中决策问题的模式分类器以支持联机、增量学习f 1 0 1 该分 类器通过将相似的学习用例划分为一个被称为“a e n s i t i v i t y a p h e r e ”的聚类集合来 构建层次性的数据结构；实验显示，这种结构能提高增量学习和模式分类的效率 w i c l w a m a s i n g h el k a l a h a k o o n , 上d 在人类行为和脑研究的启发下，提出 了一个具有学习和进亿能力的智能体( a g e n t ) 决策概念框架l l l l 它使用进化入 工神经网络来模拟人的决策模型，各组成成分之间相互合作以使得智能体对其所 处的动态环境具有认知、学习和反应的能力，可以以一种类似人类决策的方式做 出决策 此外，模糊逻辑、模糊集和随机过程等工具也用到了决策支持中来，它们提 供了一种对备选方案有利性的量化工具rs a b h e r w a l 兄k i n g t 形式化了一个基 于证据细铡棚够腑的决策方j 去1 1 2 1 。它可以根据带有不同权值的证据计算出 可接受的最有利于我们获利的备选方案它与目前盛行的基于概率逻辑的定量分 析方法是一致的 尽管以上的人工智能方法在决镶支持系统中取得了一定程度的满意成果，但 它们仅仅使用以往的经验作为启发信息；缺乏对推理性知识的应用这类方法的 成功很大程度上是模拟了以下事实：人类对于熟悉的事物或者环境往往能够做出 准确的、迅速的辨识和反映i 期这是为什么呢? 很明显，人类能对熟悉的事物或 第 5 页 中山大学硕士学位论文：竞争领域的决策：形式化建模、支持策略及有效性验证 者环境做出准确迅速的辨识和反应得益于他们以往与外界的交互中获得了大量 的经验，从而提高了其大脑对类似信息的处理能力。 那么当人类面对不熟悉，乃至完全陌生的事物或者环境时，他们又是怎样做 决策的呢? 在这种情况下，依靠主观想法或者猜测，绝不是明智的选择。现实中，我们 经常会遇到各种各样的决策问题。譬如我们如何解决面临的一个经济难题或者如 何褥到自己向往的工作。在这样的问题解决或者目标实现过程中，与我们工作生 活在一起的其他人的行为往往会影响到我们最终的成功：因此，我们不得不考虑 竟争过程中其他人的行为对我们决策的影响在这些现实的决策问题中，我们并 非仅仅依靠以往的竞争经验，我们往往是利用自身掌握的推理性知识来辅助我们 的决策：首先认清当前的环境，然后找到所有的可能选择，并综合竞争领域中存 在的其他个人或者组织的后继反应，分析比较备选方案的有利性，最终做出最有 利于我们目标实现的选择可以说现实生活中，我们除去经验性的知识外，往 往更需要利用有关的领域知识来分析得到备选方案，并对它们进行综合评判，最 终做出合理、有利的选择。 根据以上分析，我们可以看到，以往的决策方法的成功在于它们成功地模拟 了人类决策的一个方面：在自身熟悉的领域中根据以往的竞争经验做出反应也 就是说，这类决策方法仅仅着眼予对以往竞争经验的利用，而忽视了推理论性知 识在决策过程中的应用，这类知识当竞争参与者需要在不熟悉的领域中做决策时 更为重要。以往的决策方法的成功与否往往依赖于是否有足够数量的竞争经验以 及拥有的竞争经验是否可靠。! 绩争经验不够充分或者不够可靠时，它们给出的 结果往往与好的决策有很大差距根据这样的结果行动，往往会给决策者带来严 重的损失 现实竞争中领域知识要比以往的经验更为可靠，因此一个合理的决策方法 应不仅仅局限于以往竞争经验的使用，更重要的是充分利用竞争的领域知识采 用新的决镱支持信息知识来辅助决策是必要的，也是自然的下一小节将简 要介绍本文所提出的新决策支持策略的思路 第 6 页 中出大学硬士学位论文： 竞争领域的决策：形式亿建模、支持镱喀及有效性验证 1 3 基于知识的决策方法的思路 现实生活给科学发展以最直接的推动力我们首先考虑一下现实生括中的 决策问题是怎样解决的如前所述，现实的决策中，决策者并非仅仅依靠以往的 竞争经验，更多的依靠更为可靠的推理性知识，结合对当前竞争环境的认识，分 析备选方案的有利性大小做出选择的。譬如：通过竞争环境的知识确定出某具体 环境下的可能选择、通过有关行为的知识计算某行为的结果环境以及通过有关我 们目标的知识指导我们决策的方向在现实的竞争过程中，尽管以往的经验性知 识会给我们的竞争决策一定的帮助，但我们更多的是依赖竞争的领域知识 一个竞争决策通常是一个使用“如果则”的分析过程： 1 ) 尽可能全面地收集信息，得到比较完备的领域知识，并找到当前环境下 的所有可能选择j 2 ) 对予每一种可能的选择，利甩知识分析其行为后果； 3 ) 分析对手的可能行为及其行为后果； 4 ) 根据2 ) 、3 ) 的结果可以得到我们每一可能选择行为的优势与劣势，并 选择最有利于我们的行为 我们参与竞争的目的是改变自身所处的环境以最大化我们的利益因此， 我们应该首先有关于我们目标的知识，环境所具有的莱一些性质可以作为我们的 目标，我们根据这类知识明确定义了什么是。赢的环境”和“输的环境”参与 竞争的各个个体在各自目标的指引和一定规则的约束下，积极采取措旌，实现环 境之间的转变，以期到达赢，同时尽可能避免输有两类环境值得我们关注： 1 赢的环境或不管其他竞争参与个体采取什么样的行为，我们都可以 在新的环境下选择某一行为，来保证我们获得最终的胜利这样的 环境我们称之为致胜环境，而这样的环境下保证我们最终到达赢的 环境的行为则被称为致胜行为； 2 输的环境或不管我们采取什么样的行为，其他竞争参与个体都存在 可能的行为使得我们最终到达输的环境：我们称这类环境为致输环 境，而我们使得当前环境进入致输环境的行为则被称为自毁行为； 我们利用掌握的知识计算当前竞争环境下的所有可能行为和各个可能选择 行为将生成的后继环境；当竞争的当前环境是一个赢或者输的环境时，我们认为 第 7 页 中山大学硕士学位论文：竞争领域的决鲠：形式纯建模、支持策培及有效桎验证 竞争已经没有必要进行下去，不需要做决策；否则，通过判断当前环境是否是一 个致胜环境而判断该环境下有无保证我们最终获胜的致胜彳亍为；在该环境不是一 个致胜环境、不存在致胜行为时，我们首先排除当前环境下的自毁行为，然后在 当前环境的所有可选择行为中选择最有利于我们获胜的行为。当某一环境下的可 选择行为都是自毁行为时，我们将随机选择其中之一作为这一阶段的决策，这种 随机性是因为我们暂时不考虑其他竞争参与个体的行为习惯，他们使我们的局势 得到转机的失误是随机的 到这里，我们遇刭了一个闯题：什么是“优势”? 舒么又是“劣势”呢? 这些日常生活中的自然概念并没有明确的定义。很自然的想法是：竞争领域中可 能行为的“优势”应该是该行为对于提高我们获胜可能性的一种度量，而“劣势” 则与之相反，量化了某可能行为在一定的竞争环境下对我们最终输掉竞争的可能 性。本文中，我们根据这样的思路精确定义了在某环境下可能行为的优势和劣势， 并在此基础上量化7 某环境下的可选择行为的有利性 本文提出的竞争领域中基于知识的决策方法( k ，l d w l e d g e - b a s e d d e c i s i o n - m a k i n g m e t h o d i nc o m p e t i t i v e d o m a i n s ，k d m c d ) 是对以上现实中决策 过程的模拟。利用计算机来帮助用户决策的方法充分利用竞争的领域知识来衡量 竞争过程中的可能性，从而使得各可能行为的有利性得到衡量，最终褥到最大化 我们利益的方案 将现实中的问题空间映射到机器内部的逻辑空间进而解决问题是建立形式 系统的目的本文所提出的基于知识的决策方法所要做的就是符号化现实中的竞 争过程，通过语法层次的操作来指导现实中的竞争；并通过一致性定理的证明保 证本文符号化的过程没有错误l t 4 本文的创新点 本文的创新点主要表现在以下三个方面： i 高度概括的竞争领域的概念模型，这种高度的抽象性带来的应用的 广泛，而不是仅仅局限于对抗性游戏； 2 使用了一种具有动态语义的形式语言完成了对竞争环境的描述，具 有动态可变语义的形式语言在以往的工作中是没有的； 第 8 页 中山大学硬士学位论文： 竞争领域的决簿：形式亿建筷，支持荒喀及有效性验证 3 在语法语义的基础上，精确严格地定义了。优势”、“劣势”等自然 语言中的概念，以及致胜位置、致输位置、转换符( 它是竞争中的 行为的语法对应物) 的支持度等相关的概念，通过这些概念，可以 很容易地量化该转换符所对应的行为的有利性，进而保证了我们决 策方法的正确 本文给出的决策方法是基于现有知识和当前环境信息作出决策这种决策方 法更为合理：它更加接近人类思维，所作出的决策与当前的竞争领域和竞争者密 切相关k d m c d 中知识的引入使我们可以针对具体的竞争领域具体分析，者再 结合以往的竞争经验，则可以从两个角度来考虑决策闯题，从而，k d m c d 给出 的决策结果更加合理可靠 1 5 本文的结构 本文剩余部分的结构如下； 第二章讨论了现实生活中的竞争，精确定义了竞争参与者、环境、竞争 对手、行为以及输赢等基本概念，给出了竞争领域的概念模型； 第三章引入了一种具有动态语义的形式语言，并在第二章的基础上，以 第二章的概念模型为语义，给出了竞争领域的形式系统； 第四章进一步定义了语法、语义上的概念，明确了自然语言中的“优势久 。劣势”；并在语法、语义基础上建立了一系列的形式推理规则，完成 了圈聊的基本构建； 第五章给出并证明了k d m c d 的一致性定理，然后是九富模 ( t i c - t a c - t o e ) 的l b t t ( a l l e g r oc l s o ) 实验； 第六章给出了一些有待继续探讨的开放性问题，提出了本文的不足之 处，并介绍了下一步的工作方向 第 9 页 中山大学硕士学位论文：竞争领域的决蹙：形式化建模、支持策略及有效性验证 第2 章竞争领域的概念模型 本章串t 我讯将进一步罚论现实竞争领域中酌决策两题；并给出它基于特 征f e 醵l 他b a s e d ) 的概念模型。 任何竞争均在一定的环境中进行。我们采用一种基于特征的方法对现实竞争 过程中的环境建模。当我们要描述一个竞争环境时，我们不愿也没有必要去做不 相关的描述，假定我们选定n 类特征来区分现实竞争中的环境每一类特征的一 个具体值描述了某一具体环境某一方面的性质，而类型齐全的力个特征值则描述 了竞争过程中一个具体的环境。我们定义这些基本概念如下： 定义2 - l ：( 参与者) 竞争过程中出现的某一组织或者个人是一个参与者 定义2 - 2 ：( 竞争对手) 竞争对手是竞争过程中除我们之外的参与者 定义2 3 ：( 特征类型及特征) 特征类型是现实中某一竞争场景中某一方面属 性的所有可能取值构成的集合我们假定有月类特征类型：d 。，d 2 ，d 。； 并称d ；的一个元素是一个i 类特征。 定义2 - 4 ：( 环境) 一个环境是满足以下条件的特征的集合：对于每一类的特 征类型d i ，该集合中存在唯一的一个i 类特征f i d ； 构成一个环境的特征共同描述并区分现实竞争中出现的各个环境。 我们用殴，表示某一竞争过程中所有可能环境的集合 在生活中的绝大多数竞争中，我们所要面对的竞争对手可能不止一个本 文不考虑他们之间的相互作用对我们目标实现的影响，而假设所有的竞争对手 是一个竞争对手团队这一假设是非本质的：当需要打破这一假设，考虑不同竞 争对手之间的相互影响时，本文所阐述的解决方案同样可以给人启发 竞争中，参与者的目标是通过自己的行为改变环境以最大化自己的利益。因 此，环境所具有的某一些性质可以作为我们的目标这些性质可能是我们对环境 某些方面特征的期待，也可能是对我们竭力想避免的环境中某些特征所满足的关 系的陈述。在规划“h o w t o g o ”之前，明确“w h e r e t o g o ”是必须的基于这种 现实需要我们做如下定义： 定义2 - 5 ：( 赢的环境和输的环境) 赢的环境是我们所期望的环境；而输的环 第1 0 页 中山大学硬士学位论文：竞争领域的决策：形式化建模、支持燕略厦有效性验证 境则是我们竭力要避免的环境 倒2 1 ：在国际象棋中，某一“我们某一子可以将死对方王”的棋盘格局就 是一个赢的环境；而“我们的王被对方将死”的棋局则是输的环境 参与者通过实施各自的决策改变着共居的环境，我们首先定义这类改变环境 的操作我们称之为行为： 定义2 - 6 ( 行为) 对于某一环境e ，参与者的某一行为a c t 往往会引发占内 一系列的特征改变，使得竞争环境转变成为新的环境e 此环境转换可以表示为： e ，a c t “一 e t 我们用a c t , 铅t 表示某一竞争过程中所有可能行为的集合 定义2 - 7 ：( 直接后继) 如果某一行为a c t 在环境e 内发生后新的竞争环境为 e - ，即e i , a _ c 4 ，则我们称e l 为e 的直接后继，表示为：e = i s e ( a e t ，e ) ，或简记 l 为e = i s e ( e ) 在各自目标的指引下，竞争的参与者在一定的规则约束下积极采取措旌，实 现环境之间的转变，以期到达赢的环境，同时尽可能避免输的环境 通过观察现实生活中的竞争，我们可以得到一个很明显的结论：行为的发生 需要一定的前提条件，在某一环境下，只有当某一行为的前提条件得到满足时， 该行为才可以被竞争中的参与耆用于实现环境的改变我们定义如下： ? “ 定义2 - 8 ：( 行为的前提条件) 假设a 是一个关于环境特征的陈述，如果某 行为a c t 的执行需要当时所处的环境下a 真，则a 是a c t 的个前提条件这种 前提条件关系可以表示为：a c ti fa 对于a c t 而言，所有这类要求的集合构成 它的前提条件集：c o n d ( a c t ) = a ta c t i f a ) 前提条件是行为的执行对环境的要求，若某行为的前提条件为t r u e ，则它 可以在任意环境下执行对于某一行为而言，其前提条件可能会有不止一个，但 它的执行只需要某一前提条件的满足 定义7 - 9 ；( 合理行为) 行为a c t 在环境e 下是合理的，当且仅当存在 a e c o n d ( a c t ) 并且a 在e 下真 例2 - 2 ：我们继续使用国际象棋作为举例背景：某一个棋局下，棋手只能在 比赛规则的约束下移动自己的棋子来改变棋盘格局 第 l l 页 中山大学硬士学位论文：竞争领域的决镶：形式纯建摸、支持燕喀及有效性验证 接下来，我们讨论的主角将是环境。我们首先定义某一环境的合理行为集。 很自然地，它将由该环境下所有的合理行为构成。 定义2 1 0 ：( 环境的合理行为集) 环境e 的合理行为集( r e a s o n a b l ea c t i o ns e t ) 可以定义为：r a s o ! ) = a c t ：t ea c t s e t 并且j a c o n d ( a c t ) ，a 在e 内真) 。 某一环境下，参与者执行某一合理行为会引起环境的改变。现实生活中，我 们需要预测某一环境中某合理行为发生后竞争所进入的新环境。为方便这类计 算，我们通过环境在某行为作用前后所发生的特征改变来表示该行为。我们下面 将精确定义行为造成的环境转换： 定义2 - 1 1 ：( 环境的转换) 环境转换是一个函效：t ：a c t s e t e s e t - - * e s e t 。 它将一竞争环境和该环境内的一个合理行为映射刭一个新的环境： t ( e ，a c t ) = e 如果訾； 其中e = f l ，f 2 ，f l i f i ed i ，f o r i = l ，2 ，n ) ，行为a c t 使得e 中的特征发 生了如下改变：l 改变为同类型的特征l 、f _ ，改变为同类型的特征f 。，、 改变为同类型的特征f 、；而e 中 f m ，f 。，k 以外的特征均未改变，则我 们表示行为a c t 为： 毛，t ，f m 。 舞 f ，f | 。，f ) ，且孔t 在e 中发生后所 得到的新环境e | 可以透过以下公式计算：e i 镪 f m ，f i ，毛。u f 。，f 。：，f 。 ；其中， f m ，f i ：，l 。) e ，且对任意i m l ，m 2 ，m k ) ： f i f i ，f i ，f i d i 利用以上新引进的定义，可以将现实生活中的竞争领域描述为如下的六元 组： 定义2 1 2 ：( 竞争领域) 竞争领域可以表示为如下的六元组： c o m p = ( p s e t , f _ s e t ，a c t s e t , e w ，g o a t , ，g o a l ) 其中： 1 p & t ：竞争过程中参与者的集合，本文假定它有2 个元素：我方 和一个竞争对手( 团队) ； 2 e s e t ：竞争过程中所有可能环境的集合； 第 1 2 页 3 a e t s e t ：竞争过程中所有可能的行为的集合# 4 e 0 ：竞争的初始环境： s 。g 白口t ：所有的赢的环境构成的集合： 6 g o a l ：所有的输的环境构成的集合 将本章中竞争领域的基于特征的概念模型以及某一具体竞争领域的知识形 式化为一种形式语言使得该领域的决策问题通过计算机来解决成为可能这将是 下一章的任务 第1 3 页 中山大学硕士学位论文：竞争领域的决镱：形式化建模、支持策略及有效性验证 第3 章竞争领域的形式系统 本章中。我 ) 将翻甬一阶谓词演算描述竞争领域：并以第二章中竞争领域的 概念模型为语义给出竞争领域的形式系统。 3 1 语言符号表 我们构造形式语言一一动态环境描述语言也咖册缸e m i 加m n e n t d e s c r i p t i o n l a n g u a g e ，d e d l ) 来描述竞争领域；d e d l 使用以下符号： 1 2 个特殊常元构成的集合p n a m e s e t ： p l a y e r l ，p l a y e r 2 ) ，其中的元素 为竞争中参与者的名字，根据第二章中的假定，竞争中有我们和一个 竞争对手；p n a m e s e t 与现实竞争的参与者集p s e t 之间存在一一映 射，每一个竞争参与者都通过p n a m e s e t 中某一个常元标识； 2 个特殊的变元：v a r t u m ，它的取值空间为p n a m e s e = t ，用以标识当 前拥有决策权的参与者； 3 假设竞争环境具有栉类特征( d l ，d 2 ，d 。) ，对应于每一特征类 型d 。，都有一定数目的常元构成的符号集合c j ( 称为i 型保留常元 集) ：且存在双射f i ：c i 哼d i ( i = i 2 ，n ) 将c ；中的常元映射为相 应特征类型d ：中的一个具体特征； 4 一类特殊的操作符号集o p s e t ：盯，尼，等( 或者包含数字下标) 希腊 字母； 5 竹类变元集k ，：巧中的变元的取值空间为c t ； 6 两类谓词符号：一类是对应于一类特征类型的描述谓词集 p l , p ：，p 。) ( 其中p i 称为i 型描述谓词符号) ，另一类是描述谓词集 以外的普通谓词符号集； 7 另一个特殊的谓词符号：= ； 8 逻辑连接符：、 ，v ，j ，付； 第1 4 页 中山大学硕士学位论文：竞争领域的决策：形式化建模、支持策略及有效性验证 9 标点符号：( ) ，； l o 量词符号：3 , v ； 1 1 条件符号：仁； 1 2 替换符号：j 注：d e d l 没有使用通常的函数符号，这是因为本文中作为d e d l 语义论 域的竞争领域是封闭的，并且我们所具有的关于个体的属性知识能够帮助我们确 定出每一个个体，因而可以给它分配一个常元作为名字 3 2 语法定义及语义映射 项、文字、原子公式、合式公式、以及变量在公式中的自由出现、约束出现 的定义与经典逻辑系统大致相同：唯一的区别在于函数符号的缺乏使得d e d l 中的项仅包含常元和变元；一个语句( s e m e n c e ) 是一个无自由变元的公式；接 下来，我们给出d e d l 特有的一些语法定义， 定义3 - 1 ：( 竞争参与者名) p n a m e s e t 中的一个常元是一个竞争参与者名 定义3 - 2 - ( 状态) 一个i 型状态是一个由i 型谓词符号构成的形如p i ( a i ) 的闭 公式，其中a je c i 由以上定义可以看出，i 型状态只能由i 型谓词符p i 和保留常元集c i 中元素 构成：所有i 型状态的集合为 p i ( x ) i x e c i ) ，我们标记它为s s e t i 定义3 - 3 s ( 系统描述) 一个系统描述是满足以下条件的一系列状态的集合： 对于每一i 型的状态集合s s e t i ，该集合中都存在唯一的i 型状态p i ( a i ) s s e t i ， i = l ，2 ，n 我们假设系统描述是一致的；且用s d 。m 表示d e d l 中所有可能的系统描 述一个系统描述无遗漏地包含了各个类型状态集合的一个状态，它们分别对应 于现实竞争环境中相应类型的特征，描述的是竞争环境在一定时间内所有类型的 特征取值一个系统描述对应于竞争领域的概念模型中的一个环境 定义3 - 4 t ( 系统描述的语义) 系统描述的语义映射是一个s d m 到现实竞 第l ，页 中山大学硕士学位论文：竞争领域的决簟：形式化建模、支持策略及有效性验证 争环境集e s e t 的双射：f s d ：s d 。l 斗e s e t ；某解释肘下系统描述 s d = p l ( a 。) ，p 2 ( a 2 ) ，p 。( a 。) ) 的语 义 环境 是 ： m ( s d ) = f s d ( s d ，= m ( q ) ，a ( a ：) ， ( d 。) ；在该解释中的某环境e 下；s d 为 真当且仅当m ( s d ) = e ，即：肘 。s d 当且仅当m ( s d ) = e 定义3 - 5 ：( 状态的语义) 假设p i ( a i ) 为一个i 型状态、