Solving Chess

[SeanDamnit]

I'm curious to know if anyone is anywhere close to solving chess, like they did with checkers not too long ago. Wikipedia doens't have too much info on it. Is it even possible to solve chess using today's technology?

 

[van_dutch]

If I remember correctly, it is possible as there are a finite number of states of the game. The problem is that the states are very complex (multiple pieces with different moves) that it cannot be solved right now. I'm pretty sure there are partial solutions but no complete ones yet.

 

[nimzov]

It is solved....

http://kirr.homeunix.org/chess/3x3-chess/

...for a 3x3 board.

nimzo

 

[Molinaro]

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

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.

That number is hugely larger than the number of nanoseconds that has passed since the big bang. 10¹²⁰ vs 10²⁶

 

[SeanDamnit]

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

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.

That number is hugely larger than the number of nanoseconds that has passed since the big bang. 10¹²⁰ vs 10²⁶

As an aside, is there some sort of website where I can find obscure number comparisons like that? Or is that just something you know for whatever reason?

Like I put in some number, and it returns with "This is larger than 5 Texases (Texi?) laid side by side!"

 

[robinson]

A quantum computer could do those numbers.

 

[nimzov]

The number of legal positions is estimated to be 10^43 according to Shannon.

http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/series014

nimzo

 

[SeanDamnit]

That number is hugely larger than the number of nanoseconds that has passed since the big bang. 10¹²⁰ vs 10²⁶

Wikipedia states that it is 10⁴⁰ - if that's true, would that change the possibilites of solving chess?

 

[Jimbo07]

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

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.

That number is hugely larger than the number of nanoseconds that has passed since the big bang. 10¹²⁰ vs 10²⁶

Bah! That's got nuthin' on Go postions!

 

[Molinaro]

I went with a google look at a few web sites and a book on my shelf titled "Computer Chess II".

 

[robinson]

The thing with chess, is that most of the positions are bad ones.

 

[nimzov]

I went with a google look at a few web sites and a book on my shelf titled "Computer Chess II".

Are we talking positions of the chess pieces on a chessboard or "legal" positions. I guess that would drop the number from 10^120 to 10^43.

nimzo

 

[SeanDamnit]

The thing with chess, is that most of the positions are bad ones.

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?

 

[Molinaro]

The US dept of defence recently built a petaflops super computer. That's 10¹⁵ floating point operations per second. Imagine that you somehow, magically, consider a single board arrangement in just 1 operation.

You would have to run this computer for 10³⁵ seconds. As mentioned earlier, that's more seconds than there have been nanoseconds since the big bang 10²⁶.

It's still no where near the realm of possibility, especialy when you consider how many operations are actualy involved in considering just 1 position.

 

[Molinaro]

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?

I would think by bad positions they mean illegal. You couldn't have both of your bishops on the same color square at any time during the game. Nor could one of my pawns ever be on my 1st row.

 

[nimzov]

I would think by bad positions they mean illegal. You couldn't have both of your bishops on the same color square at any time during the game. Nor could one of my pawns ever be on my 1st row.

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

 

[Molinaro]

I didn't consider some crazy person wanting another bishop

 

[nimzov]

I didn't consider some crazy person wanting another bishop

There must surely be some chess problems based on that theme.

nimzo

 

[Molinaro]

Now I can't shake the question:

What's the longest line of pawns of the same color that can legaly be obtained during a game of chess.

One in front of the other is easy, and somewhat common. I would expect 3 to be simple to demonstrate. Four? Sure, why not if you contrive a set of moves.

6? and the theoretical max of 7? Which only can hapen if you can promote a pawn into a pawn

 

[Third Eye Open]

I would think by bad positions they mean illegal. You couldn't have both of your bishops on the same color square at any time during the game. Nor could one of my pawns ever be on my 1st row.

Or moving any pieces other than the knight when you haven't moved your pawns yet.