一个程序能否判断另一个程序在下棋？

Question

我想询问以下问题。显然我不期望任何实际解决方案，但我很感激任何开发者对此的看法：

理论上是否可能有一个程序打开其他程序（为了论证，让我们假设它打开.exe文件），并确定特定可执行文件在执行时（具有固定的输入和机器状态）是否进行国际象棋游戏（除了其他任务之外）。

“下国际象棋”是指具有国际象棋AI引擎的黑白相间的棋盘和棋子的某种表示形式，并应用后续的移动。

这样的理论“国际象棋检测程序”可以包含虚拟机或PC模拟器或其他内容，以实际模拟扫描的可执行文件（如果需要）。我们可以假设它在具有相同RAM的任意快速计算机上运行。

关于停机问题，我可以这样解决：

在虚拟机中加载程序，该程序具有N位（硬盘和内存空间和CPU寄存器总共）。这个虚拟机最多可以假定2 ^ N个不同状态。

逐步在VM中执行程序。每一步之后，检查它是否停止。 如果是：问题已解决（结果：是，它停止）。 如果不是：获取虚拟机的当前状态，并查看此状态是否存在于我们已经遇到的状态列表中。如果是：问题已解决（结果：不会停止）。如果没有：将此状态添加到列表中并继续。

由于最多可能出现2 ^ N种不同状态，因此此算法将在有限时间内确定程序是否停止。

关于扫描的可执行文件或其运行的虚拟机的（无）限制性似乎存在一些歧义。让我们假设要扫描的可执行文件最多为1 GB（这应该足够，因为大多数国际象棋程序要小得多），它们应该在具有10 GB RAM的PC（或VM）上运行。

我们的理论国际象棋检测器程序可以使用任意数量的RAM。

- Sheldon Pinkman

---

编写一个程序，检测能够检测国际象棋程序的程序。然后在您的任意快速计算机上创建随机的.exe文件，并等待它检测到您正在寻找的exe文件。（不，这是不可能的） - Karoly Horvath

为什么不呢？（尽管棋子检测器检测器很可能比棋子检测器更难） - Sheldon Pinkman

如果你想要抓住作弊者，那么你为什么要关心“exe”可执行文件是否能玩国际象棋呢？相反，扫描当前正在运行的内存程序，这将为你提供每个程序的快照，并且更容易处理，也不会降低到停机问题。 - ldog

这不是我想要的，但听起来很有趣。你会如何确定当前运行的程序是否在下棋？（无论它是否会停止） - Sheldon Pinkman

你可以做一些像在内存中查找位棋盘表示这样的事情。http://en.wikipedia.org/wiki/Bitboard 这样做的好处是，位棋盘通常占用相当大的连续内存块，每个棋子都是64位（棋盘上每个方格1位），其中某些移动被编码在64位字中。 - ldog

在资源有限的情况下，停机问题在理论上是可解的，因此这样一个象棋程序是可能的。只要您对可执行大小/输入/状态引入任何限制，停机问题的所有悖论都会消失（提示：Cantor对角线需要无穷大）。如果您只看n个程序，请拿一个直接匹配它们并根据它们输出真或假的程序。其中之一将是您的象棋检查程序。还可以在这里看到：http://stackoverflow.com/questions/8264468/writing-a-program-that-writes-a-program/8267088#8267088 - LiKao

Answer 1

没有这样的算法可以检测一个可执行程序是否下棋。

证明在于以下问题（称为“停机问题”）不能被任何算法解决：

给定一个计算机程序，那个程序最终会终止吗？

我们可以证明，如果有一个能够确定另一个程序是否下棋的计算机程序，就可以解决停机问题。要做到这一点，我们将编写一个计算机程序，该程序执行以下操作：

1.以某些其他计算机程序P作为输入。 2.运行程序P。 3.如果程序P终止，则玩一局下棋。

这个程序具有以下有趣的行为：只有当程序P终止时，它才能下棋。换句话说，如果我们能够检测到这个程序是否能够下棋，我们将检测到程序P是否终止。但是，我们知道这是不可能的，因此必须没有一个程序能够检测某个计算机程序是否会下棋。

