17

Chess is not completely solved yet but what efforts have been undertaken to solve it? Has there been a large project like the HGP or is something like that even worth pursuing? What failed efforts have been there if any? I am speculating that the the Alpha Zero project must have taken some steps towards that end.

EDIT:-Answers ponder on the point that is extremely difficult to solve chess which i have clearly indicated in the first line in the question. What I would like to know that are there or have there been any projects that try to solve chess. Like that Moscow university 7-piece tablebases and any efforts like that. It is clearly an expensive problem to solve but who is doing it and what approaches are being taken? It is often said that there are more chess combinations than atoms in the universe (probably because of that ad) but so are the real numbers but we have a rich theory about that. We also know a great deal about the universe as well but we had to try hard to get to that point. Is chess being treated the same is my question.

  • 5
    How about projects to show that it is pragmatically unsolvable? Showing PSPACE-completeness for example. This result suggests we should not expect to find a short enough solution to be computed in this universe. – usul Jul 8 at 22:42
  • 3
    This post estimates there about 10^44 possible chess positions. Which is ~ 2^146, thus, theoretically, 146 bits are needed to store one chess position. You need 12 atoms to store a bit (at -272 °C). Thus you need 146*12*10^44 = 1.75*10^48 atoms to store all the positions. Earth has 1.33*10^50 atoms, so it is at least theoretically possible to build a memory large enough to store all the chess positions if we use 1.31 % of Earth's atoms on this endeavor. – lvella Jul 9 at 14:12
  • 6
    @Ivella The argument about storing the positions is fallacious to say the least. Solving a game does not mean having to store each possible position: it means finding out whether or not there exist at least one solution where one side does not lose by force - you could just as well loop through all possible positions without storing anything until you find one. That this will take a vaste amount of time we all agree, but it is a different problem than the one you mention. – gented Jul 10 at 7:59
  • 1
    "What projects have been undertaken to solve chess completely?" -- None, for the simple reason that anyone with the technical skills to undertake the project would have the technical skills to realize that the project is likely infeasible. – John Coleman Jul 10 at 19:34
  • 2
    @gented: I might be willing to accept that, except that to the best of my knowledge, nobody has presented a provably-correct algorithm for solving Chess or Chess-like games which does not involve searching a large subset of the game tree. So I find this line of reasoning rather suspicious. Sure, it's possible that we've missed some extremely cheap algorithm despite decades of effort by many experts in the field - but I'm skeptical. – Kevin Jul 10 at 21:30

10 Answers 10

43

Endgame tablebases can be seen as such an effort, in that we started at few pieces and have increased the number. In 2012, 7 piece tablebases -from Moscow state university were generated, so chess is solved for positions of 7 or fewer pieces (including the kings).

The problem is, the 7 piece tablebases take about 140 TB in storage. 8 piece tablebases would take about 10 petabyte of storage, and a computer with 50 TB of ram (source) to keep hashes in memory to generate them in reasonable time (a few years?). I guess it would be doable these days if someone makes the millions of dollars available. 9 seems way out of reach.

So it will take a while before we get to 32.

| improve this answer | |
  • 5
    Of course these are efforts to strongly solve chess, meaning that the winning strategy is known for every possible combination of pieces and locations on the board. Theoretically it should be significantly easier to weakly solve chess, meaning that the winning strategy is found only for the single starting position. – Brady Gilg Jul 8 at 19:47
  • 9
    @chaslyfromUK In game theory, "strategy" refers to a set of rules of how one responds to other players' actions. A winning strategy would not have to be adjusted according the opponent's moves; deciding what to do based on their moves is what "strategy" means. In the context of a computer, a winning strategy would be a computer program that is guaranteed to not lose. – Acccumulation Jul 8 at 21:56
  • 2
    @chaslyfromUK I don't know what you mean, a strategy takes into account the possible moves your opponent can make. – Brady Gilg Jul 8 at 21:56
  • 3
    @DanDascalescu Similar to how IBM gained great publicity for programming computers to beat the best humans at chess and Jeopardy!, fully solving chess would be worldwide news. It would give the responsible institution a big boost in reputation and customer interest for their likely ability to apply computing power and search algorithms to other hugely difficult, but more practical and profitable, problems. – nanoman Jul 9 at 9:00
  • 3
    @chaslyfromUK In that case we have weakly solved chess in finding that, with perfect play, the starting position will always lead to a draw. – Omegastick Jul 9 at 10:37
