Improved Tree Search for Automatic Program Synthesis
This work addresses the challenge of program synthesis for researchers and practitioners by improving search efficiency, though it appears incremental as it builds on existing MCTS methods.
The authors tackled the problem of efficient search in automatic program synthesis by proposing a variant of Monte Carlo Tree Search (MCTS) with modifications like a changed visit count and program encoding, achieving state-of-the-art results on two domain-specific languages.
In the task of automatic program synthesis, one obtains pairs of matching inputs and outputs and generates a computer program, in a particular domain-specific language (DSL), which given each sample input returns the matching output. A key element is being able to perform an efficient search in the space of valid programs. Here, we suggest a variant of MCTS that leads to state of the art results on two vastly different DSLs. The exploration method we propose includes multiple contributions: a modified visit count, a preprocessing procedure for the training dataset, and encoding the part of the program that was already executed.