Milos wrote:
It seams you have mixed up something. Determining whether a given number is a prime is log(n) complexity. You probably thought of prime factorization which is neither P nor NP problem (it's so called NP intermediate).
Not really. I thought of PRIMES is in P. As I said it was believed PRIMES was in NP.
Polynomial solution does exist with quantum computers, however quantum computers do not exist in a real world and probably never will.
I wrote the upper statement coz you wrote a number 2) which simply doesn't follow from the premises and looks quite ridiculous, which implied that you don't understand P and NP problems.
The smile in 2) means it is a joke. I meant it is such a breakthrough that they would have solved the P=NP problem.
bob wrote:
Chess is only NP until it is solved. And since it is finite, because of the rules, it can be solved, just not in the foreseeable future.
You must be confused here:
1- You say chess is finite, so you're talking about the standard version of chess with 8x8 board etc. That is not a decision problem (the set of inputs is not infinite), so you can't classify it as NP, P or anything like that.
2- Problems don't come out of NP due to getting solved. They either are or they aren't NP problems.
Last edited by rbarreira on Tue Mar 22, 2011 7:52 pm, edited 3 times in total.
bob wrote:
Chess is only NP until it is solved. And since it is finite, because of the rules, it can be solved, just not in the foreseeable future.
You must be confused here:
1- You say chess is finite, so you're talking about the standard version of chess with 8x8 board etc. That is not a decision problem (the set of inputs is not infinite), so you can't classify it as NP, P or anything like that.
2- Problems don't come out of NP due to getting solved. They either are or they aren't NP problems.
It is an exponential tree. Hence it is usually lumped into the NP class, by definition. But it is not infinite in size. A game can only have a finite number of moves before it ends, because you can only reset the 50 move counter so many times by pawn pushes or captures.
Once you search the entire tree, the game is solved and you no longer talk about exponential, or NP or anything else. As with the EGTBs.
I agree that a finite game can not be NP. But a game where the tree grows exponentially on depth is. So perhaps we would call this a "slang" use of NP.
It is certainly a "slang-NP" problem computationally, today. because the cost of going deeper is big and is exponential with depth.
bhlangonijr wrote:According to Aviezri Fraenkel (http://www.springerlink.com/content/y87641531hp807h9/), chess is classified into NP problem.If chess is solved, or even if you are able to catch up the omniscient player, it implies that either:
1) You reduced and solved every position of the chess game in a computable set of strategy rules, which don't require a exponential time, and thus chess is NOT into NP;
OR
2) You solved the P = NP problem;
Someone with at least a bit of formal computer science education doesn't need a scientific paper to understand that chess is NP.
This is simply not true. For instance, an algorithm that determines whether a given number is prime, was believed to be NP. Although it was proved there is a polynomial-time algorithm for solving it.
It seams you have mixed up something. Determining whether a given number is a prime is log(n) complexity. You probably thought of prime factorization which is neither P nor NP problem (it's so called NP intermediate). Polynomial solution does exist with quantum computers, however quantum computers do not exist in a real world and probably never will.
I wrote the upper statement coz you wrote a number 2) which simply doesn't follow from the premises and looks quite ridiculous, which implied that you don't understand P and NP problems.
What is you take on that (Is computer chess solved?)?
It's not solved and is far from it, but it might pass a lot of time before next big breakthrough is made (in programming sense), even though we might see a couple of hundred points in next 5-10 years on small ideas and tuning, but the wall will be hit eventually. And the state of CC at that point would be still very far away from solved.
Prognostication is very tricky business. I remember a number of statements in the 70's and 80's about computer chess progress hitting the wall. I'm sure Bob Hyatt and other old timers here remember that stuff.
Watch yer mouth, sonny.
Grandmasters predicting that computers would never be master strength (because they could not "plan") and even speculation that expert (USCF 2000) might be too ambitious.
In the last few years, that kind of talk has mostly stopped, but it persisted for what seemed like a long time. In each case we could see progress, but it always seemed like we had pretty much reached the point of diminishing returns and anything beyond would be small potatoes.
Moores law was around back then, but it was just a statement, most were not aware of it nor did we fully appreciate it's significance. Very few people in the computer chess community could imagine computers getting several orders of magnitude faster. Remember, Bill Gates himself said, "640K ought to be enough for anybody." He saw that as a very generous upper limit and we suffered for years because of it.
But as we vigorously argued as a group months ago, the progress in software for chess has been equally as amazing. Very few imagined it being so much. I think we have a lot more to go and we are not that close to the wall yet.
The wall however might be more about getting closer to perfect play than running out of tricks and ideas. It will also get harder and harder to measure superiority because it will require a lot more games when most games are draws.
It's not clear where hardware stands either. There is more of a focus on more cores and less on the speed of each core, but there are still a few breakthroughs we will see and I think we will still see computers that make what we have now look like embedded devices that go inside our toasters.
bhlangonijr wrote:According to Aviezri Fraenkel (http://www.springerlink.com/content/y87641531hp807h9/), chess is classified into NP problem.If chess is solved, or even if you are able to catch up the omniscient player, it implies that either:
1) You reduced and solved every position of the chess game in a computable set of strategy rules, which don't require a exponential time, and thus chess is NOT into NP;
OR
2) You solved the P = NP problem;
Someone with at least a bit of formal computer science education doesn't need a scientific paper to understand that chess is NP.
This is simply not true. For instance, an algorithm that determines whether a given number is prime, was believed to be NP. Although it was proved there is a polynomial-time algorithm for solving it.
It seams you have mixed up something. Determining whether a given number is a prime is log(n) complexity. You probably thought of prime factorization which is neither P nor NP problem (it's so called NP intermediate). Polynomial solution does exist with quantum computers, however quantum computers do not exist in a real world and probably never will.
I wrote the upper statement coz you wrote a number 2) which simply doesn't follow from the premises and looks quite ridiculous, which implied that you don't understand P and NP problems.
What is you take on that (Is computer chess solved?)?
It's not solved and is far from it, but it might pass a lot of time before next big breakthrough is made (in programming sense), even though we might see a couple of hundred points in next 5-10 years on small ideas and tuning, but the wall will be hit eventually. And the state of CC at that point would be still very far away from solved.
Prognostication is very tricky business. I remember a number of statements in the 70's and 80's about computer chess progress hitting the wall. I'm sure Bob Hyatt and other old timers here remember that stuff.
Watch yer mouth, sonny.
Grandmasters predicting that computers would never be master strength (because they could not "plan") and even speculation that expert (USCF 2000) might be too ambitious.
In the last few years, that kind of talk has mostly stopped, but it persisted for what seemed like a long time. In each case we could see progress, but it always seemed like we had pretty much reached the point of diminishing returns and anything beyond would be small potatoes.
Moores law was around back then, but it was just a statement, most were not aware of it nor did we fully appreciate it's significance. Very few people in the computer chess community could imagine computers getting several orders of magnitude faster. Remember, Bill Gates himself said, "640K ought to be enough for anybody." He saw that as a very generous upper limit and we suffered for years because of it.
But as we vigorously argued as a group months ago, the progress in software for chess has been equally as amazing. Very few imagined it being so much. I think we have a lot more to go and we are not that close to the wall yet.
The wall however might be more about getting closer to perfect play than running out of tricks and ideas. It will also get harder and harder to measure superiority because it will require a lot more games when most games are draws.
It's not clear where hardware stands either. There is more of a focus on more cores and less on the speed of each core, but there are still a few breakthroughs we will see and I think we will still see computers that make what we have now look like embedded devices that go inside our toasters.
_No one can hit as hard as life.But it ain’t about how hard you can hit.It’s about how hard you can get hit and keep moving forward.How much you can take and keep moving forward….
bob wrote:
Chess is only NP until it is solved. And since it is finite, because of the rules, it can be solved, just not in the foreseeable future.
You must be confused here:
1- You say chess is finite, so you're talking about the standard version of chess with 8x8 board etc. That is not a decision problem (the set of inputs is not infinite), so you can't classify it as NP, P or anything like that.
2- Problems don't come out of NP due to getting solved. They either are or they aren't NP problems.
It is an exponential tree. Hence it is usually lumped into the NP class, by definition. But it is not infinite in size. A game can only have a finite number of moves before it ends, because you can only reset the 50 move counter so many times by pawn pushes or captures.
Once you search the entire tree, the game is solved and you no longer talk about exponential, or NP or anything else. As with the EGTBs.
That doesn't make any sense at all, you're just ignoring the real definitions and confusing everyone else in the process. As I said, problems don't get out of the NP class due to getting solved. And there is no definition which says that NP problems have anything to do with "exponential trees".
bob wrote:I agree that a finite game can not be NP. But a game where the tree grows exponentially on depth is. So perhaps we would call this a "slang" use of NP.
It is certainly a "slang-NP" problem computationally, today. because the cost of going deeper is big and is exponential with depth.
bob wrote:
Chess is only NP until it is solved. And since it is finite, because of the rules, it can be solved, just not in the foreseeable future.
You must be confused here:
1- You say chess is finite, so you're talking about the standard version of chess with 8x8 board etc. That is not a decision problem (the set of inputs is not infinite), so you can't classify it as NP, P or anything like that.
2- Problems don't come out of NP due to getting solved. They either are or they aren't NP problems.
It is an exponential tree. Hence it is usually lumped into the NP class, by definition. But it is not infinite in size. A game can only have a finite number of moves before it ends, because you can only reset the 50 move counter so many times by pawn pushes or captures.
Once you search the entire tree, the game is solved and you no longer talk about exponential, or NP or anything else. As with the EGTBs.
That doesn't make any sense at all, you're just ignoring the real definitions and confusing everyone else in the process. As I said, problems don't get out of the NP class due to getting solved. And there is no definition which says that NP problems have anything to do with "exponential trees".
bob wrote:I agree that a finite game can not be NP. But a game where the tree grows exponentially on depth is. So perhaps we would call this a "slang" use of NP.
It is certainly a "slang-NP" problem computationally, today. because the cost of going deeper is big and is exponential with depth.
Oh, we're talking slang... OK then.
I didn't make the NP statement. I simply agreed that one could, given a bit of literary license, call a finite problem NP when even though it is finite, the size is really beyond comprehension, and certainly beyond the ability to search exhaustively for any conceivable time into the future.
I would have said "search is exponential" which is a very hard problem, until you reach the point in time where you can search the complete tree. Then it is not so hard any longer.
all depends what you call "solved".
In theory, cannot be done yes, as it has been said.
in practice for what to play chess means for humans, it is solved. We just cannot win a top 5 engine.
