Re: [computer-go] Computer Go tournament at EGF

[Richard Brown <rbrown@xxxxxxxx>]

John Tromp wrote:

> Richard Brown wrote:
>
> > Furthermore, the number of go positions one would have to store is
> > larger than the (finite) number of atomic particles in the universe,
> > so even if there were an _infinite_ amount of time (which there isn't,
> > because the universe does have an age) there isn't enough storage
> > space to keep track of the results.
>
> This is not true. We can reasonably expect perfect playing strategies that
> finish the game within a thousand ply. A search of the gametree to a depth
> of 1000 takes no more than 1000*1000 bytes.
That may be true, but you must be making some unspoken assumptions here.

As they're unspoken, I don't know what they are, other than that
you think that reading the game tree to a depth of 1000 is sufficient,
and that you think one byte is sufficient, somehow, to store the result.

My point was about naive brute-force search of the entire game-tree, and
the oft-trotted-out assertion that, given enough time, we could merely
searce the entire game-tree and keep the results we like.  Every time I
hear that, I cringe.

To the people doing the trotting out, the words "inherently intractable"
have no meaning.

There's a difference between "given enough time you can search the entire
tree" -- you can't, darn it! -- and that which can be reasonably expected,
through the use of whatever your unspoken tree-trimming heuristics are.

I was addressing the former (apples), and you appear to be addressing
the latter (oranges).

> > Such problems -- those that require a longer time than the age of the
> > universe, or that require more storage than the number of atomic
> > particles in the universe are called "inherently intractable".
> > And that's why _not_even_ brute-force will work.  It is _NOT_ possible.
> > The assertion that it is "easy to write a perfect go program given no
> > time constraints" is simply not true.
> > Not even theoretically.
>
> It's easy to write such a program, even under the time constraint of one
> week:-) Running the program is also easy in theory; it will terminate 
> within
> 1000^1000 "steps". This is only a *practical* impossibility in our 
> shortlived
> universe.
One of us is being deliberately dense.  (Which doesn't rule out the
possibility that both of us are.)

--
Rich

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/