HACKING

This is brief developer-oriented overview of Pachi structure.

The aim of the software framework is to make it easy to plug your
engine to the common infrastructure and implement your ideas while
minimalizing the overhead of implementing the GTP, speed-optimized
board implementation, etc.  Also, there are premade random playout
and UCT tree engines, so that you can directly tweak only particular
policies.  The infrastructure is pretty fast and it should be quite
easy for you (or us) to extend it to provide more facilities for
your engine.

Pachi is completely Go-specific (c.f. Fuego; though e.g. atari go support
should be easy to add), but fairly modular. It has been built with focus
on MonteCarlo-based play, but it can in principle be used for other
play engines as well.


Basic architecture
==================

Pachi consists of the following components:

  +------+    +--------+    +---------+
  | core | -- | engine | -- | playout |
  +------+    +--------+    +---------+
                     |        |     |
            +-------------------+  +---------+
            |      modules      |--| tactics |
            | dcnn, patterns    |  +---------+
            | joseki, ownermap  |
            +-------------------+

* "core" takes care of the program's lifetime, GTP interface and basic
  fast Go board implementation

	pachi.c		global initialization and the main loop
	version.h	current version information
	debug.h		debugging infrastructure
	random.[ch]	fast random number generator
	gtp.[ch]	GTP protocol interface
	network.[ch]	Network interface (useful for distributed engine)
	timeinfo.[ch]	Time-keeping information
	stone.[ch]	one board point coloring definition
	move.[ch]	one board move definition
	board.[ch]	board definition and basic interface
	gogui.[ch]      gogui analyze commands

* "modules" provides extra functions like static tactical evaluation
  and pattern matching; it is somewhat interwound with "core" component

	mq.h		 "move queue" data structure
	stats.h		 "move statistics" data structure
	probdist.[ch]	 "probability distribution" data structure
	ownermap.[ch]	 simulation-based finalpos. "owner map" data structure
	fbook.[ch]       fuseki database (opening book)
	pattern3.[ch]	 fast 3x3 spatial pattern matcher

* "dcnn" manages neural networks for root node evaluation (policy network)

	dcnn/dcnn.[ch]			network loading and evaluation (c side)
	dcnn/caffe.cpp			network loading and evaluation (c++ side)
	dcnn/dcnn_engine.c		example "dcnn move generator" engine
	dcnn/blunder.c			filter out some obvious bad moves from dcnn output before
					they get used in search to work around dcnn blind spots
	dcnn/blunderscan.c		internal engine for dcnn blunder debugging

* "pattern" mm pattern matcher provides priors to guide tree search

	pattern/pattern.[ch]		general multi-feature pattern matcher
	pattern/spatial.[ch]		spatial pattern matching
	pattern/prob.[ch]		pattern-based move predictor
	pattern/pattern_engine.c	example "mm patterns move generator" engine, used for testing / debugging
	pattern/patternscan.c		auxiliary engine used by mm pattern training pipeline
	training/                       mm training pipeline
	patterns_mm.spat		spatial patterns data
	patterns_mm.gamma		mm patterns gammas

