[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: computer-go:life and death

At 01:25 PM 5/29/2001 -0700, you wrote:

Interesting thread.  On the one hand, David says, among other
things, that writing hand-crafted C code embodying the requisite
knowledge is _faster_ (in execution time).  On the other hand, I
remember a previous discussion in this list to the effect that
more computer power isn't really useful for computer go right now
because we don't have the algorithms to make use of it.

My memory of that discussion was that taking an existing program and
giving it more computing power wouldn't make it faster.  But this is
because the algorithms that need more speed haven't been coded yet :)
Programs today run on machines 1000 times faster than the machines I
had when I started, and we certainly use the increased processing power to
make the programs stronger.



But aren't these two points of view contradictory?  Intuitively,
techniques involving a formal encoding of knowledge, which can
then be reasoned about and applied consistently, should over time
yield stronger, more maintainable, and more extensible programs
than would coding knowledge ad hoc in C.
This isn't my intuition, and it isn't supported by decades of results in
computer chess, or in computer go. The strong programs use heuristics,
and are tightly coded for speed. It does seem that the formal encoding would
be more maintainable, but actually, I think that the opposite is the case, since the
formalism would get in the way of expressing some of the important heuristic
rules that are useful for strong play.

Isn't using a
higher-level formalism for this aspect of the computer go problem
in one way conceptually not that different from using a
higher-level computer language to program in?  And as these types
of approaches evolve isn't there a strong likelihood that the
processing power will be there to support them?  Even now, I
mean, what's the point of a C program running on a 1.2GHz P4
machine and the program is so optimized that it can make a move
in 300 milliseconds anyway?

Are you talking about go?  The strong programs are not that fast.



(By the way, speaking of performance questions, I ran a really
simple benchmark on the 1d vs. 2d board representation question
that came up on this list a few weeks ago, and the result was
that the 1d approach was about 25% faster.  I am betting that
that is less than many posters thought.  This benchmark is
basically doing _only_ coordinate arithmetic.  If you randomly
assume that the typical go program spends 10% of its time doing
coordinate arithmetic, the savings from the 1d representation is
therefore 2.5% across total execution time.  This seems too small
to worry about.)

Why only 10% of the time?  Anyway, the 1d approach makes the code
more simple and readable.



Also, in my opinion, it's setting the bar too high to insist that
people working on things like knowledge representation prove
before their research is done that it will be successful.  I also
do not think that formal approaches to representing knowledge
necessarily needs to be incompatible with the probabilistic,
stochastic, or heuristic approaches that David espouses.
I agree with you that we shouldn't set the bar too high. I'd like to see
more variety in approach. There are probably approaches that haven't been
thought of that can lead to strong play. Certainly the current approach is
way too labor intensive. I was just objecting to the incorrect characterization of
the current state of the art. The thesis results are interesting already, so there
is no need to state that the current programs are weaker than they are. I expect
statements of fact in a thesis to be checked, so I was a little upset at the claim that
current programs couldn't solve a simple position that they all can solve.

David

--
Bob Myers

On Tue, 29 May 2001, David Fotland wrote:

> [snip]
>
> To me the best evidence of correct understanding is getting
> the right answer to problems :)  I take more of an
> engineering approach of using what works without worrying too
> much about theoretic elegance :)  If the program doesn't
> understand the relevant goals, it won't be able to solve the
> problems.  You are right that these programs have not been
> described, either because the authors don't have time, or the
> algorithms are too complex to describe in a short paper.
>
> I wasn't objecting to your approach, just to your incorrect
> description of the state of the art in computer go.  I don't
> think you have presented enough evidence in your thesis to
> demonstrate that your approach will lead to stronger play.
> Certainly the results you show are quite a bit weaker and
> slower than current programs.  But of course the current
> programs contain much more knowledge than is represented in
> your rules.
>
> [snip]
>
> Of course they have this knowledge.  Otherwise they could not
> solve the problems that need this knowledge.  You are correct
> that the representation is quite ad-hoc, and can't be
> formalized in the way you do it in your thesis.
>
> I have a bias against trying to reason with exact knowledge
> in go, since I've tried it and it didn't work.  The results
> from this kind of reasoning always seem very brittle.
>
> There are always exceptions to general rules.  I prefer a
> probabilistic approach, which leads to code with many
> heuristics, ad-hoc rules, and tuned constants :) But it seems
> to work better this way.
>
> David

David Fotland