Is computer chess "solved"?

[bhlangonijr]

Since chess is finite, I think classifying it into P or NP is pretty pointless. Solving it is O(1) (though that's a pointless metric as well).

Now if you have some way to scale chess (say by board size or something), then you can talk about the algorithmic complexity.

Zach, in the paper I provided it is actually scaled using a n x n board.

[Zach Wegner]

Ah, thanks. I obviously didn't even read the title.

I was still confused by how they would show it's NP, so I read the abstract. They define chess as determining the outcome from an arbitrary position. I'd disagree with that, but it gets around the problem of having a starting position for chess on board size n.

[bhlangonijr]

Ah, thanks. I obviously didn't even read the title.

I was still confused by how they would show it's NP, so I read the abstract. They define chess as determining the outcome from an arbitrary position. I'd disagree with that, but it gets around the problem of having a starting position for chess on board size n.

Yes, and actually I pointed that out somewhere in the thread "some start positions may lead to a win for the white or black sides...", so that a given side may lost the game and even then with a perfect-play. That was my argument (guess) to show that win/draw percentages was not very useful for that matter. Only guesses though..

[bhlangonijr]

Agreed. Normally I don't like to nitpick this type of thing, but I find it a little annoying to see this mistake in the middle of a post denigrating those without a formal background in the area. kind of like finding a lot of spelling errors in a post about how dumb people are that can't spell.

-sam

Sam, in case you are referring to me, I actually have a formal background in the area. Despite the fact I have never been an assiduous student.

[Don]

Ah, thanks. I obviously didn't even read the title.

I was still confused by how they would show it's NP, so I read the abstract. They define chess as determining the outcome from an arbitrary position. I'd disagree with that, but it gets around the problem of having a starting position for chess on board size n.

Yes, and actually I pointed that out somewhere in the thread "some start positions may lead to a win for the white or black sides...", so that a given side may lost the game and even then with a perfect-play. That was my argument (guess) to show that win/draw percentages was not very useful for that matter. Only guesses though..

It would be huge surprise if it were the case that the game is not a draw with perfect play. In fact I think it may be a draw with any first move you can play, although some first moves may make it more difficult.

The way I like to think of this is in terms of how often does a given player blunder, that is make a move that with perfect play in response loses half a point, or a full point. Assuming the game really is a draw, nobody will even win or lose until a player makes one of these errors.

It think current programs make these errors often - but some of the time it's not punished. When computers get even better, the same blunders will start to get punished but there will be less of them too.

As humans we view chess strength a little backwards in my opinion when we talk about "great" moves and brilliancies and such. But I think it's more useful as a chess concept for computers to think of the game as blunder avoidance. Never play a losing move and never miss a win when your opponent offers it to you (that is a blunder.) But you can never "create" a win, it's either there or it isn't.

I'm speaking theoretically of course. In practical terms you can play provocatively in a such a way as to confuse your opponent or make it difficult. But to a perfect player every move is either good or bad and there is nothing in between.

[Milos]

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.

[UncombedCoconut]

It seams you have mixed up something. Determining whether a given number is a prime is log(n) complexity.

It is poly-time in the size of the input, which is measured in bits. (This is indeed proportional to the log of the number it represents.) This is the standard way of defining these complexity classes; if we used your way, finding a nontrivial factor of a composite number would be a simple O(n) problem.

[Don]

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. 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.

[bob]

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.
You seam not to understand what do P and NP mean. It doesn't matter how much real total time you need. Complexity is all that matters.
You and others (except maybe Bob) also seam not to understand what Cozzie claims.
He basically claims that there is nothing else left in computer chess programming except tuning. No more new, fundamental concepts will be introduced in the future.
The is certainly arguable, but it has nothing to do with elo, or percentage of draws and other things you discuss...

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.

If you take "foreseeable future" into account, chess is _far_ from solved today. There are almost certainly new ideas that will be discovered that take us deeper and deeper into the tree, giving us more accuracy and higher skill levels. Every few years we hear the same "computer science is solved". But software keeps on advancing. I find it no harder to make advances in chess today than it was 30 years ago. We knew less 30 years ago than we do today. But in 30 more years, we will know more then than we know now...

[bob]

Doubtful. This same discussion has come up several times in the past 40 years of computer chess activity. And each time some new idea comes along that rekindles interest and progress...

Agreed. I found his statement odd, specially because he said it comes from his background as PhD. Well, there is no scientific background in his statement.

Regards,

Perhaps "solved" means "no interesting ideas that I can see..." Everyone burns out eventually.