Author: martin fierz
Date: 13:04:38 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:
>
>"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.
if you look at games which have been solved or which are close to being solved,
you will see that they have some properties which help. for example, 4 in a row
is limited to 42 ply (and has only 7 possible moves at each node) and can just
be done with a brute force search (1990 or therearounds). 9 men's morris has
been solved because you can construct an endgame database for the second phase
of the game, and because the first phase of the game is always 18 ply long,
meaning you get into that database after 18 ply. checkers will be solved because
of a similar property, although it's not as forced there. schaeffer & co are
working on the 10-piece db and most games of checkers trade down into that
relatively soon. however, IMO even with a 10-piece db checkers will not be
solved completely, and larger dbs will be necessary. other games that have been
solved have a forced win for one side which can also be found through a search
without having to go through the entire game.
you should note that e.g. for 9 men's morris there are LOTS of possible games,
but not many possible positions in phase 2, which makes constructing databases
possible, and the special property of the game ("convergence") makes sure that
the database is also useful (100% convergence after 18 ply).
something similar is true for checkers (say, 90% convergence into a 10-piece db
after 50 ply - just a wild guess). now let's go to chess:
the number of positions (10^40) is much smaller than the number of games
(10^120) - i'll just assume these numbers are correct, i have no idea actually.
10^40 is the size of the "state space", while 10^120 is the size of the "search
space". now here comes the important part: if you want to solve chess by
searching deep, you need to beat the search space, and not the state space
(that's to counter your argument that you don't need to store many positions
because of alpha-beta. if you don't want to store anything, you will not
remember that you have already seen a certain position and have to go through
everything over and over again).
this looks completely unfeasible (10^120... even if a 10^21x speedup is true).
so the only reasonable alternative is to beat the state space. which means you
would have to build huge endgame databases. let's say, you can build huge
endgame databases, e.g. with 10^30 positions in them. even if you can do that,
the game of chess does not have the convergence property of 9 men's morris or
checkers. which means that although you might have huge databases they are not
very relevant (take a look at the relevance of todays chess endgame databases -
it's very small).
for a deeper discussion of the topic, look at victor allis' masters thesis which
you can get on http://www.cs.vu.nl/~victor/thesis.html (chapter 6 is the
relevant one).
finally, a short look at practical problems:
1) how do you store 10^30 positions? even if you could store an entire position
in a single atom, we are talking of a device here which would weigh TONS. being
more realistic, your device would need a few 1000 atoms to store a position and
then we are talking about a real monster...
2) moore's law has been correct throughout the years because engineers have
managed to build ever smaller silicon structures. but there is a clear limit to
that, and it will probably be reached in a decade or two. after that, the thing
which drives moore's law (size reduction) will simply not be available any more.
some people have said that since moore's law is correct, this means that that is
when quantum computers will start being built :-)
aloha
martin
This page took 0 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.