Sunday, May 11, 2014

What is Sancho

This post is just to provide a little background about the overall structure of the Sancho GGP player, as a basis for later posts.

Sancho is based upon the open-source ggp-base Java codebase for GGP, which may be found on GITHub at, 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

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)

No comments:

Post a Comment