True or false? Chess will never be solved! why?

You got me, I didn't look at the links. Thank you for opening my eyes to a whole new way of thinking!

Mindboggling stuff - once I had reconciled to the fact that both sides weren't playing white (shiny white and matt white).

:-) Those two don't play chess any more. No point, obviously, once you have worked it out. They are back in England now and they just sit round mostly, not saying much but obviously deep in thought. They must be working on some other complex problem, but I don't know what. Thanks for taking the time to understand. 

To solve chess, we need a blue police box.

According to my calculation adding a piece to an existing tablebase increases the complexity a hundred times. Going from a 7 men tablebase to a 10 men tablebase requires a million times more memory.

Currently one million atoms are used to store one bit of information and also the energy used for storage is million times more than allowed by theory.

It is realistic that storage can be made a million times more effective, making a 10 men tablebase feasible.

http://www.wired.com/2012/01/ibm-scientists/

Big achievement.

Here's an update on the progress of using diamond to store data, which I mentioned much earlier in this thread, sometime last year:

http://www.theregister.co.uk/2014/08/11/another_step_forward_for_diamondbased_quantum_computers/

This is about the current limit of "foreseeable future".

So based on the 100 fold estimate, from there, it's only a 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000 fold increase to get to a 32 bit tablebase!

Question: do you think the 100 fold increase holds for calculation intesity as well?

(Assuming classical computing, of course)

....if not ?....at least a pixie detective bombing around on a beach croozer singing "Do u know the way to San Jose ?" (i.e., silicon valley)

Diamond sounds unviably expensive however. 

Not really.  Diamond prices are artificially inflated and have been ever since manufactured diamonds came into being; plus, the diamonds you are thinking of are mined diamonds with flaws in them...wholly unsuitable for this purpose :).

This would use manufactured diamond "sheets", and all it takes is carbon and pressure.  Thus, "foreseeable future", aka hard science fiction vs. soft science fiction.

Gold, silver, platinum...these are actually rare elements (because fusion inside stars only compacts to iron normally...heavier elements require a greater catalyst) that will remain hard to find or produce.  Diamonds, no.  Diamonds are made of cheap and abundant carbon.  Someday, diamond coffee tables will be commonplace.

Diamond is artificially expensive, there is a long standing cartel manufactured "supply shortage" created by withholding diamonds from the market.

Diamond is also possible to synthesize.

Ahh, seconds too slow.

Ooh, ostentatious!

100 fold increase in complexity with adding a new chessman only holds at the current level of tablebases. Two kings are 3612 positions + 30 chessmen would mean 3612 * 10^( 30 * 2 ) positions or 3.6 * 10^63 positions and it is proven that there are less than 10^46.

When there are many chessmen on the board there are less squares to put a new chessman on and also this new chessman can't be anything due to legality issues. If apart from kings you already have 16 pawns and a white queen on board, you can't put an other white queen there, because this would be illegal. If apart from kings you have only a white queen on board, you can put there an other 8 white queens and it will still be legal. ( There are even more subtle combinatorial reasons, but I don't want to discuss them here. I have calculated complexity up to 10 men with a program that takes into account every possibility. )

On the other hand if in positions with two kings you put a single chessman on board, you can do this is 62 * 10 ways ( 62 squares are free and there are 10 chessmen available: white / black: pawn, knight, bishop, rook, queen ). So to go from a 'two men tablebase' ( only kings ) to a three men tablebase you added complexity of 620 times insted of 100 times.

( Note: the above are raw estimates for completely random positions, pawns can be on the first and last rank, they can be illegal due to checks, symmetries are ignored, turn is ignored, etc. ).

Complexity increases very quickly with adding a new chessman when there are only a few chessmen on board, then with more and more chessman on board this pace starts to slow down. Adding a new chessman to a 31 men tablebase only increases complexity in a marginal way. However this increase will be 100 times in the foreseeable future.

Also computational power has to increase, but this is a lesser worry because theoretical limits to computational power are ridiculously high compared to limits of storage. A 1 kg computer operating at Bremermann's limit could perform operations on the order of the number of legal positions in less than a second.

Combinatorially possible positions with legally placed kings ( according to my program's run ) :

 3 men: 2.24e+006

 4 men: 6.85e+008

 5 men: 1.37e+011

 6 men: 2.03e+013

 7 men: 2.36e+015

 8 men: 2.24e+017

 9 men: 1.80e+019

10 men: 1.24e+021

Some bullhit math ( bullhit means something that was hit by a bull ):

How to build a perfect hash of all 7 men combinatorially possible positions?

What makes this possible is that the problem can be divided into three independent parts.

There are always two kings on the board, so first create a function h1 which maps all possible legal king arrangements to an index:

h1 ( king arrangement ) -> 0 ... 3611

For all king arrangements there are 62 squares to place 5 non king chessmen, this can be done in choose(62,5) = 6 471 002 ways. Create a function h2 which maps all possible occupied square arrangement to an index:

h2 ( occupied squares ) -> 0 ... 6 471 001

Given 5 occupied squares there are 10^5 ways to fill these places with chessmen ( order matters! ). It is trivial to create a hash function for this case, just use codes 0 ... 9 for the ten possible chessmen and write them down in the right order, you will get a number between 0 and 10^5-1:

h3 ( chessmen arrangement ) -> 0 ... 99 999

You can get the address at which the value of a position is stored:

memory index = ( h1 * 6 471 002 + h2 ) * 100 000 + h3

The only thing you have to actually store in memory is an integer per position ( 0 for draw, or +/- mate in N moves ).

Since most of the positions are draw or mate in a couple of dozen moves, the true information content of those integers is not more than 5-6 bits / position. You can zip integers in 100 000 integer blocks to reach this compression, and unzip only the block which is queried.

The outcome of all chess positions without castling rights is invariant under flipping the board over the vertical axis. This means that you can improve by a factor of two on the raw method. ( There are more symmetries for positions without pawns but in a typical 7 men position there will be at least one pawn. )

Using this method the 7 men tablebase can be stored on cca. 6 * 10^15 bits.

It is actually stored on 1.12 * 10^15 bits ( 140 TB = 140 * 10^12 * 8 = 1.12 * 10^15 bits ). So the creators of the tablebase must have used a more clever method than this.

Watcha's the only one who can use bogus math in this thread.

This may be easier to come to terms with: the human genome contains cca. 1 GB of information coded in DNA. This DNA is cca. 6.9 cubic micrometer in volume. This means that a 10 men tablebase can be stored in 1 cubic centimeter DNA: