Solving Chess

[maxpower1227]

For the two bishops on the same colour, I disagree. You could have the second bishop on the same colour as the first one if you promoted a pawn to a bishop. Technically it would not be an illegal position. But having a pawn on the first rank definitely gives rise to an illegal position.

nimzo

Agreed. Pawn promotion makes the already absurdly high number of legal positions even more ridiculous. There are relatively few "rules" I can think of that govern what's a legal position:

- No more than 16 pieces of either color
- One king of each color
- No more than 8 pawns of either color
- No more than 10 rooks/bishops/knights
- No more than 9 bishops operating on the same color squares
- No more than 9 queens
- No double checks that could not have arisen through a discovery
- No checks being given by more than 2 pieces simultaneously
- Both kings cannot simultaneously be in check
- No pawns on the first rank
- Pieces can't be beyond a closed pawn formation (in some cases, such as the beginning of the game)
- Pawns can't be doubled/tripled/etc on the same files without an appropriate number/type of missing pieces on the other side
- No more than 5 pawns in the same file, subject to the above point
- Probably some more complicated ones

(I know nobody cares. I just thought it seemed like a neat exercise to come up with these)

 

[Molinaro]

- Pawns can't be doubled/tripled/etc on the same files without an appropriate number/type of missing pieces on the other side

(I know nobody cares. I just thought it seemed like a neat exercise to come up with these)

Very well thought out list , thanks.

Related to my question above I checked if 7 in one file could be discounted based on the required number of captures.

3+2+1+0+1+2+3 = 12 tells me no.

 

[maxpower1227]

Very well thought out list , thanks.

Related to my question above I checked if 7 in one file could be discounted based on the required number of captures.

3+2+1+0+1+2+3 = 12 tells me no.

EDIT: Mulligan

Actually, the req'd number of captures should be 21. I don't think they can come from both directions in the way you're thinking.

 

[Molinaro]

I mean no, as in I cannot rule out having 7 on one file.

 

[nimzov]

- No more than 5 bishops operating on the same color squares

I think this one is wrong. In theory you could have 9 bishops on the same colour.

All 8 pawns could promote on, say, white squares.

4 of them by capturing a piece on the 8th rank, and the other four by promoting without capturing anything on the 8th rank.

nimzo

 

[maxpower1227]

I think this one is wrong. In theory you could have 9 bishops on the same colour.

All 8 pawns could promote on, say, white squares.

4 of them by capturing a piece on the 8th rank, and the other four by promoting without capturing anything on the 8th rank.

nimzo

Good call.

And I'm thinking the max pawns on the same file is 5

 

[nimzov]

Good call.

And I'm thinking the max pawns on the same file is 5

I think I can put 6 on the d file with 9 captures.

d2
d3(c2xd3)
d4(b2xc3xd4)
d5(e2-e3-e4xd5)
d6(a2xb3xc4-c5xd6)
d7(f2-f3-f4-f5xe6xd7)

nimzo

 

[Folly]

In checkers there are 500,000,000,000 possible positions during the game that can occur. A computer can easily consider them all.

You're off by 9 orders of magnitude. There are roughly 5*10^20 valid board configurations.

In chess there are 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible positions during the game that can occur. A computer will never, ever be able to consider them all.

