Can chess be analytically "solved" in the forseeable future?

[Brian-E]

Originally Posted by science_man_88

one thing popped up in my mind today:

can progressive chess be solved even if normal chess can't ? , the reason I ask is because if it can we have a backward way to solve normal chess I think. I think this because normal chess is basically progressive chess with only one non reversed move/capture per player's turn.

My guessed answer to your question is: yes, I think progressive chess probably can be solved to a clear win for either White or Black (I think it's extremely unlikely that this game is a theoretical draw with best play) if someone chooses to spend the effort and considerable computing time on the question. But I don't think it can be done by retrograde analysis if that is what you are talking about. Simply brute force analysis of the continuations from the starting position should yield results because games reach a checkmate within a few turns of each side. This shortness of games, to my mind, is the key difference between progressive chess and normal chess when it comes to the ability to "solve" them.

[science_man_88]

Originally Posted by Brian-E

My guessed answer to your question is: yes, I think progressive chess probably can be solved to a clear win for either White or Black (I think it's extremely unlikely that this game is a theoretical draw with best play) if someone chooses to spend the effort and considerable computing time on the question. But I don't think it can be done by retrograde analysis if that is what you are talking about. Simply brute force analysis of the continuations from the starting position should yield results because games reach a checkmate within a few turns of each side. This shortness of games, to my mind, is the key difference between progressive chess and normal chess when it comes to the ability to "solve" them.

if you reverse moves done by knights etc. as long as you don't capture with any of these moves and do only up to one non reversible move per set of moves this game becomes normal chess basically ( okay so the 2 moves black gets on it's first move doesn't quite allow you to reverse all reversible and not look like you haven't moved).

[Brian-E]

Originally Posted by science_man_88

if you reverse moves done by knights etc. as long as you don't capture with any of these moves and do only up to one non reversible move per set of moves this game becomes normal chess basically ( okay so the 2 moves black gets on it's first move doesn't quite allow you to reverse all reversible and not look like you haven't moved).

Okay, clearly you weren't talking about retrograde analysis.

If you are talking about a version of "progressive chess" whereby captures and other non-reversible moves are limited in some way, maybe you had better define the rules of that game so that we can take it from there. My comments referred to the rules (several versions, but each version making for a similar game) defined in the link which you provided. And in the rules of that game I would think that captures are extremely important: once the game has progressed to each player making 3, 4, 5 and more moves each turn, if there is no way to checkmate on that turn then the player must probably capture as many of his opponent's significant pieces as possible to avoid being checkmated himself on his opponent's subsequent turn.

(Disclaimer: I have never played progressive chess, nor have I found anything out about it. Therefore I may well be totally wrong about the above strategy.)

[science_man_88]

Originally Posted by Brian-E

Okay, clearly you weren't talking about retrograde analysis.

If you are talking about a version of "progressive chess" whereby captures and other non-reversible moves are limited in some way, maybe you had better define the rules of that game so that we can take it from there. My comments referred to the rules (several versions, but each version making for a similar game) defined in the link which you provided. And in the rules of that game I would think that captures are extremely important: once the game has progressed to each player making 3, 4, 5 and more moves each turn, if there is no way to checkmate on that turn then the player must probably capture as many of his opponent's significant pieces as possible to avoid being checkmated himself on his opponent's subsequent turn.

(Disclaimer: I have never played progressive chess, nor have I found anything out about it. Therefore I may well be totally wrong about the above strategy.)

for example with white moving an odd number of moves Nf3 Ng1 e4 is possible but because the knight didn't effectively move or capture it's equivalent to 2. e4 in normal chess. admittedly it's black that has the problem as they get all even number of moves and so don't just have just one move left that can't be reversed at least to my knowledge.

edit: the other thing that comes to mind is the possible need for a 3 time repeat by either player which would be a draw in normal chess.

[Brian-E]

Science Man: Without being 100% sure I understand what you are getting at, I suspect you have the wrong mindset for what is required to "solve" chess or a variation of chess. It has nothing, for example, to do with counting legal continuations or legal positions like we were doing in a different thread. We are looking for the result of the game with "best play" by both sides.

To illustrate a particular feature of Progressive Chess, which I can think of without investigating the game properly, if White opens 1.e4 (or 1.e3) Black must immediately, on his first move, guard against the scholars mate because White is immediately threatening to play the 3-move sequence Bc4,Qh5,Qxf7mate. I hope this illustrates that looking at continuations like Nf3,Ng1 is completely irrelevant.

[science_man_88]

Originally Posted by Brian-E

Science Man: Without being 100% sure I understand what you are getting at, I suspect you have the wrong mindset for what is required to "solve" chess or a variation of chess. It has nothing, for example, to do with counting legal continuations or legal positions like we were doing in a different thread. We are looking for the result of the game with "best play" by both sides.

To illustrate a particular feature of Progressive Chess, which I can think of without investigating the game properly, if White opens 1.e4 (or 1.e3) Black must immediately, on his first move, guard against the scholars mate because White is immediately threatening to play the 3-move sequence Bc4,Qh5,Qxf7mate. I hope this illustrates that looking at continuations like Nf3,Ng1 is completely irrelevant.

