由 AlphaGo 看演算法 聊聊演算法最基本的元素

所属栏目:区域专业 2020-07-24 23:50:50 来源于:http://www.058am.com

由 AlphaGo 看演算法 聊聊演算法最基本的元素

在近期科技界最引人注目的新闻话题,就是电脑与人类进行围棋对弈,名为 AlphaGo 的电脑击败世界排名相当高的韩国九段职业棋士李世乭。如果大家还有印象的话,在 1997 年时由 IBM 所发展的深蓝击败当时的世界西洋棋冠军 Garik Kimovich Weinstein,也引起相同的注目,电脑演算速度经过 18 年的进化后,终于可以在複杂度高上许多的围棋中,击败世界上前几强的职业棋士。

 

这项电脑技术上的成就,也让这 18 年间的电脑运算速度成长有了一个重大里程碑,也就是说在相同时间限制内,在过往的电脑仅能有业余五段的实力,但这次以分散式的运算架构,构筑高达 1920 核心 CPU 与 280 核心 GPU,并搭配 Monte Carlo tree search 为基础的演算法,来击败围棋世界冠军。能达成这样的里程碑,其实要有两个重要的关键,其一就是演算速度相当快速的电脑设备,另外一个就是合适又有效率的演算法,两者缺一不可。

其实写这篇前一直非常挣扎,如果写得太详细,那可能一篇文章要好几万个字,而且大家可能没有兴趣看,所以就学生时代所学习的知识,以尽量以简单明了的方式来为大家说明演算法的基本元素,当然实际在设计演算法时并没有那幺轻鬆自在,毕竟在研究所时也花了将近一年来研究验证。

 

演算法其实简单来说,就是找出解答的方式,这解答不一定是最好的结果,但是一定是合理的结果。就像是今天我们要解决 ”怎幺由新竹到台北” 的问题,就会有好几种不同的答案,你可以搭高铁、搭火车、搭客运、开车、骑 Gogoro、走路......等上百种方式,也会有上百种路线,这些都是解决方法。因应每个人的需求或是目的不同,所以也会有不同的方法。

举个比较常遇到的问题,就像是常常会有读者问我哪一支手机比较好,这也是有成千上百的解答,因为每个人因为其使用方式、经济状况,会有不同的选择。所以接下来我会问你有没有哪个品牌不要?你期望的价格範围?你比较想要哪个功能?经过几个问题的筛选后,就会找出一个或多个答案,这就是演算法的过程,这答案可能不是每个人的最好答案,但是却是经过这个人的喜好订定评估指标,并在许多条件限制下所得出来的合理最佳解。

 

 

好的评估指标

每一个问题都有成千上百个答案,究竟哪个答案比较好呢?这时候就要利用评估指标来做为好坏的依据。那什幺是评估指标呢?我们来使用 “怎幺由新竹到台北” 作为例子来解释。今天如果某人希望用最短的时间从新竹到台北,我们所期待的就是以最少通勤时间为主,评估指标就是最短时间;如果某人想要的是最节省的方式,那评估指标就是花最少的钱。演算法中的评估指标非常重要,这指标将用来计算评估你解答的品质,用以找出好的答案。当然,评估指标可以是综合指标,也就是可以把两个以上的指标放入一个评估的算式中,这接下来我们会继续聊。

 

 

合理的基本假设

当有了好的评估指标后,你就可以把有可能的 “怎幺由新竹到台北” 方式,来套入评估指标中计算,但这其中有个非常大的问题,底下直接用举例的方式说明。

如果说 “怎幺由新竹到台北” 我们以最短时间来做为评估指标,我们就要开始考虑高铁、火车、开车…等交通方式来评估,大部分的朋友一定会选择高铁,但如果不计成本来说,高铁不一定是最快速的,今天如果请 F1 车手开着顶级跑车由新竹载你到台北呢?或是有直升机专程接送呢?

所以在这样的状况下,我们要有基本假设,把目前某人能力範围外的选项拿掉,例如说他有惧高症,那我们就会把直升机选项拿掉;他不想花超过 1000 元,就可能把顶级跑车选项拿掉…,这样所找到的解,才会是合理又正常的解。