这种常规方法被称为从停机问题的约化，并可用于显示大量不同的问题可能无法解决。

希望这可以帮助你，对于这个“否”的答案感到抱歉！

- templatetypedef

---

我认为这种推理方式行不通。假设我们的问题是“我们能否确定9的平方根是3”。现在编写一个计算机程序，按照上述步骤1和2，将步骤3替换为“如果程序P终止，则将9除以3并测试结果是否等于3”。实际上，你对象棋能力的三步测试甚至不需要输入一个PC程序，该程序是要测试象棋能力的程序。 - phoog

@phoog："你对象棋能力的3步测试甚至没有将程序[..]作为输入进行测试。" - 我认为你读错了。他是在描述要输入到我们的象棋检测神谕中的程序。如果这样的象棋检测神谕存在，它将不得不解决停机问题来确定上述程序是否在下棋。 - BlueRaja - Danny Pflughoeft

@BlueRaja-DannyPflughoeft 哦，当然，谢谢你纠正我。 - phoog

Answer 2

关于您编辑后的问题：如果我们限制内存大小，使得程序数量是有限的，理论上我们可以枚举每一个可能的程序，并按照你想要的一组标准手动将它们分为“下棋”和“非下棋”两类。在这种情况下，我们不再拥有图灵机，因此停机问题就不适用了。相反，我们会有一个有限状态机（是的，在现实世界中，所有计算机实际上都是图灵机的有限状态近似）。然而，您添加了这个限制，因为您想要更“实际，而不是理论性”，所以这里还有另一个实际性：枚举所有256位程序（使用十亿台PC，每秒枚举十亿个程序）需要比宇宙年龄长得多的时间才能完成。那么，枚举所有小于1 GB（〜10亿位）的程序需要多长时间，你几乎无法想象。因此，实际上将真实计算机建模为图灵机比建模为有限状态机更加实际；并且根据@templatetypedef的证明，在这个模型下是不可能的。

- BlueRaja - Danny Pflughoeft

---

我们都认同我们所处理的荒谬数字的不切实际之处。这只是理论上的，我只是添加了限制以确保我们正在处理有限状态机（感谢您澄清了这个术语）。但现在我在想：我们是否可以客观地确定给定的程序是否下棋？我的意思是，它可能隐藏在许多抽象层中，我们根本无法将其识别为下棋。 - Sheldon Pinkman

Answer 3

不行。这相当于停机问题。

- phoog

---

请注意我上面关于停机问题的编辑。我认为原始的停机问题是关于检测能够在无限计算机上运行的程序。这在这里不适用。 - Sheldon Pinkman

但是用一系列比特来表示棋局有无限种方法。 - phoog

限制要检查的可执行文件是否有帮助？（请参见上面的编辑2） - Sheldon Pinkman

即使您只考虑有限长度的位序列，仍然有无限数量的方法来解释每个序列。例如，您如何知道1000001表示整数65还是ASCII字符'A'，或者可能是带符号的7位整数-63，或者可能是某种未知编码方案中的字符'k'，或者可能是表示棋盘的64个元素数组中的两个6位索引，或者可能是位图图像的一部分或... - phoog

Answer 4

程序下棋意味着什么？我不相信存在一个精确的数学定义，不能被操纵并且不会轻易等同于一个无法处理的问题。

例如，如果你问“是否存在一种移动编码方式，使得该程序能下棋？”那么一个裸的Python解释器就可以下棋了——根据规定输入：

- 一个下棋的Python程序，如果你想它执黑子并且还需要输入对手的第一步； - 一个下棋的Python程序，如果你想它执白子。

如果你固定了编码方式，那么问题就变得无聊起来。棋局是有限的（按照50步规则），所以唯一的难题是“这个程序在任何有限的棋局中是否会长时间停滞不前？”如果不会，并且始终遵循编码方式（并且做出有效的走法，这些都很容易检查），那么它就能下棋。当然，检查它是否会停滞不前是无法处理的。列举所有的棋局是可处理的，但是考虑到实际情况，也完全不可能。

- Rafał Dowgird