npm's personal messenger

    gmcts

    0.1.2 • Public • Published

    Downloads Auto Test Status license Gitter chat

    gMCTS : Generic Monte Carlo Tree Search

    This implementation of MCTS makes minimal assumptions about your simulation (or game), allowing you to focus on making your simulation and have gMCTS do the search.

    Section Links : Construction , Execution , Examples , FAQ , Related , and References

    Construction

    gMCTS constructor

    var gMCTS = require('gmcts')
    var search = gMCTS.new()

    Or as a one-liner

    var search = require('gmcts').new()

    Execution

    search.simulate( simulation , C=2 )

    Do one full simulation. This does everything needed under the covers needed for MCTS including the following steps : tree traversal, node expansion, rollout, and backprop. simulation is an object that is or wraps your simulation, and C is the exploration constant (default of 2). This returns the final output of the simulation.

    var result = search.simulate( simulation )

    search.best_action()

    Retrive the action with the best score.

    var best = search.best_action()

    If there are two actions, 'left' and 'right' with scores 7 and 2 respectively, then...

    console.log(action_n_score)
    'left'

    search.action_scores()

    Retrieve the actions and scores.

    var action_n_score = gMCTS.actions_and_scores()

    If there are two actions, 'left' and 'right' with scores 7 and 2 respectively, then...

    console.log(action_n_score)
    [ {action:'left',score:7} , {action:'right',score:2} ]

    Simulation

    This is the specification of the simulation object that you pass to gMCTS

    var simulation = {
        'get_actions' : // return a list of possible actions given the current state of the simulation
            function get_actions(),
        'do_action' : // preform the given action 
            function do_action(action),
        'is_terminal' : // return True if the simulation has 'ended'
            function is_terminal(),
        'value' : // the 'value' of the simulation at its current state.  Only called if the simulation is terminal
            function value()
    }

    get_actions

    Must return a list of objects that can be an associative array key, like strings or integers.

    do_action

    Is called with an action collected from get_actions. This needs to update the internal state of the simulation.

    is_terminal

    Return true if the simulation has 'ended', false otherwise. The end condition is of your own choice, but ensure there is an end condition. If your simulation doesn't end after a fixed number of actions, consider adding a counter and returning true for is_terminal after 1,000 or so actions, to avoid an infinite loop.

    value

    The extimated value of the simulation

    Example

    If you have installed this as a npm dependency first change directory to node_modules/gmcts/.

    Template

    The template is a boiler plate of how to get started. It has a dummy simulation stubbed out. Execute it like so:

    node examples/template.js 
    

    Demo

    A simulation that mimics John Levine's example in this video

    node examples/demo.js 
    

    There are 7 states, S0, S1, ... S6, with actions (A1, A2 ... A6) that go to exactly their corresponding state. The simulation starts in S0, which has actions A1 and A2 that go to S1 and S2 accordingly. The whole graph looks like this

    S0 ---> action A1 ---> S1 ---> action A3 ---> S3
        |                      |
        |                      --> action A4 ---> S4 
        |
        |
        --> action A2 ---> S2 ---> action A5 ---> S5
                               |
                               --> action A6 ---> S6
    

    The rollout values for the different states are as follows

    S1 = 20
    S2 = 10
    S3 = 0
    S5 = 14
    

    After 4 simulations search.action_scores() will correctly return that action A1 has a value of 10 and A2 has a value of 12.

    Related AI Projects

    This is part of a set of related projects.

    References

    Install

    npm i gmcts

    DownloadsWeekly Downloads

    0

    Version

    0.1.2

    License

    Unlicense

    Unpacked Size

    15.4 kB

    Total Files

    7

    Last publish

    Collaborators

    • panchishin