但有没有人想要便宜又快速的方式由新竹前往台北呢?这绝对有,在这状况下,我们又要回到评估指标那边,把时间与花费做成一个综合性的指标,简单说,就是把时间与花费都加上权重来衡量。这时候你可以问那个麻烦的人说,速度与金钱对你由新竹前往台北的重要性,如果速度佔 70% 重要,金钱佔 50% 重要,那你的评估指标就可以做成 速度* 70% 金钱 * 50%,写到这里专业人士一定会嗤之以鼻,因为我少了一个速度与金钱的标準化,但写那个就太过麻烦了,反正知道要标準化的人也不用看这篇啦!

 

 

选择演算法

有了评估指标、基本假设后,接下来就要拟定演算法了,对于正常的大家来说,最直觉简单的方式,就是把有可能的选项一一放入评估指标中,看看哪个比较好就选哪一个,这就是所谓的穷举法。穷举法对于小型的题目来说,是非常好用的方式,因为你不用花时间去思考其他演算法,因为使用穷举法所花的时间都比你验证其他演算法来的短,但对于大型题目来说,穷举法就不是个好方法。

这次就直接用主题所说的围棋来举例,围棋有 19*19 的位置可以下,所以第一手就要考虑 361 种可能,如果是这样就简单多了,但事实并非如此。因为第一手下完后,你必须开始考量对手下的位置,也就是有360 个可能,接这还要考虑换你下的位置一直到分出胜负为止,中间还要考虑到子被吃掉后的空间,所以光想就头皮发麻,更不要想说用穷举法了。

那有没有更快速的方式,当然有,就像是这次 AlphaGo 所採用的 Monte Carlo tree search并搭配Policy Network 与 Value Network 所设计的演算法。另外我在研究所的论文用的禁忌演算法、模拟退火法…也都是历史久远但都经过各种题型来演化修正的利害演算法。这些方法都可以在反覆求解的过程中,去除胜率较低的方式,得到一个好的解,但并不一定是最佳解。而 AlphaGo 的演算法也是,他在有限时间内,只能找出胜率最大的方式,并无法找到 100% 获胜的走法,所以电脑效能绝对是与演算法同等重要的关键所在。

 

 

验证演算法

既然说演算法没有办法 100% 找到最佳解,那你怎幺证明你的解法是好的?最一般的方式我们会从相同题目背景下,以小规模的方式找出最佳解进行验证,一般来说就真的会使用穷举法或是保证可以找到最佳解的方式来证明你的演算法是好的。若以围棋为例,会将棋盘缩小到 10*10 甚至更小,在验证过程中,会以下围棋时的演算法与穷举法来对弈,如果最后的棋力不分上下,这就表示在小规模中可以有最佳解或是很好的解,这也可证明演算法的实力。而在验证演算法时,会花掉非常多时间,因为上一段也说明了穷举法的组合相当庞大,以原题目规格来说,可能都要好几年才求的出答案,所以一定要缩小规模来验证。

另外,在同一种题型下,大多会有 Benchmark 的资料可参考,也就是前人在相同题型下得到的答案,如果你可以有比他好的答案,又花比较少的时间(电脑等级也有差异),这表示你的演算法是很优秀的。

 

上面聊到的,就是完成一个演算法所要的基本元素,当然其中还有很多机制,可以让你更快找到更好的解,希望大家可以由这些简单的说明,更了解演算法一点。而回到 AlphaGo 来说,他真的是无法击败的吗?事实证明他是可以击败的,这也是每个演算法中因为演算时间限制下,只能找到比较好的解,但因为运算速度太快,所以可以考量的棋路会比人类高出许多,所以是不容易被击败的。过几年后,当电脑运算效率更好时,或许真的可以让人类无招架之地,但也仅限于围棋这还算有範围的问题上,要像是电影 A.I. 人工智慧的机器小孩一样有思考,还有相当长的一段路要走。

由 AlphaGo 看演算法 聊聊演算法最基本的元素

相关文章