Slashdot Mirror
Solving Chess?
R. Jason Valentine asks: "One of the more complex problems that computing has tackled has been the game of Chess. The rules are simple, the strategy complex. We now have computers, based upon current technology, that can play as good as or better than the best humans. However, the current computing power is still far from answering the age old question: Is there such a thing as a perfect game of chess?" Anyone have spare processor time on a Beowulf Cluster? Or maybe this could be another project for distributed.net? Update: 04/30 10:38 by J : Remy de Ruysscher writes to say he's still working on
distributed chess;
to join his mailing list,
email him.
"For those who don't know, it is theorized Chess may be a solveable game -- i.e. one that if played perfectly, yields a predictable outcome -- be it a victory for white, black, or a draw. There are two new computing technologies that *may* be able to answer this question -- DNA computing and quantum computing. DNA computing is advancing fairly rapidly, and recently the largest quantum computer was devised -- a mere 7 qubits.
I am admittedly completely ignorant in algorithms used by computers to calculate moves, but I was wondering if anyone had any ideas on which technology would be more likely to solve the game of chess, and how one would devise a method to do so."
this probably isn't the most relevant post, but some may find it interesting...
when Deep Blue and Kasparov faced off some time back, IBM had some "guest essays" up on their site... my favorite was Arthur C. Clarke's essay/story piece. take a look.
-rbw
Heck, people haven't even solved checkers yet, despite a popular misconception to the contrary that an early 60's program played "perfect checkers" (it didn't, it was merely the first checkers program that was any good at all)
Click here for a discussion of the practical problems involved in solving the chess or checkers search tree.
A few posters have pointed out at the incredibly large number of possible games of chess. However, determining the optimal strategy does not require analyzing every game but "only" every single move from every configuration (still a rather large number in the ten-to-the-fourty's).
A few perfect endgames are known, however. That is, when only a small number of pieces are left on the board (five, I think, or pehaps only four in some situations), we have some gigabyte-sized tables which will give the optimal solution. Such tables are available for the Chess program "crafty" (semi-free I think; I don't remember the URL but it should be easy to find): so not only will the program play perfectly (if the tables are installed) at endgame, but it will also be able to make use of the tables a few moves before that to prune its search tree (so it can sometimes claim a mate in 30 or some crazy thing like that).
(Talking about crafty, I'd like to hear some comparison between it and the new version of GNU chess. Does anyone have data here?)
Playing chess against a perfect algorithm must be weird. Suppose the optimal solution is a win for white, say: then the perfect player would make its first move and announce "mate in 58 moves" (say). You make your move, and he announces "mate in 54": ah, well, you didn't do as good as you could have, some move would have let you remain alive for 57 more moves. And so on, you could see your "time to live" go down and down as you make those moves. Really weird.
Inventor of Unix Ken Thompson has always been very interested in chess (he was involved in some way in the Deep Blue event, I don't recall how, exactly). His web page has this table of chess endgames on it. Can someone figure out how it works? (I couldn't.)
From chess we can move to other games. The book you want to read is Winning Ways by E. Berlekam, J. H. Conway and R. Guy. It is the ultimate reference bible in combinatorial game theory (unfortunately, volume 1 is out of print; but you can still understand much of volume 2 without it; in it you will learn optimal solutions for a certain number of games, including some "classical" games (that is, not specially constructed so as to make this easy)). Really worth reading.
I think that people around here don't quite understand the term "perfect game" The perfect game would be a set of moves that always wins, no matter who/what was playing against you. This can only be calculated by recursivly trying every possible move. The number of possible moves in a chess game is completely astronomical, and I doubt we have the computing power to do it yet. You figure there are 16 pieses to a side, each piece can move in several different ways, there is a different set of moves for each previous move... etc...
I propose we chain a thousand monkies to chess boards to play each other for all eternity, constantly monitoring every move using highly sophistocated tracking equipment.
Given enough time this method will undoubtedly determine the perfect game of chess.
In a game limited games to 50 moves, with a very modest average branching factor of 15 moves per ply. Exhaustive analysis of this limited tree would require enumerating 10^120 nodes.
One widely accepted estimate for the number of atoms in the observable universe is 10^80. If each such atom were a supercomputer capable of generating and evaluating 1 trillion board positions per second, and had been doing so since the Big Bang (say 20 billion years ago), only the tiniest fraction of the analysis would thus far have been completed.
Now we need the computers to do it. Anybody care to hack together some code for a distributed network of chess computers? Once there is a good following we can issue a challenge to Deep Blue, see if the distributed project can take the chess title!
Enigma
You can get an exhaustive search of a tree without searching every node in the tree. Pruning techniques can remove many, many orders of magnitude from the amount of nodes that need to be search.
Have a look at Branch and Bound for example.
I have implemented a circuit partitioning engine using branch and bound that only searched 1% of the possible partitionings, and was still guaranteed to come up with the same solution you get with a real exhaustive search. This was with very small circuits; the larger the circuit, the smaller proportion of the nodes need be searched.
So, the raw number of possible games is not really an issue, even if you want to do the equivalent of an exhaustive search. If there happens to be a good pruning technique, the number of nodes in the tree becomes almost irrelevant. Branch and Bound may not work for Chess, but perhaps another technique would make the problem solvable by current technology.
--
Patrick Doyle
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
Chess has been the focus of most of the AI research of western world for the last, I don't know, twenty or so years. It is fairly clear that computers have improved by leaps and bounds in this time. Computer programs running on Intel computers have beaten grandmasters in tournament time. (e.g. Rebel and Deep Junior)
However, the game of Go/Weiqi/Baduk is a complex computational problem even when compared to chess as stones (pieces of Go) can be placed anywhere on a 19x19 board, making for a very large branching factor in the selection of each move, whereas pieces in chess are constrained to a much smaller set of legal moves (branch factor ~40). Go is also a loopy game, in other words, it has a game graph with cycles. (This occurs when you have double kos for example)
The branching factor plays a major role in the different stages of both games (beginning, middle and end). In the opening stage of chess, there are many well-known openings (Ruy Lopez, King's Gambit, blahblah) and these are often followed by both players (including the computer who really loves it, who can forget the last game of Deep Blue vs Kasparov?) upto 10 or more moves. In Go, the number of sensible openings is much larger, and whole game openings are rarely followed for more than about 5 moves. However, there are sequences of moves in local skirmishes, known as joseki, that reflect local optimal play (for both sides) in tactical battles in the corners. Skill in the use of joseki libraries lies in selecting the right joseki to optimise interactions with stones on the whole board or diverge from the known sequence to serve other interests. In the endgame stage of Chess, massive databases have been made to solve specific endgames. Computer programs thus can effectively wait and see if its puny human opponent makes a mistake when it finds itself in a favourable position. In Go, to the best of my knowledge, there has been a lot of research that have produced very good (even locally optimal) Go endgame programs but none of the existing Go programs in the market play even a decent endgame.
The quality of Go programs is looking better these days. The best programs can give an average amateur a good game at best. The ranking system of Go is (in ascending order), 30kyu-1kyu, 1dan-9dan (amateur), 1dan-9dan (professional). The highest ranked program Handtalk was awarded a 3kyu, but I remember reading somewhere that the author felt that it was due more to the fact that it was then the best computer program rather than its true ability that the Japanese Go association awarded the rank to it. (they are ranked around 15kyu in Internet Go servers) What does this entail? It means that you can pick up Go, play it for a about a month or so, and you can probably beat the best Go programs out there more then 50% of the time! Try doing that with chess!
In conclusion, while chess and checkers have not been solved, it is my opinion that computers are already better then any human being. (can be argued against for Kasparov vs Deep Blue but we will leave that aside) The point of my discussion? Forget about pumping more man hours into chess and reach for the pinnacle of AI research, Go!!!
That's my 5 cents.
[No Flames Intended]