Chess will never be solved, here's why

Sort:
MARattigan
EylonShachmon wrote:
MARattigan wrote:
EylonShachmon wrote:
...

There are (64!)/(32!) positions just with all the prices on the board...

Er, you sure about that? I think I prefer the gibberish.

So long as we're talking about basic rules positions at any rate (@tygxc obviously isn't).

No I ment positions in total not legal positions, that is the number if you just put every piece in a random position.

Only if you label the pieces, e.g. calling your white horses Prancer and Charger.

one of the things they check when they check if the position is legal or not is stuff like bishops not on the same colour, pawns not on first and last row, kings not near each other ….

Last is normally king of side not to move not in check, but you haven't mentioned side to move. Some tablebases have extra constraints like no triple checks (but unless you can get hold of the generating code you'll probably need to find out by trial and error). The upshot is to significantly reduce the number. 

The best available estimate of legal positions under basic rules to date is the paper you didn't like, as far as I know. And it's not 10^44 as @tygxc keeps trying to tell everyone, but (4.82 +- 0.03) * 10^44.

If you want to talk about legal positions under competition rules and equate them to game states (as @tygxc does) then you have to increase that number by a ridiculously huge unknown factor (as @tygxc doesn't - he instead divides it by something rather less huge but more ridiculous). 

(! Is factorial, it is the number times every integer smaller, so 5! = 5•4•3•2•1=120, 6! = 6•5•4•3•2•1=720, 10! = 10•9•8•7•…•2•1=3,628,800)

I assumed so.

 

MARattigan
Optimissed wrote:


Seriously, no-one is going to buy this as any kind of a solution for chess...The entire, artificial idea of "weakly solving", "strongly solving" etc is complete nonsense because in practice, they overlap considerably.

...

Weakly solving overlaps strongly solving in exactly the same way that vegetables overlaps cabbages. That doesn't mean that no-one is going to buy any cabbages.

tygxc

@6899

"there is a reason very few mathematicians study chess"
++ There has been a lot of progress. Work by Tromp and Gourion has shown there are not as many positions as previously thought. Work with AlphaZero has acquired game knowledge with only the Laws of Chess as input and hence no human bias.
There is also progress on the 8-men endgame table base.

"there is currently little to no advancements to be made" ++ There has been advance last year.

"all the research has pretty much already been done" ++ No way, it has barely started.

"we know it cannot be solved" ++ We know it can be weakly solved and it takes 5 years.

"the few games that have been “solved” like checkers is just a proof of concept"
++ No, Schaeffer has weakly solved Checkers with 10^14 relevant positions of the 10^20 legal positions and by pruning the 300 tournament openings down to 19.
The same  path is viable for Chess, but it takes 10^17 relevant positions, that is 1000 times more than Checkers. Present computers can do that in 5 years.

EylonShachmon
MARattigan wrote:
EylonShachmon wrote:
MARattigan wrote:
EylonShachmon wrote:
...

There are (64!)/(32!) positions just with all the prices on the board...

Er, you sure about that? I think I prefer the gibberish.

So long as we're talking about basic rules positions at any rate (@tygxc obviously isn't).

No I ment positions in total not legal positions, that is the number if you just put every piece in a random position.

Only if you label the pieces, e.g. calling your white horses Prancer and Charger.

one of the things they check when they check if the position is legal or not is stuff like bishops not on the same colour, pawns not on first and last row, kings not near each other ….

Last is normally king of side not to move not in check, but you haven't mentioned side to move. Some tablebases have extra constraints like no triple checks (but unless you can get hold of the generating code you'll probably need to find out by trial and error). The upshot is to significantly reduce the number. 

The best available estimate of legal positions under basic rules to date is the paper you didn't like, as far as I know. And it's not 10^44 as @tygxc keeps trying to tell everyone, but (4.82 +- 0.03) * 10^44.

