Solving chess

teacher_1 is an anagram for cheater_1...

 Two key phrases:

1. Chess playing software - Where are we at with chess software?  I hear so much talk about Rybka this and Rybka that by GMs on this site, as though it's the holy grail for calculating best moves, or in post analysis: Was that the best move I could have played?

It sounds like Rybka has satisfied the GMs regarding the practical side of chess: evaluating the position and arriving at the perfect answer. Has Rybka solved chess, as it relates to finding the best move to play in any given chess position? That would be wonderful. Isn't that the only thing that truly matters to chess players around the world?   I don't believe any human has this rating, yet.

Rybka's current rating is a staggering 3238!!!

http://www.chess.com/news/rybka-wins-computer-world-chess-championship

Now, if some here are concerned with the possibility that chess may be a game that always ends in a draw, like tic tac toe when played perfectly, well, no one's perfect. Gary Kasparov may be perfect when it comes to chess: By that, I mean Mr. Kasparov may always be able to calculate the best move when his brain is well rested. However, we will never really know due to mental fatigue.

Computers never get tired, humans do, thus, human calculations get worse as time on the clock heads towards zero. If Gary Kasparov were only required to calculate 5-10 positions in one sitting, take a break, rinse-repeat, would he arrive at the same answers that Rybka spits out? If not the exact same, at least answers of equal quality? A human Rybka?

2. When people ask the question: Can chess be solved, what are they asking?

Are the number of atoms in the universe relevant to this discussion. There are 64 squares, however, not all of them are relevant all of the time, to humans. Example: When White is in check and only has one move to get out of check, how many of the 64 squares will the human scan, how many squares will the computer scan before arriving at a decision? You see, the computer needs to do what a human does not need to do: scan the entire universe of possibilities to calculate the best possible move. IBM did that with Deep Blue some years ago. I believe it's called brute force calculations. The software of tomorrow needs to be written in such a way that computers calculate more like humans, in order to avoid the unneccesary brute force calculations done today. Computers will not have the processing power in my life time to solve chess, if done by brute force. The article below sheds light on brute force calculatiuons as it relates to chess.

 ------

An excerpt from an article I found relevant to this topic of discussion:

Deep Blue (the cost of the Deep Blue project from 1985 to 1997 is estimated to have been over $100 million), which was a massively parallel RS/6000 SP based computer with 32 processors that could evaluate 200 million chess positions per second.

If Deep Blue's computing power is compared with its chess rating, assuming Deep Blue was a chess master (rating 2200) in 1985 and equal to the World Champion in 1997 (chess rating 2800+), we can see a dramatic acceleration of the number of chess positions per second necessary to achieve a significant gain in chess rating. On average, the number of positions per second evaluated by Deep Blue increased by a factor of 2.2 times the number of positions per second every year, and an average of two years passed for every 100 point chess gain in Deep Blue's rating.

As a result, if Gary Kasparov's chess rating had been 2900, rather than 2820, it would have taken IBM at least another two years to develop a computer that could beat him.

What is interesting, however, is that it would have required calculating nearly 1 billion positions per second (969,289,665) to reach the chess rating of 2900.

---------------

What does having studied at MIT have to do with anything? Is that to be interpreted as the ever-lasting moronic I-am-a-member-of-mensa-so-I-am-right thing?

Having studied in a good university on a related subject is, in my opinion, a decent factor in making one's opinion more credible than someone who's done nothing more than read popular science articles and Wikipedia. There are, of course, exceptions, but as a general rule of thumb it's good in gauging whether someone knows What the Heck S/he's Talking About(TM). Admittedly I don't have much past interaction with pbrocoum to be able to make a fully valid judgement, but given his credentials (as listed on his profile page) I'm more likely to trust him on this subject as compared to, say, an arts major, all other things being equal.

BTW, pbocoum, just taking note of something you've brought up...I assume that by "energy" in "pi times energy divided by Planck's constant" you mean the energy equivalent of 1kg of mass, i.e. (1kg)c^2 joules? EDIT: Never mind, I'm being an idiot, I could just do the calculation outright...it does come out to the right order of magnitude.

Also, you said that's the "potential computing capability" of 1 kg of matter. As this isn't really my field, just to get some feel of the numbers, how far are our computers from this potential capability? I mean, you did mention it can do 10^50 operations per second, and given the number of possible positions is (or so I hear) on the order of 10^40, it doesn't seem implausible that given such capability and some time, chess could be solved. Although if our computers are operating at like 10^-10 of that capability then yeah, we're nowhere near.

PBROCOUM brings some much needed INTELLECT into the conversation.

