algorithm - 国际象棋有完美的算法吗？

Question

我最近在与一位非编码人员讨论国际象棋计算机的可能性。我对理论并不精通，但我认为我知道的足够多。

我认为，不可能存在一个总是在国际象棋中获胜或陷入僵局的确定性图灵机。我认为，即使您搜索 player1/2 动作的所有组合的整个空间，计算机在每一步中决定的单个动作也是基于启发式的。基于启发式，它不一定能击败对手可以做的所有动作。

相反，我的朋友认为，如果计算机从不犯“错误”举动，那么它总是会赢或打平（但是您如何定义？）。但是，作为一个学过 CS 的程序员，我知道即使是你的好选择——给定一个聪明的对手——最终也会迫使你做出“错误”的举动。即使你什么都知道，你的下一步行动是贪婪地匹配一个启发式。

大多数国际象棋计算机试图将可能的最终游戏与正在进行的游戏相匹配，这本质上是一种动态编程回溯。再一次，有问题的残局是可以避免的。

编辑：嗯......看起来我在这里激怒了一些羽毛。那挺好的。

再想一想，解决像国际象棋这样的有限游戏似乎没有理论上的问题。我认为国际象棋比跳棋要复杂一点，因为获胜不一定是通过棋子的数字耗尽，而是通过队友。我最初的断言可能是错误的，但话又说回来，我想我已经指出了一些尚未得到令人满意的证明（正式）的东西。

我想我的思想实验是，每当树中的一个分支被取走时，算法（或记忆的路径）必须为对手移动的任何可能分支找到一条通向配偶的路径（而不是交配）。讨论后，我会购买，因为内存比我们想象的要多，所有这些路径都可以找到。

Answer 1

“我认为不可能存在一个总是在国际象棋中获胜或陷入僵局的确定性图灵机。”

你不太对。可以有这样的机器。问题是它必须搜索的状态空间巨大。它是有限的，它真的很大。

这就是国际象棋依赖启发式的原因——状态空间太大（但有限）。甚至列举——更不用说在每一个可能的游戏的每一个过程中搜索每一个完美的移动——将是一个非常非常大的搜索问题。

开局的脚本是为了让你进入一个给你一个“强大”位置的游戏中期。不是一个已知的结果。即使是最后的比赛——当棋子较少时——也很难列举出最佳的下一步行动。从技术上讲，它们是有限的。但是替代品的数量是巨大的。即使是 2 车 + 国王也有 22 种可能的下一步行动。如果需要 6 步才能配对，那么您将看到 12,855,002,631,049,216 步。

对开局动作进行数学计算。虽然只有大约 20 个开始动作，但有大约 30 个第二个动作，所以到第三个动作时，我们正在查看 360,000 个替代游戏状态。

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

Answer 2

我对国际象棋的实际发现几乎一无所知。但作为一名数学家，这是我的推理：

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

现在假设黑方没有完美的策略让他总是获胜/相持。这意味着无论黑方做什么，白方都可以遵循一种策略来取胜。等一下——这意味着白方有一个完美的策略！

这告诉我们，至少两个玩家中的一个确实有一个完美的策略，可以让那个玩家总是赢或平。

那么只有三种可能：

• 如果白棋打得完美，白棋总能赢
• 如果黑棋打得完美，黑棋总能赢
• 如果一名球员发挥出色，他就可以获胜或平局（如果两名球员都发挥出色，那么他们总是处于胶着状态）

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

问题的答案是肯定的：国际象棋必须有一个完美的算法，至少对于两个棋手之一。

Answer 3

对于跳棋游戏已经证明，一个程序总是可以赢得或平局。也就是说，没有一个玩家可以做出迫使另一玩家输的动作的选择。

研究人员花了将近 20 年的时间研究了5000 亿个可能的跳棋位置，顺便说一句，这仍然只是国际象棋位置数量的极小部分。跳棋工作包括顶级玩家，他们帮助研究团队将跳棋经验法则编程到将移动分类为成功或不成功的软件中。然后研究人员让程序运行，平均每天有 50 台计算机运行。有些日子，该程序在 200 台机器上运行。当研究人员监测进展并相应地调整程序时。事实上，奇努克早在 1994 年就击败了人类赢得了跳棋世界冠军。

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

Answer 4

这不是关于计算机的问题，而只是关于国际象棋的问题。

问题是，是否存在永不输掉比赛的防故障策略？如果存在这样的策略，那么什么都知道的计算机总是可以使用它，它不再是启发式的。