If you want to talk about legal positions under competition rules and equate them to game states (as @tygxc does) then you have to increase that number by a ridiculously huge unknown factor (as @tygxc doesn't - he instead divides it by something rather less huge but more ridiculous). 

(! Is factorial, it is the number times every integer smaller, so 5! = 5•4•3•2•1=120, 6! = 6•5•4•3•2•1=720, 10! = 10•9•8•7•…•2•1=3,628,800)

I assumed so.

 

Yes if you label the horses that was a very basic number to start with, but as I said if you make the calculations with the horses and the pawn unlabelled(and the king and the rooks have a “can castle” option) and you include the positions with less than 32 pieces is comes to about the same number, a bit less, my point with 12/2,000,000 still stands.

 

I didn’t give a list of all things they check that was an example ;-;

 

i really don’t understand where that 4.82*10^44 came from, in the gibberish page the number just appeared out of nowhere and that is the only place I have seen it.

 

 

DiogenesDue

Don't conflate Tromp's data with Tygxc's theories.  Tromp has previously told Tygxc to take a walk wink.png.  The 10^44 number is the most solid estimate for unique legal positions , down from the previous 10^46 that was accepted before it.  If you think it's all gibberish, load up the software yourself and run it, and collect the $250 dollar bounty for finding an issue with it.  If you can't make heads or tales of GitHub or figure out how the number was derived, then...maybe not the right person to comment on the veracity of the data.

tygxc

@6904

"I just read the page you linked to, that was a mess of gibberish."
++ Tromp's and Gourion's work is solid.

"There is no explanation of anything, and they are just throwing numbers and terms from nowhere." ++ Maybe you lack some background.

"What I did understand is that they tested 2 million random positions, and got 12 legal positions out." ++ No, not at all. Tromp calculated exactly 8726713169886222032347729969256422370854716254 positions with a Haskell program.
Then he randomly sampled 1,000,000 of these and he found 56011 of those to be legal.
Thus he arrived at (4.85304 +- 0.039) e+44 legal positions.
The vast majority of those positions makes no sense,
see the 3 displayed random samples with 3 rooks / bishops per side.
Gourion counted the positions without promotions to pieces not previously captured as 10^37.

"I have no clue how they got there" ++ They explained in their papers. You can read it.

"but it doesn’t matter!" ++ It does matter.

"There are (64!)/(32!) positions" ++ No.

"How did they get to 10^44 is beyond me."
++ 8726713169886222032347729969256422370854716254 * 56011 / 1000000 = 4.85 * 10^44

"there are a ton of flaws in the page" ++ No. It is solid work.

"it appears you didn’t read the paper?" ++ I did read it, did you?

"He is calculating legal positions where pawns can’t promote?" ++ Legal positions where pawns do not promote to pieces not previously captured, i.e. no 3 rooks or 3 bishops per side.

"These are vastly fewer than the amount of total possible positions?"
++ Yes 10^37 as opposed to 10^44. The vast majority of the 10^44 legal positions has e.g. 3 rooks / bishops per side, as you can see from the 3 random samples displayed on the Tromp page. So the Gourion figure of 10^37 is more realistic for the purpose of estimating the viability of solving Chess.

"there is literally 0 reason for that random division by 10000"
++ Inspection of a random sample of 10,000 Gourion positions shows none can result from optimal play by both sides. Hence 10^37 / 10000 = 10^33 reasonable positions.

"What you do afterwards with square rooting and multiplying by 10 is nonsense, you can’t do that with no explanation, needing one strategy doesn’t magically square root away your problems." ++ It is the main difference between weakly solving and strongly solving. To strongly solve you need all legal positions i.e. all legal white moves and all legal black responses. E.g. on move 1: 20 * 20 = 400 positions. To weakly solve you need only 1 black response to each white move: 20 * 1 = 20 positions. 20 = Sqrt (400). The same after 2 moves, 3 moves... d moves.
To weakly solve only needs the square root of the number of positions to strongly solve.

"this is NOT how you calculate how much it would take to weakly solve chess." ++ It is.

"yes you need only one strategy” ++ Yes, that is the whole point of weakly solving.

"you need to firstly find it" ++ Just take the top 1 engine move for black. If the black moves thus found lead to a 7-men endgame table base draw, then they were all good enough to draw.

"so you need to go over most of the possible moves, and somehow decide which is the best"
++ Best is not necessary: only good enough to draw for black.

"which will get you the win(if possible) or draw"
++ White tries to win, black tries to draw.
Once black succeeds in leading all reasonable white moves to 7-men endgame table base draws or prior 3-fold repetitions, then Chess is weakly solved.

"So it is not just to find one move for each of the other player’s."
++ It is. It is about finding 1 black response to all reasonable white moves such that it ends in a 7-men endgame table base draw or a prior 3-fold repetition.

"this whole idea of finding the total amount of possible positions and then going down from there is broken." ++ It is the only way to estimate how long it takes to weakly solve Chess.

"You need yo start at the first move, and calculated every move you can make, and run with it until the game finishes(stale mate, win, lose, repeat..) and every position you get to you write down" ++ For strongly solving chess you need all legal white moves and all legal black moves.
For weakly solving chess you need only 1 black response to all reasonable white moves.

"if you get to a position you have already been to, you stop(because you already calculated it) "
++ That is called transition tables, those were used in weakly solving Checkers and Losing Chess.

"This(and variations of this) is the only way to do it."
++ The essence: strongly solving: all legal white moves, all legal black responses;
weakly solving: all reasonable white moves, only 1 black response each.
Many here fail to understand that and use the time for strongly solving mistakenly as the time for weakly solving.

"Because the game is so complex this is very similar to strongly solving it" ++ No it is not. Schaeffer weakly solved Checkers, not strongly. He did not calculate all 10^20 legal positions, only 10^14 relevant ones. He pruned the 300 tournament openings down to 19 relevant ones.

"if we somehow agree on this 10^17 number of yours, this is still way too much"
++ 3 cloud engines of 10^9 nodes/s can do that in 5 years.

"if every one of these positions would take just 8 bytes to store, that would take be more information than the whole internet" ++ Storage poses no problem. You store only the paths from the initial position to the 7-men endgame table base draw. The solution tree is even smaller than the search tree. Checkers has a solution tree of only 10^7 positions, linking the initial position to the table base drawn positions by a path of legal moves from one drawn position to the other.

"3M$ is a lot for normal people, but it is a joke in these terms." ++ Nobody put up 3M$ so far.

tygxc

@6912

"For getting again material balance does not win, lose, or draw a game of chess."
++ 'Other things being equal, any material gain, no matter how small, means success' - Capablanca
Example:
1 e4 e5 2 Ba6?
This loses material: a bishop.
All other things are equal, white gets no compensation of any kind.
This is a forced win for black.
There is no need for further calculation.

MARattigan
tygxc wrote:

@6912

"For getting again material balance does not win, lose, or draw a game of chess."
++ 'Other things being equal, any material gain, no matter how small, means success' - Capablanca
Example:
1 e4 e5 2 Ba6?
This loses material: a bishop.
All other things are equal, white gets no compensation of any kind.
This is a forced win for black.
There is no need for further calculation.

"There is no need for further calculation."

Unless you want to solve chess. If you want to not solve chess we can agree.

tygxc

@6919

1 e4 e5 2 Ba6? is irrelevant to solving chess.
We know that loses by force for white.
It is not necessary to burn computer engine time on something we already know.
Such trivial obstacles are needed if you want to not solve chess.

Relevant questions:
How to draw against 1 e4, 1 d4, 1 c4, 1 Nf3
How to draw against 1 e4 e5 2 Nf3, 2 Nc3, 2 Bc4, 2 d4
How to draw against 1 e4 e5 2 Nf3 Nc6 3 Bb5, 3 Bc4, 3 Nc3, 3 d4
Etc, etc.

MARattigan
EylonShachmon wrote:
MARattigan wrote:
EylonShachmon wrote:
MARattigan wrote:
EylonShachmon wrote:
...

There are (64!)/(32!) positions just with all the prices on the board...

Er, you sure about that? I think I prefer the gibberish.

So long as we're talking about basic rules positions at any rate (@tygxc obviously isn't).

