棋牌游戏及事件对策

棋牌游戏与事件对策徐心和郑新颖东北大学人工智能与机器人研究所2006年8月5日北京2006中国机器博弈学术研讨会本文动机我们所从事的机器博弈活动决不仅仅是计算机游戏，它和程序设计方法学密不可分，它是人工智能搜索原理的充分体现，这些都是我们研发的基础，不能偏离。棋牌游戏显然属于博弈论研究的范畴。但是现有的博弈论成果还无法解决棋牌游戏中的基本问题。机器博弈的辉煌成果为棋类博弈论的研究创造了极好的条件。博弈论（对策论）的一个新分支——”事件对策论”应该注意探索和创立！东北大学人工智能与机器人研究所主要内容博弈论研究的基本问题用博弈论研究棋牌游戏什么是离散事件动态系统？棋牌游戏的系统属性分析事件对策的理论框架事件对策的基本研究路线事件对策论的应用前景东北大学人工智能与机器人研究所1.博弈论研究的基本问题博弈论研究的是人与人之间利益相互制约下的策略选择的理性行为及相应结局，又称对策论，游戏论。系统的博弈论研究是从研究国际象棋开始的。冯·诺依曼通过对二人零和一类博弈游戏的分析，提出了极大极小值定理，这是博弈论产生的第一个里程碑。如今，博弈论已经广泛地运用在经济学、社会学、心理学、政治学等各类社会科学，并对进化生物学和计算科学等自然科学产生了重要的影响。这里介绍几个博弈论研究的基本问题和研究方法。东北大学人工智能与机器人研究所东北大学人工智能与机器人研究所问题的模型描述与求解-3，-3-9，0-1，-10，-9坦白沉默囚徒2囚徒1坦白沉默可以用双变量矩阵的形式进行描述囚徒困境博弈暴露了个人理性与团体理性的冲突问题。都沉默更好，但靠不住对于囚徒而言，它的“严格优势策略”——（坦白，坦白）东北大学人工智能与机器人研究所囚徒困境问题的普遍意义A,B两个公司以高低两种价格向市场竞相销售同一种产品高价垄断肯定获利颇丰,但是不稳定

竞争的结果则是低价出售，消费者获利反对垄断，打击寡头经济公共产品的供给出钱、不出钱

最终选择都不出钱军备竞赛扩军、裁军

最终选择都扩军由此可见，理论的突破可以解决一系列问题。东北大学人工智能与机器人研究所东北大学人工智能与机器人研究所问题的描述、求解与应用3.5，1.56，-0.50，00.5，5拱不拱小猪大猪拱不拱可以用双变量矩阵的形式进行描述博弈论求解的结果：

“严格优势战略组合”——（拱，不拱）股份公司的大股东和小股东

股票市场的大户与小户东北大学人工智能与机器人研究所东北大学人工智能与机器人研究所问题的分析、求解与应用两个冷饮摊贩应当如何合理地安置自己的摊位这是在连续的变量区间进行求解问题的严格优势策略组合是（1/2，1/2）甲乙双方都在海滩中点设摊相同行业的多家商店都挤在一起

电子一条街，饮食广场不同航空公司经营的飞往同一目的地的航班，常常出现起飞时间几乎相同的现象。由此可见博弈论威力巨大的指导意义。东北大学人工智能与机器人研究所东北大学人工智能与机器人研究所类似的博弈论基本问题情侣博弈的其他例子银行挤兑的成因与预防诺曼底登陆串通作弊和风险优势斗鸡博弈和航行规则………博弈论最成功的应用是在经济学领域。没有任何其它数学分支像博弈论这样为经济学研究和发展提供强有力的理论支持，也没有任何其它学科门类像经济学这样为博弈论的理论发展提供如此众多的背景模型。

东北大学人工智能与机器人研究所博弈论的基本概念参与者 自然人信息战略 最优战略（最好招数）收益是所有参与者各选定一个战略形成的战略组合的函数均衡 所有参与者的最优战略的组合每个博弈主体所选战略一定是针对其它主体所选战略的最优反应

——前提条件东北大学人工智能与机器人研究所博弈问题的分类四种不同类型的博弈：

