Sancho is based upon the open-source ggp-base Java codebase for GGP, which may be found on GITHub at https://github.com/ggp-org/ggp-base, and which provides a large set of utility and template classes for the construction of GGP players. The Sancho forked repository is also available on GITHub at https://github.com/SteveDraper/ggp-base.
At its core, Sancho is an MCTS player with a number of tweaks, the main ones being:
- A high performance propositional-network-based state machine. I'll talk more about this in a future post, but for background, propositional networks (or propnets for short) are a variation of Petri networks, and represent the state machine effectively as a sequence of virtual logic gates, whose outputs are propositions about or within the state of the state machine.
- Replacement of the MCTS tree with a more general graph, which allows for transitions between lines of play without duplication of nodes for any given state
- Bounded size MCTS node structure, independent of number of expansions performed (necessary for memory scalability as the number of expansions performed increases)
- Active trimming of lines that have fully-determined outcomes, propagating those outcomes up the MCTS structure to the highest level at which they remain fully determined (with best play)
- An efficient infrastructure for parallelization across threads
- Use of heuristics, determined during game setup time, to aid MCTS selection in preferentially expanding some branches
- Static analysis to identify game factorization opportunities (currently just disjunctive ones), and the ability to play such games with factorized search
- Static analysis to identify significant latches (ongoing work)