19

7-piece endgame tablebases were completed in 2012. 8-piece endgame tablebases is the next logical step. This page says a little about how those are going (context is searching for the longest forced mate in pawnless positions):

Many show interest in what is to expect from [8-piece] endings ... Unfortunately the size of [8-piece tablebases] will be 100 times larger than size of [7-piece] tablebases. To fully compute them, one will need about 10 PB (10000 TB) of disk space and 50 TB of RAM. Only top 10 supercomputers can solve [8-piece] problem in 2014. So don't hold your breath expecting new breakthroughs too soon - the first 1000-move mate is unlikely to be found until 2020 when a part of a TOP100 supercomputer may be allowed to be used for solving this task.

If we get 8-piece tablebases one day (if we get them) that'll be the next step to solving chess, but we don't expect to get them for many years more at least. Even if they are created, they'll take huge amounts of disk space to store.

In principle chess will be solved when we have 32-piece tablebases, but if 8-piece tablebases are this hard to create, we are not going to solve chess in the foreseeable future, AlphaZero or not.

| improve this answer | |
  • 5
    In 2020 you can rent 10PB of disk and 50TB of RAM (and a few tens of thousands of CPU cores into the bargain) for maybe 5 million dollars per year. – hobbs Jul 9 at 1:28
  • @hobbs Right, but I guess the people who are willing to spend 5 million dollars per year have better applications for it, like COVID-19-related protein folding. – user253751 Jul 11 at 14:04
15

AlphaZero has no intention of solving chess. It's just an engine that plays spectacularly well. The number of positions you'd have to evaluate in order to solve chess is larger than the number of atoms in the universe, so even if you could solve chess (which is nowhere near the capabilities of the current capability of all computers on Earth combined), you wouldn't be able to store the entire solution anywhere

| improve this answer | |
  • 12
    Well, you're assuming that you'd have to store every position. You could certainly discard the "worst" moves without storing them, or encode a "short" algorithm that works from a number of similar positions, avoiding the need to store them directly. Also, you can make the case that any chess-playing AI is a storage of the solution to every position it is able to win from, regardless of whether it had any a-priori knowledge of that position or not. – jpaugh Jul 8 at 15:24
  • 3
    As I mentioned elsewhere, results like PSAPCE completeness of generalized chess suggests we should not expect to be able to compress a solution into sub-galactic size, even implicitly like in the guts of an engine. This contrasts with NP-complete problems whose solutions may be hard to find, but are small. – usul Jul 8 at 22:47
  • 2
    @David Nim with initial heaps of sizes {1,2,...,100} has a larger space of valid positions than chess, but it's solved. The solution consists of an algorithm that computes a move given a position, and a proof that the move it computes is always optimal. Chess is probably harder than Nim but the size of the position space by itself doesn't tell you much. – benrg Jul 9 at 0:55
  • 2
    @benrg sure, the argument about storage space implicitly assumes that you have to store a significant fraction of positions. However, no algorithm has been found for chess, and given the numerous attempts at finding one, it's likely that an implementable one exists. The chess computer community certainly has given up on finding one, anyway. – toolforger Jul 9 at 6:25
  • 2
    You can store it in a black hole:) – postoronnim Jul 10 at 15:16
6

Can't answer your main question, but to the point about alphazero: from my perspective, AlphaZero, although it may be a major step in superhuman performance in games, is not even a minor step towards solving chess.

if we could follow A0 with big investment maybe it can take us very far into uncharted territories

I don't think this is true. Its approach, which is to explore the game-tree by picking paths which have high probability of being good, doesn't seem to have much implication to fully solve chess. Although it may be very very good at being very very good at chess, I think this heuristic-based approach is less viable to exactly solving chess than you think.