Exactly what I had hoped for. Exactly why I returned to this site. Exactly what this site NEEDS. The average IQ of posters was sinking and sinking. I have a PROBLEM with that, as it drags what I brought to the table, DOWN.

I am SICK and tired of seeing, "what's your favorite opening". I'm on a MISSION to change that.

Anyways, I do have a problem with things being classified as definitely impossible. Call me a glass half FULL type of guy. To be sure, there are the glass half empty type of guys (pbrocoum) who have a problem with things being 100% possible. Nothing wrong with that, no disrespect.

But see, the solving of chess is SOLELY based on computing power, nothing more. That is the only requisite item. As of today, it is 100% impossible. As of next year, it is 100% impossible. !0 years from now, 100% impossible. THat may be the problem with you YOUNGSTERS, lack of farsightedness. But in our lifetimes, there WILL exist the computing power. History PROVES that 100%.

Allow me illustrate using the advances of computer MEMORY. I'd like SOMEONE else to do an analysis based on processor power.

1982: average memory 64 k

2009: average memory 4 GB

1 GB = 1,048,576 kb so therefore 4 GB = 4,194,304 kb.

So, the ratio of 64 to 4,194,304 is a 6,553,500 PERCENT INCREASE!!!!! Do the MATH!!!!

Anyone wanna argue with that? Good. Now to ROUGHLY project, based on that percentage, what the future hold for computing memory: 4 GB increased by 6,553,500 percent equals 262,140 GB of memory.

This translates to 1024 GB = 1 TB so 256 TERABYTES of memory within the next 20 years.

Geometric progression on steroids.

Finally, almost everyone agreed that checkers would never be solved until CHINOOK came along. 500 billion billion possibilites was OUT OF THE REALM of possibility back in the day. Time solves everything.

http://www.nytimes.com/2007/07/19/science/19cnd-checkers.html?_r=1&hp

Will chess ever be solved? In the near future? No. Yes, chess is finite, yes, it can theoretically be solved, but in the near future? I find this very unlikely, even with the amazing progression of modern computers. On top of this, if chess were to be solved, would it really influence the game to know that perfect play would end in a draw?

I know, I know, mentioning that I'm from MIT makes me sound arrogant, but I only bring it up so that people don't think that I'm some schmuck on the internet.

Practically, I don't think solving chess will make any difference. If chess is solved, computers will always win... but computers already always win. And yet human beings still play and chess isn't dead yet, so I don't think there's anything to worry about.

The actual numbers aren't so important from a math perspective. With a theoretically perfect computer, it would be able to list all the possible chess positions in a few minutes. Still, listing all positions and analyzing all positions are completely different. However, yes, a theoretically perfect computer does bring solving-by-calculation within the realm of possibility, but the idea that we will ever have a theoretically perfect computer is very far-fetched. Also, as Seth Lloyd points out, such a computer would only exist for a fraction of a second before all the matter was converted to energy and thus the computer blinks out of existence. We'd have to use the entire mass of the Earth for our calculation. Anyway, again, none of this matters, I was just trying to put into perspective just how difficult the calculation would be.

Currently, the world's fastest supercomputer can perform 1.759 x 10^15 operations per second [1], and there are 10^50 possible positions in chess, so it would take 3 x 10^27 years to list all the possibilities (list, not analyze). The universe is 1.4 x 10^9 years old, about 14 billion years. It would take said supercomputer a billion billion histories of the universe to list all the possible chess positions.

As the teacher pointed out, I don't like to use the word "impossible". If chess ever is solved, it's much more likely that it will be solved through some clever mathematical theorem than through brute force. That's kind of the problem: right now, our approach to computers playing chess is brute force, which is a bad approach (as far as "solving the game" goes, playing the game it works very well). We don't have any extra planets lying around that we can conveniently convert to supercomputers at the moment. But that doesn't mean we won't change our approach in the future.

My point is this: don't hold your breath. It's not going to be solved in your lifetime, which is the only lifetime that matters. It's very romantic to believe that science will solve everything, but it's also sort of dangerous. Imagine if someone said, "20 years from now medical science will probably have a cure for cancer, so I'm just going to keep smoking today because what do I care?" Well, MAYBE science will be able to cure cancer, but probably not. It's more likely they will come up with better drugs or artificial lungs that will allow you to keep living, albeit at a lesser quality of life. Trust me, smoking isn't worth it, no matter what medical advances we make.

[1] http://en.wikipedia.org/wiki/Supercomputer#The_fastest_supercomputers_today

