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

[Dirt]

To get to 10^43 computations is however total independent 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).

I don't think so. Alpha-beta lets you cut down the size of a game tree, but there is no tree here - just a bunch positions. As far as I can see, you can only cut the search down to the square root of the game tree complexity, from 10^123 to 10^62.5. With a large enough transposition table I guess you can get the total number of nodes visited down below 10^43, but I have little idea how far. I very much doubt you could get anyplace nearly as low as 10^22.5.

[Dann Corbit]

To get to 10^43 computations is however total independent 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).

I don't think so. Alpha-beta lets you cut down the size of a game tree, but there is no tree here - just a bunch positions. As far as I can see, you can only cut the search down to the square root of the game tree complexity, from 10^123 to 10^62.5. With a large enough transposition table I guess you can get the total number of nodes visited down below 10^43, but I have little idea how far. I very much doubt you could get anyplace nearly as low as 10^22.5.

Ignoring half move clock, those positions (the 10^43) are the game tree expanded in full (mini-max). There are no other positions to insert into it.

Now, those nodes might appear at many places in the tree, so we will have to store the pv nodes at least into a database (I don't think we can use a regular hash table because the knowledge is imperfect).

But we could use a memory mapped database. Now, it will require 128 bit processors, because even 64 bit processors will not address the RAM directly.

I'm not saying that anything here is practical in the next 5 decades. Just that Vincent's notion about solving chess isn't absurd.

[Dirt]

Ignoring half move clock, those positions (the 10^43) are the game tree expanded in full (mini-max). There are no other positions to insert into it.

Now, those nodes might appear at many places in the tree, so we will have to store the pv nodes at least into a database (I don't think we can use a regular hash table because the knowledge is imperfect).

But we could use a memory mapped database. Now, it will require 128 bit processors, because even 64 bit processors will not address the RAM directly.

I'm not saying that anything here is practical in the next 5 decades. Just that Vincent's notion about solving chess isn't absurd.

I'm certainly not taking the position that chess can't be solved. I took just the opposite position with Dr. Hyatt, even though he insisted on using 10^50 as the total number of possible positions.

If you just use alpha-beta, you're going to visit each of those 10^43 positions many times on average. Just look at the positions that will be visited in such a search: While we only need to look at one white move on the odd plies, we have to examine all of black's moves on the even plies. There are going to transpositions that lead to a reversal of color, so excluding most of the moves at the odd plies doesn't do much to reduce the total number of positions visited. I think you just end up creating a nearly complete tablebase in the end.

Just what is a "half move clock", anyhow?

[Dann Corbit]

Ignoring half move clock, those positions (the 10^43) are the game tree expanded in full (mini-max). There are no other positions to insert into it.

Now, those nodes might appear at many places in the tree, so we will have to store the pv nodes at least into a database (I don't think we can use a regular hash table because the knowledge is imperfect).

But we could use a memory mapped database. Now, it will require 128 bit processors, because even 64 bit processors will not address the RAM directly.

I'm not saying that anything here is practical in the next 5 decades. Just that Vincent's notion about solving chess isn't absurd.

I'm certainly not taking the position that chess can't be solved. I took just the opposite position with Dr. Hyatt, even though he insisted on using 10^50 as the total number of possible positions.

If you just use alpha-beta, you're going to visit each of those 10^43 positions many times on average. Just look at the positions that will be visited in such a search: While we only need to look at one white move on the odd plies, we have to examine all of black's moves on the even plies. There are going to transpositions that lead to a reversal of color, so excluding most of the moves at the odd plies doesn't do much to reduce the total number of positions visited. I think you just end up creating a nearly complete tablebase in the end.

Just what is a "half move clock", anyhow?

We only have to visit them all if we mini-max search. If we save previous searches in a database, then we will essentially get hash hits when we revisit them.

The half move clock is the evil monkey wrench that makes two positions that look identical different.

Code: Select all

16.2.5.14: Opcode "hmvc": halfmove clock

The opcode "hmvc" represents the halfmove clock associated with the position.
The halfmove clock of a position is equal to the number of plies since the last
pawn move or capture.  This information is used to implement the fifty move
draw rule.  It always takes a single operand that is the non-negative integer
value of the halfmove clock.

[Ciron]

(...)Maybe Botvinnik or Capablanca or Fischer understood some things, but not everything. Someone needs to tell us what Botvinnik got right and what he didn't).

The human way of playing chess is highly based on intuition and experience, both developed by training. This practical side seems to be much more important than theoretical knowledge and may also explain the current boom of super grandmasters at children age. Even the best players in chess history were (or are) not able to explain a) the exact way of decision making for many of their best moves, and b) the complete logical verification of those moves.

I doubt, that a complete database of possible top games in chess (supposed 10 million games with only slight inaccuracies or even perfectly played) would lead to a complete understanding what chess is really about. We might find some new patterns, of course, and get a deeper insight, just similar to what happened within the last 20, 50 or 100 years.
But then... just try to understand what's going on in any 5- or 6-men tablebase endgame, and in the end you will not know much more about chess than rather what you don't know about chess.

If there is a simple "code" for chess, than surely not in terms of (human) logic. I fear, a perfect verification (in terms of logic) of any not obvious chess move would need 1, 2, 3 or many more books, where you could read about the importance of that move for keeping the balance or gaining an advantage. Not very promising.

[chesstango]

Dear Norman: i agree u when u say that genoma map was discovered; its a fact, but although u have got the whole genoma, u have people still dieing of cancer, aids, and so many other diseases....... I dont want to compare chess with humankind, but i guess it applies to the fact that life is a wonderful but secret freeway to numan beings, and the fact we dont know where we come from neither wher we go to..... These topics will be unsolvable stuff and the mistery of life.
I guess anyway, that in case chess algorythm is ever found out, it will be a sad day for chess lovers......

[diep]

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.

The thing is, that this wasn't needed for solving other games either.
It will be a combination of things in the end, where you combine say 10 piece EGTBs with search with everything else. Chess will prove a lot harder than checkers there, because where checkers is real complicated in far endgame when both sides have a bunch of queens (i'd argue more complicated than chess, as in chess getting more than 2 queens usually means something total dubious has happened in move ordering), in both chess and checkers we have all that in EGTBs. Exact calculations should include also the effort of generating those EGTBs which is for 10 men going to be a lot more than 10^25 instructions.

So the important point i try to drop here is that CHESS IS SOLVABLE,
not to mention that an unbeatable chessprogram is possible.

After we all agree about that, let's do calculations on what we need huh?

I see Dan for example question 10^43; all not relevant, try to explain to a person who is not capable of a highschool course math, to prove alphabeta. In fact the original proof already is an upperbound on reality, as hashtables speedup things a lot; so storing search space speeds up dramatically the solving time of a search space. Reason for this is that search alone you can never prove with that you need less than 10^43 in chess with. The only thing we know about search is that if solving depth of tree is say 200 ply, that probably it is less than 2^200 to solve it with search (Corbitt would get to more like 4^200 using his lemma's).

So to avoid all those complicated proofs, much easier is giving the understanding that:
a) chess is a lot smaller than atoms in planet earth (10^43 vs 10^49)
b) that we can do 10^43 calculations around the year 2066 using todays
knowledge on what hardware gives us each 18 months in
calculation power.
c) i claim chess is solvable on planet earth

Vincent

[james uselton]

Why did such geniuses as Capablanca, Fischer and others believe that chess had been played out, or soon would be.

Happy New Year to all!

[Bill Rogers]

Why did such geniuses as Capablanca, Fischer and others believe that chess had been played out, or soon would be.

Happy New Year to all!

Hi James
You answered yourself in you post above. The answere is "geniuses".
Bill

[Bill Rogers]

I may have stated this before but I believe that with millions of games to be studied that there may be a way to solve chess, in fact it may have already been solved it is just that the solution is so big that people can not recognize it for what it is.
As an example take this analogy.
Suppose we elimnate all duplicates games, then we use transportation tables that we create on the remainder of those games to various fixed depths. Then we compare the the endings for say a fixed number of moves and create transportation tablles for all of them. Now if we could find usuable links between the first tables to the last tables we might just find that there is an answer to all or almost all of chess games, we just did not analyze all of the data presented to us in the first place.
I am not sure if a computer program might ever find the winning combination for winning every game but the above may have already found the solution.
Bill