Here is a Wikepedia page explaining just what it means for a game to be solved.

To summarize: checkers/draughts has a weak solution and chess is partially solved.

"partially solved" is such a vague and bad term that it applies to any game you can think of.

A better way to put this is "checkers is solved, chess is unsolved". (I know it is useful to distinguish between weak and strong solutions of checkers, but you can almost consider it strongly solved).

That was a great read, thanks for the link.

One of the unsolved games, Go, looks really interesting.

"It has been claimed that Go is the most complex game in the world due to its vast number of variations in individual games."
"In fact, numerical estimates show that the number of possible games of Go far exceeds the number of atoms in the known universe."

It is interesting.

What fascinates me about go is not the extremely elegant handicapping system that allows people of differing skill levels to play against each other...but the fact that there so many gradations in skill levels possible.

The fact that I can give a 9 stone handicap to a 15 kyu...and HE can give a 9 stone handicap to a 25 kyu...plus the fact that I can get a 9 stone handicap game from a 4 dan....who in turn could be given a 9 stone handicap from a professional. It just blows my mind that the game can accommodate such a range in skill. And be fun and fascinating at all of these levels.


Chess will be solved. It's a matter of computing power, storage space, and time. Well, the same could be said about go, but I think the targets of each are possible in the foreseeable future for chess.

In chess the ratings range from below 800 to above 2800.

A 150 point difference gives you about a roughly 70% expectation over another player. And in spite of what many people think, 1100 is not a joke and is substantially stronger than most of all completely casual players. So you could easily have 30 levels of I can crush a guy who can crush a guy who can crush a guy who can...

And nobody who's familiar with the requirements for solving chess would ever state there's any chance of it being solved anytime in the foreseeable future no matter how loosely you define foreseeable future. Increase computing power a billion times over and you've walked an inch on a journey of many many miles.

Well not really. Professional dans are 1-2 stones apart from each other depending where you live.

20 years ago, was it conceivable that 6 piece table bases be available and accessible on any computer?

How long before opening books intersect with endgame tablebases?


I was referring to a 4 dan amateur vs a professional.

You missed icepick's point I think? He wasn't demonstrating merely a range of ability in Go. He was demonstrating the broad range of the handicapping system. A nine stone handicap requires you do be able to do more than just beat a guy with a 70% expectation in even games. We're talking 99%. Maybe more like 99.99%.

A one stone difference eliminates the compensation for going first. That's 6-7 points. Two stones let's the weaker player have two stones on the board before the stronger player plays. Probably a 12 point advantage. 4 stones lets the weaker player have a stone in each corner to start, let's say 25 points. Once you get up to nine, with a stone on each corner, on the middle of each side, and in the center of the board...

Yes, trivially so in fact. I don't think you understand the scale here. By assumption of Moore's law which there was absolutely no reason to doubt 20 years ago, again it can be said that anybody who said it's extremely unlikely probably would not really have been particularly familiar with what they were talking about.

Checkers took about nearly 20 years of massive computing to weakly solve during a time period when Moore's law has been proceeding without exception which is no longer the case. Without throwing out exponentials here, I'll use an easier to grasp analogy - incidentally also from the man who worked to solve checkers. Let's say we had a computer that could solve checkers in one nanosecond. That's one billionth of one second, or one cycle on a 1ghz computer. It would take that computer 3,000 years to solve chess. And actually that was an offhand remark that seems to have underestimated the complexity of chess - you can multiply by a few more magnitudes there.

Source?

http://www.chessbase.com/newsdetail.asp?newsid=3997

Chess is probably about as difficult for computers as 9x9 go. I don't see either falling to a solution.

Am I the one who missed the point? His first statement was: What fascinates me about go is not the extremely elegant handicapping system that allows people of differing skill levels to play against each other...but the fact that there so many gradations in skill levels possible.

It seemed to me that he was saying that what fascinated him about the game wasn't the handicapping system, but the huge range of skill gradations - which I simply mentioned are also clearly present in chess. Maybe I'm just putting words in his mouth.

Guess I misread that.

Assuming a computer than can solve checkers in a nanosecond (5*10^20 positions, from your link)...

Thats 5*10^20*10^9*60*60*24*365 = 1.5768 × 10^37 positions per year.

Given there's about 10^40 chess positions that can arise from a game (again from your link), and assuming no changes in technology...that's only 635 years.

Eh. Point made.


I'll revise my statement. Chess from a practical standpoint will be (and may already be) solved. IE, computers beat top tier humans.

Indeed, my point was the skill gradations. But the handicapping system is also quite elegant.


"If there are aliens, they play Go." -Edward Lasker

As mentioned that was an offhand comment. The number of positions in chess is actually ~10^43 which changes that to 635,000 years - but in the grand scheme of things that doesn't really change much. It's not happening any time soon.

From a game theory persepective chess is not solved.

I suppose your use of "solved" there does makes sense from the perspective of an engineer, though. If your goal is to be able to beat the best chess players who ever lived, then the chess engines we have now have already "solved" that problem.

I don't really see what computers defeating humans has to do with anything regarding solving a game. In particular the complexity of chess is such that humans are just rather poor at it compared to calculating machines. I think the complexity of go is of such a nature that humans are naturally rather good at it compared to calculating machines.

Oddly enough it seems a computer has already defeated an 8 dan pro at Go on a 9 stone handicap: http://www.cs.unimaas.nl/g.chaslot/muyungwan-mogo/ The success was declared to be due to the development of: "revolutionary algorithms that were invented in the period 2006-2008". Hyperbole or not, Go doesn't have anywhere near the history of computer involvement that chess does and the computers aren't going to be getting any weaker.

If you get to a stage where computers are consistently scoring 100% with white against other computers (or in the case chess is drawn then drawing near 100%) then maybe your comment might have some merit, but right now - computers just show that humans are bad at chess, not that computers are particularly good at it.

I'm aware of that game. The algorithms that Mogo (and MogoTitian) uses, is very ironically, the Monte Carlo method. It essentially plays random moves (for both sides), very quickly, and chooses the one that leads to the best result. Seems hardly a advancement, but it works.

For the record, they played several rematches, and MogoTitian was crushed, making mistakes that a 15 kyu wouldn't make.

Hypothetical: Get the top 10 GMs, the top 10 correspondence GMs, throw them in a room, and have them play a no-time limit game vs whatever computer is best now. What's the result?

The computer never moves because it has no time limit and thus never has a reason to move when it could instead calculate just one more ply (what's a few centuries, for the player who doesn't need to eat, sleep, breathe, etcetera?)

So an 8 dan professional can lose to a guy who is making moves that even a 15 kyu would know not to make? That seems kind of strange given how much you guys were praising the gradations in skill, Neil even mentioned that a 9 stone handicap would be only proper when the first player had something like a 99% expectation over the first. And an 8 dan is like 6 tiers of 9 stone handicaps above a 15 kyu. Of course I don't know much about go, so maybe I'm just misunderstanding something here?

Two different games. In the first, MogoTitian won, and played well.

In the rematch, MogoTitian played horribly, and lost very badly. Mistakes on the level of hanging your queen on move 5 bad. Same program. Same hardware. Same opponent. So, I don't know what kind of conclusions can be drawn with that kind of variance.

An 8 dan professional can probably give a 9 stone handicap to upto about a 5 dan amateur. The handicap isn't exactly linear. I'd say a 8 dan pro is about 3 tiers of 9 stone handicaps above a 15k. Experiments between equal strength professionals indicate that a 9 stone handicap is about a 130 point lead.

Fine. Time limit of 24 hours per move.