超越P和NP问题的思考：国际象棋
NP就像是一个迷宫一样，在任意大小的棋盘上各种操作。数独也是NP完全的问题，它需要从一些正方形中给定的数字设置中求解。但是，当我们问到谁从给定的初始设置中获胜时，我们是不是就没办法给出准确的回答了呢？即使我们有P=NP的前提，它也不一定会给我们一个完美的国际象棋的程序来解决问题，这就像需要设计一个程序，它保证能够让白棋走的这一步，逼迫黑棋走那一步，然后白棋再按照计划走这一步，使得黑棋…，最终是白棋获胜。人们无法单独在P=NP上完成所有这些白棋和黑棋的交替。像这样的游戏往往被称为PSPACE－hard，即很难计算、或使用合理数量的内存，并且在约定的时间之内求解完成的问题。根据规则的精确限制，国际象棋和围棋甚至可能更难。
这不意味着如果P=NP，你就不能得到一个好的国际象棋程序。事实上，在某种程度上，象棋的程序体积越大，其智能程度越高。我们可以找到一种有效的计算机程序，它可以击败所有尺寸稍小的其他程序。同时，即使没有P=NP，计算机在国际象棋和围棋方面也变得非常强大了。1997年，IBM的深蓝击败了当时的国际象棋世界冠军。
此外，机器学习为电脑游戏带来了巨大的进步。我们讨论一下声名大噪的AlphaZero，它是2017年DeepMind开发出来的人工智能程序。
AlphaZero使用了一种被称为蒙特卡洛树搜索MCTS的技术，这个技术为两个玩家随机移动以确定最佳的行动方案。AlphaZero使用深度学习来预测游戏位置的最佳分布，以优化使用MCTS的获胜机会。虽然AlphaZero不是第一个使用MCTS的工作，但是它没有任何内置的人工策略或者使用任何已有的游戏数据库。
AlphaZero只学习了游戏的规则。这就让AlphaZero在国际象棋和围棋这两个运动中大放异彩，除了交替移动和固定大小的棋盘之外，这两个游戏在规则和目的上没有任何相似之处。DeepMind最近在MuZero上也有新动作。它甚至都没有得到完整的游戏规则，只得到了对棋盘位置的一些表示，和合法动作列表，以及对哪些位置是输是赢有了一些了解。也就是说，现在我们已经发展到了一个阶段，在这个阶段里，纯机器学习在国际象棋或者围棋这样的高复杂度的问题中都能轻松击败大多数的人类或者启发式算法。人类的先验知识只会画蛇添足、碍手碍脚。对于国际象棋和围棋这样的游戏，机器学习可以在P=NP无法满足的情况下取得成功。太不可思议了。
No post found!
- 《纽约客》丨纪念9·11二十五周年 - 09/12/26
- 数学500年：新的黄金时代？（1） - 06/05/26
- 没有美洲，我们吃啥？ - 05/17/26