Solving Chess Kickstarter

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Michel
Posts: 2038
Joined: Sun Sep 28, 2008 11:50 pm

Re: Solving Chess Kickstarter

Post by Michel » Thu Apr 17, 2014 6:46 pm

but feel free to start with connect 4 to get your feet wet
Alas, connect 4 has already been solved. Perhaps you mean on a bigger board?

AlvaroBegue
Posts: 919
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Solving Chess Kickstarter

Post by AlvaroBegue » Thu Apr 17, 2014 6:51 pm

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.

syzygy
Posts: 4447
Joined: Tue Feb 28, 2012 10:56 pm

Re: Solving Chess Kickstarter

Post by syzygy » Thu Apr 17, 2014 10:47 pm

Michel wrote:
but feel free to start with connect 4 to get your feet wet
Alas, connect 4 has already been solved. Perhaps you mean on a bigger board?
Note that the OP is still struggling to finish a basic move generator.
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.
Tic-tac-toe is a more realistic goal.

DustinYoder
Posts: 21
Joined: Wed Jul 13, 2011 3:20 am

Re: Solving Chess Kickstarter

Post by DustinYoder » Sun Apr 20, 2014 3:16 am

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.

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Solving Chess Kickstarter

Post by mvk » Sun Apr 20, 2014 5:39 am

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
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.
[Account deleted]

Angrim
Posts: 62
Joined: Mon Jun 25, 2012 8:16 pm
Location: Missoula, MT

Re: Solving Chess Kickstarter

Post by Angrim » Sun Apr 20, 2014 7:50 am

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.

User avatar
nanochess
Posts: 64
Joined: Thu Feb 19, 2009 4:34 pm
Location: Mexico, Mexico
Contact:

Re: Solving Chess Kickstarter

Post by nanochess » Tue Apr 22, 2014 7:55 pm

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.
OMG! You really don't realize that your approach is totally unfeasible!

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

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Solving Chess Kickstarter

Post by wgarvin » Tue Apr 22, 2014 9:04 pm

nanochess wrote:
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.
OMG! You really don't realize that your approach is totally unfeasible!

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)
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.

mvk
Posts: 589
Joined: Tue Jun 04, 2013 8:15 pm

Re: Solving Chess Kickstarter

Post by mvk » Sat Apr 26, 2014 3:27 pm

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.
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.
[Account deleted]

Uri Blass
Posts: 8530
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Solving Chess Kickstarter

Post by Uri Blass » Sat Apr 26, 2014 4:33 pm

wgarvin wrote:
nanochess wrote:
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.
OMG! You really don't realize that your approach is totally unfeasible!

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)
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.
The project is of course nonsense but I am not sure that it is impossible to solve chess.

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.

Post Reply