joseki_load(): Introduce joseki pattern file parser
[pachi.git] / HACKING
blob4be377e9028d9b064357466304704ca20c71628a
1 This is brief developer-oriented overview in Pachi structure.
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.
9 Basic architecture
10 ==================
12 Pachi consists of the following components:
15   +------+    +--------+    +---------+
16   | core | -- | engine | -- | playout |
17   +------+    +--------+    +---------+
18                      |        |
19                   +-------------+
20                   | aux library |
21                   +-------------+
23 * "core" takes care of the program's lifetime, GTP interface and basic
24   fast Go board implementation
26         zzgo.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         timeinfo.[ch]   Time-keeping information
32         stone.[ch]      one board point coloring definition
33         move.[ch]       one board move definition
34         board.[ch]      board definition and basic interface
36 * "aux library" provides extra functions like static tactical evaluation
37   and pattern matching; it is somewhat interwound with "core" component
39         tactics.[ch]    extended interfaces for the go board
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         network.[ch]    Network interface (useful for distributed engine)
48 * "engine" receives notifications about opponent moves and is asked
49   to generate a move to play on given board
51         engine.h        abstract engine interface
52         random/         example "random move generator" engine
53         replay/         example "playout move generator" engine
54         montecarlo/     simple treeless Monte Carlo engine, quite bitrotten
55         uct/            the main UCT-player engine, see below
56         distributed/    "meta-engine" for distributed play by orchestrating
57                                 several UCT engines on different computers
58         patternscan/    auxiliary engine for harvesting patterns from
59                                 existing games
60         joseki/         auxiliary engine for generating joseki patterns
62 * "playout" policy is asked to generate moves to play during the Monte Carlo
63   simulations, and to provide rough evaluation of moves feasibility for
64   the engine
66         playout.[ch]    abstract playout policy interface,
67                                 Monte Carlo simulation execution
68         playout/light   uniformly random playout policy
69         playout/moggy   rule-based "Mogo-like" playout policy
70         playout/elo     probdist-based "CrazyStone-like" playout policy
72 * Also, several ways of testing Pachi are provided:
74         t-unit/         interface for writing unit-tests for specific
75                                 functionality, mainly tactics
76         t-play/         interface for testing performance by playing games
77                                 against a fixed opponent (e.g. GNUGo)
80 UCT architecture
81 ================
83 The UCT engine has non-trivial structure by itself:
85   +-------------+    +-----+     +-------------------+
86   | node policy | -- | UCT | --- | node prior-hinter |
87   +-------------+    +-----+     +-------------------+
88                         |           |
89                    +---------+      |
90                    | playout | -----'
91                    +---------+
93 * "UCT" is the core of the engine
95         uct.[ch]        engine initialization, public interface
96         internal.h      internal state and data structures
97         tree.[ch]       minimax move tree with success statistics
98         walk.[ch]       filling the tree by walking it many times
99                                 and running MC simulations from leaves
100         slave.[ch]      engine interface for the distributed engine
102 * "node prior-hinter" assigns newly created nodes preliminary success
103   statistics ("prior values") to focus the search better
105         prior.[ch]      variety of methods for setting the priors
107 * "node policy" mainly chooses the current node's child to descend
108   through during the tree walk, based on the already recorded statistics;
109   it must balance exploration and exploitation well during the selection
111         policy/ucb1     the old-school original simple policy
112         policy/ucb1amaf the AMAF/RAVE-based policy gathering statistics rapidly
114 * "dynkomi driver" dynamically determines self-imposed extra virtual komi
116         dynkomi.[ch]
119 Board Implementation
120 ====================
122 The infrastructure is optimized for speed to make it well suited
123 for bruteforce engines, however tradeoffs are made to make it useful
124 for heavier MonteCarlo playouts as well (e.g. real liberties are
125 tracked instead of pseudoliberties). If you are looking for raw
126 light playout speed, libEGO is better choice.
128 In general, arbitrary board sizes are supported; however, board sizes
129 smaller than 9x9 have not been tested and board sizes larger than 25x25
130 are not supported by GTP - also, in theory some buffer overflows might
131 happen with board sizes larger than 19x19. The engine parameters are
132 primarily tuned for 19x19 play.
134 Ruleset
135 -------
137 While the Pachi engines generally play according to Chinese rules,
138 internally, Pachi uses Tromp-Taylor rules because they are simple,
139 fast and universal; they are very close to the New Zealand rules.
140 That means, it simply counts the number of stones and one-point eyes
141 of each color on the board, plus komi and handicap correction.
143 Tromp-Taylor rules also mean that multi-stone suicide is allowed! If you
144 do not like that (basically if you want to pretend it plays according
145 to Chinese rules), you need to rule that out in your engine, currently.
146 The provided engines DO avoid multi-stone suicide, though it is allowed
147 in the playouts for performance reasons (perhaps we should re-visit that
148 decision in light of heavy playouts).
150 Tromp-Taylor rules have positional superko; the board implementation
151 will set a flag if it is violated, but play the move anyway. You need
152 to enforce the superko rule in your engine.
155 GTP Implementation
156 ==================
158 ...is a very sad hack. ENSURE that only trusted parties talk to Pachi's
159 GTP interface, as it is totally non-resilient to any kind of overflow
160 or bad input attacks and allowing arbitrary input to be entered within
161 is a major security hole. Yes, this needs to be cleaned up. Also, currently
162 engines cannot plug in their own commands and there is no GoGui interface.
164 Pachi supports only few GTP commands now. Most importantly, it does not
165 support the undo command.  The final_status_list command requires engine
166 support.
169 General Pattern Matcher
170 =======================
172 Pachi has in-development general pattern matcher that can match various
173 sets of features (spatial and others), inspired by the CrazyStone pattern
174 model. Please see pattern.h for detailed description of the pattern concept
175 and recognized features.
177 To harvest patterns, use 'zzgo -e patternscan' (see patternscan/patternscan.c
178 for available options).  The output of the pattern scanner are two data
179 structures: The matched patterns
181         (feature1:payload feature2:payload ...)
183 and spatial dictionary. "Spatial" feature represents a particular
184 configuration of stones in a circle around the move-to-play; each
185 configuration has its own record in the dictionary and the spatial
186 feature references only the id in the dictionary; so you need to keep
187 both the patterns and the "patterns.spat" file.  Normally, 'patternscan'
188 will only match already existing dictionary entries, but you
189 can pass it "gen_spat_dict" so that it appends all newly found spatial
190 features to the dictionary - use "spat_threshold" to limit recording
191 only to frequently occuring spatial features; to start the dictionary
192 from scratch, simply remove any existing "patterns.spat" file.
194 There are few pre-made scripts to make the initialization of the pattern
195 matcher easy:
197 * pattern_byplayer.sh: Sorts out patterns from given SGF collection by
198   player names, one player per file in a dedicated directory. This is
199   useful if you want to use the patterns to e.g. recognize games of a
200   player by characteristic patterns. Spatial dictionary is autogenerated
201   in full.
203 * pattern_spatial_gen.sh: Initializes spatial dictionary by spatial features
204   found at least N times in given SGF collection.  This is useful for
205   further gathering of general pattern statistics while keeping the amount
206   of spatial features manageable.
208 * pattern_spatial_show.pl ID: Shows spatial pattern of given id in 2D plane.
210 * pattern_mm.sh: Combines patternsacn engine and the MM tool (see below),
211   producing gamma values for harvested patterns.
213 Minorization-majorization (CrazyStone patterns)
214 -----------------------------------------------
216 The pattern harvester can be used together with the MM tool by Remi Coulom:
218         http://remi.coulom.free.fr/Amsterdam2007/mm.tar.bz2
220 This tool will compute relative strength of individual features for teaming
221 them up and using the outcoming probability distribution for generating moves.
222 There is a script that will take you from SGF game collection to gamma values
223 in single shot - "pattern_mm.sh".
225 The resulting "patterns.gamma" file contains mapping from feature instances
226 to gamma floats, representing the features strength; note that it is totally
227 meaningless without the accompanying "patterns.spat" file generated by the
228 pattern_gather script. This file is used for "full-scale" pattern matching
229 used for tree node priors. Another "fast" pattern feature set is used for
230 generation of in-playout probability distribution - gamma values for these
231 features are stored in "patterns.gammaf".
233 To make Pachi use the gamma values for tree bias and in MC playouts, use the
234 "elo" playout policy - but note that it's still in heavy development.
237 Plugin API
238 ==========
240 The UCT engine allows external plugins to be loaded and provide external
241 knowledge for various heuristics - currently just biasing the MCTS priors,
242 but more can be added easily. The plugins should follow the API in
243 <uct/plugin.h> - see that file for details.
246 Joseki Patterns
247 ===============
249 Joseki patterns can be generated from variations of a SGF file. Josekis
250 are matched per-quadrant, no other move must be within the quadrant. See
251 joseki/README for details on usage of the auxiliary engine.