|
|
#11
01-31-2007, 04:52 PM
|
|||
|
|||
Re: Is Chess solvable?
Computing power advances at an amazing rate. Chess is not that complicated. I think it wont be so long before it can be solved. A couple centuries maybe. Have in mind we didn't even get to the point where we can solve a game as simple as checkers.
Now talk about solving Go, there you have a challenge. 
|
|
#12
01-31-2007, 06:02 PM
|
|||
|
|||
|
Re: Is Chess solvable?
I personally would not be THAT amazed to see chess solved in my lifetime, though I am not holding my breath.
The database holding all the solved positions is of course huge and will keep getting huger. The database necessary to make a meaningful contribution is not so huge -- a 7-piece ending either leads to a draw or to one of seven families of 6-piece endings - so all you need access to to solve that position are those seven families of 6-piece endings.
|
|
#13
01-31-2007, 10:51 PM
|
|||
|
|||
|
Re: Is Chess solvable?
[ QUOTE ]
Although there is a limited number of legal moves, you have to consider the total number of combinations of all those legal moves. This would give you the total number of all possible endgames. This number is greater than the total number of atoms in the universe. [/ QUOTE ] The game-tree complexity of chess (that is, the number of possible games of chess that can be played) is much, MUCH higher than the number of atoms in the universe. In fact, if you took the number of atoms in the universe and squared it, that would be closer to the mark. However, the number of legal positions in chess is far less than the number of atoms in the universe. In fact, the Earth alone contains at a minimum 10,000 times more atoms than the number of legal chess positions. But even so, you can imagine that this makes a database storing all possible positions completely infeasible - it would take up a good chunk of the Earth.
|
|
#14
02-01-2007, 04:46 AM
|
|||
|
|||
|
Re: Is Chess solvable?
[ QUOTE ]
In fact, the Earth alone contains at a minimum 10,000 times more atoms than the number of legal chess positions. But even so, you can imagine that this makes a database storing all possible positions completely infeasible [/ QUOTE ] No, it doesn't. A simple list of positions is infeasible. But what matters is how much *information* is contained in that database. It can be compressed, greatly - recall, for instance, a king and a bishop cannot mate a king, but a king and rook can. That one sentence covers just short of a million positions. (2*64*63*62 arrangements of three distinct pieces, only a tiny handful of which need handled individually - for instance those where the singleton king moves next and can capture the threatening rook and cause a draw) The simple endings have been known for years, of course -- but there are many more officially unexplored areas which won't take up much storage at all. Say, white has lost no pieces and black has 3 randomly selected pieces left: the list of such positions from which black can force a draw is gonna be realllll short.
|
|
#15
02-01-2007, 12:49 PM
|
|||
|
|||
|
Re: Is Chess solvable?
[ QUOTE ]
Although there is a limited number of legal moves, you have to consider the total number of combinations of all those legal moves. This would give you the total number of all possible endgames. This number is greater than the total number of atoms in the universe. No, I'm not joking and I'm not making it up. This is why IBM cannot just have their chess computer analize all possible endgames and always win. There is not enough computing power in the world to do that. They have to try to teach the computor how to play, analize the strength of their position, anticipate future moves, etc., similar to the way a human plays. [/ QUOTE ] Can you show me the math behind your statement.
|
|
#16
02-01-2007, 01:02 PM
|
|||
|
|||
|
Re: Is Chess solvable?
[ QUOTE ]
No, it doesn't. A simple list of positions is infeasible. But what matters is how much *information* is contained in that database. It can be compressed, greatly - recall, for instance, a king and a bishop cannot mate a king, but a king and rook can. That one sentence covers just short of a million positions. (2*64*63*62 arrangements of three distinct pieces, only a tiny handful of which need handled individually - for instance those where the singleton king moves next and can capture the threatening rook and cause a draw) [/ QUOTE ] This is an interesting point. But I don't think anybody looks at this type of compression. I assuming that chess programs are just doing a heuristic search. They take a move, and the resulting position, and they have a really good metric for evaluating whether the resulting position is good. The technology direction would then be to (1) Do better evaluations (2) Find new, interesting ways to explore the search space. I wouldn't think there's much current effort to say "Well, this position really reduces the same as this other position", in a provable way, beyond what is already there (i.e., the endgames you mentioned). Maybe there's some automated way to do these reductions (to AI people (or you if you're one of them), it seems like you are proposing finding interesting relations that can prune the search space ). I dunno, it's an interesting thought, but personally I'd be a little surprised the compression is effective enough.
|
|
#17
02-01-2007, 01:40 PM
|
|||
|
|||
|
Re: Is Chess solvable?
[ QUOTE ]
[ QUOTE ] Although there is a limited number of legal moves, you have to consider the total number of combinations of all those legal moves. This would give you the total number of all possible endgames. This number is greater than the total number of atoms in the universe. No, I'm not joking and I'm not making it up. This is why IBM cannot just have their chess computer analize all possible endgames and always win. There is not enough computing power in the world to do that. They have to try to teach the computor how to play, analize the strength of their position, anticipate future moves, etc., similar to the way a human plays. [/ QUOTE ] Can you show me the math behind your statement. [/ QUOTE ] Maybe he means solar system or galaxy ?
|
|
#18
02-01-2007, 01:48 PM
|
|||
|
|||
|
Re: Is Chess solvable?
Can they even reasonable estimate the matter in the Universe? If its infinite and we cannot see the 'end of it'... how can they reasonable assume they know the amount of matter?
|
|
#20
02-01-2007, 02:42 PM
|
|||
|
|||
|
Re: Is Chess solvable?
Okay, so I've read before about endgame tablebases, and clearly there's a mind-numbing gap between the current coverage (wikipedia says all 6-piece endgames have been solved: 4 pieces, 2 kings) and the complete 32-piece endgame tablebase that would solve that pesky "chess" issue.
Are there any Folding-at-home type distributed efforts to advance this? Or is the effort pretty much proprietary? And someone must have done the math somewhere to estimate the total storage space necessary for storing that data. Petabytes? Exabytes? Zettabytes?
|
 |
|
|
Linear Mode
