[gnugo-devel] opening db proposal

[Douglas Ridgway]

Hi all,

I've used extract_fuseki and Ashley's game set to generate a potential new
opening pattern set. The design goal is high variety given reasonable
quality. The games are amateur online games, and should be unique by Dyer
signature.  For extract_fuseki popularity tuning parameters, I used 4 1.0
2, meaning a position is not included unless it appears 4 times, a move is
not included unless it appears twice, and at least 1% as often as the most
popular move in that position. 1% was picked so that 3-3 and 5-3 openings
on 19x19 even were included, they are played between 1-2% as often as the
most popular opening, 4-4. The position frequency of 4 and move frequency
of 2 maximize variability given the basic requirement that each selected
move is repeated. Minimum player strength in kyu varies, as does the depth
cutoff. Here is a summary table: 

  Size  Handicap        MinStrength     Games   Depth   Patterns
  9     0               6               1999    11      1041
  9     2               10              231     9       121     
  13    0               8               497     7       211
  19    0               0               35411   25      20263
  19    2               0               3930    25      2145
  19    3               0               2622    25      1548
  19    4               1               2172    25      1186
  19    5               3               2062    25      1102
  19    6               6               2026    25      958
  19    7               6               771     25      376
  19    8               6               250     25      122
  19    9               6               458     25      195

The 19x19 even database would look a lot like
http://dridgway.com/Go/fuseki19-0.db.gz, the file I posted earlier.
Small boards are in http://dridgway.com/Go/smalldb.tgz, and full board
handicaps are in http://dridgway.com/Go/full-handi.tgz.

There's a tradeoff between minimum player strength and number of
games. I've tuned for maximizing strength up to 1d given > 2000 games,
which ought to produce a reasonable amount of variety in play.  Depth
goes up to 25 in 19x19. For even and H2, there are some lines that
deep, but for higher handicaps I suspect this just amounts to ensuring
that games with < 25 moves get excluded, which seems like a good idea.
Note that there are no patterns for 9x9 handicap > 2 and 13x13
handicap > 0. Demanding 8-10k players, I have only 20-30 games to work
with, which doesn't seem like enough. We could either keep the
existing patterns, or just rely on the code in fuseki.c to generate
moves in these cases.

For size/handicap combinations where there's < 1000 games, the
resulting number of patterns is kind of small. We might want to think
about relaxing the popularity cutoff to allow moves which appear only
once, to give more variety of play.

Since we can now control popularity while rebuilding the opening db
itself, it makes sense to now get rid of the popularity cutoff in
fuseki.c. If we want a more stringent cutoff than the one above, it
can be done in generating the opening db.

I haven't tried to restrict total number of patterns for its own sake.
This might be an issue in the 19x19 even db. If so, we need to decide
how big it can be.

I haven't reweighted based on results, either results in the training set
(though the stats are in the files) or GNU Go's game results. Nor have I
made sure that patterns deleted from the existing db are also missing
here. I think all of this should be done by hand.

For reference, here's the comparable table for the existing opening db.
The new set is strictly better than the old set (better players, more
games, and more patterns), except for 9x9 handicap and all 13x13. Note
that the existing 13x13 pattern set required accepting moves which
appeared in only one game.

  Size  Handicap        MinStrength     Games   Patterns
  9     0               8               1625    849
  9     2               16              500
  9     3               16              117
  9     4               16              78
  9     5               16              43
  9     6               16              3
  9     7               16              0
  9     8               16              4
  9     9               16              2
  9     2-9             16              747     473
  9     0-9             8-16            2372    1322
  13    0               10              1591    2000
  13    2               10              146
  13    3               10              135     
  13    4               10              304
  13    5               10              124
  13    6               10              13
  13    7               10              13
  13    8               10              3
  13    9               10              23
  13    2-9             10              761     1000
  13    0-9             10              2352    3000
  19    0               0               6203    1000
  19    2               7               4382
  19    3               7               2547
  19    4               7               1642
  19    5               7               781
  19    6               7               481
  19    7               7               190
  19    8               7               77
  19    9               7               175
  19    2-9             7               10275   500     
  19    0-9             0-7             16478   1500


Let me know if any of this sounds reasonable, if I can provide more
information about any of the various tradeoffs, if anyone has more games
that ought to be included, and whether/how we should move forward on this.

Thanks!

doug.