是否有一个完美的算法下棋吗？ [英] Is there a perfect algorithm for chess?

问题描述

最近我在用非codeR人在国际象棋电脑的可能性进行了讨论。我不精通理论，但想我知道就好了。

I was recently in a discussion with a non-coder person on the possibilities of chess computers. I'm not well versed in theory, but think I know enough.

我认为，有可能不存在确定性图灵机始终赢得或僵持在下棋。我认为，即使你搜索PLAYER1 / 2移动，一次移动的所有组合的整个空间，计算机决定后，在每一个步骤是基于启发式。基于启发式之中，它不一定打败所有的动作，对手可以做的。

I argued that there could not exist a deterministic Turing machine that always won or stalemated at chess. I think that, even if you search the entire space of all combinations of player1/2 moves, the single move that the computer decides upon at each step is based on a heuristic. Being based on a heuristic, it does not necessarily beat ALL of the moves that the opponent could do.

我的朋友认为，与此相反，一台计算机总是赢或领带，如果它从来没有一个错误的举动（但是你确定吗？）。然而，作为谁采取CS程序员，我知道，即使你的好选择 - 给一个明智的对手 - 可以迫使你做到底错的动作。即使你什么都知道，你的下一步行动是贪婪匹配启发式。

My friend thought, to the contrary, that a computer would always win or tie if it never made a "mistake" move (however do you define that?). However, being a programmer who has taken CS, I know that even your good choices - given a wise opponent - can force you to make "mistake" moves in the end. Even if you know everything, your next move is greedy in matching a heuristic.

大多数国际象棋计算机试图将一个可能的最终游戏匹配到游戏中进展，这实质上是一个动态编程回溯。再次，在讨论的最后阶段是可以避免的，但。

Most chess computers try to match a possible end game to the game in progress, which is essentially a dynamic programming traceback. Again, the endgame in question is avoidable though.

编辑：嗯...看起来像我在这里竖起了一些羽毛。这是很好的。

Hmm... looks like I ruffled some feathers here. That's good.

再仔细想想，好像有一个与解决一个有限的游戏，如国际象棋没有理论问题。我认为，国际象棋是一个比较复杂一点比在跳棋的胜利并不一定是件数值枯竭，而是由队友。我原来的说法也许是错误的，但话又说回来，我想我已经指出了一些不令人满意地证明（正式）。

Thinking about it again, it seems like there is no theoretical problem with solving a finite game like chess. I would argue that chess is a bit more complicated than checkers in that a win is not necessarily by numerical exhaustion of pieces, but by a mate. My original assertion is probably wrong, but then again I think I've pointed out something that is not yet satisfactorily proven (formally).

我想我的思想实验是，每当在树中的一个分支，则算法（或背诵路径）必须找到一种途径伴侣（没有得到交​​配），用于对对手移动的任何可能的分支。讨论结束后，我会买，鉴于更多的内存，比我们都不可能梦想，所有这些路径可寻。

I guess my thought experiment was that whenever a branch in the tree is taken, then the algorithm (or memorized paths) must find a path to a mate (without getting mated) for any possible branch on the opponent moves. After the discussion, I will buy that given more memory than we can possibly dream of, all these paths could be found.

推荐答案

我认为，有可能不存在确定性图灵机始终赢得或僵持在下棋。

"I argued that there could not exist a deterministic Turing machine that always won or stalemated at chess."

您是不完全正确。可以有这样的机器。问题是状态空间，这将要搜索的广大。它是有限的，它只是真的大。

You're not quite right. There can be such a machine. The issue is the hugeness of the state space that it would have to search. It's finite, it's just REALLY big.

这就是为什么国际象棋回落启发式 - 状态空间过于巨大的（但有限的）。甚至列举 - 沿每一个可能的游戏的每一个过程中每一个完美的移动少得多的搜索 - 将是一个非常，非常大的搜索问题

That's why chess falls back on heuristics -- the state space is too huge (but finite). To even enumerate -- much less search for every perfect move along every course of every possible game -- would be a very, very big search problem.

开口的脚本，让你到游戏中期，给你一个强的位置。没有一个已知的结果。即使结束游戏 - 当有少件 - 难以列举，以确定最佳的下一步行动。从技术上讲，他们是有限的。但替代的数目是巨大的​​。即使是2乌鸦+国王拥有像22可能的下一步行动。而如果它需要6移动到队友，你看12,855,002,631,049,216行动。

Openings are scripted to get you to a mid-game that gives you a "strong" position. Not a known outcome. Even end games -- when there are fewer pieces -- are hard to enumerate to determine a best next move. Technically they're finite. But the number of alternatives is huge. Even a 2 rooks + king has something like 22 possible next moves. And if it takes 6 moves to mate, you're looking at 12,855,002,631,049,216 moves.

请在开局数学。虽然只有大约20开放举措，有像30左右秒的动作，所以由第三招，我们正在寻找替代36万游戏状态。

Do the math on opening moves. While there's only about 20 opening moves, there are something like 30 or so second moves, so by the third move we're looking at 360,000 alternative game states.

不过，国际象棋游戏（技术）有限的。巨大的，但有限的。有完善的信息。有明确的起点和最终状态，没有硬币抛或掷骰。

But chess games are (technically) finite. Huge, but finite. There's perfect information. There are defined start and end-states, There are no coin-tosses or dice rolls.

这篇关于是否有一个完美的算法下棋吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！