实践 手把手教你开拓三子棋AI

ApacheCN 优质AI博文推举项目正式启动

优质AI博文推举

逐日从从所有投稿博文中精选两篇，在ApacheCN全"大众平台推送。

投稿须知

接管个人学习博文，论文解读，打比赛心得等AI干系文章投稿。

投稿时请新建Issues，按以下格式进行填写：

博文地址：是否为个人原创：

投稿推举语：

原作者信息(选填)：作者昵称，原始发布平台，联系办法

投稿地址：https://github.com/apachecn/awesome-AI-blog-post

本期给大家带来由 Jeff-Tian (jeff.tian@outlook.com)小哥哥带来的《手把手教你开拓三子棋AI》

试玩三子棋地址：https://tictactoe.js.org

一、择要：

二、三子棋

三、游戏界面编写

四、人工智能

五、机器学习

1、定义

2、设计

2.1、选择演习履历

2.2、选择目标函数

2.3、选择目标函数的表示

2.4、选择函数逼近算法

六、运用程序架构

1．域名：tictactoe.js.org

2. 系统类型：纯静态网站

2.1 ReactJs

2.2 Ant Design

3. 源代码

3.1 目标函数的表示

3.2 检讨棋盘的边

3.3 函数逼近算法

4. CI/CD：

七、评估以及后续事情：

简化

繁芜化

意见意义性

八、参考文献：

一、择要：

2016 年 3 月，AlphaGo【1】击败天下围棋冠军李世石，使得人工智能引起人们的广泛谈论。
如今，人工智能创业潮不断呈现，这个话题不仅生动于科技教诲界，乃至进入了街头巷尾，成为了人们的日常谈资。

各种人工智能框架的涌现，也大大降落了人工智能编程的门槛。
比如 tensorflow 不仅开源，还供应了一个在线演习人工神经网络的界面：https://playground.tensorflow.org【2、3】。
这使得开拓职员可以利用各种强大的工具，给自己的运用赋能，让传统的运用程序变得“聪明”。

通过利用这些工具，开拓职员不须要理解人工智能的根本事理，知其然而不知其以是然。
即如果须要从 0 开始，编写具有智能特性的程序，每每不知道如何下手。
缘故原由是这些框架本身是为理解决实际的运用问题而产生，并不是用来学习人工智能的知识和思想的。

以是本文考试测验通过一个实际的例子（https://tictactoe.js.org/），展示人工智能程序开拓的一样平常步骤。
出于演示目的，本文选择了三子棋（tic-tac-toe）这个最大略的棋类游戏来举例。
简化，也是学习根本事理的通用方法，通过简化的问题和模型打消不必要的滋扰，让人看清事理。
在节制了事理之后，即可推而广之，办理更繁芜的问题。

本文展示的一样平常步骤，不仅可以运用于棋类游戏开拓，而且是所有人工智能程序开拓的一样平常步骤。
当然，繁芜的程序步骤会更繁杂，但仍旧会以本文列出的一样平常步骤为主干。

二、三子棋

三子棋，起源于古希腊【4】，也称为井字棋，或者圈圈叉叉。
由于棋盘是一个九宫格，或者说像汉字中的“井”字，以是得名井字棋；又由于一个玩家通过打圈，另一个玩家打叉来玩这个游戏，以是得名为圈圈叉叉。
本文称其为三子棋，是由于在这个游戏中，当玩家的棋子能够三子成线时，即为得胜，故名三子棋。

图 2.1：三子棋盘

图 2.2：一个 X 方取胜的例子

三子棋是最大略的棋类游戏，它只有 765 个可能局势，26830 个棋局。
如果要实现一个人机对战的三子棋游戏，由于棋局的可能性并不多，完备可以利用穷举法做到。
但是这样做，代码量并不少，而且对人类玩家来说，由于机器对手每次策略都一样，以是意见意义性不高。

本文展示的人工智能程序的编写，不仅大大缩减了代码量（由于不须要存储取胜策略），而且由于程序的学习是一个动态过程，对付人类玩家的同样的走法，程序可能会给予不同的回应，这样下棋的意见意义性更高。

三、游戏界面编写

游戏界面不涉及人工智能部分，但却是玩家必须要通过界面来与程序交互。
本文选择了网页版界面，无需安装即可利用，而且便于传播。

要编写精良的网页界面，有很多精良的开拓框架可供选择。
本文采取了 ReactJs【5】，不仅由于它是目前最精良的前端框架之一，而且它的官方教程恰好供应了一个详细的编写井字棋游戏的教程【6】。

