如何战胜 AlphaGo?

李世乭今日再输一场,比分 0:3 负于 AlphaGo,与百万奖金无缘了。而 AlphaGo 今天的表现异常完美,开局 45 分钟左右,李世乭已经招架不住。赛后英文解说 Michael Redmond 更是直言,AlphaGo 很有可能成为继吴清源之后又一位开创新格局的历史性角色。

虽然我不懂围棋,但可以从计算机的角度来介绍一下 AlphaGo 有哪些弱点。看了一些赛后评论,发现多数都是从围棋的角度来讲棋,而忽视了计算机的东西。所谓“知己知彼”,了解 AlphaGo 是怎么工作的,才更有可能击败它。

先说说 AlphaGo 的工作原理。已经有一些文章详细地介绍过了,这里就简单说一下。AlphaGo 决策的时候有两个步骤,一是选出下一步棋所有可能的位置(由 Policy Network 做出),二是在这些可能的位置里,精算一个最优的(由 Value Network 做出)。新闻中提到的 AlphaGo 每天几千万盘棋,都是在训练 Policy Network,就是培养它尽可能找全所有价值高的点。而 Value Network 似乎是在比赛中实时计算的,不需要训练。

Value Network 的工作原理和自然人无异,就是一步一步推演,看看之后几步的胜负情况。这一步骤在讲棋的时候经常用到,嘉宾和主持人都会用棋子摆一摆,并揣测棋手下一步的动向。Value Network 也是这样做的,只是它算得特别快而已。我看了一些现场解说,一般都是算出之后的五到十步棋左右,越到后面,计算的复杂度越高。这对人和电脑都是一样的。

影响 Value Network 精确程度的一个重要因素是时间,比如给它五秒钟,它可以算到五步之后,给它十秒钟,它可以算七步。我重看了一下前两场比赛,刚开场的时候,AlphaGo 大约是每 60 - 80 秒下一步棋;而到了中盘的时候,决策时间会上升到两分钟以上。这是因为刚开场的时候,每个位置的重要性都差不多,算了几步之后发现各个位置都不错,就随便选一个即可。而到了中盘,一个位置可能要算上几十步才能确定它的重要性,于是耗时就上去了。

想要打击 AlphaGo,就必须尽量不给它时间做计算。让它计算的步数减小,提高犯错的可能性。要做到这一点,只有一个办法,增加 Policy Network 选出来的位置的数量。假设一个位置它要算 10 秒钟,那么 10 个并列的位置,它就要算 100 秒,这样就大大地增加了时间上的消耗。时间耗尽之后进行读秒阶段,这个阶段中,AlphaGo 大约 30 秒左右就会给出计算结果,估计是在程序中强制设定了的。很明显,30 秒和 2 分钟的计算相比,30 秒算得不清楚,更容易犯错。李世乭在第二场成功地把 AlphaGo 拖进了读秒阶段,但依然没有把握住,有点可惜。当然主要原因是当时李世乭自己也开始读秒了。

由于 AlphaGo 并不会在局部战场鏖战很久,即它没有局部战场的概念,每次选位置都会从整个盘面入手。虽然这样有很好的大局观,但也损失了不少计算性能。如果李世乭能够尽可能多地制造出重要性差不多的位置,可以极大地增加 AlphaGo 的计算量。而 AlphaGo 的应对方式,要么是增加计算时间,要么是在没算完的时候直接给出一个临时最优解,无论哪种方式,都对李世乭有利。

另外网络上有人提到下模仿棋。虽然模仿棋在围棋界不是什么光彩的事情,但对 AlphaGo 确实有效。所谓的模仿棋就是利用棋盘的对称性,对方在哪里落子,自己就在对称地方落子。对人类而言,模仿棋是有破解招数的(详情略);而 AlphaGo 是否有理解对方在下模仿棋,这一点还不清楚,需要我们的“高级软件测试工程师”来验证一下(笑)。如果 AlphaGo 没有对应模仿棋的特殊策略,按正常情况来选位置,那会相当于自己左右互搏,实际上也会产生一盘不错的棋。