To be very charitable, maybe... and by maybe I mean this is a pie-in-the-sky thought that just came from my dumb brain... maybe the AlphaZero work could someday lead to a proof that with training, the model converges to a model that plays correctly with probability 1 (and 1 in this case is aka 99.999...%), but even this may not be considered "solving" chess as we still cannot not prove that any model we have trained in real life makes every move correctly.

| improve this answer | |
  • ".... Its approach, which is to explore the game-tree by picking paths which have high probability of being good" what is wrong with this approach? – shashank shekhar singh Jul 9 at 4:39
  • 1
    @shashankshekharsingh I just don't see how it is related to the prospect of fully solving chess. As I said, there's nothing "wrong" with it -- it's very very good at playing games better than anything we've seen before, but I don't see the connection to the goal at hand. – Kevin Wang Jul 9 at 5:57
  • well lets say there are 10^40 sensible positions , a0 can at least bring that number further down without needing those humongous amounts of storage since it is the best at chess. and then maybe some other approach can be applied. – shashank shekhar singh Jul 9 at 10:00
  • Is a0 even being used to solve chess , say the 8 piece table-bases ? – shashank shekhar singh Jul 9 at 10:08
  • "Is a0 even being used to solve chess , say the 8 piece table-bases?" That's a good question. I don't know the answer to that. – Kevin Wang Jul 9 at 18:56
6

It is funny that you bring up mathematics and the universe as things we know quite a bit about. Yet neither of these fields is 'solved'. Moreover, neither ever can be.

Mathematics can never be fully solved due to Goedel's Incompleteness Theorems. There will always be true facts about numbers that we cannot find proofs of.

As with the Universe, we can never know the full 'state' of the universe (eg what every atom and subatomic particle is doing) precisely due to theHeisenberg's Uncertainty Principle. We can never hope to tell what is going on outside the observable universe due to relativity.

So in some sense, they are pretty fair comparisons to chess. We know a lot, but due to universe we live in, we will never know it all.

The best I believe we can hope for in terms of solving chess would be an ultra-weak solution (possibly involving some strategy stealing) that proves a eg a forced draw (or better) for white from the starting position without explicitly solving how.

For an interesting article about endgame table-bases and methods for solving games, check out this. Checkers (a MUCH simpler game) was solved to be a draw over a decade ago

EDIT To clear up some confusion:

As pointed out in the comments, the unsolvability of these three systems are immensely and qualitatively different. The incompleteness theorems derive from first principles and would hold up in ANY universe. The unsolvability of the state of the universe is based on the physical laws of the one we live in. The unsolvability of chess is only due to the fact that the universe we happen to live in is too small and chess is too large for a (strong) solution to be held inside it. The reason they are similar here are pure coincidence, simply a by-product of universe we all happen to inhabit.

| improve this answer | |
  • 9
    Chess is solvable. Peano arithmetic, in the sense of being able to find a proof of every true statement, is not. Your first three paragraphs are nonsense, from a mathematical point of view. – Carl-Fredrik Nyberg Brodda Jul 8 at 17:47
  • 10
    @DongKy still, your answer is mixing up the reasons why chess is unsolvable. Mathematics is unsolvable by first principles, the universe is unsolvable due to immutable limits imposed by laws of nature, but in the case of chess, neither reason applies, it's merely the size of the state space that prevents us from exhausting it. That makes chess actually more interesting, because the size of chess' state space prevents a full solution so we explore more of the space of approximations and incomplete solutions, neither of which is relevant to math or universe. – toolforger Jul 9 at 6:29
  • 1
    Regarding your paragraph about physics: Heisenbergs relation doesn't forbid us to theoretically know the quantum state of the entire universe, it only forbids us to know the values of certain observables simultaneously. This is only really an issue if one is obsessed with the Newtonian definition of "state of a system". Our lack of understanding of the universe does not stem from us not knowing the impulse and position of every particle at the same time, but from our little understanding of the governing physical laws. – TheoreticalMinimum Jul 9 at 15:22
  • 7
    This answer is total nonsense. There are games that are solved. If you're arguing that chess can't be solved, then you have to explain how it's different from games that can be. General considerations like Godel and Heisenberg can't tell us this. – Ben Crowell Jul 9 at 18:51
  • 2
    Losing chess are solved, under a reasonable definition of the term, so I am not sure that these "state space" arguments hold water. – Federico Poloni Jul 10 at 16:05
