如果发明一种机器学习难以战胜人类的棋类规则，这种规则应该具备什么样的特点？

源济

如果发明一种机器学习难以战胜人类的棋类规则，这种规则应该具备什么样的特点？

作者 / 宜城漫士

这个问题乍一看是一个很荒唐的问题，但仔细咂摸有很多值得玩味的东西。

首先需要在问题定义里明晰这样一件事：机器学习战胜人类很困难，这里的困难到底包不包含实现（Implementation）层面的的难度？

很多高赞回答的本质其实都是在这个维度里设置“恶心”，比如让状态的记录变得棘手、棋盘的形状变得不规则、提高维度、增加环境的不确定性等等，其实充其量只是说“恶心恶心程序员”而已。这样设置规则本质上提升的是“代码复杂性”而不是问题本身的“计算复杂性”。代码复杂性诚然是 AI 进军一个具体问题的重要阻碍，但算不上是本质的阻碍。AlphaZero 乃至 MuZero 之类的工作已经表明，只要可以用 tensor 表征整个游戏，终究可以自己学着怎么理解这个游戏并优化策略的，都不是个事儿。

所以，我认为这个问题更重要、更本质的方面应当是：假设我们有一个理想中的 Oracle，可以自动完成所有现实中代码层面的复杂难题，从机器学习（强化学习、深度学习等等）这个方法本质性的能力边界出发，是否可以找到一个简单的实例，使得解决这个问题（或者说达到与人类媲美的程度）是一个从计算本质上来讲困难的事情？

“从计算上来讲本质困难的事情”在理论计算机科学中有一个现成的概念，就是 NP Hard 问题。大意是说，如果存在一个传统图灵机算法，可以在多项式于这个问题规模的时间里解决这个问题，那么就可以在多项式时间里解决任何一个非确定性图灵机(Non-deterministic Turing Machine)在多项式时间里解决的问题（NP problem）。

说起来很抽象，举个 NP Hard 最简单的例子之一：

Subset Sum 问题：给 n 个数字，判断是否可以把这 N 个数字分成两个集合，使得两边的和是相等的。

这个问题看似简单，实则在复杂性的本质上，不存在比穷举所有

个非空子集更好的办法。换言之，你很难（实则是几乎不能）在 n 的多项式的时间里找到这个问题的解答。如果你能，那么恭喜你，你已经解决并且证明了 P=NP 这个人类难题，可以去领千禧年大奖的一百万美金了。

一切的机器学习算法（无论是强化学习还是神经网络），本质上依然是基于确定性图灵机的传统算法，那么就要受到 P 问题本质难度的约束。所以，在这个层面上的思路，应该是“如何将一个本质非常复杂的 NP Hard 问题包装成一个棋类问题”，从而高枕无忧的声明：一切现有的算法都不能有效的解决它。

但是且慢，这里还有两个最大的问题：

1. 当我们提到这些“计算复杂度”的时候，我们讨论的都是“渐进复杂度”（即 Asymptoptic Complexity）。啥意思呢？我们是设棋盘的大小是

，然后考察计算复杂度随着 n 的增加趋向于无穷时所增加的速度。在这个意义上定义“广义棋类游戏”后，我们才能判定某一个棋类游戏（比如围棋）是很难的（EXPTIME-Complete）。

https://en.wikipedia.org/wiki/Go_and_mathematics#cite_note-sipser1980-2

可是，在日常真正的棋类游戏中，我们通常会假定棋盘、棋子等数量是有限的（受限于物理实现）。而一旦将 n 的规模定下来，这个问题立刻变成一个本质状态数量有限的问题，你能定下来的是一个虽然可能海量、但本质终究有限的问题规模。我们希望借助计算复杂度压倒 AI 的目的会大打折扣。

2. 在这个层面上，19 路围棋其实已经足够复杂了。早先一直说“围棋是迄今为止人类创造的最为复杂的棋类游戏，没有之一，其可能状态数比宇宙中的原子都要多”云云。可是 AlphaGo 依然成功吊着人类打，颠覆了以往我们“围棋智慧对 AI 高不可攀”的认知。

其实说到底，从真正的“围棋之神”、也就是能够给出每一个局面的胜负判定和最佳下法的 Oracle 看来，AlphaZero 依然还是一个弟弟，远没有达到所谓“解决 19 路围棋”的地步。可是，它采用了非常好的近似算法（Approximation Algorithm），使得它对于当前状态的策略、估值函数相较于真实判断非常接近，至少是远超人类，这才达到了吊着人类打的水平。

3. 因此别忘了我们的另一个目的约束：让人类赢。我们说了这么多，只是在想着怎么让 AI 输，却从来没有想过让人类占据独到的优势。而且，看起来我们处于一个非常尴尬的境况：我们想用本质计算复杂性极为复杂的问题来让 AI 麻爪，可是棋类游戏本质有限的规模，使得 AI 的近似算法总可以找到挺好的解，而人类却已经在这个“难度起飞”的过程里被打爆了。

从而，我们终于来到了这个问题最有意义的层面：人脑智能相较于这些机器学习的算法而言，究竟在计算本质层面上有什么超越图灵机的优势？如何找到这样一个实例？甚至……如何证明？这才是思考这个问题最有意义、也是最深刻的路向。

我个人对于这个问题的理解是：

第一，能耗。麦克斯韦妖的思想实验已经表明，对信息的处理本质上是需要消耗能量的，而对于复杂棋局的计算涉及海量信息时，其消耗的能量是惊人的。人脑虽然在绝对的计算水平上稍逊一筹，但是如果考虑到消耗能量和处理信息的比值，依然是极其优秀的（训练一个 AI 需要核电厂半个月的电力，训练一个人只需要十年的馒头）。能否有一个理论框架描述这个问题？

第二，类似视觉这类任务的理解力。其实，对于计算机而言有一个有趣的悖论，那就是对人而言复杂的事情对计算机而言很简单（比如超大规模的算术运算，在棋局的博弈树上游走之类），可对人而言很简单的问题对计算机来说却很复杂（比如给一张图片，识别出每个像素的归属，并还原出三维的场景）。人类的视觉中枢处理视觉信息的效率和能力令人惊叹，而且是生物经过大自然上亿年的演化得到的。从一个矩阵的像素中完成对现实世界“实体”的理解这件事，也许严格形式化下来也是一个人能够战胜人工智能的问题。

综上所述，一个现阶段最简单的答案是：双方各摆一枚棋子，需要向前行进 100 格到达终点，先到终点者赢。控制游戏双方的能量使用，每次让玩家看带噪声污染的图片验证码，识别正确往前走一步，错误往后退一步（起点不退）。

这个棋，AI 想赢人类，本质等价于彻底解决计算机视觉的理解问题，短期内几乎很难解决。

而真的老老实实在本质上是“有限状态转移的马尔可夫决策过程”里比拼计算力和直觉的棋类游戏里，恐怕人类都难逃被吊打的命运

以上