Re: computer-go: FPGA

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Hi Mike,

I wouldn't  worry about whether  GO  is pathological  or not, the fact
that it is has such a high branching factor will  force us to be a lot
smarter about it than we were chess.

I can easily  imagine that if  we did  come up  with really good  fast
global evaluation function with   clever extension rules and   perhaps
with local tactical searches as in integral part of it we could expect
a improvement with  each ply of  search.  BUT, like  in chess, despite
the big improvement from ply to ply it still takes a a large number of
ply put together to play a really good game.

In go it would take  many more of them  to reach the equivalent level,
perhaps 2  or more for  every 1 in chess.   Combine that with the fact
that it takes so much more power to even get an additional ply and you
will  see that GO will  not  easily succomb to  powerful hardware,  at
least not in the same way chess did.

I would remind you than even chess made us wait a long  time, a lot of
software  improvments had   to  come along  in  addition  to the extra
hardware and  null move  selectivity   and similar techniques   had to
assist (except in the case of Deep Blue which I think doesn't use null
move   selectivity but managed   to  attack  the problem with  massive
hardware.)

But go   is of such  a  complexity that taking   full advantage of the
hardware   will  almost certainly   involve  something  other  than  a
continuous refinement  of the same  old techniques (that chess uses or
current   go programs use.)    It   could involve, for  instance,  the
application  of massive rule  sets  and massive storage requiring  big
memory and processor speed.  Of course massive  storage will be the PC
on everyones desktop.

I fully agree with you  about the course that chess  took and hope  it
doesn't happen the same (and I don't think it will.)  I think in a big
way, the  development of ever increasing  powerful hardware  gave us a
way out  and may even have  prevented us from developing truly elegant
methods and algorithms.

In go we HAVE to either develop these methods  or be content with very
weak programs.

I am trying to be careful about what I say, so  that 20 years from now
someone won't show me  these emails and I will   have to laugh at  how
silly and naive I was!  So I admit anything is possible.

I could still see  search being  a very  big component, it  even seems
likely, but I  can imagine that  it won't be  the traditional "look as
deep   as you can and evaluate"   There might  be  very focused search
elements (similar to the local tactical search) designed to return one
thing about the position, not to evaluate it as a whole.


Don






   From: Mike Gherrity <gherrity@xxxxxxxxxxxxxxxxx>
   Date: Thu, 31 Aug 2000 00:56:48 -0700 (PDT)
   CC: Mike Gherrity <gherrity@xxxxxxxxxxxxxxxxx>
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   >> Dana Nau at U. Maryland showed there were games with this property.  The
   >> deeper you search, the worse you play.  He called such games "pathological."

   > I   don't  think this   result applies   in   practice  to  chess, go,
   > tic-tac-toe or any  typical 2 player game we  are used to playing.

   It doesn't apply to tic-tac-toe, and history suggests it doesn't apply to
   chess either.  I think Go is the last of the perfect information games that
   still has a chance against the brute-force, iterative deepening search
   machine.  Since it is known that a pathological game would foil the search,
   it is not unreasonable to suspect the last holdout is pathological.  Still,
   I feel like I am routing for John Henry.

   Some of the early work on AI algorithm development for chess was interesting.
   That was when computers were too slow to do a brute-force, iterative deepening
   search.  If Go succumbs to a brute-force, iterative deepening search, then
   it would seem that only imperfect information games can be used for AI
   algorithm development.  That will eliminate all "typical 2 player game(s) we
   are used to playing."  Heavy sigh.

   The problem is that people don't do a brute-force, iterative deepening
   search.  How do they play so well?  It would be nice to figure out the
   answer to this question using a game like Chess or Go.  However, if it
   can't beat the brute-force, iterative deepening search machine, people
   aren't interested.

   So I find myself hoping Go is pathological.


	   mike