Alas, connect 4 has already been solved. Perhaps you mean on a bigger board?but feel free to start with connect 4 to get your feet wet
Solving Chess Kickstarter
Moderators: hgm, Rebel, chrisw
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Solving Chess Kickstarter
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Solving Chess Kickstarter
No, I mean that before you can tackle an unsolved problem, it is a good idea to hone your skills on a problem that has been solved.
8x8 connect-4 is still unsolved, however.
8x8 connect-4 is still unsolved, however.
-
- Posts: 5557
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Solving Chess Kickstarter
Note that the OP is still struggling to finish a basic move generator.Michel wrote:Alas, connect 4 has already been solved. Perhaps you mean on a bigger board?but feel free to start with connect 4 to get your feet wet
Tic-tac-toe is a more realistic goal.I have currently written software to represent a chess position and a chess move. This would be a key component for looking up positions in the database. So this has to be step1.
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.
-
- Posts: 21
- Joined: Wed Jul 13, 2011 5:20 am
Re: Solving Chess Kickstarter
Forgetting all else involved with solving chess, let's agree that to do this we need a database capable of several requirements. I'll list these and then someone please show me the db structure that i am so blissfully unaware of that accomplishes these requirements.
1. Is capable of storing any legally reachable chess position's next move which will lead to a forced mate. So given a position this database could report back the move that will lead to mate, or it will say the position is not forcible.
2. To solve chess we would need to be able to lookup a position to see if it is already analyzed.
3. We need to be able to lookup a position with 100% assurance, no hash collisions acceptible.
4. We cannot relay on a predetermined address for each position, this would require too much storage and not allow for a compact database. Each position needs to be able to be stored in any position, and still be able to be found reliably.
What existing database claims all these? I really want to know.
1. Is capable of storing any legally reachable chess position's next move which will lead to a forced mate. So given a position this database could report back the move that will lead to mate, or it will say the position is not forcible.
2. To solve chess we would need to be able to lookup a position to see if it is already analyzed.
3. We need to be able to lookup a position with 100% assurance, no hash collisions acceptible.
4. We cannot relay on a predetermined address for each position, this would require too much storage and not allow for a compact database. Each position needs to be able to be stored in any position, and still be able to be found reliably.
What existing database claims all these? I really want to know.
-
- Posts: 589
- Joined: Tue Jun 04, 2013 10:15 pm
Re: Solving Chess Kickstarter
Obviously, the number 1 requirement is space. All other requirements are side-show. You have dodged all direct questions regarding space. Not a single estimate or number, only blah blah blah. "thousands of computers", "a lot less than x", blah blah blah. It makes you a fraudster if you continue along that path. The "he is just a bit naive" defence only works for a limited time.DustinYoder wrote:Forgetting all else involved with solving chess, let's agree that to do this we need a database capable of several requirements.
blah blah blah
[Account deleted]
-
- Posts: 97
- Joined: Mon Jun 25, 2012 10:16 pm
- Location: Forks, WA
- Full name: Ben Nye
Re: Solving Chess Kickstarter
Actually, the database isn't the hard part. Figuring out which part of the tree to search is. But I'll focus on the database here since you are doing so
Once you are done, you can just store the tree of moves in a compact format, and traverse it to find the correct move to make.
Once such format would be:
For each white to move position in the tree, store the winning move as a 32 bit int(most chess programs already do that) and then
store the number of black responses as a 16 bit int, then for each of those responses store the disk address of the resulting white
to move position, or 0 if it is a terminal position.
That will work unless you need move than 2^64 wtm positions for the solution tree.
This seems to meet the requirements you listed, and is very simple to use although limited to locating positions based on a list of moves
rather than the resulting position. But during the search each position needs data about the search results to date, not just "has been solved or not",
and more than one white move needs to be considered until the ideal one has been proven, so far more more disk space and complexity will be needed.
Once you are done, you can just store the tree of moves in a compact format, and traverse it to find the correct move to make.
Once such format would be:
For each white to move position in the tree, store the winning move as a 32 bit int(most chess programs already do that) and then
store the number of black responses as a 16 bit int, then for each of those responses store the disk address of the resulting white
to move position, or 0 if it is a terminal position.
That will work unless you need move than 2^64 wtm positions for the solution tree.
This seems to meet the requirements you listed, and is very simple to use although limited to locating positions based on a list of moves
rather than the resulting position. But during the search each position needs data about the search results to date, not just "has been solved or not",
and more than one white move needs to be considered until the ideal one has been proven, so far more more disk space and complexity will be needed.
-
- Posts: 64
- Joined: Thu Feb 19, 2009 5:34 pm
- Location: Mexico, Mexico
Re: Solving Chess Kickstarter
OMG! You really don't realize that your approach is totally unfeasible!DustinYoder wrote:Forgetting all else involved with solving chess, let's agree that to do this we need a database capable of several requirements. I'll list these and then someone please show me the db structure that i am so blissfully unaware of that accomplishes these requirements.
1. Is capable of storing any legally reachable chess position's next move which will lead to a forced mate. So given a position this database could report back the move that will lead to mate, or it will say the position is not forcible.
2. To solve chess we would need to be able to lookup a position to see if it is already analyzed.
3. We need to be able to lookup a position with 100% assurance, no hash collisions acceptible.
4. We cannot relay on a predetermined address for each position, this would require too much storage and not allow for a compact database. Each position needs to be able to be stored in any position, and still be able to be found reliably.
What existing database claims all these? I really want to know.
You should read about the Shannon number http://en.wikipedia.org/wiki/Shannon_number.
It sounds very easy to keep a database of each possible chess position (in fact I thought about it when I was almost a kid) and get the winning move each time.
But don't believe me, just write your move generator, make it to generate every possible move and answer, getting a report each hour or so, and see how much time it takes to advance almost nothing
Let us suppose there are 10e50 positions in chess, and that your program can generate 10 million positions per second, that is 10e7. Then your program would take 10e43 seconds to run, that is 3.2e35 years (that is 35 digits after point), which unfortunately is even more than the life expectancy of our sun, a mere 10 billion of years (10e9)
All good things are difficult to achieve.
Toledo Nanochess book http://www.amazon.com/Toledo-Nanochess- ... 1304864375
Toledo Nanochess book http://www.amazon.com/Toledo-Nanochess- ... 1304864375
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Solving Chess Kickstarter
I don't wish to be mean, but this project is either an outright scam (i.e. to get money via kickstarter from gullible saps) or else the OP literally doesn't understand how unfeasible it is.nanochess wrote:OMG! You really don't realize that your approach is totally unfeasible!DustinYoder wrote:Forgetting all else involved with solving chess, let's agree that to do this we need a database capable of several requirements. I'll list these and then someone please show me the db structure that i am so blissfully unaware of that accomplishes these requirements.
1. Is capable of storing any legally reachable chess position's next move which will lead to a forced mate. So given a position this database could report back the move that will lead to mate, or it will say the position is not forcible.
2. To solve chess we would need to be able to lookup a position to see if it is already analyzed.
3. We need to be able to lookup a position with 100% assurance, no hash collisions acceptible.
4. We cannot relay on a predetermined address for each position, this would require too much storage and not allow for a compact database. Each position needs to be able to be stored in any position, and still be able to be found reliably.
What existing database claims all these? I really want to know.
You should read about the Shannon number http://en.wikipedia.org/wiki/Shannon_number.
It sounds very easy to keep a database of each possible chess position (in fact I thought about it when I was almost a kid) and get the winning move each time.
But don't believe me, just write your move generator, make it to generate every possible move and answer, getting a report each hour or so, and see how much time it takes to advance almost nothing
Let us suppose there are 10e50 positions in chess, and that your program can generate 10 million positions per second, that is 10e7. Then your program would take 10e43 seconds to run, that is 3.2e35 years (that is 35 digits after point), which unfortunately is even more than the life expectancy of our sun, a mere 10 billion of years (10e9)
You could take all of the physical matter in our solar system and rearrange it into massive parallel supercomputing clusters and insane quantities of storage, and it would still be... nowhere near enough to solve this problem before the human race goes extinct.
-
- Posts: 589
- Joined: Tue Jun 04, 2013 10:15 pm
Re: Solving Chess Kickstarter
I'm announcing a kickstarter project to jump over the moon. I need $2000 for the first step: selecting the color of the required trampoline. People have tried without trampoline and failed, therefore I believe that a trampoline is needed.wgarvin wrote:I don't wish to be mean, but this project is either an outright scam (i.e. to get money via kickstarter from gullible saps) or else the OP literally doesn't understand how unfeasible it is.
You could take all of the physical matter in our solar system and rearrange it into massive parallel supercomputing clusters and insane quantities of storage, and it would still be... nowhere near enough to solve this problem before the human race goes extinct.
[Account deleted]
-
- Posts: 10279
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Solving Chess Kickstarter
The project is of course nonsense but I am not sure that it is impossible to solve chess.wgarvin wrote:I don't wish to be mean, but this project is either an outright scam (i.e. to get money via kickstarter from gullible saps) or else the OP literally doesn't understand how unfeasible it is.nanochess wrote:OMG! You really don't realize that your approach is totally unfeasible!DustinYoder wrote:Forgetting all else involved with solving chess, let's agree that to do this we need a database capable of several requirements. I'll list these and then someone please show me the db structure that i am so blissfully unaware of that accomplishes these requirements.
1. Is capable of storing any legally reachable chess position's next move which will lead to a forced mate. So given a position this database could report back the move that will lead to mate, or it will say the position is not forcible.
2. To solve chess we would need to be able to lookup a position to see if it is already analyzed.
3. We need to be able to lookup a position with 100% assurance, no hash collisions acceptible.
4. We cannot relay on a predetermined address for each position, this would require too much storage and not allow for a compact database. Each position needs to be able to be stored in any position, and still be able to be found reliably.
What existing database claims all these? I really want to know.
You should read about the Shannon number http://en.wikipedia.org/wiki/Shannon_number.
It sounds very easy to keep a database of each possible chess position (in fact I thought about it when I was almost a kid) and get the winning move each time.
But don't believe me, just write your move generator, make it to generate every possible move and answer, getting a report each hour or so, and see how much time it takes to advance almost nothing
Let us suppose there are 10e50 positions in chess, and that your program can generate 10 million positions per second, that is 10e7. Then your program would take 10e43 seconds to run, that is 3.2e35 years (that is 35 digits after point), which unfortunately is even more than the life expectancy of our sun, a mere 10 billion of years (10e9)
You could take all of the physical matter in our solar system and rearrange it into massive parallel supercomputing clusters and insane quantities of storage, and it would still be... nowhere near enough to solve this problem before the human race goes extinct.
1)I will not be surprised if in in the future we see a program that is simply unbeatable in years 2040-2050 so even with no proof that chess is a draw it is going to be a convincing evidence that chess is a draw
2)You do not need to know what to do in every legal position
in order to solve chess.
There are positions that you are never going to get with perfect play by one side so there is no need to know what to do in them.
3)It may be possible to have classes of positions and have rules to define the right move in classes of positions so you do not need to memorize what to do in every position that you can reach in order to solve chess.