< Earlier Kibitzing · PAGE 4 OF 4 ·
|Feb-04-06|| ||DeepBlade: If something has limits, it is possible to solve it.|
|Feb-04-06|| ||ganstaman: I wish I joined this site earlier, this stuff sounds fun.|
Here's my two cents: For chess to be 'solved,' we don't need to finish every game to completion. It would be nearly sufficient to simply demonstrate that a given position is won or drawn without going through all the near infinite gory details.
Examples of what I mean: If one side sacrifices a queen for no compensation, we can just say that the other side wins as long as we play out a few moves to make sure there really is no compensation. Games like 1.e3 e5 2.e4 are really just like 1.e4 e5 but with colors reversed. The games are of no independent significance, but add to the total a lot. Also, games like 1.Nf3 Nf6 2.Ng1 Ng8 just end up wasting a lot of resources if we study them.
And for my final penny, in computer science there are ways of classifying problems based on the size of the input compared to the amount of space or time needed to compute the answer. For example, if you have a list of N items in random order, finding a specific item would require the computer to traverse the entire list until it found it. This would take some multiple of N units of time (1 unit of time to read in the next item on the list, some more units of time to compare, and then another unit to decide to move on or that we found it). It would also take N units of space plus change (1 unit for each item in the list and maybe some more to store the item you are looking for).
One class of problems is called P. Problems in P are solvable in polynomial time, meaning that for input size N, the upperbound of time required is some polynomial with respect to N (such as 4N, or 3N^6-5N^4+N^3+N/8, etc). Another class of problems is creatively called NP, or not polynomial, I believe. These problems require more than a polynomial amount of time, something like exponential time (4^N, for example).
Chess is definitely a problem in NP. After every move you make, there is exponentially more games possible. Currently, no one has been able to prove if P=NP or if P != NP (where != means not equal to). That is, we don't know if there is a way to transform problems that are now in NP into something solvable in P. If NP=P, then many problems (like cracking security things on the Internet, or chess) would become solvable in a reasonable amount of time (i.e. before we die). It is believed, however, that NP!=P.
This leaves us with finding a new way to solve problems. Computers as we know them may get faster, but exponential problems will remain huge and take loooooooong times to solve. Quantum computers, as someone alluded to earlier, may be a solution. But for now, we haven't been able to build one (at least as far as I know).
Ok, that was a waste of time. I guess I just wanted to see if that class I took in Modern Complexity Theory taught me anything. Either way, I find it to be a fascinating problem.
|Feb-04-06|| ||ganstaman: One other thing, solving chess would not be the death of chess! Not even close! Well, for computers maybe. But not humans.|
Let's say it's discovered the 1.e4 wins for white and nothing else does. Fine, I'll play 1.d4 against you. Do you know the refutation? Let's say it lies within the Nimzo-Indian, so you play 1...Nf6. Ok then, I'll played the Tromp (2.Bg5) and see if you know how to refute that.
The point is, in order for chess to die amongst humans, all players would need to know the refutations of all non-winning lines. And I highly doubt this would ever happen even at the GM level.
And even if chess dies, at least it had a good run.
|Feb-04-06|| ||aw1988: Chess will never be solved, on the pure fact that a) it's of course huge and b) computers are terrible at long term strategy and c) even if you could program all this into a computer, it would be too much space, the computer could not handle it.|
|Feb-04-06|| ||ganstaman: <aw1988: Chess will never be solved, on the pure fact that a) it's of course huge and b) computers are terrible at long term strategy and c) even if you could program all this into a computer, it would be too much space, the computer could not handle it.>|
Sorry, but this is simply not true. With our current knowledge and computing abilities, chess is too large to solve. But if new techniques are developed so that either we can simplify the problem of chess into something much smaller or make computers work magnitudes faster (eg quantum computers), then chess no longer will be all that hard of a problem to solve.
Also, the idea of solving chess with a computer has nothing to do with it coming up with a strategy. Instead, every possibility will be tried out (or something to that effect). Therefore, the computer only needs to know when the game is won, lost, or drawn. Also, as AI continues to develop, computers may be able to become good at long term planning.
|Feb-04-06|| ||aw1988: <Also, as AI continues to develop, computers may be able to become good at long term planning.>|
Two words: Alan Turing.
So we'd have to check every single subvariation of every single variation of every single move, get all the strong players involved to find the truth in a complicated positional struggle, etc, etc...
|Feb-04-06|| ||ganstaman: With computers as they are (following Turing's Law or Theory or Whatever), I admit that chess can't be solvable in a decent amount of time. And the AI won't be perfect, but that doesn't mean that the AI can't get better. Humans don't calculate every subvariation to the end and yet we can make long term plans. As AI improves to become more like real intelligence, it will be capable of performing tasks that real intelligence can.|
Also, Turing's Law doesn't state anything about time. That is, if a quantum computer can solve chess in a reasonable amount of time, that means that our computers today can solve chess, but it can take any amount of time. And this is the issue we have been discussing the whole time.
|Feb-04-06|| ||aw1988: Well, I cannot make any solid foundation of an argument based solely on the fact that we do not have a crystal ball in front of us. I think it is impossible, but you will need more reason to convince you than 'computers are simply' whatever.|
|Feb-05-06|| ||DeepBlade: <Gangstaman on ''The Death Of Chess''>
True, not everybody can learn the refutation of every opening possible, but the Computer can refute it. So mankind will lose to its own son.|
And another thing about solving chess. When I search stuff I get big numbers of legal positions afer, say, 5 moves. Do they count the losing variations due less material or mate with the huge number or is it excluded?
|Feb-05-06|| ||aw1988: A lost position is "matter of technique", no need to analyze it further.|
|Mar-07-06|| ||LluviaSean: It looks like my air-conditioner. LOLZ!!|
|Jun-28-06|| ||blingice: Why did Kasparov lose to a machine several years earlier, but draw one that was even MORE prepared?|
|Jun-28-06|| ||suenteus po 147: <blingice: Why did Kasparov lose to a machine several years earlier, but draw one that was even MORE prepared?> One theory? Money.|
|Jul-01-06|| ||blingice: We've all heard THAT theory...
Is there a plausible chess reason?
|Sep-13-06|| ||h1a8: I have a suggestion (It may be a dumb one though) for a possible proof of chess. It is based off the assumption that perfect chess play by both sides will always result in a draw. But before the suggestion here are my motivations: |
Just like mathematicians can prove theorems that includes the infinity of numbers (like proving the prime number theorem without using brute force), I think it is possible to solve chess in a similar manner.
I remember an episode on Star Trek the Next Generation where Data stalemates a top strategical alien in a game. Data went for the draw and not a win because he deduced both that he cannot lose this way (he calculated an absolute drawing strategy) and that if both players played with the best strategy anyway the game will result in a stalemate. He did this because he lost previously to the alien and didn't know why. He then realized that he lost because he was going for a win and thus left himself open for losing. He thus used the principles for optimal strategy from game theory and drew the game.
In chess, without brute force, it can be proven for many positions that if played with the given strategy, a certain result will always be the outcome. This can be the case even though the number of moves (or positions) that can arise from it is beyond today's computer processing power. But we humans can see the solution relatively easy. We can even easily explain the plan that will guarantee the result without giving any variations. Thus we can create a somewhat proof of why the result(s) will happen no matter what (assuming we are to follow the given plan /rules).
Here is the suggestion:
One way is to find a perfect setup(s) for black and then prove that the setup(s) cannot lose if certain plans/rules are applied to it regardless of white's tempi (there may be many of them but they must be feasible to learn, record in books, and or program). This proof will take into consideration every possible strategy against the setup. For example, these strategies may include pawn break trys, exchanging, etc.
The setup(s) may be even only compromised (where the rules don't apply anymore) at the cost of severe material lost of white where no compensation exists. If this is the case then one should accept this event as a non-lose situation (as an axiom) just like, for example, many accept that a king with queen, rook, and pawns is a win (always) against a king with rook unless there is a mate in 1 by the side with king and rook.
The proof must contain that the required setup(s) cannot be stopped from existing without creating a huge axiomatic disadvantage. In other words, without the cost of decisive material, white cannot stop black from achieving the required setup(s). This may be the most complicated thing of the proof. It may need a supercomputer to prove it using brute force. Or then again it may be proven using some simple rules and or with a few variations.
Many of you may say that such positions (with their rules) are impossible.
And then I will say that such statements must be proven as well.
This suggestion I am giving is only a conjecture. The conjecture that such a setup with rules exist. This conjecture may never be proven but I think it is worth a try. And if anyone succeeds in finding a setup and proof they would have just proven the solution to chess (that it is a dead draw).
|Sep-26-06|| ||Ardashir: Ah, the stalemate... favorite ploy of writers who don't understand chess. Several times I have seen films or books where two equally strong players play each other, only for the game to end in at stalemate. |
In Alan Moore's otherwise excellent Swamp Thing series, the Swamp Thing plays himself in a series of games when he is stranded on an unihabited planet, but every single game ends in a stalemate - not just a draw, but a stalemate!
Now, I could accept an argument that two equally strong players might conceivably play draw after draw against each other, although even that is unlikely, but repeated stalemates?! Yeah, right.
If Data managed to end the game with a stalemate, he must have come pretty close to losing... these things annoy me...
|Sep-26-06|| ||Karpova: <Ardashir>
In the episode <h1a8> was referring to, Data didn't play chess against the alien. it was some strange game the alien race brought with them.
|Dec-07-08|| ||davidcinca: I'm not afraid if chess is solved. If it does, we change the board by adding new pieces like Capablanca's game, and the complexity will increase exponencially (it wouldn't be the first time chess rules are changed) so we will have 1000 years more of chess.|
|Dec-07-08|| ||Alphastar: What gives if chess is solved? It's pretty obvious that with best play the game ends in a draw anyway.
Besides, there's only so much one can memorize.|
|Dec-07-08|| ||Once: <with best play the game ends in a draw> Hmmm - are we sure about this? I see three plausible outcomes:|
1. White has an advantage because he moves first. With best play, this ought to mean that white should always win.
2. Black has an advantage because white moves first and so black can adapt his strategy to whatever white plays. With best play, black should always win.
3. The advantage/ disadvantage of the first move is insufficient. With best play, all games should end in a draw.
Maybe one day computers will tell us which of these is true. Until then, I'll keep on enjoying this game as an entirely fallible human.
|Dec-11-08|| ||Alphastar: <Once> I am pretty sure about it. Ofcourse, this is assuming that current opening theory is more or less faultless. When two GMs more or less play the opening faultlessly, the result is either equality or a slight advantage for white. Assuming both players make no more mistakes, it will remain a slight advantage or equality. Kramnik already remarked recently that it is harder to obtain a slight advantage as white than equality as black.|
|Dec-17-12|| ||Conrad93: Machines at their best can turn a score of 0.90 to 0.10 with accurate play.|
Even with best play relatively bad positions are drawable.
|Dec-17-12|| ||WannaBe: This machine is X3D, without special glasses, it will look fuzzy...|
|Dec-17-12|| ||Conrad93: So, how many positions could it calculate per second?|
More than a million?
|Aug-14-14|| ||Xeroxx: Nice picture.|
< Earlier Kibitzing · PAGE 4 OF 4 ·