例如，井字游戏通常基于启发式进行。但是，存在故障安全策略。无论对手怎么走，你总能找到避免输掉比赛的方法，如果你从一开始就做到这一点。

因此，您需要证明这种策略是否也适用于国际象棋。基本上是一样的，只是可能动作的空间要大得多。

Answer 5

我很晚才来到这个线程，你已经意识到了一些问题。但作为一名前大师和前专业国际象棋程序员，我想我可以添加一些有用的事实和数据。有几种方法可以衡量国际象棋的复杂性：

• 棋局总数约为 10^(10^50)。这个数字大得难以想象。
• 40步以下的棋局数在10^40左右。这仍然是一个非常大的数字。
• 可能的国际象棋位置数约为 10^46。
• 完整的国际象棋搜索树（香农数）约为 10^123，基于 35 的平均分支因子和 80 的平均游戏长度。
• 作为比较，可观测宇宙中的原子数通常估计为 10^80 左右。
• 6张以下的残局全部整理并解决。

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

Answer 6

事实上，有些游戏已经解决了。Tic-Tac-Toe 是一种非常简单的游戏，可以构建一个总是赢或平的 AI。最近，连接 4 也被解决了（这表明对第二名玩家不公平，因为完美的游戏会导致他输掉）。

然而，国际象棋还没有解决，我认为没有任何证据表明这是一场公平的比赛（即完美的下棋是否会导致平局）。不过，从理论上讲，国际象棋的可能棋子配置数量是有限的。因此，搜索空间是有限的（尽管非常大）。因此，确实存在可以完美运行的确定性图灵机。然而，是否可以建造一个是另一回事。

Answer 7

实际上，在没有良序的无限博弈中，双方玩家都有可能拥有获胜策略；然而，国际象棋是井然有序的。事实上，由于50 步规则，一盘棋的步数是有上限的，因此国际象棋的可能棋局只有有限多（可以枚举出精确解……理论上，至少 ：）

Answer 8

到 2040 年（5x10^20 计算），平均 1000 美元的台式机将能够在 5 秒内解决跳棋。

即使以这种速度，100 台这样的计算机仍然需要大约 6.34 x 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，甚至可能会比预期的增长更快。

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

另一方面，井字游戏非常简单，有 2,653,002 种可能的计算（使用开放式棋盘）。1990 年实现了在大约 2.5 秒（每秒 100 万次计算）内解决井字游戏的计算能力。

向后移动，在 1955 年，一台计算机有能力在大约 1 个月内解决井字游戏（每秒 1 次计算）。同样，这是基于如果您可以将其打包成一台计算机（1000 美元的台式机显然在 1955 年不存在），您将获得 1000 美元的收益，而这台计算机将致力于解决井字游戏.... 1955 年的情况并非如此。计算很昂贵，不会用于此目的，尽管我不相信有任何日期井字游戏被计算机视为“解决”，但我确保它落后于实际的计算能力。

此外，考虑到 45 年后 1000 美元的价值将比现在低 4 倍左右，因此可以将更多的钱用于此类项目，而计算能力将继续变得更便宜。

Answer 9

现代国际象棋程序现在的工作方式支持你的论点。他们之所以这样工作，是因为编写一个国际象棋程序来确定性地运行太耗费资源了。他们不一定总是那样工作。国际象棋有可能有一天会被解决，如果发生这种情况，它很可能会被计算机解决。

Answer 10

作为 1970 年代的国际象棋程序员，我对此肯定有意见。我大约 10 年前写的，今天仍然基本正确：

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

那时，我认为如果处理得当，我们可以用传统的方式解决国际象棋。

跳棋最近被解决了（耶，加拿大阿尔伯塔大学！！！）但这实际上是蛮力完成的。要按照传统方式下棋，你必须更聪明。

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

在 1970 年代早期的《科学美国人》中，有一个简短的模仿引起了我的注意。这是一个公告，国际象棋游戏由俄罗斯国际象棋计算机解决。它已经确定了白棋有一个完美的棋步，可以确保双方都完美的打法，这一步棋是：1. a4！

Answer 11

作为记录，有些计算机可以在跳棋中获胜或打平。我不确定国际象棋是否可以这样做。移动的数量要高得多。此外，事情会发生变化，因为棋子可以向任何方向移动，而不仅仅是向前和向后。我认为虽然我不确定，国际象棋是确定性的，但是对于计算机而言，目前有太多可能的移动方式无法在合理的时间内确定所有移动方式。

