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.
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 May 21, 2014 8:40 pm

duncan wrote:what about going a bit further and saying the combination of black to move gives it a positional advantage and combined with strong material advantage means black cannot lose and white will not win.
does one need exhaustive analysis to prove this. ?
Well, you need to prove it, however you want. But you don't get to just state it hoping others will say "yeah, that sounds about right".

bob
Posts: 20474
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Solving Chess Kickstarter

Post by bob » Wed May 21, 2014 9:41 pm

duncan wrote:
bob wrote:
duncan wrote:
Brunetti wrote:Duncan's position _is_ a certain win, I don't think it's necessary to prove it by brute force, we don't need a scientific proof for obvious facts like that. E.g., there's no need for TB's (or other exhaustive analysis) to assess K+R vs K, or KRR vs KP, KQRR vs KPP and so on.
The Qh5 example is different, I agree.

Alex
does one need exhaustive analysis to assess this position ?

[d]rnbqkb1r/pppppppp/8/8/8/8/PPPPPPPP/4K3 b kq - 0 1
Do you need a formal proof, or exhaustive proof to show that

sin^2(x) + cos^2(x) = 1?

Or can you just try a few values and see if it works?

the word "proof" is pretty well-defined. intuitive observation is not good enough. Most would agree with your position above being won for black. But that still isn't a "proof".

what about going a bit further and saying the combination of black to move gives it a positional advantage and combined with strong material advantage means black cannot lose and white will not win.
does one need exhaustive analysis to prove this. ?
Yes. Otherwise it is not a "proof" just a reasonable conjecture.

As far as "black to move" no one knows whether the initial chess position is a zugzwang position or not. Might be that whomever moves first loses for all we know at present.

bob
Posts: 20474
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Solving Chess Kickstarter

Post by bob » Wed May 21, 2014 9:58 pm

duncan wrote:
bob wrote:
duncan wrote:
bob wrote:

First, as far as the queen goes, it is likely a loss. But until it is proven, it is just an assumption. As to any advantage for white/black, I don't think that would be the issue. If anything, it would be black's knight ending up at h5 probably.
I meant what would be black's advantage to win in this position ?

[d]rnb1kbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

wrote: In Crafty, for example, reductions, pruning and null-move can be disabled by the user if wanted. It will be very slow to reach any reasonable depth, however.
how would do you do it with crafty in winboard?


step one: start crafty in a normal console window

type "personality list"


Now look at the output. You want to find all terms that apply to any of this selectiveness. For example:

2 null-move reduction 3

to your .craftyrc or crafty.rc file, add the following

personality 2 0

which changes item 2 to zero. Repeat for the other selective terms such as

pers 4 0
pers 5 0 {these disable LMR}

pers 6 0 {disables forward pruning}


Now you have a very accurate searcher, but a very slow one as far as reaching significant depth goes.
thanks for that

duncan
Just tested the above and it works. Just verify those line numbers as I am using version 24.0, which I think is about ready to release. With the above commands, it will be dog slow. Normally it solves wac2 at depth 17 in under .2 secs using one core on my macbook. With the above, it took almost 7 seconds at depth=13... back to the 1990's even with today's hardware. :)

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

Re: Solving Chess Kickstarter

Post by syzygy » Fri Aug 22, 2014 8:55 pm

Angrim wrote: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.
By now we also know that 6-piece tables (and a lot of computation) suffice to solve 1.e3 e6 as winning for white.

The only responses left for black are 1...b6 and 2...c5.

http://magma.maths.usyd.edu.au/~watkins/LOSING_CHESS/

User avatar
Brunetti
Posts: 112
Joined: Tue Dec 08, 2009 12:37 pm
Location: Milan, Italy
Contact:

Re: Solving Chess Kickstarter

Post by Brunetti » Fri Aug 22, 2014 9:03 pm

syzygy wrote:By now we also know that 6-piece tables (and a lot of computation) suffice to solve 1.e3 e6 as winning for white.
Losing chess is computationally *far* less complex than chess :)

Alex

User avatar
vittyvirus
Posts: 645
Joined: Wed Jun 18, 2014 12:30 pm
Full name: Fahad Syed

Re: Solving Chess Kickstarter

Post by vittyvirus » Fri Aug 29, 2014 11:15 am

Why does the CC community show such a little interest in solving chess? I'm not talking about this guys project, but solving chess in general.

Roger Brown
Posts: 782
Joined: Wed Mar 08, 2006 8:22 pm

Re: Solving Chess Kickstarter

Post by Roger Brown » Fri Aug 29, 2014 1:20 pm

