# How can I reduce combinatorial explosion in an MCTS-like algorithm for program induction?

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?

• Hi Josh and welcome to AI SE. Please, ask one question per post. You're asking too many questions in a single post! – nbro Feb 19 at 1:01
• @nbro - Thanks for letting me know. Sorry about that! – joshrule Feb 19 at 17:45
• Given that someone already attempted to give an answer to one of your questions, maybe edit this post only to leave that question and ask the other questions in their separate post ;) – nbro Feb 19 at 17:46

For question 2, 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.

• Hi and welcome to AI SE. Can you explain why that paper may be useful to answer the second question? – nbro Feb 22 at 2:58
• 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. – Miquel Ramirez Feb 23 at 10:59