分类目录归档：计算机

  作者：杨超 本文地址：http://sokoban.ws/blog/?p=3757 量子计算机常被大众媒体描述得十分神奇，甚至有科学家也添油加醋，如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗？我在读了David Deutsch的书后，对此问题颇感兴趣。这个月，阅读了不少相关文献，找到了答案。答案是否定的。 首先，制造出通用的量子计算机仍然有极大的工程技术困难。 第二，再看看理论上，量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法，这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出（Shor因此获得哥德尔奖Godel Prize），历史也没有太长。想要知道这一算法与传统计算机算法有何不同，可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年，才36岁，是德州大学奥斯汀分校的教授，在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律，量子算法恰恰能更好地利用这一规律，一定程度上避免了暴力穷举。 要注意的是，整数分解并非特别难的问题。在基于传统计算机（图灵机）的计算复杂度理论中，整数分解被认为不属于P，但也只是比P问题略难一些，介于P和NP-Complete之间，且更靠近P。因此，量子算法能快速分解大数也只是情理之中。 知道量子算法是怎么做的，能做什么，就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话，澄清大众对量子计算的误解： If you take just one piece of information from this blog: Quantum computers would … 继续阅读 →

  本文地址：http://sokoban.ws/blog/?p=2330 作者：杨超 这个月，2016年3月，Google 的 DeepMind 团队开发的围棋程序 AlphaGo 在韩国首都以 4:1 战胜世界冠军围棋九段李世石。早在近20年前，IBM 的国际象棋程序“深蓝”就已经战胜人类冠军。而围棋棋盘比较大，人们普遍认为人类对计算机程序的优势在围棋项目还可以保持比较长的时间。而这次 Google 团队的胜利，证明了其实开发一个战胜人类的下围棋程序并没有那么难，而是开发这样的程序没有太大的直接收益，哪怕是国际象棋和围棋这样就有悠久历史传统和广泛的群众基础和关注度的棋类。 围棋究竟有多难？我们拿它和推箱子来比较一下。恰好我刚刚完成了用三篇博文来介绍推箱子问题的计算复杂度：推箱子是PSPACE完全问题。 为了从计算复杂度方面和推箱子问题比较，我们需要准确地定义一下什么叫围棋问题。 虽然人们常说围棋的变化很多，但是无论变化有多少，终究是一个有限的数。所有有限步内能分出胜负的、没有隐藏信息、也没有运气成分的二人棋类游戏，一定有一方有必胜策略（或者必和策略）。打个比分说，19路围棋按照中国的贴目规则也许是先手有必胜策略。那么我们所说的围棋问题，就是对于任意的n x n棋盘上下的围棋，如何设计一个算法来确定究竟是先手必胜还是后手必胜？或者等价地说，先手究竟有没有必胜策略？（即这是一个回答“是”或者“否”的问题）通常的19路棋盘围棋是围棋问题的一个实例。要回答这个问题，除了穷举所有的对弈变化之外，人们暂时还没能找到其它规律来判断谁有必胜策略。对围棋而言，穷举所需要的时间随着棋盘 n 的增大，是成指数增长的。事实上，已经有文献证明，按日本规则，围棋问题是EXPTIME完全问题（见［1，2］，该文章作者猜测，若按中国规则，围棋问题可能更难，成为指数空间完全问题）。也就是说，在指数时间可解的问题里面，围棋问题是最困难的其中一个。除了围棋，其它一些棋类问题如国际象棋、西洋跳棋（checkers）都被证明是EXPTIME完全问题。其中8×8棋盘的西洋跳棋在使用计算机花了近20年的穷举计算后，在2007年被证明双方都采取完美策略一定是和棋。 所以，从计算复杂度来看，包括围棋在内的许多棋类游戏比推箱子要难一个层次。计算复杂度的几个概念（EXPTIME、PSPACE、NP、P）的关系可用下图表示。虽然还没有从理论上严格证明，但是一般认为，从内到外，这四类问题的计算复杂度是严格地越来越难。 更有甚者，围棋问题的一些子问题，如征子能否成功问题在文献中被证明是PSPACE完全问题［3］。而围棋残局收官问题，则是PSPACE难的［4］。也就是说围棋问题的某些子问题就已经和推箱子问题一样难了。 那么，为什么比推箱子更难的围棋都已经开发出能战胜人类的程序，但是比围棋还容易一些的推箱子，我们却没有看到优秀的推箱子求解程序能够解出较大的、箱子数目较多的关卡呢？我想主要有以下这么一些因素。 首先，开发推箱子求解程序比开发下围棋程序更加无利可图。目前看到的一些求解程序基本都是个人单打独斗编写的，运行在个人电脑上，而且都是作为业余兴趣进行的。尚未看到有软件类企业或者研究团队投入较大资源来开发。作为对比，Google的AlphaGo程序投入了至少20人的开发团队，和李世石对战时动用了上千个CPU和GPU同时计算。 其次，AlphaGo虽然战胜了人类，但是并没有回答我们前面所定义的围棋问题，也就是说并不知道是否先手必胜。战胜人类并不需要穷遍所有变化，比判断19路围棋谁有必胜策略稍微容易一些。而一个推箱子关卡求解程序从某种意义上必须回答出推箱子问题，一般来说，必须穷遍所有路经才能判断一个关卡无解。而找到一个答案，除了穷举剪枝之外也还没有见到有人提出新的算法思路。 比较令人好奇的是，如果投入更多的人力和计算机运算资源，计算机求解推箱子能达到一个什么样的水平呢？能解出多大的关卡？解大关卡能比人解得更快吗？ 第83期推箱子比赛，我们也借着这个机会，由麦英兄设计了一关AlphaGo关卡。这一关计算机能解出来吗？ ［参考文献］ 1.  J. M. Robson, The complexity of Go, Proc. IFIP (1983) … 继续阅读 →