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
Farkov
Posts: 6
Joined: Fri Nov 08, 2013 10:35 am

Re: Solving Chess Kickstarter

Post by Farkov » Fri Apr 04, 2014 9:00 am

Angrim wrote:
syzygy wrote:
If you can solve the above problems maybe you'll want to have a crack at solving Suicide Chess which, although an almighty task, is next on the list of "solvable chess variants that aren't completely contrived". This might, although it's unlikely, be possible to solve once 6-man tablebases are generated.
I have most of the 5v1 but still many many to go and I have stopped the generation for the moment to do some other things. I'll finish them eventually.

I'm afraid they won't suffice to solve the game, but who knows.
An interesting experiment is to temporarily add code to your tablebase probe function that returns "white wins" whenever it probes a 6 piece table. Then search some of the interesting unsolved lines and see if the modified version returns a win. If not, the 6 piece tables won't solve that line. Then assuming that no win shows up from that, change it to probe and return "white wins" for all 7 piece positions, which will give an upper bound on how many lines will be solvable once the 7 piece tables are done.
Since hard drive sizes seem to have stagnated at 2TB, I don't expect 7 piece suicide egtb to be practical anytime soon. But it's still interesting to have some idea of what would be possible if they were.
To be honest, I never really considered hard drive capacity to be the achilles heel of suicide tablebases. I say this because if one has the patience to code them properly, and the 1000 years to generate them, then one would probably invest in some sort of array of disks :)

Also, one would presumably use bitbases when solving and fill in the blanks later.

On that note, have you guys seen how cheap it is to set up something decent with 64GB of RAM these days? :)

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

Re: Solving Chess Kickstarter

Post by syzygy » Fri Apr 04, 2014 8:43 pm

Angrim wrote:An interesting experiment is to temporarily add code to your tablebase probe function that returns "white wins" whenever it probes a 6 piece table. Then search some of the interesting unsolved lines and see if the modified version returns a win. If not, the 6 piece tables won't solve that line.
Nice idea. I have just "temporarily" solved e3 e6 :-)
Funny enough it was about 2x as easy as solving e3 a6 with the same modification.

Code: Select all

1.e3 e6? 2.b4! Bxb4? 3.Qg4! Bxd2? 4.Qxg7! Bxe3? 5.Bxe3! c5? 6.Bxc5! Qg5? 7.Qxh7! 
           6...b6? 7.Bxb6! Qxb6? 8.Qxh8! Qxb1? 9.Qxg8! Qxc2? 10.Qxe8! Qxf2? 11.Kxf2! a5? 12.Qxf7! Ba6? 13.Bxa6! 
               8...Qxf2? 9.Qxg8!
I'm now searching the initial position.

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

Re: Solving Chess Kickstarter

Post by Angrim » Fri Apr 04, 2014 9:26 pm

rreagan wrote:
Angrim wrote: Since hard drive sizes seem to have stagnated at 2TB...
You can buy 4 TB hard drives in any computer store. Much larger drives are on the way.

http://en.wikipedia.org/wiki/History_of ... s#Timeline
Good to see that some progress is being made. It just seems that the drives sold in stores around here have been from 500gig to 2tb for several years now.
If those 60tb drives actually make it into stores in a few more years, that will have interesting results for tablebases.

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

Re: Solving Chess Kickstarter

Post by syzygy » Sat Apr 05, 2014 10:50 am

syzygy wrote:I'm now searching the initial position.
e3 wins :D

The first 11 plies of the tree:

Code: Select all