模仿棋还有另一个好处,就是李世乭所消耗的时间不多。在前期节约一些时间,就可以把更多的时间放在中盘拉锯上,就更有可能获得胜利。由田渊栋的赛后分析来看,第一局中盘李世乭曾经一度扳了回来。所以有更多的时间放在中盘,李世乭更有希望赢得比赛。

无论如何,这场比赛都会被载入史册。虽然已经连输三场,还希望李世乭可以放下包袱,贡献出两场更为精彩的对局。

两年胜过一百年

AlphaGo 在昨天和今天两场比赛中以较大优势战胜李世乭,基本已经宣告了现代围棋百年基业的崩塌。围棋会成为国际象棋之后,另一个人类被计算机程序完全战胜的棋类项目。在战胜了棋类中最复杂的围棋之后,计算机算法也将统治所有的棋类游戏。

现代围棋从二十世纪初在日本兴起,由吴清源等宗师级人物开创,发展到现在已有一百多年,经历了数个时代。而 AlphaGo 从投入使用到战胜李世乭不超过两年。有消息说在 2014 年 4 月 AlphaGo 在弈城对战平台上注册了帐号用于实战练习,起始等级为业余五段。短短两年之内,实力从业余五段上升到可以和顶尖职业选手叫板,这样快速的进步令众多职业选手汗颜。

我对围棋没有那么了解,不过我可以从计算机的角度来讲解一下大家对 AlphaGo 的一些误区。

假设李世乭五番棋不敌 AlphaGo,中国的职业高手能否和 AlphaGo 一战?

如果计算机程序两年时间可以做到人类一百年才能达到的水平,那么全面超越人类也就是几个月的事情。1997 年深蓝在国际象棋上战胜世界冠军,到 2006 年人类最后一次战胜计算机,程序用了十年的时间赢下了国际象棋。而这一次,或许 AlphaGo 会用更短的时候全面超越人类。人类高手想要挑战 AlphaGo 还得趁早。

为什么 AlphaGo 依然会下出一些“臭棋”?

据 DeepMind 的开发人员表示,在第一盘棋中,AlphaGo 全程认为自己处于优势状态。当然程序可能有 bug,但更重要的一点是,人类认为某些下法不好,是真的不好么?人类下围棋,一天不过一两盘,顶尖高手两三天才能下一盘棋。以这种速度,在一两百年之内积攒出了各种理论、定式。而 AlphaGo 一天则可以自己和自己对战上千盘棋,对于一些围棋理论,显然 AlphaGo 会有更全面的看法。这些臭棋经过仔细研究,说不定会被证明是一步好棋。

不用正常围棋的路数,是否能迷惑 AlphaGo?

在人与人对战时,如果对方下了一步看不懂的棋,选手肯定会猜测这是一步好棋,还是故意晃点我。而 AlphaGo 还不具备这种能力,对于无论是有意还是无意的落子,AlphaGo 都会以精确地计算来应对。换句话说,AlphaGo 不会轻敌。

天网是否已经来临?

如果 AlphaGo 故意输掉了一盘,那才是令人恐惧的。如果你对计算机行业不了解,可以去搜索一下“图灵测试”。能通过图灵测试的程序才具有“思维”的能力,而其它的程序都只是按照人类的指令运行而已。目前还没有可以通过图灵测试的计算机程序。

收官阶段李世乭是否会有优势?

众多场外评论说收官阶段的“打劫”会对计算机程序造成一定的影响。我猜这一说法的原因是之前多数程序都处理不好这一步骤。至于 AlphaGo 懂不懂“打劫”的要领,暂时还无人可知,所有公开的对战中,AlphaGo 都没有走到“打劫”这一步就已经赢了。

