计算机博弈的基本原理

弈棋过程分析

为了深入探讨计算机博弈的原理与方法学问题，有必要分析二人（设为甲方——先手、 乙方——后手）对弈的演化过程，建立相应的数学模型。图 2-1 给出了博弈状态演化过程图 [5]。图中表明棋局状态是在着法算子作用下进行演化的，其对应的状态转移方程可以写成

式中 S0为棋局的初始局面，qn+1为第 n+1 步的着法算子，而 Sn+1 为下完第 n+1 步后的棋局。 于是，不难写出

弈棋的过程是双方轮流给出着法，使棋局向着本方有利的方向发展，直至最后的胜利。 弈棋的核心是如何给出着法，这涉及一个复杂的思维过程。简单说来就是：用着法推演局面， 从有利的局面中选择当前的着法。显然准确地评估推演出来的局面是选手棋力的重要体现。

如何让计算机下棋

为了让计算机能够下棋，首要的任务就是通过恰当的数据结构使棋类要素数字化，这里 包括：棋盘、棋子、棋规（着法规则，胜负规则）等。

为了用着法推演局面和展开博弈树，就需要具有着法生成器，用以生成该局面下全部（或 部分感兴趣）的着法。图 2-2 给出了博弈者思维过程的机器实现过程框图。从而可以产生如图 2-3 所示的博弈树（Game Tree）。节点为局面，树枝为着法，根节点为当前局面，叶节点 为展开相应深度的终点局面。双方轮流出手，偶数层为本方（方块表示），奇数层为对方（圆 圈表示）。如果叶节点还不是能够给出胜-负-和的最终局面，则要对叶节点进行评估 （Evaluation）。以便从有利局面选择当前着法。这便是博弈搜索的职能。 搜索引擎根据极大-极小的搜索算法，找到对于本方而言最好的结局。然后找到最佳路 径（Principal Variation – 主要变例），从而找到相应的根着法（Root Move），即是本轮搜索 所要给出的当前着法[5]。不难看出，评估和搜索将成为博弈软件的重要部分。

如果在叶子节点不能给出胜-负-和的结果，那“有利局面”的选择就只能依靠局面的评 估了。通常设计的评估函数需要考虑如下不同类型的知识，并通过量化后加权组合而成。

子力(Material)

在象棋和国际象棋中，它是所有子力价值的和；在围棋或黑白棋中，通常计算双方棋盘 上棋子的数量。但是黑白棋有个有趣的反例：棋局只由最后的子数决定，而在中局根据子力 来评价却是很差的思路，因为好的局势下子数通常很少。其他像五子棋一样的游戏，子力是 没有作用的，因为局面好坏仅仅取决于棋子在棋盘上的相互位置，看它是否能够发挥作用。

位置(Position)

棋子落于不同的棋位其作用可能差别很大。象棋中的车占中路，兵过河，马卧槽都是具 有威胁性的位置。相反如果马窝心，兵下底又都不甚理想。围棋中的星位也是兵家必争之地。 于是不同的位置给予不同的分值，以表示不同的价值。

空间(Space)

在某些棋类中，棋盘可以分为本方控制的区域和对方控制的区域，以及有争议的区域。 在围棋中，这个思想被充分体现。而包括象棋在内的一些棋类也具有这种概念，本方的区域 包括一些棋位，它被本方的棋子攻击或保护，而不被对方棋子攻击或保护。在黑白棋中，如 果一块相连的棋子占据一个角，那么这些棋子就吃不掉了，成为该方的领地。空间的评价就 是简单地把这些区域加起来，如果所含棋位的重要程度存在差别，那就在区域的计算上增加 棋位重要性的因素。 2.4.4 机动(Mobility) 各个棋子的机动性如何，关系到棋子可行着法 的多少。如象棋中的马是可以“马踏八方”的，但 是贴边或被憋腿，其活动余地大减。显然机动性越 好，可行着法越多，选择有利局势的机会也越多。

拍节(Tempo)

某些情况下起决定作用的不是着法的多少，而 是出招的拍节和数量的奇偶性等。以一数学游戏为 例：有两堆石子，双方轮流从石堆中拿去几颗，每 次只能从一堆石子中拿走至少一颗石子，拿完最后 一堆者获胜。这个游戏的诀窍是：始终让对方面临 两堆石子一样多的窘境。面向这样的问题时，先手 方只要头一步让两堆石子数目一样多就可以了。然 图 2-6 一个受制于节拍的象棋棋局 计算机博弈教程 计算机博弈原理与方法学概述 - 15 - 后对手从某一堆取走几颗，先手方便在另一堆取走同样数量的石子。在黑白棋和象棋中都会 遇到这样的问题。而对于一字棋和点格棋这招则是制胜的法宝。 图 2-6 给出了一个中国象棋的排局，也包括类似奇偶性的主动权问题。在这个局面中， 双方的兵(卒)都不能离开原位，否则对方平帅(将)即可造成铁门栓杀。双方的中炮不能离开 中线，而三七路炮也不能离开该线，否则对方就会有闷宫杀。这样的棋型只能有一种取胜方 法——用自己的两个炮顶住对方的两个炮，迫使对方让开兵(卒)或三七路炮。此时红方取胜 的关键一步就是炮七进四，使双方的两个炮间等距。以后的着法则是始终保持等距。

威胁(Threat)

威胁的思想是“步步紧逼”，或要取胜，或要吃子，使对方仅有招架之功，而无还手之 力。在五子棋、六子棋中常常采用基于威胁的搜索。以五子棋为例，可通过不断地摆出“活 3”、“冲 4”的棋型的方法，将对方逼到防无可防的境地，从而取胜。

