Re: Re: computer-go: minimax and go

[Rong Zeng <rodneyzeng@xxxxxxxxx>]

Hi, Don Dailey

I think the only way to make a good elevator for Go is make a good static model. As I stated in my idea. Do yo agree with me?

And I think this static model is not a technique problem if those excellent game companies would like to produce an engine for it. It's the problem of inadequate programming power now. We'll see it earlier if they would do it.

After we have this engine, dynamic searching won't be so hard as now.

In 00-11-8 18:11:00 you wrote:
>Hi Dave,                 
>
>Your reasoning  is basically correct, the   branching factor is indeed
>much larger in Go than in Chess.   Not to be  sarcastic, but I have to
>ask, "so what?"
>
>To me, this might imply  that it takes a lot  more hardware to play  a
>little bit better.   Ok.
>
>The previous poster wrote:
>
>   I need to know (succintly) what are the arguments that a brute-force
>   minimax approach to Go won't work assuming increased computer power 
>   just like it worked for Chess? 
>
>
>A brute force program will "work."   Give me infinite computing power,
>or enough computing power  to search the  entire game tree and I  will
>write a perfect Go program.   Short of that, I can  write a Go program
>that plays better with every hardware doubling of power.  It might not
>play much better,  it might even  be hard to  measure but it will play
>better on the average  with each doubling, until  it reaches the point
>where it can search the entire game tree.  
>
>So I have a pathway (in principle) to making a program play perfect GO
>with a finite amount of computing power,  or to get abritrarily strong
>with an  increasing amount of computing power.   Do you have a pathway
>to do the same  without involving any  searching?  I doubt that any of
>us do.
>
>Please note that  I   am taking  a  bit of  a philosophical  approach,
>believe me I understand the problems, and I realize that we don't know
>how  to  construct a  very effective search  ...   yet.  A naive fixed
>depth n  ply search  with a simple   static evaluation  is not  what I
>suggest.  I'm also not being critical of how Go programs are currently
>written,  I think  we are  doing  the best  we  can.  But I just don't
>believe that we  will  make much more progress  by  tweaking  our eval
>rules, patterns and  openings.  At some point,  we will have  to start
>searching more than  just local string battles and  we will have to do
>it really intelligently.
>
>The key, is that both evaluation AND search  is much harder in Go than
>in Chess.  That only means that whatever we do, it won't be as good or
>as easy as in  Chess.  You can't say search  won't work any  more than
>you can  say evaluation won't  work just  because it's  so much harder
>than Chess and we can't even do it in Chess.
>
>
>Don
>
>
>P.S.
>
>  >    Now factor in that chess programs get very good reductions in the
>  >    raw numbers because very strong, fast, simple evaluators prune out
>  >    most of the really bad nodes without having to evaluate them.
>
>That's  not true.  A true brute  force chess program only prunes based
>on alpha/beta    cutoffs.  A Go program written    in this style would
>actually prune much more heavily, and it's  doesn't matter how good or
>bad the evaluation function is.
>
>Yes,  modern programs  do null    move prunning  and  this does   have
>something to do with the strength of the evaluation function and gives
>more cutoffs than  alpha/beta.   However, it's not why  Chess programs
>are so strong.   If you  throw out  null move prunning  you will still
>have a master strength Chess program.  
>
>
>
>
>
>   X-Sender: ddyer@xxxxxxxxxxxxxxxxx
>   X-Mailer: QUALCOMM Windows Eudora Version 5.0
>   Date: Wed, 08 Nov 2000 11:49:57 -0800
>   From: Dave Dyer <ddyer@xxxxxxxxxxxxxxxxx>
>   References: <200011071757.MAA04849@xxxxxxxxxxxxxxxxx>
>   Mime-Version: 1.0
>   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
>   Precedence: bulk
>   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
>   Content-Type: text/plain; charset="us-ascii"
>   Content-Length: 783
>
>
>   The basic arithmetic is this:  
>
>   To do a 10 ply brute force search in Chess might in principle have to examine 
>   25^10 ~= 9.5e13 nodes
>
>   To do a 10 ply brute force search in Go might in principle have to examine
>   200^10 ~= 1.024e23 nodes
>
>   that's a billion times harder.
>
>
>   Now factor in that chess programs get very good reductions in the
>   raw numbers because very strong, fast, simple evaluators prune out
>   most of the really bad nodes without having to evaluate them.
>
>   Now factor in that in go, even very simple, local problems require reading
>   15 - 20 ply, and there are usually many such "simple" problems on the
>   board at once, so reading the full outcome of a midgame position 
>   could easily require 100 ply.
>
>   Now factor in that in go, there are no "strong, simple, fast" evaluators.


Regards,
 Rong Zeng
 rodneyzeng@xxxxxxxxxxxxxxxxx




_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com