Is computer chess "solved"?

[Dr.Wael Deeb]

in the position, the best five moves lead to a draw, however, 2 of the moves create a greater number of chances down the road for the opponent to lose, whereas the other three lead to fewer chances. Then there is one move which may lead to dangers of losing (which I will not fall for as I am perfect) but far more chances to lose for the opponent, and then there is the sixth move which is objectively losing, but leads to the greatest number of winning chances. This last move might be desirable if the opponent is very unlikely (with X%) to find the correct defense, much less the winning defensive sequence. A calculated gamble.

I play like this all the time ...and it happens a lot in online blitz ..There are many "odd opening lines" that are really bad at least according to computers, but humans have problems with them.


Even if chess is solved -- chess960 even if solved would be exciting for humans to play. -- and i suspect other variants would be too.

Chess960 is a stupid variation of chess.....nothing beats the classic chess of game....

To play several games of every opening system/variation and feel the beauty out of it will take you more than a life time....
Dr.D

[Terry McCracken]

Chess960 is a stupid variation of chess.....nothing beats the classic chess of game....

To play several games of every opening system/variation and feel the beauty out of it will take you more than a life time....
Dr.D

I agree 100%!

[Dr.Wael Deeb]

Chess960 is a stupid variation of chess.....nothing beats the classic chess of game....

To play several games of every opening system/variation and feel the beauty out of it will take you more than a life time....
Dr.D

I agree 100%!

My man

[bhlangonijr]

It's still about your odds of winning and I think ELO is still relevant. I could be wrong about this, but I think we can get a fairly good measure of how close we are to perfect play by how often the top programs draw. And I think it's almost certain that the game is a draw because as programs get stronger (and at the top human levels) we see more and more draws. We can take a cue from checkers, where the top programs draw almost every game against each other, and we know they are close to solving the game because Chinook DID solve the game, and the other programs are not far behind.

If two of the top chess programs of the future play a 200 game match and every game is a draw, I think we can confidently speculate that we are within a few ELO of perfect play.

I would predict that an omniscient player would beat the best current modern programs almost every game. We are probably 500-1000 ELO from perfect play. You are probably going to hear that computers have practically solved chess, but nothing could be farther from the truth. We just think that because we are so weak at chess and are impressed with their playing ability, not realizing the very best humans suck pretty badly.

There will come some point when it becomes like checkers is now. Checkers programs are still not quite perfect, but close. Although chinook has "solved" the game, programs in practical time controls are still not quite there. But checkers can be pretty boring because in order to determine if one PC checkers program is better than another, you have to play a lot of games, the vast majority of which are draws. You might play 100 games and the score is 3 to 2 for example with 95 draws. (This is just an example, I don't know the exact percentage of draws modern checkers programs attain.)

If a program draws 98% of it's games against an equal opponent, it may still be a significant distance away from perfect play. It could be that if you draw 98% against an equal and great playing opponent you would still only draw 60% against a perfect player. I'm guessing of course.

Let's say the omniscient player is 1000 Elo far from the current best chess engine - "IvanHoeX". It would take ~20 years to improve IvanHoeX at the level of a perfect player in a pace of 50 Elo points per year (doable?). 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;

Once again, Elo and draw percentages are always relative to a given point of reference. It is not absolute. You can have 100% of draws and still be far away from the perfect play.
Don't you think so?

[Don]

It's still about your odds of winning and I think ELO is still relevant. I could be wrong about this, but I think we can get a fairly good measure of how close we are to perfect play by how often the top programs draw. And I think it's almost certain that the game is a draw because as programs get stronger (and at the top human levels) we see more and more draws. We can take a cue from checkers, where the top programs draw almost every game against each other, and we know they are close to solving the game because Chinook DID solve the game, and the other programs are not far behind.

If two of the top chess programs of the future play a 200 game match and every game is a draw, I think we can confidently speculate that we are within a few ELO of perfect play.

I would predict that an omniscient player would beat the best current modern programs almost every game. We are probably 500-1000 ELO from perfect play. You are probably going to hear that computers have practically solved chess, but nothing could be farther from the truth. We just think that because we are so weak at chess and are impressed with their playing ability, not realizing the very best humans suck pretty badly.

There will come some point when it becomes like checkers is now. Checkers programs are still not quite perfect, but close. Although chinook has "solved" the game, programs in practical time controls are still not quite there. But checkers can be pretty boring because in order to determine if one PC checkers program is better than another, you have to play a lot of games, the vast majority of which are draws. You might play 100 games and the score is 3 to 2 for example with 95 draws. (This is just an example, I don't know the exact percentage of draws modern checkers programs attain.)

If a program draws 98% of it's games against an equal opponent, it may still be a significant distance away from perfect play. It could be that if you draw 98% against an equal and great playing opponent you would still only draw 60% against a perfect player. I'm guessing of course.

Let's say the omniscient player is 1000 Elo far from the current best chess engine - "IvanHoeX". It would take ~20 years to improve IvanHoeX at the level of a perfect player in a pace of 50 Elo points per year (doable?). 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;

Once again, Elo and draw percentages are always relative to a given point of reference. It is not absolute. You can have 100% of draws and still be far away from the perfect play.
Don't you think so?

Basically I agree with you, but there is theory and there is practice.

I think in theory it will a very long time before we solve the game in a provable way. But it may be a much shorter period of time before it's possible to draw against "God" most of the time and come within, say, 50 ELO of perfect play. We just won't really know for sure how close we are.

In practical terms, I believe that if we keep improving programs and it gets to the point where they draw 99.9 percent of the games between each other, it's probably playing the best move 99.999 percent of the time, rarely making a move that throws away half a point. So even "god" cannot beat you if you don't make errors. So we will play close to perfect chess long before we have the resources to solve the game.

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

[BubbaTough]

Errr...technically chess is P.

-sam

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

[Zach Wegner]

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.

[bhlangonijr]

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.

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.

I know what it means.

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

That was _exactly_ what I understood. The point is: There is a gap between the best current chess engine and the hypothetical perfect-play "God" engine. The question is, how far we are from the perfect-play engine? How to measure that? Is it mostly solved? Would that would imply the best current chess engine is close to the perfect play? etc etc...
You stopped writing exactly in the relevant part. What is your take on that?

BTW, it seems that all your responses to any post have the follow predicted format:

... You know nothing... You suck... You are a complete ignorant about XXXXX....
... Please stop saying BS ....
...

If you are more knowledgeable & superior than the rest of us, then why don't you act like such? Start answering that simple question: What is you take on that (Is computer chess solved?)?

Regards,

[BubbaTough]

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

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.