最近我和一位非编码人员就国际象棋电脑的可能性进行了讨论.我不太懂理论,但想想我已经足够了解.
我认为不存在确定性的图灵机总是在国际象棋中获胜或陷入僵局.我认为,即使你搜索了玩家1/2移动的所有组合的整个空间,计算机在每一步决定的单一动作都是基于启发式的.基于启发式,它不一定能击败对手可以做的所有动作.
相反,我的朋友认为,如果计算机永远不会做出"错误"动作,那么计算机将永远胜出或结合(但是你定义了吗？).然而,作为一名采用CS的程序员,我知道即使你的好选择 - 给予明智的对手 - 也会迫使你最终做出"错误"的动作.即使你知道所有事情,你的下一步行动也是贪婪地匹配启发式.
大多数国际象棋计算机都试图将可能的最终游戏与正在进行的游戏相匹配,这本质上是一个动态的编程追溯.同样,有问题的最后阶段是可以避免的.
编辑:嗯......看起来我在这里乱了一些羽毛.非常好.
再考虑一下,似乎解决像国际象棋这样的有限游戏没有理论上的问题.我认为国际象棋比跳棋更复杂,因为胜利不一定是数字耗尽,而是通过配偶.我最初的断言可能是错误的,但我认为我已经指出了一些尚未得到令人满意的证明(正式).
我想我的思想实验是,无论何时树中的分支被采用,那么算法(或记忆路径)必须找到对手移动的任何可能分支的配偶路径(不进行交配).在讨论之后,我会购买比我们可能梦想的更多的内存,所有这些路径都可以找到.