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

Bachelor thesis (2022)

Authors

N.I. Matulewicz Electrical Engineering, Mathematics and Computer Science

Contributors

S. Dumančić Algorithmics - (mentor)

Faculty

Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science

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

To reference this document use:

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

More Info

expand_more

Published Date

28-01-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.

Files

Combinepdf_6_.pdf

(pdf | 0.551 Mb)