从计算机算法的角度来说,收官阶段的计算肯定比中盘来得简单。举个例子,玩过”数独“的朋友都知道,在一个数独局面中,如果局面是全空的,很简单,随便填数字即可;如果局面差不多都满了,只有少数几个空,那也很简单,按着规律填。数独最难的局面,就是半满的局面,每个空都有多种可能,也有很多限制,要推演出每一种可能,需要大量的时间。围棋也一样,最需要计算的是中盘阶段。过了中盘之后,每多下一个子,计算复杂度呈指数级下降,计算机会觉得轻松了很多。即使中盘战和,在收官阶段,计算机也会具有巨大的优势。这也是为什么 AlphaGo 的多数比赛在中盘过后就显示出不可逆转的优势。

Google 内部对这场比赛怎么看?

很明显众多码农都很兴奋,有人甚至要求 DeepMind 团队在比赛时内部直播 AlphaGo 的决策过程,以增加观赏性。不过这一要求被 DeepMind 拒绝了,大概是不想泄露任何可能影响比赛进程的信息。

经典面试题 之 按位奇偶性

整数的奇偶性大家都知道,就是看它能不能被2整除:能整除就是偶数,不能整数就是奇数。

那么我们来研究一下按位的奇偶性:一个整数的二进制表示中,如果‘1’的个数为偶数,那就定义这个数是偶数,反之是奇数。完成以下函数,如果这个整数按位是偶数,返回0,奇数返回1。

很容易想到的一个方法是,按位运算嘛,把其中的'1'的个数算出来,再算个数的奇偶性就行了,比如:

很容易证明上述的方法是正确的。但是它足够快吗?uint64_t是64的无符号整数,平均情况下也要几十次迭代才可以算出结果。

有没有更快的方法呢?上面的方法实际上可以算出一个整数的二进制中有多少个"1",但我们并不需要这多余的信息。仔细一想,不用加法,异或就可以了。在异或运算中,两个1异或变成0,两个0依然是0,但是1和0在一起就是1,并且关键的是异或运算满足交换率,就是多个0和1的异或,不论顺序怎样,算出来都是同样的结果。

于是可以推导出,只要每次把这个整数折半,一半异或另一半,这样在6次之内算出结果。比之前的几十次要好很多了。

能不能再给力一点?

结论是可以的。上述的方法中,需要计算长度为2、4、8、16、32位的整数的异或,如果我们能预先算出所有的16位整数的运算结果,保存起来。由于运算结果只是0或1,只需要32K的字节的空间,不算多。这些保存的结果,可以把上面的方法优化到3次计算。如果这个函数被经常使用,这种打表的方式还是很有效果的。

具体的代码就不附了,也就是一堆的异或运算……

排序的方法

此文谨献于那段徘徊在AC、WA和TLE之间的时光……

排序,就是把一堆杂乱无章的元素,按照一定的顺序排列起来。比如以前在学校里,考完试老师发考卷的时候,会按照分数从高到低来发,于是他就需要事先把考卷按顺序排好,然后在上课的时候发掉。把考卷按分数从高到低排好的过程,就可以称为排序。

排序的方法有很多种,有一些在日常生活中可以用得到,另一些则是仅用于计算机领域,因为计算机的思考过程和人类多少有点不一样。

从一个简单的例子开始:扑克的“争上游”玩法,假设没有顺子和葫芦(即三拖一或三拖二)的规则,所以手中的牌按照牌面的大小来排序是比较合理的。发牌完成之后,我一般会一张一张地摸起面前的牌,每摸起一张牌,就把它插入手中牌的相应位置,并保证手中的牌有序。比方说,摸起第二张的时候,如果它比第一张大,就放在第一张的后面,否则就放在第一张的前面;摸起第三张的时候,就按大小放在第一张之前、第一第二张之前或者第二张之后;以此类推。这样把面前的牌都拿到手中时,手中的牌就是有序的。这种方法被称为插入排序(Insertion Sort)。(插入排序有一个进化版叫做希尔排序(Shell Sort),有兴趣的同学可以自已研究。)当然也有些人不喜欢这种方法,他们一下子把所有的牌都拿起来,这时候手里的牌是无序的,然后他们会做一个操作:(假设一共有12张牌),先在所有的牌中挑出牌面最大的一张,比如黑桃2,放在所有牌的最后面,然后在剩于的11张牌中,挑出最大的一张,比如红桃A,放在黑桃2之前,以此类推,也可以把牌都理好顺序。这种方法叫做选择排序(Selection Sort)。

