HACKING

   1 This is brief developer-oriented overview in Pachi structure.
   2
   3 Pachi is completely Go-specific (c.f. Fuego; though e.g. atari go support
   4 should be easy to add), but fairly modular. It has been built with focus
   5 on MonteCarlo-based play, but it can in principle be used for other
   6 play engines as well.
   7
   8
   9 Basic architecture
  10 ==================
  11
  12 Pachi consists of the following components:
  13
  14
  15   +------+    +--------+    +---------+    +------------------+
  16   | core | -- | engine | -- | playout | -- | tactical library |
  17   +------+    +--------+    +---------+    +------------------+
  18                      |        |
  19                   +-------------+
  20                   | aux library |
  21                   +-------------+
  22
  23 * "core" takes care of the program's lifetime, GTP interface and basic
  24   fast Go board implementation
  25
  26         pachi.c         global initialization and the main loop
  27         version.h       current version information
  28         debug.h         debugging infrastructure
  29         random.[ch]     fast random number generator
  30         gtp.[ch]        GTP protocol interface
  31         network.[ch]    Network interface (useful for distributed engine)
  32         timeinfo.[ch]   Time-keeping information
  33         stone.[ch]      one board point coloring definition
  34         move.[ch]       one board move definition
  35         board.[ch]      board definition and basic interface
  36
  37 * "aux library" provides extra functions like static tactical evaluation
  38   and pattern matching; it is somewhat interwound with "core" component
  39
  40         mq.h            "move queue" data structure
  41         stats.h         "move statistics" data structure
  42         probdist.[ch]   "probability distribution" data structure
  43         ownermap.[ch]   simulation-based finalpos. "owner map" data structure
  44         pattern3.[ch]   fast 3x3 spatial pattern matcher
  45         pattern.[ch]    general multi-feature pattern matcher
  46
  47 * "tactical library" provides extended interfaces for the go board,
  48   most important non-trivial tactical information
  49
  50         tactics/
  51
  52 * "engine" receives notifications about opponent moves and is asked
  53   to generate a move to play on given board
  54
  55         engine.h        abstract engine interface
  56         random/         example "random move generator" engine
  57         replay/         example "playout move generator" engine
  58         montecarlo/     simple treeless Monte Carlo engine, quite bitrotten
  59         uct/            the main UCT-player engine, see below
  60         distributed/    "meta-engine" for distributed play by orchestrating
  61                                 several UCT engines on different computers
  62         patternscan/    auxiliary engine for harvesting patterns from
  63                                 existing games
  64         joseki/         auxiliary engine for generating joseki patterns
  65
  66 * "playout" policy is asked to generate moves to play during the Monte Carlo
  67   simulations, and to provide rough evaluation of moves feasibility for
  68   the engine
  69
  70         playout.[ch]    abstract playout policy interface,
  71                                 Monte Carlo simulation execution
  72         playout/light   uniformly random playout policy
  73         playout/moggy   rule-based "Mogo-like" playout policy
  74
  75 * Also, several ways of testing Pachi are provided:
  76
  77         t-unit/         interface for writing unit-tests for specific
  78                                 functionality, mainly tactics
  79         t-play/         interface for testing performance by playing games
  80                                 against a fixed opponent (e.g. GNUGo)
  81
  82
  83 UCT architecture
  84 ================
  85
  86 The UCT engine (the proper name should be MCTS as it does not have that
  87 much common with classic UCT now) has non-trivial structure by itself:
  88
  89   +-------------+    +-----+     +-------------------+
  90   | node policy | -- | UCT | --- | node prior-hinter |
  91   +-------------+    +-----+     +-------------------+
  92                         |           |
  93                    +---------+      |
  94                    | playout | -----'
  95                    +---------+
  96
  97 * "UCT" is the core of the engine
  98
  99         uct.[ch]        engine initialization, public interface
 100         internal.h      internal state and data structures
 101         tree.[ch]       minimax move tree with success statistics
 102         walk.[ch]       filling the tree by walking it many times
 103                                 and running MC simulations from leaves
 104         slave.[ch]      engine interface for the distributed engine
 105
 106 * "node prior-hinter" assigns newly created nodes preliminary success
 107   statistics ("prior values") to focus the search better
 108
 109         prior.[ch]      variety of methods for setting the priors
 110
 111 * "node policy" mainly chooses the current node's child to descend
 112   through during the tree walk, based on the already recorded statistics;
 113   it must balance exploration and exploitation well during the selection
 114
 115         policy/ucb1     the old-school original simple policy
 116         policy/ucb1amaf the AMAF/RAVE-based policy gathering statistics rapidly
 117
 118 * "dynkomi driver" dynamically determines self-imposed extra virtual komi
 119
 120         dynkomi.[ch]
 121
 122
 123 Board Implementation
 124 ====================
 125
 126 The infrastructure is optimized for speed to make it well suited
 127 for bruteforce engines, however tradeoffs are made to make it useful
 128 for heavier MonteCarlo playouts as well (e.g. real liberties are
 129 tracked instead of pseudoliberties). If you are looking for raw
 130 light playout speed, libEGO is better choice.
 131
 132 In general, arbitrary board sizes are supported; however, board sizes
 133 smaller than 9x9 have not been tested and board sizes larger than 25x25
 134 are not supported by GTP - also, in theory some buffer overflows might
 135 happen with board sizes larger than 19x19. The engine parameters are
 136 primarily tuned for 19x19 play.
 137
 138 Ruleset
 139 -------
 140
 141 While the Pachi engines generally play according to Chinese rules,
 142 internally, Pachi uses Tromp-Taylor rules because they are simple,
 143 fast and universal; they are very close to the New Zealand rules.
 144 That means, it simply counts the number of stones and one-point eyes
 145 of each color on the board, plus komi and handicap correction.
 146
 147 Tromp-Taylor rules also mean that multi-stone suicide is allowed! If you
 148 do not like that (basically if you want to pretend it plays according
 149 to Chinese rules), you need to rule that out in your engine, currently.
 150 The provided engines DO avoid multi-stone suicide, though it is allowed
 151 in the playouts for performance reasons (perhaps we should re-visit that
 152 decision in light of heavy playouts).
 153
 154 Tromp-Taylor rules have positional superko; the board implementation
 155 will set a flag if it is violated, but play the move anyway. You need
 156 to enforce the superko rule in your engine.
 157
 158
 159 GTP Implementation
 160 ==================
 161
 162 ...is a very sad hack. ENSURE that only trusted parties talk to Pachi's
 163 GTP interface, as it is totally non-resilient to any kind of overflow
 164 or bad input attacks and allowing arbitrary input to be entered within
 165 is a major security hole. Yes, this needs to be cleaned up. Also, currently
 166 engines cannot plug in their own commands and there is no GoGui interface.
 167
 168 Pachi supports only few GTP commands now. Most importantly, it does not
 169 support the undo command.  The final_status_list command requires engine
 170 support.
 171
 172
 173 General Pattern Matcher
 174 =======================
 175
 176 Pachi has in-development general pattern matcher that can match various
 177 sets of features (spatial and others), inspired by the CrazyStone and
 178 van der Werf - de Groot - Stern pattern model. Please see pattern.h
 179 for detailed description of the pattern concept and recognized features.
 180
 181 To harvest patterns, use 'pachi -e patternscan' (see patternscan/patternscan.c
 182 for available options).  The output of the pattern scanner are two data
 183 structures: The matched patterns
 184
 185         (feature1:payload feature2:payload ...)
 186
 187 and spatial dictionary. "Spatial" feature represents a particular
 188 configuration of stones in a circle around the move-to-play; each
 189 configuration has its own record in the dictionary and the spatial
 190 feature references only the id in the dictionary; so you need to keep
 191 both the patterns and the "patterns.spat" file.  Normally, 'patternscan'
 192 will only match already existing dictionary entries, but you
 193 can pass it "gen_spat_dict" so that it appends all newly found spatial
 194 features to the dictionary - use "spat_threshold" to limit recording
 195 only to frequently occuring spatial features; to start the dictionary
 196 from scratch, simply remove any existing "patterns.spat" file.
 197
 198 There are few pre-made scripts to make the initialization of the pattern
 199 matcher easy:
 200
 201 * tools/pattern_byplayer.sh: Sorts out patterns from given SGF collection
 202   by player names, one player per file in a dedicated directory. This is
 203   useful if you want to use the patterns to e.g. recognize games of a
 204   player by characteristic patterns. Spatial dictionary is autogenerated
 205   in full.
 206
 207 * tools/pattern_spatial_gen.sh: Initializes spatial dictionary by spatial
 208   features found at least N times in given SGF collection.  This is useful
 209   for further gathering of general pattern statistics while keeping
 210   the amount of spatial features manageable.
 211
 212 * tools/pattern_spatial_show.pl ID: Shows spatial pattern of given id
 213   in 2D plane.
 214
 215
 216 Plugin API
 217 ==========
 218
 219 The UCT engine allows external plugins to be loaded and provide external
 220 knowledge for various heuristics - currently just biasing the MCTS priors,
 221 but more can be added easily. The plugins should follow the API in
 222 <uct/plugin.h> - see that file for details.
 223
 224
 225 Joseki Patterns
 226 ===============
 227
 228 Joseki patterns can be generated from variations of a SGF file. Josekis
 229 are matched per-quadrant, no other move must be within the quadrant. See
 230 joseki/README for details on usage of the auxiliary engine and a full
 231 recipe for making Pachi play according to joseki sequences extracted from
 232 the Kogo dictionary.
 233
 234
 235 Opening Book
 236 ============
 237
 238 The UCT engine can "pre-read" the starting board position and
 239 dump the core of the built tree to a file, loading it later. This is
 240 called a 'tbook' (as in "tree book") and can be generated using the
 241 tools/gentbook.sh script. The newly generated file is automatically
 242 used by the UCT engine when found.
 243
 244 Alternatively, there is a support for directly used opening book
 245 (so-called fbook, a.k.a. "forced book" or "fuseki book"). The book
 246 is stored in a text file in Fuego-compatible format and can be loaded
 247 using the ./pachi -f parameter. A naive way to build such a book
 248 based on shell-based, twogtp-based UCT is available through the
 249 tools/autobook/ framework.
 250
 251
 252 Local Trees
 253 ===========
 254
 255 This is a mostly unique idea in Pachi, currently in development;
 256 it does not work too well yet, but Pasky has great hopes for it in
 257 the future.
 258
 259 A local tree is a tree comprising of (CFG-topologically) local
 260 sequences, built in parallel with the real game tree; there is
 261 a separate tree for black-first and white-first sequences. E.g if
 262 the game tree (on empty board) consists of D4-C6-D6-Q16-O17-D7,
 263 the coresponding local tree sequences are (black) D4-C6-D6, (white)
 264 Q16-O17 and (white) D7. The simulation result is then recorded as
 265 usual in the game tree, but also in the corresponding local trees.
 266
 267 The goal of this is to dynamically build a cache of various
 268 resolutions of local situations. This is to overcome cases where
 269 the proper resolution of a given situation is easily found in
 270 the tree, but improper heuristical bisaes keep muddying the
 271 evaluation down.
 272
 273 Exactly what kind of values to store in the local tree nodes is
 274 still an open question. The original approach has been to simply
 275 use simulation results directly or biased on base "value temperature";
 276 now, we are experimenting with survival rate of the "base stone"
 277 of the branch (the first move in the branch sequence). We also intend
 278 to integrate criticality information with local tree data.
 279
 280 The local trees are descended in parallel with the main tree.
 281 The values stored in local trees are added to the RAVE term
 282 from the main tree during node selection. We also wish to use
 283 the information from local trees in the simulations, but this is
 284 still subject to research.
 285
 286 To enable local trees usage, pass local_tree=1 to the UCT engine.
 287 There are many further knobs to twiddle, too.