1.e3! a5? 2.Ba6! bxa6? 3.Na3! c6? 4.d3! g5? 5.b4! 
       4...f6? 5.h4! 
   2...Rxa6? 3.b4! axb4? 4.Qf3! Rxa2? 5.Qxb7! Rxc2? 6.Qxb4! 
 1...b5? 2.Bxb5! Bb7? 3.Bxd7! Bxg2? 4.Bxe8! Bxh1? 5.Bxf7! Qxd2? 6.Kxd2! 
       4...Qxd2? 5.Kxd2! Bxh1? 6.Bxf7! 
   2...c5? 3.Bxd7! Nxd7? 4.c4! a5? 5.Qh5! 
       4...e6? 5.h4! Qxh4? 6.Rxh4! 
     3...Kxd7? 4.Nc3! Qa5? 5.Qg4! Qxa2? 6.Nxa2! 
       4...c4? 5.b4! cxb3? 6.axb3! 
   2...Ba6? 3.Bxd7! Nxd7? 4.d3! Bxd3? 5.Qxd3! Qc8? 6.Qxh7! 
         5...Qb8? 6.Qxh7! 
         5...Rc8? 6.Qxh7! 
         5...h5? 6.Qxd7! 
         5...Rb8? 6.Qxh7! 
         5...c6? 6.Qxh7! 
         5...f6? 6.Qxh7! 
         5...g6? 6.Qxg6! 
         5...h6? 6.Qxd7! 
         5...Nh6? 6.Qxh7! 
         5...Nb6? 6.Qxh7! 
         5...Nb8? 6.Qxh7! 
         5...Ngf6? 6.Qxh7! 
     3...Qxd7? 4.c4! Bxc4? 5.Qc2! 
   2...f5? 3.Bxd7! Kxd7? 4.Ne2! Qe8? 5.e4! fxe4? 6.Nd4! 
       4...c6? 5.g4! fxg4? 6.f3! 
   2...g5? 3.Bxd7! Nxd7? 4.Qh5! Ne5? 5.Qxh7! Rxh7? 6.f4! 
     3...Kxd7? 4.Qh5! Bh6? 5.Qxf7! g4? 6.Qxg8! 
       4...Nh6? 5.Qxf7! Nxf7? 6.e4! 
       4...Nf6? 5.Qxh7! Nxh7? 6.Nf3! 
       4...g4? 5.Qxh7! Rxh7? 6.g3! 
       4...c6? 5.Qxh7! Rxh7? 6.Nc3! 
   2...h5? 3.Bxd7! Qxd7? 4.Qxh5! Rxh5? 5.c4! Rxh2? 6.Rxh2! 
         5...Qxd2? 6.Bxd2! 
     3...Kxd7? 4.Qxh5! Rxh5? 5.e4! Rxh2? 6.Rxh2! 
   2...Nh6? 3.Bxd7! Nxd7? 4.e4! Nb8? 5.h4! Qxd2? 6.Bxd2! 
       4...Nf5? 5.exf5! Ba6? 6.c4! 
         5...f6? 6.Nf3! 
       4...Ng4? 5.Qxg4! g5? 6.Qxd7! 
       4...f5? 5.exf5! Nxf5? 6.Qh5! 
       4...f6? 5.e5! Nxe5? 6.c4! 
     3...Bxd7? 4.h3! Bxh3? 5.Rxh3! Qxd2? 6.Rxh6! 
     3...Qxd7? 4.Qh5! Qxd2? 5.Bxd2! Bh3? 6.Nxh3! 
     3...Kxd7? 4.Nc3! Qe8? 5.Qg4! 
       4...Rg8? 5.Qh5! Rh8? 6.Qxf7! 
         5...Ng4? 6.Qxf7! 
         5...c6? 6.Qxh6! 
       4...Ng8? 5.Qe2! h5? 6.Qxh5! 
       4...Ng4? 5.Qxg4! Qe8? 6.Qxd7! 
         5...Rg8? 6.Qxg7! 
         5...h6? 6.Qxd7! 
         5...g5? 6.Qxd7! 
         5...g6? 6.Qxd7! 
       4...g6? 5.Qh5! gxh5? 6.Nh3! 
   2...c6? 3.Bxc6! Nxc6? 4.b4! Nxb4? 5.a4! Nxc2? 6.Qxc2! 
   2...e6? 3.Bxd7! 
   2...f6? 3.Bxd7! Kxd7? 4.Qe2! a5? 5.b4! axb4? 6.c4! 
       4...c5? 5.Qa6! Nxa6? 6.Nc3! 
       4...Qe8? 5.Qh5! Qxh5? 6.g3! 
       4...Ba6? 5.Qxa6! Nxa6? 6.b4! 
   2...g6? 3.Bxd7! Kxd7? 4.Qh5! gxh5? 5.g4! hxg4? 6.Nf3! 
   2...h6? 3.Bxd7! Kxd7? 4.Nh3! 
 1...c5? 2.b4! cxb4? 3.Ba6! bxa6? 4.Ba3! bxa3? 5.Nxa3! Qc7? 6.Qf3! 
         5...f5? 6.Nb5! 
         5...g5? 6.Nb5! 
         5...h5? 6.Qxh5! 
         5...a5? 6.Nf3! 
         5...d6? 6.Nf3! 
         5...f6? 6.Nb5! 
         5...g6? 6.Qh5! 
         5...h6? 6.Nh3! 
         5...Nh6? 6.Ke2! 
     3...Nxa6? 4.d3! b5? 5.Nc3! bxc3? 6.Bb2! 
       4...Qc7? 5.Qf3! Qxc2? 6.Qxb7! 
       4...Qa5? 5.Qf3! Qxa2? 6.Qxb7! 
       4...Rb8? 5.Nc3! bxc3? 6.Bb2! 
       4...Nh6? 5.Nc3! bxc3? 6.Bb2! 
       4...b3? 5.cxb3! b6? 6.Qg4! 
         5...Nc7? 6.b4! 
         5...Nb8? 6.Bd2! 
         5...Qa5? 6.Qf3! 
       4...b6? 5.Nc3! 
 1...e5? 2.Ba6! bxa6? 3.a3! Bxa3? 4.Nxa3! Qg5? 5.Ne2! 
 1...f5? 2.e4! 
 1...g5? 2.Qh5! a5? 3.Qxh7! Rxh7? 4.Ba6! 
   2...b5? 3.Bxb5! Nh6? 4.Bxd7! Kxd7? 5.Qxf7! Nxf7? 6.e4! 
     3...c5? 4.Bxd7! 
     3...Nf6? 4.Qxh7! Nxh7? 5.Bxd7! Nxd7? 6.c4! 
         5...Kxd7? 6.Nf3! 
     3...g4? 4.Bxd7! Kxd7? 5.Qxh7! Rxh7? 6.g3! 
   2...c5? 3.Qxh7! Rxh7? 4.Ba6! bxa6? 5.e4! 
       4...Rxh2? 5.Rxh2! bxa6? 6.b4! 
   2...Bg7? 3.Qxh7! Bxb2? 4.Bxb2! Rxh7? 5.Bf6! exf6? 6.h4! 
         5...Rxh2? 6.Rxh2! 
   2...g4? 3.Qxh7! Rxh7? 4.Ba6! bxa6? 5.g3! Rxh2? 6.Rxh2! 
       4...Nxa6? 5.g3! Rxh2? 6.Rxh2! 
       4...Rxh2? 5.Rxh2! bxa6? 6.g3! 
         5...Nxa6? 6.g3! 
   2...Nh6? 3.Qxh6! Bxh6? 4.f4! gxf4? 5.exf4! Bxf4? 6.Bd3! 
   2...c6? 3.Qxh7! Rxh7? 4.e4! 
 1...h5? 2.Qxh5! Rxh5? 3.Ba6! bxa6? 4.Nc3! Rxh2? 5.Rxh2! g6? 6.Rh5! 
         5...c6? 6.Kd1! 
     3...Nxa6? 4.b4! Nxb4? 5.a4! Nxc2? 6.e4! 
         5...Rxh2? 6.Rxh2! 
       4...Rxh2? 5.Rxh2! Nxb4? 6.a4! 
     3...Rxh2? 4.Rxh2! bxa6? 5.Nc3! g6? 6.Rh5! 
         5...c6? 6.Kd1! 
       4...Nxa6? 5.b4! Nxb4? 6.a4! 
 1...a6? 2.Bxa6! bxa6? 3.Qg4! g5? 4.Qxd7! Nxd7? 5.Na3! c6? 6.c4! 
       4...Kxd7? 5.Nc3! 
     3...g6? 4.Qxd7! Kxd7? 5.Nc3! c6? 6.Kd1! 
 1...b6? 2.Ba6! Nxa6? 3.Qh5! c5? 4.Qxh7! Rxh7? 5.h3! Rxh3? 6.Rxh3! 
     3...Nh6? 4.Qxh6! gxh6? 5.b4! Nxb4? 6.a4! 
     3...c6? 4.Qxh7! Rxh7? 5.Nc3! Rxh2? 6.Rxh2! 
     3...Nb8? 4.Qxh7! Rxh7? 5.Nc3! Rxh2? 6.Rxh2! 
     3...h6? 4.Qxf7! Kxf7? 5.b4! 
     3...Nb4? 4.Qxh7! Nxc2? 5.Qxg7! 
     3...Nc5? 4.Qxh7! Rxh7? 5.e4! Nxe4? 6.Kd1! 
 1...c6? 2.Bb5! cxb5? 3.b4! Qc7? 4.Qh5! 
     3...Qa5? 4.bxa5! Na6? 5.Nh3! Nh6? 6.Ng5! 
         5...b4? 6.Qg4! 
       4...a6? 5.Qh5! b4? 6.Qxf7! 
       4...b4? 5.a4! bxa3? 6.Nxa3! 
       4...h5? 5.Qxh5! Rxh5? 6.Kd1! 
     3...g5? 4.Qh5! Qa5? 5.bxa5! h6? 6.Qxg5! 
       4...h6? 5.Qxg5! hxg5? 6.h3! 
     3...h6? 4.Nh3! f6? 5.Qf3! Qc7? 6.Qxb7! 
     3...g6? 4.c4! bxc4? 5.Qh5! gxh5? 6.d4! 
     3...b6? 4.Nf3! a5? 5.bxa5! bxa5? 6.Ng5! 
       4...e5? 5.Nxe5! Bxb4? 6.Nxf7! 
       4...g5? 5.Nxg5! Qc7? 6.Nxf7! 
       4...Ba6? 5.Ne5! g5? 6.Nxf7! 
       4...g6? 5.d4! g5? 6.Nxg5! 
     3...f6? 4.Nf3! h6? 5.Ne5! 
 1...e6? 2.b4! Bxb4? 3.Qg4! Bxd2? 4.Qxg7! Bxe3? 5.Bxe3! c5? 6.Bxc5! 
 1...f6? 2.Ba6! bxa6? 3.Nf3! c5? 4.b4! cxb4? 5.Ne5! fxe5? 6.a4! 
     3...g5? 4.Nxg5! fxg5? 5.Qh5! Bh6? 6.Qxe8! 
         5...Nh6? 6.Qxh6! 
         5...Nf6? 6.Qxh7! 
     3...c6? 4.Nc3! h6? 5.a4! Qa5? 6.Ng5! 
     3...g6? 4.Nd4! 
     3...Nh6? 4.Ne5! fxe5? 5.e4! c6? 6.Qh5! 
 1...g6? 2.Ba6! bxa6? 3.Qh5! gxh5? 4.g4! hxg4? 5.Nf3! 
 1...h6? 2.Ba6! bxa6? 3.Nh3! h5? 4.Qxh5! Rxh5? 5.g3! Rxh3? 6.Nc3! 
     3...f6? 4.Ng5! 
 1...Nh6? 2.Qg4! Nxg4? 3.Bd3! Nxf2? 4.Bxh7! Rxh7? 5.Kxf2! Rxh2? 6.Rxh2! 
     3...Nxe3? 4.Bxh7! Nxc2? 5.Bxc2! Rxh2? 6.Rxh2! 
       4...Rxh7? 5.dxe3! Rxh2? 6.Rxh2! 
 1...Nc6? 2.Ba6! bxa6? 3.b4! Nxb4? 4.Na3! Nxa2? 5.Rxa2! a5? 6.Qg4! 
         5...Rb8? 6.Qh5! 
       4...Nxc2? 5.Nxc2! c5? 6.Nh3! 
         5...c6? 6.a4! 
         5...a5? 6.a4! 
 1...Nf6? 2.Ba6! bxa6? 3.e4! Nxe4? 4.Qh5! Nxf2? 5.Qxh7! Rxh7? 6.Kxf2!
