I know it’s actually somewhat old news, but I just found out about the computer program that can’t lose at checkers. I really wasn’t that surprised, seeing as how simple of a game it is (4 initial moves with 4 initial responses, all pieces the same, 32 squares, etc.) But it is still a sign of the times and of how powerful computers are becoming.
I’m an avid chessplayer, so I know computers are already beating up on even the best humans in the world. Kasparov and Kramnik, among others, have been happy with their draws when they get them.
So I guess I question is, how long until chess, too, is solved? I figure there must be some way to calculate how long until it is solved, by it’s complexity in comparison to checkers, and the rate at which computers are improving, but I don’t have those statistics, all I know is they exist.
Isn’t is one of those things where in order to codify it, you need a computer with more bits of memory than there are fundamental particles in the known universe?
According to Wikipedia, the game tree complexity of chess is 10[sup]123[/sup]. If computers can do no better than brute force examination of sequential positions, they ain’t ever going there.
Cool. I’ll just have to root against quantum technology!
And as for “no better than brute force”, I’d like to point out that (although they are still weaklings right now) there are chess programs being made that play and analyze according to the position at hand, the way good human players do. They’ve got nothing on the supercomputers of brute force right now, but I think if anything they will be the future.
It’s important to mention that the computer solution for checkers only solved the game in the weak sense. It found a single line of play that can’t be beaten, no matter what moves the second player makes. However, there are many other legal positions that do not occur in this line, where the computer does not know what to play.
Something similar might be possible in chess. It might be the case that playing 1.e4 wins in all variations, and with a small enough number of possible lines to make the calculation managable. But again, such a computer would not know how to play the position after 1.d4.
That’s a good idea, like how the Sicilian Najdorf has become known as basically the most perfect first 5 moves for both sides, so maybe a computer could take the main line of that and force it to a won endgame. That would be much less work, and thus I’d think much more acheivable.
‘basically the most perfect 5 moves’ - according to who?
I could do a search on Chessbase for the most popular opening in GM play, but I doubt any single opening could match all of these in popularity:
Ruy Lopez (including the Open and the Marshall Gambit)
Petroff (drawing weapon of choice)
Caro-Kann
French
Pirc
Queen’s Gambit (including the Slav, Accepted and Exchange)
Kings Indian
Queens Indian
Nimzo-Indian
English (with all those transpositions)
Sicilian (Kan system)
Sicilian (O’Kelly system)
Sicilian (Dragon system)
Sicilian (c3 system)
Sicilian (Marcozy Bind system)
One way to look at the progress of solving chess completely is to study the speed of tablebases, which take all positions with a certain number of pieces and sort them into a searchable database. Then the database, **using no thought at all **, plays perfect chess.
They’re up to 6 pieces so far. When they reach 32 chess is solved. (Won’t be for a while, though!)
‘…tablebases require a lot of memory to store the many thousands of positions. The Nalimov tablebases, which use state-of-the-art compression techniques, require 7.05 GB of hard disk space for all five-piece endings. The six-piece endings require approximately 1.2 terabytes’
Programmers have been trying to prune the tree search ever since they started writing chess programs.
I don’t know of any success, because there’s no logical way to tell if a move doesn’t work unless you analyse it.
Good human players use a lot of pattern recognition - I don’t know of any computer program that can do this.
'The first paper on the subject by Claude Shannon, published in 1950 before anyone had programmed a computer to play chess, successfully predicted the two main possible search strategies which would be used, which he labeled “Type A” and “Type B” (Shannon 1950).
Type A programs would use a “brute force” approach, examining every possible position for a fixed number of moves using the minimax algorithm
…
Type B programs would use two improvements:
Employ a quiescence search.
Only look at a few good moves for each position
…
The problem with type B is that it relies on the program being able to decide which moves are good enough to be worthy of consideration (‘plausible’) in any given position and this proved to be a much harder problem to solve than speeding up type A searches with superior hardware and search extension techniques’
‘Chess 4.0 set the paradigm that was and still is followed essentially by all modern Chess programs today. Chess 4.0 type programs won out for the simple reason that their programs simply played better chess. Such programs did not try to mimic human thought processes’
