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)


8 comments:

  1. I am really enjoying reading your well written articles. It looks like you spend a lot of effort and time on your blog. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work.

    Simple Linear Regression

    ReplyDelete
  2. Thank you for helping people get the information they need. Great stuff as usual. Keep up the great work!!!
    360digitmg

    ReplyDelete
  3. This was a very informative article, indeed loved to read and clear my doubts. Keep us posted a lot more blogs.

    AWS Training in Hyderabad

    ReplyDelete
  4. Really an awesome blog and informative content. Thanks for sharing with us. If you want to become a data scientist, then check out the following link.
    Data Science Training Institute in Hyderabad

    ReplyDelete
  5. I recently came across your article and have been reading along. I want to express my admiration of your writing skill and ability to make readers read from the beginning to the end. I would like to read newer posts and to share my thoughts with you.
    data scientist course in hyderabad

    ReplyDelete
  6. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. Great work
    full stack developer course with placement

    ReplyDelete