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

[Dann Corbit]

It's always a mistake to declare that some particular problem cannot be solved.

However, it is certainly possible that chess may never be solved.

Those two things are very, very different.

[playjunior]

It's always a mistake to declare that some particular problem cannot be solved.

However, it is certainly possible that chess may never be solved.

Those two things are very, very different.

This summarizes and closes the discussion IMHO

[Dirt]

It's always a mistake to declare that some particular problem cannot be solved.

How about the halting problem?

[Dann Corbit]

It's always a mistake to declare that some particular problem cannot be solved.

How about the halting problem?

Just remove the touring machine restriction and we have a whole new (currently unknown) ballgame.

It's always hard to win the game with one hand tied behind our back.

[S.Taylor]

It's always a mistake to declare that some particular problem cannot be solved.

However, it is certainly possible that chess may never be solved.

Those two things are very, very different.

You mean that CAN not and WILL not (under the circumstances) are such different things?

[Dann Corbit]

It's always a mistake to declare that some particular problem cannot be solved.

However, it is certainly possible that chess may never be solved.

Those two things are very, very different.

You mean that CAN not and WILL not (under the circumstances) are such different things?

I mean that it might be possible to solve it, and at the same time nobody ever will solve it.

It is possible that there is a forced mate 55 plies from the origin and nobody has ever found it. If it exists, and someone finds it, then chess is solved {perhaps it starts with something really stupid looking like 1.f4! and so nobody has spent much time investigating}.

It is possible that someone may invent a new algorithm which is as big of an advance as alpha-beta was that reduces the branching factor of chess {36 with mini-max} with identical solution from the current 6 {alpha-beta} to 1.25 {with magical-new-algorithm}. If that should happen, chess could be solved with today's technology.

It is possible that someone may invent a computer someday that can perform 10^100 operations in one second. We do not know of that technology today, which is farther above ours is than the current technology is above stone tablets. But that does not mean it will never happen.

There are many things that used to be impossible according to all the experts but now are simple.

Man will never fly!

Man will never go to the moon!

Now, there are things that can be mathematically proven as impossible under certain circumstances. An example is squaring the circle with a compass and straightedge (formally proven to be impossible). But it is a simple thing to do with a bit of trig and a calculator.

To say that we "CANNOT" solve chess implies that it is not possible to solve chess by any means.

To say that we "WILL NOT" solve chess implies that we will never find a formal solution to the game.

It may be possible to solve it, but we may never find the solution.

Checkers was solved, but we do not have a complete tablebase for checkers. It was solved by moving from both ends (opening theory and also tablebase). So what was left was that sticky bit in the middle.
It is not inconceivable that chess will be solved someday in a similar manner (or in a completely different manner).

If you put enough restrictions on it (e.g. "A blind german shepherd using an abacus can't solve chess in 15 minutes next thursday") then we can pretty well agree that it won't be solved {under the stated conditions}.

When we use the expression "solve chess" we are using a mathematical term that means to literally prove the value of the game (won,lost or drawn from the opening position). It is strongly suspected that chess is a draw but we don't really know if it is won, lost or drawn. For someone to solve chess, they will have to prove the outcome of the game via some formal manner. Today, that proof looks to be centuries away or even millenia away. But someone might solve it tomorrow by some clever means that we have never encountered.

If we never do solve chess, we won't know if it was impossible or we just did not find the solution.

Another compelling question relates to the zeros of the Riemann zeta function all lie on the line with a real part of 1/2. Nobody has ever solved it (even though it is *strongly* suspected to be true and it has been verified out to 10^13). We might suspect that with lots of smart mathematicians pondering over this mystery since 1859, it should have been solved. Can we conclude that it will never be solved? No. Can we conclude that it *cannot* be solved? No. But if a solution exists or not, we might never find it.

[Dirt]

It is possible that there is a forced mate 55 plies from the origin and nobody has ever found it. If it exists, and someone finds it, then chess is solved {perhaps it starts with something really stupid looking like 1.f4! and so nobody has spent much time investigating}.

