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."
All I can say is, Bollocks!! While it is inevitable that computers will eventually clearly stronger than the best humans, this is not the case now. Kasparov-Deep Blue was hardly convincing. As for advancing chess, what human and computer players actually do are so different from each other that it is hard to imagine one learning from another. Computers will be stronger simply because they calculate longer and accurate variations. Human capacity to calculate variations won't get any better, we will carry on using intuition and judgement like we always have. Even games between the strongest chess programs are full of terrible positional and strategic mistakes,this will probably always the case. Human games are full of tactical mistakes. They always will be. Unfortunately, tactical mistakes are more devastating as the punishment is immediate.
A perfect game by both sides might result in a stalemate; I'm not sure anyone really knows. In game theory, you try to find optimal strategies for both sides. An optimal strategy satisfies the property that if one player deviates from the optimal strategy and the other sticks to it, then the latter will always do better because of the former's poor decision. Thus between any two sufficiently intelligent players, there is an equilibrium in which they know they have to stick to a well-specified strategy because they know their intelligent opponent can take advantage of any deviation from the optimal strategy. (In a game with a score, the latter will win by a bigger margin---and if the game is biased (for example by one party being forced to make the second move) the underpriveleged player will at least know that deviating from the optimal strategy results in a bigger loss so long as the other player is smart enough to stick to his/her optimal strategy). The key assumption here is that the other player is intelligent enough to exploit your failure to follow the optimal strategy; if he/she isn't, and doesn't know his or her optimal strategy, you can trick them in various ways with sub-optimal strategies---and that's what actual chess is all about. Optimal strategies exist for sufficiently intelligent players in both sides in any two-player zero-sum (zero sum means their loss of points is your win of points) game. This is a theorem by Von Neumann. See The Theory of Games and Economic Behavior by Von Neumann and Morgenstern.
Along these lines, in asking more game-theoretic questions about chess, it would be interesting to know if the leading player has a strategy available to always win and if the other player can always force a stalemate. Hell, I can't even think of an ironclad argument that the player who doesn't start can't always force a win. If either side stuck to these sorts of strategies, it would, in game theoretic sense, be a game played perfectly by one side, even if it resulted in a stalemate.
BTW, we don't have the computational power to check all possible moves yet, and, unless we develop an approach to non-deterministic computing I doubt we ever will. We are talking about particles in the universe type numbers here. This would be an extremely nasty exponential time problem.
Chess is a good game of logic and strategy, but it is hardly the epitome of either. I prefer RTS games like Red Alert or Warcraft - the AI stinks but when you play against a human there is no comparison.
:) ) Even Civilization has to take second place, IMO. (although that's a far better comparison)
I'm sorry, but that's just blasphemy. Comparing the clickfest that is your average RTS to the intellectual exercise of chess? The only thing that could explain such a gross misapprehension is that you have never studied chess more deeply than the Parker Bros. rulebook. I don't think I can enlighten you in this space, but get a couple of good chess books and read them -- it's far deeper than anything to come out of the computer game companies (not that those games aren't fun anyway
Also, since you mentioned stalemate--it's generally agreed that chess has to have one of two outcomes if played perfectly: either White wins or it's a draw. (Black could win, but most chess-players would eat their hats (metaphorically) if that turned out to be the case) Note that one of these *has* to be true: if there's ever a position where a player has two moves, one of them inevitably leading to a better end for him, he'll take the better one, and this can be extrapolated back up the game tree.
What makes chess still interesting is that even if it were solved, no human would be able to memorize all the intricacies of every line of play. (learning one line of play would be feasible, but all your opponent has to do is to play a line that you don't know, even if it's slightly worse) Given this, we have to fall back on general pattern-recognition and short-term calculation, which makes it still a game of skill and justifies comments like "slightly better" when a 'perfect' game only has three, very discrete valuations of positions.
Daniel
Hurry up and jump on the individualist bandwagon!
There are published sequences of moves for both players. But there is not a published strategy for white which will always win, no matter what moves black plays. This would of course be an impossibly enormous task, at least using conventional computers. (Work out the number of possibilities, even approximately, after twenty moves.)
AFAIK 'solving' the game of chess means finding a perfect strategy for both players, a strategy which would have to work out all the possible cominations in advance and plays the best move. If both players did this and neither made a mistake, what would the outcome be?
There is already a perfect strategy for each player in noughts and crosses (tic-tac-toe); AFAIK it leads to a draw. (Some people say that the first player can always win, but this seems to be an urban myth.)
-- Ed Avis ed@membled.com
In fact there is a mathematical theory that most humans don't learn which in a significant portion of endgames can determine who wins the last point.
Of course in general we don't know how to get computers to win at Go. What we do know is that the technique used in chess is useless because of the branching factor. The state of the art of chess programs today is not much better than it was 20 years ago. But they can throw more computational power at the same problem and that makes the difference.
Even with Moore's law, raw computational power will not suffice to become good at Go within the next few decades.
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
-There is still no simple/elegant solution to AI Chess. This is why chess is a realm essentially abandoned by the AI community. There is no decent uniform solution to chess around (whether it involve genetic algorithms, neural nets, or game trees). Deep Blue, while very effective, is apparently full of messy hacks and different AI techniques. And because it uses search trees, it does not run in linear time, like the following example
-checkers, on the other hand, has a beatiful solution that works quite well. let me quote Russel & Norvig's excellent Artificial Intelligence: A Modern Approach:
-solving the game of Go seems to be even more difficult than chess. There is a $2,000,000 prize for the first program to defeat a top level player.
Not even that good. Handtalk, one of the best programs, has a 5 kyu Japanese diploma, but most people agree that it is not even that good. For reference, I'm a American 5 kyu, and have only been playing 2 years. A pro player, the equivalent of a chess grandmaster, would probably give me between 9 and 13 free moves at the start of the game to make it reasonably even.
In a public demonstration, Janice Kim (one of the few western-born pros, and far from one of the top pros) gave Handtalk a handicap of 35(!) free moves at the start of the game, and then beat it. The current best program, Go4++, is perhaps two or three stones (free moves) stronger than Handtalk, but that's still a *long* way from the chess equivalent of grandmaster.
Now, I'm not saying that Go is a "better" game, but computationally, Go is a whole different scope of problem than Chess.
For more information on Go, email me or check out the home page of the American Go Association.
Patrick Bridges
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]