5

Others have already mentioned tablebases and their development, but something that hasn't been touched on yet is the sheer space complexity of chess.

In order to say that chess is solved, we need a function gameState -> move, and that function needs to be defined for all possible states of the game, or at least all of the ones that are reachable within the rules of the game. There are vastly more of these than there are atoms in the observable universe. So even if we could somehow encode each game state and its corresponding best move into a single atom, there isn't enough matter in the universe to build the server that would run the database.

Endgame tablebases are interesting, but there's nobody who's seriously attempting to solve chess.

| improve this answer | |
  • 8
    Who said that in order for a function to be defined, all possible inputs and their outputs need to be stored in a database? By this argument, the function f(x, y) = x + y cannot be defined, even for natural numbers, because there are more natural numbers than there are atoms in the universe. – LarsH Jul 9 at 1:49
  • @LarsH that's just what solving means in this context. If you're saying it can be a function that we compute on the fly... then we're right back to game tree search. – MattPutnam Jul 9 at 3:03
  • @MattPutnam "....but there's nobody who's seriously attempting to solve chess." well that is the actual answer I guess. :) – shashank shekhar singh Jul 9 at 4:28
  • 6
    A mathematical proof of whether the starting position is a win, or a forced draw, would be one kind of "solution" of chess without necessarily requiring a brute-force exhaustive tablebase. – nanoman Jul 9 at 9:06
  • @nanoman yes exactly. i am more interested in that kind of solution rather than engine based brute force attempts. Chess theory has to be developed. – shashank shekhar singh Jul 9 at 10:32
2

Shirish Chinchalkar has a paper which calculates an upper bound of ~10^46 for the number of positions in chess (different from moves obviously). Arguments which talk about the number of atoms in the universe are very facetious on account of using position differences (we can only get to a position from another, so why not just store what piece moved instead of the whole new position?) as well as compression. IIRC, in the Syzygy endgame tables, each position can be represented by less than a single bit after taking into consideration compression.

One thing that I personally wonder, and I could be completely wrong, is whether there would be at a certain point a relative small decrease in complexity as n -> 32 as there will be less starting nodes.

It's an amazing question though. I would love to see it (even weakly) solved in my lifetime.

| improve this answer | |
  • A quick calculation shows 3x10^23 possible positions, of which some number are unreachable. There are 13 possible states for each square - 6 pieces on each side - pawn, rook, knight, bishop, queen, king plus 1 empty space. There are 64 squares - so 64^13 possible positions. This seems much more reasonable than 10^46, though still a very large number. the fact that the game-tree has 10^120 moves (shannon number) is irrelevant. you only need to keep 'the one winning move' for each of these 10^23 states. – Jim Jul 10 at 14:53
  • the unreachable states would take into account that there are only ever 2 kings on a board with 2048 total positions of them, instead of up to 64 kings. it would also limit to a maximum of 8 pawns each (again down from 64), and have a maximum bounds on the other pieces due to promotion - say, 4 queens, 6 rooks, 6 bishops, and 6 knights. my math is too rusty to calculate this, but i expect orders of magnitudes of possible positions can be discarded. – Jim Jul 10 at 15:19
  • one final note on unreachable states - there has to be a minimum of 32 empty spaces, up to 61. so, again, anything outside this range can be excluded. – Jim Jul 10 at 15:54
  • Hi Jim, it's actually 13^64 (~10^71) according to your reasoning. So using the different pieces of information you've given you could look to reduce it. However, positions also take account of whether castling is possible for either side and if there are any en-passant squares. See here for position vs diagram: wismuth.com/chess/statistics-positions.html – Colin McDonagh Jul 10 at 16:40
  • 1
    @Jim I'm currently trying to publish a small paper on pawn positions. I'll post it here if it ever gets published! – Colin McDonagh Jul 14 at 15:23
