第5章博 弈 知己知彼,百战不殆。 ———孙武① 按照本书惯例,还是从博弈这个名字说起。博弈,中文原意就是下棋。但是今天博弈这 个词引申的含义非常广,现在一般说到博弈,都是指在双方或者多方指定的规则下,选择合 适的行为或者策略,从中获取各自最优的收益。一般用于描述运筹学、管理学、经济学等学 科中的博弈行为。 博弈又分为零和博弈、正和博弈、负和博弈。零和博弈就是在双方博弈过程中,一方输 掉的正是另一方所赢得的。例如,零和博弈过程中,你输了5元,那对手就赢了5元,棋类游 戏就是最典型的零和博弈。在博弈过程中,如果加入增量,输赢之和大于零,就属于正和博 弈,人们所说的“双赢”就是一种正和博弈(正和博弈也可能一方赢一方输,例如,一方输了5 元,另一方赢了7元,也是一种正和博弈)。类似的,如果输赢之和小于0,就是负和博弈。 另外,按照博弈双方掌握信息的情况,博弈也可以分为完全信息博弈和不完全信息博 弈。所谓完全信息博弈是指在博弈过程中,博弈双方均知道对方的博弈动作、策略等相关信 息,例如双方下棋;不完全信息是指在博弈过程中,至少有部分信息是博弈对方不知道的,打 扑克、打麻将就是典型的不完全信息博弈,因为并不知道对方手中有什么牌。 本章主要介绍计算机博弈,就是学习如何让计算机下棋。让计算机下棋一直是很多天 才的梦想,事实上,如果以人机对弈为主线写一部人工智能的发展史,和本书第1章的内容 应该有很大重合。计算机的博弈水平一直随着人工智能技术的发展而进步。人工智能最近 一次大热,也是AlphaGo 战胜人类围棋顶尖高手,从那时候开始,人工智能才从学术界走向 大众。机器在围棋上打败人类之后,可以认为棋类问题已经被人工智能解决了。 本章从最简单的棋类游戏———井字棋开始。 5.棋类游戏框架 井字棋,英文叫作tic-tac-toe,规则是在3×3 的棋盘上,双方轮流下棋,谁能够首先把横 线、竖线或者斜线连成一排,1是一个井字棋游戏示例。井字棋的规则如此 谁就赢了。图5. 之简单,大家很快就能上手下棋。那么,如何编写一个下棋程序呢? 一个下棋程序需要有一个数据结构描述棋局的状态,这个数据结构一般是一个一维数 ① 这句话来自《孙子兵法·谋攻篇》。博弈是不见硝烟的战争。博弈胜利的关键在于不仅要知道自己的想法,而 且要知道对方的想法。 第5章博弈141 图5.井字棋 1 (井字棋有个必赢的走法,但是本书不会剧透给你) 组或者二维数组(香农很早就提出用二维数组表示棋局局面)。对于井字棋来说,只需要一 个3×3 的二维数组即可(或者有9个元素的一维数组也可以), 这个数组中每个元素的值分 别代表当前局面下每个空格的状态。数组中每个元素的取值有三种,例如,可以用-1表示 一个(X)玩家的棋子落子在对应的位置上,用1表示另一个(O)玩家,用0表示当前位置还 没有落子。例如,图5.0,1,1][1,1][0,1]。 1中的棋局局面对应的数组是[---1,0, 其实中国象棋和围棋在维护棋局局面方面,原理上和井字棋是一样的。围棋和井字棋 一样,只有黑白两种棋子,有一个19×19 的数组就可以描述围棋的棋局局面。中国象棋比 较复杂,需要一个9×10 的数组表示整个棋盘,因为中国象棋棋子的种类多一些,双方一共 有32 个子,其中又包括车、马、炮等不同的棋子,因此数组元素的可能值有33 个(16 个表示 红方,16 个表示黑方,1个表示无子)。在真正实现棋类游戏的时候,很多程序使用位数组来 表示,加快运行速度。 当然,大家见到的棋类游戏软件都是图形界面的,这些软件中维护棋局局面的依然是数 组,只不过在软件开发过程中,背景是棋盘图片,每个棋子也是图片,双方数组的元素值也和 相应的棋子图片对应。双方每落一个子之后,都要刷新一下这个局面,对于图形界面,就是 把棋子图片显示到正确的位置上。 另外,一个下棋程序还需要能够判断棋局的胜负。任何棋类游戏都有一个胜负规则,谁 先满足了这个规则,就可以认为他胜利了。井字棋的规则最简单,任何一方只要有三个子连 成一行、一列或者对角线,就可以认为该方胜利。围棋的胜负判定是数“气”,中国象棋是判 断主帅是否被杀(象棋还要判断是否处于“将军”局面), 其他的棋类游戏各有各的判定方法。 下棋的核心就是要选择正确的位置落子。对于人类来说,落子决定是由人做出来的,因 此程序写起来简单。例如,井字棋在设计程序的时候,只要考虑对应位置上有无棋子即可。但 是其他棋类,例如象棋,还要考虑合理的走法,(“) 马走日、象走田”,围棋有“禁着点”,程序只要保 证人类下棋应该遵守这些规则就可以。机器的落子方法是本章的核心,后文将会介绍。 有了以上基本概念之后,下棋程序就是双方轮流落子了。当然,不管这个程序是人机对 弈还是人人对弈,写法都比较简单,双方轮流落子,每次落子之后,都刷新一下局面,判断是 否一方胜利,如果没有判断出胜、负、平局状态,另一方接着落子即可…… 循环一直进行,直 到能够判断出胜、负、平局状态。 程序5.1是一个井字棋游戏的框架,这个框架提供了人机博弈的界面,这里机器落子是 随机的,这个框架中机器能下棋,但是没有棋力。如果人类和这个程序下棋,应该能做到百 战百胜。 142人工智能:是什么? 为什么? 怎么做? 怎么才能让机器也有棋力呢? 5.对抗搜索 2 5.2.1 博弈树 所有的下棋程序都可以用一棵树表示,称之为博弈树,下棋程序就是在这棵树上进行搜 索。博弈树描述了下棋的每个步骤。图5.部分)。 2是井字棋的博弈树( 图5.井字棋的博弈树(部分) 2 图5.第零层( 是开局状态,假设第一步是X落子,X可能的落子点有9个, 2中, 最上层) 这样第一层就有9个可能的棋局;然后第二步是O落子,O此时落子的可能位置有8个(因 为某一个位置已经被X落子了), 因此,第一层每个棋局后续都有8种可能(也可以说这棵 树中第一层的每个节点都有8个孩子节点), 图中只选取一个局面绘制其孩子节点,假设第 一步X落到棋盘最中间的位置,随后O的8种可能落子位置如图中第二层所示;交替进行, 现在下到第三步,X落子,以此类推,一直到博弈结束。 理论上,这棵树应该有9!(=362880)个节点。但是实际上,这里面很多节点是相同的 (也就是棋局是重复的), 另外,很多时候棋局没有到最后一层可能就判出胜负(例如在倒数 第5章博弈143 第二层的最后一个节点,此时X玩家已经赢了,这个节点就不应该有后续节点), 实际的博 弈树节点会少一些。 井字棋是一个非常简单的游戏,因为与更复杂的棋类游戏相比,该游戏的最大走棋步数 非常少(双方加起来最多只能走9步)。因此,井字棋游戏非常适合计算机博弈入门。 本章的目标就是搜索这棵博弈树,找到下棋的最佳方案。 理论上,任何一种棋类游戏均可以创建一棵博弈树,并且,如果能够搜索整棵博弈树, 一定会找到一种必胜的走法。然而实际上,很多棋类游戏的博弈树太庞大,根本无法完全 搜索,即使是复杂如围棋,也有一个必胜的走法,只不过这个必胜走法可能永远不会被人 类发现。 博弈树的想法十分自然,如果有下棋经验就会知道,下棋过程中经常要考虑,如果对方 这么走,自己应该那样走,如果对方继续走这步,自己应该怎样应对。实际上,这样的思考过 程就是一棵博弈树。 5.2.2 静态估值 在设计棋类游戏的时候,也有启发式的想法,一个最简单的启发式就是给每一个棋局状 态打分(也叫估值), 分数越高,表明该棋局越容易胜利。然后搜索分数最大的分支,现在的 关键就是,如何去打分? 假设现在井字棋到了图5.3这一局面,X刚刚落子完毕,此时轮到O落子,O有5种选 择(图5. 3中的5个孩子节点)。 图5.博弈树的静态估值 3 因为在X落子之后,只有5个空位,那么O的落子,只能落在剩余的5个空位上(粗体 的O表示这一步的落子)。在这5个分支中,选择哪个分支最好呢? 在这棵树中,可以使用一个静态的估值函数,来评估下一步走棋的优良程度值。井字棋 中一个可能的静态估值函数f(为 n) f( = 自己可能获胜的位置数-对方可能获胜的位置数 例如,在分支① n 中 ) ,O如果落子在这个位置,那么,第一列、第二列、第三行、主对角线都 可能使自己获胜,自己可能获胜的位置数是4,故而分值是4,而第一行和第三列有可能使得 对方获胜,对方可能获胜的位置数为2,因此,这个局面的估值分数是4-2=2。利用这个估 144人工智能:是什么? 为什么? 怎么做? 值函数可以得到下一步走棋的分数,该估值函数的值越高,意味越有可能使玩家获胜。这 样,在搜索的时候沿着估值高的分支前进,获胜的可能性就大一些。 静态估值函数虽然可以得到一个分数,但是这个估值函数存在一些问题。例如,这里有 三种走棋方案的估值函数值等于3(③、④、⑤分支), 但是只有一种方案能够使O玩家获胜 (分支③)。因为虽然有另外两种方案(分支④和分支⑤), 但是O玩家如果走分支④或分支 ⑤,那么玩家X在随后的走棋中马上就可获胜。因此,虽然静态估值函数有用,但是只靠静 态估值函数是远远不够的。 在博弈这种对抗搜索中,minimax算法(极小极大算法)是最基础的算法。 5.2.3 minimax 算法 普通人和高手下棋的一个重要区别就是普通人在下棋的时候只关注自己,只想着自己 快走几步并杀掉对方,而不太关注对方的用意,这样很容易陷入对方的圈套,反而输掉棋局。 换句话说,在下棋的时候,你不光要考虑自己怎么走的,还要考虑对方为什么这么走,而 不能把对方当成一个笨蛋。 那么,如何能做到既关注自己又关注对方? 冯·诺依曼和摩根斯特恩在《博弈论与经济 行为》一书中提出了minimax算法[1]。事实上,minimax算法并不是专门为人机对弈所设 计,它能够解决博弈论中的很多问题。不过这个算法在人机对弈中发挥了巨大的作用,所有 的棋类设计软件都能看到它的身影。 minimax算法是在轮流行动游戏中,选择最优行动的一种方法。轮流行动游戏是指一 个玩家与另一玩家相互对抗,具有相同且相互排斥的目标,也就是说是一个零和博弈。在已 给定的游戏状态下,每个玩家都知道下一步可能的行动方案,因此对于每一次行动,玩家都 可以考察随后的所有行动。下棋就是标准的轮流行动游戏。 双人游戏轮流走棋,玩家会在走棋时选择对己方最有利而对对方最不利的走法。如何 做到“损人利己”? 原则非常简单,对于自己走棋,选择最大评估值的那个分支,如果是对方 走棋,选择最小的评估值分支。因为双方交替走棋,因此,算法交替地在博弈树中寻求最大 评估值和最小评估值。 在博弈树中的每一个节点都可以保存一个值,这个值即为评估值。该值用来定义对应 行动在帮助玩家获胜方面的优良程度,前文介绍的静态函数估值即是计算该值的一种方法。 在设计人工智能棋类游戏中,节点评估值对于计算机下棋落子位置有指导性作用,该值 越大,获胜的可能性越大。事实上,不只是人机对弈,人人对弈的双方其实也都有一个评估 值,只不过对人类来说,这个评估值是隐性的,下棋的时候人们可能不会注意。对于计算机 来说,需要有一个显性的评估值。 图5.4给出了在一个特定的井字棋棋局的残局博弈树中,minimax算法的运行过程。 图5.图中的树共有4层, 这 4是一棵博弈树的一部分, 根节点所在的那层为MAX 层, 一层所有的节点都是MAX 节点,也就是说,这一层的每个节点的评估值是其所有孩子节点 的评估值的最大值;图中标记MIN 的那两层的节点为MIN 节点,这两层中每一个节点的评 估值是其所有孩子节点的评估值的最小值。这里的终局状态有三个可能的评估值:-1表 示玩家X赢,0表示平局,1表示玩家O赢。 现在棋局走到根节点这个局面,O玩家和X玩家各走了三个子(根节点状态), 下一步 第5章博弈145 图5.mnmx算法示例 4 iia 轮到O玩家走棋。minimax算法可以帮助O玩家找到最优的下棋路径,这个算法需要计算 当前节点的评估值,如果当前节点是MAX 节点,那么就取所有孩子的最大评估值;如果是 MIN 节点,就取所有孩子节点的最小评估值。 在图5.灰色的节点为叶子节点, 也就是达到了胜、平、负三种状态之一, 4中, 表示终局, 在井字棋中,只有这个时候才能得到评估值。在图5.O玩家最后根节点的 4这棵博弈树中, 评估值是0(也就是说,O玩家最好的结果就是平局)。看看这个0是怎么得到的,对于根节 点局面①来说,它是一个MAX 节点,因此,它会取它三个孩子节点的最大评估值(分别是 -1,-1,0), 结果是0,来自局面④。局面④的评估值0是怎么得到的? 这一层是MIN 层, 所以它会取它的两个孩子节点评估值(0和1)的最小值,得到0。同理,局面⑨在一个MAX 层,所以它会取所有的孩子节点的最大值,因为只有一个孩子节点,所以它的评估值为0。 ..是一个终局局面, 双方平局, ..的估值是0。其他局局面....也就是在这个局面下, 因此,局面.... 面也通过同样的过程得到评估值。从这个过程可以看出,minimax算法非常适合使用递归 程序来实现。 根据minimax算法,对于当前局面来说,O玩家最好的结果就是平局,走棋方式如黑色 粗线所示,即按照局面①→④→⑨→..这样的走法对于O玩家来说是最优的。如果 ..走棋, 不这么走,O玩家很可能的结局就是输掉比赛。 .. 1 46 人工智能:是什么? 为什么? 怎么做? 对于O 玩家来说,当然希望能够赢棋,下到估值为1的局面,也就是局面......和......。但是 别忘了博弈是双方进行的,O 玩家想要下到这些状态,X玩家可不会同意,以最左侧的分支 为例,如果O 玩家走到局面②(也就是落子在最左上角),那么X玩家马上会落到最右下角 位置,局面⑥,从而X取得胜利。因此,对于O 玩家来说,是走不到局面......的。对手不是白 痴,不会让你轻易胜利。 对于井字棋游戏来说,因为博弈树不会很深,最深的层数才是9,所以可以搜索完整的 博弈树。但是对于大部分棋类来说,都需要建立一棵庞大的博弈树,这样的博弈树是不可能 搜索到全部局面节点的。在大多数棋类游戏中,包括国际象棋和中国象棋等,对于搜索都限 制了一定的深度,例如从当前局面出发,只搜索下面10层的博弈树。这里搜索10层相当于 人们平时说的下棋能看到后面多少步,例如,专业棋手能看到十步到二十步棋,一般的高手 能看到三步到五步棋,普通人下棋只能走一步看一步。 博弈树太深意味着无法到达叶子节点。递归地搜索完整的博弈树是一个费时且费空间 的过程。这意味着虽然minimax算法能够应用到简单的游戏中(例如井字棋游戏),但对于 很多其他棋类来说应用起来却很困难,因为其他棋类游戏的博弈树太复杂而且难以搜索完 全。这也是早期电脑下不过人类的原因之一,因为没有办法搜索那么大的博弈树。 minimax算法的基本过程如下。 minimax(player,board) if judge(player,board)==end return for 当前局面之后的每一个局面 if(player==computer) return max_score if(player==human) return min_score 在这个函数中,player、board分别指当前玩家和当前局面,judge用于评估当前局面的 胜负情况。 对于如何得到每个局面的最大值和最小值,可以使用递归调用,因为在不同的层上 (MAX层和MIN 层)需要分别计算极大值和极小值,因此,需要有两个函数player_ computer(board)和player_human(board)。 以下是player_computer()函数。 player_computer(board) if judge(board)==end return for every empty entry new_board=board mark entry in new_board as player_computer value=player_human(new_board) if value>max max = value return max 以下是player_human()函数。 第5章 博弈1 47 player_human(board) if judge(board)==end return for every empty entry new_board=board mark entry in new_board as player_human value=player_computer(board) if value