Re: computer-go: Discarding the rubbish moves

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Thu, Jan 16, 2003 at 02:21:59PM -0000, Churchill, Julian wrote:
>  I've actually been doing some experiments with neural networks and so 
> far the best net trained classifies the next move in a test set of 
> pro games, on average, in the top 19% of moves available. So using this
> network to 'score' all available moves I could reasonably cut out ~80% 
> of those moves and then conduct further analysis on the remaining moves
> in more detail. In practice I have used the net to remove 90% or more 
> due to resource limitations.
>   
>  I've used it in combination with minimax search and various rough eval
> functions. Playing 9x9 test games against GNUGo (3.0.0) the program 
> achieves a score average of -10 points with the most favourable 
> configurations (this does include some wins :)). None of the eval 
> functions are complex, just simple such as stone counting, liberty
> counting or Bouzy's 5/21 influence algorithm.
> 
>  Just thought you might be interested to know some practical experiment
> results, and I'd be very interested to hear if anyone else has results
> from similar experiments...

I don't have any direct experience with this, but both reading
published stuff about computer Chess, and reading Robert Hyatt's
writing on Usenet (about current work on his program "crafty", and
about history, including his work on Cray Blitz) I get the strong
impression that once you can afford to do a couple of ply of search
(as in computer Chess since the 1970s), it becomes very dangerous (as
in usually very harmful to the average strength of your program) to
try to speed search by discarding moves which are likely to be wrong
-- but not reliably *known* to be wrong.
 
So the results are interesting and useful, and I'm glad you posted
them, but they're not exactly what I was trying to talk about. I was
talking about moves that you can safely utterly ignore without
impairing your playing strength (like my example of moves off the
third or fourth line which are sufficiently far from any other
stones), not moves that pros strive not to make (but are sometimes
forced to make in unusual positions).

In computer chess terms I think people would say that your results are
very useful for move ordering in search, while what I was arguing
about are rules which can safely be used to prune search completely.
Good move ordering is very important too, but it's not the same thing
as pruning, being able to simply throw away all variations starting
from a bad move, never investigating any of them.

(My reading of Brown's original discussion
  > for any potential move, correctly places it into one of two classes:
  >     o-  Moves that no reasonable player would ever even consider.
  >     o-  Other.
was that pruning, not move ordering, was what he was talking about
too.)

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
"That's our advantage at Microsoft; we set the standards and we can
change them."
 -- Karen Hargrove, Microsoft (quoted in Feb 1993 Unix Review editorial)
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C