大家好
欢迎回来
我们继续基于决策树和搜索的人工智能系统的介绍
我们第一个实例其实是基于规则和基于搜索
介绍了读心术
当然在读心术被剖析之前
你可能认为它还挺神秘的
但我们揭示了背后的这些规则和判断和搜索之后
你可能会不以为然
原来这样就是一个智能
我们接下来来介绍一个更为复杂的
真正能够下棋的人工智能系统
这就是井字棋
那么井字棋英文叫做tictactoe
它是由两个玩家在一个3×3的一个棋盘上来玩的
那么棋子有两种
一种是叉
一种是圈
那么你只要在棋盘上画就行了
叉先下
圈后下
然后呢
最终的结局是应该当然也是轮流下
最终结局谁赢
就是谁先能够把自己的棋子排成三个一行
也就是或者是横的
或者是直的
或者是斜的
如果能够连成一线的话
那么它就胜利了
当然我们可以看到这个是一个我们在闲暇的时候
实在很无聊的时候
可能会玩的一个小游戏
当然如果真的有一个计算机程序
能够每一把都能够战胜你的话
你可能会觉得比较惊奇
他也能够下棋了
对不对
当然井字棋游戏它如此的简单
或者说如此的普及
以至于在1952年
英国的计算机科学家道格拉斯他就开发出了第一款电子游戏
就是井字棋游戏
那么这个井字棋的游戏的目标
我们下面来对它进行分析
看看这样的一个人工智能下棋系统
它究竟应该怎么样来构建
我们首先就要知道这个目标
目标是把自己这一方的三个棋子连在一起
那么就像这样有横的有斜的还有竖的
这些都算
第二个目标就是尽量的阻止对方的三个棋子连在一起
因为一旦对方的三三个棋子连在一起的话
它先于我连在一起
那我就输了是吧
所以第一个是要自己要赢
第二个是阻止
让对方赢得这个机会大大的减小
那么我们就可以来分析棋盘上的局面
它到底有多少种这样的局面
当然在分析局面之前
我们首先发现这个棋盘它是一个正方形的棋盘
而且它的格数其实是很有限的
它只有3×3
也就是只有九格
那这个我们实际上就可以通过分析
很可能就可以穷尽所有的局面
当然在穷尽局面之前
实际上我们对于这个局面的特征也会有一个认识
因为存在旋转对称性以及轴对称性
实际上也大大减少了局面的个数
那么原来的局面的特征会有多少种呢
如果我们把每一个格子画上圈画上叉
或者说不放上棋子的话
它每个格子就会有三种不同的可能
那么总的局数应该是3的9次方
但是如果我们认识到这种旋转对称性和轴对称性之后
我们考虑到这些对称性
其实最终的局面它是非常有限的只有138种
而且其中先手方就是叉获胜的局面会有91种
而后手方获胜的局面会有44种
最终平局的话其实只有三种
也就是我们下面列出来的三种的局面
这样的话我们就可以再进一步的研究游戏的策略
当然游戏策略首先是让自己获得胜利
也就是说当我有两个棋子连在一起的时候
就把它们连成三个
第二个是如何去阻止对方获得胜利
当然很明显
如果说对方已经有了两粒连子的话
就要阻止他们构成这个三连
也就是连在一起
就要在第三个位置上赶紧打上自己的棋子才行
那么最终我们其实游戏策略总的来讲
应该还是要创造出能够获胜的这些机会
什么样叫做能够必胜的机会
我们一定要争取同时有两个路径能够完成
三个棋子连在一起
也就是说我只要在这个位置上下
那么就会有两个连在一起的
有两条这个路径
我无论在哪个地方下都能够胜利
那这样的话对方就只能够堵一个的话
封堵其中的一个可能我也能够在另一个可能上进行获胜
所以这个就是创造出我们获胜的机会
这样的一个局面
尽量是创造出这样的一个局面
而也要阻止对方创造出这样的一个机会来
就是当它快要出现有两个路径都能够完成
三个棋子连在一起的时候
我们要事先要预测到
然后同时把这个机会给它破坏掉
所以其实有一个决定的问题
就是当我们一个新手玩家选择下在某一个地方的时候
我们下一步应该下在哪儿
比如说在图上
我们的先手玩家选择下在角上的时候
那么后手方在这个图当中
当然后手方它其他的八个都是可以画的
当然在经过进一步的规则的精简之后
在123这三个位置里头
通过旋转性旋转的对称和轴对称性
其实只有这三个地方这个位置好下
那么这三个位置下的时候
哪一个其实是最好的
那么所谓的最好
能够使得自己有两个路径的连接
同时破坏对方有两个路径连接的这样的一个状况
实际上既然这个局面的数量其实是只有一百多个
在这么少的情况下
其实我们可以把这所有的局面通过下棋的步数
给它连接在一起
构成一个规则的搜索树
那么这个树当中的每一个内部的分叉点
就是一个局面
那么这样的一百多个局面其实是一个
很快可以穷尽的这么一个搜索树了
在树上进行搜索的时候
我们其实还可以去判断对方是一个什么样的角色
如果双方玩家其实都采取最优的策略的话
那么井字棋一定最终会落到三个平局当中的一个
我们通过分析我们刚才一百多个局面的搜索树
其实是可以知道的
如果说双方的玩家的水平都比较高的话
也就是说他可能偶尔会出现一些失误
这种情况下先手方下的角落
它其实是更有机会获胜
这些都是从我们的构建出来的规则的搜索树
就是局面的树当中推理出来的策略
当然如果说双方的玩家的水平都不高的情况下
其实就是说失误比较多
那么下的中间其实更容易获胜
因为下在中间的话
它可以称之为是一个四通八达的一个位置
它的上下左右斜上斜下
其实都可以下进一步的下子
所以它的机会更多
那么这样的话
如果我们做一个计算机的程序
让他在这个规则树上局面树上进行搜索
从而根据我们的策略
让人工智能让AI程序来决定下在哪的话
实际上只需要经过简单的在树上进行推理就可以了
所以我们说从这个角度上来看
让人工智能学会下棋
其实他并不需要下棋的直觉
或者说赢棋的一种智能
那么他只需要在局面树上进行简单的策略的搜索
只要搜索的路径最终达到己方获胜的那些局面
那么AI人工智能的下棋程序他就一定能够胜过你
但这当中其实也有一个选择策略的较量的问题
人工智能程序总是把他的下棋的可能性
一直引导到他能够获胜的那些局面
而如果说是经验丰富的人类
当然就要尽量的把局面进行扭转
下到自己获胜的那一方
从而让我们觉得人工智能的程序来具有一定的智能
它能够想出很好的策略
其实我们在分析了这些策略之后
其实我们可以看出来
在特定的这些局面的情况下
其实人工智能他只是按照一定的规则给出一些固定的决定而已
并不是说它具有真正一个思考的能力
那么至于井字棋游戏的具体的程序
我们还会在练习当中会给大家进行展示