The micmac Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The micmac Reference Manual

This is the micmac Reference Manual, version 0.0.2, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:17:00 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

# Micmac Manual

###### \[in package MICMAC\]
## micmac ASDF System Details

- Version: 0.0.2
- Description: Micmac is mainly a library of graph search algorithms
  such as alpha-beta, UCT and beam search, but it also has some MCMC
  and other slightly unrelated stuff.
- Licence: MIT, see COPYING.
- Author: Gábor Melis
- Mailto: [mega@retes.hu](mailto:mega@retes.hu)
- Homepage: [http://quotenil.com](http://quotenil.com)

## Introduction

### Overview

MICMAC is a Common Lisp library by [Gábor
Melis](http://quotenil.com) focusing on [graph
search](http://en.wikipedia.org/wiki/Graph_traversal) algorithms.

### Links

Here is the [official
repository](https://github.com/melisgl/micmac) and the [HTML
documentation](http://melisgl.github.io/mgl-pax-world/micmac-manual.html)
for the latest version.

## Graph Search

- [function] ALPHA-BETA STATE &KEY (DEPTH 0) ALPHA BETA CALL-WITH-ACTION MAYBE-EVALUATE-STATE LIST-ACTIONS RECORD-BEST

    Alpha-beta pruning for two player, zero-sum maximax (like minimax
    but both players maximize and the score is negated when passed
    between depths). Return the score of the game STATE from the point
    of view of the player to move at DEPTH and as the second value the
    list of actions of the principal variant.
    
    CALL-WITH-ACTION is a function of (STATE DEPTH ACTION FN). It
    carries out ACTION (returned by LIST-ACTIONS or NIL) to get the
    state corresponding to DEPTH and calls FN with that state. It may
    destructively modify STATE provided it undoes the damage after FN
    returns. CALL-WITH-ACTION is called with NIL as ACTION for the root
    of the tree, in this case STATE need not be changed. FN returns the
    same kinds of values as ALPHA-BETA. They may be useful for logging.
    
    MAYBE-EVALUATE-STATE is a function of (STATE DEPTH). If STATE at
    DEPTH is a terminal node then it returns the score from the point of
    view of the player to move and as the second value a list of actions
    that lead from STATE to the position that was evaluated. The list of
    actions is typically empty. If we are not at a terminal node then
    MAYBE-EVALUATE-STATE returns NIL.
    
    LIST-ACTIONS is a function of (STATE DEPTH) and returns a non-empty
    list of legal candidate moves for non-terminal nodes. Actions are
    tried in the order LIST-ACTIONS returns them: stronger moves
    
    CALL-WITH-ACTION, MAYBE-EVALUATE-STATE and LIST-ACTIONS are
    mandatory.
    
    RECORD-BEST, if non-NIL, is a function of (DEPTH SCORE ACTIONS). It
    is called when at DEPTH a new best action is found. ACTIONS is a
    list of all the actions in the principle variant corresonding to the
    newly found best score. RECORD-BEST is useful for graceful
    degradation in case of timeout.
    
    ALPHA and BETA are typically NIL (equivalent to -infinity,
    +infinity) but any real number is allowed if the range of scores can
    be boxed.
    
    See `test/test-alpha-beta.lisp` for an example.

- [function] BEAM-SEARCH START-NODES &KEY MAX-DEPTH (N-SOLUTIONS 1) (BEAM-WIDTH (LENGTH START-NODES)) EXPAND-NODE-FN EXPAND-BEAM-FN SCORE-FN UPPER-BOUND-FN SOLUTIONP-FN (FINISHEDP-FN SOLUTIONP-FN)

    In a graph, search for nodes that with the best scores with [beam
    search](http://en.wikipedia.org/wiki/Beam_search). That is, starting
    from START-NODES perform a breadth-first search but at each depth
    only keep BEAM-WIDTH number of nodes with the best scores. Keep the
    best N-SOLUTIONS (at most) complete solutions. Discard nodes known
    to be unable to get into the best N-SOLUTIONS (due to
    UPPER-BOUND-FN). Finally, return the solutions and the active
    nodes (the *beam*) as adjustable arrays sorted by score in
    descending order.
    
    START-NODES (a sequence of elements of arbitrary type). SCORE-FN,
    UPPER-BOUND-FN, SOLUTIONP-FN, FINISHEDP-FN are all functions of one
    argument: the node. SOLUTIONP-FN checks whether a node represents a
    complete solution (i.e. some goal is reached). SCORE-FN returns a
    real number that's to be maximized, it's only called for node for
    which SOLUTIONP-FN returned true. UPPER-BOUND-FN (if not NIL)
    returns a real number that equal or greater than the score of all
    solutions reachable from that node. FINISHEDP-FN returns true iff
    there is nowhere to go from the node.
    
    EXPAND-NODE-FN is also a function of a single node argument. It
    returns a sequence of nodes to 'one step away' from its argument
    node. EXPAND-BEAM-FN is similar, but it takes a vector of nodes and
    returns all nodes one step away from any of them. It's enough
    provide either EXPAND-NODE-FN or EXPAND-BEAM-FN. The purpose of
    EXPAND-BEAM-FN. is to allow more efficient, batch-like operations.
    
    See `test/test-beam-search.lisp` for an example.

- [function] PARALLEL-BEAM-SEARCH START-NODE-SEQS &KEY MAX-DEPTH (N-SOLUTIONS 1) BEAM-WIDTH EXPAND-NODE-FN EXPAND-BEAMS-FN SCORE-FN UPPER-BOUND-FN SOLUTIONP-FN (FINISHEDP-FN SOLUTIONP-FN)

    This is very much like BEAM-SEARCH except it solves a number of
    instances of the same search problem starting from different sets of
    nodes. The sole purpose of PARALLEL-BEAM-SEARCH is to amortize the
    cost EXPAND-BEAM-FN if possible.
    
    EXPAND-BEAMS-FN is called with sequence of beams (i.e. it's a
    sequence of sequence of nodes) and it must return another sequence
    of sequences of nodes. Each element of the returned sequence is the
    reachable nodes of the nodes in the corresponding element of its
    argument sequence.
    
    PARALLEL-BEAM-SEARCH returns a sequence of solutions sequences, and
    a sequence of active node sequences.
    
    See `test/test-beam-search.lisp` for an example.

### UCT

###### \[in package MICMAC.UCT\]
UCT Monte Carlo tree search. This is what makes current Go programs
tick. And Hex programs as well, for that matter. This is a cleanup
and generalization of code originally created in course of the
Google AI Challenge 2010.

For now, the documentation is just a reference. See
`test/test-uct.lisp` for an example.

- [class] UCT-NODE

    A node in the UCT tree. Roughly translates to a
    state in the search space. Note that the state itself is not stored
    explicity, but it can be recovered by \`replaying' the actions from
    the starting state or by customizing MAKE-UCT-NODE.

- [reader] DEPTH UCT-NODE (:DEPTH = 0)

- [accessor] EDGES UCT-NODE

    Outgoing edges.

- [accessor] AVERAGE-REWARD UCT-NODE (:AVERAGE-REWARD = 0)

    Average reward over random playouts started from
    below this node. See UPDATE-UCT-STATISTICS and REWARD.

- [class] UCT-EDGE

    An edge in the UCT tree. Represents an action taken
    from a state. The value of an action is the value of its target
    state which is not quite as generic as it could be; feel free to
    specialize AVERAGE-REWARD for the edges if that's not the case.

- [reader] ACTION UCT-EDGE (:ACTION)

    The action represented by the edge.

- [accessor] FROM-NODE UCT-EDGE (:FROM-NODE)

    The node this edge starts from.

- [accessor] TO-NODE UCT-EDGE (= NIL)

    The node this edge points to if the edge has been
    visited or NIL.

- [function] VISITED-EDGES NODE

- [function] UNVISITED-EDGES NODE

- [generic-function] EDGE-SCORE NODE EDGE EXPLORATION-BIAS

- [generic-function] SELECT-EDGE NODE EXPLORATION-BIAS

    Choose an action to take from a state, in other
    words an edge to follow from NODE in the tree. The default
    implementation chooses randomly from the yet unvisited edges or if
    there is none moves down the edge with the maximum EDGE-SCORE. If
    you are thinking of customizing this, for example to make it choose
    the minimum at odd depths, the you may want to consider specializing
    REWARD or UPDATE-UCT-STATISTICS instead.

- [generic-function] OUTCOME->REWARD NODE OUTCOME

    Compute the reward for a node in the tree from
    OUTCOME that is the result of a playout. This is called by the
    default implementation of UPDATE-UCT-STATISTICS. This is where one
    typically negates depending on the parity of DEPTH in two player
    games.

- [generic-function] UPDATE-UCT-STATISTICS ROOT PATH OUTCOME

    Increment the number of visits and update the
    average reward in nodes and edges of PATH. By default, edges simply
    get their visit counter incremented while nodes also get an update
    to AVERAGE-REWARD based on what OUTCOME->REWARD returns.

- [generic-function] MAKE-UCT-NODE PARENT EDGE PARENT-STATE

    Create a node representing the state of that EDGE
    leads to from PARENT. Specialize this if you want to keep track of
    the state which is not done by default as it can be expensive,
    especially in light of TAKE-ACTION mutating it. The default
    implementation simply creates an instance of the class of PARENT so
    that one can start from a subclass of UCT-NODE and be sure that that
    class is going to be used for nodes below it.

- [generic-function] STATE NODE PARENT EDGE PARENT-STATE

    Return the state that corresponds to NODE. This is
    not a straightforward accessor unless NODE is customized to store
    it. The rest of the parameters are provided so that one can
    reconstruct the state by taking the action of EDGE in the
    PARENT-STATE of PARENT. It's okay to destroy PARENT-STATE in the
    process as long as it's not stored elsewhere. This function must be
    customized.

- [generic-function] LIST-EDGES NODE STATE

    Return a list of edges representing the possible
    actions from NODE with STATE. This function must be customized.

- [generic-function] PLAY-OUT NODE STATE REVERSE-PATH

    Play a random game from NODE with STATE and return
    the outcome that's fed into UPDATE-UCT-STATISTICS. The way the
    random game is played is referred to as \`default policy' and that's
    what makes or breaks UCT search. This function must be
    customized.

- [function] UCT &KEY ROOT FRESH-ROOT-STATE EXPLORATION-BIAS MAX-N-PLAYOUTS

    Starting from the ROOT node search the tree expanding it one node
    for each playout. Finally return the mutated ROOT. ROOT may be the
    root node of any tree, need not be a single node with no edges.
    FRESH-ROOT-STATE is a function that returns a fresh state
    corresponding to ROOT. This state will be destroyed unless special
    care is taken in STATE.

## Metropolis Hastings

###### \[in package MICMAC.METROPOLIS-HASTINGS\]
Generic interface for the Metropolis-Hastings algorithm, also
Metropolis Coupled MCMC.

References:

- http://en.wikipedia.org/wiki/Metropolis–Hastings\_algorithm

- Markov Chain Monte Carlo and Gibbs Sampling
  Lecture Notes for EEB 581, version 26 April 2004 c B. Walsh 2004
  http://web.mit.edu/~wingated/www/introductions/mcmc-gibbs-intro.pdf

- Geyer, C.J. (1991) Markov chain Monte Carlo maximum likelihood

For now, the documentation is just a reference. See
`test/test-metropolis-hastings.lisp` for an example.

- [class] MC-CHAIN

    A simple markov chain for Metropolis Hastings. With
    temperature it is suitable for MC3.

- [accessor] TEMPERATURE MC-CHAIN (:TEMPERATURE = 1.0d0)

    The PROBABILITY-RATIO of samples is raised to the
    power of 1 / TEMPERATURE before calculating the acceptance
    probability. This effectively flattens the peaks if TEMPERATURE >
    1 which makes it easier for the chain to traverse deep valleys.

- [reader] STATE MC-CHAIN (:STATE)

    This is the current sample where the chain is.

- [function] JUMP-TO-SAMPLE CHAIN JUMP &KEY (RESULT-SAMPLE (STATE CHAIN))

    From the current state of CHAIN make JUMP (from the current
    distribution of CHAIN) and return the sample where we landed. Reuse
    RESULT-SAMPLE when possible. 

- [generic-function] JUMP-TO-SAMPLE* CHAIN JUMP RESULT-SAMPLE

    This function is called by JUMP-TO-SAMPLE. It is
    where JUMP-TO-SAMPLE behaviour shall be customized.

- [generic-function] PREPARE-JUMP-DISTRIBUTION CHAIN

    Prepare for sampling from the F(X) = Q(SAMPLE->X)
    distribution. Called by RANDOM-JUMP. The around method ensures that
    nothing is done unless there was a state change.

- [generic-function] RANDOM-JUMP CHAIN

    Sample a jump from the current distribution of
    jumps that was computed by PREPARE-JUMP-DISTRIBUTION.

- [generic-function] LOG-PROBABILITY-RATIO CHAIN SAMPLE1 SAMPLE2

    Return P(SAMPLE1)/P(SAMPLE2). It's in the log
    domain to avoid overflows and the ratio part is because that it may
    allow computational shortcuts as opposed to calculating unnormalized
    probabilities separately.

- [generic-function] LOG-PROBABILITY-RATIO-TO-JUMP-TARGET CHAIN JUMP TARGET

    Return P(TARGET)/P(STATE) where JUMP is from the
    current state of CHAIN to TARGET sample. This can be specialized for
    speed. The default implementation just falls back on
    LOG-PROBABILITY-RATIO.

- [generic-function] LOG-JUMP-PROBABILITY-RATIO CHAIN JUMP TARGET

    Return Q(TARGET->STATE) / Q(STATE->TARGET) where Q
    is the jump distribution and JUMP is from the current STATE of CHAIN
    to TARGET sample.

- [generic-function] ACCEPTANCE-PROBABILITY CHAIN JUMP CANDIDATE

    Calculate the acceptance probability of CANDIDATE
    to which JUMP leads from the current STATE of CHAIN.

- [generic-function] ACCEPT-JUMP CHAIN JUMP CANDIDATE

    Called when CHAIN accepts JUMP to CANDIDATE.

- [generic-function] REJECT-JUMP CHAIN JUMP CANDIDATE

    Called when CHAIN rejects JUMP to CANDIDATE. It
    does nothing by default, it's just a convenience for debugging.

- [generic-function] MAYBE-JUMP CHAIN JUMP CANDIDATE ACCEPTANCE-PROBABILITY

    Randomly accept or reject JUMP to CANDIDATE from
    the current state of CHAIN with ACCEPTANCE-PROBABILITY.

- [generic-function] JUMP CHAIN

    Take a step on the markov chain. Return a boolean
    indicating whether the proposed jump was accepted.

- [class] MC3-CHAIN MC-CHAIN

    High probability island separated by low valley
    make the chain poorly mixing. MC3-CHAIN has a number of HOT-CHAINS
    that have state probabilities similar to that of the main chain but
    less jagged. Often it suffices to set the temperatures of the
    HOT-CHAINS higher use the very same base probability
    distribution.

- [generic-function] ACCEPT-SWAP-CHAIN-STATES MC3 CHAIN1 CHAIN2

    Swap the states of CHAIN1 and CHAIN2 of MC3.

- [generic-function] REJECT-SWAP-CHAIN-STATES MC3 CHAIN1 CHAIN2

    Called when the swap of states of CHAIN1 and CHAIN2
    is rejected. It does nothing by default, it's just a convenience for
    debugging.

- [generic-function] MAYBE-SWAP-CHAIN-STATES MC3 CHAIN1 CHAIN2 ACCEPTANCE-PROBABILITY

    Swap of states of CHAIN1 and CHAIN2 of MC3 with
    ACCEPTANCE-PROBABILITY.

- [generic-function] JUMP-BETWEEN-CHAINS MC3

    Choose two chains randomly and swap their states
    with MC3 acceptance probability.

- [class] ENUMERATING-CHAIN MC-CHAIN

    A simple abstract chain subclass that explicitly
    enumerates the probabilities of the distribution.

- [class] TRACING-CHAIN

    Mix this in with your chain to have it print trace
    of acceptances/rejections.

## Game Theory

###### \[in package MICMAC.GAME-THEORY\]
- [function] FIND-NASH-EQUILIBRIUM PAYOFF &KEY (N-ITERATIONS 100)

    Find a Nash equilibrium of a zero-sum game represented by PAYOFF
    matrix (a 2d matrix or a nested list). PAYOFF is from the point of
    view of the row player: the player who choses column wants to
    minimize, the row player wants to maximize. The first value returned
    is a vector of unnormalized probabilities assigned to each action of
    the row player, the second value is the same for the column player
    and the third is the expected payoff of the row player in the nash
    equilibrium represented by the oddment vectors.

* * *
###### \[generated by [MGL-PAX](https://github.com/melisgl/mgl-pax)\]


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 micmac

Author

Gábor Melis

Contact

mega@retes.hu

Home Page

http://quotenil.com

License

MIT, see COPYING.

Description

Micmac is mainly a library of graph search algorithms
such as alpha-beta, UCT and beam search, but it also has some MCMC and other slightly unrelated stuff.

Version

0.0.2

Dependency

mgl-pax

Source

micmac.asd (file)

Component

src (module)


Next: , Previous: , Up: Top   [Contents][Index]

3 Modules

Modules are listed depth-first from the system components tree.


Previous: , Up: Modules   [Contents][Index]

3.1 micmac/src

Parent

micmac (system)

Location

src/

Components

Next: , Previous: , Up: Top   [Contents][Index]

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

4.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.1 micmac.asd

Location

micmac.asd

Systems

micmac (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.2 micmac/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.3 micmac/src/uct.lisp

Dependency

package.lisp (file)

Parent

src (module)

Location

src/uct.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.4 micmac/src/graph-search.lisp

Dependency

uct.lisp (file)

Parent

src (module)

Location

src/graph-search.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.5 micmac/src/metropolis-hastings.lisp

Dependency

graph-search.lisp (file)

Parent

src (module)

Location

src/metropolis-hastings.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

4.1.6 micmac/src/game-theory.lisp

Dependency

metropolis-hastings.lisp (file)

Parent

src (module)

Location

src/game-theory.lisp

Exported Definitions
Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

4.1.7 micmac/src/micmac.lisp

Dependency

game-theory.lisp (file)

Parent

src (module)

Location

src/micmac.lisp

Exported Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

5.1 micmac.game-theory

See MICMAC.GAME-THEORY:@MICMAC-GAME-THEORY.

Source

package.lisp (file)

Use List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Packages   [Contents][Index]

5.2 micmac.uct

See MICMAC.UCT:@MICMAC-UCT.

Source

package.lisp (file)

Use List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Packages   [Contents][Index]

5.3 micmac.metropolis-hastings

See MICMAC.METROPOLIS-HASTINGS:@MICMAC-METROPOLIS-HASTINGS.

Source

package.lisp (file)

Nickname

micmac.mh

Use List
Exported Definitions
Internal Definitions

Previous: , Up: Packages   [Contents][Index]

5.4 micmac

See MICMAC:@MICMAC-MANUAL.

Source

package.lisp (file)

Use List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

6.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.1 Special variables

Special Variable: @micmac-game-theory
Package

micmac.game-theory

Source

game-theory.lisp (file)

Special Variable: @micmac-graph-search
Package

micmac

Source

graph-search.lisp (file)

Special Variable: @micmac-introduction
Package

micmac

Source

micmac.lisp (file)

Special Variable: @micmac-links
Package

micmac

Source

micmac.lisp (file)

Special Variable: @micmac-manual
Package

micmac

Source

micmac.lisp (file)

Special Variable: @micmac-metropolis-hastings
Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Special Variable: @micmac-overview
Package

micmac

Source

micmac.lisp (file)

Special Variable: @micmac-uct
Package

micmac.uct

Source

uct.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.2 Functions

Function: alpha-beta STATE &key DEPTH ALPHA BETA CALL-WITH-ACTION MAYBE-EVALUATE-STATE LIST-ACTIONS RECORD-BEST

Alpha-beta pruning for two player, zero-sum maximax (like minimax but both players maximize and the score is negated when passed between depths). Return the score of the game STATE from the point of view of the player to move at DEPTH and as the second value the list of actions of the principal variant.

CALL-WITH-ACTION is a function of (STATE DEPTH ACTION FN). It carries out ACTION (returned by LIST-ACTIONS or NIL) to get the state corresponding to DEPTH and calls FN with that state. It may destructively modify STATE provided it undoes the damage after FN returns. CALL-WITH-ACTION is called with NIL as ACTION for the root of the tree, in this case STATE need not be changed. FN returns the same kinds of values as ALPHA-BETA. They may be useful for logging.

MAYBE-EVALUATE-STATE is a function of (STATE DEPTH). If STATE at DEPTH is a terminal node then it returns the score from the point of view of the player to move and as the second value a list of actions that lead from STATE to the position that was evaluated. The list of actions is typically empty. If we are not at a terminal node then MAYBE-EVALUATE-STATE returns NIL.

LIST-ACTIONS is a function of (STATE DEPTH) and returns a non-empty list of legal candidate moves for non-terminal nodes. Actions are tried in the order LIST-ACTIONS returns them: stronger moves

CALL-WITH-ACTION, MAYBE-EVALUATE-STATE and LIST-ACTIONS are mandatory.

RECORD-BEST, if non-NIL, is a function of (DEPTH SCORE ACTIONS). It is called when at DEPTH a new best action is found. ACTIONS is a list of all the actions in the principle variant corresonding to the newly found best score. RECORD-BEST is useful for graceful degradation in case of timeout.

ALPHA and BETA are typically NIL (equivalent to -infinity, +infinity) but any real number is allowed if the range of scores can be boxed.

See ‘test/test-alpha-beta.lisp‘ for an example.

Package

micmac

Source

graph-search.lisp (file)

Function: beam-search START-NODES &key MAX-DEPTH N-SOLUTIONS BEAM-WIDTH EXPAND-NODE-FN EXPAND-BEAM-FN SCORE-FN UPPER-BOUND-FN SOLUTIONP-FN FINISHEDP-FN

In a graph, search for nodes that with the best scores with [beam search](http://en.wikipedia.org/wiki/Beam_search). That is, starting from START-NODES perform a breadth-first search but at each depth only keep BEAM-WIDTH number of nodes with the best scores. Keep the best N-SOLUTIONS (at most) complete solutions. Discard nodes known to be unable to get into the best N-SOLUTIONS (due to UPPER-BOUND-FN). Finally, return the solutions and the active nodes (the _beam_) as adjustable arrays sorted by score in descending order.

START-NODES (a sequence of elements of arbitrary type). SCORE-FN, UPPER-BOUND-FN, SOLUTIONP-FN, FINISHEDP-FN are all functions of one argument: the node. SOLUTIONP-FN checks whether a node represents a complete solution (i.e. some goal is reached). SCORE-FN returns a real number that’s to be maximized, it’s only called for node for which SOLUTIONP-FN returned true. UPPER-BOUND-FN (if not NIL) returns a real number that equal or greater than the score of all solutions reachable from that node. FINISHEDP-FN returns true iff there is nowhere to go from the node.

EXPAND-NODE-FN is also a function of a single node argument. It returns a sequence of nodes to ’one step away’ from its argument node. EXPAND-BEAM-FN is similar, but it takes a vector of nodes and returns all nodes one step away from any of them. It’s enough provide either EXPAND-NODE-FN or EXPAND-BEAM-FN. The purpose of EXPAND-BEAM-FN. is to allow more efficient, batch-like operations.

See ‘test/test-beam-search.lisp‘ for an example.

Package

micmac

Source

graph-search.lisp (file)

Function: find-nash-equilibrium PAYOFF &key N-ITERATIONS

Find a Nash equilibrium of a zero-sum game represented by PAYOFF matrix (a 2d matrix or a nested list). PAYOFF is from the point of view of the row player: the player who choses column wants to minimize, the row player wants to maximize. The first value returned is a vector of unnormalized probabilities assigned to each action of the row player, the second value is the same for the column player and the third is the expected payoff of the row player in the nash equilibrium represented by the oddment vectors.

Package

micmac.game-theory

Source

game-theory.lisp (file)

Function: jump-to-sample CHAIN JUMP &key RESULT-SAMPLE

From the current state of CHAIN make JUMP (from the current distribution of CHAIN) and return the sample where we landed. Reuse RESULT-SAMPLE when possible.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Function: parallel-beam-search START-NODE-SEQS &key MAX-DEPTH N-SOLUTIONS BEAM-WIDTH EXPAND-NODE-FN EXPAND-BEAMS-FN SCORE-FN UPPER-BOUND-FN SOLUTIONP-FN FINISHEDP-FN

This is very much like BEAM-SEARCH except it solves a number of instances of the same search problem starting from different sets of nodes. The sole purpose of PARALLEL-BEAM-SEARCH is to amortize the cost EXPAND-BEAM-FN if possible.

EXPAND-BEAMS-FN is called with sequence of beams (i.e. it’s a sequence of sequence of nodes) and it must return another sequence of sequences of nodes. Each element of the returned sequence is the reachable nodes of the nodes in the corresponding element of its argument sequence.

PARALLEL-BEAM-SEARCH returns a sequence of solutions sequences, and a sequence of active node sequences.

See ‘test/test-beam-search.lisp‘ for an example.

Package

micmac

Source

graph-search.lisp (file)

Function: uct &key ROOT FRESH-ROOT-STATE EXPLORATION-BIAS MAX-N-PLAYOUTS

Starting from the ROOT node search the tree expanding it one node for each playout. Finally return the mutated ROOT. ROOT may be the root node of any tree, need not be a single node with no edges. FRESH-ROOT-STATE is a function that returns a fresh state corresponding to ROOT. This state will be destroyed unless special care is taken in STATE.

Package

micmac.uct

Source

uct.lisp (file)

Function: unvisited-edges NODE
Package

micmac.uct

Source

uct.lisp (file)

Function: visited-edges NODE
Package

micmac.uct

Source

uct.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

6.1.3 Generic functions

Generic Function: accept-jump CHAIN JUMP CANDIDATE

Called when CHAIN accepts JUMP to CANDIDATE.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: accept-jump (CHAIN tracing-chain) JUMP CANDIDATE
Method: accept-jump CHAIN JUMP CANDIDATE
Generic Function: accept-swap-chain-states MC3 CHAIN1 CHAIN2

Swap the states of CHAIN1 and CHAIN2 of MC3.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: accept-swap-chain-states (CHAIN tracing-chain) CHAIN1 CHAIN2
Method: accept-swap-chain-states MC3 CHAIN1 CHAIN2
Generic Function: acceptance-probability CHAIN JUMP CANDIDATE

Calculate the acceptance probability of CANDIDATE to which JUMP leads from the current STATE of CHAIN.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: acceptance-probability CHAIN JUMP CANDIDATE
Generic Function: action OBJECT
Package

micmac.uct

Methods
Method: action (UCT-EDGE uct-edge)

The action represented by the edge.

Source

uct.lisp (file)

Generic Function: average-reward OBJECT
Generic Function: (setf average-reward) NEW-VALUE OBJECT
Package

micmac.uct

Methods
Method: average-reward (EDGE uct-edge)
Source

uct.lisp (file)

Method: average-reward (UCT-NODE uct-node)
Method: (setf average-reward) NEW-VALUE (UCT-NODE uct-node)

Average reward over random playouts started from
below this node. See UPDATE-UCT-STATISTICS and REWARD.

Source

uct.lisp (file)

Generic Function: depth OBJECT
Package

micmac.uct

Methods
Method: depth (UCT-NODE uct-node)

automatically generated reader method

Source

uct.lisp (file)

Generic Function: edge-score NODE EDGE EXPLORATION-BIAS
Package

micmac.uct

Source

uct.lisp (file)

Methods
Method: edge-score (NODE uct-node) EDGE EXPLORATION-BIAS
Generic Function: edges OBJECT
Generic Function: (setf edges) NEW-VALUE OBJECT
Package

micmac.uct

Methods
Method: edges (UCT-NODE uct-node)
Method: (setf edges) NEW-VALUE (UCT-NODE uct-node)

Outgoing edges.

Source

uct.lisp (file)

Generic Function: from-node OBJECT
Generic Function: (setf from-node) NEW-VALUE OBJECT
Package

micmac.uct

Methods
Method: from-node (UCT-EDGE uct-edge)
Method: (setf from-node) NEW-VALUE (UCT-EDGE uct-edge)

The node this edge starts from.

Source

uct.lisp (file)

Generic Function: jump CHAIN

Take a step on the markov chain. Return a boolean indicating whether the proposed jump was accepted.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: jump (CHAIN mc3-chain)
Method: jump CHAIN
Generic Function: jump-between-chains MC3

Choose two chains randomly and swap their states with MC3 acceptance probability.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: jump-between-chains MC3
Generic Function: jump-to-sample* CHAIN JUMP RESULT-SAMPLE

This function is called by JUMP-TO-SAMPLE. It is where JUMP-TO-SAMPLE behaviour shall be customized.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Generic Function: list-edges NODE STATE

Return a list of edges representing the possible
actions from NODE with STATE. This function must be customized.

Package

micmac.uct

Source

uct.lisp (file)

Generic Function: log-jump-probability-ratio CHAIN JUMP TARGET

Return Q(TARGET->STATE) / Q(STATE->TARGET) where Q
is the jump distribution and JUMP is from the current STATE of CHAIN to TARGET sample.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Generic Function: log-probability-ratio CHAIN SAMPLE1 SAMPLE2

Return P(SAMPLE1)/P(SAMPLE2). It’s in the log
domain to avoid overflows and the ratio part is because that it may allow computational shortcuts as opposed to calculating unnormalized probabilities separately.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Generic Function: log-probability-ratio-to-jump-target CHAIN JUMP TARGET

Return P(TARGET)/P(STATE) where JUMP is from the
current state of CHAIN to TARGET sample. This can be specialized for speed. The default implementation just falls back on LOG-PROBABILITY-RATIO.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: log-probability-ratio-to-jump-target CHAIN JUMP TARGET
Generic Function: make-uct-node PARENT EDGE PARENT-STATE

Create a node representing the state of that EDGE
leads to from PARENT. Specialize this if you want to keep track of the state which is not done by default as it can be expensive, especially in light of TAKE-ACTION mutating it. The default implementation simply creates an instance of the class of PARENT so that one can start from a subclass of UCT-NODE and be sure that that class is going to be used for nodes below it.

Package

micmac.uct

Source

uct.lisp (file)

Methods
Method: make-uct-node (PARENT uct-node) EDGE STATE
Generic Function: maybe-jump CHAIN JUMP CANDIDATE ACCEPTANCE-PROBABILITY

Randomly accept or reject JUMP to CANDIDATE from
the current state of CHAIN with ACCEPTANCE-PROBABILITY.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: maybe-jump (CHAIN tracing-chain) JUMP CANDIDATE ACCEPTANCE-PROBABILITY
Method: maybe-jump CHAIN JUMP CANDIDATE ACCEPTANCE-PROBABILITY
Generic Function: maybe-swap-chain-states MC3 CHAIN1 CHAIN2 ACCEPTANCE-PROBABILITY

Swap of states of CHAIN1 and CHAIN2 of MC3 with ACCEPTANCE-PROBABILITY.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: maybe-swap-chain-states (CHAIN tracing-chain) CHAIN1 CHAIN2 ACCEPTANCE-PROBABILITY
Method: maybe-swap-chain-states MC3 CHAIN1 CHAIN2 ACCEPTANCE-PROBABILITY
Generic Function: outcome->reward NODE OUTCOME

Compute the reward for a node in the tree from
OUTCOME that is the result of a playout. This is called by the default implementation of UPDATE-UCT-STATISTICS. This is where one typically negates depending on the parity of DEPTH in two player games.

Package

micmac.uct

Source

uct.lisp (file)

Methods
Method: outcome->reward (NODE uct-node) OUTCOME
Generic Function: play-out NODE STATE REVERSE-PATH

Play a random game from NODE with STATE and return
the outcome that’s fed into UPDATE-UCT-STATISTICS. The way the random game is played is referred to as ‘default policy’ and that’s what makes or breaks UCT search. This function must be customized.

Package

micmac.uct

Source

uct.lisp (file)

Generic Function: prepare-jump-distribution CHAIN

Prepare for sampling from the F(X) = Q(SAMPLE->X)
distribution. Called by RANDOM-JUMP. The around method ensures that nothing is done unless there was a state change.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: prepare-jump-distribution CHAIN around
Generic Function: random-jump CHAIN

Sample a jump from the current distribution of jumps that was computed by PREPARE-JUMP-DISTRIBUTION.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: random-jump (CHAIN enumerating-chain)
Method: random-jump CHAIN before
Generic Function: reject-jump CHAIN JUMP CANDIDATE

Called when CHAIN rejects JUMP to CANDIDATE. It
does nothing by default, it’s just a convenience for debugging.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: reject-jump (CHAIN tracing-chain) JUMP CANDIDATE
Method: reject-jump CHAIN JUMP CANDIDATE
Generic Function: reject-swap-chain-states MC3 CHAIN1 CHAIN2

Called when the swap of states of CHAIN1 and CHAIN2
is rejected. It does nothing by default, it’s just a convenience for debugging.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: reject-swap-chain-states (CHAIN tracing-chain) CHAIN1 CHAIN2
Method: reject-swap-chain-states MC3 CHAIN1 CHAIN2
Generic Function: select-edge NODE EXPLORATION-BIAS

Choose an action to take from a state, in other
words an edge to follow from NODE in the tree. The default implementation chooses randomly from the yet unvisited edges or if there is none moves down the edge with the maximum EDGE-SCORE. If you are thinking of customizing this, for example to make it choose the minimum at odd depths, the you may want to consider specializing REWARD or UPDATE-UCT-STATISTICS instead.

Package

micmac.uct

Source

uct.lisp (file)

Methods
Method: select-edge (NODE uct-node) EXPLORATION-BIAS
Generic Function: state NODE PARENT EDGE PARENT-STATE

Return the state that corresponds to NODE. This is
not a straightforward accessor unless NODE is customized to store it. The rest of the parameters are provided so that one can reconstruct the state by taking the action of EDGE in the PARENT-STATE of PARENT. It’s okay to destroy PARENT-STATE in the process as long as it’s not stored elsewhere. This function must be customized.

Package

micmac.uct

Source

uct.lisp (file)

Generic Function: state OBJECT
Package

micmac.metropolis-hastings

Setf Expander

(setf state) (setf expander)

Methods
Method: state (MC-CHAIN mc-chain)

This is the current sample where the chain is.

Source

metropolis-hastings.lisp (file)

Setf Expander: (setf state) OBJECT
Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Reader

state (generic function)

Generic Function: temperature OBJECT
Generic Function: (setf temperature) NEW-VALUE OBJECT
Package

micmac.metropolis-hastings

Methods
Method: temperature (MC-CHAIN mc-chain)
Method: (setf temperature) NEW-VALUE (MC-CHAIN mc-chain)

The PROBABILITY-RATIO of samples is raised to the
power of 1 / TEMPERATURE before calculating the acceptance probability. This effectively flattens the peaks if TEMPERATURE > 1 which makes it easier for the chain to traverse deep valleys.

Source

metropolis-hastings.lisp (file)

Generic Function: to-node OBJECT
Generic Function: (setf to-node) NEW-VALUE OBJECT
Package

micmac.uct

Methods
Method: to-node (UCT-EDGE uct-edge)
Method: (setf to-node) NEW-VALUE (UCT-EDGE uct-edge)

The node this edge points to if the edge has been visited or NIL.

Source

uct.lisp (file)

Generic Function: update-uct-statistics ROOT PATH OUTCOME

Increment the number of visits and update the
average reward in nodes and edges of PATH. By default, edges simply get their visit counter incremented while nodes also get an update to AVERAGE-REWARD based on what OUTCOME->REWARD returns.

Package

micmac.uct

Source

uct.lisp (file)

Methods
Method: update-uct-statistics (NODE uct-node) PATH OUTCOME

Previous: , Up: Exported definitions   [Contents][Index]

6.1.4 Classes

Class: enumerating-chain ()

A simple abstract chain subclass that explicitly enumerates the probabilities of the distribution.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Direct superclasses

mc-chain (class)

Direct methods
Direct slots
Slot: p-jumps
Readers

p-jumps (generic function)

Class: mc-chain ()

A simple markov chain for Metropolis Hastings. With temperature it is suitable for MC3.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses
Direct methods
Direct slots
Slot: temperature

The PROBABILITY-RATIO of samples is raised to the
power of 1 / TEMPERATURE before calculating the acceptance probability. This effectively flattens the peaks if TEMPERATURE > 1 which makes it easier for the chain to traverse deep valleys.

Initargs

:temperature

Initform

1.0d0

Readers

temperature (generic function)

Writers

(setf temperature) (generic function)

Slot: state

This is the current sample where the chain is.

Initargs

:state

Readers

state (generic function)

Slot: candidate
Readers

candidate (generic function)

Writers

(setf candidate) (generic function)

Slot: jump-distribution-prepared-p
Readers

jump-distribution-prepared-p (generic function)

Writers

(setf jump-distribution-prepared-p) (generic function)

Class: mc3-chain ()

High probability island separated by low valley
make the chain poorly mixing. MC3-CHAIN has a number of HOT-CHAINS that have state probabilities similar to that of the main chain but less jagged. Often it suffices to set the temperatures of the HOT-CHAINS higher use the very same base probability distribution.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Direct superclasses

mc-chain (class)

Direct methods
Direct slots
Slot: hot-chains
Type

list

Initargs

:hot-chains

Readers

hot-chains (generic function)

Class: tracing-chain ()

Mix this in with your chain to have it print trace of acceptances/rejections.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Class: uct-edge ()

An edge in the UCT tree. Represents an action taken
from a state. The value of an action is the value of its target state which is not quite as generic as it could be; feel free to specialize AVERAGE-REWARD for the edges if that’s not the case.

Package

micmac.uct

Source

uct.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: action

The action represented by the edge.

Initargs

:action

Readers

action (generic function)

Slot: from-node

The node this edge starts from.

Initargs

:from-node

Readers

from-node (generic function)

Writers

(setf from-node) (generic function)

Slot: to-node

The node this edge points to if the edge has been visited or NIL.

Readers

to-node (generic function)

Writers

(setf to-node) (generic function)

Slot: n-visits

The number of times this action was taken from the parent state.

Initform

0

Readers

n-visits (generic function)

Writers

(setf n-visits) (generic function)

Class: uct-node ()

A node in the UCT tree. Roughly translates to a
state in the search space. Note that the state itself is not stored explicity, but it can be recovered by ‘replaying’ the actions from the starting state or by customizing MAKE-UCT-NODE.

Package

micmac.uct

Source

uct.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: depth
Initargs

:depth

Initform

0

Readers

depth (generic function)

Slot: n-visits

The number of times this node was visited.

Initform

0

Readers

n-visits (generic function)

Writers

(setf n-visits) (generic function)

Slot: edges

Outgoing edges.

Readers

edges (generic function)

Writers

(setf edges) (generic function)

Slot: average-reward

Average reward over random playouts started from
below this node. See UPDATE-UCT-STATISTICS and REWARD.

Initargs

:average-reward

Initform

0

Readers

average-reward (generic function)

Writers

(setf average-reward) (generic function)


Previous: , Up: Definitions   [Contents][Index]

6.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.1 Macros

Macro: apply-key KEY OBJECT
Package

micmac

Source

graph-search.lisp (file)

Macro: dup N MAKER
Package

micmac

Source

graph-search.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

6.2.2 Functions

Function: extremum VECTOR PRED &key START END

Find the first extreme value of the [START,END) subsequence of VECTOR and return it along with its index. The extremum is what would be the first element of VECTOR sorted by SORT with PRED.

Package

micmac.game-theory

Source

game-theory.lisp (file)

Function: extremum SEQ PRED &key KEY
Package

micmac.uct

Source

uct.lisp (file)

Function: insert-into-sorted-vector ITEM VECTOR PRED &key KEY MAX-LENGTH

Insert ITEM into VECTOR while keeping it sorted by PRED. Extend the vector if needed while respecting MAX-LENGTH.

Package

micmac

Source

graph-search.lisp (file)

Function: list-to-2d-matrix LIST
Package

micmac.game-theory

Source

game-theory.lisp (file)

Function: log->acceptance-probability X
Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Function: random-element SEQ
Package

micmac.uct

Source

uct.lisp (file)

Function: random-element SEQ &key KEY START END SUM

Choose an element randomly from the [START,END) subsequence of SEQ with given probabilities. KEY returns the unormalized probability of an element, SUM is the sum of these unnormalized probalities contains unnormalized probabilties. Return the element chosen and its index.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Function: random-until-different LIMIT TABU &key TEST
Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Function: sum-seq SEQ &key KEY START END

Return the sum of elements in the [START,END) subsequence of SEQ.

Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

6.2.3 Generic functions

Generic Function: candidate OBJECT
Generic Function: (setf candidate) NEW-VALUE OBJECT
Package

micmac.metropolis-hastings

Methods
Method: candidate (MC-CHAIN mc-chain)

automatically generated reader method

Source

metropolis-hastings.lisp (file)

Method: (setf candidate) NEW-VALUE (MC-CHAIN mc-chain)

automatically generated writer method

Source

metropolis-hastings.lisp (file)

Generic Function: hot-chains OBJECT
Package

micmac.metropolis-hastings

Methods
Method: hot-chains (MC3-CHAIN mc3-chain)

automatically generated reader method

Source

metropolis-hastings.lisp (file)

Generic Function: jump-distribution-prepared-p OBJECT
Generic Function: (setf jump-distribution-prepared-p) NEW-VALUE OBJECT
Package

micmac.metropolis-hastings

Methods
Method: jump-distribution-prepared-p (MC-CHAIN mc-chain)

automatically generated reader method

Source

metropolis-hastings.lisp (file)

Method: (setf jump-distribution-prepared-p) NEW-VALUE (MC-CHAIN mc-chain)

automatically generated writer method

Source

metropolis-hastings.lisp (file)

Generic Function: n-visits OBJECT
Generic Function: (setf n-visits) NEW-VALUE OBJECT
Package

micmac.uct

Methods
Method: n-visits (UCT-EDGE uct-edge)
Method: (setf n-visits) NEW-VALUE (UCT-EDGE uct-edge)

The number of times this action was taken from the parent state.

Source

uct.lisp (file)

Method: n-visits (UCT-NODE uct-node)
Method: (setf n-visits) NEW-VALUE (UCT-NODE uct-node)

The number of times this node was visited.

Source

uct.lisp (file)

Generic Function: p-jumps OBJECT
Package

micmac.metropolis-hastings

Methods
Method: p-jumps (ENUMERATING-CHAIN enumerating-chain)

automatically generated reader method

Source

metropolis-hastings.lisp (file)

Generic Function: set-state STATE CHAIN
Package

micmac.metropolis-hastings

Source

metropolis-hastings.lisp (file)

Methods
Method: set-state STATE CHAIN

Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   M  
Index Entry  Section

F
File, Lisp, micmac.asd: The micmac<dot>asd file
File, Lisp, micmac/src/game-theory.lisp: The micmac/src/game-theory<dot>lisp file
File, Lisp, micmac/src/graph-search.lisp: The micmac/src/graph-search<dot>lisp file
File, Lisp, micmac/src/metropolis-hastings.lisp: The micmac/src/metropolis-hastings<dot>lisp file
File, Lisp, micmac/src/micmac.lisp: The micmac/src/micmac<dot>lisp file
File, Lisp, micmac/src/package.lisp: The micmac/src/package<dot>lisp file
File, Lisp, micmac/src/uct.lisp: The micmac/src/uct<dot>lisp file

L
Lisp File, micmac.asd: The micmac<dot>asd file
Lisp File, micmac/src/game-theory.lisp: The micmac/src/game-theory<dot>lisp file
Lisp File, micmac/src/graph-search.lisp: The micmac/src/graph-search<dot>lisp file
Lisp File, micmac/src/metropolis-hastings.lisp: The micmac/src/metropolis-hastings<dot>lisp file
Lisp File, micmac/src/micmac.lisp: The micmac/src/micmac<dot>lisp file
Lisp File, micmac/src/package.lisp: The micmac/src/package<dot>lisp file
Lisp File, micmac/src/uct.lisp: The micmac/src/uct<dot>lisp file

M
micmac.asd: The micmac<dot>asd file
micmac/src: The micmac/src module
micmac/src/game-theory.lisp: The micmac/src/game-theory<dot>lisp file
micmac/src/graph-search.lisp: The micmac/src/graph-search<dot>lisp file
micmac/src/metropolis-hastings.lisp: The micmac/src/metropolis-hastings<dot>lisp file
micmac/src/micmac.lisp: The micmac/src/micmac<dot>lisp file
micmac/src/package.lisp: The micmac/src/package<dot>lisp file
micmac/src/uct.lisp: The micmac/src/uct<dot>lisp file
Module, micmac/src: The micmac/src module

Jump to:   F   L   M  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
A   B   C   D   E   F   G   H   I   J   L   M   N   O   P   R   S   T   U   V  
Index Entry  Section

(
(setf average-reward): Exported generic functions
(setf average-reward): Exported generic functions
(setf candidate): Internal generic functions
(setf candidate): Internal generic functions
(setf edges): Exported generic functions
(setf edges): Exported generic functions
(setf from-node): Exported generic functions
(setf from-node): Exported generic functions
(setf jump-distribution-prepared-p): Internal generic functions
(setf jump-distribution-prepared-p): Internal generic functions
(setf n-visits): Internal generic functions
(setf n-visits): Internal generic functions
(setf n-visits): Internal generic functions
(setf state): Exported generic functions
(setf temperature): Exported generic functions
(setf temperature): Exported generic functions
(setf to-node): Exported generic functions
(setf to-node): Exported generic functions

A
accept-jump: Exported generic functions
accept-jump: Exported generic functions
accept-jump: Exported generic functions
accept-swap-chain-states: Exported generic functions
accept-swap-chain-states: Exported generic functions
accept-swap-chain-states: Exported generic functions
acceptance-probability: Exported generic functions
acceptance-probability: Exported generic functions
action: Exported generic functions
action: Exported generic functions
alpha-beta: Exported functions
apply-key: Internal macros
average-reward: Exported generic functions
average-reward: Exported generic functions
average-reward: Exported generic functions

B
beam-search: Exported functions

C
candidate: Internal generic functions
candidate: Internal generic functions

D
depth: Exported generic functions
depth: Exported generic functions
dup: Internal macros

E
edge-score: Exported generic functions
edge-score: Exported generic functions
edges: Exported generic functions
edges: Exported generic functions
extremum: Internal functions
extremum: Internal functions

F
find-nash-equilibrium: Exported functions
from-node: Exported generic functions
from-node: Exported generic functions
Function, alpha-beta: Exported functions
Function, beam-search: Exported functions
Function, extremum: Internal functions
Function, extremum: Internal functions
Function, find-nash-equilibrium: Exported functions
Function, insert-into-sorted-vector: Internal functions
Function, jump-to-sample: Exported functions
Function, list-to-2d-matrix: Internal functions
Function, log->acceptance-probability: Internal functions
Function, parallel-beam-search: Exported functions
Function, random-element: Internal functions
Function, random-element: Internal functions
Function, random-until-different: Internal functions
Function, sum-seq: Internal functions
Function, uct: Exported functions
Function, unvisited-edges: Exported functions
Function, visited-edges: Exported functions

G
Generic Function, (setf average-reward): Exported generic functions
Generic Function, (setf candidate): Internal generic functions
Generic Function, (setf edges): Exported generic functions
Generic Function, (setf from-node): Exported generic functions
Generic Function, (setf jump-distribution-prepared-p): Internal generic functions
Generic Function, (setf n-visits): Internal generic functions
Generic Function, (setf temperature): Exported generic functions
Generic Function, (setf to-node): Exported generic functions
Generic Function, accept-jump: Exported generic functions
Generic Function, accept-swap-chain-states: Exported generic functions
Generic Function, acceptance-probability: Exported generic functions
Generic Function, action: Exported generic functions
Generic Function, average-reward: Exported generic functions
Generic Function, candidate: Internal generic functions
Generic Function, depth: Exported generic functions
Generic Function, edge-score: Exported generic functions
Generic Function, edges: Exported generic functions
Generic Function, from-node: Exported generic functions
Generic Function, hot-chains: Internal generic functions
Generic Function, jump: Exported generic functions
Generic Function, jump-between-chains: Exported generic functions
Generic Function, jump-distribution-prepared-p: Internal generic functions
Generic Function, jump-to-sample*: Exported generic functions
Generic Function, list-edges: Exported generic functions
Generic Function, log-jump-probability-ratio: Exported generic functions
Generic Function, log-probability-ratio: Exported generic functions
Generic Function, log-probability-ratio-to-jump-target: Exported generic functions
Generic Function, make-uct-node: Exported generic functions
Generic Function, maybe-jump: Exported generic functions
Generic Function, maybe-swap-chain-states: Exported generic functions
Generic Function, n-visits: Internal generic functions
Generic Function, outcome->reward: Exported generic functions
Generic Function, p-jumps: Internal generic functions
Generic Function, play-out: Exported generic functions
Generic Function, prepare-jump-distribution: Exported generic functions
Generic Function, random-jump: Exported generic functions
Generic Function, reject-jump: Exported generic functions
Generic Function, reject-swap-chain-states: Exported generic functions
Generic Function, select-edge: Exported generic functions
Generic Function, set-state: Internal generic functions
Generic Function, state: Exported generic functions
Generic Function, state: Exported generic functions
Generic Function, temperature: Exported generic functions
Generic Function, to-node: Exported generic functions
Generic Function, update-uct-statistics: Exported generic functions

H
hot-chains: Internal generic functions
hot-chains: Internal generic functions

I
insert-into-sorted-vector: Internal functions

J
jump: Exported generic functions
jump: Exported generic functions
jump: Exported generic functions
jump-between-chains: Exported generic functions
jump-between-chains: Exported generic functions
jump-distribution-prepared-p: Internal generic functions
jump-distribution-prepared-p: Internal generic functions
jump-to-sample: Exported functions
jump-to-sample*: Exported generic functions

L
list-edges: Exported generic functions
list-to-2d-matrix: Internal functions
log->acceptance-probability: Internal functions
log-jump-probability-ratio: Exported generic functions
log-probability-ratio: Exported generic functions
log-probability-ratio-to-jump-target: Exported generic functions
log-probability-ratio-to-jump-target: Exported generic functions

M
Macro, apply-key: Internal macros
Macro, dup: Internal macros
make-uct-node: Exported generic functions
make-uct-node: Exported generic functions
maybe-jump: Exported generic functions
maybe-jump: Exported generic functions
maybe-jump: Exported generic functions
maybe-swap-chain-states: Exported generic functions
maybe-swap-chain-states: Exported generic functions
maybe-swap-chain-states: Exported generic functions
Method, (setf average-reward): Exported generic functions
Method, (setf candidate): Internal generic functions
Method, (setf edges): Exported generic functions
Method, (setf from-node): Exported generic functions
Method, (setf jump-distribution-prepared-p): Internal generic functions
Method, (setf n-visits): Internal generic functions
Method, (setf n-visits): Internal generic functions
Method, (setf temperature): Exported generic functions
Method, (setf to-node): Exported generic functions
Method, accept-jump: Exported generic functions
Method, accept-jump: Exported generic functions
Method, accept-swap-chain-states: Exported generic functions
Method, accept-swap-chain-states: Exported generic functions
Method, acceptance-probability: Exported generic functions
Method, action: Exported generic functions
Method, average-reward: Exported generic functions
Method, average-reward: Exported generic functions
Method, candidate: Internal generic functions
Method, depth: Exported generic functions
Method, edge-score: Exported generic functions
Method, edges: Exported generic functions
Method, from-node: Exported generic functions
Method, hot-chains: Internal generic functions
Method, jump: Exported generic functions
Method, jump: Exported generic functions
Method, jump-between-chains: Exported generic functions
Method, jump-distribution-prepared-p: Internal generic functions
Method, log-probability-ratio-to-jump-target: Exported generic functions
Method, make-uct-node: Exported generic functions
Method, maybe-jump: Exported generic functions
Method, maybe-jump: Exported generic functions
Method, maybe-swap-chain-states: Exported generic functions
Method, maybe-swap-chain-states: Exported generic functions
Method, n-visits: Internal generic functions
Method, n-visits: Internal generic functions
Method, outcome->reward: Exported generic functions
Method, p-jumps: Internal generic functions
Method, prepare-jump-distribution: Exported generic functions
Method, random-jump: Exported generic functions
Method, random-jump: Exported generic functions
Method, reject-jump: Exported generic functions
Method, reject-jump: Exported generic functions
Method, reject-swap-chain-states: Exported generic functions
Method, reject-swap-chain-states: Exported generic functions
Method, select-edge: Exported generic functions
Method, set-state: Internal generic functions
Method, state: Exported generic functions
Method, temperature: Exported generic functions
Method, to-node: Exported generic functions
Method, update-uct-statistics: Exported generic functions

N
n-visits: Internal generic functions
n-visits: Internal generic functions
n-visits: Internal generic functions

O
outcome->reward: Exported generic functions
outcome->reward: Exported generic functions

P
p-jumps: Internal generic functions
p-jumps: Internal generic functions
parallel-beam-search: Exported functions
play-out: Exported generic functions
prepare-jump-distribution: Exported generic functions
prepare-jump-distribution: Exported generic functions

R
random-element: Internal functions
random-element: Internal functions
random-jump: Exported generic functions
random-jump: Exported generic functions
random-jump: Exported generic functions
random-until-different: Internal functions
reject-jump: Exported generic functions
reject-jump: Exported generic functions
reject-jump: Exported generic functions
reject-swap-chain-states: Exported generic functions
reject-swap-chain-states: Exported generic functions
reject-swap-chain-states: Exported generic functions

S
select-edge: Exported generic functions
select-edge: Exported generic functions
set-state: Internal generic functions
set-state: Internal generic functions
Setf Expander, (setf state): Exported generic functions
state: Exported generic functions
state: Exported generic functions
state: Exported generic functions
sum-seq: Internal functions

T
temperature: Exported generic functions
temperature: Exported generic functions
to-node: Exported generic functions
to-node: Exported generic functions

U
uct: Exported functions
unvisited-edges: Exported functions
update-uct-statistics: Exported generic functions
update-uct-statistics: Exported generic functions

V
visited-edges: Exported functions

Jump to:   (  
A   B   C   D   E   F   G   H   I   J   L   M   N   O   P   R   S   T   U   V  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   @  
A   C   D   E   F   H   J   N   P   S   T  
Index Entry  Section

@
@micmac-game-theory: Exported special variables
@micmac-graph-search: Exported special variables
@micmac-introduction: Exported special variables
@micmac-links: Exported special variables
@micmac-manual: Exported special variables
@micmac-metropolis-hastings: Exported special variables
@micmac-overview: Exported special variables
@micmac-uct: Exported special variables

A
action: Exported classes
average-reward: Exported classes

C
candidate: Exported classes

D
depth: Exported classes

E
edges: Exported classes

F
from-node: Exported classes

H
hot-chains: Exported classes

J
jump-distribution-prepared-p: Exported classes

N
n-visits: Exported classes
n-visits: Exported classes

P
p-jumps: Exported classes

S
Slot, action: Exported classes
Slot, average-reward: Exported classes
Slot, candidate: Exported classes
Slot, depth: Exported classes
Slot, edges: Exported classes
Slot, from-node: Exported classes
Slot, hot-chains: Exported classes
Slot, jump-distribution-prepared-p: Exported classes
Slot, n-visits: Exported classes
Slot, n-visits: Exported classes
Slot, p-jumps: Exported classes
Slot, state: Exported classes
Slot, temperature: Exported classes
Slot, to-node: Exported classes
Special Variable, @micmac-game-theory: Exported special variables
Special Variable, @micmac-graph-search: Exported special variables
Special Variable, @micmac-introduction: Exported special variables
Special Variable, @micmac-links: Exported special variables
Special Variable, @micmac-manual: Exported special variables
Special Variable, @micmac-metropolis-hastings: Exported special variables
Special Variable, @micmac-overview: Exported special variables
Special Variable, @micmac-uct: Exported special variables
state: Exported classes

T
temperature: Exported classes
to-node: Exported classes

Jump to:   @  
A   C   D   E   F   H   J   N   P   S   T  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   C   E   M   P   S   T   U  
Index Entry  Section

C
Class, enumerating-chain: Exported classes
Class, mc-chain: Exported classes
Class, mc3-chain: Exported classes
Class, tracing-chain: Exported classes
Class, uct-edge: Exported classes
Class, uct-node: Exported classes

E
enumerating-chain: Exported classes

M
mc-chain: Exported classes
mc3-chain: Exported classes
micmac: The micmac system
micmac: The micmac package
micmac.game-theory: The micmac<dot>game-theory package
micmac.metropolis-hastings: The micmac<dot>metropolis-hastings package
micmac.uct: The micmac<dot>uct package

P
Package, micmac: The micmac package
Package, micmac.game-theory: The micmac<dot>game-theory package
Package, micmac.metropolis-hastings: The micmac<dot>metropolis-hastings package
Package, micmac.uct: The micmac<dot>uct package

S
System, micmac: The micmac system

T
tracing-chain: Exported classes

U
uct-edge: Exported classes
uct-node: Exported classes

Jump to:   C   E   M   P   S   T   U