Solving Chess? 269
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."
Re:Solving Chess (Score:1)
Your error was that you said "unsolvable" without qualifying it... which is the same thing as saying "impossible".. which some things may be, but we can never know for certain (and even if we prove it, something beyond our current knowledge may be a disproof or throw uncertainty into the mix).
Remember, we're "only" "human"! (at least, you are :P)
how about the perfect blowjob? (Score:1)
heheh (Score:1)
My computer can beat me at chess but I kick its ass at kickbox.
( I post my insightful thoughts on real
Re:I wouldn't think so... (Score:1)
Go watch a blitz chess tournament. (Score:1)
Re:Chess has already been conquered. Humans lose! (Score:1)
Given the complexity of chess, and the heat death of the universe, there will be no such point.
Re:Solving Chess (Score:1)
There's more to a board position in chess than the layout of the pieces. What moves have been made in reaching the position is essential-- for example, if the king has moved at all during the game makes a difference in many positions (castling is not allowed). Pawn capture "en passant" is only possible immediately after an opponents' pawn has moved two steps. Also, there are rules that allow a player to claim a draw if the same position is reached three times in a game, or the 50-move draw rule (if 50 moves go by without a pawn move or a check, the a player can claim a draw).
It might indeed be possible to find a more compact representation than a game tree-- but certainly the representatio will be much more complicated than a graph of board layouts.
Sorry, you're wrong. (Score:1)
Re:how large is the chess tree? infinite! (Score:1)
1) If the same position is repeated three times, it's a draw.
2) If an opponent doesn't move anything except his king and his pawns for some number of moves (50? I don't remember.), it's a draw.
Re:I don't think this should be determined (Score:1)
is playing to win the perfect strategy? (Score:1)
It's a little offtopic but still interesting...
Positions, Moves and Chess (Score:1)
However, there are more possible board positions in chess than there are molecules in the known universe, or so I've been told.
If that's true then only Quantum computing would seem reasonable for finding the solution.
Does anyone know how much space a book solutions would take up? (A book solution is one where all possible positions are mapped and linked to any other position that could occure from it.)
Re:Computers aren't better at chess (Score:1)
Until humans can play and actually consider all their moves instead of making wild guessess, I can't be truly impressed with a human's ability.
All things considered... (Score:1)
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.
So maybe it's possible they could make the perfect chess player.. one who never lost.. but who's to say you still couldn't stalemate it?
Re:how to determine the perfect game of chess (Score:1)
Re:Chess vs Go (Score:1)
take on a 4-5dan professional player, the race will be on.
Actually, someone in Taiwan (a certain Mr. Ing, I beilieve), has been sponsoring tournaments for Go-playing programs, and offering a prize (something like a million dollars) for any program that can beat a strong human player (something like a 1-Dan pro). This has been going on for at least 15 years, and no one is even close to claiming the prize money.
Go-playing programs can be very good at LOCALIZED problems, e.g. a life-and-death problem in a small part of a corner. But they are horrible at making GLOBAL decisions.
The difficulty in programming Go is not just the width of the move tree (in the middle of a Go game, there are a couple of hundred possible moves; in the middle-game of chess, a couple of dozen). The other problem is evaluating a given position. In chess you can devise a simple, fast, fairly reliable static evaluation function that tells you for whom the situation is favorable, and by how much (by assigning values to the types of pieces, and by looking at which pieces are attacking which other pieces). You can even do this in hardware.
But for Go, no one has been able to devise such simple, fast, global evaluation function.
Re:o/~ can't get there from here o/~ (Score:1)
The universe is about 15 billion years old, and there are about 19^79 atoms estimated by physicists. Do the math yourself.
Re:Insoluble (Score:1)
Re:Solving Chess (Score:1)
Ridiculous Idea (Score:2)
The problem is *storage* (Score:2)
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.
Re:All things considered... (Score:2)
Daniel
One place to start... (Score:2)
With source code available, it might be a place to start.
What would happen if we changed the rules? (Score:2)
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
Wrong question (Score:2)
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.
Re:Solving Chess (Score:2)
Re:I don't understand the question. (Score:2)
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.
Re:I don't understand the question. (Score:2)
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.
Re:Chess vs Go (Score:2)
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.
How do Humans Play Chess? (Score:2)
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
I always liked this idea... (Score:2)
"Pawn to king's knight four. Mate in seventy-two."
That would be pretty freaky.
Absolutely true. But absolutely impractical. (Score:2)
Also. (Score:2)
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.
--
If you belirve in distributed computation. . . (Score:2)
Pfft! (Score:2)
Re:how to determine the perfect game of chess (Score:2)
I can't believe I just said that.
Re:Some numbers..... (Score:2)
Computers aren't better at chess (Score:2)
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."
Re:Some Perfect... (correction) (Score:2)
Sorry, URL missing. Should have used "Preview".
Ken Thompson's web page is here [bell-labs.com] and his page on chess endgames is there [bell-labs.com].
Insoluble (Score:2)
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.
Re:I don't think this should be determined (Score:2)
-----------
"You can't shake the Devil's hand and say you're only kidding."
Re:Perfect Game? (Score:2)
-----------
"You can't shake the Devil's hand and say you're only kidding."
Re:I don't understand the question. (Score:2)
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.
Re:Solving Chess (Score:2)
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
I've played some of the best. (Score:2)
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.
Checkers == Draughts? (Score:2)
Re:Chess vs Go (Score:2)
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.
Re:Solving Chess (Score:2)
Thanks.
Re:how to determine the perfect game of chess (Score:2)
Re:Perfect Game (Score:2)
If both players have full knowledge of the game, the first (or the second, depending on the exact rules) always wins.
Re:chess is not that hard, Go is (Score:2)
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?)
Some thoughts (Score:2)
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!
Re:I don't think this should be determined (Score:2)
--
No more e-mail address game - see my user info. Time for revenge.
Re:just a thought... (Score:2)
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.
Re:just a thought... (Score:2)
Re:Have you ever watched a game of chess? (Score:2)
"solving" chess... (Score:2)
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)
Re:I don't understand the question. (Score:2)
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.
Clarification: "Solve" (Score:2)
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
Take the best player in the world and . . (Score:2)
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 [ibm.com]
___
Re:Always take Woopie . . (Score:2)
___
You have the logic of klingon! (Score:2)
"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).
Re:I don't understand the question. (Score:2)
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.
Re: (Score:2)
Re:Some numbers..... (Score:2)
Anyone seen wargames? (Score:2)
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
Re:Some numbers..... (Score:2)
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.
Re:Perfect strategy for tic-tac-toe (Score:2)
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.
---
I don't understand the question. (Score:2)
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.
---
Re:I don't understand the question. (Score:2)
I dare say the fastest way to solve this is rather low-tech: stick all the grandmasters in a room with a bunch of chess boards and a truckload of Jolt...
After all, if you're looking for a strategy to win every time if you are (white|black), this is quite different than a sequence of moves. The aforementioned grandmasters could probably provide a lot of insight into this.
But if we're talking about a "perfect" sequence of moves made by white, played against a "perfect" sequence of moves made by black, with neither player making a "mistake," then a computer might be able to solve this.
The major stumbling block is defining what a "mistake" is. After all, there are numerous points in a game where one might make an unorthodox move. I believe these are called gambits. A computer might rate one of these gambits as a mistake, when in fact it is the key to winning the game. Some of these gambits might even involve sacrificing a piece, which a computer might rate as a "mistake."
So now I'm down to the question: what is a "mistake"?
---
Perfect strategy for tic-tac-toe (Score:2)
---
Using Trees Aren't an Option (Score:2)
Re:Why tackle Go instead of Chess? (Score:2)
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 ?
Formatting? (Score:2)
Re:I don't understand the question. (Score:2)
Imagine having God's own Beowulf cluster. Make every possible first move for White. For each of those cases, make each possible first move for Black. For each of those cases, make each possible second move for White. And so on. Every game must end in White winning, Black winning, or a stalemate. (I think ... IANACP, so maybe there are situations of infinite recursion. Can a chess game be chaotic?)
Out of all those games, find the game in which White wins after the fewest moves. Call this WW. Find the game in which Black wins after the fewest moves. Call this BW. Find the game in which a stalemate is produced in the fewest moves. Call it SM. Let N(g) be the number of moves to conclude the game g.
Due to HTML, I have to use "lt" and "gt" for "less than" and "greater than".
** If N(WW) lt N(BW) and N(WW) lt N(SM), then White will win.
** If N(WW) lt N(BW) but N(WW) gt N(SM), then Black will cause a stalemate.
** If N(WW) gt N(BW) and N(WW) gt N(SM), then White will cause a stalemate.
** If N(WW) gt N(BW) and N(WW) gt N(SM), then Black will win.
Since at every move, each player will take the move that leads to the most favorable outcome in the fewest moves, and since there is no element of chance in chess, the "best" game is predetermined. Given infinite knowledge -- or even just the really huge knowledge implied by knowing all possible chess games -- the game is "solved".
As noted, the key thing is the completely deterministic rules of chess. Given any initial board, all possible future derivative boards can be known, at least in principle. If both players have access to this database, then the requirement that they try to win forces them to make predetermined moves and thus makes the game automatic.
That's why I don't play chess. Well, that and the fact that any five year old could whup me at it. :)
Re:The problem is *storage* (Score:2)
Or so I think. I haven't done more than Sunday-paper thinking on it, though.
interesting (Score:2)
-----BEGIN GEEK CODE BLOCK-----
v.3.12
GCS d-(--) s+: a-- C+++$>++++$$ UL++$>++++$$ P+>++++$ L++>++++$ E--- W++$>++
Why tackle Go instead of Chess? (Score:2)
For a complete survey of Computer Go hit this link [uq.edu.au] 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.
Too easy for machines (Score:2)
Re:Solving Chess (Score:2)
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
perfect chess.... (Score:2)
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.
Re:Some numbers..... (Score:2)
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...
Re:Chess has already been conquered. Humans lose! (Score:3)
Re:Perfect Game (Score:3)
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.
Re:All things considered... (Score:3)
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
Re:I don't understand the question. (Score:3)
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.)
On some Go endgames computers can outplay humans (Score:3)
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
Just some tasty AI morsels (Score:3)
-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.
Re:chess is not that hard, Go is (Score:3)
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. [usgo.org]
Patrick Bridges
Arthur C. Clarke story on the solvability of chess (Score:4)
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 [ibm.com]. take a look.
-rbw
Solving Chess (Score:4)
Click here [mcn.net] for a discussion of the practical problems involved in solving the chess or checkers search tree.
Some Perfect endgames are known (Score:4)
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.
Perfect Game (Score:4)
how to determine the perfect game of chess (Score:4)
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.
Some numbers..... (Score:4)
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.
Chess has already been conquered. Humans lose! (Score:4)
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!
Re:Some numbers..... (Score:4)
That said, quantum and DNA computing bring an interesting light to it. Quantum would allow all the possibilities to be evaluated at once! All of a sudden, our exponential-time problem becomes solvable in polynomial time! DNA (I believe) cannot guarantee us the correct solution (excuse the pun), because in many ways it is "probabilistic" - you can set the probabilities as low as you like though, by using enough of the "reagents", but you cannot guarantee you have the perfect answer. [flame me if I'm wrong here! =]
So yeah, it's more likely that people will be able to forge my PGP signature before they can solve chess.
-- Maz
Re:Some numbers..... (Score:5)
According to his calculation, a perfect computer kept at background temperature, powered by the energy from a perfect Dyson sphere around our Sun, could do 2^187 bit operations in a year.
All the energy from a supernova could power such a computer to do 2^219 operations.
10^120 = 2^398 is 8*10^53 Supernovas, or the annual output of 3*10^63 Sun sized stars. Something tells me that we can have as many quantum and DNA computers as we want, chess will hold out.
-
We cannot reason ourselves out of our basic irrationality. All we can do is learn the art of being irrational in a reasonable way.
Not true (Score:5)
Have a look at Branch and Bound [sandia.gov] 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
Chess vs Go (Score:5)
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]