Author: Russell Reagan
Date: 09:36:28 11/03/02
Go up one level in this thread
On November 03, 2002 at 05:20:31, Omid David wrote: >The game of chess can never ever be solved: This is incorrect. >There are about 10^128 potential chess positions. This is also incorrect. I believe the number 10^128 is the number of unique GAMES, not POSITIONS. I believe the estimated number of positions is 10^40. >If we start searching with a >supercomputer with the speed of 100 million nodes per second (10^8 NPS), it will >take about 10^113 years to process all possible positions! Deep Blue easily surpassed 100 million nodes per second. I imagine that today we could easily surpass what Deep Blue did, with the proper financial backing of course. >What is the speed you >can imagine in the next 100 years? Let's say 100 million million nodes per >second (10^14 NPS); then it will take "only" 10^107 years to solve the game of >chess! "100 million million" is 1 quadrillion, if I'm not mistaken. If computer speed continues to double every 18 months for the next 100 years, computers will be 147,573,952,589,676,412,928 times faster, which is way faster than your estimate. >And even if we process all 10^128 possible positions, we will have one little >problem: where to store the data?! Even if we manage to store a position in an >atom, there won't be enough atoms for that, since there are "only" 10^80 atoms >in the entire universe...! While this is a well known fact, it's not relevant to this discussion. In reality you would only need to store a few hundred nodes at a time, not the entire tree. Surely you understand how alpha-beta works. It doesn't store the entire tree, right? No, it stores only the current line it's searching. Today's programs store maximum of 14+ ply (or whatever the number) at a time, not millions of positions, so if a computer was fast enough to search 300 ply, it wouldn't have to store trillions upon trillions of positions. It would only have to store 300 or so. The problem is building a machine fast enough to iterate over all positions, not storing them. With a little quick math, I estimate that in 100 years, with the computers we will have then, it would take a little over 2,000 years to search the entire chess tree. Then every 18 months that number gets cut in half, so in a little over 100 years it'll be doable. Maybe my numbers are off slightly, but the point is, EVENTUALLY it WILL happen. Russell
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.