Inductive Program Synthesis through using Monte Carlo Tree Search guided by a heuristic-based loss function

Inductive Program Synthesis through using Monte Carlo Tree Search guided by a heuristic-based loss function

Matulewicz, Nadia (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Algorithmics)

Dumančić, S. (mentor)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2022-01-28

Recently, a new and promising Inductive Program Synthesis (IPS) system, Brute, showed the potential of using a heuristic-based loss function. However, Brute also has its limitations and struggles with escaping local optima. The Monte Carlo Tree Search might offer a solution to this problem since it balances between exploitation and exploration. I design MUTE, a new IPS system which uses MCTS guided by a heuristic-based loss function. MUTE's performance is tested and compared to other IPS systems in three diverse domains, namely robot planning, ASCII art and string transformations. MUTE's performance for string transformations is a first indication that MUTE can outperform Brute and other IPS systems. Manual analysis of the results shows that MUTE can indeed escape local optima. Two branch reducing enhancements, namely the removal of similar programs and the removal of tokens that show no potential, are essential for the success of MUTE.

Inductive Program Synthesis
MUTE
Brute
Monte Carlo Tree Search
UCT
Program Synthesis
local optima

http://resolver.tudelft.nl/uuid:4ad6c3bf-6a66-4666-8700-aecd06b4407d

52.0022, 4.3736

https://github.com/victorvwier/BEP_project_synthesis Implementation code of MUTE and IPS systems that were used for comparison. Also contains uses test and training data.

Student theses

bachelor thesis

© 2022 Nadia Matulewicz