国际象棋有完美的算法吗?

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

你说得不对。可能有这样一台机器。问题是它必须搜索的州空间之大。它是有限的,只是 很大。

这就是为什么国际象棋依赖于启发式——状态空间太大(但有限)。甚至列举——更不用说在每一个游戏的每一个过程中寻找每一个完美的动作——都是一个非常非常大的搜索问题。

开场白是为了给你一个“强势”的位置。结果不得而知。即使是最后的游戏——当棋子更少的时候——也很难列举出下一步的最佳动作。从技术上讲,它们是有限的。但替代品的数量是巨大的。即使是2辆车+国王也有22个可能的下一步行动。如果需要6步才能配对,你需要12855002631049216步。

但国际象棋游戏(技术上)是有限的。巨大,但有限。有完美的信息。有明确的开始和结束状态,没有硬币投掷或骰子卷。

我对国际象棋的发现几乎一无所知。但作为一名数学家,我的理由是:

首先,我们必须记住,白人先去,也许这给了他一个优势;也许这给了黑人一个优势。

没有完美的策略 对布莱克来说,这让他总是获胜/陷入僵局。这就意味着,无论布莱克做什么,都有一个策略是白人可以遵循的。等等-这意味着 是

这告诉我们两个玩家中至少有一个 有一个完美的策略,让球员总是赢或平。

那么,只有三种可能性:

• 如果怀特打得很好,他总能赢
• 如果布莱克打得很好,他总能赢
• 如果一个球员打得很好,他可以赢也可以平(如果两个球员都打得很好,那么他们总是陷入僵局)

但哪一个是正确的,我们可能永远不会知道。

这个问题的答案是 对

事实证明 game of checkers 一个程序总是可以赢得或平局的。也就是说,没有一个玩家可以选择的动作来迫使另一个玩家失败。

顺便说一句,通过5000亿个可能的棋位,这仍然是国际象棋棋位数量的一小部分。跳棋的努力包括顶级玩家,他们帮助研究团队将跳棋的经验法则编入软件,将动作分为成功或失败。然后研究人员让程序运行,平均每天运行50台计算机。有几天,这个程序在200台机器上运行。而研究人员则监测进展并相应地调整程序。事实上,奇努克早在1994年就击败人类赢得了跳棋世界冠军。

是的,你可以下棋,不,你不会很快下棋的。

这不是一个关于计算机的问题,而是一个关于国际象棋的问题。

问题是,是否存在一种永不输掉游戏的防故障策略?如果这种策略存在,那么一台无所不知的计算机就可以一直使用它,而不再是一种启发式方法。

因此,你需要证明这样的策略是否存在,以及国际象棋。基本上是一样的,只是可能的移动空间要大得多。

我很晚才谈到这个话题,你已经意识到了一些问题。但作为一个前大师和前专业象棋程序员,我想我可以添加一些有用的事实和数字。有几种方法可以测量 complexity of chess :

• 下棋40步或以下的棋数约为10^40。这仍然是一个非常大的数字。
• 根据平均分支因子35和平均游戏长度80,完整的象棋搜索树(香农数)约为10^123。
• 相比之下,可观测宇宙中的原子数量通常估计在10^80左右。
• collated and solved .

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

然而,国际象棋还没有解决,我认为没有任何证据表明这是一场公平的比赛(即完美的比赛是否会导致平局)。严格地说,从理论的角度来看,国际象棋有有限的可能的棋子配置。因此,搜索空间是有限的(尽管非常大)。因此,一个确定的图灵机器,可以发挥完美的存在。然而,能否建造一座是另一回事。

即使以这样的速度,仍需要100台这样的计算机大约6.34 x 10^19 年

在2080年左右,我们的台式机平均每秒大约有10^45次计算。一台计算机在大约27.7小时内就有计算能力解国际象棋。只要计算能力像过去30年一样继续增长,到2080年肯定会实现。

到2090年,一台价值1000美元的台式机将拥有足够的计算能力,可以在1秒钟内解出国际象棋……所以到那一天,这将是非常微不足道的。

鉴于checkers是在2007年解决的,而在1秒内解决它的计算能力将落后大约33-35年,我们可能可以 粗略地 估计国际象棋将在2055-2057年之间解决。可能更早,因为有更多的计算能力可用(45年后会是这种情况),更多的资金可以投入到这样的项目中。不过,我认为最早2050年,最晚2060年。

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

