AG
A. Guncan
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
Program synthesis searches a grammar-defined space for a program that satisfies a user specification. Constraints can significantly reduce this search space. They can either be added manually by the user or derived through conflict analysis, which turns failed candidates into learned constraints. These constraints often retain irrelevant candidate details and accumulate costly redundancy. This thesis extends a conflict-analysis framework with core-guided MUC generalization and constraint-set cleanup. Generalization uses a semantic unsatisfiable core to wildcard irrelevant branches while preserving the candidate root and core nodes, as well as values referenced by core relations. Cleanup minimizes the active constraint set in many ways: by either removing constraints through exact deduplication or subsumption, or by merging constraints through single-differences and cross-relations. We evaluate both extensions on several benchmarks, assessing the reduced search space, constraint set size, runtime, and number of solved problems and used enumerations. At the largest program sizes, generalized MUC reduces enumerations by anywhere between 60 and 99.9%, consistently improving over the previous MUC implementation. Similarly, the strongest cleanup configuration can reduce the mean active constraint population by more than three orders of magnitude. While the new extensions manage to solve slightly more problems, their runtime improvement is negligible. Nonetheless, our extensions show that conflict analysis can learn substantially more general constraints and represent them more compactly.
...
Program synthesis searches a grammar-defined space for a program that satisfies a user specification. Constraints can significantly reduce this search space. They can either be added manually by the user or derived through conflict analysis, which turns failed candidates into learned constraints. These constraints often retain irrelevant candidate details and accumulate costly redundancy. This thesis extends a conflict-analysis framework with core-guided MUC generalization and constraint-set cleanup. Generalization uses a semantic unsatisfiable core to wildcard irrelevant branches while preserving the candidate root and core nodes, as well as values referenced by core relations. Cleanup minimizes the active constraint set in many ways: by either removing constraints through exact deduplication or subsumption, or by merging constraints through single-differences and cross-relations. We evaluate both extensions on several benchmarks, assessing the reduced search space, constraint set size, runtime, and number of solved problems and used enumerations. At the largest program sizes, generalized MUC reduces enumerations by anywhere between 60 and 99.9%, consistently improving over the previous MUC implementation. Similarly, the strongest cleanup configuration can reduce the mean active constraint population by more than three orders of magnitude. While the new extensions manage to solve slightly more problems, their runtime improvement is negligible. Nonetheless, our extensions show that conflict analysis can learn substantially more general constraints and represent them more compactly.
Program Synthesis from Game Rewards Using FrAngel
Finding Complex Subprograms for Solving Minecraft
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 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.