So this is assuming that all 6-piece positions are won for white (except for those without black pieces and those in which white has a bishop it can't get rid of anymore), which obviously is not a correct assumption.

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

Re: Solving Chess Kickstarter

Post by Angrim » Sat Apr 05, 2014 5:53 pm

cool. This discussion has been bumping my own efforts to do the 6 piece tables up a little on my todo list, although it will still be quite a while since the rest of my life is keeping pretty busy lately.

Vladimir Xern
Posts: 39
Joined: Wed Mar 08, 2006 7:30 pm

Re: Solving Chess Kickstarter

Post by Vladimir Xern » Sun Apr 13, 2014 11:48 pm

Hi, Ronald and Ben. This is way off-topic, but it's really great to see you two posting here.

I know the fervor around suicide chess has died down a lot and you guys have redirected most of your focus to other things, but have you been keeping up with the academic developments to PN search?

Df-pn and its progeny, for example, have shown promise, including several recent reasonably successful attempts at parallelization. I'm not sure about their amenability to suicide chess, however, and from these last few posts it sounds like the endgame tablebases may be the final bottleneck in the end.

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

Re: Solving Chess Kickstarter

Post by Angrim » Tue Apr 15, 2014 6:51 am

Vladimir Xern wrote:Hi, Ronald and Ben. This is way off-topic, but it's really great to see you two posting here.

I know the fervor around suicide chess has died down a lot and you guys have redirected most of your focus to other things, but have you been keeping up with the academic developments to PN search?

Df-pn and its progeny, for example, have shown promise, including several recent reasonably successful attempts at parallelization. I'm not sure about their amenability to suicide chess, however, and from these last few posts it sounds like the endgame tablebases may be the final bottleneck in the end.
I haven't really paid attention to search in quite a while, what little time I have had for suicide chess has mostly been spent on trying to finish the rewrite of my opening book code. Once that's done, I'll evaluate what part of my engine is currently the weakest link and switch focus to that.

I just spent half an hour reading up on the newer pn-related stuff, and I don't see a large improvement over pn^2. Most of the improvements are to reduce memory usage, and I did multi-week searches with pn^2 without running out of ram. And that was back when a gig of ram was a major investment :)

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

Re: Solving Chess Kickstarter

Post by DustinYoder » Wed Apr 16, 2014 6:40 pm

More details about the database included in the FAQ section of the kickstarter.com page. Please take a look to see if this helps people understand the project.

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 » Wed Apr 16, 2014 6:46 pm

DustinYoder wrote:More details about the database included in the FAQ section of the kickstarter.com page. Please take a look to see if this helps people understand the project.
I think you are the one who doesn't understand. Solve a "small" problem first (someone proposed suicide chess in this thread, which I think is a great idea, but feel free to start with connect 4 to get your feet wet). You will then have a much larger sense of how difficult the problem really is.

I am sorry if I am feeding the troll.

User avatar
hgm
Posts: 23610
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Solving Chess Kickstarter

Post by hgm » Wed Apr 16, 2014 7:42 pm

The point of course is that he does not intend to solve anything. Just produce some general stuff that every engine author already knows how to do.

Post Reply