Re: computer-go: Insight of a human

[Heikki Levanto <heikki@xxxxxx>]

Don Dailey <drd@xxxxxxxxxxxxxxxxx> wrote:

> Of   course planning is  important  in any game.  But forgive me for
> another diversion into computer chess ...

You are easy to forgive, you come with serious arguments...


> In  the early days  of  computer chess,  it was  extremely common  for
> people, in a moment of deep inspiration,  to proclaim that the problem
> was that computers didn't have the same ability to plan that human do!
> It was repeated so much that it became  almost a mantra. 

Interesting! Maybe you are right, we ask "why don't computers play better",
and come up with differences to how we humans play. In most games some other
algorithm has turned out to be more effective than imitating (our limited
understanding of) human thought processes. And not only in games, aeroplaens
don't flap their wings, although all natural models (birds, insects, etc)
do. The starting point is different, and the resulting solution is different
too.


> I am not  intending to trivialize the   importance of planning, but  I
> think the  whole point was missed.  Some  projects were  launched with
> the goal of creating chess programs that  made plans.  Typically, they
> would examine the  board, apply some  rules defined by a meta-language
> of  some sort and  the rules  would suggest  moves consistant with the
> plan  or plans  determined by this  process.   In principal this seems
> like a very good way to do things and  apparently mimicks the ways the
> great masters do it!

Yes, it does seem like a good way, in general. This may be controversial,
but how much evidence do we have that humans *ever* think that way? Maybe
the problem is not in the way we apply "human" reasoning to chess or go,
but in the way we think humans do their reasoning! When was the last time
you actually formulated a plan? 


> What happened to these programs?  As  far as I can  tell, none of them
> are  used today.  In  my   humble opinion,  chess  programs are   goal
> oriented to  the extreme,  even more  so  than  humans are.   They are
> totally focused on trying to the very  best of their ability, to REACH
> the position   that   scores  the  very  highest   according  to their
> evaluation function.  You might even say  they are "hell bent" to make
> this  happen.  In fact, the term  "thinking  ahead" is synomonous with
> "planning."

Yes, in most simple problems just following a simple algorithm is enough. 
If you want to find a better approximation for a square root of a number, 
you don't make fancy plans, you follow a well-known procedure of taking the
average of your best guess and the fraction of the original number and your
best guess. Repeat a few times, and voila, you have a pretty good estimate.

For chess we do not have such a simple, good algorithm. But we know that a
rather trivial evaluation function and a simple search will get us pretty
close to playing good chess.

Like you say, earlier this was not clear, and all sort of fancy theories
were put forth. Then it turned out that simple search and simple evaluation
were enough for chess, and the fancy theories were forgotten.

Trying to apply this to go, I could make two conclusions:
  1) Simple search and simple evaluation will eventually be sufficient
     for solving go.
  2) In time we will find a way to solve go that will (then) seem simple and
     mechanical, and in no way connected to how humans think.

or, to rephrase the question, is go "just like chess, but more so", or is it
fundamentally different? 

There are a few "simple" differences:
  1) There are many more possible moves in go, leading to a much bigger
     search tree.
  2) There is (seems to be?) no simple evaluation function for a go
     position. In chess you can always count the pieces, and get some idea
     of who might be ahead. In go the lost pieces (groups) may still be on
     the board, and some extra effort must be made to decide if they are 
     alive or not.

There are also some "complex" differences
  1) In chess, almost every move affects everything on the board. In go
     there are many local situations that are almost (but not quite)
     independent of each other.
  2) The winning criteria in chess is simple: Got the king, or did not. In
     go it is a matter of balance: Got territory and prisoners, just a bit
     more than the opponent.
     
Being a great fan of go, I would like to conclude that go is fundamentally
different. But I fear I do not have enough reasons to make this conclusion -
yet.


So, how on earth do we humans play chess or go? Do we use some mechanisms
that could be applied in software? Can we learn something about ourselves?
Or even about problem-solving in general? You do come with one good point:

> It's the ability to generalize effectively.  THAT is really what sets us
> far apart from the stupid machines.

I would like to generalize that :-) What makes us different is that we are
able to work on various different levels of generalization at the same time.
We can worry, at (nearly?) the same time, about the life status of this
group, and about the effect of this status to the whole balance of the game,
and about the necessary chancges in the way we deal with another group
depending on the life status of this group... (And about how we are doing in
the tournament, if this is the right way to spend a weekend, and what the
guys at the rowing club think of this all...)


In a way, this all comes back to some deeply philosophical questions: What
is thinking all about? How do we think? Are there other ways of thinking?
How much can a machine think? If I could deliver clear answers to these
questions, I might win a few go tournaments. And collect a few Nobles!


- Heikki

P.S. You keep talking of chess. What can we learn of other games? Backgammon? 
Bridge? Poker? Business? Law? Diplomacy? Family? Love?


-- 
Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
               "In Murphy we Turst"