Re: computer-go: FPGA

["Mark Boon" <tesuji@xxxxxxxxx>]

It's certainly possible to make a program read more when given more
resources, but most likely in Go the gain in playing strength will increase
only so marginally, that it may be hard to measure.

Hoping that increase in computer-power will automatically give a good
go-program is a lazy thought. I also think it's not realistic, at least not
until someone finds a good way to make a good self-learning program. With
the power of computers today there's still so much possible, so much to do
to improve a programs play. The main problem is one of man-power. How to
find enough computer-programming resources to make a better go-program.

There is a good, fairly simple way to use the increase of computer power.
Almost fifteen years ago I realised that almost all go-programs at that time
were based on a little bit of tactical search and a large collection of
heuristic rules. So I decided to focus on whole-board evaluation and a
planner and let a sub-program generate moves with heuristic rules, much like
the other programs did. Even though its lookahead algorithm was initially
rather poor, the fact that it actually did lookahead in a way other programs
played gave it a significant advantage over programs without such lookahead.
Today, computers are fast enough that it would be feasible to make an even
more sophisticated evaluation function and an even more sophisticated
planner and use a Go program of about ten years ago to produce candidate
moves for lookahead. Just as the original program only looked at at most a
few hundred moves using hardware of ten year ago, the new program could use
the old one to do a selective lookahead of a few hundred moves using todays
computers. It doesn't come as easy as just increasing the amount of
lookahead, one still needs to make the new evaluation and planning programs,
but at least I believe that's a very feasible way to improve upon todays
programs without having to start from scratch. And when done properly, maybe
in ten years this process can repeat, building layer upon layer of ever more
sophisticated computer-go algorithms.

    Mark Boon


----- Original Message -----
From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Wednesday, August 30, 2000 7:21 PM
Subject: Re: computer-go: FPGA


>
> That's a good understandable answer.
>
> I have always believed that  any program should be  designed in such a
> way  that  it is   GUARANTEED  to  improve with   increasing computing
> resources.  I think you accomplish  this indirectly by simply changing
> your program over  time to adopt to the  latest and greatest hardware.
> If you are not  doing this, then your  program must be returing a move
> more quickly as computers get faster.
>
> But I do  think this is  a desirable characteristic  for a  program to
> have, if only we can figure  out how to do it.   But I concede that it
> may be very difficult to do this well.
>
> The most obvious way  is to add to the  search, but it's not clear how
> to  do this effectively in  go.   Still it might be  useful  to take a
> quick look at what happened in computer chess:
>
> In the early days  of computer chess,  no one believed that looking  a
> little deeper would  make any  difference,  it just seemed counter  to
> intuition.   The very  first computers were  happy to  do  2  or 3 ply
> searches and when they made bad moves  people laughed their heads off.
> It was "easy" to see that looking a ply  deeper just wouldn't make any
> difference because chess  was "just  way too  strategic."   But it was
> soon  proven  that this was actually  a   totally false assumption.  A
> computer doing 4 ply would totally crush a computer doing 3 ply!
>
> What was  being  overlooked was that  a   single extra  ply  presented
> numerous opportunities to avoid bad  moves, opportunities the previous
> versions were oblivious to.  But human observers still focused on what
> it couldn't do, and when  a bad move  invariably came along, it seemed
> like absolute proof  that nothing had  "really"  or fundamentally been
> improved.  And  yet that extra  ply really put the  machine in a whole
> new playing class which  was discovered when people actually attempted
> to measure the improvement!
>
> Does any of this apply  to go?  I suspect  that one extra ply of  full
> width depth would    improve the program, perhaps   significantly even
> though it  might  appear that nothing   happened because this wouldn't
> come close  to solving the  most laughable problems.   But  even if it
> did, this is very  expensive considering the enormous branching factor
> of go.
>
> But in the early days of computer chess, we  very often identified the
> wrong  problems to solve first and  actually chose  the ones that were
> the hardest to solve   and   returned the   least benefit.  The    big
> "breakhrough" was to simply do an efficient full width search and this
> turned  out to be  extremely effective  because it addressed important
> core problems, instead of worrying  about the romantic notions of deep
> positional insight which we were foolishly focused on back then.
>
> I know a full width search is not feasible in this domain  and I am by
> no means suggesting it.  I just wonder if there is something simple we
> are  overlooking (in the same  way we missed  the "obvious" full width
> search in computer chess and denounced it for years before discovering
> it's power.)  If there is something like this  in go, it's not obvious
> at all, just as it wasn't back then in chess.
>
>
> Don
>