大家好
欢迎回来
我们继续基于决策树和搜索的智能系统这一节的介绍
我们这一节来介绍博弈树
我们知道在人类社会的发展过程当中
人类发明了很多游戏
很大一类就是棋牌类的游戏
各种各样的棋和扑克牌
还有其他的一些这种对抗竞争性的游戏
这些游戏除了说它具有闲暇娱乐打发时间的功能之外
实际上它也有在游戏当中锻炼智能的这么一个作用
可以培养你的智力
我们知道所谓的智能其实很大程度上来讲
就是当你面临一个复杂的环境
或者甚至在不断的变化的环境里边
当你又有竞争者同时有合作者
那么你采取什么样的一个行动
才能够使得自己获利最大
或者说使得己方与以合作方一起能够获利最大
那这样就能够在整个的竞争当中获得优势
所以我们人工智能所面临的任务
其实也有很大一部分的任务就是落在这种在
复杂的环境当中进行合作进行竞争
然后获胜这么一个任务
这是一个很大的任务的领域
所以从这个角度来说
我们人工智能的研究棋牌类的这种游戏
或者说统称叫做博弈
那么就有很重要的意义
所以我们这儿把所谓的博弈可以给它分成几种类别
首先第一个是所谓的完全信息的博弈
什么是完全信息
在你的竞争的过程当中
游戏当中的所有的状态的信息
对于所有玩家都是完全可见的
那么比如说我们的井字棋
比如说我们的象棋
国际象棋围棋
这些都是属于所谓的完全信息
那么在完全信息当中
双方掌握的对于游戏和对于环境的信息是完全一样的
然后在这种信息对称的情况下开展博弈
那么相对的另外一种类型
就是所谓的不完全信息
不完全信息就会更加复杂一些
每个玩家都有自己的一些私有信息和一部分被公开的信息
那么这样的话
你的游戏策略就需要建立在对于真实的状态
一些合理的猜测之上
在这种游戏里头
那些不善于记忆
不善于统计不善于猜测的玩家
可能就会落在下风
那么这种游戏像我们经常玩的军棋是吧
都是背对背
而且会有一个裁判
那么当你进行试探的时候
试探性的进攻
然后是取胜或者说失败
你从这些不完全信息当中去推测出对方的布局
以及对方的下一步的行动的策略
当然还有一些其他的一些牌类
比如说一般的扑克牌或者说桥牌
玩家之间是不会公开你的所有的牌面了
你要在打牌的过程当中
根据对方的这个策略和这个过程当中的一些
输赢的状态来去推断对方整个的牌面的信息是什么样的
他手里握着什么样的牌
他会怎么样去做
所以不完全信息的这种博弈比完全信息它是不一样的
可能会更加的复杂一些
它所需要考虑的因素就更多一些
不光光仅是一个策略的问题
可能还会涉及到一些博弈心理的问题
这是完全信息和不完全信息
另外还有我们还可以进一步的进行分类
分出所谓的叫做零和博弈
那么什么叫做零和英语叫做zero sum
那么既然是零和
也就是说有人赢就必然有人输
所以就是零和博弈当中
双方或者多方的它的收益的总和加起来是零
所以这叫做零和
那么在零和博弈里头
很显然我只要让跟我一起竞争的其他的人
他的收益最小化
那么就可以使得自己的收益最大化
也就是说只要是损人的
我们就必然会利己
这是所谓的零和博弈
那么我们知道在很多的棋类当中
基本上都是属于你死我活
你输我赢的这种零和博弈
当然说到零和就会有非零和
因为人类社会当中人们的竞争和合作这种状态
是相当复杂的
那么所谓的非零和博弈
就是所有的人的收益之和不为零
也就是说它存在合作或者双赢的可能
只要你采取适当的策略
你获得的胜利不一定建立在对方失败的基础上
你可以让大家都可以有一个大的收益
这种叫做非零和
那么这样自己的所得并不是跟其他人的所失的
大小是相等的
那么也就是说它存在当然存在双赢的可能
也可能存在所谓的叫做损人不利己
也就是说你的使得其他人的收益最小化
也未必见得能够使自己的收益会变大
可能并不会变大
那么这里头很著名的非零和的博弈的例子
就包括我们中国人很爱玩的游戏
就是麻将
风靡全国的这种麻将的这种牌类游戏
以及经济学家经常讨论的叫做囚徒困境
囚徒困境就很生动的说明了一种非零和博弈
那么囚徒困境他的这个故事是说有两个小偷
他去偷东西
然后被抓到了
警察把他们分隔开
然后让他们分别去认罪
那么只要答应他们
什么样的条件呢
如果你被检举了
那么就证明你是有罪的
你就要多坐牢
如果说双方都拒绝认罪
那么警察在无奈的情况下
也只可能把双方的都按照基本的刑期来去惩罚
那么所以我们列一个表就能知道了
什么样是一个非零和博弈的这种状态
在这个表里头
我们把两个囚徒称之为甲和乙
然后把它们合作或者说背叛
所谓的合作就是双方合作
但是我们注意到这个合作是在双方信息不对等的情况下
他们之间没有串通好的可能
如果他们能够商量好的话
那么自然他们会选择合作
因为只要双方都合作
大家都拒绝认罪
两个人都只要坐牢半年就够了
当然在非零和博弈当中
环境所给予的就是两个人不能够串通
如果说有一方背叛
也就是说指认了对方的话
那么对方就要服刑十年
然后自己就可以马上获得释放
当然还有存在的就是互相指认
所以这两个人都背叛
那么这种情况下
两个人都坐牢五年
这里就有坐牢是半年五年和十年之分
这显然就是一个收益
半年是收益最大化的
十年的收益是最小的
那么在这个当中
所谓的囚徒困境
就是你在跟对方没有沟通的情况下
你怎么选择策略
这个问题
当然最好的情况下是双方都合作
双方收益都最大
这是一个双赢
那么双输两个人都输
就是两个人都选择背叛
就是双输
那么还有一个单方面输得很惨
一方面合作
一方面背叛
那么那么最后大家想想
在这种信息完全隔绝开的情况下
这种非零和博弈囚徒困境
它最可能发生的结果是什么
当然这个经济学家会告诉我们说
最可能发生的结果
你采用的最优的策略
其实并不是说让自己的收益最大化的策略
也就是自己选择背叛
期望对方合作
这样的话自己马上就一天牢都不用坐
这是不太可能的
经济学家告诉我们说
在囚徒困境的情况下
你所采取的最好的策略并不是自己收益最大的策略
你只能够说是双方都背叛
选择检举对方
然后去做五年牢
所以这是囚徒困境
非零和博弈的一个很好的例子
所以在非零和博弈当中
它是相当复杂的一个局面
那么你如果只考虑你自己的一个最佳选择
不考虑这个团队的最佳选择的话
你可能就得不到你的最高的利益
所以这个和零和博弈是不一样的
而且选择让对方收益最小化的这种策略
并不能使得自己收益最大化
也就是说让对方收益最小化
你就是检举
对方显然也会这么想
在这种情况下
实际上你自己的收益是不可能最大化的
所以最有可能就是在囚徒困境当中
双方都各自检举对方
然后双方都做了五年
这当然不是一个利益最大化
但是这是一个非零和博弈特别复杂的一个例子
当然在人类社会当中
你需要用到的智能
当然也并不一定是人和人之间的竞争和合作
包括其他的你和环境之间和整个的团体之间
进行选择竞争的时候
非零和博弈是非常常见的一种状况
现在大家都希望叫做合作能够双赢
也就是说希望整个不是一个零和
就不是说是你输我赢的这种状况
而是期望大家能够通过信息的充分的沟通
然后都取得一个最大的收益
双方都取得最大收益
这个就是一个非零和博弈
所以从博弈的角度上来讲
完全信息，不完全信息，零和和非零和这个就形成
了一个非常复杂的这么一个局面
那么包括在我们的所谓的中国人经常玩的游戏
的麻将里面也有这样的一个情况
就是在麻将当中
为了不让一个对手
你有三个对手
不让一个对手来和大牌
如果让它和了一个大牌的话
你的损失就会比较惨重
那么你可能会选择故意让另外一个可以和小牌
的对手去点炮
叫作点炮
然后让他去和
这样使得自己的损失更小一些
而不是说去拼命的去争取自己能和牌
你可能在这个情况过程当中
觉得自己和牌的已经没有什么希望了
你就要退而求其次
来选择一个次佳的策略
让自己的损失更变得更小一些
这个也是说明了博弈当中非常的复杂
也就说明了说人工智能要处理这方面的这个
任务也还是需要走很长的一段路
那么人工智能来处理博弈的这种状况
可以是什么样的一个做法呢
首先我们基本上来先说现在都是所谓的
构建一棵叫做博弈树
我们第一次提到树这个概念
其实并不是很神秘的
你虽然没有学过这个计算机
你可能大概也见到街上马路上的一个树
所有的树就是它有分叉
然后他有分层
是吧
那么我们所谓的建立博弈树
让每一个节点它都对应一个下棋或者打牌的一个局面
所谓的局面可能比如说对于完全博弈
完全信息的博弈来说
这一个局面就是一个牌局的布局
黑的在哪
白的在哪
这么一个布局就叫一个局面
那么一个局面由一方来下了一步棋之后
就是做了一个动作之后
他就可以变为局面二就是下一个局面
当然这个动作的选择可能会有很多
在一个复杂的这种棋局当中
你可以选择这么走
你也可以选择那么走
那这样一个局面就在不同的动作情况下
它就会再下一层
就会扩展出更多的局面出来
那么可想而知
博弈树它是一层一层往下会越来越大
正如我们在自然界当中看到的树从一个主树干开始
一直到整个的树叶的分支
树干只有一根
你要是数树叶的数量肯定多得多了
那么这当中有非常多的层次
所以我们的博弈树实际上它整个的构建跟树的
生长过程是非常类似的
我们从局面如果是井字棋的话
第一个局面是空的棋盘
你下了一个之后
因为有九个位置可下
那么就会分出九个支来
然后每个又分成九个支来
对于不同的这种棋类来说
它的博弈树是不一样的
那么我们可想而知
博弈树的生长也是特别的快的
不像我们自然界当中树过了很多年
它就慢慢生长
但是整个你要说树叶的数量
相对于一根主干而言
肯定是多的去了
那么所以我们这个也可想而知
你如果要整个的对于博弈树进行操作进行探访的话
那么它需要花费很大的代价
所以我们在完全信息和零和博弈的情况下
其实能够构造出来的博弈树相对来讲还是比较简单的
也就是这个局面是一个节点
然后我们在局面上有几个分支
下一层就会多出多少来
然后再下一层的每一个局面又有对方可下的
这种可能的动作
它又可以展出来
那么实际上博弈树虽然庞大
但实际上它还是比较简单的
如果是不完全信息
如果是非零和博弈的这种情况下
那么博弈树就更加的复杂
因为你所采取的动作
它受到很多的限制
以及你对于这个局面的猜测
因为你并不知道这个局面是一个什么样确切的局面
你并不知道对方是什么牌
那么这种情况下
你所采取的这个动作以及决策的分支就会非常的复杂
所以目前来说
我们人工智能所能够很好解决的问题
还是第一是完全信息
第二是零和博弈
所以在无论是像从最简单的井字棋开始
到黑白棋到五子棋到中国象棋到国际象棋到围棋
其实这些一系列的所有的这些棋下来
它都是属于叫做零和博弈完全信息
这当中最简单的企业当然就是属于井字棋了
在井字旗的博弈树
我们可以看到它就是这个样子的
它最高能有九层
所以其实他受到的限制还是挺大的
所以在井字棋的情况下
我们其实是可以把博弈树给它完全构建出来
以现在目前计算机的硬件的能力
是可以把整个井字棋的整个博弈树穷举出来的
你看在树根当中叉的玩家在左上角下了一个叉
那么接下来这个圈它就有几种选择
当然我们可以按照人为的规则把一些旋转对称
和轴对称的这种方式都去掉
那么一共它接下来就会有四种的下法
下在中间，挨着它下，下在对角
还有下在对边上
那么这四种这个圈每种圈的这情况局面的情况下
再由叉的玩家再去继续下
这样一层一层地扩展出去
我们就可以把整个的博弈树给构建起来
构建博弈树还只是人工智能来下这个棋的第一步
后续构建好博弈树之后
我们要怎么办
才能够赢得这个棋子的最后的行为
我们等后边再为大家来介绍