Author: Omid David
Date: 10:17:46 11/03/02
Go up one level in this thread
On November 03, 2002 at 12:36:28, Russell Reagan wrote: >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. > Russell and Norvig mention 10^40 unique positions. >>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. > Most people (Hsu amongst which) suggest that we are reaching a speed limit, for which any speed beyond will be much harder to achieve. So the linear speed grow might not be accurate. >>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. There are two options to solve the game: 1) real-time search: You believe it is possible in the future, I don't. We disagree in the speed limit. 2) preprocessing and storing all possible position in database: We both agree that it is impossible due to lack of storage space. >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. > As I mentioned above, if you manage to search the game till the end, then you won't need any storage space at all. >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. > So, summing up the discussion, we disagree in the possible speed limit. Is there any speed limit? Will the processing speed grow in a linear manner? >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.