syzygy wrote: By now we also know that 6-piece tables (and a lot of computation) suffice to solve 1.e3 e6 as winning for white.

The only responses left for black are 1...b6 and 2...c5.

http://magma.maths.usyd.edu.au/~watkins/LOSING_CHESS/
Hello Ronald,

I see that you were credited as the person who did the hard work. Would you mind saying what is that you did? As in, what is the solver engine referred to? What constitutes a lot of computation? Has a paper been written? I just find it surprising - and a little scary - that a game can be decided on the basis of the first opening move.

There is a joke that after e4 the game is lost.

I guess I did not know that the state of technology was anywhere near to making that call.

Later.

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

Re: Solving Chess Kickstarter

Post by Angrim » Fri Aug 29, 2014 2:26 pm

Roger Brown wrote:
syzygy wrote: By now we also know that 6-piece tables (and a lot of computation) suffice to solve 1.e3 e6 as winning for white.

The only responses left for black are 1...b6 and 2...c5.

http://magma.maths.usyd.edu.au/~watkins/LOSING_CHESS/
Hello Ronald,

I see that you were credited as the person who did the hard work. Would you mind saying what is that you did? As in, what is the solver engine referred to? What constitutes a lot of computation? Has a paper been written? I just find it surprising - and a little scary - that a game can be decided on the basis of the first opening move.

There is a joke that after e4 the game is lost.

I guess I did not know that the state of technology was anywhere near to making that call.

Later.
This is suicide chess that is being discussed at this point in the thread, which tends to have very narrow playable lines.
1. e4 is indeed a known loss in suicide, as are quite a few other opening moves. Proving equivalent things for regular chess will be orders of magnitude harder.
If you follow that link that you quoted, you will find that Mark Watkins did most of the recent work, he has been using a quite impressive amount of hardware to advance the state of the suicide chess opening knowledge.
He is using pn^2 with partial transposition support, which is roughly the same technology that several of us have been using for the last decade to prove suicide opening lines.
The part that Ronald added is the use of 6 piece endgame tables, which were needed to solve one deep line in the proof. I suspect they would have speeded up several other lines quite a bit, and will be a significant help in the future.
This tech will also work for proving chess positions, but it will take a whole lot longer for the really interesting positions.

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

Re: Solving Chess Kickstarter

Post by syzygy » Fri Aug 29, 2014 7:39 pm

Roger Brown wrote:I see that you were credited as the person who did the hard work. Would you mind saying what is that you did?
So this is about suicide chess / losing chess / giveaway chess. (Captures are forced, the goal is to lose all your pieces, kings are regular pieces i.e. no castling and pawns can promote to king.)

I only did a very minor part of the work. Mark managed to solve 1.e3 e6 except for one line that he thought needed certain 7-piece tablebases. I ran my pn^2 solver on this line using the 6-piece suicide chess tablebases I have generated (I only had most of the 5v1 tables, but the 7-piece tables he needed were 6v1 so 5v1 seemed close enough to give it a try). The line turned out to be solvable overnight, so there was no need to generate those 7-piece tablebases. Mark then generated some of the 6-piece tablebases himself and finished his proof. He would certainly have solved it without my help, but of course knowing where to go saves time.
As in, what is the solver engine referred to?
https://chessprogramming.wikispaces.com ... ber+search
What constitutes a lot of computation?
Many months, but it seems most of the time was spent on lines that - in hindsight - were not the most promising.
Has a paper been written?
I suppose Mark will do this if he finishes the remaining lines.
I just find it surprising - and a little scary - that a game can be decided on the basis of the first opening move.
For suicide chess this is not so surprising.
There is a joke that after e4 the game is lost.
In suicide chess the game is trivially lost after 1.e4. Many other moves are known to lose as well. 1.e3 seems to be best for white and seems likely to be winning (but it's too early to tell).

A considerable amount of opening theory can be browsed here:
http://catalin.francu.com/nilatac/book.php

It does not have the wins for 1.e3 g5/b5/e6 yet.

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

Re: Solving Chess Kickstarter

Post by syzygy » Fri Aug 29, 2014 7:48 pm

vittyvirus wrote:Why does the CC community show such a little interest in solving chess? I'm not talking about this guys project, but solving chess in general.
Because once you get a good grasp of the size of the problem (i.e. weakly solving regular chess from the opening position), you realise that it cannot be done with current technology.

But it is interesting that a (different) game that uses the same board and pieces that move in the same way is within reach. Suicide chess even has far and far more legal positions than normal chess. But it has a far smaller branching factor.

Post Reply