有一个完美的国际象棋algorithm吗？

我最近和一个非编码人讨论了国际象棋计算机的可能性。我不是很懂理论，但是我觉得我知道的够多了。

我争辩说，不可能存在一个在国际象棋中总是赢得或僵持的确定性图灵机。我认为，即使你search了所有的player1 / 2移动组合的整个空间，计算机在每个步骤所决定的单一移动都是基于启发式的。基于启发式，它不一定会击败对手所能做的所有动作。

我的朋友认为，相反，如果一个电脑从来没有犯过“错误”的行为，那么电脑总是会赢的，但是你是怎么定义的呢？但是，作为一个CS的程序员，我知道即使你的好select – 给一个明智的对手 – 也会迫使你最终做出“错误”的举动。即使你知道所有的事情，你的下一步行动是贪婪匹配启发式。

大多数国际象棋电脑都试图将可能的最终游戏与正在进行的游戏进行匹配，这本质上是一个dynamic编程追踪。同样，有争议的问题也是可以避免的。

编辑：嗯…看起来像我在这里吹了一些羽毛。那很好。

再考虑一下，似乎没有解决象棋这样有限的游戏的理论问题。我认为国际象棋比棋子要复杂一点，因为胜利不一定是棋子的数量耗尽，而是棋手。我原来的主张可能是错误的，但是我想我已经指出了一些尚未被令人满意地证实的东西（正式的）。

我想我的想法是，只要树中的某个分支被占用，那么algorithm（或者记忆path）就必须find对手的path（没有交配），以便对手的任何可能的分支移动。经过讨论后，我会买更多的回忆，所有这些path都可以find。

“我认为，不可能存在一个在国际象棋中总是赢得或僵持的确定性图灵机。”

你不太对。可以有这样一台机器。问题在于它必须search的状态空间的巨大性。这是有限的，它真的很大。

这就是为什么国际象棋回落启发式 – 国家空间太大（但有限）。甚至可以列举 – 在每个可能的游戏的每个过程中search每一个完美的动作 – 将是一个非常非常大的search问题。

开场是脚本让你到一个中游，给你一个“强”的位置。不是一个已知的结果。即使是结局游戏 – 当游戏的数量较less时，也很难列举出最佳的下一步棋。技术上他们是有限的。但替代品的数量是巨大的。即使是两个车+国王也有22个可能的下一步行动。如果需要6次交配，则您正在查看12,855,002,631,049,216次移动。

做开幕动作的math。虽然只有20个左右的开局动作，但也有30个左右的动作，所以通过第三步，我们可以看到36万个替代游戏状态。

但是国际象棋游戏在技术上是有限的。巨大的，但有限的。有完美的信息。有定义的开始和结束状态，没有掷硬币或掷骰子。

我几乎不知道什么是关于国际象棋的发现。但作为一名math家，这是我的推理：

首先我们必须记住，怀特先走了，也许这给了他一个优势。也许这给了黑方一个优势。

现在假设黑方没有完美的策略 ，让他总是赢/僵持。这意味着无论黑方做什么，白方都可以采取一种策略来赢得胜利。等一下 – 这意味着有一个完美的白色战略！

这告诉我们，至less有一名球员确实有一个完美的策略，让球员总是赢或僵持。

那么只有三种可能性：

如果他打得很好，白人总能赢
如果他打得很好，黑方总能赢
如果一个球员打的非常好（如果两个球员打得非常好，那么他们总是僵持不下）

但是其中哪一个其实是正确的，我们可能永远不会知道。

这个问题的答案是肯定的 ：至less对于其中一个玩家来说，必须有一个完美的国际象棋algorithm。

对于跳棋的比赛已经certificate，一个程序总是可以赢得或绑定游戏。也就是说，一个玩家可以做出的强制另一个玩家失败的行动是没有select的。

研究人员花费了将近二十年的时间 ，通过5000亿亿可能的棋子位置，顺便说一下，棋子位置的数量仍然是一小部分。跳棋的努力包括顶级球员，谁帮助研究团队程序跳棋经验法则成软件分类移动成功或不成功。然后研究人员让程序每天平均运行50台电脑。有些日子，程序运行在200台机器上。而研究人员监测进展，并相应地调整了scheme。事实上，奇努克在1994年击败人类赢得了跳棋世界冠军。