As was already noted, this number is also off. There are around 10^43, give or take a few orders of magnitude (what's a factor of a thousand between friends?) This actually makes a world of difference, because there's no reason to consider all of the positions. It's not currently technically feasible to search all the positions in checkers either (even if it was close enough to make thinking about it worth serious consideration.)

If we're trying to prove/disprove a win, we only need to show one of our moves is a win/one of our opponent's moves is not a loss. This means in the best case, we only need approximately the square root of the total number of positions to come up with a proof. The only gotcha lies in figuring out which move is the single move that needs to be considered.

Assuming chess has roughly 10^40 reachable positions, this would mean that the proof tree needed around 10^20 positions. This is "only" a million times larger than the checkers proof tree, which involved around 10^14 positions. Of course, the skeptic will cry "but the checkers proof was 10 thousand times larger than the square root! Why expect chess to be done in 10^20?!" And they would be entirely right. Barring some new clever ideas, or very large increases in computational power and storage space, chess is pretty much right out.

 

[maxpower1227]

I think I can put 6 on the d file with 9 captures.

d2
d3(c2xd3)
d4(b2xc3xd4)
d5(e2-e3-e4xd5)
d6(a2xb3xc4-c5xd6)
d7(f2-f3-f4-f5xe6xd7)

nimzo

Heh, yeah. I was stupid and neglected to consider the pawns actually moving
forward without capturing

To add another point though:
- For every promoted pawn, there must have been at least one capture made of a pawn or by a pawn.

 

[gnome]

Can the problem be solved by a clever trick of distributed computing, like SETI@Home?

 

[drkitten]

I'm not too keen on how this all works, so forgive me if this sounds silly, but if bad positions are eliminated - positions that wouldn't come up given perfect play, or at least some level of competent playing - would we be able to reach statements like "Given perfect play, white (will always win, can force a draw, will always lose)". Or are we even able to know what bad positions are without knowing what ALL positions are?

Simple answer : yes.

If we define "bad positions" as positions that can't come up during perfect play, then of course they won't come up during perfect play. (Duh.) Most researchers are aware that perfect play for White is the worst possible play for Black, and vice versa. But a large part of AI/game analysis is trying to identify positions where analysis is no longer needed because (for example), it can be statically identified as a loss for White.

 

[drkitten]

Can the problem be solved by a clever trick of distributed computing, like SETI@Home?

Probably not. The storage requirements would be immense. The basic problem is that if I trace a particular line of play to the end and find that it's a win for White, there's no easy way for me to make that finding available to the rest of the Internet. With SETI@home, each piece of data simply generates a "yes" or a "no," and we're not really interested in the "no"s except to eliminate them. With chess, each move generates 40 or so additional moves that need to be analyzed.

BELLE tried something like what you are suggesting back in the late 70s/early 80s, when she essentially generated random endgame positions and made tables of which ones were wins, which ones were losses, and which ones led to positions that were known wins and known losses. Revolutionized endgame play, too. But she couldn't handle more than about four pieces on the board before AT&T-BL ran out of memory for her to store the tables in. Today, we could easily replicate BELLE's hardware as many times as we needed to handle as many pieces as we liked. But we'd need several googols of Googles to store the resulting tables.

 

[geni]

Should be noted that not all posible draughts positions have been analyised yet.

 

[Cuddles]

- Pieces can't be beyond a closed pawn formation (in some cases, such as the beginning of the game)

Sure they can. Firstly, knights. Secondly, a piece could move beyond the pawns before the formation is formed. If you're only talking about the beginning of the game then that is true, but irrelevant, since the intial setup forms part of the definition of the problem, not the solution.

 

[Folly]

Probably not. The storage requirements would be immense. The basic problem is that if I trace a particular line of play to the end and find that it's a win for White, there's no easy way for me to make that finding available to the rest of the Internet. With SETI@home, each piece of data simply generates a "yes" or a "no," and we're not really interested in the "no"s except to eliminate them. With chess, each move generates 40 or so additional moves that need to be analyzed.

I completely agree with drkitten's answer: not very likely. This is despite the fact that the checkers solution used an idea designed to address this. Instead of having databases of all positions, or an enormous tree where the leaves are won/lost/repeated positions, you can make a tree where the leaves are the roots of smaller trees generated by some fixed time/size search. If each search examines roughly a million positions, your top level proof tree is reduced by some fraction of that amount (you don't get full savings because you can't keep track of transpositions between leaf searches.) This also makes using clusters very convenient, because each leaf search is now an entirely independent but non-trivial amount of work.

The fact of the matter is... chess is just really, really big. Just because it is absolutely dwarfed by other problems doesn't change this. 10^40 is one of those incomprehensibly large numbers. Even the estimated size of a minimum proof tree is enormous at roughly 10^20 positions. With the generous assumption of one byte per position (the list is sparse, so it would need a description of the position) that's still one hundred milion terrabytes.

 

[gnome]

Here's one for ya... don't store the positions. Have each computer on the distributed network record wins, losses, draws until all the positions are exhausted. It won't result in a playable algorithm for winning, but in the end it could tell you in theory whether a perfect game exists for white or black.

 

[drkitten]

Here's one for ya... don't store the positions. Have each computer on the distributed network record wins, losses, draws until all the positions are exhausted. It won't result in a playable algorithm for winning, but in the end it could tell you in theory whether a perfect game exists for white or black.

Um,...

I don't see how that would work. Let's say that computer A determines that a particular endgame position is a forced win for White.

Let's say that computer B determines that particular midgame position will (given perfect play) produce the endgame position analyzed by A, but then runs out of time before it can completely analyze that position.

Let's further say that computer C determines that perfect play from the starting position will result in the particular midgame position analyzed by B.

From these three findings, we can infer that chess is a win for White --- but only if we can stitch the three positions together, which in turn requires that A publish the position(s) it has analyzed, and B likewise.

If you're instead suggesting that every computer simply play a game (randomly) to completion and then record whether or not it was a win.... that won't tell us much, since we don't have any way of knowing whether the opponent used "perfect" play. There are lots of ways that White can make mistakes and allow Black to win and vice versa.

 

[Ashles]

The US dept of defence recently built a petaflops super computer.

I was with you until you started making up words.

 

[Mashuna]

I was with you until you started making up words.

No, there really is a US dept. of defense.

 

[Arthur Denton]

Can the problem be solved by a clever trick of distributed computing, like SETI@Home?

I believe it could, but solving chess is not really useful, is it? except, perhaps, if you're a crazy chess player who thinks that will save your soul in the end, or that maybe god, in its infinite anger will actually save you and burn the rest of the humans, because the rest of us would be whatever.

Chess is nice but hey - don't solve it. Let people lose their hair to do so. Computers already spoil the fun of having an unbeatable grandmaster.