Answers.Body: <p>I think you may get some inspiration from the work on deterministic environments by Javier Segovia et al. See their paper <a href="https://www.sciencedirect.com/science/article/abs/pii/S0004370219300232" rel="nofollow noreferrer">Computing programs for generalized planning using a classical planner</a> (2019).</p>
  <p>If you don't have access to Elsevier's papers, I recommend that you check out the <a href="https://dblp.org/pers/a/Aguas:Javier_Segovia.html" rel="nofollow noreferrer">first author's profile</a> on <code>dblp.org</code>. From there you will find links to open access versions of the conference paper that led up to the publication above.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-22T02:58:12.457Z
Answers.Text: Can you explain why that paper may be useful to answer the second question?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-23T10:59:09.787Z
Answers.Text: That paper targets a very specific class of programs and shows effective heuristic and search strategies to scale up with program size to some extent.
Answers.UserDisplayName: Miquel Ramirez
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-19T03:37:06.033Z
Answers.LastActivityDate: 2020-12-19T13:43:59.500Z
Answers.LastEditDate: 2020-12-19T13:43:59.500Z
Answers.UserDisplayName: Miquel Ramirez
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.</p>
  
  <p>Many of these expansions revise a single program: randomly resample a subtree of the program, replace a constant with a variable, etc. It looks 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.</p>
  
  <p>One idea I've had is to switch from nodes representing programs to nodes representing tuples of programs. The root node would represent the empty tuple <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> as well as the pair <span class="math-container">$(p, p')$</span>. Even assuming some 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.</p>
  
  <p><strong>What techniques from the MCTS literature (or other literatures) might reduce the impact of this combinatorial explosion?</strong></p>
  
Tags: <monte-carlo-tree-search><combinatorics><inductive-programming><program-synthesis>
Title: How can I reduce combinatorial explosion in an MCTS-like algorithm for program induction?
UserDisplayName: joshrule
ThreadText: # How can I reduce combinatorial explosion in an MCTS-like algorithm for program induction?
  
  (Asked by: username_0 on 2020-02-18)
  
  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.
  
  Many of these expansions revise a single program: randomly resample a subtree of the program, replace a constant with a variable, etc. It looks 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.
  
  One idea I've had is to switch from nodes representing programs to nodes representing tuples of programs. The root node would represent the empty tuple $()$, 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')$ as well as the pair $(p, p')$. Even assuming some 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.
  
  **What techniques from the MCTS literature (or other literatures) might reduce the impact of this combinatorial explosion?**
  
  **Tags:** monte-carlo-tree-search, combinatorics, inductive-programming, program-synthesis
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-02-19. Score: 0
  
  I think you may get some inspiration from the work on deterministic environments by Javier Segovia et al. See their paper [Computing programs for generalized planning using a classical planner](https://www.sciencedirect.com/science/article/abs/pii/S0004370219300232) (2019).
  
  If you don't have access to Elsevier's papers, I recommend that you check out the [first author's profile](https://dblp.org/pers/a/Aguas:Javier_Segovia.html) on `dblp.org`. From there you will find links to open access versions of the conference paper that led up to the publication above.
  
  > **Comments:**
  > **username_2**: Can you explain why that paper may be useful to answer the second question?  
  > **username_1**: That paper targets a very specific class of programs and shows effective heuristic and search strategies to scale up with program size to some extent.  
  
  ---
  
  