okay maybe I'm not thinking correctly when I think progressive chess can be turned back into normal chess and therefore have a way to solve it.

[CRGreathouse]

Originally Posted by Zeta-Flux

This brings up two problems in such searches: do you ignore the 50 move rule? what metric do you use to measure a position (moves to conversion? moves to mate? win/loss? etc...)?

The valuation I would use: first (of course) prefer games which win to games which do not guarantee a win. Next, minimize the number of rounds in which your opponent has the opportunity to claim draw under the 50-move rule (thus preferring games abiding by the limit when possible). Next, minimize the maximum number of moves to mate. Finally, prefer the lexicographically first such move.

[LaurV]

re: post #11, the OP about progressive chess:

The two games are not equivalent, "taking back" moves in progressive chess is not the same as "solving" normal chess. "Solving" games uses a minmax algorithm, i.e. shortest path. If I am to move I will try to maximize my chances and minimize yours, or try to minimize my damages, when you maximize your attack efficiency. That is, I have to pick up my "best move", in such a way that whatever move you do after, my damages are minimum (or yours are maxed) and/or my advantage is maximized (or your is minimized), and do this recursively (deep search, backtracking, whatever heuristic).

Progressive chess is a "limited" (bounded) game. One can prove that no (optimum) game of progressive chess can take more the N turns, because there is a limit (N,T) of the number of (moves,turns) which can win any position. This N is very small (100? 47? 20? 10?), and T is smaller then 8. This means, given any position where
1. I am to move
2. I have more then the king on the table, and not only (king plus single bishop), or (king and locked pawns), i.e. I have at least an active piece which is not a single officer or locked pawn.
and where the game continues normally, like:
1. I make N moves,
2. You make N+1 moves, etc.
Then there exists a (small) N for which I can always win in less then 8 turns.

The idea is very simple, given any position and enough big N, if I have an active piece, or an unlocked pawn (which is a queen in just few moves), then I can use my N moves to capture all your pieces and put your king in an "unpleasant" situation, or even make him checkmate.