Answer 12

我想你死定了。像 Deep Blue 和 Deep Thought 这样的机器编程了许多预定义的游戏，以及将树解析到这些游戏的末端的聪明算法。当然，这是一种戏剧性的过度简化。在游戏过程中总是有机会“击败”计算机。我的意思是做出一个动作，迫使计算机做出一个不太理想的动作（不管是什么）。如果计算机在移动的时间限制之前无法找到最佳路径，它很可能会通过选择不太理想的路径之一而犯错误。

还有另一类国际象棋程序使用真正的机器学习或遗传编程/进化算法。一些程序已经进化并使用神经网络等来做出决策。在这种情况下，我会想象计算机可能会犯“错误”，但最终还是会取得胜利。

有一本关于这种类型 GP 的引人入胜的书叫做Blondie24，你可能会读到。它是关于跳棋的，但它也适用于国际象棋。

Answer 13

从博弈论来看，这就是这个问题的意义所在，答案是肯定的，国际象棋可以完美下棋。游戏空间是已知/可预测的，是的，如果您拥有孙子的量子计算机，您可能会消除所有启发式方法。

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

奥赛罗是目前电脑可以轻松完美玩的另一款游戏，但机器的内存和CPU需要一点帮助

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

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

Answer 14

国际象棋是矩阵博弈的一个例子，根据定义，它具有最佳结果（想想纳什均衡）。如果玩家 1 和 2 各自采取最佳行动，则总是会达到某个结果（是否是输赢还是未知数）。

Answer 15

这里的很多答案都构成了重要的博弈论点：

1. 国际象棋是一种有限的、确定性的游戏，具有关于游戏状态的完整信息
2. 您可以解决有限游戏并确定完美策略
3. 然而，国际象棋足够大，你将无法用蛮力方法完全解决它

然而，这些观察忽略了一个重要的实际点：没有必要完美地解决完整的游戏才能创造出无与伦比的机器。

事实上，您很有可能在不搜索可能状态空间的一小部分的情况下创建一个无与伦比的国际象棋机器（即永远不会输，并且总是会强制获胜或平局）。

例如，以下技术都大大减少了所需的搜索空间：

• Alpha/Beta 或MTD-f等树修剪技术已经大大减少了搜索空间
• 可证明的获胜位置。许多结局都属于这一类：例如，您无需搜索 KR 与 K，这是一个经过验证的胜利。通过一些工作，可以证明更多有保证的胜利。
• 几乎可以肯定的胜利——因为“足够好”的比赛没有任何愚蠢的错误（比如 ELO 2200+？），许多国际象棋位置几乎是肯定的胜利，例如体面的物质优势（例如额外的骑士）没有补偿位置优势。如果你的程序可以强制这样一个位置，并且有足够好的启发式方法来检测位置优势，它可以安全地假设它会以 100% 的概率获胜或至少平局。
• 树搜索启发式 - 通过足够好的模式识别，您可以快速专注于“有趣”动作的相关子集。这就是人类大师的比赛方式，所以这显然不是一个糟糕的策略......而且我们的模式识别算法不断变得更好
• 风险评估 - 通过将计算能力集中在结果更不确定的情况（这是静默搜索的自然扩展），更好地理解职位的“风险”将实现更有效的搜索

通过上述技术的正确组合，我很乐意断言可以创建一个“无与伦比的”国际象棋游戏机。我们可能与当前的技术相差不远。

请注意，证明这台机器无法被击败几乎肯定更难。它可能类似于 Reimann 假设——我们很确定它会完美运行，并且经验结果表明它从未输过（包括对自身的数十亿顺子平局），但我们实际上并没有能力证明给我看。

关于“完美”的附加说明：

我注意不要将机器描述为博弈论意义上的“完美”，因为这意味着异常强大的附加条件，例如：

• 无论获胜组合多么复杂，在任何可能迫使获胜的情况下始终获胜。在赢/平之间的边界上会有一些情况，这很难完美计算。
• 利用所有关于对手打法中潜在缺陷的可用信息，例如推断对手可能过于贪婪并故意打出比平时稍弱的路线，因为它更有可能诱使对手犯错。对抗不完美的对手，如果你估计你的对手可能不会发现强制获胜，那么实际上输掉比赛可能是最佳选择，这会让你自己获胜的可能性更高。

完美（特别是考虑到不完美和未知的对手）是一个比简单的无与伦比更难的问题。

Answer 16

这是完全可以解决的。