Oh, and you might be interested in an example of what I meant by a "clever mathematical theorem". The game of Munch has been "solved" in the sense that it can be proven that the first player always wins even though we are unable to find a general strategy that will win for boards of larger size. Using the "strategy stealing argument" it can be shown that any move the second player can make, the first player could have made before him on the first turn. Therefore, since the game cannot end in a draw, and since any winning strategy employed on the second turn could have previously been employed on the first, the first player always wins with perfect play. Even if we don't know how :-)

You can play the game here: http://www.philipbrocoum.com/munch/

 1. So, the planet would blink out of existence as well? We would all be converted to pure energy, just to solve a board game? Astounding!

It reminds me of the book, Hitchhiker's Guide to the Galaxy", and the Answer to the Ultimate Question of Life, the Universe, and Everything. It required a super computer which produced a silly number 42, which then required a computer to build an even larger computer (earth) to bring meaning to the number 42!

It takes Deep Thought 7½ million years to compute and check the answer, which turns out to be 42. Unfortunately, The Ultimate Question itself is unknown.

When asked to produce The Ultimate Question, the computer says that it cannot; however, it can help to design an even more powerful computer (the Earth), that can. The programmers then embark on a further ten-million-year program to discover The Ultimate Question. This new computer will incorporate living beings in the "computational matrix", with the pan-dimensional creators assuming the form of mice. The process is hindered after eight million years by the unexpected arrival on Earth of the Golgafrinchans and then is ruined completely, five minutes before completion, when the Earth is destroyed by the Vogons to make way for a new Hyperspace Bypass. 

--------------------------

2. If you read my post, #26 , you will see my mention of brute force not being the answer, and that software that enables a computer to calculate as a human does is required to solve chess.

"The software of tomorrow needs to be written in such a way that computers calculate more like humans, in order to avoid the unneccesary brute force calculations done today." - Musikamole  

Question for the math experts: How close are we to getting computers to calculate in an intelligent way? Today, computers are completely stupid! They can't think, at all.  To think that the little machines scan all 64 squares when the obvious answer is found on one square: Qxf7 - checkmate!

3. Munch has been solved using a clever mathematical theorem? Well, I'm a music teacher, not a math genius. So, in simple terms, what kind of math would be required to solve chess? Is it really that difficult to develop a mathematical theorem for chess? What other problems would this new mathematical theorem solve, i.e., world hunger, cure for cancer, etc. ? I'm sure there would be a government grant for such a theorem, since solving chess right now requires the destruction of entire planets! If chess could be solved, then perhaps most of life's problems could be solved as well. Get to work, all you math geniuses!

4. Munch can't end in a draw? Hmm, perhaps I should switch to that game. If my chess skills drift towards mastery, well, it may just become a boring game where I can at least play for a draw, not taking any risk. I believe that risk taking is required at the highest levels of play to achieve a win.

Ah, that settles it. Better to not become a master chess player, where the game becomes drawish.  

pbrocoum - Now I know which door to select when playing the Monty Hall game! I have a 2/3 chance to win if I switch doors.  And I thought it went to 50/50.

Then, why not correct the quote? You claim to be a scholar, yet you overlook key details in the claims that you pretend to refute. Failing to note the error, you then offer absurdities, rather than clear data.

Coincidentally, this sort of error is tantalizingly similar to another poser with a name very much like yours. Even the capitalization and preferred verbs, logic, and sentence patterns are similar. I'm tempted to investigate the disappearance of the Other, as I seem to recall that it occured somewhat prior to July 11.

10^120 is a conservative estimate of the number of permutations of a game of chess lasting forty moves or less. Yes, that number is finite, but it grossly exceeds the estimate of the number of atoms in the visible universe 10^82 (when Commodore 64s were the best home computer, 10^79 was the estimate, but our telescopes have improved dramatically). The seven piece tablebases will be completed before the Mayan calendar runs out, and they will fit on a hard drive that you can buy this holiday season at Best Buy, but the eight-piece tablebases are many years away, and thirty-two piece tablebases remain a distant and remote theoretical possibility that almost certainly will be within reach of 512 bit processors when they are developed.

ZIRYAB, I have one word to summarize my take on what you said......"HUH?"

First off, I DID correct the quote by saying that it was like comparing apples to automobiles (see the sarcasm? even apples to oranges is too close a comparison). Absurd? Absolutely, because an absurd quote deserves an absurd response.

Second off, why continue to even compare atoms vs chess moves. There is no CONNECTION? Help me understand why people even bring it up.

For example, I'd like to buy my my girlfriend (yes I have one) a $500 piece of jewelry for Christmas. That's all she wants: jewelry. NOTHING more. But you know what? There is this $125 circular saw out there that she ABSOLUTELY does NOT want. You know that $500 is more than $125, so I guess that means that I CANNOT buy her the jewelry because the saw that she does not want is cheaper than what she does want.