从简单到复杂排列：完全信息静态博弈完全信息动态博弈不完全信息静态博弈不完全信息动态博弈前面所列举的大量基本问题还都属于静态博弈的范畴。东北大学人工智能与机器人研究所2.用博弈论研究棋牌游戏从博弈论的角度来讲，棋牌类游戏一般可以分为两大类：一类如象棋、围棋等游戏具有完全信息的博弈，即在博弈的每一时刻局中人完全知道自己和对手在这一时刻以前所采用的策略，也能确定这一时刻以后对手的可选择对策有哪些。另一类是如扑克和麻将等具有不完全信息的博弈。前一种博弈的求解(寻找最优策略)一般是和概率论无关的，而后一种博弈的求解是和概率论密切相关的。需要说明的是，除单人和个别少数游戏外，其他均为动态博弈。由二人参与的游戏，都可以看成是二人零和博弈。东北大学人工智能与机器人研究所博弈论研究棋牌游戏遇到的问题

博弈论基本问题棋牌类游戏策略空间很小,数以个计很大,数以十/百计展开层数很小,数以个计很大,数以十/百计状态空间十分有限天文数字传统方法可解不可解

棋牌类博弈必须寻找新的理论与求解方法

东北大学人工智能与机器人研究所3.什么是离散事件动态系统？交通调度系统（信号灯）东北大学人工智能与机器人研究所离散事件动态系统的特点离散事件动态系统（DEDS

）（DiscreteEventDynamicSystem）DEDS由离散事件驱动，是本质离散的状态与事件按照一定的运行规则相互作用，进而导致系统状态不断演化的一类动态系统。实际的DEDS大多属于人造系统的范畴，不管是系统的运行机制还是系统的研究方法，都和CVDS（ContinuousVariableDynamicSystem）有着重要的区别。

东北大学人工智能与机器人研究所CVDS与DEDS的主要区别东北大学人工智能与机器人研究所离散事件动态系统的研究方法在DEDS的研究中，常把DEDS的模型和分析方法区分为三个基本层次，即逻辑层次、代数层次和统计性能层次。DEDS的逻辑层次着眼于在逻辑时间层面上研究DEDS中时间和状态的符号序列关系；DEDS的代数层次着眼于在物理时间层次上来研究DEDS的代数特性和运动过程；DEDS的统计性能层次，着眼于在性能层面上研究随机情况下DEDS的各种平均性能及其优化。尽管这三个层次模型所面对的都是DEDS，但由于研究侧重点和描述手段不同，目前看来还不具备相互取代的前景。

东北大学人工智能与机器人研究所4.棋牌游戏的系统属性分析棋牌游戏系统主要由两部分构成，即局面和着法。着法是导致局面状态变化和进而引发新着法产生的唯一因素，是驱动棋牌游戏系统状态演变的基本因素。局面的状态都是在离散时间点上发生跃变，即仅在着法产生的瞬时局面才能发生跃变，其它时刻则保持不变，并且在状态空间中具有一种不连续的固有属性。着法的变化域和局面的状态空间都具有离散性。基于以上因素，有理由认为棋牌类游戏系统属于离散事件动态系统，着法即是触发DEDS状态变化的事件。东北大学人工智能与机器人研究所棋牌游戏的系统属性——

事件对策问题中国象棋棋局演化过程——棋谱(红方)(黑方)东北大学人工智能与机器人研究所5.事件对策的理论框架事件对策系统由以下四个要素构成：事件对策的参与者集合。事件的变化集，其中1，2，3…F代表了事件发生的顺序，为第一个发生的事件，为最后发生的事件。事件对策系统的状态空间

，

代表了系统的初始状态，

代表了系统的终止状态。参与者的收益集，其中代表每个参与者的收益，代表在不同事件序列下的不同收益。

