Solving Chess Kickstarter

[DustinYoder]

I wanted to announce that I have started a kick starter project to build and test a database structure to handle solving chess. I have discussed solving chess here and I think the community might be interested to read the details here https://www.kickstarter.com/projects/12 ... tep-1-of-3 I would request comments and advice on other outlets who might be interested in this project.

[Sven]

Hi Dustin,

may I just ask one question:

How many chess programs have you written so far?

Sven

[syzygy]

How many chess programs have you written so far?

He almost has a move generator, he thinks.

[syzygy]

I had a look at this old thread.

It seems that he wants to show that 1.e4 (or 1.d4?) is winning by building a proof tree. For each position with white to move, such a tree only needs one - winning - move.

Assuming chess is won for white, the number of nodes of such a tree would be far smaller than the number of legal chess positions. The fact that chess has a huge number of positions does not prove that the idea is unworkable.

What does make it unworkable though, is the fact that the branching factor of chess is simply too large. While it is sufficient to store only one (winning) move for positions with white to move, the tree would have to store ALL moves for positions with black to move.

Another problem is that determining a winning move a priori is next to impossible. How is one going to chose between 1.e4 and 1.d4 or any of the other reasonable opening moves? Put all eggs in the 1.e4 basket and calculate for thousands of years until one loses confidence that 1.e4 is winning and only then start looking at 1.d4? Or do both at the same time? Same for all the other positions with white to move.

For suicide chess (on the same 8x8 board with the same set of pieces, but with mandatory captures) it is possible to solve many opening positions. This shows that the state space as such is not the main problem. What makes parts of this game solvable is the much smaller branching factor resulting from the mandatory capture rule. Still the intermediate trees that get generated are several orders larger than the final proof tree, because it remains difficult to pick the right "winning" moves.

[mvk]

I wanted to announce that I have started a kick starter project to build and test a database structure to handle solving chess. I have discussed solving chess here and I think the community might be interested to read the details here https://www.kickstarter.com/projects/12 ... tep-1-of-3 I would request comments and advice on other outlets who might be interested in this project.

You might have more succes raising the money from places where the audience is completely clueless about chess programming and also has no grasp of numbers.

Other than that:

1. Why do you believe that the solution to chess involves you?

2. How long can you support yourself on $2000?

3. What is step 2 and 3, and how much do you think they will cost?

4. What is the estimated total size of the final database using your scheme?

[Henk]

It's always nice if you get payed for the time you spend on your hobby,

[ambrooks1]

Just trying to understand what is involved in "solving chess".

Let's say that you claim white has a forced win. You need a proof.

Obviously generating a game tree to represent this proof with billions of nodes on it is not going to be very appetizing. Nobody is going to want to spend the rest of their life checking this for correctness.

So somebody is going to have to try and say - "No need- I have a program which can check the game tree for correctness. " But who is going to prove that program to be correct?

It seems to me that only if you can come up with a concise, clever and elegant mathematical proof, is this thing worth doing.

For example, even when the worlds' best mathematicians came up with a proof of the four-color theorem, it was a letdown, because of the length and the complexity of the proof. I doubt that this proof is admired the same way that Euclid's proof of the infinitude of prime numbers is admired.

I am no chess expert/chess programming expert/mathematics expert - maybe I am missing something basic here?

[rbarreira]

This paragraph of the Kickstarter is hilarious:

I have currently written software to represent a chess position and a chess move. It can make and unmake moves. It can generate possible moves, check if squares are attacked, etc. What I'd like to do as a first step is finalize this code with extensive unit testing. Once it seems to be as perfect as I can make it, I would release this code to the public for review and improvement. Hopefully any remaining bugs would be caught and we could safely move to the next phase of solving chess.

This is kind of like saying "once we have built a surgical scalpel we can safely move on to the next phase of curing cancer".

I admire your ambitiousness but throwing money at this project is just about hopeless.

[syzygy]

So somebody is going to have to try and say - "No need- I have a program which can check the game tree for correctness. " But who is going to prove that program to be correct?

It seems to me that only if you can come up with a concise, clever and elegant mathematical proof, is this thing worth doing.

If you mean a concise, clever and elegant proof that white wins, obviously you can forget it.

Probably you mean a concise, clever and elegant proof that the verification program is correct. This shouldn't be too difficult. The verification program is basically a simple move generator.

For example, even when the worlds' best mathematicians came up with a proof of the four-color theorem, it was a letdown, because of the length and the complexity of the proof. I doubt that this proof is admired the same way that Euclid's proof of the infinitude of prime numbers is admired.

With the 4-color theorem one could hope for the existence of a short, concise and elegant proof. The original proof was nothing of the sort. But as far as mathematical rigor is concerned, it is probably much easier to verify the correctness of that proof (i.e. program correctness) than to verify the correctness of many conventional 20th and 21st century mathematical proofs.

The inevitable future of mathematics is one of complete formalisation of proofs so that computers can do all the correctness checking (using a well-understood verification program). Human mathematicians are far too unreliable. Mathematics cannot afford to rely much longer on informal proofs spread over thousands of pages of textbooks and journal papers that no single person can ever completely verify.

Appel and Haken were not the first to publish a proof of the four-color theorem. The first was published by Kempe in 1879. It took 12 years for it to be shown incorrect. (There exists a short elegant proof of the five-colour theorem. If you understand that proof, you can come up in 15 minutes with a proof of the four-colour theorem. It will then take you 2-3 hours to find the flaw, provided you accept that there is one.) There are probably quite many mathematical theorems that are "known" to be true but that have proofs with as of yet undiscovered flaws.

[syzygy]

A quite funny and provocative opinion:
http://www.math.rutgers.edu/~zeilberg/Opinion53.html

...

So Frank Quinn is probably right, that Steve Ferry's work contains some gaps. But, with probability 1-epsilon, so do all the other papers in this difficult, heavily human, field, including Quinn's own papers, that use human, semi-formal arguments that have not yet been combinatorialized and computerized. In my humble opinion, only combinatorial and computer proofs are truly reliable. I trust the computer-assisted proofs of the Four Color Theorem (and would have trusted them even more had they been fully computer-generated) much more than any human proof in Homology. If such great experts as Quinn and Ferry can't agree between them on what's correct, then this makes their whole field of questionable rigor.

...