# 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

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.