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 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)


No comments:

Post a Comment