按照教程编写出来的界面是一个可以运行的井字棋游戏，可以由两人交替走子：https://codepen.io/gaearon/pen/gWWZgR?editors=0010。

图3.1：按照 ReactJs 官方教程编写的游戏界面

四、人工智能

据维基百科【7】阐明，人工智能（英语：Artificial Intelligence，缩写为AI）也称为机器智能，指由人制造出来的机器所表现出来有智能。
常日人工智能是指通过普通打算机程序来呈现人类智能的技能。

本文聚焦在这个定义的后一段，即通过编写一个普通的打算机程序来呈现人类智能。

人工智能的研究课题非常之多，个中之一是机器学习，本文所展示的程序，更精确地说，是一个机器学习程序。
本文所要展示的程序开拓步骤，也即机器学习程序的开拓步骤。

五、机器学习

机器学习是人工智能的一个分支【8】。
人工智能的研究历史有着一条从以“推理”为重点，到以“知识”为重点，再到以“学习”为重点的自然、清晰的脉络 。
显然，机器学习是实现人工智能的一个路子，即以机器学习为手段办理人工智能中的问题。

1、定义

常日有以下几种定义：

机器学习是一门人工智能的科学，该领域的紧张研究工具是人工智能，特殊是如何在履历学习中改进详细算法的性能。

机器学习是对能通过履历自动改进的打算机算法的研究。

机器学习是用数据或以往的履历，以优化打算机程序的性能标准。

一种更精确的教科书式的定义如下：

对付某类任务 T 和性能度量 P，如果一个打算机程序在 T 上以 P 衡量的性能随着履历 E 而自我改进，那么我们称这个打算机程序在从履历 E 中学习。

比如详细到我们的井字棋游戏，便是：对付学习下井字棋的打算机程序，它可以通过和自己下棋获取履历；它的任务是参与井字棋对弈；它的性能用它赢棋的能力来衡量。

图 5.1：三子棋学习问题的抽象

2、设计

那么如何来设计一个机器学习系统呢？一样平常有以下几个步骤：

图 5.2：设计学习系统的一样平常步骤

2.1、选择演习履历

本程序选择了两种演习履历：

产生随机合法的棋局：在本程序对外公开访问之前，可以通过让程序与一些随机产生的合法棋局对弈，产生低级的智能，然后再公开给用户访问。
这样比直接公开要好一些，由于直接公开，程序完备不具有智能，会让用户失落去兴趣。

和玩家对弈：在程序对外公开后，随着玩家与程序的对弈，程序连续不断调度自身内部的评估函数（目标函数）参数的权值。
玩家在与程序对弈的过程中，可能会觉得程序越来越聪明，从而更加引发玩家的好奇与兴趣。

当然，除了以上两种演习履历，还可以选择其他的演习履历，比如一个利用固定评估函数走子的棋局产生器。

2.2、选择目标函数

目标函数，也便是机器学习程序的评估函数，对程序的性能表现进行打分。
大致地说，这个目标函数该当对好的表现打高分，对差的表现打低分。

详细到本三子棋程序，对付凑集 B 中的任意棋局状态 b，我们定义如下目标函数 V(b)：

如果 b 是一终极的胜局，那么 V(b) = π/2；

如果 b 是一终极的负局，那么 V(b) = -π/2；

如果 b 是一终极的和局，那么 V(b) = 0；

