Program synthesis is often seen as the holy grail of computer science. A user only needs to provide program specifications and a computer will automatically generate the desired program. This often involves searching for the desired program in the program space, which is like searching for a needle in a haystack. Luckily, there is room for improvement here. Many programs in the program space are redundant and should never be considered. To filter out these redundant programs, we propagated grammar constraints during search using a novel built-in constraint solver. Only programs that satisfy these constraints will be considered as candidates for synthesis. To measure the effectiveness of the solver, we have enumerated several program spaces with and without constraints. Although the amount of filtering largely depends on the concrete grammar and constraints, the results show that constraints can often eliminate $99\%$ of the program space. Accounting for the overhead of propagation, this comes down to a 50-fold improvement in runtime.

Program synthesis is the task of generating a program that satisfies some specification. An important aspect of program synthesis is the method of specification. There are various ways in which a desired program can be specified, such as I/O examples, traces, and natural language. This research paper aims to explore a novel method of specifying a desired program in program synthesis -- rewards. This concept is explored by adjusting the Probe program synthesiser to solve the dense navigation environments in MineRL. In order to avoid local maxima, it is necessary to increase the amount of exploration. To that end, different ways of increasing exploration were tested by changing the parameters of Probe. By increasing the amount of exploration, it is possible to solve more environments, or solve them faster. But increasing exploration could also have the opposite effect, depending on the environment.

Program synthesis has been extensively used for automating code-related tasks, but it has yet to be applied in the realm of reward-based games. FrAngel is a component-based program synthesizer that addresses the aspects of exploration and exploitation, both important for the performance of a program synthesizer. However, its specific implementation makes it hard to study and extend. We first implement a generalized version of FrAngel that takes arbitrary grammars and program generators, while also generalizing most of its features by redesign. We then use it to introduce a novel approach to formulating a reward-based problem into an inductive specification. We integrate this algorithm within MineRL, an AI framework for playing Minecraft. Lastly, we lay the groundwork for using program synthesis for Minecraft by investigating the ways of tuning the algorithm to generate complex subprograms. By changing the configuration parameters, as well as slightly changing the algorithm’s implementation, we managed to observe a significant increase in the complexity of fragments and generated programs. These modifications are a stepping stone towards using program synthesis to solve complex game tasks.

Program synthesis remains largely unexplored in the context of playing games, where exploration and exploitation are crucial for solving tasks within complex environments. FrAngel is a program synthesis algorithm that addresses both of these aspects with its fragments used for the generation of new candidate programs. We introduce a generalised version of the FrAngel program synthesis algorithm that accepts an arbitrary iterator and grammar, enabling flexible modifications. We then formulate Program by Example (PBE) program synthesis from rewards and apply this framework to Minecraft's navigation task, where dense rewards guide the algorithm's exploration. Then, we use the generalised version of the algorithm to conduct experiments in the context of exploration of the algorithm. The experiments show the importance of exploration as a step required for the exploitation and finding the wanted solution to the task while also revealing that sometimes more exploration does not necessarily mean reaching the solution faster.

Program synthesis is the task to construct a program that provably satisfies a given high-level specification. There are various ways in which a specification can be described. This research focuses on adapting the Probe synthesizer, traditionally reliant on input-output examples, to utilize reward-based synthesis. The generalization of Probe allows for flexibility in using various search algorithms, selection and updating algorithms, enhancing its applicability to a general case. By modifying the Probe algorithm to learn from rewards, we explore how exploiting existing programs as partial solutions impacts synthesis performance. Different ways of exploitation were tested, specifically, how much the probabilities change, and how a starting probabilities can affect the synthesis. Exploitation of programs could lead to faster synthesis but it could also lead to no solutions depending on the world environment.

Machine learning pipelines encompass various sequential steps involved in tasks such as data extraction, preprocessing, model training, and deployment. Manual construction of these pipelines demands expert knowledge and can be time-consuming. To address this challenge, program synthesis offers an automated approach to generate computer programs based on high-level specifications or examples. By leveraging program synthesis, the development of machine learning solutions can be expedited, leading to broader adaptability. A key element of program synthesis is the objective function, which guides the combinatorial search for a program that satisfies user-defined requirements. This study examines the performance of the Monte Carlo Tree Search (MCTS) algorithm in the realm of generating machine learning pipelines through program synthesis. The research investigates the method's efficacy, explores its findings in terms of accuracy, cost, variance, and execution time, and draws conclusions regarding the algorithm's potential and limitations. By analyzing the MCTS algorithm's performance, this research contributes to the advancement of automated machine learning pipeline generation and highlights the benefits and considerations associated with using program synthesis techniques.