Re: computer-go: minimax and go

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: Heikki Levanto <heikki@xxxxxxxxxxxxxxxxx>

   Don Dailey <drd@xxxxxxxxxxxxxxxxx> wrote:
   > How would you write  a program on that computer we 
   > will have in 60 years that doesn't do any kind of search?

   I do not think that anyone here is claiming to have a better 
   way for a go program in 60 (or 600) years. 

Which is  the point I hoped to  make.  I don't  mind criticism  but it
should be tempered with some useful suggestions,  and I have not heard
any from those being critical.


   ...  I think that most of 
   us who think in the practical line consider 60 (or even 10) years 
   to be far in the future. Our focus is not in what is theoretically
   possible, but in how can we improve on today's systems.

I'm one of those people too.  My main argument,  which I realize isn't
being expressed very well is this:

  1. We are not taking very good advantage of the power of our 
     computers.  (I think probably most of us agree on this)

  2. If we were, then our algorithms would automatically scale,
     as a by-product of this.
 
  3. But they don't, therefore, I believe  we haven't figured out 
     yet how to write good programs for Go.


No  one really  knows how  good  a program  "should"  be.  Everyone is
critical of how lousy even the  best programs are,  but no one can say
for  sure that it's  possible to  write one  significantly  better.  I
believe  someone can probably  do much much  better,  but I don't know
how.   I'm not going to  be shooting down  everyone elses ideas when I
don't know how myself.

   I must also object to your "doesn't do any kind of search". You seem 
   to divide the approaches to comuter go into 
     a) those that are based on global search, and
     b) those that don't do any kind of searh

Actually, YOU are making this division.  I did a thought expermient to
describe scalability, but  people, including  you, completely  ignored
the point of the  experiment and focused  entirely on the experimental
apparatus.  It's almost   as  if  I was   trying  to  illustrate   the
uncertainty principle    in physics  by    using "Schrodingers    cat"
illustration,  and then having people come  after me for animal abuse.
That's about how silly it was.

Yes, I DID say  doesn't do any  kind of  search.   Again, look at  the
context of the discussion and stop  picking on me.   I was replying to
someone   who   was being critical   (and   sarcastic)  of the scaling
argument.  He didn't pay any attention to the scaling argument either,
he only wanted to know why I would want to hurt a poor cat.

I have proposed ONE possible algorithm that  does indeed scale just to
illustrate that it is possible.  I tried  to convince you that this is
a very  useful property  to have  in  a  good program.   If  you don't
believe that then  you probably, at least  in principle, feel that the
quality of  the  programming, is the  only thing  that  matters, which
directly implies  that it shouldn't  matter  how powerful the computer
is.  If that's how you feel then that is  what divides our thinking on
this, not whether there is a global search or not.   


   May I humbly propose that searching is one of the many ways to get 
   towards a better go playing program. That in the theoretically perfect
   program there will be some searching, but that it may possibly not be
   the main ingredience - just like we use boolean algebra in various
   ways, without claiming that it is the one and only thing that makes 
   computers (or programs) work...

   -H

Yes, that is a good proposal and I agree with you.  

Computer power  is often measured in  2 ways, by  the amount of memory
your computer has and the execution  speed of the program.  Very often
one can  be replaced by another  (square roots  by table lookup versus
calculation for instance.)

For Go programs to get better, they have to simulate more knowledge of
the game.  This can be done in only 2  fundamental ways, with space or
time.  Space usually also involves time.  Examples of space are adding
knowledge  by making the opening library  bigger (takes a lot of extra
memory), adding  pattern databases (takes a lot   of extra memory) and
adding  code to evaluate  things (also takes  memory for  the code AND
time.)

Fundamentally, there is  NO way around this,  you have to  invest BOTH
space and time to play Go by computer, and  I don't care how GOOD your
program  is.  To improve it  you have to ADD either  time  or space or
both.

Some of us imagine  that the ultimate Go  program will just require  a
nice smart program, not more hardware.  This is a fundamentally flawed
notion.  Again,  you  never get something  for  nothing, you  MUST add
space or time and that means more powerful hardware.

You  might  legitimately argue that   current  programs are incredibly
wasteful of space  and time, and so  much  more is possible given  the
current usage  of resources.  That's a  good and  reasonable argument.
As long as you understand that  you are not  really getting around the
time/space issue I'm ok with that.

Personally, I think we  are very wasteful   and our programs could  be
much better on  current hardware (I know  mine certainly could be  :-)
That's why I promote any approach that tries to utilize to the fullest
extent  possible,  the  potential  of  the hardware,    and that means
automatically that  it will scale superbly  well.  And I don't care if
it involves global search or not.


Don