另一方面,Tic-Tac-Toe的游戏,简单得多,有2653002个可能的计算(有一个开放板)。1990年实现了在大约250秒(每秒100万次计算)内求解Tic-Tac-Toe的计算能力。

向后看,在1955年,一台计算机有能力在大约1个月内(每秒1次计算)解决Tic-Tac-Toe。同样,这是基于如果你能把1000美元打包到一台电脑上(一台1000美元的台式机显然在1955年并不存在),你会得到多少钱, 和 这台电脑本可以用来解决Tic-Tac-Toe的问题……但在1955年就不是这样了。计算是昂贵的,不会被用于这个目的,虽然我不相信有任何日期的Tic-Tac-Toe被认为是“解决”了计算机,但我相信它落后于实际的计算能力。

另外,考虑到45年内1000美元的价值将是现在的4倍,所以更多的钱可以用于这样的项目,而计算能力将继续变得更便宜。

实际上 is possible 50-move rule ,一个游戏的移动次数有一个上限,因此只有有限多个可能的棋局

现代象棋程序的工作方式支持你的论点 现在 . 它们这样工作是因为资源太紧张,无法对一个象棋程序进行确定的操作编码。他们不一定 这样做。国际象棋有可能 solved ,如果发生这种情况,很可能会被计算机解决。

有记录显示,有些电脑可以在 checkers . 我不确定象棋是否也能这样。移动的次数要高得多。而且,事情之所以会改变,是因为碎片可以朝任何方向移动,而不仅仅是向前或向后。我认为,虽然我不确定,国际象棋是确定的,但有太多的可能的移动,目前计算机确定所有的移动在一个合理的时间量。

我想你已经死定了。像“深蓝”和“深邃思维”这样的机器是用一些预定义的游戏和聪明的算法来编程的,这些算法可以将树解析为这些游戏的结尾。当然,这是戏剧性的过分简单化。在游戏过程中总有机会“击败”电脑。我的意思是做一个动作,迫使计算机做出一个不太理想的动作(不管是什么)。如果计算机在移动的时间限制之前找不到最佳路径,它很可能会选择一条不太理想的路径而犯错误。

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

Blondie24 你可能会读到。它是关于跳棋的,但也可以应用于国际象棋。

从博弈论的角度看,这就是问题所在,答案是:象棋是可以完美下棋的。游戏空间是已知的/可预测的,是的,如果你有孙子的量子计算机,你可能会消除所有的启发式。

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

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

作为一个70年代的国际象棋程序员,我对这个问题肯定有自己的看法。我10年前写的,今天基本上还是真的:

"Unfinished Work and Challenges to Chess Programmers"

那时候,我想如果下棋做得好的话,我们可以按惯例下棋。

跳棋最近被解决了(耶,加拿大阿尔伯塔大学!!!)但这实际上是用蛮力做的。要按惯例下棋,你必须更聪明。

当然,除非, Quantum Computing 变成现实。如果是这样的话,国际象棋将像井字游戏一样容易解决。

在20世纪70年代初的《科学美国人》中,有一个简短的模仿引起了我的注意。这是一个宣布,国际象棋比赛是由俄罗斯象棋计算机解决的。它已经确定,对于怀特来说,有一个完美的举动可以确保双方都能在完美的比赛中获胜,那就是:1。a4!

1. 国际象棋是一种有限的、确定性的游戏,它具有关于游戏状态的完整信息
2. 你可以解决一个有限的游戏,并确定一个完美的策略

然而,这些观察忽略了一个重要的实际问题: 没有必要为了创造一台无与伦比的机器而完美地解决整个游戏 .

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

• MTD-f 已经大大减少了搜索空间
• 几乎可以肯定的胜利-为了“足够好”而不犯任何愚蠢的错误(比如说埃洛2200+?)许多棋位几乎都是肯定的胜利,例如一个体面的物质优势(例如一个额外的骑士)没有补偿位置优势。如果你的程序可以强制这样一个位置,并有足够好的启发式检测位置优势,它可以安全地假设它将赢得或至少以100%的概率抽签。
• 树搜索启发式-有足够好的模式识别,你可以迅速集中在相关的子集“有趣”的举动。这就是人类大师们的游戏方式,所以这显然不是一个坏策略。。。。。我们的模式识别算法也在不断的改进
• Quiescence Search )

有了以上技术的正确结合,我会很舒服地断言,有可能创造出一个“无与伦比”的国际象棋游戏机。我们可能离目前的技术还不远。