有 10^50 个奇数位置。据我估计，每个位置至少需要存储 64 个圆形字节（每个正方形有：2 个附属位，3 个片段位）。整理它们后，可以识别将死的位置，并且可以比较位置以形成关系，显示哪些位置导致大型结果树中的其他位置。

然后，如果存在这样的事情，程序只需要找到最低的只有一侧将死根。无论如何，国际象棋在第一段的末尾相当简单地解决了。

Answer 17

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

在国际象棋中，白方可以强制获胜，或者黑色可以强制获胜，或者双方都可以强制至少平局。

逻辑在我看来是合理的。

Answer 18

如果您搜索 player1/2 移动的所有组合的整个空间，则计算机在每一步中决定的单个移动是基于启发式的。

那里有两个相互竞争的想法。一个是你搜索每一个可能的动作，另一个是你根据启发式做出决定。启发式是一种进行良好猜测的系统。如果你正在搜索每一个可能的动作，那么你就不再猜测了。

Answer 19

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

1. 如果您的图灵机不是“有限的”（在内存、速度等方面），您不需要使用启发式算法，但您可以计算评估最终状态（赢、输、平）。要找到完美的游戏，您只需要使用 Minimax 算法（请参阅http://en.wikipedia.org/wiki/Minimax）计算每个玩家的最佳移动，这将导致一个或多个最佳游戏。

2. 使用的启发式算法的复杂性也没有限制。如果您可以计算出完美的游戏，那么还有一种方法可以从中计算出完美的启发式。如果需要，它只是一个以“如果我处于这种情况 S 我最好的移动是 M”的方式映射国际象棋位置的功能。

正如其他人已经指出的那样，这将导致 3 种可能的结果：白色可以强制获胜，黑色可以强制获胜，其中一个可以强制平局。

完美跳棋游戏的结果已经被“计算”出来。如果人类以前不会毁灭自己，那么有一天，当计算机已经进化到足够的内存和速度时，国际象棋也会有计算。或者我们有一些量子计算机……或者直到有人（研究人员、国际象棋专家、天才）找到一些可以显着降低游戏复杂性的算法。举个例子：1到1000之间所有数字的总和是多少？您可以计算 1+2+3+4+5...+999+1000，也可以简单地计算：N*(N+1)/2 with N = 1000; 结果 = 500500。现在想象不知道那个公式，你不知道数学归纳法，你甚至不知道如何乘法或加法，......所以，可能有一种目前未知的算法最终会降低该游戏的复杂性，并且只需 5 分钟即可使用当前计算机计算出最佳移动。也许甚至可以用笔和纸来估计它是一个人，或者甚至在你的脑海中，再给一些时间。

所以，快速的答案是：如果人类存活的时间足够长，那只是时间问题！

Answer 20

“国际象棋有完美的算法吗？”

就在这里。也许白棋总是赢。也许黑方总是赢。也许至少双方总是打成平手。我们不知道是哪一个，也永远不会知道，但它肯定存在。

也可以看看

• 上帝的算法

Answer 21

我知道这有点麻烦，但我必须把我的 5 美分放在这里。计算机或个人有可能以胜利或相持的方式结束他/她/它参与的每一场国际象棋比赛。

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

中心节点将是游戏的开始。每个节点的每个分支都象征着一个动作，每个分支都与其兄弟动作不同。在这个庄园里展示它需要很多资源，特别是如果你在纸上做这个。在计算机上，这可能需要数百太字节的数据，因为您将有很多重复动作，除非您让分支回来。

然而，记住这些数据是不可信的，如果不是不可能的话。为了让计算机识别出从（最多）8 个即时可能的移动中取出的最佳移动，这是可能的，但并不合理......因为该计算机需要能够处理该移动之后的所有分支，一直到得出结论，计算所有导致胜利或僵局的结论，然后根据获胜结论的数量对失败的结论采取行动，这将需要能够处理泰字节或更多数据的 RAM！以今天的技术，像这样的计算机需要的不仅仅是世界上 5 位最富有的男人和/或女人的银行余额！

所以经过这么多考虑，它是可以做到的，但是，没有人能做到。这样的任务需要 30 位当今世界上最聪明的头脑，不仅在国际象棋方面，而且在科学和计算机技术方面，而这样的任务只能在（让我们完全从基本角度来看）......超级超级计算机……它不可能存在至少一个世纪。将会完成！只是这辈子没有。

Answer 22