2

Another line of attack is reducing dimension: Gardner's 5x5 minichess has been weakly solved by Mehdi Mhalla and Frederic Prost in 2013. 3x3 and 3x4 boards have been strongly solved in the 2000s with complete tablebases for each position by Kirill Kryukov, and 9-men tablebases for 4x4 chess have been completed in 2011 by the same author.

| improve this answer | |
1

I think the other answers and comment have made it clear that this is a really complex problem. So complex, that no classic computer will ever come close to solving it.

But I have asked myself the same question. Isn't chess a perfect example to use a quantum computer? Although quantum computers are not yet fully ready for use there do exist "programming languages", and there are already many algorithms for a quantum computer described this way. There actually even exist simulators for running these quantum computer "programs" on classic computers.

I wonder how feasible it would be to write an algorithm for solving chess on a quantum computer. Or would that require so many qbits, that we can never expect an actual quantum computer that could run this algorithm? But if it would once exist, shouldn't it be able to answer the question within a second?

Just to clarify, since I mentioned the possibility to simulate these algorithms on classic computers. This simulation of course only makes this very complex problem solved even less performant, so those simulators could only be used for testing of the algorithm, not for really using it.

| improve this answer | |
  • there are no actual quantum computers as of now hence those algorithms don't mean much as you still don't get the time advantage of quantum computers. so we have to wait for that – shashank shekhar singh Jul 11 at 4:11
-2

I think everyone here has a good and necessary point with the space complexity of chess being larger than the number of atoms in the observable universe. However, I think I can add some additional points onto that.

  1. As others have pointed out, the definition of "solved" is not super clear. If "solved" means "find the optimal move from any possible game state", solving chess is impossible. However, if we take solved to mean that we just want to play the single "perfect" game of chess we may be able to reduce space complexity.

  2. The problem with point one is that chess does not have a single perfect game. A perfect game of chess implies that you are always making the move that leaves you with the highest chance of winning. It also implies that you are accounting for your opponent making optimal moves, as otherwise it would not be a perfect game (and would also break the previous space complexity issues). However, chess is a well balanced game and any game perfectly played would necessarily end in a draw.

  3. There are likely a near-infinite number of optimally played games that end in a draw. While the number of optimal moves from any position is much smaller than the number of possible moves, according to the best chess engines we have today there are many moves that have near-optimal results from the starting position and in the first few moves. Because a significant advantage is needed to win any game of chess, many of these moves would likely be included in a "perfect" or solved game.

  4. Lastly, how would you prove my points 2 and 3 right or wrong? You can't. Again, you run into the space complexity issue. To prove any position is either winnable or unwinnable if both players play optimally, you need to diagram out every single possible move from a given position. As we have shown earlier, this is impossible until we are below a certain piece number.

| improve this answer | |
  • 1
    I'm not sure you understand what "solving" a game means. Once you "solve" a game you have a strategy by which you always win (as with checkers, which has been solved), or for some games, always tie (as in tic-tac-toe). It isn't just playing "a single perfect game" – Kevin Wells Jul 9 at 21:13
  • "There are likely a near-infinite number of optimally played games that end in a draw.": It is believed that an optimally played chess game is a draw. proving it would be a huge step toward solving chess. – Bit Chaser Jul 11 at 1:33
  • @KevinWells That definition of "solving" is not available to chess, so it makes the conversation much less interesting. (You can't force a win from every possible game position, and it isn't clear that you could force a win from the starting position, either.) – jpaugh Jul 14 at 22:27
  • @jpaugh What other definition of "solving" are you using then? The whole point of this question is if we are able to move towards that goal, and if so what efforts are being made to do so. The real answer is that solving chess is certainly out of reach currently, and may never be in reach, but there are still efforts to be made to improve our knowledge of solving increasingly complex starting positions – Kevin Wells Jul 15 at 14:27
  • @KevinWells How about, being able to know the outcome of any game, given the starting position, and two opponents who play perfectly? Solving chess is not about winning an individual game, but predicting the outcome of every game well enough to give yourself the best chance of winning. – jpaugh Jul 15 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.