我最近与一位非编码人员就国际象棋电脑的可能性进行了讨论 . 我不太懂理论，但想想我已经足够了解 .
我认为不可能存在确定性的图灵机，它总是在国际象棋中获胜或陷入僵局 . 我认为，即使您搜索播放器1/2移动的所有组合的整个空间，计算机在每个步骤决定的单个移动都基于启发式 . 基于启发式，它不一定能击败对手可以做的所有动作 .
相反，我的朋友认为，如果计算机永远不会做出“错误”的举动，那么计算机将永远胜出或结合（但是你定义了吗？） . 然而，作为一名采取CS的程序员，我知道即使你的好选择 - 给予明智的对手 - 也会迫使你最终做出“错误”的举动 . 即使你知道一切，你的下一步行动在匹配启发式方面也很贪婪 .
大多数国际象棋计算机试图将可能的最终游戏与正在进行的游戏相匹配，这本质上是一个动态的编程追溯 . 同样，有问题的最后阶段是可以避免的 .
编辑：嗯......看起来我在这里乱了一些羽毛 . 非常好 .
再考虑一下，似乎解决像国际象棋这样的有限游戏没有理论上的问题 . 我认为国际象棋比跳棋更复杂，因为胜利不一定是数字耗尽，而是通过配偶 . 我最初的断言可能是错误的，但我认为我已经指出了一些尚未得到令人满意的证明（正式） .
我想我的思想实验是，无论何时树中的分支被采用，那么算法（或记忆路径）必须找到对手移动的任何可能分支的配偶路径（不进行交配） . 在讨论之后，我将购买比我们可能梦想的更多内存，所有这些路径都可以找到 .
27 回答
“我认为不可能存在确定性的图灵机，它总是在国际象棋中获胜或陷入僵局 . ”
你有限，它只是 REALLY 大 .
这就是国际象棋回归启发式的原因 - 国家空间太大（但有限） . 甚至可以列举 - 更不用说搜索每个可能游戏的每个过程中的每个完美移动 - 将是一个非常非常大的搜索问题 .
开场编写脚本，让你进入游戏中期，让你有一个“强势”的位置 . 不是已知的结果 . 即使是最终游戏 - 当数量较少时 - 很难枚举以确定最佳的下一步行动 . 从技术上讲，它们是有限的 . 但替代品的数量巨大 . 即使是一个2个车手的国王也有类似22个可能的下一步行动 . 如果需要6个动作来交配，你会看到12,855,002,631,049,216个动作 .
打开动作的数学运算 . 虽然只有大约20个开场动作，但有大约30个左右的第二步，所以在第三步中我们正在寻找360,000个替代游戏状态 .
但国际象棋比赛（技术上）是有限的 . 巨大但有限 . 有完美的信息 . 有定义的开始和结束状态，没有掷硬币或掷骰子 .
我几乎不知道国际象棋究竟发现了什么 . 但作为一名数学家，这是我的理由：
首先，我们必须记住怀特先走了，也许这给了他一个优势;也许它给了布莱克一个优势 .
现在假设布莱克没有完美的策略让他总能赢得/僵持 . 这意味着无论黑方做什么，白方都可以采取一种策略来赢得胜利 . 等一下 - 这意味着白方有一个完美的策略！
这告诉我们，两个玩家中至少有一个确实有一个完美的策略，让玩家总是赢或抽 .
那么只有三种可能性：
如果白棋完美，白方总能获胜
如果他打得很完美，他总能获胜
一名球员如果能够完美打球就能赢或抽（如果两名球员都打得很完美，那么他们总是陷入僵局）
但其中哪一项实际上是正确的，我们可能永远不会知道 .
这个问题的答案是 yes ：必须有一个完美的国际象棋算法，至少对于两个球员中的一个 .
已经证明game of checkers一个程序总能赢得或打败游戏 . 也就是说，没有选择一个玩家可以做出的动作迫使另一个玩家失败 .
是的，你可以解决国际象棋，不，你不会很快 .
这不是关于计算机的问题，而是关于国际象棋的问题 .
问题是，是否存在永不丢失游戏的故障安全策略？如果存在这样的策略，那么知道所有内容的计算机总是可以使用它并且它不再是启发式的 .
例如，游戏井字游戏通常基于启发式来玩 . 但是，存在一种故障安全策略 . 无论对手如何移动，如果你从一开始就做到这一点，你总能找到避免输掉比赛的方法 .
因此，您需要证明国际象棋是否存在这样的策略 . 它基本上是相同的，只是可能的移动空间要大得多 .
我已经意识到了一些问题 . 但作为一名前大师和前职业国际象棋程序员，我想我可以添加一些有用的事实和数据 . 有几种方法可以测量complexity of chess：
国际象棋比赛总数约为10 ^（10 ^ 50） . 这个数字难以想象 .
40次或更少的国际象棋比赛的数量大约是10 ^ 40 . 这仍然是一个非常大的数字 .
可能的国际象棋位置数约为10 ^ 46 .
完整的国际象棋搜索树（香农数）约为10 ^ 123，基于平均分支因子35和平均游戏长度80 .
为了进行比较，可观察宇宙中的原子数通常估计为10 ^ 80左右 .
所有6件或更少的游戏都是collated and solved .
我的结论是：虽然国际象棋在理论上是可以解决的，但我们永远不会有金钱，动力，计算能力或存储空间 .
事实上，有些游戏已经解决了 . Tic-Tac-Toe是一个非常容易的人，可以 Build 一个永远赢或平的AI . 最近，Connect 4也得到了解决（并且显示对第二个玩家不公平，因为完美的游戏将导致他失败） .
然而，国际象棋尚未解决，我认为没有任何证据表明这是一场公平的比赛（即，完美的比赛是否会导致平局） . 严格地说，从理论的角度来看，国际象棋有可能的部分配置 . 因此，搜索空间是有限的（尽管非常大） . 因此，确实存在可以完美发挥的图灵机 . 然而，是否可以建造一个是另一回事 .
到2040年，平均1000美元的桌面将能够在5秒内解决跳棋（5x10 ^ 20计算） .
即使以这样的速度，它仍然需要100台这些计算机大约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 x 10 ^ 10年 . 意识到我使用1000美元的计算机作为我的基准，而大型系统和超级计算机可能会因为它们的性价比也在提高而可用 . 而且，它们的计算能力的数量级以更快的速度增加 . 考虑一台超级计算机现在每秒可以执行2.33 x 10 ^ 15次计算，而一台1000美元的计算机可以执行大约2 x 10 ^ 9的计算 . 相比之下，10年前的差异是10 ^ 5而不是10 ^ 6 . 到2060年，数量级的差异可能是10 ^ 12，甚至这可能比预期的增加得更快 .
其中很大一部分取决于我们作为人类是否有解决国际象棋的动力，但计算能力将使其在此期间可行（只要我们的步伐继续） .
另一方面，Tic-Tac-Toe的游戏更简单，有2653,002个可能的计算（有一个开放的板） . 在1990年实现了以大约2.5（每秒100万次计算）秒来解决Tic-Tac-Toe的计算能力 .
向后移动，在1955年，计算机有能力在大约1个月内解决Tic-Tac-Toe（每秒计算1次） . 再一次，这是基于1000美元，如果你可以将它打包到一台电脑（1000美元）桌面显然不存在于1955年），这台计算机本来就致力于解决Tic-Tac-Toe .... 1955年情况并非如此 . 计算费用昂贵，不会用于此目的，尽管我不确定它是否落后于实际的计算能力 .
此外，考虑到45年内1000美元的 Value 将比现在少4倍，所以更多的钱可以用于这样的项目，而计算能力将继续变得更便宜 .
实际上，对于两个玩家而言，无限游戏中的获胜策略并没有良好的排序，这实际上是is possible . 国际象棋是有序的 . 事实上，由于50-move rule，游戏可以拥有的移动数量有一个上限，因此只有有限的许多可能的国际象棋游戏（可以枚举以完全解决...理论上，至少： ）
现代国际象棋程序的工作方式支持你的论证结束 . 他们以这种方式工作，因为它必然总是以这种方式工作 . 有一天国际象棋有可能是solved，如果发生这种情况，它很可能会被计算机解决 .
为了记录，有些计算机可以在checkers获胜或打成平手 . 我不确定，国际象棋是确定性的，但目前有太多可能的动作让计算机在合理的时间内确定所有动作 .
我想你已经死了 . 像Deep Blue和Deep Thought这样的机器被编程有许多预定义的游戏，以及用于将树解析为这些游戏的末端的聪明算法 . 当然，这是一种戏剧性的过度简化 . 总是有机会在游戏过程中“击败”计算机 . 我的意思是做出一个动作，迫使计算机做出一个不太理想的动作（无论是什么） . 如果计算机在移动的时间限制之前找不到最佳路径，那么通过选择一个不太理想的路径可能会犯错误 .
还有另一类国际象棋程序使用真正的机器学习，或遗传编程/进化算法 . 一些程序已经进化并使用神经网络等来做出决策 . 在这种情况下，我会想象计算机可能会犯“错误”，但最终还是会取得胜利 .
有一本关于这种类型的GP的书很有趣，你可能会读到Blondie24 . 这是关于跳棋，但它可以适用于国际象棋 .
从博弈论这个问题来看，答案是肯定国际象棋可以完美发挥 . 游戏空间是已知的/可预测的，是的，如果你有孙子的量子计算机，你可能可以消除所有的启发式 .
您现在可以用任何脚本语言编写一个完美的井字游戏机，它可以实时完美地播放 .
奥赛罗是另一款当前计算机可以轻松完美播放的游戏，但机器的内存和CPU需要一些帮助
国际象棋在理论上是可行的，但实际上不可能（2008年）
i-Go很棘手，它的可能性空间超出了宇宙中原子的数量，所以我们可能需要一些时间才能制造出完美的i-Go机器 .
国际象棋是矩阵游戏的一个例子，根据定义，它具有最佳结果（想想纳什均衡） . 如果玩家1和玩家2各自采取最佳动作，则总是会达到某种结果（无论是胜利还是未知） .
作为二十世纪七十年代的国际象棋程序员，我对此肯定有一个看法 . 我大约10年前写的，今天基本上是真的：
"Unfinished Work and Challenges to Chess Programmers"
那时候，我认为如果做得好，我们可以按常规解决国际象棋问题 .
Checkers最近解决了（Yay，加拿大阿尔伯塔大学!!!）但这实际上是Brute Force完成的 . 按惯例做国际象棋，你必须更聪明 .
当然，除非Quantum Computing成为现实 . 如果是这样，国际象棋将像Tic-Tac-Toe一样轻松解决 .
在1970年代早期的“科学美国人”中，有一个引起我注意的短暂模仿 . 国际象棋游戏是由俄罗斯国际象棋计算机解决的 . 它已经确定白棋有一个完美的举动，可以确保双方完美发挥的胜利，这一举动是：1 . a4！
这里有很多答案可以说明重要的游戏理论要点：
国际象棋是一种有限的，确定性的游戏，其中包含有关游戏状态的完整信息
您可以解决有限游戏并确定完美策略
国际象棋足够大，你无法用蛮力方法完全解决它
然而，这些观察结果错过了一个重要的实际观点： it is not necessary to solve the complete game perfectly in order to create an unbeatable machine .
事实上，很有可能你可以创造一个无与伦比的国际象棋机器（即永远不会失去并将永远强制胜利或平局），而不用搜索可能的状态空间的一小部分 .
以下技术例如都是大规模的减少所需的搜索空间：
像Alpha / Beta或MTD-f这样的树修剪技术已经大大减少了搜索空间
可胜利的位置 . 许多结局属于这一类：你不是一个经证实的胜利 . 通过一些工作，可以证明更多的保证胜利 .
几乎可以确定胜利 - 没有任何愚蠢的错误（比如关于ELO 2200？）许多国际象棋位置几乎都是肯定的胜利，例如一个体面的物质优势（例如额外的骑士）没有补偿的位置优势 . 如果你的程序可以强制执行这样的位置并具有足够的启发式来检测位置优势，那么它可以安全地假设它将赢得或至少以100％的概率绘制 .
树搜索启发式 - 具有足够好的模式识别功能，可以快速关注"interesting"移动的相关子集 . 这就是人类大师们玩耍的方式，所以这显然不是一个糟糕的策略.....我们的模式识别算法不断变得更好
风险评估 - 通过将计算能力集中在结果更不确定的情况下（这是Quiescence Search的自然延伸），对职位的更好概念将能够实现更有效的搜索 .
通过上述技术的正确组合，我很自然地断言可以创造一个“无与伦比”的国际象棋游戏机 . 对于当前的技术，我们可能并不太遥远 .
请注意，几乎可以肯定地证明这台机器不能被打败 . 它可能类似于Reimann假设 - 我们非常肯定它会完美地发挥并且会有实证结果表明它永远不会丢失（包括几十亿直接对抗自身），但我们实际上没有能力证明给我看 .
Additional note regarding "perfection":
我小心不要在游戏理论意义上将机器描述为“完美”，因为这意味着异常强大的附加条件，例如：
无论胜利组合多么复杂，总能赢得任何可以取胜的局面 . 在胜利/平局之间的边界上会出现这种情况，这是非常难以完美计算的 .
利用有关对手比赛中潜在不完美的所有可用信息，例如推断你的对手可能过于贪婪并故意打出比平时略弱的线，理由是它有更大的诱惑你的对手犯错误的可能性 . 对于不完美的对手来说，如果你估计你的对手可能不会发现强制获胜并且你给自己赢得更高的概率，那么它实际上可能是输掉的最佳选择 .
完美（特别是对于不完美和未知的对手）是一个更难的问题，而不仅仅是无与伦比 .
那里有两个相互竞争的想法 . 一个是你搜索每一个可能的移动，另一个是你根据启发式决定 . 启发式算法是一个很好的猜测系统 . 如果你正在搜索每一个可能的动作，那么你就不再猜测了 .
就在这里 . 也许白方总能获胜 . 也许黑人总能获胜 . 也许两者总是至少打成平手 . 我们不知道哪个，我们永远不会知道，但它确实存在 .
另见
我发现article by John MacQuarrie引用了"father of game theory" Ernst Friedrich Ferdinand Zermelo的工作 . 它得出以下结论：
逻辑对我来说似乎很合理 .
它完全可以解决 .
有10 ^ 50个奇数位置 . 根据我的计算，每个位置需要至少64个圆形字节来存储（每个方格具有：2个从属位，3个位） . 一旦它们被整理，就可以识别作为核对的位置并且可以比较位置以形成关系，从而显示哪些位置导致大结果树中的其他位置 .
然后，如果存在这样的事情，程序只需要找到最低的唯一一方将死根 . 无论如何，国际象棋在第一段末尾相当简单地解决了 .
我只有99.9％的人认为国家空间的大小使人们无法希望找到解决方案 .
当然，10 ^ 50是一个不可思议的大数字 . 我们称之为状态空间n的大小 .
在最长的游戏中，动作数量的界限是什么？由于所有游戏都以有限数量的移动结束，因此存在这样的界限，称之为m .
从初始状态开始，你不能枚举O（m）空间中的所有n个移动吗？当然，它需要O（n）时间，但是来自宇宙大小的参数并没有直接解决那 . O（m）空间可能甚至不是很大 . 对于O（m）空间，在此遍历期间，您是否也无法跟踪沿着您正在遍历的路径的任何状态的延续是否导致EitherMayWin，EitherMayForceDraw，WhiteMayWin，WhiteMayWinOrForceDraw，BlackMayWin或BlackMayWinOrForceDraw？ （根据它的转向，有一个格子，在格子相遇的情况下，在遍历的历史中注释每个状态 . ）
除非我遗漏了某些东西，否则这是一个O（n）时间/ O（m）空间算法，用于确定国际象棋属于哪种类别 . 维基百科引用了大约10 ^ 60普朗克时代对宇宙年龄的估计 . 在没有进入宇宙学论证的情况下，让我们猜测在热/冷/无论宇宙死亡之前还剩下那么多时间 . 这使得我们需要每10 ^ 10th Planck时间或每10 ^ -34秒评估一次移动 . 这是一个不可能短的时间（比有史以来最短的时间短约16个数量级） . 让我们乐观地说，我们可以希望评估一种超级优秀的实施方案，这种方法可以在现有的 - 或 - 非 - 非 - 量子 - P - 是 - 适当的NP子集技术的基础上运行 . 单步前进，以100MHz的速率（每10 ^ -8秒一次）将结果状态分类为中间状态或三种结束状态之一 . 由于这个算法非常可并行化，因此我们需要10 ^ 26个这样的计算机，或者我的身体中每个原子需要一个，以及收集结果的能力 .
我认为蛮力解决方案总有一些希望 . 我们可能会很幸运，在探索白人可能的开场动作中，两者都选择一个低于平均值的扇出，一个选择白色总是赢或赢或抽奖 .
我们也可能希望在某种程度上缩小国际象棋的定义，并说服每个人，它在道德上仍然是同一个游戏 . 我们真的需要在平局前要求重复三次位置吗？我们是否真的需要让失控派对展示50次逃跑的能力？有没有人甚至明白什么是通过规则？ ;）更严重的是，我们是否真的需要强迫玩家移动（而不是画或丢失）当他或她的唯一移动逃避检查或僵局是一个难以接受的捕获？如果所谓的非女王晋升不会导致立即检查或将死，我们是否可以限制可以晋升典当的棋子的选择？
我也不确定允许每个计算机基于散列访问大型后期游戏状态数据库及其可能的结果（在现有硬件和现有的游戏结束数据库上可能相对可行）有多少可以帮助更早地修剪搜索 . 显然你不能在没有O（n）存储的情况下记住整个函数，但是你可以选择一个大整数并记住许多结束从每个可能的（或者甚至不容易证明是不可能的，我认为）最终状态向后枚举的结束 .
我知道这有点不对劲，但我必须在这里投入5美分 . 对于计算机或人来说，有可能在胜利或僵局中结束他/她/它参与的每一个国际象棋游戏 .
然而，要实现这一目标，你必须确切地知道每一个可能的动作和反应等等，一直到每一个可能的游戏结果，并想象这一点，或者想要一个简单的方法来分析这些信息，想一想它作为一个不断分支的思维导图 .
中心节点将是游戏的开始 . 每个节点中的每个分支都将象征一个移动，每个移动都与其移动的移动不同 . 在这个庄园中展示它会花费很多资源，特别是如果你在纸上做这件事 . 在计算机上，这可能需要数百TB的数据，因为除非你让分支回来，否则会有很多重复的动作 .
然而，记住这些数据即使不是不可能，也是难以置信的 . 为了使计算机能够识别最佳的移动（最多）8个可能的瞬间移动，这是可能的，但不可能......因为计算机需要能够处理过去的所有分支，一直到结论，计算导致胜利或僵局的所有结论，然后根据失去结论的那些结论行动，这将要求RAM能够处理Terrabytes中的数据，或者更多！使用当今的技术，这样的计算机需要的不仅仅是世界上最富有的5个男人和/或女人的银行余额！
因此，经过所有这些考虑，可以做到，但是，没有人可以做到这一点 . 这样的任务需要今天有30位最聪明的人才，不仅在国际象棋中，而且在科学和计算机技术方面，这样的任务只能在a上完成（让我们把它完全放到基本的角度来看）......最终超级超级计算机......至少在一个世纪内不可能存在 . 将会完成！只是不在这一生 .
你的思想实验有两个错误：
如果您的图灵机不是"limited"（在记忆中，速度，......）您不需要使用启发式算法，但您可以计算评估最终状态（胜利，损失，平局） . 要找到完美的游戏，您只需要使用Minimax算法（参见http://en.wikipedia.org/wiki/Minimax）来计算每个玩家的最佳动作，这将导致一个或多个最佳游戏 .
使用的启发式的复杂性也没有限制 . 如果你可以计算出完美的游戏，那么还有一种方法可以从中计算出完美的启发式算法 . 如果需要的话，它只是一个能够映射国际象棋位置的功能“如果我在这种情况下，我的最佳动作是M” .
正如其他人已经指出的那样，这将以3种可能的结果结束：白色可以强制获胜，黑色可以强制获胜，其中一个可以强制平局 .
完美的跳棋游戏的结果已经被“计算”了 . 如果人类以前不会自我毁灭，那么有一天国际象棋也将计算出来，当时计算机已经进化到足以拥有足够的记忆和速度 . 或者我们有一些量子计算机......或者直到有人（研究员，国际象棋专家，天才）找到一些能够显着降低游戏复杂性的算法 . 举个例子：1到1000之间所有数字的总和是多少？你可以计算1 2 3 4 5 ... 999 1000，或者你可以简单地计算：N *（N 1）/ 2，其中N = 1000;结果= 500500.现在想象不知道那个公式，你不知道数学归纳，你甚至不知道如何乘法或加数，...所以，有可能当前有一个未知算法最终会降低此游戏的复杂性，只需5分钟即可计算出当前计算机的最佳移动速度 . 也许甚至可以用笔和纸来估计它是一个人，甚至在你的脑海里，给予更多的时间 .
所以，快速回答是：如果人类存活的时间足够长，那只是时间问题！
它可能是可以解决的，但是让我困扰的是：即使整个树都可以遍历，仍然无法预测对手的下一步行动 . 我们必须始终将我们的下一步行动 Build 在对手的状态上，并做出“最佳”行动 . 然后，根据下一个状态，我们再次进行 . 因此，如果对手以某种方式移动，我们的最佳移动可能是最佳的 . 对于对手的一些动作，我们的最后一步可能是次优的 .
我只是没有看到每一步都会有一个“完美”的举动 .
对于那种情况，必须为每个状态[在当前游戏中]成为树中的路径，导致胜利，无论对手的下一步行动（如在井字游戏中），我都很难时间搞清楚 .
在数学上，国际象棋已经被_625349解决了，这可以追溯到20世纪20年代（由波雷尔或冯诺伊曼发现） . 因此，图灵机确实可以完美地下棋 .
然而，国际象棋的计算复杂性使其几乎不可行 . 当前的引擎使用了几种改进和启发式方法 . 今天的顶级引擎在游戏强度方面已经超过了最优秀的人类，但是由于他们正在使用的启发式方法，当给予无限时间时它们可能不会发挥完美（例如，哈希冲突可能导致不正确的结果） .
我们目前在完美比赛方面最接近的是endgame tablebases . 生成它们的典型技术称为retrograde analysis . 目前，所有最多六件的位置都已解决 .
Yes ，在数学方面，国际象棋被归类为一个确定的游戏，这意味着它对每个第一个玩家都有一个完美的算法，即使对于infinate棋盘也证明这是真的，所以有一天，量子AI可能会找到完美的策略，然后游戏就消失了
此视频中的更多内容：https://www.youtube.com/watch?v=PN-I6u-AxMg
还有quantom国际象棋，没有数学证明确定游戏http://store.steampowered.com/app/453870/Quantum_Chess/
那里有关于quantom chess的详细视频https://chess24.com/en/read/news/quantum-chess
当然，只有10个可能的板上五十种可能组合的力量 . 考虑到这一点，为了适应每一次复合，你需要在10以下的力量下进行50次移动（包括重复次数乘以3） . 因此，在国际象棋中，一百次动作的力量不到十分之一 . 只需挑选那些导致将死的人，你就可以去了
64位数学（=棋盘）和按位运算符（=下一个可能的移动）就是你所需要的 . 这么简单 . 蛮力通常会找到最好的方式 . 当然，对于所有位置都没有通用算法 . 在现实生活中，计算也受到时间的限制，超时会使其停止 . 一个好的国际象棋程序意味着重型代码（传递，加倍的棋子等） . 小代码不能很强大 . 打开和结束数据库只是保存处理时间，某种预处理数据 . 我的意思是设备 - 操作系统，线程化，环境，硬件定义要求 . 编程语言很重要 . 无论如何，开发过程很有趣 .