人工智能如何解决《水晶迷宫传奇》中的古老谜题?

20世纪90年代,英国有一部流行的电视剧叫做《水晶迷宫传奇》(The Crystal Maze),其中有一个谜题可以用来解释人工智能遇到的一个难题。

20世纪90年代,英国有一部流行的电视剧叫做《水晶迷宫传奇》(The Crystal Maze),其中有一个谜题可以用来解释人工智能遇到的一个难题。这个谜题出现在未来世纪区( Futuristic Zone),这是四个区之一,参赛者会在其中搜寻「时间水晶」以赢得时间来赢取最后水晶宫中的大奖。

在电视剧中,这个谜题从没有在2分钟的时间限制内完成过。它由若干红色圆圈以及连接它们的网络组成,墙上写着要求:「相邻圆圈内不能有连续字母。」旁边放着一堆红色圆盘,印着A~H的字母,可以放入圆圈内。

那么,正确的方法是什么呢?一开始,我们可以先确定,哪些圆圈是最困难的部分。只需要观察一下,你就会选择中间的两个圆圈,因为它们连接的圆圈最多。那么,A和H就是最适合这两个圆圈的选项,因为它们都只有一个邻居(A只和B相连,H只和G相连)。我们可以把它们放入下面这个图中。

现在,我们可以做一些推理,来排除掉其他圆圈中不能填的选项。比如说,左上角的圆圈和A和H都相连,由于字母不能连续,所以排除掉B和G。右上角、左下角、右下角的圆圈也可以用同样的方法,排除掉B和G。

最左边和最右边的圆圈需要分别对待,因为它们分别与A和B相连。左边的,我们可以排除B,右边排除G。

在仔细看看剩下的选项,只有最左边的圆圈可以选择G,只有最右边的圆圈可以选择B。只要把G和B放进去,其他四个圆圈中也可以排除掉一些选项了。

现在,我们再猜一猜。左上角圆圈还剩3个可能性C、D和E,那就先选第一个C吧。这样,右上角圆圈就排除了D。左下角就只能是D,而右下角就只能是F。这样,我们就解出了这个问题。如下图所示。

决策,还是决策

这个谜题属于一个很大的决策问题类型,在生活中很常见,例如医院或工厂的名字登记策略,调度公交车或火车,或者设计医疗实验。为了帮助我们得出最好的解决方案,人工智能的一大挑战就是开发出一种通用的方法,对这些问题进行表征和推理。

其中一个方法是所谓的约束满足问题( constraint satisfaction problem)。就像水晶迷宫里的谜题一样,满足这个模型的问题都涉及到如下这些方面:一组需要进行的决策(比如,把红色盘子放入所有圆圈中);一组可能性(用所提供的A~H圆盘);一组约束条件,只允许某些可能性的组合出现(如,相邻圆圈内不能有连续字母)。如果你把这些问题的要求放入一个约束求解软件中,它就会尝试解决这个问题。它解题的方法与我们很相似:将猜测(我们称之为「搜索」)和推导结合起来,并基于目前的决策排除掉那些无法作为解的可能性。

在这个领域,程序员最大的挑战就是,当输入的问题变得越来越多时,会变得越来越难找到解。这与软件「猜测」答案的方式直接相关。尽管在简单的谜题中,我们的猜测被证明是正确的,但人工智能(AI)却常常将我们领向死路。庞大的问题中,可能存在大量的可能性,同样也存在大量的死路。

其中一个关键问题是,有没有一种不需要钻进死胡同的答案搜索方法?目前我们并不知道。这与计算机科学中两个最重要的开放式问题有关:P问题和NP问题。为此,美国克雷数学研究所悬赏1百万美元征集答案。从本质上说,它就是在询问,如果一个问题的答案能被计算机迅速检查,那这个问题是否也能被计算机迅速解决。

目前流行的答案是否定的。如果真是这样,我们的软件不得不搜索所有可能的猜测,那我们必须让它的效率尽可能的高。这里有一个重要的因素是:搜索策略——我们想让计算机下一步聚焦在什么决策,以及我们赋予它的权重是多少。还有一件非常重要的事情是,特定问题的要求是什么。可以选择把谜题直接套入约束满足的模板,但是在真实生活中,还有很多其他选项。只有选择了正确的策略和模型,才能在实际可行的时间内迅速找到解决办法。

现在,我们的水平已经比10年前高很多,目前的约束求解软件可以解决比10年前复杂很多的实际问题。它被用在科学项目中,例如去年的菲莱彗星着陆器。它还能为灾害事件编制更好的疏散计划。

约束求解在调度问题中非常成功,但是,还有许多其他的AI工具可以解决更多类型的问题。例如,命题满足、进化算法、数学规划技术等,它们可以组合使用来解决问题。一旦计算机能够完成这样的分析,我们就能往前迈进一大步。

机器之心,最专业的前沿科技媒体和产业服务平台,每日提供优质产业资讯与深度思考,欢迎关注微信公众号「机器之心」(almosthuman2014),或登录机器之心网站www.almosthuman.cn查看更多精彩内容。