In general, I agree with everything you wrote. Specifically, though, I don't think we have the technology today to verify a 55 ply forced mate from the opening position, even if we received the PV from on high.

[diep]

Hi,

A few years ago a TV team was here to interview me about chess. They quoted Jaap van den Herik who had said : "chess is unsolvable as it has more positions possible than there is particles in planet earth".

When i googled:

http://pages.prodigy.net/jhonig/bignum/qaearth.html

Planet earth has 8.87 x 10 ^ 49 atoms

"(f) Atoms in all the earth5 = (a) x (d) x (e)6 = (1.3 x 1025) x (11.34) x (6.02 x 1023) = 88.745 x 1025 x 1023 = 88.745 x 10^48 = 8.87 x 10^49"

On other hand in his own ICGA journal (nowadays ICCA journal), in 90s a math guy had calculated the new upperbound on how many chesspositions chess has.

It was 10^43

So first claim is not true to start with.

Secondly there is a definition problem. Mathematically SOLVING is different from "being practical unbeatable". Jaap having studied math long time ago, will of course realize clearly the difference. He was speaking i assume about SOLVING. Note that commercially spoken no chessplayer cares about solving, they just care about being 'unbeatable'.

Quite soon we might be able to play in 'unbeatable manner', once we can search say 10^20 positions (or maybe even with a lot less we already can do perfectly fine).

Solving in math means however that you play it out perfect, so each won position really gets won and each drawn position you recognize as being a draw.

So that requires more than 10^43 computations obviously.

To get to 10^43 computations is however total independant from the number of particles in planet earth. It is about the number of MOVEMENTS you can manage in hardware.

Obviously getting to 10^43 movements is a lot easier than owning an object of 10^43 atoms.

A few years ago i extrapolated, assuming a speed increase of factor 2 in processing power each 18 months, what year we would get to 10^43 calculations.

That year was 2066.

I do have faith that future scientists will manage to increase the number of calculations a second we can do each year. For that of course we need clever people who get a lot of experience in parallel calculations.

Increasing the number of calculations a second that we can make might be bitter necessity, so mankind wants to survive at planet earth.

Right now it seems manycores (GPU's) and/or more complicated forms of mass calculations in complicated parallel setups are on the winning hand slowly. CPU's nowadays have a L3 cache already and the end is not in sight yet of things getting ever more complicated. Yet the increase in cpu power is definitely happening.

Thanks,
Vincent

[Dirt]

To get to 10^43 computations is however total independant from the number of particles in planet earth. It is about the number of MOVEMENTS you can manage in hardware.

Obviously getting to 10^43 movements is a lot easier than owning an object of 10^43 atoms.

A few years ago i extrapolated, assuming a speed increase of factor 2 in processing power each 18 months, what year we would get to 10^43 calculations.

That year was 2066.

You might be able to visit 10^43 nodes sometime this century (maybe!), but can you tie these together to solve chess without storing the results? I've never heard anyone suggest a method of doing this.

[Dann Corbit]

To get to 10^43 computations is however total independant from the number of particles in planet earth. It is about the number of MOVEMENTS you can manage in hardware.

Obviously getting to 10^43 movements is a lot easier than owning an object of 10^43 atoms.

A few years ago i extrapolated, assuming a speed increase of factor 2 in processing power each 18 months, what year we would get to 10^43 calculations.

That year was 2066.

You might be able to visit 10^43 nodes sometime this century (maybe!), but can you tie these together to solve chess without storing the results? I've never heard anyone suggest a method of doing this.

Using alpha-beta, you only have to process sqrt(10^43) nodes.
That is 3,162,277,660,168,379,331,999 or a paultry (using U.S. nomenclature):
Three Sextillion One Hundred Sixty-Two Quintillion Two Hundred Seventy-Seven Quadrillion Six Hundred Sixty Trillion One Hundred Sixty-Eight Billion Three Hundred Seventy-Nine Million Three Hundred Thirty-One Thousand Nine Hundred Ninety-Nine.

Now, I am not sure that it is that simple. We also have to worry about the half move clock. But perhaps that can be taken care of separately (the algorithm that crawls the tree might have internal counters for the pathways).