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."
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)
To repeat the classic tagline:
.org sites )
My computer can beat me at chess but I kick its ass at kickbox.
( I post my insightful thoughts on real
Sorry, Chess can be solved. Sure, it's a lot harder to solve than tic-tac-toe, but fundamentally, it's the same maths involved... Probably with current technology, it could be solved in a few decades if there was the money to do it (i'm talking hundreds of billions of dollars here). As computer tech gets fast and faster, it will become more affordable to solve chess. I'd be very suprised if it couldn't be done in less than year for a few million dollars in 2100).
If you know enough about the game, watching a blitz (10 min game) tournament with good players can keep you on the edge of the seat.
Given the complexity of chess, and the heat death of the universe, there will be no such point.
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.
Standard, 2 dimensional, 9 square Tic-Tac-Toe, played perfectly by both sides, is a no-win game, and the onus is on black to lose it. If white plays the center, black plays a corner. If white plays anywhere else, black plays the center. Beyond that, it's still codifiable, but it'll take me longer to write up.
--
Ben Kosse
Remember Ed Curry!
Sorry, no. You're mixing up two different rules -- and you're close, but not quite.
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.
Umm. You're wrong. While there almost certainly is a "perfect" game of chess, all it would take would be for the opponent to not use one of the scripted moves -- while it would, by definition, put him at a disadvantage, it would then require skill, not memorization, to see what the disadvantage was, and the scripted game would be in the circular filing cabinet.
Well, what I mean is that the perfect strategy doesn't really mean playing to win. I am thinking about the Star Trek episode where Data finally beats some game master just by playing for a draw and not to win.
It's a little offtopic but still interesting...
/* We dance to the sounds of sirens and we watch genocide to relax*/
There are a finite amount of moves and board positions in chess. It would appear that either DNA or Quantum computing would be able to solve the problem.
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.)
It kind of pisses me off when people say that humans are better than computers at chess. Humans aren't better, they are different.
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.
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?
But they'd be dead after only a few days without food....
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.
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.
I'm a poor player, but I'll strut and fret for an hour, if you like.
The universe is about 15 billion years old, and there are about 19^79 atoms estimated by physicists. Do the math yourself.
Youd only really have to store the game trees that are _candidates_ for the solution. Game trees that result in losses can be pruned.
I don't care if it's 90,000 hectares. That lake was not my doing.
Of course, Shakespeare was a homo sapiens sapiens--a glorified bald monkey. So we know that the works of Shakespeare can be created by just one monkey in less than 52 years--if it's the right monkey.
I don't care if it's 90,000 hectares. That lake was not my doing.
Just to correct mistake I've seen a lot of people make - When solving a game by building a game tree and then searching all possible lines for one which produces a certain victory, it is not necessary to store the entire tree at once. If you use the basic algorithms for solving a game tree, like MiniMax or AlphaBeta, you generate the game tree recursively as you go, depth first. So at any one time, you only have N board states in memory, where N is the number of moves into the game you have calculated so far. You would also need a list of moves you have already tried so far, and the outcome (win, loss, draw) associated with each. Assuming a game lasted 200 moves, and a 100K to keep track of one board position,
a PC would do fine on memory. The problem is simply one of time, as has already been discussed.
Out of curiosity, how many people are required to take an AI class as part of their CS degree?
Interesting facts:
More information, can of course, be found at the University of Alberta's Chinook Web Page
"You know, Hobbes, some days even my lucky rocketship underpants don't help" -- Calvin
It has in the past been quite popular for spectators. It isn't really part of the social background of most people to watch a game of chess. It is for some though.
I remember watching a bunch of guys play on one of those big boards they have in parks some places. There were a fair few othe people watching as well. It's less boring than say, cricket. Or baseball.
There are several problems that, by their nature, can only be solved by the exhaustive search method you have proposed, or more accurately, an optimised search heuristic. I have never heard of chess being included in this class of problem.
It shouldn't be necessary to examine every possible branching that exists. You can eliminate stupid moves at the start, such as moving your bishops all the way to the other side of the board.
It would be better to write a program that only ever chooses sensible moves, and thus eliminate the need to filter out dumb moves. This is no particular leap of logic. It is plainly obvious. It also cuts a large swathe out of your search space.
I really don't think that discussion of branching factors is necessarily relevant to the problem of solving chess. It is an impressive way of indicating that the problem is difficult, but it isn't all that representative, really.
Assuming that problems should be solved by an exhaustive search, or even a heuristic, may be a form of computer-brutishness. The assumption that this is the ideal use of resources to solve a difficult mathematical problem may cost valuable time and ultimately prove futile.
I think the people who build the computer and write the software that solve chess will get far more respect than the computer itself. I'll start worrying when computers can write their own software, but not much.
The perfect game doesn't necessarily mean a win every time. It means that the worst you can do is a draw, as in tic-tac-toe.
Shortly after discovering tic-tac-toe, every kid solves it and never does worse than a draw. Well... most kids.
Same principle for chess.
Frankly, I don't think solving chess is that far off. There are a lot of moves, but there are only 64 squares on the board, and most pieces are restricted to a much smaller set of those squares. As the poster from 'way up there said, Go presents a much more difficult problem.
B
do we really need chess solved? I mean grandmasters are always saying that for the good of the game we shouldn't develop computers that play it.
besides, there is a much more important question: is every sparting position of FreeCell solvable?
I was thinking of how to intentionally fail my drug test... It would make a good memoir story someday.
If you never move your pawns, you'll never lose.
--
RumorsDaily
Lets hope that computer technology will never be so high that A Perfect Chess game will take place, because othervise the game of Chess won't be interesting anymore. C'mon, that's like saying tic-tac-toe isn't fun anymore. Or the box game. 8)
A planet where apes evolved from men? Long live the apes.
You know those chess problems where it says "white to play and mate in two moves". Well if chess were solved you would see a chess problem showing the opening position saying "white to play and mate in 100 moves" or some such. In other words you could say before the game starts that if white plays perfectly he will always win. Or maybe black will always win. Or maybe if black and white play perfectly it will always be stalement. One of those three outcomes, but which we don't know till chess is solved.
It doesn't look like chess is going to be solved anytime soon, but it doesn't mean chess is unsolvable. There are still some directions to look at using conventional computers.
One possible approach is dealing with the game symbolically. What does it means? Instead of scanning the whole possible run-tree of the game, or at least most of it, the way it would happen using conventional a-b-prunning techniques to unlimited depth, it is possible to describe a group of states in a symbolic way and thus scan huge number of games at ones.
This technique is commonly used in the domain of formal verification (also known as "model-checking). When we wish to prove a property on a protocol or hardware design that may have 2^100 states or more, it is impossible to solve it by going through all the states. Instead, the state space is encoded using a symbolic representation called BDD (binary decision diagram).
I would expect BDDs to fail in the case of chess. However, if we find the right symbolic representation, the game may be solved.
Sela
Move 5 is wrong in your example. X needs to block O at left center, then O blocks X at right center, and from there nobody can force a win.
Branch and Bound is an interesting technique, but it won't help you in chess. I work in computational biology, where some biological problems are simulated through recursive searching through trees (i.e., something like protein threading). I know people have used branch and bound for that problem, and it doesn't make exponential problems possible to solve (although it may help the running time for some things). The point is, it's hard to predict how branch and bound will affect your search.
For that matter, what is branch and bound? You're pruning elements of your search tree that are _provably_ worse than the optimal solution. I think you could do this in some cases in chess (i.e., you can prune trees which lead to loss immediately, perhaps) but I can't see how you'd implement it to be able to remove massive sections of your search tree, enough to make the problem feasible... that's the whole point of chess: sometimes a move looks bad, but you have to investigate (i.e., search) to find out for sure.
Branch and bound is interesting, but I don't think it's applicable here...
"The horse leech's daughter is a closed system. Her quantum of wantum does not vary."
Being the poster, I assure you I am informed. I did not have at hand the absolute number of positions available, but I knew that it was far more than any current computer could ever solve. I doubt that DNA could do it, but I really don't know much about how that works.
Personally, I think that if Chess is ever solved, it will be done by a Quantum computer. These things have phenomenal calculating abilities - ones not dependent upon having enough atoms to store the 1 or 0 - because they simply use a 1 AND 0.
Linux - Because Mommy taught me to Share.
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.
Don't feel too bad -- I'm doing just that (w/o the beowolf cluster, just one computer's idle cpu time) to calculate how long it would take to randomly write out the works of shakespeare (hint: so far it has taken around 9 days just to get 9 letters.)
POWER processors would probably be used instead of the PowerPC procs... a subtle difference, but they *are* different chips... if you are going to go parallel, you gotta use the best available.
"It's tough to be bilingual when you get hit in the head."
Strangely, this isn't the case. I think that chess is solvable. The depth of the tree alone does not make it unsolvable. It does make it hard to find the solution (probably impossible for all intents and purposes) but it doesn't mean it doesn't exist.
Branch and Bound is an interesting technique, but it won't help you in chess.
Right. I did say that in my article, but it bears repeating. It was meant as an example of how the raw number of games is not necessarily relevant.
--
Patrick Doyle
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
Ok, so you only have to search 1 percent of the game tree. Now, lets do our freshman computer science math here, kids: .01 * (35 ^ 100) = (an intractable runtime)
(Ok, please try to see the point I'm making instead of getting lost in the example.)
Who said it's 1 percent? What if it's 1/(35^98) of the game tree?
The point is that the total number of games doesn't matter because you may only need to search a tiny fraction of them. How tiny? I don't know. The point (again) is that you can't argue that solving chess is impossible because of the huge number of possible games.
I could use the same argument to claim that adding 1+2 is impossible because you'd have to search every possible integer answer. It's just a ridiculous argument.
Got it?
--
Patrick Doyle
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
"If you put an infinite number of monkeys, working on an infinite number of typewriters eventually one will bang out the script to hamlet"
Actually, if you have an infinite number of monkeys, you could even say that an infinite subset of them will immediately produce Hamlet.
I think the original monkey theorem was that 1000 monkeys on 1000 typewriters will eventually produce Hamlet.
--
Patrick Doyle
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
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?
Um, that's precisely the point of the question: can we "solve" chess and say that there is a way to play that always wins?
We have our answer for tic-tac-toe, for instance. The answer is no. A perfect player cannot force a win.
The idea is to answer the same question for Chess.
--
Patrick Doyle
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
Ok, to be more clear, mass-energy is conserved. When you convert from mass to energy or from energy to mass, you have simply changed its form.
My point is that you can never "run out" of energy in the universe, as long as you can continue to recapture it in whatever wasteproduct form it occurs.
Doug
Venn ist das nurnstuck git und Slotermeyer? Ya! Beigerhund das oder die Flipperwaldt gersput!
There's already an RFC for a new Infinite Monkey Protocol...
ftp://ftp.isi.edu/in-notes/rfc2795.txt
((lambda (x) (x x)) (lambda (x) (x x))) http://www.endpointcomputing.com a scientific approach to custom computing.
Let's bust some myths about computer chess:
Think of it in an AI perspective; the game is just another search space. Sure, the space is infinitely deep, but a good algorithm will recognize when an infinite branch is reached and make the appropriate decision. Chess's complexity is not increasing, but computers' power is. Chess will be solved some day; it's just a search problem.
Again, think of it in an AI perspective. On average, the winner will be the computer that examines the most search space and implements the best tricks to guess what lies beyond the examined search space. Once computers are powerful enough to examine the entire search space, all such computers will be equally matched.
We simply won't know for sure until the entire search space has been examined.
Washington, DC: It's like Hollywood for ugly people.
That doesn't actually prove anything (although it is an important point to bear in mind). We already have minimax algorithms for pruning the tree (discarding whole branches at a stroke). If someone came up with better pruning algorithm, chess might become solvable.
Female Prison Rape in NY
Female Prison Rape in NY
Female Prison Rape in NY
Female Prison Rape in NY
If you had read the earlier posts, you would know that certain sections of the tree can be discarded. Specifically, those sections that lead to an unfavorable outcome. The set of winning games is smaller than the set of possible games.
The point isn't to construct the whole tree, but rather the solution as expressed by the tree. If part of the tree doesn't express a part of the solution, why do you need it?
> The search tree for chess has more nodes than there are atoms of the universe.
Then maybe it's not appropriate to use a tree. Why not use a graph? Each node could represent one unique layout for the board - with a graph, there would be no need for this kind of redundancy.
So, uh, anyone know how many ways you can put chess pieces on a chess board?
> There's more to a board position in chess than the layout of the pieces.
I have to agree, but if I'm not mistaken a second time, the extra information you're referring to should be storable separately from the graph, and would be at most some constant amount. We can count to 50 with just one byte, for example. Only the graph risks becoming very large.
This approach wouldn't reduce the number of traversals needed, of course, so time would be just as much a factor.
So I guess a perfect player could always draw, but not strictly in the context of a zero sum two player game.
--
Here's an example of a twisted chess game such that all first moves are disadvantageous... The board is 5 squares wide and 1 square high:
- WK WQ BQ BQ BK
Where WK is a white king and BQ is a black queen. Granted, normal chess doesn't seem to be like this, and it might be possible to prove that it's not. So I was wondering if such a proof exists.Relative to what? Well, if you assume that white and black both can forsee all moves and will choose the best possible move... then a disadvantageous move would be a move that would result in a loss, where maybe abstaining from a move would result in not a loss.
--
If Shakespeare's works are n characters long in total, then it would take 38^n tries to get it right ( /[A-Z0-9. ]{n)/ ).
If it takes t seconds on average to type out n characters, then it will take t * 38^n seconds (or, slightly past the end of the universe) to type out Shakespeare's works.
Given m monkeys, that's t * 38^n / m seconds. If m == infinity, then the entire works will be typed out instantaneously.
Does anybody have a good bulk rate on monkeys?
--
At each board position, there are probably more possible random moves than there are legal moves, and it's probably easier to generate a list of legal moves than it is to generate a random list of moves and then check each for legality.
Or, more likely, set a network of computers to all play against each other. Use some AI to have them "learn", and realise what they did wrong in the past, and what they should do better in the future.
That's a greedy algorithm though. It's possible that you'll miss an important subtree doing that. Don't you have to try every possible way of doing it?
Given enough time, either all games should end in stalemate, or white would win all games.
Is it theoretically possible that black to win them all as well? For every move that white could pick, there exists a black move, such that if black plays intelligently from there on out, black will win? (or \forall white_1 \exists black_1 \forall white_2 \exists black_2 black-will-win, or...)
--
Hrm. I could be wrong, but... this page, titled "Zero-Sum Two Person Games of Perfect Information" starts off by saying "The almost perfect example of this type of games is chess."
--
Well, within the context of perfect knowledge zero sum games, it's possible for the 2nd player to always win given a perfect strategy... the game may be such that all first moves either give no strategic advantage, or they're actually disadvantageous.
I believe the Game of Nim is one such game?
So my question was... is it possible for chess to be such a game?
--
If every possible move is disadvantageous, then the game is at fault, not the player, so yes, it would be a perfect move.
--
Chess is not a hard problem computation wise, it's long.
:)
But for example, checking the victory condition is easy (can the king move).
Now, take the game of Go... it's much harder to figure out the victory condition. There are currently no computer Go program that play very very well (I think the best if first dan?)
Now, that would be an interesting problem to tackled down
Yes, checkers is draughts. I think that this is an American vs. British naming thing.
tangent - art and creation are a higher purpose
postmoderncore - art and creation are a higher purpose
Strategy has nothing to do with this "perfect computational game". It is merely a matter of finding moves which always win.
In practice, one player often has a better strategy, but still loses due to a tactic (ie. clever move, perhaps against the run of play) which the other player finds.
Your claim is that the chess-game tree is not finite. I think that it is, and here's my reasoning:
There are certain rules in the game that ensure that after a fixed number of moves, something has to be substantially differrent. Since there are only finitelly many states (configurations of the chessboard), there are only finitelly many substantially different states.
If you have the entire tree, you cansolve the game.
Jan
Because it is finite.
You can use very standard game-theoretic strategies to 'solve' the game of chess, by simply assigning a value to all the nodes of the game-tree (valid states of the game), beginning at the end-states and working your way up. The value of a node decides which player (if any) has a winning strategy. So, all you need to know to play a 'perfect' game of chess, is the entire game tree.
This is obviously not possible, but all contemporary chess-playing programs are an approximation of this -- using statistical data, you can predict the value of a node (using both simple rules such as 'a situation where you still have your Queen is usually better than a situation where you don't', and more complex rules such as 'a situation where the chance that in 10 moves you will lose your Queen is greater, is usually not good'). So instead of knowing the value of a node we predict it using simple statistics. This will obviously never result in a program that really 'solves' chess, but will result in programs that are much better than 'mere' humans...
Jan
yeah, as far as i know, there are ppl like this in China and Japan and Taiwan
If we had an enumeration of strings in English, each Monkey i could type out works (i-1)*1000+1 through i*1000.
Still an infinite number of monkeys, but they each have to type out 1000 works, instead of 1...
(although I'm not sure how we swing it if they're typing randomly...)
--
Repton.
Repton.
They say that only an experienced wizard can do the tengu shuffle.
Checkers has not been solved.
Supposedly, C. Scientists predict checkers will be solved sometime this decade.
Chess, however, is unsolvable. The search tree for chess has more nodes than there are atoms of the universe. Good Luck!
Felix
------ Warning! You are too close!
For what is being suggested we calculate, we wouldn't need nearly that number of operations. In fact, all we need to know is a very small of information (whether the game is a win for white, a win for black, or a draw) at each of the 2e43 positions. Once we've backtracked far enough to find that information for the initial position, we have solved the game (i.e. we know whether, given perfect play by both players, who would win).
If we wanted to keep the entire tree in memory, as we would need to do to make a machine which could play chess perfectly without doing the entire calculation at each move, that would be rather impractical.
The brunching shuttlecocks has a page about this topic. Very funny stuff.
Trees can't go dancing
So do them a big favor
Pretend dancing stinks!
There exists some optimized algorithms that make it easier.
For example, you could do a depth first search, so that you dont have to keep every node in memory - only keep the nodes that you expanded.
And you can use Alpha-Beta Pruning to reduce the number of nodes you exapand.
You can also search in parallel. Ofcorse there are problems when parallelism is introduced..
Actually, IIRC, checkers has been solved completely. Even though it at first seems that the search space will be mind boggling (like chess), the fact that all the pieces in checkers are the same makes it tractable.
As for chess, there are numerous posts above which indicate how vast the number of possible chess games are, and it is very unlikely that they will all be explored.
What might be imaginable, though, is for computers to identify patterns which allow this space to be pruned enough to make it traversable.
This /. story makes a mistake in calling for Beowulfs or distributed.net projects - these only work if your problem is not exponentially vast in the way chess is. Instead, it would be more interesting to have a really clever computer program (running on a more modest system, perhaps) which was smart enough to identify the right patterns in the system...
Fixing copyright
The average dog distinguishes between a leg and a tree with his eyes closed and probably thinks a peg is closer to a tree than a leg.
I'm not convinced. Suppose the game is white-to-win. Then what we need is a single "killer response" to each position black is able to reach. We already have one useful degree of freedom: we can select the set of killer responses based on some heuristic for minimizing the total number of positions which black can force us into (based on fore knowledge of our own responses). The first approximation for white is to select, whenever possible, moves which reduce the board "complexity" (number of pieces remaining, pawn advancement, legal castles, etc.) and responses which "force" a known response from black.
It's not at all an easy matter to estimate how much white, playing from within a set of unlosable moves, can curtail black's daliances.
Most likely we only need to store responses for the portion of this space where black plays a sensible defense. Any positions where Deep Blue can compute mate for white in under two minutes will not need to be stored in the kill database. Attempts by black to explode the size of the kill tree by playing "scambled eggs" are likely to soon lead us to a position where we can fall back to a computation in real time.
And finally, the most important asset is that we aren't tying to compute winning moves. We merely need to find a killer response which lies within the curtailed space which white's kill strategy permits the game to reach.
For example, we might examine this space and discover that white can always force victory without certain pawn structures ever being attained. All positions containing these excluded pawn structures are excluded, as are all positions allowing black to reach such an excluded position.
A recursive mini-max heuristic to "guess" the killer response can be devised on this principle trading off between space and speed. A recursive search returns an ordered list of moves for white ranking according to the probability that the move is the desired killer move. Bear in mind that this heuristic is equivalent to the heuristic which Deep Blue uses to play chess exceptionally well already, but with the benefit of a vastly more powerful set of pruning rules.
This computational heuristic could conceivably produce on computational terms the desired killer move in 99.99% of all positions we might need to evaluate, and 95% of all positions which might regard as constituting a "spirited defense". In one out of twenty positions our killer response database might need to store an override suggesting that the second (or third) ranked estimate be used in favor of the top ranked default.
The storage requirements would then be a small fraction of a bit for each position reachable within a space which is vastly constrained relative to the open game of chess. Computing the killer perimeter in the first place is vastly more difficult than contriving to make perfect moves from within this space accessible in real time.
I can't resist the urge to stick a pin in some sloppy thinking which permeates this chess thread.
Suppose we invent a new game called Chess' (chess prime). In this game white either opens with a valid move according to the rules of Chess, or white simply announces "checkmate" and wins instantly. Chess' has the same size position tree as Chess but I think we can all agree that Chess' is a bit easier to solve. Some people are way too size-centric in their approach to life.
Screw the monkeys, but the concept is pretty good. Randomly playing chess moves, when a computer sees that a certain move is good, take a note of it.
Or, more likely, set a network of computers to all play against each other. Use some AI to have them "learn", and realise what they did wrong in the past, and what they should do better in the future. Given enough time, either all games should end in stalemate, or white would win all games.
Grades, Social Life, Sleep....Pick Two.
--Justin Mitchell
"2nd Place is a fancy word for losing" --Bender (Futurama)
Well, yeah, random legal moves....
It would, unless it finally played enough games for another computer (or human, for that matter) would figure out a way to beat that, if not by any other way, by randomly guessing. And, yes, that could mean possible trying every way to do it...
And, no, it's not possible for black to win a perfect game (both sides play perfect, that is). White goes frst, therefore has an advantage, the best black can hope for is stalemate.
Grades, Social Life, Sleep....Pick Two.
--Justin Mitchell
"2nd Place is a fancy word for losing" --Bender (Futurama)
If a first move was disadvantageous could it be a perfect move?
Grades, Social Life, Sleep....Pick Two.
--Justin Mitchell
"2nd Place is a fancy word for losing" --Bender (Futurama)
It's theoretically possible.
Consider that there are a finite set of states in chess, based on the position of the pieces and whose move it is, whether or not a given King has moved, and how many moves there were since the last capture or Pawn move.
Then, there are a finite number of possible moves per state. Ergo, there are a finite number of possible policies -- each being an assignment of moves to states. Assignments may be partial because with most possible policies, many states will be completely unreachable and thus irrelevant. For instance, if a policy insists on sacrificing the Queen within the first 8 ply, then no states involving that Queen need be considered afterwards.
An optimal minimax policy is one such that versus an optimal opponent, your outcome is the best possible. For instance, in 3x3 Tic-Tac-Toe, any play but the center will allow an optimal opponent to force a win, IIRC. The value of a center play is "draw", simply because against an optimal opponent that is what will happen. That the opponent could hand you a win via a suboptimal policy is irrelevant to minimax.
It is theoretically possible that there is an optimal policy for Black such that no matter what White plays for the first move, that Black can force a victory. This seems unlikely, but possible until it has been mathematically evaluated.
See 3x3 Hexapawn for a simple game in which the first player is guaranteed a defeat against an optimal player.
Only the dead have seen the end of war.
Don't forget the 40-move rule. 40 moves without a pawn move or a capture == draw.
Plus, the time limits...
Only the dead have seen the end of war.
You'd have to memorize an entire policy -- basically, a move for every reachable state -- not just a set of moves. I doubt any chap could pull that off....
Only the dead have seen the end of war.
always someone to rain on your hopes, dreams and aspirations.
Now I have to revert to my previous career track of truck driver.
bah.
What I got out of the article, is that they wanted to see if one player always has an advantage over another. Take the classic AI example of last one loses. Two players start w/ a stack of 7 toothpicks/chips/doritoes. During each person's turn, they have the ability to take one, two, or three items. It can be proven by expanding the game tree (96 nodes from the simple scenario) and doing and/or calculations on that tree, that the player who goes first can always win, provided that they make the proper moves. If this is the case w/ Chess, then the size of the game-tree is going to be mind-boggling huge, and would require the resources of several Beowolf clusters, for several months/years (I forget the computational power of a single cluster. Rough approximation :)
You can't move back and forth infinitely because there is the repetition rule. I you and your adversary go through certain number of moves without giving check or taking a piece then you have a draw.
Given the complexity of chess, and the heat death of the universe, there will be no such point.
Except that you do not know the boundaries of what will be computable in the future. New discoveries in physics, or even mathematics, could change what is computable.
Take quantum computing.
Heck, we don't even understand how our own brains work.
Computers will be stronger simply because they calculate longer and accurate variations.
Even games between the strongest chess programs are full of terrible positional and strategic mistakes, this will probably always the case.
Computers will calculate longer variations until all possible winnable combinations have been computed. At that point, computers will have determined the game of chess.
Without looking at every possible move (intelligently, yes... for instance, if the move ends in checkmate, or infinite loops, stop), you can't prove that a given move is the best.
A computer will provably win if it looks at all possible moves (or at least provably do the best in the current situation).
because if there is a perfect game of chess, all someone has to do is memorize it and the game is theirs. It makes for a much less interesting game. It's probably a very complex thing to memorize, though, because the other player has the freedom to move where he wants, so there would have to be several branches at each move.
But then again, I disagree with people who get books of chess moves and strategies, memorize them, and play them. It takes all the fun out of having to figure out what the best move is each turn. To me, chess is a game of skill, not memorization.
But I have no control over these people, so they can read all the books they want and maybe even try to discover a perfect game.
--
Seeing is believing; You wouldn't have seen it if you didn't believe it.
You are spot-on, Sunday-paper thinking or not.
Think about doing a complete search. The first game you run through White wins (say). Back up one move and analyse all the responses Black could have made. If just one of them leads to Black winning, you can back up one node in the tree without need to store the positions along the White win branch.
You still need to store quite a bit, though. The point is, I guess, that we don't know how much, so we don't know if it is theoretically possible.
Still, there might be other proofs, that do not requite a complete search. That would be neat.
Hi!
Chess is what is known as a "perfect information" game; that is, all the necessary information to the solve the game is known, since there are no other events except standard moves and no introduction of new pieces or "information." Therefore, chess is certainly a solvable game, although solving it with brute force is not currently practical.
Because it's all about the tree. Like a hiker leaving his mark on a tree to find his way back, If you delete the tree from state as you drill down, you'll find you're answer, but won't have the path to return.
Even if you move parts of the tree off to disk or other media, you still need it in state. How big? 100. 35 ^ 100. I believe that what the original poster was trying to say is that solving chess "doesn't scale well".
___
A tree of just 50 moves would have 10^120 nodes.
___
Then where would you put it? In another hydrogen atom? If you have a section of the tree the program is not currently working on, it can be off-loaded, but can never be discarded.
___
Vision alone may be difficult, but I can't imagine a reason why you would want to create a vision only solution with so many examples in nature of a "multi-sensored aproach".
In industry, for example, vision is used quite extensivly to do quality control and gather SPC numbers on the fly. These vision systems are employed using fixtures to hold the part steady (hands) and proximity sensors (feel) to tell when the part is infront of the camera, thus telling the camera when to "look". Without these compliments, vision alone would be almost useless.
As in nature, the answer lies in a, dare I say it, a Beowulf cluster of sensors teaming up to compliment each other in order to find a solution.
___
For many years chess was thought of as the ultimate problem to check for artificial intelegence. Recent events (such as Kasparov's loss to a machine) showed that this problem is doable.
The biggest problem now lies in the field of computer vision.
Consider this example: Even a dumb dog can know the difference between a leg and a tree. How many people can write a computer program that can distinguish between the two?
It might surprise you, if you are a programmer, but try to do it. Grab few pictures from the internet (or from you webcam) and think how would you solve this. No computer-science major/geek/whatever knows how to solve this in a reasonable way.
While chess has defined rules and possibilities, a picture can have any value - and it's not clear how we humans interpret this information.
Another example is optical character recognition (OCR). In order to understand hand-written script what did people do? Here is a hint: think palm-pilot. Yes... since it's too hard, the solution was to "train the monkey". That is, you, the user have to type one character at a time, and not regular characters but special characters.
Most of these problems have no known solution yet. It is not a problem that can be solved with huge computers.
Did you wonder why we don't have fully automated appliances like in Futurama?
For examples of some neat things that can be done, check this page.
n = num of characters including spaces in work
k = number of keys on given typewriter
k^n would give you the number of possible combinations (if you think of the work as one ungodly long password), but how would you factor in the functionality of the monkey[s]?
ZEN is a prime number in base-36
Two players start w/ a stack of 7 toothpicks/chips/doritoes.
btw, I thought your comment was interesting, and I am just having a little fun.
--Scott
Maybe it's just me (it usually is), but can someone please explain to me what the purpose of finding the perfect game would be?
I don't know about you people, but I spent many, many afternoons of my childhood with my dad playing chess. I can't imagine anyone wanting to play chess anymore if all you had to do to win was memorize a long set of moves.
BORING.
Imagine:
Man: "Oh good move."
Boy: "I know. You too, that was a good move."
Man: "Do you really want to finish playing this game, boy?"
Boy: "I guess not. It will be the EXACT SAME GAME the next time that we play, right?"
Man: "Right. Wanna play Risk?"
Boy: "Sure."
So basically solving chess would kill the game. Personally I would rather not know.
Rami James
Pixel Pusher
ALST R&D Center, IL
--
rJames.org - illustration
I imagine they will start out testing some of the better known defensive openings. Even if they don't find a perfect game, we might get some hard number weightings for the strength of a few openings.
Actually you could have used < and > with surprising ease.
Chris.
chris@printf.net
what sort of algorithms are these machines going to use to reach this perfect game? sure, its nice to be able to compute the next 4 trillion possible moves, but i think once we get the computers playing eachother a genetic learning alorithm could be developed in order to find out what the perfect game is. by recognizing an patern, the computer could then eliminate many possible moves (with an exponential amount of following moves) from the ones it has to calculate.
---
/bin/fortune | slashdotsig.sh
In order to create a system to play to perfect game of chess, we need to first define the goal. We should certainly go beyond the standard primary objective of capturing the king since this seems to be a little vague as a goal for a 'perfect game'. So what should be the secondary and tertiary objectives?
Is it a win in the fewest moves? [how boring]
The fewest number of pieces lost?
The most opposition pieces captured?
Prolific and creative use of established chess strategies? [this would certainly give chess color-commentators something to talk about]
The most entertaining to watch?
The most elegant? [certainly the most challenging]
Maybe it would be helpful to first define the 'worst game'. I think the 'worst game' is not the game played by someone with a death-wish but the game played by someone with no knowledge of chess. In this way, the worst game consists of entirely random moves. The opposite of random is ordered and therefore the perfect game should aspire towards order.
That said, I'm not sure if an ordered game could be quantitatively measured - how would a win in fewer moves be considered any more ordered than a win in a longer game? Elegance and proper observance of the history of the game fall into the category of 'ordered' more readily but are much more subjective and harder to code.
Mmm, sunday for coffee and slashdot.
Jason.
Don't discount the amount of money that the video games industry is able to contribute to a problem. Their contributions towards 3d imaging were very helpful. I'm sure they'll play at least a supporting role in the development of pattern matching/recognition programs. After all, while chess is very complex ( I was undefeated in regional competition during H.S. ) it's important that computers be able to function in an environment where it isn't possible to calculate all possible moves. It's a different kind of thinking, and a type of thinking which is very important if a program is ever going to learn to interact with the real world._ ____________
_______________________________________________
___
It's the end of my comment as I know it and I feel fine.
God I hate it when people say this!
Gary Kasparov lost a 6 game series under strict conditions that are not comparable to tournament play. In this one match, under these specific conditions, Deep Blue manage to best Kasparov. But a rematch, or any furthur games, were refused, and here is why.
Computers tend to play predictable styles; it is the nature of programming an AI into a game. Human's, being adaptive, can change their own play to take advantage of this. This is why the match was so short, and this is why there has never been a rematch.
Until a computer can beat grandmasters consistently, at tournament style conditions, it ain't fair to say computers are better at chess than humans. Now, it is certainly fair to say that computers are better than 99.9% of humans, and that 99.9% of all chess playing computers are better than me!
But to 'solve' chess you would need to construct a tree of a forced game from start to end, accounting for all possible moves by your opponent. The problem is that even now I don't think computers can go farther than 10-12 ply (1 players move) even with huge amounts of power and time. You'd probably need 45 ply or more top solve chess, so who knows, maybe? I'll leave that question to those more knowledgable.
Cheers
--Pete
He felt himself break into two halves, one part warm and one part cold, one part hard and one part soft, one part trembling and one part not trembling, each half grinding against the other.
--Ray Bradbury
www.avacal.com -- the home page of pete shaw
Okay, so maybe the networked computers would work better in this case. But to add back in the risk factor, "kill" the nodes that lose, but clone the winning algorithm onto that computer. That would improve much faster, because the computing power would still be fully intact, but each computer would not need to independantly discover the winning algorithm. It would be like a Beowulf cluster, but competitive. Hey, lets apply this to other parallel-processing projects! Maybe if d.net did this, not only would they successfully factor the key, but they would come up with an algorithm that could do this in a short amount of time! Cool, huh?
I actually did something similar once, but with Connect Four, and the two opponents on the same computer. I had written out a Scheme program to play Connect Four and embodied a computer player in a stand-alone object (for more information, see The Schemer's Guide). They used a backtracking evaluation system and a database of knowledge about which moves to make given a certain situation. It was, of course, a simple matter to have them play a good number of games against each other. Then I (or an innocent bystander) would play the one that had won the most games.
The problem was, of couse, the computing power necessary to accumulate enough knowledge to be able to play a perfect game. The first problem was that my objects were written in an interpreted langauge and I had not compiled them. The second problem was the processor I was running them on -- my dad's 166 mHz laptop. Third, my algorithm was sub-optimal -- for one, I didn't check if the currect game position flipped was already in the knowledge base. But even counting these restructions, solving even a 4x4 board takes a lot of time. And Connect Four is an extremely simple game in comparison to chess -- there are at maximum the same number of moves as there are rows, and often less because rows are full or the player can easily find whether or not that move will cause the other player to win next turn. So imagine scaling this to chess. They might find a perfect algorithm the same time they find the last digit of pi. (Do you suppose that it's possible that pi, while never repeating, falls into some predictable pattern after a heck of a lot of digits? Sound like a parallel computing project?)
It kind of pisses me of when people say that computers are better than humans at chess. Computers aren't better, they are different.
It kind of pisses me off when people say that cars are faster than humans. Cars aren't faster, they are different.
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.
Why should I be impressed that humans (including myself) can't coherently explain how we figure out what move to make?
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."
That's the whole point of solving the game. For chess to be considered solved, each branch would have to be examined all the way to the end of the game (or mathematically proved to be equivalent to a branch that had already been solved), no matter how stupid the move might look.
No, because the "best player in the world" is not necessarily the best human player there will ever be.
===
-J
Karma: T-rexcellent.
...that as someone has already pointed out, you need both sides making the best moves possible to test your "perfect game." But if both sides are run by the same program, won't they stalemate each other? Or something?
===
-J
Karma: T-rexcellent.
Chess is an intractable problem, and this is well known. We can make progress in solving endgames, opening books, powerful chess computers, etc. but the game can't be solved, guys.
There are already more possible board positions than there are electrons in the universe after 10 moves. Without quantum computers, searching for (not to mention storing) this "perfect game" tree is just not possible.
Why is it every time a story is posted on slashdot everyone has to chime in lets get a Beowulf Cluster of these things running, or lets run linux on it?
I am into the copy and paste.
Well being a troll does not mean you have to stop being original.
I am into the copy and paste.
Chess is somewhat more complicated, but a similar "solution" is possible - the main theory is that you determine "book moves" for start AND end positions, and put some AI in the middle that tries to get you from your current board state to a state where you already know you can't lose (i.e. can force a win or draw).
Easier said than done of course, but the main point to consider is that you don't need to calculate EVERY board position. Since the computer has half of the control over the direction the game takes, you can try to steer away from "obviously bad" situations as well.
Yes, I make computer games for a living. :-)
sig fault
There can be only a perfect game for black or white, not both. If there was both a perfect strategy for black and white, and both players new it, who would win? It would lead to a tie, so the strategies wouldn't be perfect.
--
This space left intentionally blank.
I don't know if you've ever heard of Zillions, it's this really cool generic board game playing program. You can basically write many different types games for it and it will play them, oftentimes very well. It has certain limitations in the sort of games it can play (mainly that it doesn't handle games like Go or Hex where the concept of a topologically connected group is important), but it can play many different types of Chess variants and Chess-type games, even incredibly complicated ones like Ultima.
Anyway, playing against the program is exactly like that if you're playing a game that it plays really well. It usually can't search 50-something moves ahead, of course, but it's really strange to see it say "Win in 14!" when you thought you were winning. For certain simple games like Nim, you can see the exact move you made which caused you to lose, immediately after you make it.
This is why I like to consider go programming: If you can not do it with brute force, you need to do it intelligently. Or at least use some higher-level logic and reasoning. Just counting pieces won't get you anywhere, you need to evaluate forms and shapes, make long-term plans, and consider parts of the board separately, yet interconnected.
Chess has been compared to a battle. Go is better compred to a war, where you can loose many small skirmishes while positioning your forces so that you can just sit back and let your opponent starve to death. Win without firing a single shot. (in go terms: enclose him, sacrifice a little to force him to live small, and the rest of the board is yours. ) (of course there are other, better, strategies)
In Murphy We Turst
Isn't that called the Find-S algorithm?
No it's not. A path is the solution.
You need to generate the tree to find it, but not all of it at once.
Moderators smoke crack today.
Now just give us a good reason why you should have to keep the whole tree in memory at once.
Then came the War, and the secret was lost; the mysterious Machines on the homeworld were the only ones to survive the War, and all attempts at understanding the theory behind their operation had been futile. Intensive study revealed they were still working on a problem. Unable to determine the nature of the machines' task, the Scientist-Priests abandoned the Project of Understanding was after seven millenia. The Project's only real discovery came in its third century, when it was found that the heiroglyph on the Machines represented an ancient animal called a 'penguin'.
What are the Machines working on? The topic of discussion when young Scientist-Acolytes gathered often turned to the Machines, and speculation of their colossal task.
Then, one day, deep in the heart of the Machine Cluster on the all-but-forgitten homeworld, a terminal winked to life. Its cryptic output would be the subject of another hundred lifetimes' analysis, as it consisted of hundreds of 8x8 grids populated by six seperate symbols...
J
What are you playing it on? A Z80? Come to think of it, a Z80 port of Linux would be a neat trick... "Screw TI-Basic, I use gcc on my calculator."
J
Unless the guy's opponent has nerves of steel, that alone would freak him out enough for it to be a self-fulfilling prophecy.
J
However, if you preview, it replaces the &HTML escapes -- bug in slashdot. So after preview, instead of hitting submit, use your browsers back function, and then hit submit. This bug has been known for more than six months.
Nope, there are about 10^60 nodes for chess, and about 10^80 atoms in the universe. Of course that's still more atoms than in this solar system, this doesn't really help.
I'll take your example of "white to win in two." There could be a solution of two moves if the setup is just so. But certainly there could be some setups where checkmate was possible in two moves, but not certain. In these cases, white's second move would depend on black's move. In this case, again depending on the setup, I think you could either have a tree of moves so that no matter what the black does, white has the right move to beat it, or a mixed tree that includes some black moves which preclude checkmate in two. So I think it all depends on the setup and the movements of the opponent.
There's a really interesting passage in Douglas Hofstadler's Godel, Escher, Bach which I think pertains to this topic. It's been a while since I read it, and I don't have the book with me now, so bear with me. He's explaining systems of mathematics, as an introduction to explaining Russell and White's Principia Mathematica. I forget the example he uses, so I'll devise my own. Suppose my system starts with the axiom 5 and the only valid operation is that you can multiply by 2 or 3. So 10, 15, 20, 30, 40, 45 are obviously valid numbers in my system. He has a name (which I forget, damn!) for this type of system where the operations only go in one direction. You can take a really high number and determine if it is valid with a simple algorithm. But if I allow a dividing operation, say you can divide by 5. Then it get's more difficult, because you could go back and forth multiplying and dividing in different combinations many many times to get to a number. So if I give you a big number, say a with many decimal digits, and I ask you to prove if it's valid in my system or not, then it's impossible to solve negatively. Just because you've been trying permutations on your supercomputer for twenty years with no solution, doesn't mean you've proven that the number isn't a valid part of my system, so you have to keep calculating, and in the end, I'm not sure if you can ever prove that it isn't, just that perhaps it is when and if do eventually get a solution.
Sorry I couldn't explain that more concisely. Anyway, a game like tic-tac-toe is simple because it goes in one direction. For every possible state there is a finite number of permutations of moves that could have gotten you there. In chess, it's unfortunately the other case. It's like someone said before about the number of moves being greater than the number of hydrogen atoms in the universe. I suppose you could devise a set of rules, to prevent loops, or to limit them to a finite number of repetitions, but that would defeat the purpose of solving the perfect game of chess, since it would depart from the official rules, so then you'd just be looking for optimal moves or practical strategies to help you win in most cases.
Going back to the tic-tac-toe example, I think it's interesting that this simple game cannot be played perfectly. You can guarantee a draw, but you can only win if the opponent makes a mistake. I know this proves nothing, but I venture that with all the additional orders of magnitude of complexity that you have in chess, there can't be a guaranteed way to win.
"What I cannot create, I do not understand."
I guess I'm conjecturing that maybe there are some states which can only be reached through an extremely long set of moves, so it would take a nearly infinite amount of time to figure out if the state is valid or not. So even though the states are finite, knowing the complete set of valid states on a board could take infinity.
"What I cannot create, I do not understand."
I'll preface this comment by stating that I believe that it will be computationally unfeasible to brute force a 128-bit key for the forseeable future. Nonetheless, Scheiner's thermodynamic calculation is actually incorrect, because it assumes an irreversible state change. This is not the case! There is no lower limit to the energy needed to perform an arbitrary operation. Bruce is a great cryptographer, but he's understandably not a physicist. He creates a straw man argument that, although very impressive, is actually incorrect. If you're interested in the details, email me and I'll send you more information on Tuesday when I get back to my office.
To say that a game is solved, one is asserting that either through a theoretical proof or complete experimental evidence, it has been proven that a game is either a win, a loss, or a draw for the first player. This, of course, assumes that each player plays a perfect game without any mistakes. If a mistake is made, the other player should be able to conclude their game with perfect play to guarantee a better result in their favour. To this day, no-one has solved checkers, but it is possible that we are approaching the day that it becomes solved. In fact, a certain computing science professor may be looking for graduate students interested in furthering the research in this area. If you are interested at all in this area, I urge you to check out the aforementioned book and website.
Disclaimer:
I do not study game theory myself, but am a current graduate student under Dr. Schaeffer.
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.
<disclaimer content="I am not a mathematician">
The only reason the search tree must be stored is so you can find your way back from the solution. If the tree is searched depth-first, the search needs only about 100 words of storage, 35 values for each word. Multiply that by about a few thousand, and you have space for sophisticated tree-pruning algorithms; how about a distributed.net attack?
</disclaimer>
Will I retire or break 10K?
For the same [FIR57 P057!] reason that [hot grits down your pants] people say [Natalie Portman naked] dumb things for me to poop on at all, [goatse.cx] to get attention. It probably wouldn't bother us as much if it were part of a sig, but when it's the only thing in a reply...
Will I retire or break 10K?
Well, the king-queen switch is easy; it definitely favours the computer. A human might be disoriented by a board which is the mirror of what they're used to, but it would be trivial to modify a computer's algorithm to accomodate this.
The other switches pose a more interesting question.
The number of moves of the shortest white win/black win/stalemate is actually irrelevant. For example, it's known that it's possiblt for white to win after three moves. There are certainly no draws or black wins that quick. But this doesn't mean the game is solved, because black won't necessarily make the moves that allow this quick win to happen.
It's not the number of moves to win that count - it's which player always has an answer for every possible opponent's move which guarantees victory. (If neither player does, then a perfectly-played game is a draw.)
Nitpicky: the optimal strategy for player 1 and the optimal strategy for player 2 need not be the same, although admittedly it's difficult to see how they could be different in a symmetrical game like chess.
(Certainly, in the vague common usage sense of "strategy" good strategy for black differs from good strategy for white, but in the formal sense of a strategy as a function from game states to move, I'm pretty sure the optimal strategy for both sides has to be the same. The difference in practice is that they don't face the same game states in the early game.)
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.
While I haven't read that book, I'm pretty sure the game has to be both deterministic and have complete knowledge of the game state available to both players. There is no optimal (in the sense we're using here) strategy for Paper-Rock-Scissors, nor for Poker, despite both games' being zero-sum.
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.
Indeed not; consider a variation on Fox & Goose (you can find the rules here) with the diagonal line removed. In that game, whoever goes first is guaranteed to lose an optimally-played game. The reason people expect that chess is either a victory for white or a stalemate is that, empirically, white wins more often than black (though I don't think the difference is terribly large).
Do computers really PLAY chess? They make decisions based on the probability for best outcome due to future possibilities of moves and future opponent moves. While PLAYING chess involves such decisions on a human's part, it also involves feeling and a bit of trickery/deception. I couldn't see a computer making a bad move to "suck a player in" or bait a player into making a move. I don't think that they've been given the power to "manipulate" a player yet. These computers can do infinitely more permutations of a game than a human can do, but a human can predict strategy based on a player's habits and faults. I contest that the computers are able to win because they have this ability to play out a game based on odds and probability many times before even making a move.
"I threw up my hands in disgust and wondered if it had been such a good idea to have eaten my hands in the first place."
Even if we had a lot of time time, I don't think that the monkey solution would be productive. The problem is that we need someone to discover when the problem is solved. We might try to intend to a write down all the moves of the monkeys. But then we would have to spend eternity analysing the moves We could also try give each monkey a typewriter and wait for one of them to write a complete solution to chess. But then we have to read everything that they read.
I think you have to distinguish between two different meanings of the word strategy. You are refering to the meaning of strategy in board gaming whereas he is refering to the meaning of strategy in game theory.
I think I agree with you definition of a perfect game, but you are refering to the theory of two-player zero-sum games. This is a theory that is developed for games where both players move at the same time and they do not have full information about the other players move. An example of such a game is paper, rock and scissors. In chess players do not move at the same time. Therefore the chess is somewhat a different game.
If anyone ever succeeds in creating a quantum computer, the storage problems problems will probably be solved. A state in the quantum computer can correspond to a superpositition of a lot af different states of the game. So n bits in a binary quantum computer may be able to describe 2^n states of the game. I haven't heard of any quantum chess algorithms yet, but using a good algoritm, the quantum chess computer should be able to do a kind of massive parallel computing. Here is a nice introduction to quantum computing I am not sure if quantum computing will allow us to solve chess completely, but at least it will probably lead to a great improvement.
By the way. The ING cup will pay $1 mill to the first program that wins the cup and beats a human Taiwanese pro.
In tic tac toe (and chess), all that is needed to win is a) to start and b) to know the permutations and appropriate counter-moves required to get you to victory. Let us suppose that both players satisfy b) then the game could be said to be solved, as the result is decided by the starting order.
A computer (computers!) could conceivably "solve" chess in this manner, but us mere humans could never begin to remember the billions of permutations required to always win.
But neat idea - It'd be cool to log into a chess machine and see "The computer has chosen white. You lose. Play again? (Y/N)". Bring it on!
--
Tarkwyn.
Solving chess is rather simple. Let 2 computer players start playing a random game against each other (make up all possible moves and choose one). They start with no memory. These computer players must operate in two different modes:
- the first must learn if lost
- the other must learn if lost or it's a draw
A computer player should then memorize the board's position just prior to losing/drawing. This because the opponent is able to win/draw from that position.
Then, see my first sentence. Make up all possible moves, but now remove those which lead to a memorized position and choose a random move again. Then, probably the most important part: if no moves are left (because they all lead to a position in which the opponent is able to win/draw), memorize the position prior to the current one (so, we're learning a move ahead).
In this way, first all possible end-games are learned. After that, all possible middle-games are learned and finally a computer player could tell which opening move leads to victory or a draw. To finalize it all (to solve the game), play the following combinations:
- white: learn on draws/losses, black: learn on losses
- white: learn on losses, black: learn on draws/losses
Now, make up a suitable hash function for storing a lot of possible positions, run the program, wait a long time and it's all done. You will be able to tell: "Chess? It's a boring game, white always wins". I mean, it sounds a lot like "Tic-tac-toe? It's a boring game, noone can win". And this is a valid sentence.
--
"At the end of the journey, all men think that their youth was Arcadia..." -Goethe
$HOME is where the
-- silver_p
In some years hopefully your commnets will end up here: http://busboy.sped.ukans.edu/~adams
Thank you.
//Frisco
--
"At the end of the journey, all men think that their youth was Arcadia..." -Goethe
$HOME is where the
-- silver_p
The game of chess is a human invention to test our own limits. It is a game afterall. The fact that alot of posters feel a computer is superior and better suited for testing itself is scary. I would suggest reading The Sirens of Titan by Kurt Vonnegut. He may well of seen our future. :(
Actualy the thermodynamics explantation in Applied Crypto is incorrect. Check the errata at http://www.counterpane.com/ac2errv30.html Specifically: * Page 157: The section on "Thermodynamic Limitations" is not quite correct. It requires kT energy to set or clear a single bit because these are irreversible operations. However, complementing a bit is reversible and hence has no minimum required energy. It turns out that it is theoretically possible to do any computation in a reversible manner except for copying out the answer. At this theoretical level, energy requirements for exhaustive cryptanalysis are therefore linear in the key length, not exponential.
I think it's impossible to make such a tree or 'net' as you call it. The reason: the number of possible games isn't just beyond what's possible to compute and store, as pointed out in previous comments. The number of possible chess games is infinite. Why? Because you can always plot in repeated redundant moves anywhere in the game, eg if both sides would move their queen back and fourt 4000 times.
I'm a firm believer in the Infinite Monkey Theorem:
"If you put an infinite number of monkeys, working on an infinite number of typewriters eventually one will bang out the script to hamlet"
we should apply this to the perfect chess game. A program similar to SETI@home could be written to use computer time around the world. This would help cut down the time in years to a fraction of what it would be if just one was doing it. (plus if a 3D visual depiction of the moves being played out in a faster speed as the world network tested strategy would look cool, kind of like watching Wargames as the computer played Tic-Tac-Toe).
flatrabbit,
peripheral visionary
"Never wrestle with a pig, you both get dirty and the pig likes it."
the key to something as complicated as chess is not creating an exhaustive search of the problem space. if it was, humans would be pretty crappy chess players. what humans excel at, and what we are just learning to tell computers about, is pattern recognition. combine neural net based pattern recognition with a genetic algorithm for determining by process of elimination which strategies work out best, and then you'll get close to the 'perfect' chess player (the player, not the game, is the thing that has to be perfected, of course. the original question was mis-stated).
(email addr is at acm, not mca)
We are Number One. All others are Number Two, or lower.
--The Sphinx
Consider this example: Even a dumb dog can know the difference between a leg and a tree. How many people can write a computer program that can distinguish between the two?
It might surprise you, if you are a programmer, but try to do it. Grab few pictures from the internet (or from you webcam) and think how would you solve this. No computer-science major/geek/whatever knows how to solve this in a reasonable way.
I don't see it as an extrodanarily difficult task, we're just not thinking the way that we should. Nature can come up with strange and startlingly efficient ways to do things that we might never think of. So we pick a particular task, evolve code to do it, and then we study the code. Our own computers will be teaching us how to think!
Remember "Bring 'em on"? *sigh
It's not known as a spectator's (sp?) sport
There's absolutely no need to go through every possible position in chess to find the perfect game.
For example, according to the number of possible positions that would have to be searched, a newspaper-style cryptogram (A=Z, B=Y, etc.) has 26! = 403291461126605635584000000, or about 4 * 10^26 possible states. DES has 2^56 = 72057594037927936, or about 7.2 * 10^16 possible states.
By examing the number of possible states, you'd tell banks to encrypt their financial data with a code that is -very- easily crackable.
The trick isn't trying to find all of the possible states, then finding the best one. The trick is cutting off branches of the problem until it can be reasonably solved by a cluster of computers.
Never play leapfrog with a unicorn. Or a juggernaut.
Whether or not a solution consists of just one path depends on how you define the problem.
This has been discussed (sort of).
Because the tree *is* the solution.
The big problem with chess is that the tree is VERY large- how big isn't known but estimates vary over a large range (see netchess and wolfram mathworld). There are certainly more chess positions than there are atoms in the universe, but the lines that lead to them are mostly worthless, so they don't matter and can be pruned away. Let's pick a tree size of 10^60-10^70 for arguments sake.
This is way beyond the scope of even distributed computing like SETI. It's usually reckoned that chess is unsolvable by brute force.
Normal computer techniques can handle about trees with about 10^20 positions or so, depending on how much hardware you can throw at it, and how long you wait.
However there are a couple of approaches that can reduce the exponent by a factor of 2 each in chess:
- Quantum computing
- Alpha-Beta pruning
Use both and the search tree comes down from 10^70 to 10^17. That is still a HUGE tree, but it is searchable in a year using a quantum computer that can search 3 billion positions a second.As another poster noted, the current state of the art is 7 bits. You would need probably need 100s of thousands of bits to do chess. And the cycle time for current computers are measured in seconds rather than nanoseconds, but then again no optimisation for speed has been done AFAIK.
Finally it depends on the actual size of the chess tree. It may very well be there is a forced checkmate at say, move 40, in which case we would find it. But if there are only draws by repetition, under perfect play, the tree probably becomes impossibly large even with quantum computers.
Still, a search that said that there were no forced wins in say, the first 40 moves would be suggestive of a draw.
-WolfWithoutAClause
"Gravity is only a theory, not a fact!"For all you bored mathematicans and such, how large is the chess tree? or actually it's a net and not exactly a tree, but how many possible combinations there are for the board?
If it's possible to create the full tree, we could make it, and have each node have three links to other possibilities. one being 'win', one 'lose', and one 'draw'. Now we could start doing bruteforce for the tree, finding out the single moves that end into win, lose or draw, and mark these into the net. Then do it again, because now if we from a node can get into situation where the 'win' link is existant, we know that this node we have is a 'win' node, too, and we can make the path.
If someone has too much free time and could start a project like this one day when the hdspace is large enough to keep the whole tree, it might be interesting to see where it ends.
also, btw, does anyone have any better algorithm suggestion for finding out if there exists a perfect game? this brute-force approach is pretty heavy :D
-- Matti Nikki
Ofcourse it would be infinite, but that wasn't the point at all. the point was not to computate tree of 'all possible moves', but 'all possible situations', and then see which would be optimal move from a situation. There is limited number of possible situations, and the optimal links could be nice to calculate. :)
-- Matti Nikki
I completely disagree. The first time Gary played deep blue in the rematch, he won. A strong player like Gary could have easily forced draws the next five games, but instead Gary chose to play more aggressively and hence a riskier fashion and lost the match 3.5(DB)-2.5(GK). I, and many others believe that if Gary Kasparov were to play deep blue again, he would win. This is why: The art of learning how to play chess against a computer is a new one. Strong computers have only been around for a short period of time. There are techniques that professional chess players have developed to "beat" strong computer chess opponents like Fritz and Junior. These strategy's are things like, playing strange openings such as the double fianchetto, long term strategy planning and "closed games" which computers are notoriously poor at playing and the technique of sacrificing the exchange for position, to name a few. Keeping a game complex and tactical will confuse the computer and prevent it from capitalizing on it's powerful tactical engine which works best in clear cut, open scenarios. These are but a few of the techniques. Regularly playing Fritz, Junior and Shredder will also keep one on their toes against a computer. Although Moore's law dictates computer's will become fearlessly powerful, their is nothing that says that we cannot use our own ingenuity to advance the evolution of our own mind. An excellent way to do this is through chess.
I understood they had solved checkers more recently. Solving the game is not necessarily a workable way to play. Storing all the partial sequences stored along the way may be unfeasable
If you liked this thought maybe you would find my blog nice too:
And oh, I forgot to mention a few things. :)
Go is a 4000 year old oriental game, invented initially by Chinese, moved to Japan and Korea, and currently dominated by Japanese and Koreans.
The Web Go Page Index
This will be the only index on Go you ever need.
Mick's Computer Go Page
News and informataion about computer programs that play the ancient oriental game of Go
Memory is not an issue to solving chess, as you can use a depth-first algorithm to traverse the tree, so the actual size of the tree doesn't matter for memory usage.
Time isn't either, if we're speaking about solving it. It doesn't matter how long it takes, just that it can be done in finite time. The required time can always be shortened by using more or faster comps.
Neither will solving chess make the game less interesting. There would be no way for a human to make use of the 'solution'.
In short, all what you've said was wrong.
--
GCP
The way it could be worked out is to find out the outcome for every single move in chess. you move one piece on the board it would branch off into another completely different game, move another piece and another game branches off. What you would end up with is all possible moves that could be made, all games that could take place from 5 move check mate to the 7 hour game. If you played No matter what you moved there would be a solution against you already. So the moment you moved a couple of pieces, the computer would have already eliminated different possiblities within the game. You would pretty much loose the moment you moved a few pieces. Pit two of these computers against each other and you'd end up with a very complex game of tic tac toe, neither could win.
Be you Admins? nay, we are but lusers!
I agree that much of the complexity could be trimmed down. Perhaps by storing all previously analyzed positions so you would only have to analyze all possible moves from each position once (there are many more possible games than there are possible board positions, but I don't want to even think of the amount to storage space you'd need for that). Even after that the search space is still huge.
i must have cut myself off there. so i would say, at the least, you'd need some very good mathematician-type tricks, to vastly cut down the number of games that need to be considered. sorry if these comments are too stupid
You are correct. There are more possible chess games than there are estimated number of particles in the universe.
Part of what makes Chess such a great game is that it can't be solved. Who's to say a Sicilian defense is better than a 4-knights defense? Especially with the various openings, Chess is a game dependant on style. Some people prefer an open board and choose to push queen's pawn. Others prefer a closed board and push king's pawn. Neither is better or worse, just different. One person makes a move (for better or worse) based on their style, and the other person responds based on their style and the percieved mistakes.
Even if you remove the perception of mistakes, style still plays a key role. With 16 billion possible moves if you only give each side 4 turns each, with computers running at speeds we can't concieve of, plotting every single game would be possible, and optimizing their chance of success, at least a small element of style would vary from game to game.
Busco a alguien que me quiera como yo la quiera.
It should be about 10^7 times longer than the age of the Universe so far, because me (like a dolt) thought the Universe was only 15 billion seconds old (not years old =).
So happy birthday to the Universe, 15,123,642,124 years old today.
-- Maz
Revising maths...
First I have to say that there isn't such thing as perfect chess game because You can't make a chess game without any mistakes. The computer (currently) can't play perfectly because than on each step it will have to culaculate all the possibly steps and sutuations that any step can make and this will take a lot of time (A) and lot of memory will be needed (B) time is not always avaible in chess games and on all the computers in the world there isn't enough memory for that even not enough for two steps. Another thing, this is not mission for Distributed.NET because they working using brute-force method and as I have already wrote there is not enough time and memory for that mission. Lets hope that computer technology will never be so high that A Perfect Chess game will take place, because othervise the game of Chess won't be interesting anymore.
Sounds kinda like a genetic algorithim to me. WHat needs to be found is a quick way to rank different moves inorder to get the computer to actually think ahead several moves like a real player could do.
Spring is here. Don't believe me, look outside!
Its kinda like on the first move of the game, there are only 20 possible moves, this isn't a number of moves I'm afraid of dealing with.
Spring is here. Don't believe me, look outside!
Someone once told me (He's a chess player, I'm not) that there to many paterns and moves in all the games of chess to store any where....
Like, more ways to put the figures on the board an possible moves to follow, than there are stars in the universe.
Just wondering, because I was thinking about a brute force method for "solving" chess.
... ... ... O.. O.. O.. OX. OX. OXO .X. .X. .X. .X. .XX XXO XXO XXO XXO ... O.. O.X O.X O.X O.X O.X OOX OOX O.. OXX O.X I win !
1) If the same position is repeated three times, or
2) If there hasn't been any capture and no move of a pawn for 50 moves...
the player to move next has the right to call it a draw, but doesn't have to.
Chess IS solvable.I 'll present an imaginary proof:
.We open our book and rip off the pages that contain a game that does not start with that move.Then from the remaining pages we rip off the pages that are 1 mod 3 and 0 mod 3 equivalent(sorry for my bad english)that is we rip the pages containing games that white wins and the stalemates.
,sorry, I cant think anymore at this moment...
Suppose that:
a)We have a book that has as many blank pages as we want
b)Each blank page has enough space to hold the moves of an entire game
The algorithm is this:
First we fill the book writing on each page every possible game(Very large book).As each game was a winner or is stalemate we sort the pages in this way:
1,4,7,... are the pages containing games that white wins
2,5,8,... are the pages containing games that black wins
3,6,9,... are the pages containing stalemates.
Now let the game begin.Suppose we play the black pieces and we have(and so does the opponent)a copy
of the above book.
White makes a move
From the remaining pages we choose one and play the next move.
White does the some.Then we do the same for white's second move and white does the same and so on.
Now I have a question :
In our initial book are the number of pages that white wins equal to the number of pages that black wins?
If this is true then theoretically white will always win because:
1)at each turn players rip equal number of pages
2)black rips first
3)The game is finite
4)At each turn at least one page is ripped
So black will run out of pages first so black will have no moves.And white will have only one page remaining (the page containing the game that just has been played with number equivalent to 1 mod 3(white winning page))
If my question takes 'no' for an answer then
Kokoland- koko@otenet.gr
I was thinking about this, and thought why not use a variant of the learning-enabled robots to solve this problem. The goal could be set to get as many pieces as possible, and has only the rules built in. In the past, these robots have been very efficient in provided results - why not let them loose on this?! PS. I dont know much about AI, but this was only and idea. Anybody think its a good idea?
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
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.
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.
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!
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.
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.
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]