No I ment positions in total not legal positions, that is the number if you just put every piece in a random position.

Only if you label the pieces, e.g. calling your white horses Prancer and Charger.

one of the things they check when they check if the position is legal or not is stuff like bishops not on the same colour, pawns not on first and last row, kings not near each other ….

Last is normally king of side not to move not in check, but you haven't mentioned side to move. Some tablebases have extra constraints like no triple checks (but unless you can get hold of the generating code you'll probably need to find out by trial and error). The upshot is to significantly reduce the number. 

The best available estimate of legal positions under basic rules to date is the paper you didn't like, as far as I know. And it's not 10^44 as @tygxc keeps trying to tell everyone, but (4.82 +- 0.03) * 10^44.

If you want to talk about legal positions under competition rules and equate them to game states (as @tygxc does) then you have to increase that number by a ridiculously huge unknown factor (as @tygxc doesn't - he instead divides it by something rather less huge but more ridiculous). 

(! Is factorial, it is the number times every integer smaller, so 5! = 5•4•3•2•1=120, 6! = 6•5•4•3•2•1=720, 10! = 10•9•8•7•…•2•1=3,628,800)

I assumed so.

 

Yes if you label the horses that was a very basic number to start with, but as I said if you make the calculations with the horses and the pawn unlabelled(and the king and the rooks have a “can castle” option) and you include the positions with less than 32 pieces is comes to about the same number, a bit less, my point with 12/2,000,000 still stands.

No it doesn't.

You haven't quantified what "about the same number, a bit less" is, so you don't have a point. The number you originally came up with was (8! x 2! x 2! x 2!)^2 = 104044953600 times too high.

You then proceed to assume Tromp's measured ratio of legal to total positions will also apply to positions corresponding to the diagrams in your estimate, whereas you include all diagrams with pawns on the first and eighth ranks, 100% of which are illegal, and Tromp doesn't include any, so that would be invalid even if you were to quote the correct ratio.

 

nba_xander

that was a lot to take in

BoardMonkey

100,000,000,000,000,000,000,000,000,000,000,000,000,000,000

Elroch

No. He was right and you were wrong. Best to see it and move on, rather than a vain attempt to obfuscate.

mpaetz

     If people wish to engage in a circular discussion of this (or any) topic, delving into minutia of any aspect, that is their choice. They may well find it entertaining and informative.

     Anyone who finds this a waste of time has the simple option of not bothering to follow this thread.

MARattigan

Occasional?

MARattigan

First thing you need to do is understand what "solve chess" means.

tygxc

@6936

"First thing you need to do is understand what "solve chess" means."

++Ultra-weakly solved means that the game-theoretic value of the initial position has been determined,
weakly solved means that for the initial position a strategy has been determined to achieve the game-theoretic value against any opposition, and
strongly solved is being used for a game for which such a strategy has been determined for all legal positions.

The only meaningful to discuss for Chess is weakly solving.
For all practical purpose Chess is already ultra-weakly solved,
and the game-theoretic value of the initial position is a draw.
Strongly solving Chess would generate a 32-men table base
and need to determine a strategy for all 10^44 legal positions, that is too much.
That leaves weakly solving, and that needs 10^17 relevant positions,
which present computers can calculate in 5 years, like GM Sveshnikov said.

Just like weakly solving Checkers, pruning is allowed. Schaeffer calculated only 19 of the 300 tournament openings, eliminating 200 by transposition and 81 by pruning.
Just like weakly solving Losing Chess the 'best first' heuristic is allowed.
Just like weakly solving Connect Four it is allowed and beneficial to incorporate game knowledge. That is also what Prof. van den Herik wrote.

Elroch

You don't understand what Schaeffer did. He would tell you where you are going wrong if he had the chance.

RemovedUsername333

It is not accurate to claim that chess is already ultra-weakly solved and that the game-theoretic value of the initial position is a draw. While it is true that the game of chess is generally thought to be a draw when both players play optimally, this has not been proven and it is still possible for one player to achieve a winning advantage through superior play.

Furthermore, it is not possible to fully solve chess in the sense of finding a winning strategy for all legal positions, as there are too many positions to consider. The number of legal positions in chess is estimated to be around 10^44, which is far too large for current computers to analyze and calculate strategies for.

It is also not accurate to claim that weakly solving chess would require calculating 10^17 relevant positions, which present computers could do in about 5 years. This claim does not take into account the complexity and depth of chess positions, and it is likely that significantly more positions would need to be analyzed in order to find a satisfactory strategy.

Finally, while it is true that pruning, the "best first" heuristic, and game knowledge can be useful in the process of solving a game, it is important to recognize that these techniques have limitations and may not be sufficient to fully solve a game like chess. Ultimately, the process of solving a game like chess is a complex and ongoing endeavor that requires a combination of mathematical analysis and understanding of game principles and tactics.

Elroch
RemovedUsername333 wrote:

It is not accurate to claim that chess is already ultra-weakly solved and that the game-theoretic value of the initial position is a draw. While it is true that the game of chess is generally thought to be a draw when both players play optimally, this has not been proven

Spot on.  @tygcx seems never to have got far enough in the mathematical sciences to understand what a proof is.