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."
With all due respect the poser of this question is poorly informed. Solving the game of chess would require an exhaustive search of the tree of all positions. A conservative underestimate would be that the tree has a branching factor of 35 and a depth of 100. 35 ^ 100 is far more than the number of atoms in the Universe. Even if every atom of the Earth were a supercomputer it still would not be enough to solve this problem. DNA computing works by associating each potential solution with a unique DNA sequence and using chemical reactions to find the actual solution. However, even if the mass of the Universe were converted to DNA it would still not be enough DNA to represent all chess positions, and in any case DNA computing is only suited to problems where a solution can be verified, for example searching for an encryption key. It can't be used to search a tree if the path to the solution matters. The game of chess will not be solved by anything short of a quantum computer, which in theory could perform exponentially many calculations in parallel using quantum superposition. Any further discussion of this topic is stupid.
If you want to figure out a series of moves which could always lead to a victory (which may be possible) based on a single opening move, you could construct an algorithm that would play every possible game, and would figure out wich path did not allow the other player to win, no matter what he/she chose to do.
However, unlike distributed.net, where you know when you've found the answer and can throw away wrong answers, you have to save a whole lot of state for a brute-force chess game. The amount of storage necessary for all this state is probably prohibitive, even if we had millions of amazingly fast processors.
-- Erich
Slashdot reader since 1997
I still have to disagree. Most RTS games follow a very simple pattern: build lots of buildings, then build lots of units, then send the units to go fight the enemy. IMO, War2 is actually particularly *bad* in this respect. And yes, accomplishing those goals is more a function of how fast you can hit the buttons that of any great strategical insight.
Daniel
Hurry up and jump on the individualist bandwagon!
People might be aware of this, but I thought I would pass it along anyway - There is a GNU/Chess program. I believe that the playing ability of the computer depends on the processing power fo the computer (it has been a few years since I played it).
With source code available, it might be a place to start.
- (c) 2018 Hank Zimmerman
A question that pops into my limited mind: what would happen to the computer-human chess balance if we changed the rules slightly? Say switching the bishop and knight on one or both sides, or the knight and rook, or the King and Queen (and yes, I realize these changes would have to be analyzed by GMs to insure they didn't create a trivial game).
Now, IIRC, most if not all computer chess programs start out playing from an opening book, then switch to a search method when they go "out of book". However, thsee opening books were developed over hundreds of years by human players using standard non-quantative human methods.
If the rules were to change, and the existing opening books become useless, would the advantage then go to the human's intuitive style of play when facing the unknown? Or would the computer be better able to calculate new openings starting from zero knowledge?
sPh
You ask whether there is a perfect game --- SURE there is - that's been known for finite zero-sum games for decades now.
What the actual MOVES in that game are is a different question (and probably there are several equivalent variations for both players at most moves) which will remain clouded for quite some time yet.
Well, I recently (two weeks ago) attended a lecture by Jonathan Schaeffer, the main author of Chinook, (the "Deep Blue" of checkers) and he claimed that checkers is of yet unsolved, and I'd think he'd know.
You don't know that. That might happen, but it's also possible that white can always force a win, or maybe black can always force a win. Without exhaustively checking all possible games it's hard to tell which.
It can be determined in this manner, since you would know exactly what strategy the players are using - the best possible.
-- Ed Avis ed@membled.com
What I mean by a 'strategy' is a way to work out which move to play for any possible game position. Picking a move at random is one possible strategy, not a very good one. Another is to number all your pieces and always move the lowest-numbered piece as far as possible towards the bottom left corner of the board, or if that piece can't move or is captured, try the next piece and so on. Another rather poor strategy, but it will tell you exactly what move to play in any circumstance (deterministic).
Most computer chess programs will use a strategy that looks ahead to a certain depth and picks the move that ends up with the most favourable-looking board position after a few moves, allowing for the fact that the other player is trying to spoil things. A perfect strategy would look ahead without limit and work out the best move leading to checkmate, or at least avoiding being checkmated.
-- Ed Avis ed@membled.com
I think if someone is willing to offer US$10 million for the first computer that can serious take on a 4-5dan professional player, the race will be on.
Right now, only IBM has the possible resources to develop such a machine--imagine a massively-parallel CPU system using over 1,000 of the latest PowerPC CPU's. Someone might try by using a Linux cluster, but that will take over 300 machines running the latest Alpha AXP CPU running in clustered fashion.
In short, developing a computer that can challenge a high-level professional Go player will be the computing challenge of the 21st Century.
Raymond in Mountain View, CA
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.
I have seen this claim made on numerous occations. But I have not seen the explanation behind the claim.
Granted we know how computers play chess. Do we truely know how humans play chess? We know what humans say they do when the play chess. But do we really know what goes on in ones brain during a game?
Steve M
So this guy goes away to "study chess". He comes back after 10 years, and announces that he has figured chess out. He signs up for a tournament, and sits down.
"Pawn to king's knight four. Mate in seventy-two."
That would be pretty freaky.
My blog: http://www.seebs.net/log/ --- My iPhone/iPad app: http://www.seebs.net/seebsfrac/
The machine that could do this sort of think has a name: non-deterministic turing machine. Sadly, it doesn't exist. Yet.
> You can get an exhaustive search of a tree without searching every node in the tree.
In addition to B&B, there is at least the theoretical possibility of solving it with mathematico-logical methods that don't rely on search at all. E.g., prove certain theorems about what should and shouldn't be done in the game, and then apply induction to derive the best game.
I don't really know whether this is possible for chess, and I'm pretty sure it hasn't actually been done, but we should always keep our minds open to the possibility of solutions that do not require brute force search for "big" problems.
--
Sheesh, evil *and* a jerk. -- Jade
then I think you would have to be against the idea that chess is solveable, at least for a win. We've had a few hundred years of powerful distributed nodes (grandmasters, teachers, and prodigies, not to mention recent, silicon-based additions) hacking away at the problem with pretty good algorithms (check on Amazon.com for a good chess book) without even a hint of success.
Computers are only as smart as the humans that program them. ;)
You're correct, all that food would be expensive. It'd be much cheaper to run monkeys simulators on a big beowolf cluster.
I can't believe I just said that.
Boffoonery - downloadable Comedy Benefit for Bletchley Park
This argument is based on the number of bit operations needed to solve the argument, based on the premise that the number of bit operations is related exponentially to the key/game tree size. It does not apply to quantum computing, which has the potential to solve the problem in a number of operations related polynomially to the the problem size.
It kind of pisses me of when people say that computers are better than humans at chess. Computers aren't better, they are different.
The way computers play chess is that they brach down through all the possibilities untill they get to the limit of computing power. i.e. They will process down the tree until it gets to computationally intensive and time comsuming to warrant further branching.
Good human players don't follow every path down, and they only look a few tuns deep into any path. They recognize similar board patterns to games in their knowledge and experience and extapolate likely outcomes from the similar positions.
Until we can program a computers to win at chess that doen't use this "brute force" method of finding the best move, I can't be truly impressed with the computer's ability. Right now they have just made computers fast enough to think far enough ahead to approximate recognizing patterns in the pieces.
A wealthy eccentric who marches to the beat of a different drum. But you may call me "Noodle Noggin."
Quando Omni Flunkus Moritati
Sorry, URL missing. Should have used "Preview".
Ken Thompson's web page is here and his page on chess endgames is there.
This conclusion is based on a calculation that demonstrates that there are more possible chess games than there are hydrogen atoms in the Universe -- you'd have nowhere to store your candidate games while you evaluated their perfectness.
Though, as someone pointed out upstream, there's no reason to keep every game in memory.
-----------
"You can't shake the Devil's hand and say you're only kidding."
-----------
"You can't shake the Devil's hand and say you're only kidding."
Sorry, this analysis is wrong. The number of moves is irrelevant. It's hard to explain without diagrams, but here goes. Suppose that 30 moves into the game Black had twenty different possible moves available. By searching the tree exhaustively he finds that 18 of these lead to a white win in 10 moves or less, one leads to a black win in at least 25 moves, and one leads to stalemate in next move.
In this case we have N(WW) lt N(BW) and N(WW) gt N(SM) so according to your analysis the results is a stalemate, but actually Black wins if he makes the right move.
1) Energy is conserved, so you can never "use up" all the energy in the universe, you have simply converted it to a different form.
2) The problem is not really the computation time, I could set my little TI-82 at the task and have it finish in 10^100 years (pulled that out of nowhere). The problem is how do you store the results. If you have a very compact storage solution, where you only need a few hundred atoms per solution, you still need far more matter than we have available in our solar system.
Doug
Venn ist das nurnstuck git und Slotermeyer? Ya! Beigerhund das oder die Flipperwaldt gersput!
I'm not sure they are human.
Sure they can cope with rook to K3 but they are completely useless with in a game of 4-sqareso what does this leave? It laves the reality vs spcial training....
In about 1978 I played the 5th ranked player in the US in the age group at the time (Bert Iz.*cwi.*a?) and he said I missed betting him by one move.
He was rasied to play chess and he was good at it. He would have beeted my 10:1 at least (by my account) but I was rasied to build digital comptuters (thinks to some old bastards at NASA). I couldn't beet Bert at chess but I could program a computer to beat him but what does that get me. A box that can bet Bert-- so what. I still want to build a machine that can out think him that that just isn't going to happen.
Is this the same game? Played on a chess board but only using the white squares, where pieces move one square diagonally forwards and take by hopping over their victim, but can move diagonally backwards too once they've reached the far end.
perl -e 'fork||print for split//,"hahahaha"'
While creating a program and system that could handle a perfect game of chess would also allow it to be the best chess player possible, I do not believe that quality of game play is the objective here. Since the goal is to _solve_ the game, that is, know every posible move and determine who wins when both sides are aware of these moves, reaching this goal is theoretically within reach for the game of chess. On the other hand, we cannot possibly hope to solve the game of Go in the near future, because it is so much more complex.
If the ultimate goal is to solve both games, chess should be the first to be tackled, _because_ it is easier. Sure, people shouldn't stop writing Go programs, but they also should realize that the goal of Go programs at this point in the history of computing is to play better, not to solve the game.
I would like to see a derivation of this number. Could you please explain or link to one? (I just don't like accepting bare numbers as truth without any backing, I am not trying to be nasty here.)
Thanks.
Too bad. However, if there were an infinite number of monkies, they would have no need for canabalism, since they would finish immediatly (or rather, the amount of time it takes a single monkey to type it perfectly from beginning to end).
Not true. Do you remember those stupid "bunch of things, each move you have to take some, the last to take one loses" games?
If both players have full knowledge of the game, the first (or the second, depending on the exact rules) always wins.
But for example, checking the victory condition is easy (can the king move).
In fact there is more to it than that:
Can the king move?
Is the king in check?
Can the checking piece be captured?
Can a piece be interposed to block the check?
none of which are trivial, apart from perhaps the second.
Now, take the game of Go... it's much harder to figure out the victory condition
Not only is it difficult to spot that the game is over, it is diffuclt to see who won.
However, human players quickly build up an intuition for what style of position is a win, and they do not need to play onto the end. This intuition is extremely difficult to implement in a computer. (beyond current techniques?)
A different way of tackling this problem would be to start from the end and work backwards. How many legal board positions are there? It is certainly less than 13^64 (13 possibilities for a square, 64 squares) - much less than the 35^100 someone suggested.
I am assuming the same position will not be reached twice (if it were then we could cut out that section and still have the perfect game).
[Note for experts: I ignore the (relatively rare in this context) cases where the same board position has different move possibilities, and the case of draw by repetition).
I am sure that this 13^64 can be quickly reduced (eg. by noting there must be at least 32 blank squares) - but I will not do that here.
One could begin to assemble a tree backwards, by finding each legal position and linking it to ones that come after and before, until eventually the initial position were reached.
This of course does not escape the storage problem.. one figure i will quote is that a database exists for all possible games where it is down to 5 pieces total or fewer - this takes up 20gb of storage.
One also may be able to "classify" a large number of positions, and maybe even to create a hash that will identify classes of positions which all have the same assessment - this would alleviate the storage problem.
As to the result of the perfect game? Going by my chess experience, I would wager my life savings that it is a draw. There are just SO MANY final positions which are drawn due to lack of material. I cannot believe that white can force a win from the initial position, and i am certain that black cannot. An evenly matched game can only have an even result. The "best" game would have no clever sacrifices or traps, because the "best" line for the other player would preclude this. In fact, i think the "best" game would be exceedingly boring - and players would not play it exactly for this reason!
You seem to be mistaken about what solving chess means. The "solution" to chess would be a HUGE tree. Not just one perfect game, but a tree telling you the best move to make in any situation. That's why chess is so hard to solve.
--
No more e-mail address game - see my user info. Time for revenge.
Win dain a lotica, en vai tu ri silota
Nope. It's quite easy to envision an unsolvable FreeCell position.
Here's one, for example. The last 5 rows are:
3 3 3 3 5 5 5
6 6 6 6 4 7 7
9 9 9 9 J 7 7
2 2 2 2 4 4 4
K K K K J J J
Put any 4 cards you want in the holding cells - you won't have any valid moves.
It's possible that the 32,000 games that the Microsoft version is capable of generating are all solvable, though.
--
No more e-mail address game - see my user info. Time for revenge.
Win dain a lotica, en vai tu ri silota
offtopic, but, heres the info on freecell
---- I made the Kessel Run in under 11 parsecs.
Actually, to those who know how to play, chess can be a very interesting thing to watch. You get to think of what you would do in 's place, and if they do it and succeed, your though process has been vindicated, but if they fail, you'll know not to do that and why in one of your games. This would be especially true for two computers playing chess.
--
Seeing is believing; You wouldn't have seen it if you didn't believe it.
What would really be interesting is an algorithm-like solution of chess.
A (small) set of rules that provides an immediate and ideal answer to any possible move by the other party.
It is highly improbable that there will be one "ideal game" (ie one fixed sequence of moves to be made by either color to win the game no matter what the other color does). But a set of rules on how to respond "ideal" might actually be possible.
And then maybe the storage space required to hold this set of rules will actually be smaller than some weird number like the amount of hydrogen atoms in the known universe or whatever. That would be a "giant step for chess-player-kind" (and probably still a pretty huge step for one chess player)
Short answer: No, unless both players want it.
According to the rules of chess you may claim a draw at the third repeat of any position. This means that there are no infinite games if any one of the players claims the draw.
However, the draw is not automatic, so I guess that with suitable co-operation you could have an infinite game.
1. d4 d5 2. Qd3 Qd6 3. Qd1 Qd8 4. Qd3 Qd6 5. Qd1 Qd8 ...
Assume for the purpose of solving the game that player will claim the draw.
Hi!
This has been mentioned, but I'd like to take a crack at an explaination that might make sense to people who still don't get it.
You've seen chess problems, where you're given a board set up, and it says, "white to play and win in one". Which means, white can checkmate on the next move. When you see "white to play and win in two", it means that you make your first move so that whatever move black makes, you can checkmate them the move after that.
To Solve chess means to find the solution to one of the following problems:
1. From the initial board set up (all pieces in their original positions), find the answer to "white to play and win in n", where n is maybe 50.
2. From the initial board setup, find the answer to "white to play and draw in n".
3. From any of the 12 possible positions after white has made its first move, solve "black to play and win in n". Repeat this for the 11 other positions.
4. From any of the 12 possible positions, solve "black to play and win in n".
Since chess is a game of complete information, it's likely that there is a solution to one of these four problems. There might be more than one. There can be a solution to both 4 and 2, but there cannot be a solution to any other combination of these -- they are mutually exclusive.
If I remember my game theory correctly, any game of complete information is solvable, so one of these is the solution. No one knows which it is (although 1 and 2/4 seem more likely than 3, just intuitively.)
Funny that this was posted today. I'm working on a project for my CS class to write a program to play a simple contrived game well. We still aren't able to search the whole game tree, even for a simple game. I suspect a high end PC with a lot of RAM and hard disk space could solve it, but we don't have the time.
--Kevin
In 1997 Gary Kasparoff took on a computer built by IBM (called deep blue) and lost. Details on how the system works can be found here:http://www.research.ibm. com/deepblue/learn/html/index.html
___
. .in the center square.
___
"You get to think of what you would do in 's place, and if they do it and succeed, your though process has been vindicated, but if they fail, you'll know not to do that and why in one of your games. "
You can do that while you play someone too, which would be more fun than watching. Two uber powerful computers playing each other though is interesting (not so much fun), so is watching a human chess champ play a supercomputer (that happened and it was intriguing).
I am into the copy and paste.
It is an urban myth and it can be easily demonstrated by an 11 year old kid that it is impossible to win. Actually that is what is being done in classrooms all over the world. I still remember the tic-tac-toe sessions in primary school. There is one course of action with a higher likelihood of winning and that is starting in one of the corners. If the other player is inexperienced or stubborn, that might give a chance of winning.
Chess would probably be subject to the same problem, since both players would know all possible outcomes and the paths leading to them, they would try to steer it such that their chances of winning are the highest. Problem is that both want to win and that they will therefore in the end settle for a draw, because that is the highest either one will be able to get. Ofcourse this carries the assumption that the game cannot be determined from the outset by the first move that has been done.
Use Adsense for Charity
I know someone who made a chess program in his CompSci class... he programmed an AI for it and everything, but for some reason it started to play the opposite of the perfect game... it would *TRY* to lose... even if you just had your king left, it would just sit there and move the same piece back and forth between two squares...
If we can reverse this, does it mean that we'll have the perfect game? =)
-- Dr. Eldarion --
It's not what it is, it's something else.
It's bad form to reply to my own comment, but I'll add some more details. Schiener's argument on the basis that each operation must consume at least k*T (where k is Planck's constant and T is the temperature at which the operation is performed) makes several assumptions that are not neccesarily valid. By asserting that the mean free path of a particle is a limiting factoring for the operation (ie. in the movement for a particle between two distinct [non-quantum, physical] states) he implicitly assumes that the operation must be irreversible. This is false, as computers can be theoretically be constructued with reversible logic gates, from which all other operations can be synthesized. Additionally, even in the case that k*T consitutes a valid lower bound, the temperature of the cosmic background radiation (~2.3 K) is irrelevant. Systems can be cooled to lower temperatures; there is no neccesary lower bound to how close one can bring a system to absolute zero (without reaching it, of course).
This is sort of a "what's the big fucking deal" type post to me. Chess is a game. If it's solvable then no one would ever want to play computers at chess...and who wants two see "Deep Blue" and "Deep Green" go at it in a perfectmatchup.
Computers are still not as good as humans. Here's a tidbit of information. Deep Blue did beat Kasparov a year or so back. It was all over the papers in the whole "machine beats man" sort of thing. What most failed to mention was that the original Deep Blue had beat everyone it had played with the exception of Kasparov. When IBM went back to the drawing board. They altered some of the algorithms to specifically beat Kasparov. So we can pretty much assume that if Blue played another international grand master...it might very well lose.
By now you're asking...what's the damned point?? The point, my friends is this, one flaw is that chess is a very human game. The reason Kasparov beat Deep Blue in the first place. Because a computer can play a perfect game of chess against another computer. We're talking about calculating the best move in a given situation based on probabilities calculated 30-40 moves ahead (more realistically 10-20). But that totally removes the human element of chess....which is arguably the best element. While you can guess what your opponent is going to do on his next move...based on what you determine to be the best move...you can never say for certain! Every single move/counter move alters the game completely. GOOOOOOO HUMANS!!!!
FluX
After 16 years, MTV has finally completed its deevolution into the shiny things network
"It is seldom that liberty of any kind is lost all at once." -David Hume
No Beowulf cluster is going to crack this, so stop thinking it could: distributed.net is managing a problem of order 10^20.
Who says it has to come to a solution in our life time? It would be cool for the next few generations to see on the news in 3000 (assuming they didn't all did from the Y3K problem or the 2038 problem) to hear
"This week the dischess project completed and unrealved the prefect chess game today. The final computation was completed by a home PC with only a merger TY CPU running at 2500 THZ and a only 32TB of main memory, it is good to see slow machine still capable of running something productive."
I am not saying that it is practical today to start this type of project, it should be started, even if they know we won't see the results before we die, it would still be cool. Plus if you get a bunch of engineers, CS and grandmasters in a room with a massive cluster, something Good has to come out of it, even if they don't find the prefect chess game.
Go back to the PD11 era and tell the brightest CS that computers would be able to generate 3 hour fully CGI 3D movies in the matter of 6months-1year.
"`Ford, you're turning into a penguin. Stop it.'" -THHGTTG
You're right. It took me almost 20 minutes to get that formatted inside this small box, some 15 previews, and a lot of pain. I was bound to make a mistake. Thanks for catching it.
---
How am I supposed to fit a pithy, relevant quote into 120 characters?
What exactly does it mean to "solve" the game of chess? After all, there are widely published sequences of chess moves which lead to a given outcome. Any chess book will illustrate a number of them.
Does it mean that before you start playing you can mathematically prove what the outcome will be? I suppose if both players are computer programs with their source code published, this could be done. But then you're analyzing computer programs rather than the game...
So I guess I don't understand the question.
---
How am I supposed to fit a pithy, relevant quote into 120 characters?
---
How am I supposed to fit a pithy, relevant quote into 120 characters?
A lot of posts here deal with the impossibility of a brute force attack in repsect to a perfect game. Citing examples such as the amount of energy from the sun, 34^100 nodes, and other crazy numbers seem abound here. However, to put things in perspective, take Kasparov's mind. How many atoms do you think that's made of? How many atoms in that gray mass of his are actually working on solving a particlar game of chess? I'm not suggesting that his games are perfect, far from that, but if the human mind were to be modeled someday, and then perfected for a game of chess (true AI), computers would come very close to producing a perfect game. Heck, if quantum computing ever gets off the ground in a pratical means, maybe the question will become moot, and other recursive problems like "What will LA look like after a 30 mega ton nuke is dropped?" will be the challenge. Peace, Nic
As I mentioned before, Go has a even larger branching factor than chess which does some implications. A brute-force search method cannot be used in Go.
We are nowhere being able to 'solve chess' by brute force methods either.
Computer chess then can be based on pattern recognizationWhy is this not true of Go ? The answer here is that chess has been studied systematically, by more people, and for longer. It has a much more active press, with more published works by several orders of magnitude than Go. There are more players studying chess than Go. Programmers of chess computers have much more to work with than programmers of Go programs. Hence a chess machine that can give Kasparov a hard time on a good day. The equivalent published body of work does not currently exist for Go.
Computer chess then can be based on pattern recognization.
This is an amazing statement ! Have you ever played chess, or even seen it from a distance ? Or are you suggesting that there are no patterns in Go to recognise ? Or are the patterns not so well understood outside a small elite who are shy of publication ?
Stephen Hawking has written another book. It's about time as well.
The Mongrel Dogs Who Teach
the concept of a distributed.net approach to this is intriguing. probably as close to applying open source techniques to this game as we can get.
-----BEGIN GEEK CODE BLOCK-----
v.3.12
GCS d-(--) s+: a-- C+++$>++++$$ UL++$>++++$$ P+>++++$ L++>++++$ E--- W++$>++
*sigh* Hopefully, this should be the last thing I will append onto my own thread.
For a complete survey of Computer Go hit this link where I got most of my material.
As I mentioned before, Go has a even larger branching factor than chess which does some implications. A brute-force search method cannot be used in Go. This implies a whole paradigm shift in tackling Go. Second, this means that perhaps even when faster machines appear, they might not improve a Go program's playing ability by a lot. Rather, to improve Go programs would require improving the algorithms.
So why tackle Go instead of Chess? I feel that to make a computer play Go effectively you would need to be able to recognize patterns and act on intuition due to its impossibly large search space. i.e. brute-force searching is secondary (you still need it to determine life/death of groups) in this case. You need to incorporate tons of knowledge into Go programs, much more than you would need in Chess programs. In addition some form of functional approximation (neural networks?) will be needed to abstract all the knowledge and apply it effectively on the board. Unfortunately, many experiments involving neural networks and Go have been failures. This suggests that some new technique will be required to play Go well.
If this technique is found, the same method could possibly be applied to many areas that other people have brought up in this thread. e.g. Computer chess then can be based on pattern recognization and these programs will probably play more "human-like" and Computer vision problems can (big perhaps) can benefit from this.
On the other hand, solving chess would simply require many many more machine hours of number crunching and would have applications to other fields of computer science.
To explain this article a little better, here is what the distributed method would be doing: building the world's hugest opening game database. That is it. It would be running an alpha-beta pruning mini-max algorithm with hash tables so many times to create a huge database. Then, this database (probably, I don't know, maybe 500 mb?) could be used so that search trees would never be used again on chess. The best move for every position, in all cases, for all sides. This would only work if it were completely solved, of course, because a computer who knew only the absolute best path could be beat if someone played an inferior path. Yet, this would be very intresting. It would be the *end* of computer chess. Never again would Kasparov play deep blue, only inferior humans would challenge each other, since machines would think it to be trivial.
-------------------------------------------------
Not really. Knuth & Moore have proven the lower bound of the number of positions to be looked at, in order to prove the value (win/loss/draw) of a certain position as:
b^floor(d/2) + b^ceil(d/2) - 1
where b equals branching factor and d equals ply depth
If you know that b = 38 for chess, and the average chess game lasts 40 moves (d=80), you will see that even with a pruning technique that always reaches this minimum, the number is still terribly LARGE.
A better pruning technique would improve pratical performance of chess-playing programs, but would not make the game more solvable.
--
GCP
Give me 1000 Chimps, one chess board and a video camera.
well they wouldnt come up with the perfect game of chess, but it would be a hell of a good entrant for funniest home videos.
Be you Admins? nay, we are but lusers!
Let's imagine we have a computer chip that clocks an impressive 1,000,000,000,000,000,000,000,000 Hz (10^24, or 10^12THz), which is a LOT of noughts faster than anything around today (and given Moore's Law, it'd be a long time before we see anything like this). Now let's assume that each person on the planet (population of the Earth is, say, 1,000,000,000,000 (10^12), which is about 200 times what it is today), owns a planet which has 1,000,000,000,000,000,000,000,000 (10^24) computers, each with 1,000,000,000,000,000,000,000,000 (10^24) of those nippy chips in it as part of an SMP sort of array... And let's assume each instruction cycle evaluates 1,000,000,000,000 (10^12) nodes in the chess game graph (they're custom chips with crazy super-scalar-oojimaflipsit pipelining and parallelism, ok?)...
It's still going to take about 100,000,000,000,000 (10^14) times longer than the age of the Universe so far (and that's before you factor in all the communications overhead, the fact that these computers would take more energy than there is in this Universe, the amount of silicon or other semiconductors we used, the fact that most of the planets just collapsed into black holes, yada yada).
-- Maz
Holding out some hope for running Quake 666 on that lil' cluster...
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!
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]