I’m a bit interested in game theory; especially fascinating, I think, is how they analyze game trees via computers, thus solving a game by determining the best possible behavior for each player.
Many games have been solved in this way, including (I think) tic-tac-toe and many nim games, which made playing the games obsolete because everything that could happen during a play has already been calculated in advance.
Many books about GT emphasize that this (theoretically) also applies to chess; the game is based on the strategic interaction of two players only. So my question is: How far are the scientists currently away from having dug through the entire game tree from mate back until the opening moves? Is there any serious research being done on that field?
I know that the number of moves is tremendously high in chess - unlike in the simple games mentioned above -; but I believe that with today’s massive computing power (perhaps combined in some scheme sort of the SETI @ Home project?) it would be feasible. Are nowaday’s game theoreticians close to the solution of the chess, or is it still far beyond our possibilities? And: What would the chess associations do? The day chess is solved, it would become a useless sport to do and watch.
Remember Deep Blue, the Chessmaster-humbling machine, making all the headlines a few year back? It beat Kasparov. Google searches on Deep Blue will bring you all kinds of info on how humans are trying to “unravel” the secrets of chess.
It’s been calculated that the total number of chess moves is about 10[sup]120[/sup]. Even if everybody on earth had a Deep Blue that can calculate a billion moves a second, it would still take you…let me get out my TI-92…5.28 x 10[sup]97[/sup] years to finish the job. Only a quantum computer can possible tackle that kind of job.
George Steiner in his White Knights of Reykjavik claims, apparently, that there are more possible games of chess than there are atoms in the universe.
Even if it were possible to map them all, there’s no way I’d remember all of them (there are bound to be one or two which slip my mind) so I reckon chess would still keep on going regardless.
Indeed, but even that scenario is impossible. The number of nodes in the complete chess game tree exceeds by many orders of magnitude the number of elementary particles in the universe. I doubt even a quantum computer could solve the problem.
I always wondered what happened if Deep Blue played itself. Especially now that it also learns as it plays… it would be very interesting. I was always fascinated by making computer programs play themselves. I always felt they should end in stalemates but they never did…
Well, OK, then forget about chess (although I believe some techniques like alpha-beta and similar make the tree more handsome) and let’s skip to, say, checkers, which is also played as a serious game of skill in professional tournaments. Wouldn’t that be close to being solved?
I read the other day about a software named Zillions of Games which allegedly can play every boardgame on the world (even newly invented ones, if you input its rules into the software via some programming language code) by setting up the specific game tree and analyzing it. That must be cool stuff.
From what I have heard as a casual player for 35 years, Seraphim has the scope of the problem in hand.
However, Chess is not a game of chance, and if one had computer resources exceeding what was necessary, you would work out a tree allowing white to win or black to draw (I think it is safe to say a black win is not possible). Even if there were trillions of Deep Blue computers working for trillions of years going through every permutation, it might never be found.
That said, Kasparov (no longer the world champion, it is a young person’s game) did quite admirably against Deep Blue. The problem he had was negotiating the rules of the match, which his team seemed to ignore out of over-confidence.
But I digress. A computer would not necessarily go through all the permutations. Some moves are just stupid and in fact most moves are just stupid and the vast majority of the possible move trees can be eliminated out of hand. Most chess is played using only a few standard openings which the players and computers memorize. I am a casual player and don’t memorize opening strategies, but I do know that there are not that many viable openings for a computer to have to consider. Moreover, there are principles of movement that are used after the openings have been played that would eliminate most other moves. As a practical matter this still leaves more move possibilities than brute force computing power can deal with.
So the way this problem is going to be figured out is that computers will refine model openings and then test them. Will it happen in our lifetime? I doubt it.
I think that what happened to Kasparov was inevitable. In another 10 years, computers will be millions of times faster than Deep Blue. Humans, thinking in patterns (IMHO, no cite) rather than digitally considering every possibility many moves out will be crushed by computers at chess, even the very best.