* "joseki" provides joseki sequences to guide tree search when playing without dcnn

	joseki/*.sgf			joseki data
	joseki19.gtp			joseki data (as GTP stream)
	joseki/joseki.[ch]		pattern based joseki engine
	joseki/joseki_engine.c		"joseki move generator" engine used to visualize joseki data in gogui
	joseki/josekiload.c		load joseki data (internal engine)

* "josekifix" allows to override joseki moves that the dcnn plays poorly

	josekifix/*.sgf			joseki overrides (SGF file)
	josekifix.gtp			joseki overrides (as GTP stream)
	josekifix/josekifix.[ch]	pattern based joseki overrides matching
	josekifix/josekifixload.c	load override data (internal engine) 
	josekifix/fuseki.c		choose initial fuseki

* "tactics" provides extended interfaces for the go board,
  most important non-trivial tactical information

	tactics/1lib.c		dealing with 1-liberty groups (captures)
	tactics/2lib.c		dealing with 2-liberties groups
	tactics/dragon.c	recognizing connected groups
	tactics/ladder.c	ladder checker
	tactics/nakade.c	recognizing dead shapes
	tactics/nlib.c		dealing with n-liberties groups
	tactics/seki.c		handling sekis
	tactics/selfatari.c	distinguish between good / bad self-ataris
	tactics/util.c		board utils

* "engine" receives notifications about opponent moves and is asked
  to generate a move to play on given board

	engine.h	abstract engine interface
	uct/		the main UCT-player engine, see below
	distributed/	"meta-engine" for distributed play by orchestrating
			    several UCT engines on different computers
  other engines:
	engines/external.c      call external GTP engine
	engines/random.c	example "random move generator" engine
	engines/replay.c	example "playout move generator" engine
	engines/montecarlo.c	simple treeless Monte Carlo engine, quite bitrotten

* "playout" policy is asked to generate moves to play during the Monte Carlo
  simulations, and to provide rough evaluation of moves feasibility for
  the engine

	playout.[ch]	abstract playout policy interface,
				Monte Carlo simulation execution
	playout/light	uniformly random playout policy
	playout/moggy	rule-based "Mogo-like" playout policy

* Also, several ways of testing Pachi are provided:

	t-unit/		interface for writing unit-tests for specific
				functionality, mainly tactics
	t-play/		interface for testing performance by playing games
				against a fixed opponent (e.g. GNUGo)
	t-predict/      test prediction rates of various components


UCT architecture
================

The UCT engine (the proper name should be MCTS as it does not have that
much common with classic UCT now) has non-trivial structure by itself:

  +-------------+    +-----+     +-------------------+
  | node policy | -- | UCT | --- | node prior-hinter |
  +-------------+    +-----+     +-------------------+
                        |           |
                   +---------+      |
                   | playout | -----'
                   +---------+

* "UCT" is the core of the engine

	uct.[ch]	engine initialization, public interface
	internal.h	internal state and data structures
	tree.[ch]	minimax move tree with success statistics
	walk.[ch]	filling the tree by walking it many times
				and running MC simulations from leaves
	slave.[ch]	engine interface for the distributed engine

* "node prior-hinter" assigns newly created nodes preliminary success
  statistics ("prior values") to focus the search better

	prior.[ch]	variety of methods for setting the priors
			(dcnn for root node, mm patterns for others)

* "node policy" mainly chooses the current node's child to descend
  through during the tree walk, based on the already recorded statistics;
  it must balance exploration and exploitation well during the selection

	policy/ucb1	the old-school original simple policy
	policy/ucb1amaf	the AMAF/RAVE-based policy gathering statistics rapidly

* "dynkomi driver" dynamically determines self-imposed extra virtual komi

	dynkomi.[ch]


UCT performance
===============

What's the cost of the different components, and where do the cpu cycles go ?

Here's the result of a performance analysis on Raspberry Pi with Pachi 12.70
to answer that question (see PERFS for details):

during tree search:
   uct search takes 30% cpu time
   leaving          70% for playouts.

if uct is now 100% and we break it down further:
  priors represent     54% of that   (pattern prior 40%)
  ucb1amaf policy      38%
  tree stuff etc        8%


UCT search modes
================

There are 4 main modes for move generation depending on client / options used:

   mode                 typical clients      gtp command          uct options
 ------------------------------------------------------------------------------
   genmove                   all             genmove
   genmove_analyze      Lizzie, Sabaki       lz-genmove_analyze                     
   pondering                 all             genmove               pondering   
   analyze              Lizzie, Sabaki       lz-analyze

* genmove
  this is the normal case: client sends "genmove" gtp command to ask engine
  for a move, uct starts search in the foreground and stops when given time
  or playouts requirements are met.
  On kgs there's also "kgs-genmove_cleanup" command which is a special mode
  entered when playing chinese and opponent doesn't agree on dead stones
  (both players keep playing until all dead stones are removed)
* genmove_analyze
  used by Lizzie, Sabaki etc to display fancy graphics during genmove
  (gogui uses "gogui-livegfx" for that purpose). same as genmove but client uses
  "lz-genmove_analyze" gtp command to get updates while search is going on.
* pondering
  after genmove search continues in the background while opponent is thinking.
  pondering stops at next "play" command.
* analyze  (Lizzie, Sabaki)
  client sends "lz-analyze" gtp command. no move is generated but search is
  started in the background and updates sent to client in leela-zero format.
  search stops when next gtp command is received.

There's also "pachi-genmoves" which is used by the distributed engine to start
search in the background and report state periodically.


Board Implementation
====================

The infrastructure is optimized for speed to make it well suited
for bruteforce engines, however tradeoffs are made to make it useful
for heavier MonteCarlo playouts as well (e.g. real liberties are
tracked instead of pseudoliberties). If you are looking for raw
light playout speed, libEGO is better choice.

In general, arbitrary board sizes are supported; however, board sizes
smaller than 9x9 have not been tested and board sizes larger than 25x25
are not supported by GTP - also, in theory some buffer overflows might
happen with board sizes larger than 19x19. The engine parameters are
primarily tuned for 19x19 play.

Ruleset
-------

While the Pachi engines generally play according to Chinese rules,
internally, Pachi uses Tromp-Taylor rules because they are simple,
fast and universal; they are very close to the New Zealand rules.
That means, it simply counts the number of stones and one-point eyes
of each color on the board, plus komi and handicap correction.

Tromp-Taylor rules also mean that multi-stone suicide is allowed! If you
do not like that (basically if you want to pretend it plays according
to Chinese rules), you need to rule that out in your engine, currently.
The provided engines DO avoid multi-stone suicide, though it is allowed
in the playouts for performance reasons (perhaps we should re-visit that
decision in light of heavy playouts).

Tromp-Taylor rules have positional superko; the board implementation
will set a flag if it is violated, but play the move anyway. You need
to enforce the superko rule in your engine.


GTP Implementation
==================

... should be better now, but has certainly not been written (or tested)
with security in mind. ENSURE that only trusted parties talk to Pachi's GTP
interface, as it totally non-resilient to any kind of overflow or bad input
attacks and allowing arbitrary input to be entered within is a major security
hole. Yes, this needs to be cleaned up.

Also, currently engines cannot plug in their own commands.
The final_status_list command requires engine support.


DCNN
====

dcnn/dcnn.c has the code that prepares the input planes from board state and
feeds that to caffe for dcnn evaluation (dcnn/caffe.cpp). If you want to use
a network with different inputs this is the place to accomodate it.


General Pattern Matcher
=======================

Pachi uses MM patterns to guide tree search. The pattern matcher runs on
the cpu each time a new node is explored. For each possible move it looks
for known spatial / tactical features and rates them according to learned
weights, which are obtained through supervised learning.
See pattern/README for details.


Plugin API
==========

The UCT engine allows external plugins to be loaded and provide external
knowledge for various heuristics - currently just biasing the MCTS priors,
but more can be added easily. The plugins should follow the API in
<uct/plugin.h> - see that file for details.


Joseki Database
===============

The joseki database is generated from variations of a SGF file. Josekis
patterns are matched based on spatial patterns: situation around previous
move and move to play must match (circle of 4 stones radius). See
joseki/README for details on how to generate the joseki database from sgf
files, and joseki.[ch] for the implementation. engines/josekiload.[ch] is
the aux engine for generating joseki patterns from gtp moves.


Opening Book
============

The UCT engine can "pre-read" the starting board position and
dump the core of the built tree to a file, loading it later. This is
called a 'tbook' (as in "tree book") and can be generated using the
tools/gentbook.sh script. The newly generated file is automatically
used by the UCT engine when found.

Alternatively, there is a support for directly used opening book
(so-called fbook, a.k.a. "forced book" or "fuseki book"). The book
is stored in a text file in Fuego-compatible format and can be loaded
using the ./pachi -f parameter. A naive way to build such a book
based on shell-based, twogtp-based UCT is available through the
tools/autobook/ framework.


Local Trees
===========

This is a mostly unique idea in Pachi, currently in development;
it does not work too well yet, but Pasky has great hopes for it in
the future.

A local tree is a tree comprising of (CFG-topologically) local
sequences, built in parallel with the real game tree; there is
a separate tree for black-first and white-first sequences. E.g if
the game tree (on empty board) consists of D4-C6-D6-Q16-O17-D7,
the coresponding local tree sequences are (black) D4-C6-D6, (white)
Q16-O17 and (white) D7. The simulation result is then recorded as
usual in the game tree, but also in the corresponding local trees.

The goal of this is to dynamically build a cache of various
resolutions of local situations. This is to overcome cases where
the proper resolution of a given situation is easily found in
the tree, but improper heuristical bisaes keep muddying the
evaluation down.

Exactly what kind of values to store in the local tree nodes is
still an open question. The original approach has been to simply
use simulation results directly or biased on base "value temperature";
now, we are experimenting with survival rate of the "base stone"
of the branch (the first move in the branch sequence). We also intend
to integrate criticality information with local tree data.

The local trees are descended in parallel with the main tree.
The values stored in local trees are added to the RAVE term
from the main tree during node selection. We also wish to use
the information from local trees in the simulations, but this is
still subject to research.

To enable local trees usage, pass local_tree=1 to the UCT engine.
There are many further knobs to twiddle, too.

Code is in local_tree branch.