是的，你可以解决国际象棋，不，你不会很快。

这不是关于电脑的问题，而只是关于国际象棋的游戏。

问题是，是否存在一个永不失败的自动防故障策略？如果存在这样的策略，那么知道所有事情的计算机总是可以使用它，这不是一个启发式的了。

例如，游戏井字游戏通常是基于启发式玩法。但是，存在一个安全策略。无论对手什么动作，如果你从一开始就这样做，你总能find一种避免输掉比赛的方法。

所以你需要certificate这个策略是否存在，基本上是一样的，只是可能的动作空间要大得多。

我很晚才知道这个问题，而且你已经意识到了一些问题。但是作为一个前高手和一个前专业的国际象棋程序员，我想我可以添加一些有用的事实和数字。衡量国际象棋复杂程度有几种方法：

国际象棋比赛总数约为10 ^（10 ^ 50）。这个数字是难以想象的大。
40次或更less的棋局数量在10 ^ 40左右。这仍然是一个令人难以置信的数量。
可能的国际象棋的数量是10 ^ 46左右。
完整的国际象棋search树（香农数）约为10 ^ 123，平均分支因子为35，平均游戏长度为80。
为了比较，可观测宇宙中的primefaces数通常估计在10 ^ 80左右。
所有6个或更less的结局已被整理和解决。

我的结论是：虽然国际象棋在理论上是可以解决的，但我们永远不会有金钱，动力，计算能力或存储空间。

事实上，一些游戏已经被解决了。 Tic-Tac-Toe是一个非常容易的人，可以build立一个永远赢得或打平的AI。最近Connect 4也被解决了（对第二个玩家来说，这是不公平的，因为完美的玩法会让他失去）。

然而，国际象棋还没有解决，我不认为有证据表明这是一个公平的游戏（即完美的游戏是否能够平局）。尽pipe从理论angular度严格来说，国际象棋有可能的棋子configuration数量有限。因此，search空间是有限的（虽然，令人难以置信的大）。因此，一个可以完美演奏的确定性图灵机确实存在。然而，是否能够build造是另外一回事。

平均1000美元的桌面将能够在2040年仅仅5秒内解决跳棋问题（5×10 ^ 20的计算）。

即使以这样的速度，这些计算机仍然需要大约6.34×10 ^ 19 年的时间来解决国际象棋。仍然不可行。差远了。

2080年前后，我们平均每台桌面计算机将有大约10 ^ 45次计算。一台计算机将在27.7小时内具有解决国际象棋的计算能力。只要计算能力在过去30年持续增长，到2080年肯定会完成。

到2090年，在1000美元的台式机上将有足够的计算能力来解决大约1秒的国际象棋…所以到那个时候它将是完全微不足道的。

鉴于棋子在2007年得到了解决，在1秒内解决它的计算能力将滞后大约33 – 35年，我们大概可以估计棋子将在2055年至2057年之间某处解决。自从有了更多的计算能力（45年后就会出现这种情况），可能会更快地投入到这样的项目中。不过，我最早要说2050，最晚要2060。

到2060年，将需要100个平均桌面3.17×10 ^ 10年来解决国际象棋。意识到我使用的是1000美元的计算机作为我的基准，而更大的系统和超级计算机将可能是可用的，因为它们的性价比也在提高。而且，它们的计算能力的数量级也以更快的速度增加。考虑一台超级计算机现在可以执行每秒2.33×10 ^ 15的计算，而一台1000美元的计算机大约2×10 ^ 9。相比之下，10年前的差距是10 ^ 5而不是10 ^ 6。到2060年，数量级的差别可能会达到10 ^ 12，甚至可能比预期的增加得更快。

这很大程度上取决于我们作为人类是否有解决国际象棋的动力，但计算能力将在这个时候（只要我们的步伐还在继续）变得可行。

另一方面，Tic-Tac-Toe的游戏要简单得多，它有2,653,002个可能的计算（有开放的板）。 1990年，计算能力达到了约2.5（每秒百万次计算）秒的Tic-Tac-Toe。