东北大学人工智能与机器人研究所事件对策的理论框架（续）所有的事件对策系统都可以用来表示。事件对策系统分析的目的在于，如何在“策略相互制约”的局势中寻找到每个智能主体的最佳策略（事件集），使得在这一系列事件驱动下，系统达到的状态能够让每个智能主体都能获得尽可能大的盈利(或最大地减少损失)。即如何寻找到一个事件变化集，使。东北大学人工智能与机器人研究所6.事件对策的基本研究路线事件对策问题都属于动态博弈，所以博弈论中的动态博弈求解方法应该适用于事件对策系统。逆向递归法（Backwardinduction），也称倒退法(Rollbackmethod)，即从事件对策系统的最后一个决策阶段开始分析，确定该阶段局中人的策略选择；然后再确定前一阶段局中人的策略选择，一直推到起始点。这种方法对于策略空间较小，博弈步数较少的事件对策系统是适用的，但是对于大策略集或是博弈步数较多的事件对策系统，这种方法很难求出其均衡解。东北大学人工智能与机器人研究所事件对策的基本研究路线根据棋牌游戏的特点，特别受到机器博弈的启发，提出了事件动态系统的另一种求解方法——状态空间搜索算法。考虑到象棋大师以及游戏高手们可以在巨大的策略空间中选择合适的着法，一个主要因素就是因为他们在众多的棋局对弈中形成了一些定式，把大策略空间缩小到一个小的策略空间里，问题自然容易解决了。基本路线：结合人工智能的先进技术——搜索技术，在博弈树展开的过程中，裁剪掉没有价值的分支，成功地把大策略集缩减到小策略集，从而实现了求解过程。东北大学人工智能与机器人研究所象棋博弈树展开红方红方红方黑方黑方Depth1Depth3Depth4Depth2Depth0东北大学人工智能与机器人研究所蛮力搜索（Brutesearch）一般采用广度优先搜索一层层展开，一层层搜索，因为“穷尽”而没有风险，不会漏掉展开深度内的最优解。假设计算机搜索节点速率为1M/秒，中国象棋B=45

（分枝因子B=40~50）下表为在不同的给定时间内达到的搜索层数。给定时间1秒1分1小时1天1年10年100年搜索层数3.634.705.786.628.178.779.36东北大学人工智能与机器人研究所出路在哪里？由于完整的博弈树过于庞大，盲目搜索所能达到的层数十分有限，在象棋博弈中几乎没有实用价值。若想在指定时间内将搜索深度加以提高，一方面需要改进硬件与优化程序代码，提高单位时间内搜索的节点数；另一方面就需要像人类棋手一样有选择性地进行搜索，即对博弈树进行必要的裁剪（cut-off/pruning）。

东北大学人工智能与机器人研究所奠基者——香侬教授香侬(ClaudeShannon)教授早在1950年首先提出了极大-极小算法（MinimaxAlgorithm），从而奠定了计算机博弈的理论基础。

Shannon,ClaudeE.,Programmingacomputerforplayingchess[J],PhilosophicalMagazine, Vol.41:256-275,1950.东北大学人工智能与机器人研究所博弈树特点分析博弈树不同于一般的搜索树，它是由对弈双方共同产生的一种“变性”搜索树。红方为走棋方，它在偶数层的着法选择是要在其全部子节点中找到评估值最大的一个，即实行“Max搜索”。红方称为MAX方。而其应对方——黑方在奇数层的着法选择则是在其全部子节点中要找到评估值最小的一个，即实行“Min搜索”。黑方称为MIN方。东北大学人工智能与机器人研究所MAXMAXMIN1298765433213MaxMin搜索（1）由此产生最佳路径和最佳着法东北大学人工智能与机器人研究所MAXMAXMIN5298761431244MaxMin搜索（2）由此产生最佳路径和最佳着法东北大学人工智能与机器人研究所α-β剪枝搜索一种基于剪枝（

α-βcut-off）的深度优先搜索（depth-firstsearch）。将走棋方定为MAX方，因为它选择着法时总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；将应对方定为MIN方，因为它走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有钳制作用的着法。东北大学人工智能与机器人研究所MAXMAXMIN45682434α剪枝（1）由此产生最佳路径和最佳着法东北大学人工智能与机器人研究所MAXMAXMIN13682154α剪枝（2）7491224由此产生最佳路径和最佳着法东北大学人工智能与机器人研究所剪枝效果差别很大不难发现，和最佳着法关系密切什么是最佳着法？怎样找到最佳着法？（1）（2）东北大学人工智能与机器人研究所β-剪枝（1）174298MAXMINMIN77由此产生最佳路径和最佳着法东北大学人工智能与机器人研究所β-剪枝（2）835791MAXMINMIN8426由此产生最佳路径和最佳着法448东北大学人工智能与机器人研究所β剪枝和α剪枝具有同样规律剪枝效果与最佳着法的位置密切相关 与博弈树展开的顺序密切相关（1）（2）东北大学人工智能与机器人研究所需要指出的是