而在“八十分”的玩法中,上述两种排序方法就不怎么适用了。按照八十分的规则,手中的牌通常是按照花色来摆放的,先把同花色的牌放在一起,然后再对四种花色,分别调整同花色牌的顺序(假设是需要有顺序的)。这种方法叫做桶排序(Bucket Sort),或者基数排序(Radix Sort)。每种花色可以视为一个桶,先把牌按照它的花色分别扔进这四个桶里,然后再对每个桶中的牌分别进行排序。桶排序在一定条件下可以进化成计数排序(Counting Sort),这里不多说了。

桶排序和前面的插入排序、选择排序有一点不一样。在桶排序中,所有的元素都被放到相应的桶里之后,每个桶里的排序方式,可以是不一样的。比如第一个桶中使用插入排序,第二个桶继续使用桶排序。从另一个角度来说,各个桶之间是相互独立的,排序操作可以同时进行。也就是说,如果扑克牌的数量很多,可以先把牌放进桶里,然后找多个人,每个人对一个桶进行排序,这样的并行操作可能提高效率。而在插入排序或者选择排序中,想要并行操作就相关来说复杂一点。

另一种可以进行并行操作的方法是合并排序(Merge Sort),与桶排序不同的是,合并排序先把要排序的扑克牌分成几份,每份都是没排过序的,然后分别对每一份进行排序,于是每一份内部都是有序的了(假设顺序是从小到大),最后要做的操作是,比较每一份扑克牌的第一张,选出最小的一张牌,由于每一份牌都是从小到大有序的,所以选出来的那一张一定是所有牌中最小的,把这张放到一边,再重复同样的操作选出一张最小的牌,放在刚才那张牌的上面,以此类推,就可以达到排序的效果了。不难想象,对每一份扑克牌的排序操作,是可以同时进行的。

以上几种排序方法是日常中能见到的,下面来说说仅用于计算机中的排序方法。

首先,也就是最基本的就是冒泡排序(Bubble Sort)了。对于一个长度为n的数组A,从i=0到n-2,比较A[i]和A[i+1],如果A[i]>A[i+1],则把它们交换,这样一次循环下来,A[n-1]就是数组中最大的数(证明略:P),然后重复n次,就可以把整个数组排序了。顺便复习一下算法复杂度,冒泡排序的时间复杂度是O(n²),空间复杂度为O(1)。

剩下最著名的快速排序(Quicksort)了,顾名思义,它是目前公认最快的内排序算法。(插一句,内排序是指所有需要排序的元素都存放在内存中,如果内存不足以存放所有的元素,由于外部存储器速度的制约,排序算法需要进行一定的调整。)快排的基本思想是,先在数组中取一个元素x,然后整理这个数组,使x左边的元素都不大于x,而x右边的元素都不小于x,然后再对x左右两边分别应用快排算法,最终将整个数组排序。不难发现,快排算法的好坏取决于元素x的选取,如果每次都很不巧得选了最小的元素,快排对退化成选择排序。一般来说,快排的时间复杂度为O(nlg(n)),空间复杂度是O(lg(n))。和合并排序一样,快排是分治思想一个典型定用,也就是说,它可以使用并行算法优化。

以上几种就是基础的排序方法了,还有一些由它们演化、改进出来的算法,就不多提了。

