Answers.Body: <p><strong>Approach 1:</strong> One way would be to switch from nodes representing programs to nodes representing sets of programs. The root node would represent the empty set <span class="math-container">${}$</span>, to which expansions could be applied only if they can generate a program from scratch. The first such expansion would produce some program <span class="math-container">$p$</span>, so the root would now have child <span class="math-container">${p}$</span>. The second expansion would produce <span class="math-container">$p'$</span>, so the root would now also have child <span class="math-container">${p'}$</span> which would itself also have the child ${p,p'}.</p>
  
  <p>One downside to this approach is that, even assuming reasonable restrictions (e.g. moves can use at most 2 programs, pairs cannot have identical elements, element order doesn't matter), the branching factor will grow combinatorially, because each new program can be combined with all (or most) of the previously generated programs.</p>
  
  <p><strong>Approach 2:</strong> Another way would be to switch from nodes representing programs to nodes representing meta-programs describing an initial program and a series of revisions to that program. For example, MCTS might search for expressions in something like this grammar:</p>
  
  <pre><code>Program  -&gt; Empty
            | Program &gt; OneProgramRevision
            | Program Program &gt;&gt; TwoProgramRevision
  OneProgramRevision -&gt; AddDatumAsException
                      | SampleStatement
                      | RegenerateSubtree
                      | Delete
                      | ...
  TwoProgramRevision -&gt; Concatenate
                      | Crossover
                      | ...
  </code></pre>
  
  <p>This is just a cartoon: one would need to add details parameterizing each of the various revisions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-24T02:04:07.057Z
Answers.LastActivityDate: 2020-03-24T02:21:54.120Z
Answers.LastEditDate: 2020-03-24T02:21:54.120Z
Answers.UserDisplayName: joshrule
Body: <p>I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples.</p>
  
  <p>My initial plan is for nodes to represent programs and for the search to expand nodes by revising programs. Each edge represents a possible revision.</p>
  
  <p>Many expansions involve a single program: randomly resample a subtree of the program, replace a constant with a variable, etc. It's straightforward to use these with MCTS.</p>
  
  <p>Some expansions, however, generate a program from scratch (e.g. sample a new program). Others use two or more programs to generate a single output program (e.g. crossover in Genetic Programming).</p>
  
  <p>These latter types of moves seem nonstandard for vanilla MCTS, but I'm not deeply familiar with the literature or what technical terms might be most relevant.</p>
  
  <p><strong>How can I model expansions involving <span class="math-container">$N \ne 1$</span> nodes? Are there accepted methods for handling these situations?</strong></p>
  
Tags: <monte-carlo-tree-search><monte-carlo-methods><computer-programming>
Title: MCTS moves with multiple parents
UserDisplayName: joshrule
ThreadText: # MCTS moves with multiple parents
  
  (Asked by: username_0 on 2020-03-24)
  
  I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples.
  
  My initial plan is for nodes to represent programs and for the search to expand nodes by revising programs. Each edge represents a possible revision.
  
  Many expansions involve a single program: randomly resample a subtree of the program, replace a constant with a variable, etc. It's straightforward to use these with MCTS.
  
  Some expansions, however, generate a program from scratch (e.g. sample a new program). Others use two or more programs to generate a single output program (e.g. crossover in Genetic Programming).
  
  These latter types of moves seem nonstandard for vanilla MCTS, but I'm not deeply familiar with the literature or what technical terms might be most relevant.
  
  **How can I model expansions involving $N \ne 1$ nodes? Are there accepted methods for handling these situations?**
  
  **Tags:** monte-carlo-tree-search, monte-carlo-methods, computer-programming
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-03-24. Score: 1
  
  Approach 1: One way would be to switch from nodes representing programs to nodes representing sets of programs. The root node would represent the empty set ${}$, to which expansions could be applied only if they can generate a program from scratch. The first such expansion would produce some program $p$, so the root would now have child ${p}$. The second expansion would produce $p'$, so the root would now also have child ${p'}$ which would itself also have the child ${p,p'}.
  One downside to this approach is that, even assuming reasonable restrictions (e.g. moves can use at most 2 programs, pairs cannot have identical elements, element order doesn't matter), the branching factor will grow combinatorially, because each new program can be combined with all (or most) of the previously generated programs.
  Approach 2: Another way would be to switch from nodes representing programs to nodes representing meta-programs describing an initial program and a series of revisions to that program. For example, MCTS might search for expressions in something like this grammar:
  Program  -> Empty
            | Program > OneProgramRevision
            | Program Program >> TwoProgramRevision
  OneProgramRevision -> AddDatumAsException
                      | SampleStatement
                      | RegenerateSubtree
                      | Delete
                      | ...
  TwoProgramRevision -> Concatenate
                      | Crossover
                      | ...
  
  This is just a cartoon: one would need to add details parameterizing each of the various revisions.
  
  
  ---
  
  