向后移动，1955年，计算机有能力在大约1个月内（每秒计算1次）解决井字游戏。再次，这是基于1000美元会给你，如果你可以把它打包成一台电脑（一台1000美元的桌面显然不存在于1955年），这台电脑将致力于解决井字趾….在1955年，情况并非如此。计算起来很昂贵，不会被用于这个目的，尽pipe我不相信有什么dateTic-Tac-Toe被计算机认为是“解决”的，但是我当然，它落后于实际的计算能力。

另外，考虑到45年内1000美元的价值将比现在低4倍左右，那么这样的项目可以投入更多的钱，而计算能力将继续降低。

实际上，双方玩家都可以在无限的游戏中拥有制胜策略，然而，国际象棋是有序的。事实上，由于50步移动规则，游戏的移动次数是有上限的，所以只有有限的棋子游戏（可以列举来解决。理论上，至less ：）

争论的结局得到了现代国际象棋程序的支持。他们这样工作，是因为资源密集程度太高，无法编写国际象棋程序来确定地运行。他们不一定总是这样工作。有一天国际象棋有可能会被解决，如果发生这种情况，它可能会被计算机解决。

为了logging，有计算机可以赢得或绑在跳棋。我不确定象棋是否也可以做。动作的次数要多得多。而且，事情也会发生变化，因为棋子可以向任何方向移动，而不仅仅是向前和向后。我认为虽然我不确定，但是这个国际象棋是确定性的，但是对于一台计算机来说，在合理的时间内确定所有的棋步还有很多可能的方法。

我想你已经死了。 “深蓝”和“深思”等机器用一些预定义的游戏进行编程，并使用巧妙的algorithm将树分析到游戏的最后。这当然是一个过分简单化的过程。在游戏过程中总会有机会“击败”电脑。通过这个，我的意思是做出一个动作，迫使计算机做出一个不太理想的动作（不pipe是什么）。如果计算机在移动的时间限制之前找不到最佳path，那么select一个不太理想的path可能会导致错误。

还有一类国际象棋程序使用真正的机器学习，或遗传编程/进化algorithm。一些程序已经发展，并使用neural network等来做出决定。在这种情况下，我会想象电脑可能会犯“错误”，但最终还是会取得胜利。

关于这种名为Blondie24的GP，你可能会读到一本迷人的书。这是关于棋子，但它可以适用于国际象棋。

从博弈论，这个问题是关于什么的，答案是肯定的，国际象棋可以完美地演奏。游戏空间是已知的/可预测的，是的，如果你有你的孙子的量子计算机，你可能会消除所有的启发式。

你现在可以用任何脚本语言编写一个完美的井字游戏机，它可以实时完美地播放。

“奥赛罗”是另一款游戏，目前的电脑可以很容易地发挥完美，但机器的内存和CPU需要一些帮助

国际象棋从理论上讲是可行的，但在现实中是不可能的（2008年）

i-Go很棘手，它的可能性空间超出了宇宙中的primefaces数量，所以我们需要一些时间才能制造出完美的i-Go机器。

国际象棋是一个matrix游戏的例子，从定义上来说，它有一个最优的结果（纳什均衡）。如果玩家1和2各自采取了最佳的动作，总会有一定的结果（不pipe是双赢还是未知）。

作为一名七十年代的国际象棋程序员，我绝对有这个意见。大约十年前我写的，今天基本上是真的：

“国际象棋程序员未完成的工作和挑战”

那时候，我想我们可以常规地解决国际象棋，如果做得好的话。

跳棋最近解决了（耶，加拿大阿尔伯塔大学!!!），但那是有效地做了蛮力。按惯例做棋，你必须变得更聪明。

当然，除非量子计算成为现实。如果是这样，国际象棋将像井字棋一样轻松解决。

在“科学美国人”的七十年代早期，有一个短暂的模仿引起了我的注意。这是一个宣布，国际象棋游戏由俄罗斯国际象棋计算机解决。它已经确定白方有一个完美的举动，这将确保双方的完美发挥，这一举措是：1. a4！

如果你search所有组合的全部空间，那么计算机在每个步骤中所决定的单个动作是基于启发式的。

