Solving Chess Kickstarter
Moderators: bob, hgm, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

 Posts: 21
 Joined: Wed Jul 13, 2011 3:20 am
Solving Chess Kickstarter
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 ... tep1of3 I would request comments and advice on other outlets who might be interested in this project.

 Posts: 3826
 Joined: Thu May 15, 2008 7:57 pm
 Location: Berlin, Germany
 Full name: Sven Schüle
 Contact:
Re: Solving Chess Kickstarter
Hi Dustin,
may I just ask one question:
How many chess programs have you written so far?
Sven
may I just ask one question:
How many chess programs have you written so far?
Sven
Re: Solving Chess Kickstarter
He almost has a move generator, he thinks.Sven Schüle wrote:How many chess programs have you written so far?
Re: Solving Chess Kickstarter
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.
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.
Re: Solving Chess Kickstarter
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.DustinYoder wrote: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 ... tep1of3 I would request comments and advice on other outlets who might be interested in this project.
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?
[Account deleted]
Re: Solving Chess Kickstarter
It's always nice if you get payed for the time you spend on your hobby,
Re: Solving Chess Kickstarter
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 fourcolor 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?
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 fourcolor 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?
Re: Solving Chess Kickstarter
This paragraph of the Kickstarter is hilarious:
I admire your ambitiousness but throwing money at this project is just about hopeless.
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 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.
I admire your ambitiousness but throwing money at this project is just about hopeless.
Re: Solving Chess Kickstarter
If you mean a concise, clever and elegant proof that white wins, obviously you can forget it.ambrooks1 wrote: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.
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.
With the 4color 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.For example, even when the worlds' best mathematicians came up with a proof of the fourcolor 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.
The inevitable future of mathematics is one of complete formalisation of proofs so that computers can do all the correctness checking (using a wellunderstood 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 fourcolor 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 fivecolour theorem. If you understand that proof, you can come up in 15 minutes with a proof of the fourcolour theorem. It will then take you 23 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.
Re: Solving Chess Kickstarter
A quite funny and provocative opinion:
http://www.math.rutgers.edu/~zeilberg/Opinion53.html
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 1epsilon, so do all the other papers in this difficult, heavily human, field, including Quinn's own papers, that use human, semiformal arguments that have not yet been combinatorialized and computerized. In my humble opinion, only combinatorial and computer proofs are truly reliable. I trust the computerassisted proofs of the Four Color Theorem (and would have trusted them even more had they been fully computergenerated) 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.
...