最近我和一位非编码人员就国际象棋电脑的可能性进行了讨论.我不太懂理论,但想想我已经足够了解.
我认为不存在确定性的图灵机总是在国际象棋中获胜或陷入僵局.我认为,即使你搜索了玩家1/2移动的所有组合的整个空间,计算机在每一步决定的单一动作都是基于启发式的.基于启发式,它不一定能击败对手可以做的所有动作.
相反,我的朋友认为,如果计算机永远不会做出"错误"动作,那么计算机将永远胜出或结合(但是你定义了吗？).然而,作为一名采用CS的程序员,我知道即使你的好选择 - 给予明智的对手 - 也会迫使你最终做出"错误"的动作.即使你知道所有事情,你的下一步行动也是贪婪地匹配启发式.
大多数国际象棋计算机都试图将可能的最终游戏与正在进行的游戏相匹配,这本质上是一个动态的编程追溯.同样,有问题的最后阶段是可以避免的.
编辑:嗯......看起来我在这里乱了一些羽毛.非常好.
再考虑一下,似乎解决像国际象棋这样的有限游戏没有理论上的问题.我认为国际象棋比跳棋更复杂,因为胜利不一定是数字耗尽,而是通过配偶.我最初的断言可能是错误的,但我认为我已经指出了一些尚未得到令人满意的证明(正式).
我想我的思想实验是,无论何时树中的分支被采用,那么算法(或记忆路径)必须找到对手移动的任何可能分支的配偶路径(不进行交配).在讨论之后,我会购买比我们可能梦想的更多的内存,所有这些路径都可以找到.
"我认为不存在确定性的图灵机总是在国际象棋中赢得或陷入僵局."
你不太对劲.可以有这样的机器.问题是它必须搜索的国家空间的巨大.这是有限的,它真的很大.
这就是国际象棋回归启发式的原因 - 国家空间太大(但有限).甚至列举 - 更不用说搜索每个可能游戏的每个过程中的每个完美移动 - 将是一个非常非常大的搜索问题.
开场编写脚本,让你进入游戏中期,让你有一个"强势"的位置.不是已知的结果.即使是最终游戏 - 当数量较少时 - 很难枚举以确定最佳的下一步行动.从技术上讲,它们是有限的.但是替代品的数量巨大.即使是2个车手+国王也有22个可能的下一步动作.如果需要6次交配,你会看到12,855,002,631,049,216次移动.
打开动作的数学运算.虽然只有大约20个开场动作,但有大约30个左右的第二个动作,所以在第三个动作中我们正在寻找360,000个替代游戏状态.
但国际象棋比赛(技术上)是有限的.巨大但有限.有完美的信息.有定义的开始和结束状态,没有掷硬币或掷骰子.
我几乎不知道国际象棋究竟发现了什么.但作为一名数学家,这是我的理由:
首先,我们必须记住,怀特先走了,也许这给了他一个优势; 也许它给了布莱克一个优势.
现在假设布莱克没有完美的策略让他总能赢得/僵持.这意味着无论黑方做什么,白方都可以采取一种策略来赢得胜利.且慢-这意味着是白完美咯!
这告诉我们,两个玩家中至少有一个确实有一个完美的策略,让玩家总是赢或抽.
那么只有三种可能性:
如果他打得很完美,白方总能获胜
如果他打得很好,黑人总能获胜
一个玩家可以赢得或抽奖,如果他玩得很完美(如果两个玩家都玩得很完美,那么他们总是陷入僵局)
但其中哪一项实际上是正确的,我们可能永远不会知道.
这个问题的答案是肯定的:必须有一个完美的国际象棋算法,至少对于两个球员中的一个.
已经证明,对于棋子游戏来说,一个程序总能赢得或打败游戏.也就是说,没有选择一个玩家可以做出的动作迫使另一个玩家失败.
研究人员花了将近20年的时间来完成500亿亿可能的跳棋位置,顺便说一下,这仍然是国际象棋位置数量的极小部分.跳棋的努力包括顶级玩家,他们帮助研究团队将程序员的经验法则变成了软件,这些软件将移动分类为成功或不成功.然后研究人员让程序运行,平均每天运行50台计算机.有些日子,程序运行在200台机器上.研究人员监测进展情况并相应调整程序.事实上,奇诺克在1994年击败人类赢得了跳棋世界冠军.
是的,你可以解决国际象棋,不,你不会很快.
这不是关于计算机的问题,而是关于国际象棋的问题.
问题是,是否存在永不丢失游戏的故障安全策略？如果存在这样的策略,那么知道所有东西的计算机总是可以使用它并且它不再是启发式的.
例如,游戏井字游戏通常基于启发式来玩.但是,存在一种故障安全策略.无论对手如何移动,如果你从一开始就做到这一点,你总能找到避免输掉游戏的方法.
因此,您需要证明国际象棋是否存在这样的策略.它基本上是一样的,只是可能的移动空间要大得多.
我很晚才到这个帖子,你已经意识到了一些问题.但作为一名前大师和前职业国际象棋程序员,我想我可以添加一些有用的事实和数据.有几种方法可以衡量国际象棋的复杂程度:
国际象棋比赛总数约为10 ^(10 ^ 50).这个数字难以想象.
40次或更少的国际象棋比赛的数量大约是10 ^ 40.这仍然是一个非常大的数字.
可能的国际象棋位置数量约为10 ^ 46.
完整的国际象棋搜索树(香农数)大约是10 ^ 123,基于平均分支因子35和平均游戏长度80.
为了比较,可观察宇宙中的原子数通常估计为大约10 ^ 80.
所有6件或更少的结束游戏都经过整理和解决.
我的结论是:虽然国际象棋在理论上是可以解决的,但我们永远不会有钱,动力,计算能力或存储能力.
事实上,有些游戏已经解决了.Tic-Tac-Toe是一个非常容易构建的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年存在),而该计算机将一直致力于解决井字棋....这1955年的情况并非如此.计算费用昂贵且不会用于此目的,虽然我不相信Tic-Tac-Toe被计算机视为"解决"的日期,但我是确定它落后于实际的计算能力.
此外,考虑到45年内1000美元的价值将比现在减少约4倍,因此计算能力将继续变得更便宜,可以投入更多资金用于此类项目.
它实际上是可以为双方球员有在没有良序无限的游戏制胜战略; 国际象棋是有序的.事实上,由于50个移动规则,游戏可以拥有的移动数量有一个上限,因此只有有限的许多可能的国际象棋游戏(可以枚举以完全解决...理论上,至少 :)
现代国际象棋程序现在的工作方式支持你的论点结束.它们以这种方式工作,因为它的资源太强,无法将国际象棋程序编码为确定性操作.他们不一定总是那样工作.有一天国际象棋有可能被解决,如果发生这种情况,它很可能会被计算机解决.
为了记录,有些计算机可以赢得或与跳棋打成平手.我不确定是否可以为国际象棋做同样的事情.移动次数要高得多.而且,事情会发生变化,因为碎片可以向任何方向移动,而不仅仅是向前和向后移动.我认为虽然我不确定,国际象棋是确定性的,但是目前有太多可能的动作让计算机在合理的时间内确定所有动作.
我想你已死了.像Deep Blue和Deep Thought这样的机器被编程有许多预定义的游戏,以及用于将树解析为这些游戏的末端的聪明算法.当然,这是一种戏剧性的过度简化.总是有机会在游戏过程中"击败"计算机.通过这个我的意思是做一个移动,迫使计算机做出一个不太理想的移动(无论是什么).如果计算机在移动的时间限制之前找不到最佳路径,那么通过选择一个不太理想的路径可能会犯错误.
还有另一类国际象棋程序使用真正的机器学习,或遗传编程/进化算法.一些程序已经进化并使用神经网络等来做出决策.在这种情况下,我会想象计算机可能会犯"错误",但最终还是会取得胜利.
有一本关于这种名为Blondie24的GP的书,你可能会读到这本书.这是关于跳棋,但它可以适用于国际象棋.
从博弈论这个问题来看,答案是肯定国际象棋可以完美发挥.游戏空间是已知的/可预测的,是的,如果你有孙子的量子计算机,你可以消除所有的启发式.
您现在可以用任何脚本语言编写一个完美的井字游戏机,它可以实时完美地播放.
奥赛罗是另一款当前计算机可以轻松完美播放的游戏,但机器的内存和CPU需要一些帮助
国际象棋在理论上是可行的,但实际上并不可能(2008年)
i-Go很棘手,它的可能性空间超出了宇宙中原子的数量,所以我们可能需要一些时间才能制造出完美的i-Go机器.
国际象棋是矩阵游戏的一个例子,根据定义,它具有最佳结果(想想纳什均衡).如果玩家1和玩家2各自采取最佳动作,则总会达到某种结果(无论是胜利还是未知).
作为二十世纪七十年代的国际象棋程序员,我对此肯定有一个看法.我大约10年前写的,今天基本上是真的:
"未完成的工作和对国际象棋程序员的挑战"
那时候,我认为如果做得好,我们可以按常规解决国际象棋问题.
Checkers最近解决了(Yay,加拿大阿尔伯塔大学!!!)但这实际上是Brute Force完成的.按惯例做国际象棋,你必须更聪明.
当然,除非量子计算成为现实.如果是这样,国际象棋将像Tic-Tac-Toe一样轻松解决.
在1970年代早期的"科学美国人"杂志中,有一个引起我注意的短暂模仿.国际象棋游戏是由俄罗斯国际象棋电脑解决的.它已经确定白棋有一个完美的举动,可以确保双方完美发挥的胜利,这一举动是:1.a4!
京公网安备 11010802040832号 | 京ICP备19059560号-6 