注意,几乎可以肯定的是 证明 这台机器不能被打败。它可能类似于Reimann假设——我们非常肯定它的表现完美,并且会有实证结果表明它从未输过(包括几十亿的直接平局),但我们实际上没有能力证明它。

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

• 无论获胜的组合有多复杂,在任何可能迫使获胜的情况下都要获胜。在赢球和平局之间的边界上会有这样的情况,这是很难完美计算的。
• 充分利用对手游戏中潜在缺陷的所有可用信息,例如推断对手可能过于贪婪,故意打出比平时稍弱的一条线,理由是这条线更有可能诱使对手犯错。事实上,对不完美的对手来说 失败的 如果你估计你的对手可能看不到这场硬性胜利,那你就有更高的概率赢得自己。

完美(特别是考虑到不完美和未知的对手)是 许多的 比简单的无敌更难的问题。

有两个相互竞争的想法。一个是你搜索每一个可能的移动,另一个是你基于启发式的决定。启发式是一种做出正确猜测的系统。如果你在寻找每一个可能的行动,那么你就不再猜测了。

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

是的。也许是怀特永远赢了。也许黑人总是能赢。也许这对双方来说都是最起码的。我们不知道,也永远不会知道,但它确实存在。

另见

• God's algorithm

我找到这个了 article by John MacQuarrie Ernst Friedrich Ferdinand Zermelo . 得出以下结论:

在我看来,这一逻辑是合理的。

这是完全可以解决的。

有10^50个奇数位置。据我估计,每个位置至少需要64个字节来存储(每个正方形有:2个从属位,3个位)。一旦它们被整理,可以识别出棋友的位置,并对位置进行比较,形成一种关系,显示出在一个大的结果树中哪些位置导致了其他位置。

然后,如果存在这样一个东西,程序只需要找到最低的单侧checkmate根。无论如何,国际象棋在第一段的结尾是相当简单的。

我只有99.9%的人相信这样的说法,即国家空间的大小使人们不可能希望找到解决办法。

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

在最长的游戏中,移动次数的界限是多少?因为所有的游戏都以有限的移动结束,所以存在这样一个界限,称之为m。

从初始状态开始,不能枚举O(m)空间中的所有n个移动吗?当然,这需要O(n)时间,但宇宙大小的争论并不能直接解决这个问题。O(m)空间可能不太大。对于O(m)空间,你不能也追踪,在这个穿越过程中,沿着你正在穿越的路径的任何状态的延续是否会导致hermaywin、hermayforcedraw、WhiteMayWin、WhiteMayWinOrForceDraw、BlackMayWin或BlackMayWinOrForceDraw?(有一个晶格,根据轮到谁,使用晶格相交来注释遍历历史中的每个状态。)

除非我遗漏了什么,否则这是一个O(n)时间/O(m)空间算法,用于确定国际象棋可能属于哪些类别。维基百科援引普朗克时间约为10^60的宇宙年龄估计。在不涉及宇宙学争论的情况下,让我们猜测宇宙的热/冷/无论什么死亡之前还有那么多时间。这就需要我们每10^10普朗克一次,或者每10^34秒评估一次移动。这是一个不可能的短时间(大约比观测到的最短时间短16个数量级)。让我们乐观地说,如果一个超级重复的好的实现运行在现有的或者说是非量子的NP技术的一个适当的子集上,我们可以希望对其进行评估(向前迈出一步,以100兆赫(每10^-8秒一次)的速率将结果状态分类为中间状态或三个结束状态之一。由于这个算法是非常并行的,这就使得我们需要10^26台这样的计算机,或者我身体中每一个原子都需要一台这样的计算机,以及收集结果的能力。

我想对于暴力解决方案总有一线希望。我们可能会很幸运,在探索怀特可能的开场动作中,我们都会选择一个比平均扇形分叉低得多的动作,以及一个怀特总是赢或赢或平的动作。

我们也可以希望在某种程度上缩小国际象棋的定义,并说服所有人,这仍然是一个道德上相同的游戏。我们真的需要在平局前重复3次位置吗?我们真的需要让逃跑的一方展示50步逃跑的能力吗?有人知道到底是怎么回事吗 暂时的 规则?;)更严重的是,我们真的需要强迫一个球员移动(而不是抽签或输球),当他或她唯一的移动是为了逃避检查或僵局是 抓捕?如果所需的非皇后级升级没有导致立即检查或将死,我们是否可以限制典当可以升级的棋子的选择?