我只有 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^10 次普朗克时间或每 10^-34 秒评估一次移动。这是一个难以置信的短时间（比有史以来观察到的最短时间短约 16 个数量级）。让我们乐观地说，在现有或预见的非量子 P 是 NP 技术的正确子集之上运行一个超级好的实现，我们可以希望评估（采取单步向前，以 100 MHz 的速率（每 10^-8 秒一次）将结果状态分类为中间状态或三个最终状态之一。由于该算法非常可并行化，因此我们需要 10^26 台这样的计算机，或者我体内的每个原子大约需要一台，以及收集它们的结果的能力。

我想对于蛮力解决方案总是有一线希望。我们可能会很幸运，并且在仅探索白方可能的开局走法之一时，都选择了扇出远低于平均水平的走法和白方总是获胜或获胜或平局的走法。

我们也可以希望在某种程度上缩小国际象棋的定义，并让每个人相信它在道德上仍然是相同的游戏。我们真的需要在平局之前要求位置重复3次吗？我们真的需要让逃跑的一方展示50步的逃跑能力吗？有没有人明白过路规则到底是怎么回事？;) 更严重的是，我们真的需要强迫玩家移动（而不是平局或失败），而他或她的唯一动作是为了逃避检查或僵局是路过的俘虏吗？如果所需的非皇后升级不会导致立即检查或将死，我们是否可以限制可以升级棋子的棋子的选择？

我也不确定允许每台计算机基于哈希访问大型数据库的后期游戏状态及其可能的结果（这在现有硬件和现有的残局数据库上可能相对可行）有助于更早地修剪搜索。显然，如果没有 O(n) 存储，您将无法记住整个函数，但是您可以选择一个大整数并记住从每个可能的（或者甚至不容易证明是不可能的，我想）结束状态向后枚举的许多残局。

Answer 23

在数学上，国际象棋已经由Minimax 算法解决，该算法可以追溯到 1920 年代（由 Borel 或 von Neumann 发现）。因此，图灵机确实可以下完美的国际象棋。

然而，国际象棋的计算复杂性使其实际上是不可行的。当前的引擎使用了一些改进和启发式方法。今天的顶级引擎在游戏强度方面已经超过了最优秀的人类，但由于他们使用的启发式算法，当给定无限时间时，它们可能无法完美运行（例如，哈希冲突可能导致不正确的结果）。

就完美游戏而言，我们目前最接近的是残局表库。生成它们的典型技术称为逆行分析。目前，所有最多六件的位置都已解决。

Answer 24

只是可能可以解决，但有件事困扰着我：即使可以遍历整棵树，仍然无法预测对手的下一步行动。我们必须始终根据对手的状态采取下一步行动，并做出“最好的”行动。然后，根据下一个状态，我们再做一次。因此，如果对手以某种方式移动，我们的最优移动可能是最优的。对于对手的某些动作，我们的最后一步可能是次优的。

我只是看不到如何在每一步中都有“完美”的举动。

为此，[当前游戏中]的每个状态都必须在树中存在一条通往胜利的路径，无论对手的下一步行动如何（如井字游戏），而且我很难时间想通了。

Answer 25

是的，在数学上，国际象棋被归类为一种确定的游戏，这意味着它对每个第一个玩家都有一个完美的算法，即使对于无限的棋盘，这也被证明是正确的，所以有一天量子人工智能可能会找到完美的策略，游戏结束了

此视频中的更多信息：https ://www.youtube.com/watch?v=PN-I6u-AxMg

还有量子国际象棋，没有数学证明它是确定的游戏http://store.steampowered.com/app/453870/Quantum_Chess/

那里有关于量子国际象棋的详细视频https://chess24.com/en/read/news/quantum-chess

Answer 26

当然，棋盘上只有 50 种可能组合的 10 次方。考虑到这一点，要玩每一个组合，你需要进行 10 次以下的 50 次移动（包括重复将这个数字乘以 3）。因此，国际象棋中一百步的次方不到十。只需选择那些导致将死的人，你就可以走了

Answer 27

您只需要 64 位数学（=棋盘）和位运算符（=下一个可能的移动）。如此简单。蛮力通常会找到最好的方法。当然，没有适用于所有位置的通用算法。在现实生活中计算也有时间限制，超时会停止。一个好的国际象棋程序意味着繁重的代码（通过，加倍棋子等）。小代码不能很强大。打开和残局数据库只是节省处理时间，某种预处理数据。设备，我的意思是——操作系统、线程能力、环境、硬件定义要求。编程语言很重要。无论如何，开发过程很有趣。