I think it is almost conclusive that chess canNOT be solved.

[Zlaire]

The number of possible chess games up to move 80 is 10^123, however the number of legal positions is "only" 10^50 (same as the number of atoms the earth consists of as mentioned).

And you "only" need to store the positions, not the moves leading up to the positions.

[kranium]

there are more (possible) chess positions than atoms in the universe?
are you sure about that?

Perhaps not the universe (10^79 atoms or so), but the earth consists of about 10^50 atoms which is about the same as the number of legal chess positions.

So basically you'd need a harddrive the size of the earth to store them all, if every position took one atom to store (including best move).

as far as i know, there's no correlation between # of atoms and size....

i.e. you can have a spoonful of (dense) matter with billions of atoms..
conversely you can have 1000 sq. kilometers with only 1 atom...

aren't we just talking about the 'size' of a number (not about physical dimensions)?

[kranium]

there are more (possible) chess positions than atoms in the universe?
are you sure about that?
<:

shannon calculated 10 to the 120th chess positions

Well, since the number of atoms in our universe is about 10^80, you would still need 10^40 parallel-universes to store them all.

so, you are saying that there are more chess positions than the # of atoms in 10 to the 40th universes?

[F.Huber]

there are more (possible) chess positions than atoms in the universe?
are you sure about that?
<:

shannon calculated 10 to the 120th chess positions

Well, since the number of atoms in our universe is about 10^80, you would still need 10^40 parallel-universes to store them all.

so, you are saying that there are more chess positions than the # of atoms in 10 to the 40th universes?

No, not positions but possible moves (because your 10^120 is about the number of moves).

But all that doesn´t really make any difference: whether 10^50, 10^80 or 10^120 - none of these numbers (positions or moves) will ever be computable (or even just storable).

[Harald]

for every possible position there will be known 'best' move(s)...
(the opening is already very well known, egtb has just about 'solved' the endgame...)
middle game positions will be mapped, i.e. mate in 36? etc.

There is a very real limit to how many positions can be stored (mapped). There simply isn't enough matter on the earth (or in the universe) to store all legal chess positions.

Even if one position would take one atom to store, there wouldn't be enough atoms.

So something very drastical would have to happen in order to solve chess in the way you propose.

there are more (possible) chess positions than atoms in the universe?
are you sure about that?
<:

shannon calculated 10 to the 120th chess positions

envision this:
an extremely large disk farm with millions (or billions) of terabytes disk storage
incredibly efficient compression algoritms
a chess algoritm that has the ability to calculate the 'best' move in any position (moves to mate?, perhaps something similar to egtb?, maybe even brute force calculation...although this would certainly overwhelm any super computers that exist today) this is the unknown part i think

eventually anyone could access the database to 'lookup' the best move in any position

that's what i envision for the future... (near future?...probably not)

Talking about universes. You want to know for each position or move
the number of moves to end the game or some value.
Imagine you had a real deep thougt machine that gave you an answer. Let it be 42.
Then perhaps you have to build an even bigger machine to tell you what that means.
May be the result is "What do you get if you capture Qe6 by knight?"

Harald

[kranium]

there are more (possible) chess positions than atoms in the universe?
are you sure about that?
<:

shannon calculated 10 to the 120th chess positions

Well, since the number of atoms in our universe is about 10^80, you would still need 10^40 parallel-universes to store them all.

so, you are saying that there are more chess positions than the # of atoms in 10 to the 40th universes?

No, not positions but possible moves (because your 10^120 is about the number of moves).

But all that doesn´t really make any difference: whether 10^50, 10^80 or 10^120 - none of these numbers (positions or moves) will ever be computable (or even just storable).

i believe: since it is a finite number..., it will be eventually be calculated.

i.e. the # of moves is finite..
the calculating power of the computer is unlimited...and growing exponentially.
thus, at some point in the future, (how long is anybody guess) it will be accomplished.

[Zlaire]

aren't we just talking about the 'size' of a number (not about physical dimensions)?

The posibility to store chess positions has a physical limit. Since the number of positions is so incredibly large there simply won't be enough matter to store the positions on.