那里有两个相互竞争的想法。一个是你search每一个可能的举动，另一个是你基于启发式的决定。启发式是一个很好的猜测系统。如果你正在寻找每一个可能的举措，那么你不再猜测。

“有一个完美的国际象棋algorithm吗？”

就在这里。也许这对于怀特总是赢。也许这是黑方总是赢的。也许这对双方来说总是至less有联系。我们不知道哪一个，我们永远不会知道，但它肯定存在。

也可以看看

上帝的algorithm

我发现这篇由John MacQuarrie撰写的文章引用了“博弈论之父” Ernst Friedrich Ferdinand Zermelo的工作。得出以下结论：

在国际象棋中，白棋可以强制取胜，黑棋可以强制取胜，双方都可以强制取胜。

逻辑似乎听起来对我来说。

这里的很多答案都提出了重要的博弈论观点：

国际象棋是一个有限的，确定性的游戏与完整的游戏状态信息
你可以解决一个有限的游戏，并确定一个完美的策略
国际象棋是足够大，你将无法用蛮力的方法完全解决它

然而，这些观察结果却错过了一个重要的实践点： 没有必要为了创造一个无与伦比的机器而完美地解决完整的游戏 。

实际上很有可能你可以创build一个无与伦比的国际象棋机器（即永远不会失败，并将永远强制胜利或抽奖），而不需要search可能的状态空间的一小部分。

下面的技术例如都大量减less了所需的search空间：

像Alpha / Beta或MTD-f等树修剪技术已经大量减lesssearch空间
可certificate的获胜位置。许多结局属于这个范畴：例如，你不需要search韩元对K，这是一个certificate胜利。有些工作可以certificate更多的保证胜利。
几乎可以肯定的是，在没有任何愚蠢的错误的情况下（比如说ELO 2200+），“足够好”的游戏没有任何愚蠢的错误？许多国际象棋棋局几乎可以赢得一定的胜利，例如体面的材料优势（例如额外的骑士）如果你的程序可以强制这样一个位置，并具有足够的启发式检测位置优势，它可以安全地假设它会赢得或至less100％的概率。
树search启发式 – 具有足够好的模式识别，您可以快速关注“有趣”移动的相关子集。这就是人类大师们所扮演的angular色，所以这显然不是一个糟糕的策略……而且我们的模式识别algorithm也在不断变好
风险评估 – 一个更好的职位“风险”概念将通过将计算能力集中在结果更不确定的情况下（这是静止search的一个自然延伸）来实现更有效的search，

有了上述技术的正确组合，我可以很自信地说，创造一个“无与伦比的”象棋机器是可能的。现在的技术可能不会太远。

请注意， certificate这台机器不能被殴打几乎肯定是困难的。这可能就像雷曼假设一样 – 我们可以肯定的说，它是完美的，并且会有实证结果显示它从来没有丢失过（包括几十亿的直接借口），但是我们实际上没有能力certificate给我看。

关于“完美”的补充说明：

我注意到，在游戏理论的意义上，不要将机器描述为“完美”，因为这意味着非常强的附加条件，例如：

无论赢得组合多么复杂，总是能赢得胜利的每一个场合。在胜利/抽签的边界上会出现这种情况，这是非常难以完美计算的。
利用关于对手的潜在缺陷的所有可用信息，例如推断出你的对手可能过于贪婪，故意以比平常稍微弱一些的线条，理由是它有更大的潜在诱惑你的对手犯错误的可能性。对于不完美的对手来说，如果你估计你的对手可能不会发现被迫的胜利，那么实际上可能是最佳的，这会让你有更高的赢率。

完美（特别是给予不完美和未知的对手）是一个比无与伦比的难的问题。

这是完全可以解决的。

有10 ^ 50个单位。根据我的估算，每个位置至less需要存储64个循环字节（每个正方形有2个关联位，3个位）。一旦核对完毕，就可以确定被核对的职位，并可以比较职位形成的关系，显示哪些职位在大型结果树中导致其他职位。

那么，如果这样的事情存在，程序只需要find最低的只有一方的将军根。在任何情况下，国际象棋在第一段结尾处都相当简单。

我只有99.9％的人认为，国家空间的大小使人们不可能希望得到解决scheme。

当然，10 ^ 50是一个不可能的大数目。我们称之为状态空间n的大小。