Do you see the absolute ABSURDITY of what I just said? How many times must I be forced to RACK my brains to come up with FOOLISH comparisons so that you ALL will stop with the atom garbage. We SCHOLARS can only take so much insulting before we get upset.

For sake of argument, let's say all the data is correct about atoms and chess moves. Let's say that there are even MORE chess moves than believed. Let's take it even further and say it is PROVEN that there are 10^82 atoms and 10^240  chess moves. I say, so what?

10^52 atoms and 10^350 chess moves....so what?

10^22 and 10^500....who cares?

It means NOTHING until you say INFINITE chess moves.

Once again, and for the LAST TIME......There is NO CONNECTION.

So, now that we got THAT out of the way, I'll reiterate again, ONE day, all the possible chess moves in the known universe will fit onto the head of a pin.

NOW, this will be my LAST post in this article. LAST POST unless someone can bring to the table some valid argument as to why chess cannot be solved.

I'm starting to think I need to send a few of you to the "special needs" classroom. My patience is getting thin.

Well, that's a start. When I refuted the nonsense you posted as cheater_1, you failed to respond. I suppose I should have read your introduction before I offered my observations concerning the style of your prose and the gaps in your logic. There's no game of discovery when you've already confessed.

Several months ago, I challenged your credibility as a self-professed computer cheater because your posts revealed minimal knowledge compounded by astounding misinformation concerning computers and chess. Now, you've again made claims that you cannot substantiate. Still, if you have some evidence, please offer it.

You claim that chess will be solved. Give us a date within one century.

Ok, if we are talking about software "solving" it, then yes it makes it even more possible that way than through brute force. On one video I saw a man compare a 1970's computer with todays software with a todays computer with 1970's software. The computer with the older hardware would be faster. This gives us an idea how much infact the software has also developed. One poster brought up a point; computers can't think. I believe they can in near future. Some people even believe they will have superhuman intelligence relatively soon. I think that kind of monster could solve chess pretty quickly. :D

good topic... by the way, i dont think that any chess software can solve everything related to CHESS... CHESS is something very unique... it is an excellent game.. & is a vast game...

Chess is fun whether it's solved or not

Yeah but it's another "We did it!" thing, another achievement.

Just a point though, to throw in my own two cents, the very fact that computers don't play "intuitively" as humans do is part of the reason why they're so strong, especially at tactics. Even an amateur can see

But it takes a strong player to see

So it's not that important whether a computer can see "obvious" moves quickly, it's more important whether it can see the "non-obvious" moves that win the game.

Whether or not computers will be able to think in the future is a good question. On the one hand, it's entirely possible that human thought is nothing more than chemical calculations in the brain that are analogous to how a computer works, in which case it's very likely that computers will be able to think and probably think better than we do. On the other hand, it's entirely possible that human thought is completely different from performing calculations, in which case it's very unlikely that computers will be able to think. Finally, on the third hand, it's also possible that humans think in one way and we will devise computers that think in a different way.

I suspect the third possibility is what will eventually happen (although I don't really have any evidence for this). First off, computers are already so different from brains that I think it's kind of odd to believe we will make computers that can mimic brains. Second, computers already do most things differently, with chess being an excellent example: people plan and strategize, computers brute force a solution. Third, who's to say that the computer way of thinking won't be as good as the human way of thinking? It's clear that the computer way is vastly superior to the human way when it comes to chess, for example.

I think the problem is really a philosophical one. No matter what advances are made with computers, people are always going to complain that "computers aren't really thinking, they're just calculating." Well, if we can make a computer that calculates so well that it can emulate consciousness perfectly, who are we to say that it isn't actually thinking? Another slight problem is that as long as the source code for a computer program exists, it won't have any "free will". But then again, do we humans even have free will? If you could fully dissect every neuron in someone's brain, you would essentially have the "source code" to that person.

Some time ago I partipated in a long discussion in these forums regarding this issue. Soon I found myself the last man defending the "unsolvability" of chess, for which I exhausted every plausible argument I could come up with. Eventually, after exploring every possible avenue of argument, I had to recognize myself vanquished. I came to be persuaded that chess is indeed solvable, and I had to recognize that I was clinging to its "unsolvability" more for emotional reasons than for reasoned ones. Not wishing to go over all these arguments again, I will limit myself to saying that the finitude of chess games is imposed by the fifty-move rule; and that a game that is finite is theoretically solvable. Fortunately for my psyche, that still leaves baseball.