The micmac Reference Manual

This is the micmac Reference Manual, version 0.0.2, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sat Dec 03 22:30:12 2022 GMT+0.

Table of Contents


1 Introduction


2 Systems

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


2.1 micmac

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.

Author

Gábor Melis <>

Contact

Home Page

http://melisgl.github.io/mgl-gpr

Source Control

(GIT https://github.com/melisgl/mgl-gpr.git)

Bug Tracker

https://github.com/melisgl/mgl-gpr/issues

License

MIT, see COPYING.

Version

0.0.2

Dependencies
  • alexandria (system).
  • mgl-pax (system).
Source

micmac.asd.

Child Component

src (module).


3 Modules

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


3.1 micmac/src

Source

micmac.asd.

Parent Component

micmac (system).

Child Components

4 Files

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


4.1 Lisp


4.1.1 micmac/micmac.asd

Source

micmac.asd.

Parent Component

micmac (system).

ASDF Systems

micmac.


4.1.2 micmac/src/package.lisp

Source

micmac.asd.

Parent Component

src (module).

Packages

4.1.3 micmac/src/uct.lisp

Dependency

package.lisp (file).

Source

micmac.asd.

Parent Component

src (module).

Public Interface
Internals

4.1.4 micmac/src/graph-search.lisp

Dependency

uct.lisp (file).

Source

micmac.asd.

Parent Component

src (module).

Public Interface
Internals

4.1.5 micmac/src/metropolis-hastings.lisp

Dependency

graph-search.lisp (file).

Source

micmac.asd.

Parent Component

src (module).

Public Interface
Internals

4.1.6 micmac/src/game-theory.lisp

Dependency

metropolis-hastings.lisp (file).

Source

micmac.asd.

Parent Component

src (module).

Public Interface
Internals

4.1.7 micmac/src/micmac.lisp

Dependency

game-theory.lisp (file).

Source

micmac.asd.

Parent Component

src (module).

Public Interface

4.1.8 micmac/src/doc.lisp

Dependency

micmac.lisp (file).

Source

micmac.asd.

Parent Component

src (module).

Internals

5 Packages

Packages are listed by definition order.


5.1 micmac.uct

See MICMAC.UCT:@MICMAC-UCT.

Source

package.lisp.

Use List
  • common-lisp.
  • mgl-pax.
Public Interface
Internals

5.2 micmac.metropolis-hastings

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

Source

package.lisp.

Nickname

micmac.mh

Use List
  • common-lisp.
  • mgl-pax.
Public Interface
Internals

5.3 micmac

See MICMAC:@MICMAC-MANUAL.

Source

package.lisp.

Use List
  • common-lisp.
  • mgl-pax.
Public Interface
Internals

5.4 micmac.game-theory

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

Source

package.lisp.

Use List
  • common-lisp.
  • mgl-pax.
Public Interface
Internals

6 Definitions

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


6.1 Public Interface


6.1.1 Special variables

Special Variable: @micmac-game-theory
Package

micmac.game-theory.

Source

game-theory.lisp.

Special Variable: @micmac-graph-search
Package

micmac.

Source

graph-search.lisp.

Special Variable: @micmac-introduction
Package

micmac.

Source

micmac.lisp.

Package

micmac.

Source

micmac.lisp.

Special Variable: @micmac-manual
Package

micmac.

Source

micmac.lisp.

Special Variable: @micmac-metropolis-hastings
Package

micmac.metropolis-hastings.

Source

metropolis-hastings.lisp.

Special Variable: @micmac-overview
Package

micmac.

Source

micmac.lisp.

Special Variable: @micmac-uct
Package

micmac.uct.

Source

uct.lisp.


6.1.2 Setf expanders

Setf Expander: (setf state) (object)
Package

micmac.metropolis-hastings.

Source

metropolis-hastings.lisp.

Reader

state (generic reader).


6.1.3 Ordinary 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.

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.

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.

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.

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.

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.

Function: unvisited-edges (node)
Package

micmac.uct.

Source

uct.lisp.

Function: visited-edges (node)
Package

micmac.uct.

Source

uct.lisp.


6.1.4 Generic functions

Generic Function: accept-jump (chain jump candidate)

Called when CHAIN accepts JUMP to CANDIDATE.

Package

micmac.metropolis-hastings.

Source

metropolis-hastings.lisp.

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.

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.

Methods
Method: acceptance-probability (chain jump candidate)
Generic Reader: action (object)
Package

micmac.uct.

Methods
Reader Method: action ((uct-edge uct-edge))

The action represented by the edge.

Source

uct.lisp.

Target Slot

action.

Generic Function: average-reward (object)
Package

micmac.uct.

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

uct.lisp.

Reader Method: average-reward ((uct-node uct-node))

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

Source

uct.lisp.

Target Slot

average-reward.

Generic Writer: (setf average-reward) (object)
Package

micmac.uct.

Methods
Writer Method: (setf average-reward) ((uct-node uct-node))

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

Source

uct.lisp.

Target Slot

average-reward.

Generic Reader: depth (object)
Package

micmac.uct.

Methods
Reader Method: depth ((uct-node uct-node))

automatically generated reader method

Source

uct.lisp.

Target Slot

depth.

Generic Function: edge-score (node edge exploration-bias)
Package

micmac.uct.

Source

uct.lisp.

Methods
Method: edge-score ((node uct-node) edge exploration-bias)
Generic Reader: edges (object)
Generic Writer: (setf edges) (object)
Package

micmac.uct.

Methods
Reader Method: edges ((uct-node uct-node))
Writer Method: (setf edges) ((uct-node uct-node))

Outgoing edges.

Source

uct.lisp.

Target Slot

edges.

Generic Reader: from-node (object)
Generic Writer: (setf from-node) (object)
Package

micmac.uct.

Methods
Reader Method: from-node ((uct-edge uct-edge))
Writer Method: (setf from-node) ((uct-edge uct-edge))

The node this edge starts from.

Source

uct.lisp.

Target Slot

from-node.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

Methods
Method: prepare-jump-distribution :around (chain)
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.

Methods
Method: random-jump ((chain enumerating-chain))
Method: random-jump :before (chain)
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.

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.

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.

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 allowed to mutate PARENT-STATE and return it. This function must be specialized.

Package

micmac.uct.

Source

uct.lisp.

Generic Reader: state (object)
Package

micmac.metropolis-hastings.

Setf expander for this generic reader

(setf state).

Methods
Reader Method: state ((mc-chain mc-chain))

This is the current sample where the chain is.

Source

metropolis-hastings.lisp.

Target Slot

state.

Generic Reader: temperature (object)
Generic Writer: (setf temperature) (object)
Package

micmac.metropolis-hastings.

Methods
Reader Method: temperature ((mc-chain mc-chain))
Writer Method: (setf temperature) ((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.

Target Slot

temperature.

Generic Reader: to-node (object)
Generic Writer: (setf to-node) (object)
Package

micmac.uct.

Methods
Reader Method: to-node ((uct-edge uct-edge))
Writer Method: (setf to-node) ((uct-edge uct-edge))

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

Source

uct.lisp.

Target Slot

to-node.

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.

Methods
Method: update-uct-statistics ((node uct-node) path outcome)

6.1.5 Standalone methods

Method: initialize-instance :after ((chain enumerating-chain) &key n-jumps &allow-other-keys)
Source

metropolis-hastings.lisp.

Method: print-object ((node uct-node) stream)
Source

uct.lisp.

Method: print-object ((edge uct-edge) stream)
Source

uct.lisp.


6.1.6 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.

Direct superclasses

mc-chain.

Direct methods
Direct slots
Slot: p-jumps
Readers

p-jumps.

Writers

This slot is read-only.

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.

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.

Initform

1.0d0

Initargs

:temperature

Readers

temperature.

Writers

(setf temperature).

Slot: state

This is the current sample where the chain is.

Initargs

:state

Readers

state.

Writers

This slot is read-only.

Slot: candidate
Readers

candidate.

Writers

(setf candidate).

Slot: jump-distribution-prepared-p
Readers

jump-distribution-prepared-p.

Writers

(setf jump-distribution-prepared-p).

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.

Direct superclasses

mc-chain.

Direct methods
Direct slots
Slot: hot-chains
Type

list

Initargs

:hot-chains

Readers

hot-chains.

Writers

This slot is read-only.

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.

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.

Direct methods
Direct slots
Slot: action

The action represented by the edge.

Initargs

:action

Readers

action.

Writers

This slot is read-only.

Slot: from-node

The node this edge starts from.

Initargs

:from-node

Readers

from-node.

Writers

(setf from-node).

Slot: to-node

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

Readers

to-node.

Writers

(setf to-node).

Slot: n-visits

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

Initform

0

Readers

n-visits.

Writers

(setf n-visits).

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.

Direct methods
Direct slots
Slot: depth
Initform

0

Initargs

:depth

Readers

depth.

Writers

This slot is read-only.

Slot: n-visits

The number of times this node was visited.

Initform

0

Readers

n-visits.

Writers

(setf n-visits).

Slot: edges

Outgoing edges.

Readers

edges.

Writers

(setf edges).

Slot: average-reward

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

Initform

0

Initargs

:average-reward

Readers

average-reward.

Writers

(setf average-reward).


6.2 Internals


6.2.1 Macros

Macro: apply-key (key object)
Package

micmac.

Source

graph-search.lisp.

Macro: dup (n maker)
Package

micmac.

Source

graph-search.lisp.


6.2.2 Ordinary functions

Function: extremum (seq pred &key key)
Package

micmac.uct.

Source

uct.lisp.

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.

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.

Function: list-to-2d-matrix (list)
Package

micmac.game-theory.

Source

game-theory.lisp.

Function: log->acceptance-probability (x)
Package

micmac.metropolis-hastings.

Source

metropolis-hastings.lisp.

Function: pax-pages ()
Package

micmac.

Source

doc.lisp.

Function: pax-sections ()
Package

micmac.

Source

doc.lisp.

Function: random-element (seq)
Package

micmac.uct.

Source

uct.lisp.

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.

Function: random-until-different (limit tabu &key test)
Package

micmac.metropolis-hastings.

Source

metropolis-hastings.lisp.

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.


6.2.3 Generic functions

Generic Reader: candidate (object)
Package

micmac.metropolis-hastings.

Methods
Reader Method: candidate ((mc-chain mc-chain))

automatically generated reader method

Source

metropolis-hastings.lisp.

Target Slot

candidate.

Generic Writer: (setf candidate) (object)
Package

micmac.metropolis-hastings.

Methods
Writer Method: (setf candidate) ((mc-chain mc-chain))

automatically generated writer method

Source

metropolis-hastings.lisp.

Target Slot

candidate.

Generic Reader: hot-chains (object)
Package

micmac.metropolis-hastings.

Methods
Reader Method: hot-chains ((mc3-chain mc3-chain))

automatically generated reader method

Source

metropolis-hastings.lisp.

Target Slot

hot-chains.

Generic Reader: jump-distribution-prepared-p (object)
Package

micmac.metropolis-hastings.

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

automatically generated reader method

Source

metropolis-hastings.lisp.

Target Slot

jump-distribution-prepared-p.

Generic Writer: (setf jump-distribution-prepared-p) (object)
Package

micmac.metropolis-hastings.

Methods
Writer Method: (setf jump-distribution-prepared-p) ((mc-chain mc-chain))

automatically generated writer method

Source

metropolis-hastings.lisp.

Target Slot

jump-distribution-prepared-p.

Generic Reader: n-visits (object)
Generic Writer: (setf n-visits) (object)
Package

micmac.uct.

Methods
Reader Method: n-visits ((uct-edge uct-edge))
Writer Method: (setf n-visits) ((uct-edge uct-edge))

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

Source

uct.lisp.

Target Slot

n-visits.

Reader Method: n-visits ((uct-node uct-node))
Writer Method: (setf n-visits) ((uct-node uct-node))

The number of times this node was visited.

Source

uct.lisp.

Target Slot

n-visits.

Generic Reader: p-jumps (object)
Package

micmac.metropolis-hastings.

Methods
Reader Method: p-jumps ((enumerating-chain enumerating-chain))

automatically generated reader method

Source

metropolis-hastings.lisp.

Target Slot

p-jumps.

Generic Function: set-state (state chain)
Package

micmac.metropolis-hastings.

Source

metropolis-hastings.lisp.

Methods
Method: set-state (state chain)

Appendix A Indexes


A.1 Concepts


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): Public generic functions
(setf average-reward): Public generic functions
(setf candidate): Private generic functions
(setf candidate): Private generic functions
(setf edges): Public generic functions
(setf edges): Public generic functions
(setf from-node): Public generic functions
(setf from-node): Public generic functions
(setf jump-distribution-prepared-p): Private generic functions
(setf jump-distribution-prepared-p): Private generic functions
(setf n-visits): Private generic functions
(setf n-visits): Private generic functions
(setf n-visits): Private generic functions
(setf state): Public setf expanders
(setf temperature): Public generic functions
(setf temperature): Public generic functions
(setf to-node): Public generic functions
(setf to-node): Public generic functions

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

B
beam-search: Public ordinary functions

C
candidate: Private generic functions
candidate: Private generic functions

D
depth: Public generic functions
depth: Public generic functions
dup: Private macros

E
edge-score: Public generic functions
edge-score: Public generic functions
edges: Public generic functions
edges: Public generic functions
extremum: Private ordinary functions
extremum: Private ordinary functions

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

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

H
hot-chains: Private generic functions
hot-chains: Private generic functions

I
initialize-instance: Public standalone methods
insert-into-sorted-vector: Private ordinary functions

J
jump: Public generic functions
jump: Public generic functions
jump: Public generic functions
jump-between-chains: Public generic functions
jump-between-chains: Public generic functions
jump-distribution-prepared-p: Private generic functions
jump-distribution-prepared-p: Private generic functions
jump-to-sample: Public ordinary functions
jump-to-sample*: Public generic functions

L
list-edges: Public generic functions
list-to-2d-matrix: Private ordinary functions
log->acceptance-probability: Private ordinary functions
log-jump-probability-ratio: Public generic functions
log-probability-ratio: Public generic functions
log-probability-ratio-to-jump-target: Public generic functions
log-probability-ratio-to-jump-target: Public generic functions

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

N
n-visits: Private generic functions
n-visits: Private generic functions
n-visits: Private generic functions

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

P
p-jumps: Private generic functions
p-jumps: Private generic functions
parallel-beam-search: Public ordinary functions
pax-pages: Private ordinary functions
pax-sections: Private ordinary functions
play-out: Public generic functions
prepare-jump-distribution: Public generic functions
prepare-jump-distribution: Public generic functions
print-object: Public standalone methods
print-object: Public standalone methods

R
random-element: Private ordinary functions
random-element: Private ordinary functions
random-jump: Public generic functions
random-jump: Public generic functions
random-jump: Public generic functions
random-until-different: Private ordinary functions
reject-jump: Public generic functions
reject-jump: Public generic functions
reject-jump: Public generic functions
reject-swap-chain-states: Public generic functions
reject-swap-chain-states: Public generic functions
reject-swap-chain-states: Public generic functions

S
select-edge: Public generic functions
select-edge: Public generic functions
set-state: Private generic functions
set-state: Private generic functions
Setf Expander, (setf state): Public setf expanders
state: Public generic functions
state: Public generic functions
state: Public generic functions
sum-seq: Private ordinary functions

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

U
uct: Public ordinary functions
unvisited-edges: Public ordinary functions
update-uct-statistics: Public generic functions
update-uct-statistics: Public generic functions

V
visited-edges: Public ordinary functions


A.3 Variables

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

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

A
action: Public classes
average-reward: Public classes

C
candidate: Public classes

D
depth: Public classes

E
edges: Public classes

F
from-node: Public classes

H
hot-chains: Public classes

J
jump-distribution-prepared-p: Public classes

N
n-visits: Public classes
n-visits: Public classes

P
p-jumps: Public classes

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

T
temperature: Public classes
to-node: Public classes


A.4 Data types

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

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

D
doc.lisp: The micmac/src/doc․lisp file

E
enumerating-chain: Public classes

F
File, doc.lisp: The micmac/src/doc․lisp file
File, game-theory.lisp: The micmac/src/game-theory․lisp file
File, graph-search.lisp: The micmac/src/graph-search․lisp file
File, metropolis-hastings.lisp: The micmac/src/metropolis-hastings․lisp file
File, micmac.asd: The micmac/micmac․asd file
File, micmac.lisp: The micmac/src/micmac․lisp file
File, package.lisp: The micmac/src/package․lisp file
File, uct.lisp: The micmac/src/uct․lisp file

G
game-theory.lisp: The micmac/src/game-theory․lisp file
graph-search.lisp: The micmac/src/graph-search․lisp file

M
mc-chain: Public classes
mc3-chain: Public classes
metropolis-hastings.lisp: The micmac/src/metropolis-hastings․lisp file
micmac: The micmac system
micmac: The micmac package
micmac.asd: The micmac/micmac․asd file
micmac.game-theory: The micmac․game-theory package
micmac.lisp: The micmac/src/micmac․lisp file
micmac.metropolis-hastings: The micmac․metropolis-hastings package
micmac.uct: The micmac․uct package
Module, src: The micmac/src module

P
Package, micmac: The micmac package
Package, micmac.game-theory: The micmac․game-theory package
Package, micmac.metropolis-hastings: The micmac․metropolis-hastings package
Package, micmac.uct: The micmac․uct package
package.lisp: The micmac/src/package․lisp file

S
src: The micmac/src module
System, micmac: The micmac system

T
tracing-chain: Public classes

U
uct-edge: Public classes
uct-node: Public classes
uct.lisp: The micmac/src/uct․lisp file