在最长的游戏中，移动次数的界限是什么？由于所有的游戏都是以有限的数量结束，所以存在这样一个界限，称之为m。

从初始状态开始，不能枚举O（m）空间中的所有n次移动吗？当然，这需要O（n）时间，但是来自宇宙大小的论据并不直接解决这个问题。 O（m）空间可能不是很多。对于O（m）空间，在这个遍历过程中，你是否还可以跟踪沿着你正在遍历的path的任何状态的延续是否导致EitherMayWin，EitherMayForceDraw，WhiteMayWin，WhiteMayWinOrForceDraw，BlackMayWin或者BlackMayWinOrForceDraw？（有一个格子取决于它的转向，用格子相遇来标注遍历历史中的每个状态。）

除非我错过了一些东西，这是一个O（n）时间/ O（m）空间algorithm，用于确定哪些棋类可能属于哪个类别。维基百科引用了约10 ^ 60普朗克时间的宇宙年龄估计。没有进入宇宙论的争论，让我们猜测在宇宙的热/冷/无论死亡之前剩下多less时间。这让我们需要每10 ^ 10次普朗克时间或每10 ^ – 34秒评估一次。这是一个不可能的短时间（比有史以来最短的时间短大约16个数量级）。让我们乐观地说，通过运行在现有或非预期的非量子P-is-a-proper-subset-of-NP技术之上的超级不错的实现，我们希望能够评估（采取单步前进，将结果状态分类为中间状态或三个结束状态中的一个状态）以100MHz（每10 ^ -8秒一次）的速率进行分类。由于这个algorithm是可并行化的，所以我们需要10 ^ 26个这样的计算机，或者我的身体中的每个primefaces需要一个，以及收集结果的能力。

我想，对于暴力解决scheme总有一些希望。我们可能会很幸运，在探索白棋的一个可能的开局动作时，他们都select了一个低于平均水平的球迷，其中一个白方总是赢或者抽签。

我们也可以希望缩小国际象棋的定义，并且说服大家，这在道德上仍然是一个游戏。我们是否真的需要在抽签之前要求重复3次？我们是否真的需要让逃跑党performance出50步的逃跑能力？有人甚至不明白什么是和谐规则？ ;）更为严重的是，当他们只是为了逃避支票或者陷入僵局而被抓获的时候，我们是否真的需要迫使一个玩家移动（而不是抽中或者输掉）呢？如果所需的非女王晋升不会导致立即检查或将军，我们是否可以限制棋子的select？

我还不能确定每台计算机基于哈希的访问权限，以便能够访问大量迟到的游戏状态数据库及其可能的结果（在现有硬件和已有的游戏结束数据库上可能相对可行）可以帮助您更早地修改search结果。显然，如果没有O（n）存储，你不能记忆整个函数，但是你可以select一个大的整数并且记住许多从每个可能的（甚至不是很可能不可能的，我想是）最终状态向后枚举的endgames。

我知道这是一个颠簸，但我必须把我的5美分的价值在这里。一台电脑或一个人就可以结束他/她参与的每一个象棋游戏，无论是赢或者僵持。

然而，要实现这一点，你必须精确地知道每一个可能的行动和反应等等，一直到每一个可能的游戏结果，并想象这个，或者简单地分析这些信息，想一想它作为一个不断分支的思维导图。

中心节点将是游戏的开始。每个节点的每一个分支都代表一个移动，每一个移动都与其不同。在这个庄园介绍会花费很多资源，特别是如果你在纸上这样做。在计算机上，这将需要数百Terrabytes的数据，因为除非你让分支回来，否则你将会有非常多的调整动作。

然而，要记住这些数据，即使不是不可能，也是不可置信的。为了使计算机能够识别出（最多）8个即时可能的移动的最佳移动，将是可能的，但不是可能的，因为该计算机将需要能够处理通过该移动的所有分支，一路得出一个结论，数出所有导致胜利或僵局的结论，然后根据这些胜利的结论来对抗失败的结论，这就需要能够处理Terrabytes数据的RAM或更多！而用今天的技术，像这样的计算机将需要超过世界上最富有的5个男人和/或女人的银行平衡！

