Micmac Manual
Table of Contents
[in package MICMAC]
1 micmac ASDF System Details
 Version: 0.0.2
 Description: Micmac is mainly a library of graph search algorithms such as alphabeta, 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
 Homepage: http://quotenil.com
2 Introduction
2.1 Overview
MICMAC is a Common Lisp library by Gábor Melis focusing on graph search algorithms.
2.2 Links
Here is the official repository and the HTML documentation for the latest version.
3 Graph Search
[function] ALPHABETA STATE &KEY (DEPTH 0) ALPHA BETA CALLWITHACTION MAYBEEVALUATESTATE LISTACTIONS RECORDBEST
Alphabeta pruning for two player, zerosum 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 atDEPTH
and as the second value the list of actions of the principal variant.CALLWITHACTION
is a function of (STATE
DEPTH
ACTION
FN). It carries outACTION
(returned byLISTACTIONS
orNIL
) to get the state corresponding toDEPTH
and calls FN with that state. It may destructively modifySTATE
provided it undoes the damage after FN returns.CALLWITHACTION
is called withNIL
asACTION
for the root of the tree, in this caseSTATE
need not be changed. FN returns the same kinds of values asALPHABETA
. They may be useful for logging.MAYBEEVALUATESTATE
is a function of (STATE
DEPTH
). IfSTATE
atDEPTH
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 fromSTATE
to the position that was evaluated. The list of actions is typically empty. If we are not at a terminal node thenMAYBEEVALUATESTATE
returnsNIL
.LISTACTIONS
is a function of (STATE
DEPTH
) and returns a nonempty list of legal candidate moves for nonterminal nodes. Actions are tried in the orderLISTACTIONS
returns them: stronger movesCALLWITHACTION
,MAYBEEVALUATESTATE
andLISTACTIONS
are mandatory.RECORDBEST
, if nonNIL, is a function of (DEPTH
SCORE
ACTIONS
). It is called when atDEPTH
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.RECORDBEST
is useful for graceful degradation in case of timeout.ALPHA
andBETA
are typicallyNIL
(equivalent to infinity, +infinity) but any real number is allowed if the range of scores can be boxed.See
test/testalphabeta.lisp
for an example.
[function] BEAMSEARCH STARTNODES &KEY MAXDEPTH (NSOLUTIONS 1) (BEAMWIDTH (
LENGTH
STARTNODES
)) EXPANDNODEFN EXPANDBEAMFN SCOREFN UPPERBOUNDFN SOLUTIONPFN (FINISHEDPFNSOLUTIONPFN
)In a graph, search for nodes that with the best scores with beam search. That is, starting from
STARTNODES
perform a breadthfirst search but at each depth only keepBEAMWIDTH
number of nodes with the best scores. Keep the bestNSOLUTIONS
(at most) complete solutions. Discard nodes known to be unable to get into the bestNSOLUTIONS
(due toUPPERBOUNDFN
). Finally, return the solutions and the active nodes (the beam) as adjustable arrays sorted by score in descending order.STARTNODES
(a sequence of elements of arbitrary type).SCOREFN
,UPPERBOUNDFN
,SOLUTIONPFN
,FINISHEDPFN
are all functions of one argument: the node.SOLUTIONPFN
checks whether a node represents a complete solution (i.e. some goal is reached).SCOREFN
returns a real number that's to be maximized, it's only called for node for whichSOLUTIONPFN
returned true.UPPERBOUNDFN
(if notNIL
) returns a real number that equal or greater than the score of all solutions reachable from that node.FINISHEDPFN
returns true iff there is nowhere to go from the node.EXPANDNODEFN
is also a function of a single node argument. It returns a sequence of nodes to 'one step away' from its argument node.EXPANDBEAMFN
is similar, but it takes a vector of nodes and returns all nodes one step away from any of them. It's enough provide eitherEXPANDNODEFN
orEXPANDBEAMFN
. The purpose ofEXPANDBEAMFN
. is to allow more efficient, batchlike operations.See
test/testbeamsearch.lisp
for an example.
[function] PARALLELBEAMSEARCH STARTNODESEQS &KEY MAXDEPTH (NSOLUTIONS 1) BEAMWIDTH EXPANDNODEFN EXPANDBEAMSFN SCOREFN UPPERBOUNDFN SOLUTIONPFN (FINISHEDPFN
SOLUTIONPFN
)This is very much like
BEAMSEARCH
except it solves a number of instances of the same search problem starting from different sets of nodes. The sole purpose ofPARALLELBEAMSEARCH
is to amortize the costEXPANDBEAMFN
if possible.EXPANDBEAMSFN
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.PARALLELBEAMSEARCH
returns a sequence of solutions sequences, and a sequence of active node sequences.See
test/testbeamsearch.lisp
for an example.
3.1 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/testuct.lisp
for an example.

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 customizingMAKEUCTNODE
.
[accessor] EDGES UCTNODE
Outgoing edges.
[accessor] AVERAGEREWARD UCTNODE (:AVERAGEREWARD = 0)
Average reward over random playouts started from below this node. See
UPDATEUCTSTATISTICS
and REWARD.

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 specializeAVERAGEREWARD
for the edges if that's not the case.
[accessor] FROMNODE UCTEDGE (:FROMNODE)
The node this edge starts from.
[accessor] TONODE UCTEDGE (=
NIL
)The node this edge points to if the edge has been visited or
NIL
.
 [function] VISITEDEDGES NODE
 [genericfunction] EDGESCORE NODE EDGE EXPLORATIONBIAS
