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?


1 Answer 1


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 (2019).

If you don't have access to Elsevier's papers, I recommend that you check out the first author's profile on dblp.org. From there you will find links to open access versions of the conference paper that led up to the publication above.

  • $\begingroup$ Can you explain why that paper may be useful to answer the second question? $\endgroup$
    – nbro
    Commented Feb 22, 2020 at 2:58
  • $\begingroup$ 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. $\endgroup$ Commented Feb 23, 2020 at 10:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .