[gnugo-devel] more top-level search results

[Douglas Ridgway]

Inspired by the Doshay group's success with SlugGo, I've been trying to
see if any aspect of it can be replicated with less computer power. The
code is (almost [1]) the same as that posted Aug 26. Regular (3.5.10, more
or less) GnuGo is always black, the search program is always white and
uses the same version of GnuGo. The parameters are given below: width is
the number of GnuGo's top_moves which are considered, depth is the number
of moves played after the toplevel move, level is the level GnuGo is set
to, and there is no branching below the top level. Outcomes are stated in
white wins/games played, and include some repeated and near-repeated games
[2].  Handicap 0 games have a komi of 5.5 or 6.5 (although none of these
were in fact decided by the komi).

  Parameters           Opponent   Handicap   Outcome
Width Depth Level        Level
  5    15    1           10          0        4/8
  5     4   10           12          0        8/10
  5     5   10           10          0        9/9
  5     4   10           12          2        21/34
  5     5   10           10          2        12/15
  5     4   10           12          4        8/20
  5     5   10           10          4        8/20

It looks like there's some gain in strength over regular GnuGo, as long as
the tactical search level is adequate. A plot of outcomes for 5-4-10 vs
level 12 at various handicaps is at http://dridgway.com/Go/5-1-4-10.pdf,
indicating a strength difference of perhaps two stones or more.

The obvious question is how much of this gain is due to the "psychic evil
twin" effect, i.e. doing a search with near-perfect knowledge of opponent
responses. To get a sense of the size of intransitivity, SlugGo beats
GnuGo 70% of the time giving five stones, but can only give Many Faces, a
program near even with GnuGo, somewhere between two and three stones with
that kind of advantage. This suggests that the psychic evil twin effect is
worth ~2.5 stones at width 15 depth 16. Since the gain at width 5 depth 4
against GnuGo may not be even that big, it's possible it's entirely
accounted for by intransitivity, and there might be no gain against
external opponents at all. Still, showing any kind of gain while using
much less computer power than SlugGo seems encouraging, especially given
that David has already shown it works against other programs too.

Questions:

1. With these parameters, each game takes a few hours. Am I right in
thinking that the same tactical searches are being redone, over and over,
so there might be substantial performance gains possible?

2. Are there tools for identifying substantially similar games?

3. Does anyone want to help take data? Other opponents and other 
width/depth combos seems like a place to start.

doug.

[1] Except that fuseki is played without search.

[2] At the moment, I have to identify these by hand. To give a sense of
the frequency, one set of 20 games had 4 repeats or near repeats. Working 
with a fixed set of starting conditions might be better.