我知道这有点颠簸,但我得把我的5美分放在这里。一台电脑,或者一个人,有可能结束他/她/她参与的每一场国际象棋比赛,无论是胜利还是僵局。

然而,要做到这一点,你必须准确地知道每一个可能的动作和反应等等,一直到每一个可能的游戏结果,并将其形象化,或者以一种简单的方式分析这些信息,把它想象成一个不断延伸的思维导图。

中心节点将是游戏的开始。每个节点的每个分支都代表一个移动,每个分支都不同于其bretheren移动。在这个庄园里展示它需要很多资源,特别是如果你是在纸上做的话。在计算机上,这可能需要数百个Terrabytes的数据,因为您将有很多重复的移动,除非您使分支返回。

然而,要记住这些数据,即使不是不可能,也是不可能的。要使计算机识别出最理想的移动,从(最多)8个即时可能的移动中取出,是可能的,但不可编造。。。因为这台计算机需要能够处理过去所有移动的分支,一直到得出结论为止,计算所有导致胜负或僵局的结论,然后根据胜负结论的数量对失败的结论采取行动,这将需要能够处理Terrabytes或更多数据的RAM!而在当今的科技条件下,像这样的电脑所需的资金将超过世界上最富有的5位男性和/或女性的银行存款余额!

所以,经过这么多考虑,这是可以做到的,然而,没有人能做到。这样一个任务需要30个当今最聪明的头脑,不仅是在国际象棋,而且在科学和计算机技术方面,这样一个任务只能在一个(让我们把它完全放在基本的角度)上完成。。。超级超级电脑。。。至少一个世纪都不可能存在。一定会成功的!只是这辈子没有。

你的思维实验有两个错误:

1. 如果你的图灵机器不是“有限的”(在内存中,速度,…),你不需要使用启发式,但是你可以计算出最终的状态(赢,输,平)。为了找到完美的游戏,你只需要使用Minimax算法(参见 http://en.wikipedia.org/wiki/Minimax )计算每个玩家的最佳移动,这将导致一个或多个最佳游戏。

2. 使用的启发式算法的复杂性也没有限制。如果你能计算出一个完美的游戏,还有一种方法可以从中计算出一个完美的启发式。如果需要的话,它只是一个映射棋位的函数,就像“如果我在这种情况下,我最好的移动是m”。

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

所以,最快的答案是:如果人类生存的时间足够长,那只是时间问题!

这也许是可以解决的,但有件事困扰着我: 即使可以穿越整棵树,仍然无法预测对手的下一步行动。我们必须始终根据对手的状态采取下一步行动,并提供“最佳”行动。然后,根据下一个状态,我们再做一次。

我只是不明白在每一步中怎么会有一个“完美”的动作。

要做到这一点,(在目前的游戏中)每个州都必须有一条通向胜利的道路,不管对手下一步怎么走(就像在tic tac toe),我很难想象。

在数学上,象棋已经被 Minimax algorithm ,它可以追溯到20世纪20年代(由Borel或von Neumann发现)。因此,图灵机器确实可以下完美的国际象棋。

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

我们目前在完美发挥方面最接近的是 endgame tablebases . 生成它们的典型技术称为 retrograde analysis . 目前,所有的位置多达六件已经解决。

是的 ,在数学上,象棋被归类为一个确定的游戏,这意味着它对每一个第一个玩家都有一个完美的算法,这被证明是正确的,即使是对内插棋盘,所以有一天一个全通人工智能可能会找到完美的策略,而这个游戏就不存在了

在本视频中详细介绍: 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

当然 板上50个可能的组合只有10倍的能量。考虑到这一点,要玩到每一个组合,你需要在10到50步的力量(包括重复乘以3)。所以,国际象棋的百步威力只有不到十步。只要选那些能让你被将死的,你就可以走了

64位数学(=棋盘)和按位运算符(=下一个可能的移动)是您所需要的全部。很简单。暴力通常会找到最好的办法。当然,并不是所有位置都有通用算法。在现实生活中计算时间也是有限的,超时就会停止。一个好的象棋程序意味着繁重的代码(通过、加倍的棋子等)。小代码不可能很强。打开和结束游戏数据库只是节省了处理时间,一些预处理的数据。设备,我的意思是-操作系统,线程,环境,硬件定义需求。编程语言很重要。总之,开发过程很有趣。