What projects have been undertaken to solve chess completely?

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.

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.

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.

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.

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.

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.

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.

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.

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.

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