Solving Chess Kickstarter

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Solving Chess Kickstarter

Post by Edmund » Sun Mar 23, 2014 1:29 pm

Henk wrote:Maybe one could store records of dedicated algorithms that generate many winning positions.
I recall Daniel Shawul experimented for his bitbases with something similar. He tried using chess knowledge to predict outcome and with this information improve compression. He mentioned that for more number of pieces the gain drops substantially.

Stan Arts
Posts: 179
Joined: Fri Feb 14, 2014 9:53 pm
Location: the Netherlands

Re: Solving Chess Kickstarter

Post by Stan Arts » Sun Mar 23, 2014 1:31 pm

ZirconiumX wrote:
I won't put the whole output on this page, but according to the program, there are:
3837824955509396206205398894933217531649406893072749958129150771163299840000000 positions in a 32 man database
Yea thought that number looked vaguely familiar and then it hit me. Remember running my program overnight once. Waking up and it had like, a huge number of nodes exactly like that. Maybe a bit more. It showed 0.00. Threw away the log and the version. Seemed like a bad version. Oh well.

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Solving Chess Kickstarter

Post by Sven » Sun Mar 23, 2014 1:45 pm

Stan Arts wrote:
ZirconiumX wrote:
I won't put the whole output on this page, but according to the program, there are:
3837824955509396206205398894933217531649406893072749958129150771163299840000000 positions in a 32 man database
Yea thought that number looked vaguely familiar and then it hit me. Remember running my program overnight once. Waking up and it had like, a huge number of nodes exactly like that. Maybe a bit more. It showed 0.00. Threw away the log and the version. Seemed like a bad version. Oh well.
An overview of the "number of unique legal chess positions" as far as known today can be found here, including a definition of the term. According to those numbers I think we can extrapolate and define at least an upper bound of 10^63 (maybe much less but still a huge number) for the number of unique legal 32-men positions.

Maybe the OP should start to implement his algorithm and test it with, say, 1000 different random legal 8-men positions (excluding those with material advantage of black) to find out how long it takes to find the perfect outcome (white win or draw). Maybe just start with one position ... Then go to 9-men, 10-men, ...

Sven

Pio
Posts: 119
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Solving Chess Kickstarter

Post by Pio » Sun Mar 23, 2014 2:49 pm

Hi Sven!

An upper bound is 10^58 as can be seen from my board representation here
http://www.talkchess.com/forum/viewtopi ... 93&t=49575

Of course you could reduce it even more.

/Pio

Daniel Shawul
Posts: 3749
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Solving Chess Kickstarter

Post by Daniel Shawul » Sun Mar 23, 2014 3:30 pm

'Kickstarter' LOL.

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

Re: Solving Chess Kickstarter

Post by syzygy » Sun Mar 23, 2014 3:57 pm

The OP will not be dissuaded by these huge numbers, as he does not plan to make a tablebase with all positions. His plan is just to store the winning moves of a proof tree.

Checkers has about 5 x 10^20 positions. The proof (showing the game to be a draw) consists of the following components:
- endgame databases covering 3.9 x 10^13 positions (237 GB of disk space);
- a proof tree of 10^7 positions;
- a solver program that is able to solve each leaf position of the proof with the help of the endgame databases in a relatively short time.

Constructing a database for 5 x 10^20 positions would be a hopeless task, but the proof fits on a rather modest PC.

It is rather difficult to convince someone who clearly has no feeling for the complexity of chess that a similar strategy is not going to work.

User avatar
JVMerlino
Posts: 1003
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Solving Chess Kickstarter

Post by JVMerlino » Sun Mar 23, 2014 4:02 pm

Ok. Who pledged $250 so they could get access to the source? :roll:

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 » Mon Mar 24, 2014 2:42 am

John Tromp reduced it to under 10^46. See http://homepages.cwi.nl/~tromp/chess/chess.html

He also told me he generated 10 random positions within the set he counted, and none of the positions were actually achievable. So it is likely the true number of unique positions is several orders of magnitude smaller.

Going back to the subject of the thread, I don't see why anyone would sponsor the hobby of someone who hasn't demonstrated the ability to solve any game. Show me a program that can solve Connect-4 in seconds or minutes and I'll start to read your ideas about how to solve chess. The only person I know who has made such a program is again John Tromp, and he knows perfectly well that solving chess is hopeless.

User avatar
lucasart
Posts: 3038
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Solving Chess Kickstarter

Post by lucasart » Mon Mar 24, 2014 3:03 am

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 ... tep-1-of-3 I would request comments and advice on other outlets who might be interested in this project.
I'm very surprised that our moderators have still not taken action against this scam:
* He's claiming to be building a 32-men TB, which is nothing but a farce.
* He's asking for money, and in particular you need to give him 250$ in order to get access to his source code, only to find out that it's a scam (if you're naive enough not to realize straight away).

Apparently, someone already did send 250$. Or maybe it's a scam technique. No one sent anything, but he's just putting that on his website to attract idiots to pay. The trick is to make the idiot think he's not the only idiot. Otherwise the idiot becomes suspicious...

Normally, you buy a product. Here there is no product. It is the difference between a scam and a commercial offer.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Angrim
Posts: 69
Joined: Mon Jun 25, 2012 8:16 pm
Location: Forks, WA
Full name: Ben Nye

Re: Solving Chess Kickstarter

Post by Angrim » Mon Mar 24, 2014 4:07 am

I think before you try to solve chess with an exhaustive search method like this, you should try solving one of the chess variants that has similar moves
but a much narrower playable opening game tree. Suicide chess and Atomic chess would be good examples, I have put some effort into solving
both of those games, and can say with great confidence that they are easier to solve than chess would be, by at least an order of magnitude.
Once you have solved a game with a narrow branching factor like those, you could work on extending your methods to work on something harder like chess.
Also, it would amuse me, which is of course a wonderful and worthy goal in it's own right.

Post Reply