Re: computer-go: Complexity & SW

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

> > The intrinsic complexity of a game -- the number of possible moves,
> > the number of positions -- has zip to do with the difficulty of making 
> > a reasonably strong program.
> 
> I mostly agree with this. In particular, it's easy to construct
> soluble games (e.g. Nim) which have arbitrarily large numbers of moves
> or positions. However, a game does need to have a large number of moves
> and positions in order to avoid solution by brute force. Even some
> games which are interesting to humans can now be solved by brute force 
> -- Nine-Men-Morris, if I remember the name correctly, is one.


I think what makes  things hard for humans  is whether we are  able to
construct "congnitive shortcuts."  In Chess and Go, for example, being
"close" to something  is a natural spatial   concept to us and we  can
easily get a handle  on it.  Surrounding territory is  easy for us  to
understand.  If a game doesn't provide simple analogies for us to use,
then we may percieve it as "difficult."

I can illustrate this with a  simple game.  Let  us take turns picking
numbers from the set  1 - 9.  Once  a  number is chosen, it  cannot be
chosen again by  either  player.  If you can   make ANY 3 numbers  you
choose add up to 15, (before I  do) then you win the  game.  If we run
out of numbers, then it is a draw.

Now this game is fairly simple to describe, but it's probably a little
awkward  to play, constantly  having to  keep  up with the nubmers you
have chosen and  always trying to figure out  if any combination of  3
adds up to 15.

But take a game like  tic-tac-toe.  It doesn't take  a child very long
to master  this game and  play  to a draw  every  time.  It's easy  to
visualize getting a line of 3 x's or  3 o's.  And  yet these games are
exactly equivalent.  If   you place the number  1  - 9  on the various
squares of a tic-tac-toe board, then picking a number is equivalent to
picking an empty box and putting your mark in it:

         8  1  6
         3  5  7
         4  9  2



So I think complexity (from a humans point of view) has to relate 
somehow to the way we think.  Having a bigger branching factor is
not necessarily a good measurment.

Don