How do you propose the positions (and best move) are stored? Some type of physical storage unit will be needed. What type of (even imaginary) physical unit can store 10^50 positions?

As I said that unit would atleast have to be the size of the earth, if every atom stored one position.

the calculating power of the computer is unlimited...and growing exponentially.

Perhaps, but not the storage capacity, it has a physical limit.

[Dirt]

there are more (possible) chess positions than atoms in the universe?
are you sure about that?

Perhaps not the universe (10^79 atoms or so), but the earth consists of about 10^50 atoms which is about the same as the number of legal chess positions.

So basically you'd need a harddrive the size of the earth to store them all, if every position took one atom to store (including best move).

as far as i know, there's no correlation between # of atoms and size....

i.e. you can have a spoonful of (dense) matter with billions of atoms..
conversely you can have 1000 sq. kilometers with only 1 atom...

aren't we just talking about the 'size' of a number (not about physical dimensions)?

You still have to come up with about as much mass as the Earth has to start with. Frankly, I think it would be easier to work with ordinary matter. The size of the Earth isn't such a large barrier when you have the whole Universe available.

It's possible to store much more than one bit per atom. For example, just pick an empty cubic meter of space and place one hydrogen atom in one specific cubic millimeter. That should give us over 29 bits per hydrogen atom, but I'm dubious of the practicality of any such scheme.

We could weakly solve chess, either prove it a draw or find out which side wins, with almost no storage. Alpha beta search with near perfect move ordering would only have to visit around 10^60 nodes. Assuming that the problem is sufficiently parallelizable[*] for this to actually work, It would still take more processors than I think would fit on the Earth to finish in any sort of reasonable time frame.

The best approach is probably to combine the two approaches, as was done with checkers, but it still looks too difficult for me to expect that anyone will ever be willing to go to that much trouble to solve a problem of no practical importance.

*Yet another word I've had to add to my Firefox's private dictionary. The number of common words missing is disappointing.

[vb4]

Hi Norman,

I agree. It may be that although we may not "solve" the game fully what may happen is that eventually we may find moves that once white moves will be able to force direction of the next move where all other possibilities eventually lead to destruction. In that case as long as our databse through the years increases in information we may get to this point. Just my 2 cents.

Les

[kranium]

there are more (possible) chess positions than atoms in the universe?
are you sure about that?

Perhaps not the universe (10^79 atoms or so), but the earth consists of about 10^50 atoms which is about the same as the number of legal chess positions.

So basically you'd need a harddrive the size of the earth to store them all, if every position took one atom to store (including best move).

as far as i know, there's no correlation between # of atoms and size....

i.e. you can have a spoonful of (dense) matter with billions of atoms..
conversely you can have 1000 sq. kilometers with only 1 atom...

aren't we just talking about the 'size' of a number (not about physical dimensions)?

You still have to come up with about as much mass as the Earth has to start with. Frankly, I think it would be easier to work with ordinary matter. The size of the Earth isn't such a large barrier when you have the whole Universe available.

It's possible to store much more than one bit per atom. For example, just pick an empty cubic meter of space and place one hydrogen atom in one specific cubic millimeter. That should give us over 29 bits per hydrogen atom, but I'm dubious of the practicality of any such scheme.

We could weakly solve chess, either prove it a draw or find out which side wins, with almost no storage. Alpha beta search with near perfect move ordering would only have to visit around 10^60 nodes. Assuming that the problem is sufficiently parallelizable for this to actually work, It would still take more processors than I think would fit on the Earth to finish in any sort of reasonable time frame.

The best approach is probably to combine the two approaches, as was done with checkers, but it still looks too difficult for me to expect that anyone will ever be willing to go to that much trouble to solve a problem of no practical importance.

i'm a believer...
100 years ago they wouldn't have believed what is possible today...

i just saw the other day an external hard disk with 2 terrabyte storage capacity (it was 149 €) ! less than 10 ago, only corporations with large data centers had this kind of storage capacity (considered enormous at the time).

if ((num_possible_moves_or_positions != infinity) && (potential_storage_capacity == infinite))
then possibility_it can_and will_happen = 100;

as far as the size of the disk farm needed, who knows...compression algorithms are steadily improving..
who can say?