Solving Chess

[DustinYoder]

One key component to this is that every chess game starts from the same position and progresses from there. So perfect play would avoid a situaTion where black could force a draw. I would say a draw = losing.

I'm thinking that if you were to start evaluating moves from the end of a won game you could maybe work backwards trying to find a move where black could have forced a draw or loss. If you find one, you can safely say that whites previous move is no the perfect on so you try another.

I would probably start with a line of play from a game between the two current best chess computers and work backwards.

[hgm]

It sounds a bit like you have no understanding at all of the magnitude of the numbers involved. When you want to apply your "theory" to standard Chess, that is. On Tic-Tac-Toe it might work.

What you describe two posts ago is of course how virtually every Chess engine works. But from the openining position most of those have already difficulty searching beyond move 10 in a reasonable time... Furthermore, if there existed an evaluation that wouldpoint out winning moves, Chess would already have been solved, and there was no reason to search anything. Just play the winning moves...

[DustinYoder]

Now I'm not saying I have chess solved but I do think I know of how to build a database capable of storing the results and more importantly, actually looking them up. The current indexing method is just not possible to apply to full chess positions. At least I don't think so, is it?

[hgm]

Indeed, but as it is by far the most efficient method known, that is just the same as saying that it cannot be done yet (or in any foreseeable future). Which everyone is well aware of.

[zamar]

The current indexing method is just not possible to apply to full chess positions. At least I don't think so, is it?

It's already done up to 6 pieces and there are attempts for 7 pieces.

Getting to know the current technology is crucial before doing any reasonable research. Otherwise you (in one way or another) just end up reinvinting the wheel. I'd warmly suggest do some googling around with words like "chess", "tablebases", "nalimov", "gaviota", "EGTB".

Cheers,
Joona

[Sven]

I'm thinking that if you were to start evaluating moves from the end of a won game you could maybe work backwards trying to find a move where black could have forced a draw or loss. If you find one, you can safely say that whites previous move is no the perfect on so you try another.

The last sentence is not correct. Based on your assumption that the initial position were a forced win for white (which is the hypothesis you are trying to prove), when encountering a ">= draw for black" it is not necessarily the previous white move X at ply P that was non-optimal. That means, you cannot simply "try another move" for white. Instead you would have to find the perfect evaluation of all other previous white moves (better: as much as necessary for the proof) that are legal at ply P to determine whether the non-optimal move of white had indeed been X, or whether the position at ply P was already a forced draw and the non-optimal white move (still assuming there was any) occurred 2, 4, or even more plies earlier.

But would this be sufficient already? No, of course, since finding a winning move for white at ply P would not imply that black had played 100% optimal moves at previous plies P-1, P-3, ... So you would have to repeat your analysis for the position at P-1, and if that were already lost for black, go on with P-3, ... Now on that path you might encounter a black move that enforces a draw, so what you'll have to do is now the same as above: find out whether white played optimal or not.

The key point in all of the above is that you can reduce everything on one task: prove that in a given position there is a forced mate (for white, to stay in the context of your hypothesis), or that there isn't such a forced mate. Positions with black to move are treated the same since you have to prove that white wins after all legal black moves, where you can stop if one of the black moves does not lose.

If you are familiar with chess programming and/or chess algorithms you will have noticed that my description given above is essentially the description of minimax search, with the alpha-beta performance improvement mentioned in a side-note. As already mentioned in this thread, this is basically what almost all chess programs are doing, except for the fact that none of these programs is able today to perfectly calculate from the opening to anywhere near the leaf nodes of the game. The search tree to visit is simply too large for that.

Furthermore, as a given fact, no computer program known today is able to calculate the perfect answer to the question whether white has a forced mate even for arbitrary endgame positions. Use of state-of-the-art EGTB helps to solve some endgames with a few more than 6 pieces (and a decent search) but the overwhelming majoritiy of endgames is not perfectly solvable yet.

Now don't even start thinking about middlegames ...

What I described above can be extended up to the root node (the initial chess position), of course, since at some point you might arrive at the point where you ask "was the first black move (at ply P=1) optimal?". In theory. Not with existing hardware and software, though.

As an additional comment, you might have noticed that most chess grandmasters and computer chess experts do not share your hypothesis "white has a forced mate". Instead, most people assume that the initial position of standard chess is a forced draw.

In theory it could even be a loss for white (although there is a lot of evidence against it, just no proof) ...

I hope this might give you an idea about the complexity of the task you are challenging. Nevertheless I wish you good luck in your research, and I want to encourage you to report back any substantial progress you will make, provided it is something really new.

Sven

[FlavusSnow]

James, I find your idea about trimming down the moves very interesting as that is really the only part that I think I'm lacking in my theory.

I'm wondering if one could make the following assumptions about chess :

1. Every legal chess position where it is white's move would have only 1 best move or possibly 1 best plus a number of equally best moves which would still only require storing the 1 best move.

I don't think this is correct. Or at least it would take a very mature (read HUGE) game tree database to determine the one 'best' move, and even then probably only in endgames or nearly endgames. Arbitrarily pick a few complex middlegame positions and have Houdini, Stockfish, Komodo, Critter, and Rybka each perform a 1 minute search. My bet is that you'll get more than 1 answer from the 5 engines most of the time and it would take decades to ferret out the differences.

2. We could potentially find that move without evaluating all other possible moves if we used some 'intelligent' evaluation of the position to help our algorithm start with the most probable moves. We could stop looking through moves once we found one that is verified to be a winning move.

You could have the 5 engines (or any number of engines) search each candidate position deeply and then store only the positions that correspond to the search results. This would trim the positions stored down greatly, but at the end of the day you still end up with more of a large opening book that would have to assist an engine while playing - certainly not a solution tree. And one well-timed 'off' move by a strong human could easily bump the engine off of the database lines. Your database is only as good as the games that were input to it for analysis, so in the end I figure you would not want to store all of these 'off' lines unless it causes the engine that is assisted to lose the game.

3. A winning move is defined as a move which leads to a white win no matter how the opponent responds.

[wgarvin]

The state-space complexity of chess is something like 10^47. Assuming you took all of the atoms in the universe and used them to build a giant tablebase and a single computer for solving chess, it would still take at least 10^10 times as long as it took for Dr. Schaeffer to solve checkers (or maybe a lot longer?)

I think our sun is probably going to go nova before chess gets solved!

[Edit: actually Shannon's estimate for a complete tablebase for all of chess was 10^43. Its still ridiculous though compared to 8x8 checkers, which I guess would be something like 10^20.]