如果 b 不是终极棋局，那么 V(b) = V(b')，个中 b' 是从 b 开始双方都采纳最优对弈后可达到的结局。
（这里涌现一个递归逻辑， 以是须要后面的一步：函数逼近算法来打算这个函数值）

当然，你也可以选择其他的目标函数，比如，如果是终极胜局，令 V(b)=100；如果是负局，令 V(b)=-100 等。
如果是和局，令 V(b)=0 显然是一个得当的选择。
那么这里为什么选择了胜局时，令 V(b)=π/2 呢？

由于这里做了一个假设：即棋局的表现，在达到结局前，是介于胜局与负局之间的，如果用一个连续函数来表示这种趋势（向胜局或者向负局的趋势），该当是如下图所示的一个曲线：

图 2.2：arctan 函数图形（赤色曲线）

这很自然让人遐想到 y=arctan(x) 这个反三角函数，而这个函数恰好介于 -π/2 与 π/2 之间，故采取它们分别做为负局和胜局的表现得分，这样就省去了做函数变换的麻烦。

2.3、选择目标函数的表示

有了目标函数，如何将它表示出来，即如何将它表示成一系列自变量的函数形式呢？

首先，目标函数是受棋局的状态所影响的，以是自变量肯定是棋局上的状态。
其次，不同的状态对付目标函数的影响是不同的，即不同的自变量，其权重不同。

如何找到得当的自变量，以及将目标函数表示成这些自变量的什么函数，没有一定的标准。
但是一旦确定了这个目标函数的表示，那么机器学习的过程，就转化成了一个函数调参的过程。

通过改变不同自变量的权重，将目标函数打算出来的值逼近给定的实验数据（即履历凑集），即是机器学习的过程。

本学习程序把 V(b) 表示成对一个线性函数求反正切值（线性函数单调，但是无界。
通过求反正切值，使得这个函数值知足了我们的有界性哀求）：V(b)=arctan(w0+w1x1+w2x2+w3x3+w4x4+w5x5)，个中w0 到 w5 为数字系数，或者叫做权，由学习算法来选择。
而x1 到 x5 为棋盘状态值，权 w1 到 w5 决定了不同的棋盘特色的相对主要性，而权 w0 为一个附加的棋盘状态值常量。

再次强调，自变量的选择并没有一定的标准，这里选择的 5 个自变量，是经由一些不同的实验之后，末了总结出来的可以达到很好效果但是数量又比较少的一个变量组合。
有没有可能选择其他的变量组合来得到更好的效果，还值得进一步磋商。

这里的 5 个变量分别是：

x1：棋盘上受到对方威胁的边数（一共 8 条边，如果一条边上涌现两颗敌子并且没有我方棋子，那么这条边形成了对我方的一个威胁），取值范围是 0 到 8。

图 2.3.1： 棋盘上对我方形成的一个威胁示意图

x2：坏交叉点数：如果两条边上各有一颗敌方棋子而没有我方棋子，并且这两条边交叉，那么这个交叉点称为坏交叉点（不好的交叉点）。

图 2.3.2：坏交叉点示意图

x3：机会边数：如果有一条边有我方两颗棋子而没有敌方棋子，那这条边是一条机会边。

图 2.3.3：机会边示意图

x4：占中上风：如果中间格子是我方棋子，那么我方霸占上风，x4 记为 1；如果是空，则记为 0；如果是敌方棋子，则记为 -1。
对三子棋稍作理解就会知道，中间格子的棋子更随意马虎与其他格子里的棋子连成一条线，故谁先霸占中间格子，谁在一定程度上就霸占了一些上风。

图 2.3.4：占中示意图

x5：我方的赢面机会带来的威胁数。
如果我方某边上已有两颗棋子，另一格子为空。
如果我方霸占这个空格就能赢，但是现在轮到对方走。
如果对方霸占这个空格，不仅阻碍了我方赢棋的可能，还同时让两条边以上拥有敌方的两颗棋子而其余一格是空的这种情形，那么下一步不管我方落子在哪格，对方总能赢，这就带来了威胁。

图 2.3.5：我方赢面机会所带来的潜在威胁

x1 到 x4 都很大略直不雅观，而x5 则是高手走法，通过前面的铺垫，在某一步，落一子而给对方造成两条边上的威胁。
而不才一步中对方最多只能防一条边。

回顾：针对这个详细的三子棋学习任务，我们把它转换成了一个学习目标函数表示中的系数（或说参数）w0 到 w5 的值的问题（调参问题）。

图 2.3.6：问题的转换

2.4、选择函数逼近算法

这个过程也被称作估计演习值，便是选择权重值的过程。
我们可以从任意的权重值开始，然后不断调度权值，直到找到一个比较好的权重值组合。

本程序采取了 LMS 最小均方法，对付每一个演习样例，它能把权值向减小这个演习数据偏差的方向略为调度。

详细地说，LMS 权值更新法则是这样的【9】：

对付 每一个演习样例<b, Vtrain(b)>

六、运用程序架构

1．域名：tictactoe.js.org

采取了 js.org 的二级域名 tictactoe，即三子棋的英文名称。
Js.org 供应免费的二级域名，尤其乐意为 js 运用供应做事，而本运用恰好是一个纯js 运用。

2. 系统类型：纯静态网站

托管在 Github Pages 上。
Github Pages 非常适宜托管静态网站，而且是免费的。

2.1 ReactJs

第三章已经解释，本程序的游戏界面基于 ReactJs 的经典教程。
ReactJs是一款用来构建用户界面的精良的JavaScript库，是由Facebook出品的开源框架。

2.2 Ant Design

Ant Design是阿里推出的开源React组件库，包含了丰富的界面交互组件以及幽美的设计风格。

3. 源代码

完全的源代码托管在 github 上：https://github.com/Jeff-Tian/tic-tac-toe-ai。
这里重点先容一下前面几章先容的机器学习的关键步骤代码：

3.1 目标函数的表示

程序里利用目标函数来对棋局打分：

getBoardScore: function (bitmap, weights) { weights = weights || Strategy.getInitialWeights(); let {lost, win, factors} = Strategy.getBoardStatus(bitmap); if (lost) { return { factors: factors, namedFactors: Strategy.getNamedStrategy(factors), total: -Math.PI / 2 } } if (win) { return { factors: factors, namedFactors: Strategy.getNamedStrategy(factors), total: Math.PI / 2 } } let score = Math.atan(factors.map((s, i) => s weights[i]).reduce((prev, next) => prev + next, 0)); return { factors: factors, namedFactors: Strategy.getNamedStrategy(factors), total: score };}

求出的分数即 score，把稳这个分数是x1到x5与权重的加权和再求arctan，从而让分数单调有界。
2.3详细地解释了x1到x5这5个自变量，在代码里，将它们放在了一个factors数组里。
这个factors 是由getBoardStatus来打算的，这里抽象成一个方法，好处是，如果要换自变量，那么这个打分的函数不用改变。
如前所述，自变量的挑选，并不是确定的。

3.2 检讨棋盘的边

上面的代码中有一个主要的函数：getBoardStatus，它的核心是去检讨棋盘的边，得到棋盘的状态。
在程序里，棋盘被表示成一个长度为9的数组，每个元素要么是1、要么是0、要么是-1。
分别表示当前宫格里是我方的棋子，为空以及敌方的棋子。
棋盘一共8条边，检讨棋盘的边的函数是这样的：

function checkSides(bitmap) { let d = 0;

let dead = 0; let w = 0; let c = 0; for (let i = 0; i < sides.length; i++) { let side = bitmap.filter((_, j) => sides[i].indexOf(j) >= 0); let negatives = side.filter(b => b === -1); let zeros = side.filter(b => b === 0); let ones = side.filter(b => b === 1); if (negatives.length === 2 && zeros.length === 1) { d++; } if (negatives.length === 3) { dead++; } if (ones.length === 3) { w++; } if (ones.length === 2 && zeros.length === 1) { c++; } } return {danger: d, lost: dead, chance: c, win: w};

}

3.3 函数逼近算法

函数逼近的过程，也即学习的过程。
这里表现为一个名字叫learn()的函数。
这个函数吸收两个参数，即上一棋局，以及当前棋局。
把稳之前2.2 提到，函数逼近算法，是不断用当前的权值，对新涌现的棋局打分来估计前一棋局的分数。
以是这个函数会利用同样的权重对前后两个棋局打分，并通过这个分数的差值，采取LMS方法来调度权重：

learn(lastSquares, currentSquares) { if (!lastSquares) { return; } let estimatedLastScore= Judger.getBoardScore(lastSquares, this.weights); let actualScore = Judger.getBoardScore(currentSquares, this.weights); let diff = actualScore.total - estimatedLastScore.total; for (let i = 0; i < estimatedLastScore.factors.length; i++) { this.weights[i] = this.weights[i] + 0.1 diff estimatedLastScore.factors[i]; }}

4. CI/CD：

采取了 Travis CI系统，只须要提交代码，Travis 会自动运行测试、剖析代码。
然后发布至Github pages。

七、评估以及后续事情：

本程序很好地演示了一个最大略的人工智能程序的编写步骤，不须要任何繁芜的AI框架，可以从0开始编写。
不过，仍旧存在优化的可能性，比如：

简化

对付目标函数的表示，有没有更好的或者更简洁的表示形式呢？是否可以进一步减少自变量的数量？

繁芜化

除了简化，还可以朝另一个方向发展，即迭代更繁芜的游戏。
比如，扩展棋盘，或者扩展成五子棋等等。

意见意义性

从游戏意见意义性上扩展，可以考虑增加一个用户系统，开拓出排行榜的功能，让纯静态网站变得动态等。

八、参考文献：

【1】https://zh.wikipedia.org/wiki/AlphaGo

【2】https://www.tensorflow.org/

【3】https://playground.tensorflow.org

【4】https://zh.wikipedia.org/wiki/%E4%BA%95%E5%AD%97%E6%A3%8B

【5】https://zh-hans.reactjs.org/

【6】https://zh-hans.reactjs.org/tutorial/tutorial.html

【7】https://zh.m.wikipedia.org/zh-cn/%E4%BA%BA%E5%B7%A5%E6%99%BA%E8%83%BD

【8】https://zh.m.wikipedia.org/wiki/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0

【9】[美]米歇尔(Mitchell, T.M.).机器学习[M]. 曾华军等译.北京：机器工业出版社，2003.