| blob | 80ccb0334e0fb8f581553d5742bf9e933e1df4a9 |
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 | -- | tactical library |
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 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
37 * "aux library" provides extra functions like static tactical evaluation
38 and pattern matching; it is somewhat interwound with "core" component
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
47 * "tactical library" provides extended interfaces for the go board,
48 most important non-trivial tactical information
50 tactics/
52 * "engine" receives notifications about opponent moves and is asked
53 to generate a move to play on given board
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
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
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
75 * Also, several ways of testing Pachi are provided:
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)
83 UCT architecture
84 ================
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:
89 +-------------+ +-----+ +-------------------+
90 | node policy | -- | UCT | --- | node prior-hinter |
91 +-------------+ +-----+ +-------------------+
92 | |
93 +---------+ |
94 | playout | -----'
95 +---------+
97 * "UCT" is the core of the engine
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
106 * "node prior-hinter" assigns newly created nodes preliminary success
107 statistics ("prior values") to focus the search better
109 prior.[ch] variety of methods for setting the priors
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
115 policy/ucb1 the old-school original simple policy
116 policy/ucb1amaf the AMAF/RAVE-based policy gathering statistics rapidly
118 * "dynkomi driver" dynamically determines self-imposed extra virtual komi
120 dynkomi.[ch]
123 Board Implementation
124 ====================
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.
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.
138 Ruleset
139 -------
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.
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).
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.
159 GTP Implementation
160 ==================
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.
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.
173 General Pattern Matcher
174 =======================
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.
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
185 (feature1:payload feature2:payload ...)
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.
198 There are few pre-made scripts to make the initialization of the pattern
199 matcher easy:
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.
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.
212 * tools/pattern_spatial_show.pl ID: Shows spatial pattern of given id
213 in 2D plane.
215 * tools/pattern_bayes_gen.sh: Generates a Bayesian probability table
216 for each pattern in a SGF collection. The computed number is the empiric
217 probability of playing a given pattern when it is available on board.
220 Plugin API
221 ==========
223 The UCT engine allows external plugins to be loaded and provide external
224 knowledge for various heuristics - currently just biasing the MCTS priors,
225 but more can be added easily. The plugins should follow the API in
226 <uct/plugin.h> - see that file for details.
229 Joseki Patterns
230 ===============
232 Joseki patterns can be generated from variations of a SGF file. Josekis
233 are matched per-quadrant, no other move must be within the quadrant. See
234 joseki/README for details on usage of the auxiliary engine and a full
235 recipe for making Pachi play according to joseki sequences extracted from
236 the Kogo dictionary.
239 Opening Book
240 ============
242 The UCT engine can "pre-read" the starting board position and
243 dump the core of the built tree to a file, loading it later. This is
244 called a 'tbook' (as in "tree book") and can be generated using the
245 tools/gentbook.sh script. The newly generated file is automatically
246 used by the UCT engine when found.
248 Alternatively, there is a support for directly used opening book
249 (so-called fbook, a.k.a. "forced book" or "fuseki book"). The book
250 is stored in a text file in Fuego-compatible format and can be loaded
251 using the ./pachi -f parameter. A naive way to build such a book
252 based on shell-based, twogtp-based UCT is available through the
253 tools/autobook/ framework.
256 Local Trees
257 ===========
259 This is a mostly unique idea in Pachi, currently in development;
260 it does not work too well yet, but Pasky has great hopes for it in
261 the future.
263 A local tree is a tree comprising of (CFG-topologically) local
264 sequences, built in parallel with the real game tree; there is
265 a separate tree for black-first and white-first sequences. E.g if
266 the game tree (on empty board) consists of D4-C6-D6-Q16-O17-D7,
267 the coresponding local tree sequences are (black) D4-C6-D6, (white)
268 Q16-O17 and (white) D7. The simulation result is then recorded as
269 usual in the game tree, but also in the corresponding local trees.
271 The goal of this is to dynamically build a cache of various
272 resolutions of local situations. This is to overcome cases where
273 the proper resolution of a given situation is easily found in
274 the tree, but improper heuristical bisaes keep muddying the
275 evaluation down.
277 Exactly what kind of values to store in the local tree nodes is
278 still an open question. The original approach has been to simply
279 use simulation results directly or biased on base "value temperature";
280 now, we are experimenting with survival rate of the "base stone"
281 of the branch (the first move in the branch sequence). We also intend
282 to integrate criticality information with local tree data.
284 The local trees are descended in parallel with the main tree.
285 The values stored in local trees are added to the RAVE term
286 from the main tree during node selection. We also wish to use
287 the information from local trees in the simulations, but this is
288 still subject to research.
290 To enable local trees usage, pass local_tree=1 to the UCT engine.
291 There are many further knobs to twiddle, too.