"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.
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.
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.
I know next to nothing about what's actually been discovered about chess. But as a mathematician, here's my reasoning:
First we must remember that White gets to go first and maybe this gives him an advantage; maybe it gives Black an advantage.
Now suppose that there is no perfect strategy for Black that lets him always win/stalemate. This implies that no matter what Black does, there is a strategy White can follow to win. Wait a minute - this means there is a perfect strategy for White!
This tells us that at least one of the two players does have a perfect strategy which lets that player always win or draw.
There are only three possibilities, then:
White can always win if he plays perfectly
Black can always win if he plays perfectly
One player can win or draw if he plays perfectly (and if both players play perfectly then they always stalemate)
But which of these is actually correct, we may never know.
The answer to the question is yes: there must be a perfect algorithm for chess, at least for one of the two players.
It has been proven for the game of checkers that a program can always win or tie the game. That is, there is no choice of moves that one player can make which force the other player into losing.
The researchers spent almost two decades going through the 500 billion billion possible checkers positions, which is still an infinitesimally small fraction of the number of chess positions, by the way. The checkers effort included top players, who helped the research team program checkers rules of thumb into software that categorized moves as successful or unsuccessful. Then the researchers let the program run, on an average of 50 computers daily. Some days, the program ran on 200 machines. While the researchers monitored progress and tweaked the program accordingly. In fact, Chinook beat humans to win the checkers world championship back in 1994.
Yes, you can solve chess, no, you won't any time soon.
This is not a question about computers but only about the game of chess.
The question is, does there exist a fail-safe strategy for never losing the game? If such a strategy exists, then a computer which knows everything can always use it and it is not a heuristic anymore.
For example, the game tic-tac-toe normally is played based on heuristics. But, there exists a fail-safe strategy. Whatever the opponent moves, you always find a way to avoid losing the game, if you do it right from the start on.
So you would need to proof that such a strategy exists or not for chess as well. It is basically the same, just the space of possible moves is vastly bigger.
I'm coming to this thread very late, and that you've already realised some of the issues. But as an ex-master and an ex-professional chess programmer, I thought I could add a few useful facts and figures. There are several ways of measuring the complexity of chess:
The total number of chess games is approximately 10^(10^50). That number is unimaginably large.
The number of chess games of 40 moves or less is around 10^40. That's still an incredibly large number.
The number of possible chess positions is around 10^46.
The complete chess search tree (Shannon number) is around 10^123, based on an average branching factor of 35 and an average game length of 80.
For comparison, the number of atoms in the observable universe is commonly estimated to be around 10^80.
Some games have, in fact, been solved. Tic-Tac-Toe is a very easy one for which to build an AI that will always win or tie. Recently, Connect 4 has been solved as well (and shown to be unfair to the second player, since a perfect play will cause him to lose).
Chess, however, has not been solved, and I don't think there's any proof that it is a fair game (i.e., whether the perfect play results in a draw). Speaking strictly from a theoretical perspective though, Chess has a finite number of possible piece configurations. Therefore, the search space is finite (albeit, incredibly large). Therefore, a deterministic Turing machine that could play perfectly does exist. Whether one could ever be built, however, is a different matter.
The average $1000 desktop will be able to solve checkers in a mere 5 seconds by the year 2040 (5x10^20 calculations).
Even at this speed, it would still take 100 of these computers approximately 6.34 x 10^19 years to solve chess. Still not feasible. Not even close.
Around 2080, our average desktops will have approximately 10^45 calculations per second. A single computer will have the computational power to solve chess in about 27.7 hours. It will definitely be done by 2080 as long as computing power continues to grow as it has the past 30 years.
By 2090, enough computational power will exist on a $1000 desktop to solve chess in about 1 second...so by that date it will be completely trivial.
Given checkers was solved in 2007, and the computational power to solve it in 1 second will lag by about 33-35 years, we can probably roughly estimate chess will be solved somewhere between 2055-2057. Probably sooner since when more computational power is available (which will be the case in 45 years), more can be devoted to projects such as this. However, I would say 2050 at the earliest, and 2060 at the latest.
In 2060, it would take 100 average desktops 3.17 x 10^10 years to solve chess. Realize I am using a $1000 computer as my benchmark, whereas larger systems and supercomputers will probably be available as their price/performance ratio is also improving. Also, their order of magnitude of computational power increases at a faster pace. Consider a supercomputer now can perform 2.33 x 10^15 calculations per second, and a $1000 computer about 2 x 10^9. By comparison, 10 years ago the difference was 10^5 instead of 10^6. By 2060 the order of magnitude difference will probably be 10^12, and even this may increase faster than anticipated.
Much of this depends on whether or not we as human beings have the drive to solve chess, but the computational power will make it feasible around this time (as long as our pace continues).
On another note, the game of Tic-Tac-Toe, which is much, much simpler, has 2,653,002 possible calculations (with an open board). The computational power to solve Tic-Tac-Toe in roughly 2.5 (1 million calculations per second) seconds was achieved in 1990.
Moving backwards, in 1955, a computer had the power to solve Tic-Tac-Toe in about 1 month (1 calculation per second). Again, this is based on what $1000 would get you if you could package it into a computer (a $1000 desktop obviously did not exist in 1955), and this computer would have been devoted to solving Tic-Tac-Toe....which was just not the case in 1955. Computation was expensive and would not have been used for this purpose, although I don't believe there is any date where Tic-Tac-Toe was deemed "solved" by a computer, but I'm sure it lags behind the actual computational power.
Also, take into account $1000 in 45 years will be worth about 4 times less than it is now, so much more money can go into projects such as this while computational power will continue to get cheaper.
It actually is possible for both players to have winning strategies in infinite games with no well-ordering; however, chess is well-ordered. In fact, because of the 50-move rule, there is an upper-limit to the number of moves a game can have, and thus there are only finitely many possible games of chess (which can be enumerated to solve exactly.. theoretically, at least :)
Your end of the argument is supported by the way modern chess programs work now. They work that way because it's way too resource-intense to code a chess program to operate deterministically. They won't necessarily always work that way. It's possible that chess will someday be solved, and if that happens, it will likely be solved by a computer.
我认为你已经死定了。 像 Deep Blue 和 Deep Thought 这样的机器是用许多预定义的游戏和巧妙的算法来编程的，可以将树解析为这些游戏的结果。 当然，这过于简单化了。 在游戏过程中总是有机会“击败”计算机。 我的意思是采取一个行动，迫使计算机采取一个不太理想的行动（无论是什么）。 如果计算机在移动时间限制之前无法找到最佳路径，它很可能会因为选择不太理想的路径之一而犯错误。
您可能会读一本关于此类 GP 的有趣书籍 Blondie24。 这是关于跳棋的，但它也适用于国际象棋。
I think you are dead on. Machines like Deep Blue and Deep Thought are programmed with a number of predefined games, and clever algorithms to parse the trees into the ends of those games. This is, of course, a dramatic oversimplification. There is always a chance to "beat" the computer along the course of a game. By this I mean making a move that forces the computer to make a move that is less than optimal (whatever that is). If the computer cannot find the best path before the time limit for the move, it might very well make a mistake by choosing one of the less-desirable paths.
There is another class of chess programs that uses real machine learning, or genetic programming / evolutionary algorithms. Some programs have been evolved and use neural networks, et al, to make decisions. In this type of case, I would imagine that the computer might make "mistakes", but still end up in a victory.
There is a fascinating book on this type of GP called Blondie24 that you might read. It is about checkers, but it could apply to chess.
For the record, there are computers that can win or tie at checkers. I'm not sure if the same could be done for chess. The number of moves is a lot higher. Also, things change because pieces can move in any direction, not just forwards and backwards. I think although I'm not sure, that chess is deterministic, but that there are just way too many possible moves for a computer to currently determine all the moves in a reasonable amount of time.
From game theory, which is what this question is about, the answer is yes Chess can be played perfectly. The game space is known/predictable and yes if you had you grandchild's quantum computers you could probably eliminate all heuristics.
You could write a perfect tic-tac-toe machine now-a-days in any scripting language and it'd play perfectly in real-time.
Othello is another game that current computers can easily play perfectly, but the machine's memory and CPU will need a bit of help
Chess is theoretically possible but not practically possible (in 2008)
i-Go is tricky, it's space of possibilities falls beyond the amount of atoms in the universe, so it might take us some time to make a perfect i-Go machine.
Chess is an example of a matrix game, which by definition has an optimal outcome (think Nash equilibrium). If player 1 and 2 each take optimal moves, a certain outcome will ALWAYS be reached (whether it be a win-tie-loss is still unknown).
Back then, I thought we could solve Chess conventionally, if done properly.
Checkers was solved recently (Yay, University of Alberta, Canada!!!) but that was effectively done Brute Force. To do chess conventionally, you'll have to be smarter.
Unless, of course, Quantum Computing becomes a reality. If so, chess will be solved as easily as Tic-Tac-Toe.
In the early 1970's in Scientific American, there was a short parody that caught my attention. It was an announcement that the game of chess was solved by a Russian chess computer. It had determined that there is one perfect move for white that would ensure a win with perfect play by both sides, and that move is: 1. a4!
Lots of answers here make the important game-theoretic points:
Chess is a finite, deterministic game with complete information about the game state
You can solve a finite game and identify a perfect strategy
Chess is however big enough that you will not be able to solve it completely with a brute force method
However these observations miss an important practical point: it is not necessary to solve the complete game perfectly in order to create an unbeatable machine.
It is in fact quite likely that you could create an unbeatable chess machine (i.e. will never lose and will always force a win or draw) without searching even a tiny fraction of the possible state space.
The following techniques for example all massively reduce the search space required:
Tree pruning techniques like Alpha/Beta or MTD-f already massively reduce the search space
Provable winning position. Many endings fall in this category: You don't need to search KR vs K for example, it's a proven win. With some work it is possible to prove many more guaranteed wins.
Almost certain wins - for "good enough" play without any foolish mistakes (say about ELO 2200+?) many chess positions are almost certain wins, for example a decent material advantage (e.g. an extra Knight) with no compensating positional advantage. If your program can force such a position and has good enough heuristics for detecting positional advantage, it can safely assume it will win or at least draw with 100% probability.
Tree search heuristics - with good enough pattern recognition, you can quickly focus on the relevant subset of "interesting" moves. This is how human grandmasters play so it's clearly not a bad strategy..... and our pattern recognition algorithms are constantly getting better
Risk assessment - a better conception of the "riskiness" of a position will enable much more effective searching by focusing computing power on situations where the outcome is more uncertain (this is a natural extension of Quiescence Search)
With the right combination of the above techniques, I'd be comfortable asserting that it is possible to create an "unbeatable" chess playing machine. We're probably not too far off with current technology.
Note that It's almost certainly harder to prove that this machine cannot be beaten. It would probably be something like the Reimann hypothesis - we would be pretty sure that it plays perfectly and would have empirical results showing that it never lost (including a few billion straight draws against itself), but we wouldn't actually have the ability to prove it.
Additional note regarding "perfection":
I'm careful not to describe the machine as "perfect" in the game-theoretic sense because that implies unusually strong additional conditions, such as:
Always winning in every situation where it is possible to force a win, no matter how complex the winning combination may be. There will be situations on the boundary between win/draw where this is extremely hard to calculate perfectly.
Exploiting all available information about potential imperfection in your opponent's play, for example inferring that your opponent might be too greedy and deliberately playing a slightly weaker line than usual on the grounds that it has a greater potential to tempt your opponent into making a mistake. Against imperfect opponents it can in fact be optimal to make a losing if you estimate that your opponent probably won't spot the forced win and it gives you a higher probability of winning yourself.
Perfection (particularly given imperfect and unknown opponents) is a much harder problem than simply being unbeatable.
There are 10^50 odd positions. Each position, by my reckoning, requires a minimum of 64 round bytes to store (each square has: 2 affiliation bits, 3 piece bits). Once they are collated, the positions that are checkmates can be identified and positions can be compared to form a relationship, showing which positions lead to other positions in a large outcome tree.
Then, the program needs only to find the lowest only one side checkmate roots, if such a thing exists. In any case, Chess was fairly simply solved at the end of the first paragraph.
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.
There are two competing ideas there. One is that you search every possible move, and the other is that you decide based on a heuristic. A heuristic is a system for making a good guess. If you're searching through every possible move, then you're no longer guessing.
Yes there is. Maybe it's for White to always win. Maybe it's for Black to always win. Maybe it's for both to always tie at least. We don't know which, and we'll never know, but it certainly exist.
There are two mistakes in your thought experiment:
If your Turing machine is not "limited" (in memory, speed, ...) you do not need to use heuristics but you can calculate evaluate the final states (win, loss, draw). To find the perfect game you would then just need to use the Minimax algorithm (see http://en.wikipedia.org/wiki/Minimax) to compute the optimal moves for each player, which would lead to one or more optimal games.
There is also no limit on the complexity of the used heuristic. If you can calculate a perfect game, there is also a way to compute a perfect heuristic from it. If needed its just a function that maps chess positions in the way "If I'm in this situation S my best move is M".
As others pointed out already, this will end in 3 possible results: white can force a win, black can force a win, one of them can force a draw.
The result of a perfect checkers games has already been "computed". If humanity will not destroy itself before, there will be also a calculation for chess some day, when computers have evolved enough to have enough memory and speed. Or we have some quantum computers... Or till someone (researcher, chess experts, genius) finds some algorithms that significantly reduces the complexity of the game. To give an example: What is the sum of all numbers between 1 and 1000? You can either calculate 1+2+3+4+5...+999+1000, or you can simply calculate: N*(N+1)/2 with N = 1000; result = 500500. Now imagine don't know about that formula, you don't know about Mathematical induction, you don't even know how to multiply or add numbers, ... So, it may be possible that there is a currently unknown algorithm that just ultimately reduces the complexity of this game and it would just take 5 Minutes to calculate the best move with a current computer. Maybe it would be even possible to estimate it as a human with pen & paper, or even in your mind, given some more time.
So, the quick answer is: If humanity survives long enough, it's just a matter of time!
I'm only 99.9% convinced by the claim that the size of the state space makes it impossible to hope for a solution.
Sure, 10^50 is an impossibly large number. Let's call the size of the state space n.
What's the bound on the number of moves in the longest possible game? Since all games end in a finite number of moves there exists such a bound, call it m.
Starting from the initial state, can't you enumerate all n moves in O(m) space? Sure, it takes O(n) time, but the arguments from the size of the universe don't directly address that. O(m) space might not even be very much. For O(m) space couldn't you also track, during this traversal, whether the continuation of any state along the path you are traversing leads to EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin, or BlackMayWinOrForceDraw? (There's a lattice depending on whose turn it is, annotate each state in the history of your traversal with the lattice meet.)
Unless I'm missing something, that's an O(n) time / O(m) space algorithm for determining which of the possible categories chess falls into. Wikipedia cites an estimate for the age of the universe at approximately 10^60th Planck times. Without getting into a cosmology argument, let's guess that there's about that much time left before the heat/cold/whatever death of the universe. That leaves us needing to evaluate one move every 10^10th Planck times, or every 10^-34 seconds. That's an impossibly short time (about 16 orders of magnitude shorter than the shortest times ever observed). Let's optimistically say that with a super-duper-good implementation running on top of the line present-or-forseen-non-quantum-P-is-a-proper-subset-of-NP technology we could hope to evaluate (take a single step forward, categorize the resulting state as an intermediate state or one of the three end states) states at a rate of 100 MHz (once every 10^-8 seconds). Since this algorithm is very parallelizable, this leaves us needing 10^26th such computers or about one for every atom in my body, together with the ability to collect their results.
I suppose there's always some sliver of hope for a brute-force solution. We might get lucky and, in exploring only one of white's possible opening moves, both choose one with much-lower-than-average fanout and one in which white always wins or wins-or-draws.
We could also hope to shrink the definition of chess somewhat and persuade everyone that it's still morally the same game. Do we really need to require positions to repeat 3 times before a draw? Do we really need to make the running-away party demonstrate the ability to escape for 50 moves? Does anyone even understand what the heck is up with the en passant rule? ;) More seriously, do we really need to force a player to move (as opposed to either drawing or losing) when his or her only move to escape check or a stalemate is an en passant capture? Could we limit the choice of pieces to which a pawn may be promoted if the desired non-queen promotion does not lead to an immediate check or checkmate?
I'm also uncertain about how much allowing each computer hash-based access to a large database of late game states and their possibly outcomes (which might be relatively feasible on existing hardware and with existing endgame databases) could help in pruning the search earlier. Obviously you can't memoize the entire function without O(n) storage, but you could pick a large integer and memoize that many endgames enumerating backwards from each possible (or even not easily provably impossible, I suppose) end state.
I know this is a bit of a bump, but I have to put my 5 cents worth in here. It is possible for a computer, or a person for that matter, to end every single chess game that he/she/it participates in, in either a win or a stalemate.
To achieve this, however, you must know precisely every possible move and reaction and so forth, all the way through to each and every single possible game outcome, and to visualize this, or to make an easy way of analyising this information, think of it as a mind map that branches out constantly.
The center node would be the start of the game. Each branch out of each node would symbolize a move, each one different to its bretheren moves. Presenting it in this manor would take much resources, especially if you were doing this on paper. On a computer, this would take possibly hundreds of Terrabytes of data, as you would have very many repedative moves, unless you made the branches come back.
To memorize such data, however, would be implausable, if not impossible. To make a computer recognize the most optimal move to take out of the (at most) 8 instantly possible moves, would be possible, but not plausable... as that computer would need to be able to process all the branches past that move, all the way to a conclusion, count all conclusions that result in a win or a stalemate, then act on that number of wining conclusions against losing conclusions, and that would require RAM capable of processing data in the Terrabytes, or more! And with todays technology, a computer like that would require more than the bank balance of the 5 richest men and/or women in the world!
So after all that consideration, it could be done, however, no one person could do it. Such a task would require 30 of the brightest minds alive today, not only in chess, but in science and computer technology, and such a task could only be completed on a (lets put it entirely into basic perspective)... extremely ultimately hyper super-duper computer... which couldnt possibly exist for at least a century. It will be done! Just not in this lifetime.
Mathematically, chess has been solved by the Minimax algorithm, which goes back to the 1920s (either found by Borel or von Neumann). Thus, a turing machine can indeed play perfect chess.
However, the computational complexity of chess makes it practically infeasible. Current engines use several improvements and heuristics. Top engines today have surpassed the best humans in terms of playing strength, but because of the heuristics that they are using, they might not play perfect when given infinite time (e.g., hash collisions could lead to incorrect results).
The closest that we currently have in terms of perfect play are endgame tablebases. The typical technique to generate them is called retrograde analysis. Currently, all position with up to six pieces have been solved.
It just might be solvable, but something bothers me: Even if the entire tree could be traversed, there is still no way to predict the opponent's next move. We must always base our next move on the state of the opponent, and make the "best" move available. Then, based on the next state we do it again. So, our optimal move might be optimal iff the opponent moves in a certain way. For some moves of the opponent our last move might have been sub-optimal.
I just fail to see how there could be a "perfect" move in every step.
For that to be the case, there must for every state [in the current game] be a path in the tree which leads to victory, regardless of the opponent's next move (as in tic-tac-toe), and I have a hard time figuring that.
Yes , in math , chess is classified as a determined game , that means it has a perfect algorithm for each first player , this is proven to be true even for infinate chess board , so one day probably a fast effective AI will find the perfect strategy, and the game is gone
Of course There's only 10 to the power of fifty possible combinations of pieces on the board. Having that in mind, to play to every compibation, you would need make under 10 to the power of fifty moves (including repetitions multiply that number by 3). So, there's less than ten to the power of one hundred moves in chess. Just pick those that lead to checkmate and you're good to go
64bit math (=chessboard) and bitwise operators (=next possible moves) is all You need. So simply. Brute Force will find the most best way usually. Of course, there is no universal algorithm for all positions. In real life the calculation is also limited in time, timeout will stop it. A good chess program means heavy code (passed,doubled pawns,etc). Small code can't be very strong. Opening and endgame databases just save processing time, some kind of preprocessed data. The device, I mean - the OS,threading poss.,environment,hardware define requirements. Programming language is important. Anyway, the development process is interesting.
发布评论
评论（27）
“我认为不可能存在一个在国际象棋比赛中总是获胜或陷入僵局的确定性图灵机。”
你说得不太对。 可以有这样的机器。 问题在于它必须搜索的状态空间巨大。 它是有限的，只是真的很大。
这就是国际象棋求助于启发式的原因——状态空间太大（但有限）。 甚至枚举——更不用说在每场可能的比赛的每一个过程中寻找每一个完美的动作——将是一个非常非常大的搜索问题。
开局的脚本是为了让你进入游戏中期，让你处于“强势”位置。 未知结果。 即使是残局——当棋子较少时——也很难通过枚举来确定下一步的最佳动作。 从技术上讲，它们是有限的。 但替代品的数量是巨大的。 即使是 2 个车+K，也有 22 种可能的下一步行动。 如果交配需要 6 次移动，则需要 12,855,002,631,049,216 次移动。
计算一下开局动作。 虽然只有大约 20 个开局棋步，但第二步棋步大约有 30 个左右，因此到第三步棋步时，我们将看到 360,000 种替代游戏状态。
但国际象棋游戏（技术上）是有限的。 巨大，但有限。 有完美的信息。 有明确的开始和结束状态，没有抛硬币或掷骰子。
"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.
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.
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.
我对国际象棋的实际发现几乎一无所知。 但作为一名数学家，我的理由是：
首先，我们必须记住，白棋先走，也许这给了他一个优势； 也许这会给黑方带来优势。
现在假设黑方没有完美的策略让他总是获胜/陷入僵局。 这意味着无论黑方做什么，白方都可以遵循一个策略来获胜。 等一下 - 这意味着白方有一个完美的策略！
这告诉我们，两名玩家中至少有一个拥有完美的策略，可以让该玩家总是获胜或平局。
那么只有三种可能性：
但其中哪一个实际上是否正确，我们可能永远不会知道。
这个问题的答案是是：国际象棋必须有一个完美的算法，至少对于两个棋手之一来说是这样。
I know next to nothing about what's actually been discovered about chess. But as a mathematician, here's my reasoning:
First we must remember that White gets to go first and maybe this gives him an advantage; maybe it gives Black an advantage.
Now suppose that there is no perfect strategy for Black that lets him always win/stalemate. This implies that no matter what Black does, there is a strategy White can follow to win. Wait a minute - this means there is a perfect strategy for White!
This tells us that at least one of the two players does have a perfect strategy which lets that player always win or draw.
There are only three possibilities, then:
But which of these is actually correct, we may never know.
The answer to the question is yes: there must be a perfect algorithm for chess, at least for one of the two players.
它已在跳棋游戏中得到验证一个程序总是可以赢得或打平比赛。 也就是说，一个玩家无法选择迫使另一玩家失败的行动。
是的，你可以解决国际象棋问题，不，你很快就做不到。
It has been proven for the game of checkers that a program can always win or tie the game. That is, there is no choice of moves that one player can make which force the other player into losing.
Yes, you can solve chess, no, you won't any time soon.
这不是关于计算机的问题，而只是关于国际象棋游戏的问题。
问题是，是否存在一种永远不会输掉比赛的万无一失的策略？ 如果存在这样的策略，那么知道一切的计算机总是可以使用它，并且它不再是启发式的。
例如，井字游戏通常是基于启发式玩的。 但是，存在一种自动防故障策略。 无论对手采取什么行动，如果你从一开始就采取正确的做法，你总能找到避免输掉比赛的方法。
所以你需要证明这样的策略对于国际象棋来说也存在或不存在。 基本上是一样的，只是可动的空间大了很多。
This is not a question about computers but only about the game of chess.
The question is, does there exist a fail-safe strategy for never losing the game? If such a strategy exists, then a computer which knows everything can always use it and it is not a heuristic anymore.
For example, the game tic-tac-toe normally is played based on heuristics. But, there exists a fail-safe strategy. Whatever the opponent moves, you always find a way to avoid losing the game, if you do it right from the start on.
So you would need to proof that such a strategy exists or not for chess as well. It is basically the same, just the space of possible moves is vastly bigger.
我很晚才开始讨论这个话题，而且您已经意识到了一些问题。 但作为一名前大师和前专业国际象棋程序员，我认为我可以添加一些有用的事实和数据。 有多种方法可以衡量国际象棋的复杂性：
我的结论是：虽然国际象棋在理论上是可以解决的，但我们永远不会有金钱、动力、计算能力或存储来解决它。
I'm coming to this thread very late, and that you've already realised some of the issues. But as an ex-master and an ex-professional chess programmer, I thought I could add a few useful facts and figures. There are several ways of measuring the complexity of chess:
My conclusion: while chess is theoretically solvable, we will never have the money, the motivation, the computing power, or the storage to ever do it.
事实上，有些游戏已经解决了。 Tic-Tac-Toe 是一种非常简单的游戏，构建一个总是能赢或平的 AI 非常简单。 最近，连线 4 也已得到解决（并且被证明对第二名玩家不公平，因为完美的比赛将导致他输掉）。
然而，国际象棋尚未得到解决，而且我认为没有任何证据表明这是一场公平的游戏（即，完美的比赛是否会导致平局）。 但严格从理论角度来看，国际象棋的可能棋子配置数量是有限的。 因此，搜索空间是有限的（尽管非常大）。 因此，能够完美运行的确定性图灵机确实存在。 然而，是否能够建成则是另一回事。
Some games have, in fact, been solved. Tic-Tac-Toe is a very easy one for which to build an AI that will always win or tie. Recently, Connect 4 has been solved as well (and shown to be unfair to the second player, since a perfect play will cause him to lose).
Chess, however, has not been solved, and I don't think there's any proof that it is a fair game (i.e., whether the perfect play results in a draw). Speaking strictly from a theoretical perspective though, Chess has a finite number of possible piece configurations. Therefore, the search space is finite (albeit, incredibly large). Therefore, a deterministic Turing machine that could play perfectly does exist. Whether one could ever be built, however, is a different matter.
到 2040 年，平均 1000 美元的台式机将能够在短短 5 秒内解决跳棋问题（5x10^20 计算）。
即使按照这个速度，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 美元的台式机），这台计算机将专门用于解决 Tic-Tac 问题-Toe...1955 年的情况并非如此。计算成本昂贵，不会用于此目的，尽管我不相信有任何日期 Tic-Tac-Toe 被视为“解决”一台计算机，但我确信它落后于实际的计算能力。
此外，考虑到 45 年后 1000 美元的价值将比现在少 4 倍左右，因此可以有更多资金投入此类项目，而计算能力将继续变得更便宜。
The average $1000 desktop will be able to solve checkers in a mere 5 seconds by the year 2040 (5x10^20 calculations).
Even at this speed, it would still take 100 of these computers approximately 6.34 x 10^19 years to solve chess. Still not feasible. Not even close.
Around 2080, our average desktops will have approximately 10^45 calculations per second. A single computer will have the computational power to solve chess in about 27.7 hours. It will definitely be done by 2080 as long as computing power continues to grow as it has the past 30 years.
By 2090, enough computational power will exist on a $1000 desktop to solve chess in about 1 second...so by that date it will be completely trivial.
Given checkers was solved in 2007, and the computational power to solve it in 1 second will lag by about 33-35 years, we can probably roughly estimate chess will be solved somewhere between 2055-2057. Probably sooner since when more computational power is available (which will be the case in 45 years), more can be devoted to projects such as this. However, I would say 2050 at the earliest, and 2060 at the latest.
In 2060, it would take 100 average desktops 3.17 x 10^10 years to solve chess. Realize I am using a $1000 computer as my benchmark, whereas larger systems and supercomputers will probably be available as their price/performance ratio is also improving. Also, their order of magnitude of computational power increases at a faster pace. Consider a supercomputer now can perform 2.33 x 10^15 calculations per second, and a $1000 computer about 2 x 10^9. By comparison, 10 years ago the difference was 10^5 instead of 10^6. By 2060 the order of magnitude difference will probably be 10^12, and even this may increase faster than anticipated.
Much of this depends on whether or not we as human beings have the drive to solve chess, but the computational power will make it feasible around this time (as long as our pace continues).
On another note, the game of Tic-Tac-Toe, which is much, much simpler, has 2,653,002 possible calculations (with an open board). The computational power to solve Tic-Tac-Toe in roughly 2.5 (1 million calculations per second) seconds was achieved in 1990.
Moving backwards, in 1955, a computer had the power to solve Tic-Tac-Toe in about 1 month (1 calculation per second). Again, this is based on what $1000 would get you if you could package it into a computer (a $1000 desktop obviously did not exist in 1955), and this computer would have been devoted to solving Tic-Tac-Toe....which was just not the case in 1955. Computation was expensive and would not have been used for this purpose, although I don't believe there is any date where Tic-Tac-Toe was deemed "solved" by a computer, but I'm sure it lags behind the actual computational power.
Also, take into account $1000 in 45 years will be worth about 4 times less than it is now, so much more money can go into projects such as this while computational power will continue to get cheaper.
实际上，两个玩家都可以在无限游戏中拥有获胜策略，而无需秩序井然； 然而，国际象棋是有秩序的。 事实上，由于 50 步规则，有一个上限游戏可以进行的步数，因此只有有限多种可能的国际象棋游戏（可以通过枚举来精确解决......至少理论上是这样:）
It actually is possible for both players to have winning strategies in infinite games with no well-ordering; however, chess is well-ordered. In fact, because of the 50-move rule, there is an upper-limit to the number of moves a game can have, and thus there are only finitely many possible games of chess (which can be enumerated to solve exactly.. theoretically, at least :)
现代国际象棋程序现在的工作方式支持了你的论点。 他们之所以这样工作，是因为编写一个国际象棋程序来确定性地运行需要消耗太多的资源。 它们不一定总是以这种方式工作。 国际象棋有可能有一天会被解决，如果发生这种情况，它很可能会被解决通过计算机。
Your end of the argument is supported by the way modern chess programs work now. They work that way because it's way too resource-intense to code a chess program to operate deterministically. They won't necessarily always work that way. It's possible that chess will someday be solved, and if that happens, it will likely be solved by a computer.
我认为你已经死定了。 像 Deep Blue 和 Deep Thought 这样的机器是用许多预定义的游戏和巧妙的算法来编程的，可以将树解析为这些游戏的结果。 当然，这过于简单化了。 在游戏过程中总是有机会“击败”计算机。 我的意思是采取一个行动，迫使计算机采取一个不太理想的行动（无论是什么）。 如果计算机在移动时间限制之前无法找到最佳路径，它很可能会因为选择不太理想的路径之一而犯错误。
还有另一类国际象棋程序使用真正的机器学习或遗传编程/进化算法。 一些程序已经发展并使用神经网络等来做出决策。 在这种情况下，我会想象计算机可能会犯“错误”，但最终仍然会取得胜利。
您可能会读一本关于此类 GP 的有趣书籍 Blondie24。 这是关于跳棋的，但它也适用于国际象棋。
I think you are dead on. Machines like Deep Blue and Deep Thought are programmed with a number of predefined games, and clever algorithms to parse the trees into the ends of those games. This is, of course, a dramatic oversimplification. There is always a chance to "beat" the computer along the course of a game. By this I mean making a move that forces the computer to make a move that is less than optimal (whatever that is). If the computer cannot find the best path before the time limit for the move, it might very well make a mistake by choosing one of the less-desirable paths.
There is another class of chess programs that uses real machine learning, or genetic programming / evolutionary algorithms. Some programs have been evolved and use neural networks, et al, to make decisions. In this type of case, I would imagine that the computer might make "mistakes", but still end up in a victory.
There is a fascinating book on this type of GP called Blondie24 that you might read. It is about checkers, but it could apply to chess.
根据记录，有些计算机可以在跳棋中获胜或打平。 我不确定国际象棋是否也可以这样做。 移动次数要多得多。 此外，事情也会发生变化，因为棋子可以向任何方向移动，而不仅仅是向前和向后移动。 我认为，尽管我不确定，国际象棋是确定性的，但计算机目前可能的走法太多，无法在合理的时间内确定所有走法。
For the record, there are computers that can win or tie at checkers. I'm not sure if the same could be done for chess. The number of moves is a lot higher. Also, things change because pieces can move in any direction, not just forwards and backwards. I think although I'm not sure, that chess is deterministic, but that there are just way too many possible moves for a computer to currently determine all the moves in a reasonable amount of time.
从这个问题的博弈论来看，答案是肯定的，国际象棋可以完美地进行。 游戏空间是已知/可预测的，是的，如果您拥有孙子的量子计算机，您可能可以消除所有启发式方法。
现在，您可以使用任何脚本语言编写完美的井字游戏机，并且它可以完美地实时运行。
黑白棋是另一种当前计算机可以轻松完美玩的游戏，但机器的内存和 CPU 需要一些帮助
国际象棋在理论上是可能的，但实际上不可能（2008 年）
i-Go 很棘手，它的可能性空间超出了数量宇宙中的原子，所以我们可能需要一些时间才能制造出完美的 i-Go 机器。
From game theory, which is what this question is about, the answer is yes Chess can be played perfectly. The game space is known/predictable and yes if you had you grandchild's quantum computers you could probably eliminate all heuristics.
You could write a perfect tic-tac-toe machine now-a-days in any scripting language and it'd play perfectly in real-time.
Othello is another game that current computers can easily play perfectly, but the machine's memory and CPU will need a bit of help
Chess is theoretically possible but not practically possible (in 2008)
i-Go is tricky, it's space of possibilities falls beyond the amount of atoms in the universe, so it might take us some time to make a perfect i-Go machine.
国际象棋是矩阵游戏的一个例子，根据定义，它具有最佳结果（想想纳什均衡）。 如果玩家 1 和玩家 2 各自采取最佳行动，那么总会达到一定的结果（是否胜负仍未知）。
Chess is an example of a matrix game, which by definition has an optimal outcome (think Nash equilibrium). If player 1 and 2 each take optimal moves, a certain outcome will ALWAYS be reached (whether it be a win-tie-loss is still unknown).
作为一名 1970 年代的国际象棋程序员，我对此肯定有自己的看法。 我大约 10 年前写的内容，今天仍然基本正确：
“未完成的工作和对国际象棋程序员的挑战” “
当时，我认为如果处理得当，我们可以用传统的方式解决国际象棋问题。
跳棋最近被解决了（是的，加拿大阿尔伯塔大学！！！），但这实际上是通过蛮力完成的。 要按照传统方式下棋，你必须更聪明。
当然，除非量子计算成为现实。 如果是这样，国际象棋就会像井字游戏一样容易解决。
1970 年代初，《科学美国人》上有一个简短的模仿作品引起了我的注意。 这是一个宣布，国际象棋游戏已由俄罗斯国际象棋计算机解决。 已经确定白棋有一个完美的棋步可以确保双方完美下棋获胜，该棋步是： 1. a4！
As a chess programmer from the 1970's, I definitely have an opinion on this. What I wrote up about 10 years ago, still is basically true today:
"Unfinished Work and Challenges to Chess Programmers"
Back then, I thought we could solve Chess conventionally, if done properly.
Checkers was solved recently (Yay, University of Alberta, Canada!!!) but that was effectively done Brute Force. To do chess conventionally, you'll have to be smarter.
Unless, of course, Quantum Computing becomes a reality. If so, chess will be solved as easily as Tic-Tac-Toe.
In the early 1970's in Scientific American, there was a short parody that caught my attention. It was an announcement that the game of chess was solved by a Russian chess computer. It had determined that there is one perfect move for white that would ensure a win with perfect play by both sides, and that move is: 1. a4!
这里的许多答案提出了重要的博弈论观点：
然而，这些观察忽略了一个重要的实用点：没有必要完美地解决整个游戏才能创建一个无与伦比的机器
事实上，您很可能可以创建一个无与伦比的国际象棋机器（即永远不会输，并且总是会迫使获胜或平局），而无需搜索可能的状态空间的一小部分。
例如，以下技术都大大减少了所需的搜索空间：
在 如果将上述技术正确结合起来，我可以放心地断言，有可能创建一个“无与伦比的”国际象棋机器。 我们距离当前的技术可能已经不远了。
请注意，几乎可以肯定要证明这台机器无法被击败。 这可能类似于雷曼假设——我们非常确定它运行完美，并且实证结果表明它从未输过（包括对自己进行数十亿次平局），但我们实际上没有能力证明给我看。
关于“完美”的附加说明：
我很小心，没有将机器描述为博弈论意义上的“完美”，因为这意味着异常强大的附加条件，例如：
完美（特别是考虑到不完美和未知的对手）是一个比单纯的不可战胜更困难的问题。
Lots of answers here make the important game-theoretic points:
However these observations miss an important practical point: it is not necessary to solve the complete game perfectly in order to create an unbeatable machine.
It is in fact quite likely that you could create an unbeatable chess machine (i.e. will never lose and will always force a win or draw) without searching even a tiny fraction of the possible state space.
The following techniques for example all massively reduce the search space required:
With the right combination of the above techniques, I'd be comfortable asserting that it is possible to create an "unbeatable" chess playing machine. We're probably not too far off with current technology.
Note that It's almost certainly harder to prove that this machine cannot be beaten. It would probably be something like the Reimann hypothesis - we would be pretty sure that it plays perfectly and would have empirical results showing that it never lost (including a few billion straight draws against itself), but we wouldn't actually have the ability to prove it.
Additional note regarding "perfection":
I'm careful not to describe the machine as "perfect" in the game-theoretic sense because that implies unusually strong additional conditions, such as:
Perfection (particularly given imperfect and unknown opponents) is a much harder problem than simply being unbeatable.
完全可以解决。
有 10^50 个奇数位置。 据我估计，每个位置至少需要 64 个圆字节来存储（每个方格有：2 个从属位，3 个片位）。 一旦对它们进行整理，就可以识别将死的位置，并且可以比较位置以形成关系，显示哪些位置导致大型结果树中的其他位置。
然后，程序只需要找到最低的一侧将死根（如果存在的话）。 无论如何，国际象棋在第一段末尾就相当简单地解决了。
It's perfectly solvable.
There are 10^50 odd positions. Each position, by my reckoning, requires a minimum of 64 round bytes to store (each square has: 2 affiliation bits, 3 piece bits). Once they are collated, the positions that are checkmates can be identified and positions can be compared to form a relationship, showing which positions lead to other positions in a large outcome tree.
Then, the program needs only to find the lowest only one side checkmate roots, if such a thing exists. In any case, Chess was fairly simply solved at the end of the first paragraph.
那里有两个相互竞争的想法。 一是你搜索每一个可能的动作，二是你根据启发式做出决定。 启发式是一种进行良好猜测的系统。 如果你正在搜索每一个可能的动作，那么你就不再是猜测了。
There are two competing ideas there. One is that you search every possible move, and the other is that you decide based on a heuristic. A heuristic is a system for making a good guess. If you're searching through every possible move, then you're no longer guessing.
就在这里。 也许白棋总是能赢。 也许黑棋总是能赢。 也许至少两者总是打成平手。 我们不知道是哪一个，也永远不会知道，但它确实存在。
另请参阅
Yes there is. Maybe it's for White to always win. Maybe it's for Black to always win. Maybe it's for both to always tie at least. We don't know which, and we'll never know, but it certainly exist.
See also
我发现这篇 John MacQuarrie 的文章 引用了“博弈论之父”Ernst Friedrich Ferdinand Zermelo 的著作。 得出以下结论：
我觉得这个逻辑是合理的。
I found this article by John MacQuarrie that references work by the "father of game theory" Ernst Friedrich Ferdinand Zermelo. It draws the following conclusion:
The logic seems sound to me.
你的思想实验中有两个错误：
如果你的图灵机没有“限制”（内存、速度等），你不需要使用启发式方法，但你可以计算评估最终状态（赢、输） ， 画）。 要找到完美的游戏，您只需要使用 Minimax 算法（请参阅 http://en.wikipedia。 org/wiki/Minimax）来计算每个玩家的最佳动作，这将导致一个或多个最佳游戏。
所使用的启发式方法的复杂性也没有限制。 如果您可以计算出完美的游戏，那么还有一种方法可以从中计算出完美的启发式。 如果需要，它只是一个以“如果我处于这种情况 S，我的最佳动作是 M”的方式映射国际象棋位置的函数。
正如其他人已经指出的，这将有3种可能的结果：白可以逼胜，黑可以逼胜，其中之一可以逼平。
完美的西洋跳棋游戏的结果已经被“计算”出来。 如果人类之前不会毁灭自己，那么有一天，当计算机进化到足以拥有足够的内存和速度时，国际象棋也会有计算。 或者我们有一些量子计算机......或者直到有人（研究员、国际象棋专家、天才）找到一些可以显着降低游戏复杂性的算法。 举个例子：1到1000之间所有数字的和是多少？ 您可以计算 1+2+3+4+5...+999+1000，也可以简单地计算：N*(N+1)/2，其中 N = 1000； 结果= 500500。现在想象一下，你不知道这个公式，你不知道数学归纳法，你甚至不知道如何乘法或加法，......所以，目前可能有一个未知的算法最终会降低这个游戏的复杂性，并且用当前的计算机只需要 5 分钟即可计算出最佳动作。 也许甚至可以用笔和笔来将其估计为人类。 给你一些时间，在纸上，甚至在你的脑海里。
所以，简单的答案是：如果人类生存得足够长，这只是时间问题！
There are two mistakes in your thought experiment:
If your Turing machine is not "limited" (in memory, speed, ...) you do not need to use heuristics but you can calculate evaluate the final states (win, loss, draw). To find the perfect game you would then just need to use the Minimax algorithm (see http://en.wikipedia.org/wiki/Minimax) to compute the optimal moves for each player, which would lead to one or more optimal games.
There is also no limit on the complexity of the used heuristic. If you can calculate a perfect game, there is also a way to compute a perfect heuristic from it. If needed its just a function that maps chess positions in the way "If I'm in this situation S my best move is M".
As others pointed out already, this will end in 3 possible results: white can force a win, black can force a win, one of them can force a draw.
The result of a perfect checkers games has already been "computed". If humanity will not destroy itself before, there will be also a calculation for chess some day, when computers have evolved enough to have enough memory and speed. Or we have some quantum computers... Or till someone (researcher, chess experts, genius) finds some algorithms that significantly reduces the complexity of the game. To give an example: What is the sum of all numbers between 1 and 1000? You can either calculate 1+2+3+4+5...+999+1000, or you can simply calculate: N*(N+1)/2 with N = 1000; result = 500500. Now imagine don't know about that formula, you don't know about Mathematical induction, you don't even know how to multiply or add numbers, ... So, it may be possible that there is a currently unknown algorithm that just ultimately reduces the complexity of this game and it would just take 5 Minutes to calculate the best move with a current computer. Maybe it would be even possible to estimate it as a human with pen & paper, or even in your mind, given some more time.
So, the quick answer is: If humanity survives long enough, it's just a matter of time!
我只有 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 技术上运行的超级好实现，我们可以希望评估（采取向前一步，以 100 MHz 的速率（每 10^-8 秒一次）将结果状态分类为中间状态或三个最终状态之一）状态。 由于该算法非常可并行化，因此我们需要 10^26 台这样的计算机，或者说我体内的每个原子都需要一台这样的计算机，并且能够收集它们的结果。
我想，对于暴力解决方案，总有一线希望。 我们可能会很幸运，在只探索白棋可能的开局棋之一时，双方都选择了扇出远低于平均水平的一棋，以及白棋总是获胜或赢或平的棋。
我们还可以希望稍微缩小国际象棋的定义，并说服每个人，它在道德上仍然是同一个游戏。 我们真的需要在抽奖前要求仓位重复 3 次吗？ 真的需要让逃跑方展现出50步逃跑的能力吗？ 有谁明白en passant规则到底是怎么回事吗？ ;) 更严重的是，当玩家逃脱检查或陷入僵局的唯一移动是en passant捕获时，我们真的需要强迫玩家移动（而不是平局或失败）吗？ 如果所需的非后晋级不会导致立即将死或将死，我们是否可以限制棋子可以晋级的棋子的选择？
我还不确定允许每台计算机基于哈希的访问后期游戏状态及其可能结果的大型数据库（这在现有硬件和现有游戏结束数据库上可能相对可行）可以在多大程度上帮助更早地修剪搜索。 显然，如果没有 O(n) 存储空间，您就无法记住整个函数，但是您可以选择一个大整数并记住从每个可能（或者我认为甚至不容易证明不可能）最终状态向后枚举的许多结局。
I'm only 99.9% convinced by the claim that the size of the state space makes it impossible to hope for a solution.
Sure, 10^50 is an impossibly large number. Let's call the size of the state space n.
What's the bound on the number of moves in the longest possible game? Since all games end in a finite number of moves there exists such a bound, call it m.
Starting from the initial state, can't you enumerate all n moves in O(m) space? Sure, it takes O(n) time, but the arguments from the size of the universe don't directly address that. O(m) space might not even be very much. For O(m) space couldn't you also track, during this traversal, whether the continuation of any state along the path you are traversing leads to EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin, or BlackMayWinOrForceDraw? (There's a lattice depending on whose turn it is, annotate each state in the history of your traversal with the lattice meet.)
Unless I'm missing something, that's an O(n) time / O(m) space algorithm for determining which of the possible categories chess falls into. Wikipedia cites an estimate for the age of the universe at approximately 10^60th Planck times. Without getting into a cosmology argument, let's guess that there's about that much time left before the heat/cold/whatever death of the universe. That leaves us needing to evaluate one move every 10^10th Planck times, or every 10^-34 seconds. That's an impossibly short time (about 16 orders of magnitude shorter than the shortest times ever observed). Let's optimistically say that with a super-duper-good implementation running on top of the line present-or-forseen-non-quantum-P-is-a-proper-subset-of-NP technology we could hope to evaluate (take a single step forward, categorize the resulting state as an intermediate state or one of the three end states) states at a rate of 100 MHz (once every 10^-8 seconds). Since this algorithm is very parallelizable, this leaves us needing 10^26th such computers or about one for every atom in my body, together with the ability to collect their results.
I suppose there's always some sliver of hope for a brute-force solution. We might get lucky and, in exploring only one of white's possible opening moves, both choose one with much-lower-than-average fanout and one in which white always wins or wins-or-draws.
We could also hope to shrink the definition of chess somewhat and persuade everyone that it's still morally the same game. Do we really need to require positions to repeat 3 times before a draw? Do we really need to make the running-away party demonstrate the ability to escape for 50 moves? Does anyone even understand what the heck is up with the en passant rule? ;) More seriously, do we really need to force a player to move (as opposed to either drawing or losing) when his or her only move to escape check or a stalemate is an en passant capture? Could we limit the choice of pieces to which a pawn may be promoted if the desired non-queen promotion does not lead to an immediate check or checkmate?
I'm also uncertain about how much allowing each computer hash-based access to a large database of late game states and their possibly outcomes (which might be relatively feasible on existing hardware and with existing endgame databases) could help in pruning the search earlier. Obviously you can't memoize the entire function without O(n) storage, but you could pick a large integer and memoize that many endgames enumerating backwards from each possible (or even not easily provably impossible, I suppose) end state.
我知道这有点麻烦，但我必须把 5 美分的钱放在这里。 对于计算机或人来说，有可能以胜利或僵局结束他/她/它参与的每一场国际象棋比赛。
然而，为了实现这一目标，您必须精确地知道每一个可能的动作和反应等等，一直到每一个可能的游戏结果，并将其可视化，或者采取一种简单的方法来分析这些信息，想想它就像一张不断分支的思维导图。
中心节点将是游戏的开始。 每个节点的每个分支都象征着一次移动，每个分支都与其兄弟移动不同。 在这个庄园里展示它需要大量资源，特别是如果你在纸上做的话。 在计算机上，这可能需要数百太字节的数据，因为您将有很多重复的移动，除非您使分支返回。
然而，记住这些数据即使不是不可能，也是令人难以置信的。 要让计算机识别出（最多）8 个即时可能的移动中的最佳移动，是可能的，但不太合理……因为该计算机需要能够处理该移动之后的所有分支，一路得出结论，计算所有导致胜利或僵局的结论，然后根据获胜结论的数量对失败的结论采取行动，这将需要能够处理太字节或更多数据的 RAM！ 以当今的技术，一台这样的计算机需要的不仅仅是世界上最富有的 5 位男性和/或女性的银行余额！
所以想了想，还是可以做到的，但是，没有人能做到。 这样的任务需要 30 位当今最聪明的人，不仅在国际象棋方面，而且在科学和计算机技术方面，而且这样的任务只能在（让我们完全从基本角度来看）......超级计算机……它不可能存在至少一个世纪。 将会完成！ 只是这辈子都没有。
I know this is a bit of a bump, but I have to put my 5 cents worth in here. It is possible for a computer, or a person for that matter, to end every single chess game that he/she/it participates in, in either a win or a stalemate.
To achieve this, however, you must know precisely every possible move and reaction and so forth, all the way through to each and every single possible game outcome, and to visualize this, or to make an easy way of analyising this information, think of it as a mind map that branches out constantly.
The center node would be the start of the game. Each branch out of each node would symbolize a move, each one different to its bretheren moves. Presenting it in this manor would take much resources, especially if you were doing this on paper. On a computer, this would take possibly hundreds of Terrabytes of data, as you would have very many repedative moves, unless you made the branches come back.
To memorize such data, however, would be implausable, if not impossible. To make a computer recognize the most optimal move to take out of the (at most) 8 instantly possible moves, would be possible, but not plausable... as that computer would need to be able to process all the branches past that move, all the way to a conclusion, count all conclusions that result in a win or a stalemate, then act on that number of wining conclusions against losing conclusions, and that would require RAM capable of processing data in the Terrabytes, or more! And with todays technology, a computer like that would require more than the bank balance of the 5 richest men and/or women in the world!
So after all that consideration, it could be done, however, no one person could do it. Such a task would require 30 of the brightest minds alive today, not only in chess, but in science and computer technology, and such a task could only be completed on a (lets put it entirely into basic perspective)... extremely ultimately hyper super-duper computer... which couldnt possibly exist for at least a century. It will be done! Just not in this lifetime.
从数学上讲，国际象棋已经通过 Minimax 算法 解决，该算法可以追溯到 1920 年代（由 Borel 或冯·诺依曼）。 因此，图灵机确实可以下完美的棋。
然而，国际象棋的计算复杂性使其实际上不可行。 当前的引擎使用了多项改进和启发式方法。 如今的顶级引擎在游戏强度方面已经超越了最优秀的人类，但由于它们使用的启发式算法，在给定无限时间的情况下它们可能无法完美运行（例如，哈希冲突可能会导致不正确的结果）。
我们目前拥有的最接近完美游戏的是残局桌库。 生成它们的典型技术称为逆行分析。 目前，最多六件的位置已全部解决。
Mathematically, chess has been solved by the Minimax algorithm, which goes back to the 1920s (either found by Borel or von Neumann). Thus, a turing machine can indeed play perfect chess.
However, the computational complexity of chess makes it practically infeasible. Current engines use several improvements and heuristics. Top engines today have surpassed the best humans in terms of playing strength, but because of the heuristics that they are using, they might not play perfect when given infinite time (e.g., hash collisions could lead to incorrect results).
The closest that we currently have in terms of perfect play are endgame tablebases. The typical technique to generate them is called retrograde analysis. Currently, all position with up to six pieces have been solved.
它可能是可以解决的，但有些事情困扰着我：
即使可以遍历整棵树，仍然无法预测对手的下一步行动。 我们必须始终根据对手的状态来制定下一步行动，并做出“最佳”行动。 然后，根据下一个状态我们再次执行。
因此，当对手以某种方式移动时，我们的最佳移动可能是最佳的。 对于对手的某些动作，我们的最后一步可能不是最佳的。
我就是不明白每一步怎么可能有“完美”的举动。
为此，[当前游戏中]的每个状态都必须在树中存在一条通向胜利的路径，无论对手的下一步行动如何（如井字棋），并且我有一个困难是时候考虑一下了。
It just might be solvable, but something bothers me:
Even if the entire tree could be traversed, there is still no way to predict the opponent's next move. We must always base our next move on the state of the opponent, and make the "best" move available. Then, based on the next state we do it again.
So, our optimal move might be optimal iff the opponent moves in a certain way. For some moves of the opponent our last move might have been sub-optimal.
I just fail to see how there could be a "perfect" move in every step.
For that to be the case, there must for every state [in the current game] be a path in the tree which leads to victory, regardless of the opponent's next move (as in tic-tac-toe), and I have a hard time figuring that.
是的，在数学中，国际象棋被归类为一种确定的游戏，这意味着它对于每个第一玩家都有一个完美的算法，即使对于无限的棋盘，这也被证明是正确的，所以有一天可能会很快有效的人工智能会找到完美的策略，然后游戏就结束了。
更多内容请参见本视频：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
Yes , in math , chess is classified as a determined game , that means it has a perfect algorithm for each first player , this is proven to be true even for infinate chess board , so one day probably a fast effective AI will find the perfect strategy, and the game is gone
More on this in this video : https://www.youtube.com/watch?v=PN-I6u-AxMg
There is also quantom chess , where there is no math proof that it is determined game http://store.steampowered.com/app/453870/Quantum_Chess/
and there you are detailed video about quantom chess https://chess24.com/en/read/news/quantum-chess
当然
棋盘上只有 10 的 50 次方可能的棋子组合。 考虑到这一点，要玩每一个组合，您需要进行 10 的 50 次方以下的动作（包括重复次数将该数字乘以 3）。 所以，国际象棋中的步法不到十的一百步。 只要选择那些能将死的东西就可以了
Of course
There's only 10 to the power of fifty possible combinations of pieces on the board. Having that in mind, to play to every compibation, you would need make under 10 to the power of fifty moves (including repetitions multiply that number by 3). So, there's less than ten to the power of one hundred moves in chess. Just pick those that lead to checkmate and you're good to go
64 位数学（=棋盘）和按位运算符（=下一个可能的移动）就是您所需要的。 就这么简单。 暴力破解通常会找到最好的方法。 当然，没有适用于所有职位的通用算法。 现实生活中计算也是有时间限制的，超时就会停止计算。 一个好的国际象棋程序意味着大量的代码（通过、双卒等）。 小代码不可能很强。 开局和残局数据库只是节省处理时间，某种预处理数据。 我的意思是设备 - 操作系统、线程、环境、硬件定义要求。 编程语言很重要。 不管怎样，开发过程很有趣。
64bit math (=chessboard) and bitwise operators (=next possible moves) is all You need. So simply. Brute Force will find the most best way usually. Of course, there is no universal algorithm for all positions. In real life the calculation is also limited in time, timeout will stop it. A good chess program means heavy code (passed,doubled pawns,etc). Small code can't be very strong. Opening and endgame databases just save processing time, some kind of preprocessed data. The device, I mean - the OS,threading poss.,environment,hardware define requirements. Programming language is important. Anyway, the development process is interesting.