所以，经过这么多的考虑，可以做到，但是，没有人能做到。这样的任务需要当今最聪明的思想家中的30个，不仅在国际象棋，而且在科学和计算机技术上，这样的任务只能完成一个（让我们把它完全放在基本的angular度）超级计算机……至less在一个世纪内不可能存在。将会完成！只是不在这一生中。

你的思想实验有两个错误：

如果你的图灵机不是“有限的”（在内存，速度，…）你不需要使用启发式，但你可以计算评估最终状态（赢，输，抽）。为了find完美的游戏，你只需要使用Minimaxalgorithm（见http://en.wikipedia.org/wiki/Minimax ）来计算每个玩家的最佳动作，这将导致一个或多个最佳游戏。
使用启发式的复杂性也没有限制。如果你能计算一个完美的游戏，也有一种方法来计算一个完美的启发式。如果需要的话，它只是一个function，在国际象棋位置的方式“如果我在这种情况下，我最好的举动是M”。

正如其他人所指出的，这将以三个可能的结果结束：白方可以强制取胜，黑方可以强制取胜，其中一方可以强制平局。

一个完美的跳棋游戏的结果已经被“计算”了。如果人类以前不会消灭自己，那么有一天，当计算机发展到足够有记忆和速度的时候，也会有一个计算棋盘的计算。或者我们有一些量子计算机…或者直到有人（研究人员，国际象棋专家，天才）发现一些algorithm，大大降低了游戏的复杂性。举个例子：1到1000之间的所有数字的总和是多less？您可以计算1 + 2 + 3 + 4 + 5 … + 999 + 1000，或者可以简单地计算：N *（N + 1）/ 2，N = 1000; 结果= 500500.现在想象不知道这个公式，你不知道math归纳，你甚至不知道如何乘数或增加数字，…所以，可能有一个当前未知的algorithm只是最终降低了这个游戏的复杂性，它只需要5分钟来计算当前计算机的最佳移动。也许甚至有可能用笔和纸来估计它是一个人，或者甚至在你的脑海中，有更多的时间。

所以，最简单的答案是：如果人类足够久存，这只是时间问题！

它可能是可以解决的，但有些事情让我困扰：即使整棵树可以遍历，仍然无法预测对手的下一步行动。我们必须始终把我们的下一步移动到对手的状态，并使“最佳”的移动。然后，基于下一个状态，我们再次做。所以，如果对手以某种方式移动，我们的最优移动可能是最优的。对于对手的一些动作，我们的最后一步可能是次优的。

我只是看不出每一步可能会有一个“完美”的举动。

为此，无论对手的下一步行动（如井字游戏）如何，当前游戏中的每个状态都必须是树中的一条通向胜利的道路，而且我有一个艰难的时间的计算。

在math上，国际象棋已经被Minimaxalgorithm解决，该algorithm可追溯到20世纪20年代（由Borel或者von Neumann发现）。因此，一台图灵机确实可以打出完美的象棋。

但是，国际象棋的计算复杂性使得它几乎不可行。目前的引擎使用了一些改进和启发式。如今的顶级发动机已经超越了最好的人类，但是由于他们使用的启发式方法，在给定无限时间的情况下（例如，散列碰撞可能导致不正确的结果），它们可能无法发挥完美。

我们目前所拥有的最接近完美的游戏是残局桌面游戏。生成它们的典型技术称为逆行分析。目前，所有六个职位已经解决。

当然，棋盘上只有50个可能的棋子组合。考虑到这一点，为了发挥每一个组合的作用，你需要在10步之内完成50步的动作（包括重复3次）。所以，国际象棋还有不到十分之一的力量。只要select那些导致将死，你很好去

64位math（=棋盘）和按位运算符（=下一个可能的移动）是你所需要的。所以简单。蛮力将通常find最好的方式。当然，所有职位都没有通用的algorithm。在现实生活中，计算时间也是有限的，超时会阻止它。一个好的国际象棋程序意味着重码（通过，加倍棋子等）。小代码不能很强大。打开和结束数据库只是节省处理时间，某种预处理的数据。该设备，我的意思是 – 操作系统，线程位置，环境，硬件定义的要求。编程语言是重要的。无论如何，发展过程是有趣的。