![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
The tone of the article seems to assume that humans outperform computers at the problem being described. Although this is disputable, I do not see a reason to mention this topic in this post: it is just describing a computational problem and the tone should be neutral.
In fact, the article tone seems to assume that humans are not correctly modelled as Turing machines which is a very BIG statement. — Preceding unsigned comment added by Garrapito (talk • contribs) 23:39, 6 March 2012 (UTC)
Here is one interesting blog post on topic, that might be good to mention in the article? http://rjlipton.wordpress.com/2010/05/12/can-we-solve-chess-one-day/ 333ES (talk) 01:38, 27 May 2010 (UTC)
"This article may be confusing or unclear to readers."... uh yeah. To the layperson like me, I didn't even know chess could be "solved". What on earth does "solved" mean? – Kerαunoςcopia◁galaxies 04:42, 31 August 2010 (UTC)
Is it possible to weakly solve any single chess opening? Is anybody trying to do this? --Mschribr (talk) 16:44, 24 November 2010 (UTC)
1.e4 e5 2.Nf3 Nc6 3.Bc4 Bc5 4.d3 d6 5.Nc3 Na5 6.Na4 Bb6 7.Bd5 c6 8.Nxb6 Qxb6 9.Bb3 Qc7 10.0-0 Nxb3 11.axb3 Bg4 12.d4 Ne7 13.Qd3 Bxf3 14.Qxf3 exd4 15.Rd1 0-0 16.Rxd4 f5 17.Bf4 fxe4 18.Qxe4 Nf5 19.Qe6+ Kh8 20.Re4 Qb6 21.c3 h6 22.b4 Rf6 23.Qd7 Kh7 24.Re8 Rxe8 25.Qxe8 a6 26.Re1 Qb5 27.Qe4 Kh8 28.h3 Rf8 29.b3 a5 30.bxa5 Qxa5 31.Qc2 Qd5 32.c4 Qd4 33.Qd2 Rf6 34.Be3 Qxd2 35.Bxd2 Nd4 36.Re3 Re6 37.Rd3 c5 38.Kf1 Kg8 39.b4 Nc6 40.bxc5 dxc5 41.Rd7 Re4 42.Rxb7 Rxc4 43.Ke2 Nb4 44.g3 h5 45.Be3 Rc2+ 46.Kd1 Ra2 47.Rd7 c4 48.Bd4 Nc6 49.Rxg7+ Kf8 50.Bc3 Rxf2 51.Rc7 Rf3 52.Bd2 Rxg3 53.Rxc6 Rxh3 54.Rc7 draw. This of course proves nothing at all. But it could be the start point for a discussion. Anyone find any major or definitive reason why the above couldn't possibly be an optimal game after move 4? Yes, I know the Sicilian is considered to be more of a challenge to 1.e4; I plan to investigate that next. 72.226.2.140 (talk) 01:11, 11 March 2012 (UTC)
The article seems to talk only about strongly solving chess, meaning to find the best move for every position. Is it possible to weakly solve chess? Finding the outcome only for the initial position and two players play perfectly. This should be easier. Will this be possible in 30 years? Should there be a section on weakly solving chess? Mschribr (talk) 21:10, 23 January 2011 (UTC)
Perfect play chess = solved, here is your proof. Part 1, game is win lose draw,another persons theorum part 2, (contradictory proof)A forced position must exist from move 1,such that at no point can a move be made that does not lead to the forced line with perfect play. If a position can be reached that always leads to a win, then that position would always be played. part 3, Move 1 cannot lead to a forced win,if the next move will always prevent a "score" increment.
the contradiction is simple, If you can reach a position that always wins, then an engine would always play those moves. It cannot therefore there must not exist a position that leads to a forced win. This takes the proof all the way to the first move, since nothing can go before the first move, to prevent the forced win, etc. — Preceding unsigned comment added by 106.69.176.130 (talk) 04:33, 13 October 2015 (UTC)
I'm feeling a bit optimistic today about the possibility of the initial chess position being solved soon. Consider that there is some perfect game of chess out there where, say, White is able to win. Somewhere during this perfect game, White will likely go up in material, most likely a pawn at first. This might not occur until move 20 or so. But then White will likely start making faster and faster progress as White is ahead in material. By move 35, White could be up a minor piece, then by move 50, it might be a whole rook. Checkmate by move 65. How many years will it be before a computer finds that first pawn? The minor piece, etc? Does such an avalanche effect put solving the initial position a very real possibility in the next 25 years, say? Synesthetic (talk) 00:40, 15 April 2011 (UTC)
Rubbish. Anonywiki (talk) 06:48, 19 April 2011 (UTC)
If this were the method by which the perfect game of chess were to be found, computers would have solved it long ago. Trying to win in terms of material was an early (and contemporary?) drawback for computers. On another note, why do we have such strong reverence for positive feedback loops these days? 98.122.138.236 (talk) 00:54, 6 May 2011 (UTC)
I put the starting position into Houdini with Black's pieces (not pawns) removed and Houdini found a mate in 16. Houdini is still looking for a faster mate. Have there been any estimates on the length of a perfect chess game? Houdini also found a checkmate if Black only has a Queen. It may be possible to estimate how many more moves Black is able to survive as each defender is added. The position above where Black only has pawns is only 7 pieces from the starting position. I wonder how close in material we can get to solving the starting position. Perhaps there is a way to estimate the length of a perfect chess game from these kinds of data points. Update: If Black is only given the Queen and Queen's bishop, White mates in at most 22 moves - found by Houdini in 5.5 hours. Synesthetic (talk) 15:06, 17 April 2011 (UTC)
I question the repeated assertion in this article that the first-move advantage in chess is, or ever will be, possible to determine via computational analysis. This is certainly an intractable problem, as generalized chess is an EXPTIME-complete game: it cannot be solved in polynomial time by a deterministic Turing machine. Given the search space required in a game of chess, a weak solution of chess is intractable. Even if quantum computing ends up providing fast computation for a new class of problems, there is no way to apply it to the hardest problems in EXPTIME.
Where the article implies that "experts disagree", it uses the opinion of a chess player as an "expert" because he plays chess well. A chess player is not an expert in computational analysis. His point of view on what is possible with computers is irrelevant. If you can find a single mathematician or computer scientist who has published something indicating there will ever be a tractable solution to chess, feel free to provide it.
Also, the link to Jaheruddin, S.S.J. is not a reliable resource. It's a paragraph of text that some fellow with a Bachelor's degree put in a pdf and uploaded to the Internet. Progress is irrelevant in the face of theoretical fact of fundamental laws (spacetime speed barrier, conservation of energy, conservation of information).
I've copied this general comment to the discussion board in the first-move advantage in chess page (of which this page is mostly a copy). TricksterWolf (talk) 20:26, 21 August 2011 (UTC)
There seem to be two approaches to solving chess: (1) work from the endgame backwards (as tablebases do); (2) work from the opening forwards, ie bottom-up and top-down respectively. Now the article suggests that any complete analysis of chess would more easily come from extending tablebases towards the required 32 pieces. And yet most of the sources in this article seem to be arguing that solving chess is practically impossible because the number of games is too great, and that includes the seminal Claude Shannon paper, but this assumes that the computers are using a top-down approach. This is of course how both computers and humans play chess, but playing chess and solving it are quite different things. If we work backwards from the endgame then we only need to consider the total number of positions, which is tens of orders of magnitude smaller than the number of games, and makes the solving of chess, while still remote, at least theoretically conceivable. Doesn't this make the arguments presented rather moot? — Preceding unsigned comment added by 131.111.185.74 (talk) 15:57, 17 February 2012 (UTC)
How difficult is to solve chess by brute-force? Let’s do some calculations: Chess game tree complexity = 10^123 (source: Wikipedia) Bremermann's Limit = 1.36 × 10^50 bits per second per kilogram (source: Wikipedia) Mass of the Universe = 10^53 kg (source: http://people.cs.umass.edu/~immerman/stanford/universe.html) Age of the universe = 4.354× 10^17 seconds (source: Wikipedia) No. of chess games analyzed by the universe turned into the best computer possible < 10^121 — Preceding unsigned comment added by 83.16.208.50 (talk) 11:38, 7 June 2013 (UTC)
A practical way to do a brute-force chess solving analysis could be to consider only one best possible opponent's response to each possible legal move. Then from the starting position for each of the 20 White's moves and one corresponding Black's best move we will have only 20 games to consider, not the all 20 * 20 = 400. — Preceding unsigned comment added by Al wier (talk • contribs) 13:52, 30 April 2024 (UTC)
I think quantum computing should be in a bit more, or at least kept in check as a topic as it evolves (or just checked on...or some other kind of chess pun that actually yields clarity to what I'm trying to say here) Squish7 (talk) 00:53, 26 March 2014 (UTC)
How long would it take to verify a perfect game? There are many problems where it is much faster to verify a solution than to find one.
Have people tried to use a genetic algorithm to evolve chess games to a perfect game? Genetic algorithms have been used to search search spaces of astronomical size relatively quickly.
The article mentions speculation about it being impossible to solve chess. This is not too clear because of the clause "(as of 1950) technology" - computing has improved *exponentially* since then, and so I think it should be clarified just how he came to the conclusion. — Preceding unsigned comment added by 131.156.137.142 (talk) 00:44, 25 January 2017 (UTC)
The article implies, even though not told explicitly, that there are " 10120 possible game variations". I have seen a site that says the number is far more greater than that: http://wismuth.com/chess/longest-game.html which one is more accurate? How can we clarify? The site states:
so, this article says there are at least 10 28241 variations. or am I misunderstanding something? — Preceding unsigned comment added by Sir artur (talk • contribs) 05:56, 7 February 2017 (UTC)
Can a person beat a program if the person has no time controls and can use other programs and can take back as many moves as they want? I came here hoping to find answer — Preceding unsigned comment added by 47.72.78.79 (talk) 07:11, 22 October 2017 (UTC)
>>> I am not sure why you would reference Jonathan Rowson at all in this article. He is a Chess Grandmaster, this is true, but there are almost 1500 Grandmasters worldwide. Rowson seems to have zero background in computers/chess engines, and his commentary is akin to a football announcer commenting on a game (i.e. it's semi-informed opinion, mostly for entertainment value). A much better source would be a chess engine developer/team member that is also a titled chess player, ala Hans Berliner or Joel Benjamin. <<< — Preceding unsigned comment added by 98.210.5.17 (talk) 21:59, 6 February 2018 (UTC)
The page talks about solving more complex chess variants, but not simpler. This should probably be included. The page on Minichess mentions a bit about solving such variants, and there has certainly been other work done on the topic as well. DinoD123 (talk) 17:35, 11 September 2018 (UTC)
There is a program that plays perfect checkers, chinook. We might surmise, even in the absence of an external proof, that some program, should it compile an unbroken string of wins/draws over a considerable length of time (maybe years?) against very skillful opposition human or machine, would be considered to play "perfectly". It would be possible that the opposition has simply topped out, and technological advances like that represented by AlphaZero in chess will puncture the aura of perfection. But we do know the program plays checkers perfectly; it will never be defeated. It does that without generating the entire game tree or building a state space dictionary as posited by Shannon. It solves the game algorithmically. We are familiar with an elementary algorithmic solution of tic-tac-toe: the game tree is 9!=~360K terminal positions not taking into account rotations and reflections, and the state space is 3^9=~20,000 board configurations. Yet three rules of thumb (an algorithm by any other name) enable even rank beginners to play the game perfectly. The "rules" are a nested set of if-then-else propositions which are easily transliterated into an automaton.
Our best chance at solving chess in the strong sense is such an algorithm, or automaton. Since chess automatons are rated, it's reasonable to inquire what the rating of a perfect automaton would be, and how soon we might get there. It certainly is a valid approach. Stockfish is now rated about 3550. It has been increasing in rating by about 30 points per year for a decade, and shows no sign of slowing down any time soon, so it may be premature to speculate about a rating ceiling. The program certainly isn't perfect, and continues to suffer defeats. As a statistical artifact, no program in the ELO rating system used may be rated more than 400 points higher than the second highest program in the rating pool, so as a mathematical matter, "god" could be rated no higher than 3950 as the rating pool exists today, and extrapolating (dubiously), it would take Stockfish 13+ years to attain that. There are some additional difficulties to algorithmic solution: we already know that there is an endgame tablebase position requiring 545 forced perfect moves to win. The indicated moves are not comprehensible in any human way, so they cannot be translated into an algorithm. In a more everyday way, the tablebase's handling of king+queen vs king+rook also involves incomprehensible defensive moves which make it almost impossible to defeat the machine in that ending. It is likely that such lengthy incomprehensible sequences of moves exist in many positions throughout the game, including the opening, in order to secure or retain some possibly winning advantage. So any algorithmic solution of chess would necessarily require a comprehensive full-game tablebase of such positions.
I think some codification of the above consideration/argument ought to be included in the text of the article. And where would we get a citation for that? The entire field of chess research has been dry for about 15 years. Sbalfour (talk) 18:02, 26 July 2021 (UTC)
Five chess variants: infinite chess, Capablanca chess, Gardner mini-chess, Maharajah, and Loser's chess are mentioned in the article. There are at least a handful of others that are solved or solveable, some more chess-like than the ones enumerated here. That the subject matter of the article explicitly includes chess-like games is dubiously expansive. The 3M bookshelf game Ploy is described as a chess-like game. Does it belong here? If the definition of chess-like is taken from the lead as "combinatorial games of perfect information", this article can/will collect games that are at best incidental to the primary subject matter which is solving chess itself. That we have made vanishingly little progress in this area for 65 years is a temptation to collect tidbits. The tablebases have a clear future, but we've had a collection of solved endgames since ancient times. Solving Gardner mini-chess at least weakly is a significant breakthru, but by so doing, we're probably finished with 5x5 and smaller variants.
If we include chess-like in the subject matter, we ought to define that in a way that is most likely to result in additions that advance the topic. I think at a minimum, chess-like ought to mean that the object of the game is to checkmate the opponent's king, and the movement and capture rules of the pieces are those of the chess pieces (In some variants, we may need modest modifications due to geometric constraints.) Maharajah and Losers chess fail both constraints. A third useful constraint, since we are especially interested in the fine line between a game-theoretic value of draw and win, is that the forces should be generally balanced, so that the game is "fair" (see Mallett chess where the forces are different but ostensibly equal). Maharajah chess also fails this constraint, but we may not want to exclude chess games at plausible odds.
There are dozens of chess variants that could be included by name. For a variant, the thrust here is twofold: what did we learn, and where do we go from here? In the cases of Maharajah and Losers chess, I can't answer those questions. For Maharajah chess, the only thing I can think of is to decompose the Maharajah into a rook, bishop, knight, and pawn, add a king, and place them on the kingside in the starting positions of the chess pieces. The game is still a sacrificial slaughter, and I can't see how it would contribute to solving chess if solved (and it probably could be solved).
Useful variants would be ones on 5x6 or 6x6 boards like Los Alamos chess and its cousin with bishops instead of knights. There's advanced research in this area, but nothing published yet that I know of. Sbalfour (talk) 20:17, 26 July 2021 (UTC)
A rather large chunk of text from Shannon's seminal paper on computer chess has been copied into a footnote. My gut feeling is that if the info is important enough, it ought to be copied (with inline attribution) into the article text. If it is more like incidental or supplemental info, then it ought to be left in the paper (possibly with a page number or other locator), rather than copied into a footnote. The volume of text might exceed fair use, so I'm dubious about it anyway. Sbalfour (talk) 20:07, 4 August 2021 (UTC)
I've elided the calculation of how many years it might take to solve chess; that seems superfluous, and anyone interested can read the paper. The rest of the footnote probably bought to be moved into the text proper. Sbalfour (talk) 14:40, 6 August 2021 (UTC)
Shannon's argument for the game-theoretic value of the "pass" variant has a corollary: assume the addition of "pass" changed the game-theoretic value of chess. Then, since the proof yielded a game-theoretic value of win or draw for white in the variant, the addition of "pass" could only have changed the game-theoretic value of chess from a loss for white to a win/draw for white. Since every move is otherwise losing for white, his first move must be "pass". But now black faces the same situation due to the mirror image symmetry of the board: every other move must be losing. That's a contradiction: chess cannot be losing for both sides. Therefore the assumption that the addition of "pass" changes the game-theoretic value of chess is incorrect. Therefore the addition of "pass" does not change the game-theoretic value of chess, and the game-theoretic value of chess itself is the same as the game theoretic value of the variant, which is that chess is a win or draw for white. Yo?!... Sbalfour (talk) 15:12, 6 August 2021 (UTC)
A translation of the proof from 1997 is available here (pg 12 - 15) as well as some information on his arguments, and some updates from more recent work in game theory.
From my reading it would appear it would appear that the article overstates his claims about the solvability of chess He specifically concludes that his argument only applies to endgames or problems not to the entire game.
The special theory of the game would have, as far as possible, to determine these numbers or at least include them within certain boundaries, which hitherto has only been possible for special cases such as the ‘problems’ or the real ‘endgames’. The question as to whether the starting position p0 is already a ‘winning position’ for one of the parties is still open. Would it be answered exactly, Chess would of course lose the character of a game at all.
ConlanO (talk) 20:29, 3 March 2023 (UTC)