[genericfunction] SELECTEDGE NODE EXPLORATIONBIAS
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 maximumEDGESCORE
. 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 orUPDATEUCTSTATISTICS
instead.
[genericfunction] 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 ofUPDATEUCTSTATISTICS
. This is where one typically negates depending on the parity ofDEPTH
in two player games.
[genericfunction] UPDATEUCTSTATISTICS 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 toAVERAGEREWARD
based on whatOUTCOME>REWARD
returns.
[genericfunction] MAKEUCTNODE PARENT EDGE PARENTSTATE
Create a node representing the state of that
EDGE
leads to fromPARENT
. 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 TAKEACTION mutating it. The default implementation simply creates an instance of the class ofPARENT
so that one can start from a subclass ofUCTNODE
and be sure that that class is going to be used for nodes below it.
[genericfunction] STATE NODE PARENT EDGE PARENTSTATE
Return the state that corresponds to
NODE
. This is not a straightforward accessor unlessNODE
is customized to store it. The rest of the parameters are provided so that one can reconstruct the state by taking the action ofEDGE
in thePARENTSTATE
ofPARENT
. It's okay to destroyPARENTSTATE
in the process as long as it's not stored elsewhere. This function must be customized.
[genericfunction] LISTEDGES NODE STATE
Return a list of edges representing the possible actions from
NODE
withSTATE
. This function must be customized.
[genericfunction] PLAYOUT NODE STATE REVERSEPATH
Play a random game from
NODE
withSTATE
and return the outcome that's fed intoUPDATEUCTSTATISTICS
. The way the random game is played is referred to as `default policy' and that's what makes or breaksUCT
search. This function must be customized.
[function] UCT &KEY ROOT FRESHROOTSTATE EXPLORATIONBIAS MAXNPLAYOUTS
Starting from the
ROOT
node search the tree expanding it one node for each playout. Finally return the mutatedROOT
.ROOT
may be the root node of any tree, need not be a single node with no edges.FRESHROOTSTATE
is a function that returns a fresh state corresponding toROOT
. This state will be destroyed unless special care is taken inSTATE
.
4 Metropolis Hastings
[in package MICMAC.METROPOLISHASTINGS]
Generic interface for the MetropolisHastings 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/mcmcgibbsintro.pdf
Geyer, C.J. (1991) Markov chain Monte Carlo maximum likelihood
For now, the documentation is just a reference. See
test/testmetropolishastings.lisp
for an example.

A simple markov chain for Metropolis Hastings. With temperature it is suitable for
MC3
.
[accessor] TEMPERATURE MCCHAIN (:TEMPERATURE = 1.0d0)
The PROBABILITYRATIO of samples is raised to the power of 1 /
TEMPERATURE
before calculating the acceptance probability. This effectively flattens the peaks ifTEMPERATURE
> 1 which makes it easier for the chain to traverse deep valleys.
[function] JUMPTOSAMPLE CHAIN JUMP &KEY (RESULTSAMPLE (
STATE
CHAIN
))From the current state of
CHAIN
makeJUMP
(from the current distribution ofCHAIN
) and return the sample where we landed. ReuseRESULTSAMPLE
when possible.
[genericfunction] JUMPTOSAMPLE* CHAIN JUMP RESULTSAMPLE
This function is called by
JUMPTOSAMPLE
. It is whereJUMPTOSAMPLE
behaviour shall be customized.
[genericfunction] PREPAREJUMPDISTRIBUTION CHAIN
Prepare for sampling from the F(X) = Q(SAMPLE>X) distribution. Called by
RANDOMJUMP
. The around method ensures that nothing is done unless there was a state change.
[genericfunction] RANDOMJUMP CHAIN
Sample a jump from the current distribution of jumps that was computed by
PREPAREJUMPDISTRIBUTION
.
[genericfunction] LOGPROBABILITYRATIO 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.
[genericfunction] LOGPROBABILITYRATIOTOJUMPTARGET CHAIN JUMP TARGET
Return P(
TARGET
)/P(STATE
) whereJUMP
is from the current state ofCHAIN
toTARGET
sample. This can be specialized for speed. The default implementation just falls back onLOGPROBABILITYRATIO
.
[genericfunction] LOGJUMPPROBABILITYRATIO CHAIN JUMP TARGET
Return Q(TARGET>STATE) / Q(STATE>TARGET) where Q is the jump distribution and
JUMP
is from the currentSTATE
ofCHAIN
toTARGET
sample.
[genericfunction] ACCEPTANCEPROBABILITY CHAIN JUMP CANDIDATE
Calculate the acceptance probability of
CANDIDATE
to whichJUMP
leads from the currentSTATE
ofCHAIN
.
[genericfunction] ACCEPTJUMP CHAIN JUMP CANDIDATE
Called when
CHAIN
acceptsJUMP
toCANDIDATE
.
[genericfunction] REJECTJUMP CHAIN JUMP CANDIDATE
Called when
CHAIN
rejectsJUMP
toCANDIDATE
. It does nothing by default, it's just a convenience for debugging.
[genericfunction] MAYBEJUMP CHAIN JUMP CANDIDATE ACCEPTANCEPROBABILITY
Randomly accept or reject
JUMP
toCANDIDATE
from the current state ofCHAIN
withACCEPTANCEPROBABILITY
.
[genericfunction] JUMP CHAIN
Take a step on the markov chain. Return a boolean indicating whether the proposed jump was accepted.

High probability island separated by low valley make the chain poorly mixing.
MC3CHAIN
has a number ofHOTCHAINS
that have state probabilities similar to that of the main chain but less jagged. Often it suffices to set the temperatures of theHOTCHAINS
higher use the very same base probability distribution.
[genericfunction] ACCEPTSWAPCHAINSTATES MC3 CHAIN1 CHAIN2
Swap the states of
CHAIN1
andCHAIN2
ofMC3
.
[genericfunction] REJECTSWAPCHAINSTATES MC3 CHAIN1 CHAIN2
Called when the swap of states of
CHAIN1
andCHAIN2
is rejected. It does nothing by default, it's just a convenience for debugging.
[genericfunction] MAYBESWAPCHAINSTATES MC3 CHAIN1 CHAIN2 ACCEPTANCEPROBABILITY
Swap of states of
CHAIN1
andCHAIN2
ofMC3
withACCEPTANCEPROBABILITY
.
[genericfunction] JUMPBETWEENCHAINS MC3
Choose two chains randomly and swap their states with
MC3
acceptance probability.
[class] ENUMERATINGCHAIN MCCHAIN
A simple abstract chain subclass that explicitly enumerates the probabilities of the distribution.

Mix this in with your chain to have it print trace of acceptances/rejections.
5 Game Theory
[in package MICMAC.GAMETHEORY]
[function] FINDNASHEQUILIBRIUM PAYOFF &KEY (NITERATIONS 100)
Find a Nash equilibrium of a zerosum 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.