This N can be computed in reasonable time, and it is really small. Of course, there are exceptions, for example, a King plus a Rock against a King can NEVER be won, except when the lone king is already on the side of the board, there is no way to force him to move out of the row he already occupies, if he is allowed to do - not N, but only one or two moves. Try and see, put a black K somewhere on the board, not on a side, a white K and a white R anywhere, white can do ANY number of moves, black is allowed to do only 1 or 2 moves, and white still can't win. Having an "even" number of moves allowed is equivalent as having the right to "pass" (zero moves) and in this case you can't force the black king to move. He can make one move in one direction another one back, and repeat, or he can keep the "ring" (i.e. column, row) and never go on the side. You CANNOT mate him with K+R on the middle of the board. Also, having only a bishop, you can't capture pieces laying on bishop's opposite-color squares. Etc. But the exceptions are few, and easy to solve separate. What is left is the fact that you can win any "winnable" position, if you are allowed to do X moves, for any X>N, and this N is very small and can be computed (the opponent has maximum 15 capturable pieces, the worst case needed to capture all won't be much larger! and most of them are already captured in previous turns).

From this, you still have few turns to force the king into mate, and this could be easy to prove by each case, that T=8 is the maximum number, if N is at least 2 (for N=1 you still may need more moves, see "mate with two bishops and king against king" in classical chess, which is a laborious procedure). And N is sure bigger then 2 already.

I never played this kind of chess, and is first time I hear about, but I don't believe the optimum game takes more then 8-10 turns, TOTALLY, from the start to the end. If I am allowed to do so many moves in a row, I let the other guy without pants immediately, if he does not let me without pants before.

So, proving this is (white or black) sure-win should be piece of cake, as your search depth can't be bigger then 8, 9, 10 (?) turns maximum. A very short min-max backtrack of 8-10 levels deep. Of course the width of it is larges, on any level you have to analyze many combinations, but most of them will result in "heavy damage", simplifying the board a lot. Which is not the case in normal chess.

[diep]

Originally Posted by Brian-E

Science Man: Without being 100% sure I understand what you are getting at, I suspect you have the wrong mindset for what is required to "solve" chess or a variation of chess. It has nothing, for example, to do with counting legal continuations or legal positions like we were doing in a different thread. We are looking for the result of the game with "best play" by both sides.

To illustrate a particular feature of Progressive Chess, which I can think of without investigating the game properly, if White opens 1.e4 (or 1.e3) Black must immediately, on his first move, guard against the scholars mate because White is immediately threatening to play the 3-move sequence Bc4,Qh5,Qxf7mate. I hope this illustrates that looking at continuations like Nf3,Ng1 is completely irrelevant.

Factoring and chess are similar fields in some sense.

Chess is a much easier thing to search obviously and no complicated math skills needed.

Very important is the definition of what you want to accomplish.

Do you want to play "the best moves", or do you want a 100% proof on that what you play IS the best move?

This is 2 total different things.

Important is some history as we see how along history progress is there in search. It all focuses around the time needed to search 1 ply deeper which is a way to define what the branching factor is.

What we see in game tree search is that the branching factor to get a ply deeper is gradully getting smaller. It's in fact not possible to write a proof for what is possible to achieve there, as all proofs always are about a specific algorithm and in reality a new lossy algorithm will get found that gets the branching factor even less.

A good example is what has been written about alfabeta. It basically says (without going into details) that *roughly* you need to search the square root of the number of possibilities.

Now the average number of moves i MEASURED to be 40 in chess (in positions where you are not in check - as being in check gets extended anyway).

The big problem of the proof there is that it doesn't involve additional algorithms. Now the big question is whether using some big RAM for transpositiontables is having any impact onto the number of possibilities or whether it's just a problem in the alfabeta proof.

So if we take the square root of 40 that's something above 6

yet end 90s i observed how with just good working hashtables (transpositiontables) this branching factor already got 4.0 and with nullmove, this became 3.0+

The initial statement against this 3.0+ was that nullmove would not be a correct way to search.

Now i invented double nullmove therefore. With double nullmove we can prove that you will find every zugzwang eventually, be it against a bigger search depth for those lines where they occur.

I got back then a lot of bad responses from a lot of professors and scientists for claiming that 3.0 was possible.

Only from some of the commercial programmers i got support, yet none of them dared to public post. They just responded on my private email. The reason for that was that their engines already were ACHIEVING 2.8 in fact (like Frans Morsch emailed me). So they already had proof there, but didn't want to publicly post this.

Now to quote another programmer, reductions are trivial to invent. A search technique that i invented myself in 1999, yet it wasn't until 2004-2005 that publicly some started to post about it. Nowadays more well known under the name 'LMR' though LMR is not an accurate way to name what most engines are doing right now as in fact a small condition change already would cause it to be named different so let's call it reductions.

End 90s i posted onto the internet the notion of using several reduction factors at the same time for nullmove and i was using it. A guy then took over that idea and one small implementation of it (the casus of R=3 with R=2 the last 6 plies), he called Adaptive Nullmove in his publication. That was Ernst A Heinz. He became an assistant professor later on.

Nowadays the 2 techniques get combined with nullmove and branching factors have gone down. This in combination with improved and very well automatic parameter tuned evaluation functions.

That last thing: automatic parameter tuning, is a big issue in computerchess. In fact bigger than searching yet another ply deeper.

We simply see branching factor now is under factor 2.0, for most programs it's nearly exactly factor 2.0 on average, some already get under it, be it with more dubious techniques not seldom.

One of the underlying reasons also has to do with accurate hashtable information. Using a big buffer of RAM simply works real well.

The hard fact is: the time to search deeper goes down.

Now chess has in total less than 10^43 positions. The first question is how big the search space is that you practical see when playing the 'perfect game'.

Note i do not doubt the perfect game is a win for white, though some disagree there and guess it might be a draw.

In openingstheory i see too many lines that end with big advantage for white after which in next game a GM tries yet another move with black.

So the whole question is how big the search space is you need to cover to play that perfect game. After we know that answer some search proces of the far future will be a lot more efficient than today and might already play the best move.

Now chess is different from checkers/draughts. In those games you need to move forwards and cannot go back unlike half the pieces in chess which also move backwards when needed.

So getting a solution for checkers which gets done with a combination of endgametablebases (EGTBs) with search, this is tougher in chess.

Yet who knows?

Now on solving. Realize we didn't have an accurate estimate yet on how many positions there are. Is it 10^43 or less?

We know just 1 estimate from 90s and i do not know who made it nor how he reached it.

When i did do for some hours some calculations here, i got to somewhere around 10^39 or so and the count was still going so could be more.

Yet long before we reach this amount, we can already solve it in combination with a search, as it's rather easy to show that if we exchange a piece or what we will get far in our proving proces using a search.

So in that sense 10^30 storage would already do the job i'd suspect, maybe less.

[Brian-E]

Originally Posted by diep

Note i do not doubt the perfect game is a win for white, though some disagree there and guess it might be a draw.

In openingstheory i see too many lines that end with big advantage for white after which in next game a GM tries yet another move with black.

I'm going to nit-pick on this statement out of all the interesting analysis you have written both here and in the thread about counting legal positions.

Very few people would disagree that White has an "advantage" at the start of the game. What this means, I think, is that in a typical opening position with Black to move there are more ways for him to select a move which allows his opponent to force a win than there are for White in typical opening positions with White to move. It does not say that there are no continuations for Black which avoid White being able to force a win. I am one of those who believe the game is a draw with perfect play.

[axn]

Originally Posted by diep

Now on solving. Realize we didn't have an accurate estimate yet on how many positions there are. Is it 10^43 or less?

We know just 1 estimate from 90s and i do not know who made it nor how he reached it.

When i did do for some hours some calculations here, i got to somewhere around 10^39 or so and the count was still going so could be more.

http://en.wikipedia.org/wiki/Shannon_number