How many games would a computer have to have in its database to "solve" the game of chess?
Imagine a computer which has every game on its hard drive. It wouldn't need to do any game calculations at all; it would simply "look up" the present position on the board and choose one of the winning games to find out which move to make next. If 2 of these computers are playing, it will be a perfect game:
Who wins a game of perfect chess?
"Perfect chess" is chess in which both players, foreseeing all possibilities, play only moves to produce a win or if that is not possible a draw or if even that is not possible, a loss after the most possible moves.
Shannon amusingly describes a game between two mental giants: "They sit down at the chessboard, draw the colours, and then survey the pieces for a moment. Then either
(1) Mr. A says, "I resign" or
(2) Mr. B says, "I resign" or
(3) Mr. A says, "I offer a draw," and Mr. B replies, "I accept."
This must be so.
The above is taken from a fantastic article on the subject here:
How many games would each computer need to have stored on its hard drive? As you might suppose, the answer isn't a clear number. Do you include "nonsense" but legal moves? etc.
Anyway, the writer quotes a figure of 10 to the power 120 but settles himself on a much lower figure of 10 to the power 100.
It's a big number, but how big? Well, if you could embed a complete game of chess on 1 atom, there wouldn't be enough atoms in the entire Universe for all the games!
A nice quote from the same site:
"Who wins in a game of chess between two perfect players? We may never know. Chess appears to be effectively an infinite game with no solution. The nature of the universe and not our limited intellect may be the ultimate determinant of our knowledge of chess."
While I was pondering all this, David sent me this email which talks about computer Go and Chess. As you'll see, things get a whole lot worse when you consider the possibilities in Go.
It looks like this:
And it's played like this:
With the ongoing debate (well, maybe I'm exaggerating a little) about
the relative complexity and difficulty of chess vs Go, I thought you
might to know that a program called "Huygens" has beaten professional
players, as this news release puts it:
"This is the second victory of Huygens playing Go against
professional players. During the first two days of the event, the
Go program MoGo TITAN set two new world records by winning a 19x19
competition with a 7-stones handicap against the 9P dan
professional Go player Jun-Xun Zhou, and a 19x19 competition with a
6-stones handicap against the 1P dan professional Go player Li-Chen
Huygens, an IBM Power 575 Hydro-Cluster system, is the national
supercomputer and located at SARA Computing and Networking Services
in Amsterdam. The system, which is in production since August 2008,
has a peak speed of 60 trillion calculations per second
(Teraflop/s), 3328 Power6 processor cores at 4.7 GHz, a total
memory capacity of more than 15 TB, and almost 1,000 TB disk
There's a comparison here of their relative characteristics:
Game Board size State-space Game-tree Avg game
complexity (log)complexity Length
Draughts 32 20 or 18 31 70
Chess 64 50 123 80
Go (19x19) 361 171 360 150