形状(Shape)

形状的好坏对于局面的影响一般是长远的，在浅层的搜索中不易发现。在象棋中，对手 的空头跑，单车栓车马，就都是不好的形状，最终使本方处于被动的局面。形状对于连珠棋 一类通过“摆成形状”而决定胜负的就更是评估的焦点。

图案(Motif)

一些常见的具有鲜明特点的图案，蕴涵着特殊的意义。许多图案在围棋中称之为模式， 如 3×3 上下文模式，通过对大量高手对局中的模式提取和出现频率的统计，构造模式库， 便可以由此提供下一手落子的最佳位置。

棋局性能评估

从表面上看，棋局评估的越全面、越准确，棋力性能就会越高。其实不然。一般说来， 棋力性能 = 知识×速度，时间作为约束条件。评估中考虑的问题越多、越细致，耗费的时 间则越多，必然影响到单位时间内搜索节点的数目，影响到搜索的速度和深度。 在博弈软件的设计中通常存在“重知识”（评估）和“重速度”（搜索深度）两种倾向， 并且都有成功的范例。当然能够权衡利弊，将两者有机结合则是最为理想的方案。这也是目前共同努力的方向。

计算机博弈原理与方法学既涉及到博弈论（对策论）、搜索原理等理论内容，又更多地涉及到数据结构、软件工程、程序设计方法学等方面的知识。计算机博弈属于计算机科学与 应用学科的研究方向之一，又是人工智能领域的重要研究方向，应该属于智能科学与技术学科的一个分支。虽然这一方向的研究工作取得了举世瞩目的成果，但是相关的理论与应用技 术的归纳与提升还有很多工作要做。这也是把计算机博弈技术应用到其它领域所不可或缺的基础性工作。

(一)竞赛队及分组规则1．每个学校同一棋种的参赛队不得超过3 个(二打一扑克牌只能有一个队)，且必须用本校自己独立开发的程序参赛，并提供程序设计文档。2．各个项目将根据报名队数的多少采取双循环赛或分组双循环赛(分先、后手各赛一场)，种子队根据历届比赛成绩由组委会确定。现场抽签分组，各个小组前两名再进行双循环赛，小组成绩不带入决赛阶段。3．分组指导思想为尽量使得强队不要过于集中，使各队都有更好的出线... 本文主要讲解如何基于C++和MFC类库实现 计算机 博弈 比赛中常用的程序界面，为了方便讲解，如图所示，采用一个假想的棋种-肆棋作为例子，规则非常简单：4*4的棋盘上有黑白双方共8枚棋子，每方有4个棋子放置在底线，默认黑方先行，交替行棋，每次走一个棋子，每个棋子只可以选择向前、向左上、向右上前进，遇到对方棋子可以吃掉，不可以连吃。双方轮流行棋至无棋可走为终局，棋子多者为胜方，棋子相同为和... 一、前言人机 博弈 是人工智能的重要分支，人们在这一领域探索的过程中产生了大量的研究成果，而极小化极大算法(minimax)是其中最基础的算法，它由Shannon在1950年正式提出。Alpha-beta剪枝的本质就是一种基于极小化极大算法的改进方法。Knuth等人在1975年优化了算法，提出了负极大值(negamax)概念，这一概念的原理本质上与极小化极大值算法并无不同，但是却不需要系统区分取极大值者和极小值者，使得算法更加统一。 前言本书讨论 计算机 博弈 程序(软件)的分析、设计、实现方法和过程。对 计算机 博弈 的一些相关项目进行分析、实现，并能引导学生独立完成相关软件，为有兴趣参与 计算机 博弈 程序设计的读者提供参考。2. 预备知识要求本书主要讲述 计算机 博弈 及其实现的过程，读者需有基本的 计算机 语言知识，并能够编写简单的应用程序，对所学的语言并无特定的要求，例如C、C++、Java等语言均可作为具体实现的语言，本书中关于搜索和估值方面... 弈棋过程分析  为了深入探讨 计算机 博弈 的原理与方法学问题，有必要分析二人对弈的演化过程，建立 相应的数学模型。图 2-1 给出了 博弈 状态演化过程图[5]。图中表明棋局状态是在着法算子作 用下进行演化的，其对应的状态转移方程可以写成          ) 0(, 011 S SqSS nnn = ⋅= ++               （2-1）  式中 0 S 为棋局的初始局面， 1 +nq 第一章 计算机 博弈 简史 计算机 博弈 (Computer Game)，在某些时候也成为机器 博弈 ，在近年来受到了越来越大的关注。 博弈 （GamePlaying）是一种竞争，而竞争现象广泛存在与社会活动的许多方面，因此 博弈 论可以很自然地引深并应用到含有竞争现象的政治、经济、军事、外交等各个领域。然而，从狭义的“ 博弈 ”来讲，人机 博弈 （ 计算机 下棋）是各个领域 博弈 理论的起源与基础，在人工智能方面更是一个 规则非常简单仅有以下三条： 玩家： 如五子棋及围棋，有黑白两方，各持黑子与白子，黑先。 玩法： 除了第一次黑方下一颗子外，之后黑白双方轮流每次各下两子，直的、横的、斜的连成 6 子（或以上）者获胜。 若全部棋盘填满仍未分出胜负，则为和局。没有禁手；例如长连仍算赢。 棋盘： 因为公平性不是问题，棋盘是可以...