顺便复习一下复杂度,在单线程情况下,理论上最快的是桶排序(或者计数排序),可以达到O(n),但是需要使用大量的空间。一般情况下最快的是快速排序,O(nlg(n))时间,O(lg(n))空间。其它被快排BS掉的方法,多数是O(n²)时间,O(1)空间。

经典面试题 之 查字典

题目的大意是先给出一些字符串做为字典D,然后再依次输入单个字符串A做查询,如果A在D中,则输出Yes,否则输出No。比如:

字典:Hello、World、Time、Table
查询:Hello、Get、Found、Time
输出:Yes、No、No、Yes

很明显这道题可以用HashSet很简单地解出来,O(n)时间构造,O(1)时间查询/次。但是HashSet有一个问题,就是使用的内存比较大,字典中每个单词都要存一遍,而其中有些空间是浪费掉的,比如:

  • Astray
  • Astrology
  • Astronaut
  • Astronautics

这几个单词的开头几个字母都是一样的,它们可以被压缩起来,只保存一份就可以了。那什么样的数据结构可以共享几个元素的头部,而分离它们的尾部呢?比较常用的是树形结构,根部是共享的,树枝就分叉了。但是似乎传统的二叉树(Binary Tree)不能很好地解决字典的问题,因为它一个结点只有两个分支,而单词的一个字母后面可能有26种字母的可能,(假设单词都是小写英文字母),于是就想到了26叉树。树的结构大约是:

其实它的学名是Trie,标准的实现要更灵活高效一点,这里只是用26叉树来举个例子。

将单词插入字典,方法是每个节点保存一个字母,单词从前到后的字母顺序就是树中从上到下的路径。

在字典中查找单词,方法和插入时类似,只有当整个单词都走一遍,并且当前节点的complete为true中,才表示单词已找到,返回true:

不完全测试:

经典面试题 之 按单词逆序

题意大致是:给出一个字符串,将其中的单词的顺序颠倒,而单词本身不变,即输入"ab bc cd de",输出"de cd bc ab"。

第一次听说这个题目是在大学里,告诉我题目的那个人,没有留给我思考的时间,就直接把答案说了,所以我也不知道能不能独立想出这道题的答案。这道题的解法有很多,其中描述起来最简单的是,先把整个字符串倒序,再把每个单词倒序。

以下是代码:(这个代码假设输入数据中只包含空格和英文字母)

以下是测试数据,不是很全,应该还很多吧……

经典面试题 之 在单调矩阵中查找元素

题目的大意是要求在一个N*N的矩阵中,找出一个特定的元素,这个矩阵满足两个条件:1)每一行的元素,从左到右严格递增;2)每一列的元素,从上到下严格递增。

这道题的限制太多,以至于很容易想到结果。元素都是递增(或者递减也行)的,要在一行上找元素,很显然用二分搜索了,那么一共N行,时间复杂度就是O(N*logN)。显然这不是最快的方法,要不然题目就没有意义了。

继而想到每一行递增,每一列也递增,那么主对角线也是递增的,而且满足一个很好的性质:

A11 A12 A13 A14 A15 A16 A17

A21 A22 A23 A24 A25 A26 A27

A31 A32 A33 A34 A35 A36 A37

A41 A42 A43 A44 A45 A46 A47

A51 A52 A53 A54 A55 A56 A57

A61 A62 A63 A64 A65 A66 A67

A71 A72 A73 A74 A75 A76 A77

假设以上矩阵A满足递增的性质,那么对于A55而言,[A11, A55]这个矩阵中所有的值都不超过A55,而[A55, A77]这个矩阵中所有的值都不小于A55。所以说,如果要找个值比A44大,而比A55小,那么它一定在[A15, A67]和[A51, A76]这两个矩阵中,于是搜索规模直接减少了一半。对于[A15, A67]和[A51, A76],继续套用之前的算法就行了。

代码略,会写二分搜索的话,没几分钟就写完了。算法的总体复杂度大约是O(logN * logN),没有详细得证明过,若有错误请指出。