summaries: In this paper, the authors propose a new class of programs they call programming puzzles. The authors argue that this class of programs is ideal for helping learn AI systems to reason. The second contribution of the paper is an adaptive method of puzzle generation inspired by GAN-like generation that can generate a diverse and difficult set of programs. The paper shows that the generated puzzles are reasonably difficult to solve (using the time to solve as a measure of difficulty) and reasonably diverse.

summaries: This paper proposes a method for generating hard puzzles with a trainable puzzle solver. This is an interesting and important problem which sits at the intersection of symbolic and deep learning based AI. The approach is largely GAN inspired, where the neural solver takes the role of a discriminator, and the generator is trained with REINFORCE instead of plain gradient descend.

summaries: This paper proposes a trainable 'puzzle' program synthesizer that outputs a program f with a specific syntax. These 'puzzles' are structured as boolean programs, and a program solver solves the puzzle by finding an input x such that f(x) = True.  The authors motivate this task by making a case that puzzles of this sort are a good domain for teaching computers how to program.

abstractText: AI today is far from being able to write complex programs. What type of problems would best teach computers programming, and how should such problems be generated? We suggest programming puzzles as a domain for teaching computers programming. A programming puzzle is a short program for a Boolean function f(x) with the goal of finding an input that makes f return True. Puzzles are objective in that one can easily test the correctness of a candidate solution, in contrast to other common specifications for program synthesis like input-output pairs or English problem descriptions. To address automatic puzzle generation, we propose a GAN-like algorithm called “Troublemaker” which can generate puzzles adaptively targeted at any given puzzle-solver. Rather than generating a single dataset of puzzles at random, it generates a diverse set of puzzles that are difficult for the solver. In our experiments, Troublemaker learns to generate challenging problems for a variety of state-of-the-art puzzle-solving techniques.

authors:
Matej Balog
Alexander L Gaunt
Marc Brockschmidt
Sebastian Nowozin
Daniel Tarlow

title: Deepcoder: Learning to write programs

venue: arXiv preprint arXiv:1611.01989,

authors:
David GT Barrett
Felix Hill
Adam Santoro
Ari S Morcos
Timothy Lillicrap

title: Measuring abstract reasoning in neural networks

venue: arXiv preprint arXiv:1807.04225,

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston

title: Curriculum learning

venue: In Proceedings of the 26th annual international conference on machine learning,

authors:
James Bornholt
Emina Torlak

title: Synthesizing memory models from framework sketches and litmus tests

venue: In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation,

title: GNN-FiLM: Graph neural networks with feature-wise linear modulation

venue: arXiv preprint arXiv:1906.12192,

authors:
Marc Brockschmidt
Miltiadis Allamanis
Alexander L Gaunt
Oleksandr Polozov

title: Generative code modeling with graphs

venue: arXiv preprint arXiv:1805.08490,

title: The measure of intelligence

venue: arXiv preprint arXiv:1911.01547,

authors:
Konstantina Christakopoulou
Adam Tauman Kalai

title: Glass-box program synthesis: A machine learning approach

authors:
Jacob Devlin
Jonathan Uesato
Surya Bhupatiraju
Rishabh Singh
Abdel-rahman Mohamed
Pushmeet Kohli

title: Robustfill: Neural program learning under noisy i/o

venue: arXiv preprint arXiv:1703.07469,

authors:
Ishan Durugkar
Peter Stone

title: Adversarial goal generation for intrinsic motivation

venue: In ThirtySecond AAAI Conference on Artificial Intelligence,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

venue: In Advances in neural information processing systems,

authors:
Alex Graves
Marc G Bellemare
Jacob Menick
Remi Munos
Koray Kavukcuoglu

title: Automated curriculum learning for neural networks

authors:
Sumit Gulwani
William R Harris
Rishabh Singh

title: Spreadsheet data manipulation using examples

venue: Communications of the ACM,

authors:
Sumit Gulwani
Oleksandr Polozov
Rishabh Singh

title: Program synthesis

venue: Foundations and Trends® in Programming Languages,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

authors:
Ashwin Kalyan
Abhishek Mohta
Oleksandr Polozov
Dhruv Batra
Prateek Jain
Sumit Gulwani

title: Neural-guided deductive search for real-time program synthesis from examples

venue: arXiv preprint arXiv:1804.01186,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

title: Learning executable semantic parsers for natural language understanding

venue: Commun. ACM,

authors:
Zohar Manna
Richard Waldinger

title: A deductive approach to program synthesis

title: Zur theorie der gesellschaftsspiele

venue: Mathematische annalen,

authors:
Emilio Parisotto
Abdel-rahman Mohamed
Rishabh Singh
Lihong Li
Dengyong Zhou
Pushmeet Kohli

title: Neuro-symbolic program synthesis

venue: arXiv preprint arXiv:1611.01855,

authors:
Lerrel Pinto
James Davidson
Rahul Sukthankar
Abhinav Gupta

title: Robust adversarial reinforcement learning

authors:
David Saxton
Edward Grefenstette
Felix Hill
Pushmeet Kohli

title: Analysing mathematical reasoning abilities of neural models

authors:
Richard Shin
Neel Kant
Kavi Gupta
Chris Bender
Brandon Trabucco
Rishabh Singh
Dawn Song

title: Synthetic datasets for neural program synthesis

venue: In International Conference on Learning Representations,

title: On mathematical problem posing

venue: For the learning of mathematics,

authors:
Sainbayar Sukhbaatar
Zeming Lin
Ilya Kostrikov
Gabriel Synnaeve
Arthur Szlam
Rob Fergus

title: Intrinsic motivation and automatic curricula via asymmetric self-play

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Machine learning,

authors:
Maksym Zavershynskyi
Alexander Skidanov
Illia Polosukhin

title: NAPS: natural program synthesis

venue: dataset. CoRR,

title: Online convex programming and generalized infinitesimal gradient ascent

venue: In Proceedings of the 20th International Conference on Machine Learning

heading: 1 INTRODUCTION

text:
Computers still perform worse than humans at elementary programming and mathematical reasoning problems, let alone the AI grand challenge of designing, analyzing, and implementing sophisticated algorithms. For example, many symbolic mathematical software packages fail to solve nn n = 1010 10 for n. While programs can be taught to immediately answer such puzzles, it points to a fundamental lack of understanding that limits their ability to perform complex programming and mathematics.
The first question faced in the daunting task of teaching computers to program is, how should one represent programming problems to teach computers? The ideal representation may be different from what suits humans. Consider a question “What number follows the sequence 1-2-1-4-1-6-1?” (Barrett et al., 2018; Saxton et al., 2019). It requires: (a) understanding some English and (b) guessing which sequence the test-writer considers most natural among the many consistent ones. We refer to these biases as human priors. Program synthesis problems involve human priors as well. They are usually specified in English and/or by examples (Gulwani et al., 2012) such as “Extract the area code from a phone number” and/or “(212)123-4567”→ “212”. These involve prior knowledge about phone numbers, which may impede computers from learning the fundamentals of programming and math.1
In summary, to advance artificial reasoning, the ideal programming problem representation should be:
Objective: a candidate solution ought to be unambiguously validated as to whether or not it satisfies the specification. In particular, a problem-solving algorithm should be able to determine correctness without knowledge of English or consulting an answer key.
Challenging: Capture problems that human programmers can solve easily but which foil computers. Diverse: Capture a rich range of useful programming problems from easy to hard. Unbiased: Avoid dependence on human priors, such as language or spatio-temporal biases.
Programming Puzzles As a better standard for evaluating and advancing artificial reasoning, we propose Programming Puzzles. In a puzzle, given the source code of a function f in a fixed programming language (e.g. Python), the goal is to find an input x such that f(x) returns True.
1After creating NAPS (Zavershynskyi et al., 2018), a “Natural Programming Synthesis” dataset of programming contest problems with English descriptions and input-output examples, one of the authors later conceded that “ML, specifically natural language understanding, is not there yet.” (Polosukhin, 2018)
As Figure 1 illustrates, short puzzles can capture extremely difficult problems such as factoring or subset-sum as well as easy questions such as list reversal or solving (x+ 1)x+1 == 100100 for x. Importantly, such puzzles are objective – a candidate solution can easily be evaluated for correctness.
Not all programming problems can be nicely defined as puzzles. In some problems, writing the puzzle is as hard as solving the problem, e.g. long addition of two numbers. Other problems involve human priors, e.g. alphabetizing a list of names by last names, where language rules determine whether “Mary De Leon” is sorted under “D” or “L”. However, puzzles with polynomial-time definitions constitute the complexity class NP , which contains P problems such as shortest-path as well as hard problems such as factoring and finding a neural network with a sufficiently low training loss.
Troublemaker Our second main contribution is a “Troublemaker” algorithm that automatically generates puzzles in an adaptive manner to challenge any given puzzle-solving system. A primitive system may be given easy puzzles, while an advanced system may be given hard puzzles (or puzzles targeting a specific discovered weakness). Automatic problem generation has been applied to train program synthesis systems (Balog et al., 2016; Christakopoulou & Kalai, 2018) and in numerous related domains such as mathematical problems (Saxton et al., 2019) and IQ tests (Barrett et al., 2018). However, these problems were generated non-adaptively, often via random sampling. In this work, we use a host of state-of-the-art neural and symbolic machine intelligence techniques as target solvers, and show that Troublemaker learns to generate challenging puzzle datasets for all of them.
Troublemaker operates by searching for puzzles in a given grammar that would be hard for a given solver. The search process is made adaptive by guiding it with a trained neural network. The network is optimized to balance (a) difficulty of the puzzle w.r.t. the solver runtime, (b) diversity of generated puzzles, and (c) puzzle brevity. When the solver is trainable, this generation process results in an adversarial setup, where Troublemaker finds increasingly hard problems as the training progresses.
Contributions This paper introduces (1) programming puzzles, a class of objective problems that can be used to evaluate and improve the reasoning ability of existing AI systems; (2) an adaptive puzzle generator that can be targeted at any given puzzle solver(s). Note that we do not set out to create novel approaches for puzzle solving – we evaluate our puzzle generation on state-of-the-art neural and symbolic solvers. We focus on adaptive problem generation and establishing the puzzle domain as suitable for teaching machines how to program, leaving the improvements of puzzle solving techniques to future work.

heading: 2 RELATED WORK

text:
Program Synthesis The prior work on program synthesis is too large to survey here (see the survey by Gulwani et al., 2017). As mentioned, prior work on program synthesis largely works from input-output examples xi, yi where the goal is to find a “natural” function f such that f(xi) = yi.
This representation is subjective – the issue is not that there are multiple correct programs but rather that the correctness of a given solution f is debatable and cannot be determined from examples alone. Similarly, the research on semantic parsing (Liang, 2016) describes problems in natural language such as English, for which program correctness is even more debatable. From the point of view of expressing the intent of an end user, these representations may be quite natural and the ambiguity may be inherent to the problem. However, for the purpose of teaching computers programming and reasoning basics, such ambiguity impedes learning.
An exception is a closely-related work of Christakopoulou & Kalai (2018), which inspired this paper. They consider a specification that is itself a program that takes a whole problem-solving program as input. The specification program then generates a number of random inputs to the candidate program and ensures that the candidate satisfies them all. Similarly to our work, this specification in the form of source code is given to the problem solver.
A dual view of puzzles in that their solutions are programs, and the puzzle itself serves as a simple formal specification. Every puzzle solution can be then viewed as a constant program that satisfies this specification. In the programming languages community, the intent is often defined by a formal specification with the goal of finding any program that satisfies it (Manna & Waldinger, 1980; Bornholt & Torlak, 2017; Alur et al., 2018). The greater expressive power in some languages inherently means that it is not always trivial to determine whether a solution satisfies the specification.
Evaluating Intelligence and Reasoning Program synthesis systems that employ machine learning models are often trained on automatically generated programming problems (Balog et al., 2016; Christakopoulou & Kalai, 2018; Devlin et al., 2017; Parisotto et al., 2016). However, the way they generated problems was non-adaptive, i.e. independently of the solver. Recent work (Shin et al., 2019) has noted that such randomly generated datasets often fail to capture important properties of the desired program distribution, and thus result in a biased program synthesizer. Our Troublemaker framework allows adapting the dataset to the evaluation metric of a particular synthesizer.
As mentioned in Section 1, other tasks for evaluating and motivating progress in machine intelligence have been proposed, including mathematical word problems (Saxton et al., 2019) and IQ tests (Barrett et al., 2018). None of them achieve our desiderata of objectivity and independence of human priors. One notable example is the ARC task (Chollet, 2019), developed concurrently with this work. While it is also designed to establish a new standard in measuring intelligence and intentionally forgoes all human priors, its problem specification is still given by input-output pairs and thus is subjective.
Adversarial and Curriculum Learning The Troublemaker framework aims to generate short and diverse puzzles that are difficult for a given puzzle solver. As such, its main goal is to evaluate the solver and set an adaptive milestone to facilitate AI progress. However, a similar technique can be used to adaptively generate a training set, aiming to improve a given solver after discovering its weaknesses. In the machine learning community this is known as curriculum learning (Bengio et al., 2009; Graves et al., 2017; Sukhbaatar et al., 2018). The Alice-Bob framework of Sukhbaatar et al. (2018) is particularly relevant. In it, a teacher agent and a student agent engage in self-play where the teacher generates tasks for the student right at the edge of the student’s “comfort zone”, thus encouraging the student to continually improve. This is in contrast to Troublemaker, which over time generates problems just beyond the solver’s comfort zone to expose its limitations. When a solver is trainable, Troublemaker proceeds by iterating between improving the solver and the puzzle generator.
Troublemaker, Alice-Bob, and similar iterative frameworks drive inspiration from generative adversarial networks (GANs) (Goodfellow et al., 2014). In addition to wide usage in improving generative models via learned adversarial objectives, the GAN ideas have also been recently used to improve robustness of trained agents (Pinto et al., 2017) or to automatically adapt their reward functions (Durugkar & Stone, 2018). These works are typically applied to reinforcement learning based environments, while Troublemaker focuses on the problem of generating hard and diverse puzzles without any assumptions on the target solver.

heading: 3 PROBLEM GENERATION AS A ZERO-SUM GAME

text:
Our goal is to find a distribution over a diverse set of hard problems. The framework can be defined abstractly in terms of set P of problems and set S of solvers, where each problem p ∈ P computes a
Boolean function p : X → {>,⊥} for on some set X , and each solver S ∈ S computes a function S : P → X . Problem p is said to be easy for S if p(S(p)) = > and hard for S otherwise. The set S captures the resource constraints on solvers (e.g., our experiments have a time budget B by wrapping each solver in an appropriate timeout), and the set P captures restrictions on problems such as length limit and any other restrictions of interest such as solvability.
The Problem-generation game is a two-player zero-sum game between a Generator that chooses an arbitrary distribution D ∈ ∆(P) over P , where ∆(T ) denotes the set of probability distributions over set T , and a Learning Solver who chooses S ∈ S. For example, we implement S as a set of neural guided solvers whose parameters are trained by the Learning Solver. The payoff to the Generator is v(D,S) = Ep∼D[r(p, S,D)], where, r is a reward function and D(p) is the probability of generating problem p:
r(p, S,D) = { λ(− log2D(p)) + (1− λ) if p(S(p)) 6= > 0 if p(S(p)) = >. (1)
The reward is parameterized by λ ∈ [0, 1] which offers a trade-off: at λ = 0, any hard problem earns the Generator a reward of 1, while at λ = 1 the reward is the expected negative log-likelihood over hard problems. The reward function may seem peculiar at first since it depends not only on problem’s hardness but also on its probability of being generated. At λ = 0 the reward does not account for the diversity of the distribution of problems—against any solver S a generator could maximize v with the distribution that always outputs a single hard problem p ∈ S, yet we want D to generate diverse hard problems. To account for diversity, the reward therefore depends on D as well. As one varies λ from 0 to 1, one expects the fraction of hard problems to decrease but the entropy of the hard problems to increase, a measure of greater diversity.

heading: 3.1 STATIC SOLVER

text:
We consider two types of solvers. First, consider a fixed Solver S, i.e., the Learning Solver does not learn but instead just plays S, and let HS = {p ∈ P | p(S(p)) 6= > } denote the set of problems that are hard for S. It is not difficult to see that if the Generator only generates hard problems support(D) ⊆ HS , then v(D,S) = 1− λ− λH(D), where H(D) is the entropy of distribution D. Entropy is a standard notion of diversity of a distribution, though other notions may be used.
Lemma 1. For any λ ∈ (0, 1] and any solver S with |HS | ≥ 3 hard problems, the uniform distribution UHS over HS uniquely maximizes the Generator’s payoff v(UHS , S) = 1− λ+ λ log2 |HS |.
All proofs are deferred to Appendix B. In practice, of course the Generator may not find this uniform distribution but |HS | ≥ 2v(D,S) remains a lower bound for whatever D is found.

heading: 3.2 LEARNING SOLVER

text:
Next, consider an adaptive solver that can tailor its choice of S ∈ S by adjusting its parameters. Based on the theory of zero-sum games (Myerson, 2013), the game has a unique “value” that can be achieved by possibly different optimal “mixed strategies” which are probability distributions themselves. In the Problem-generation game, this is somewhat confusing as mixed strategies for the Generator are distributions over distributions of problems in ∆(∆(P)), and mixed strategies for the solver are distributions over solvers in ∆(S). However, we next show that there is a single optimal strategy for the Generator (as long as each solver has 3 hard problems). Fortunately, this optimal Generator strategy is a “pure strategy”, a single distribution D∗ ∈ ∆(D) over problems rather than a distribution over distributions. Nontheless, there may be multiple optimal strategies for the Learning Solver.
Theorem 1. For any set S and λ ∈ (0, 1], as long as each solver S fails on at least |HS | ≥ 3 problems, there is a unique distribution D∗ that achieves the value of the zero-sum Problem-generation game.
In particular, D∗ is simply the distribution that maximizes J(D) = minS∈S v(D,S). As mentioned, λ = 0 can admit multiple (degenerate) optimal solutions. Like Lemma 1, this Theorem is a theoretical statement as it is not clear that the Generator will find D∗.
Algorithm 1: The Troublemaker algorithm for finding parameters for the generator distribution. If a learning solver cannot accommodate weights, subsampling can be used to simulate weights. Input: sample size n, number of steps N , step size η, a function that generates samples for any
given Dθ, a differentiable function that computes log-probabilities for Dθ and either: (a) fixed solver S or, (b) Learning Solver that maps a weighted set of problems to solver S.
1 Choose θ1 ∈ Θ 2 for i← 1 to N do 3 Create a problems sample pi1, pi2, . . . , pin by independent draws from Dθi 4 if S is a fixed solver then Si ← S 5 else feed problems pi1, . . . pin with weights wij = 1− λ− λ logDθi(pij) on problem pij into
the Learning Solver and let Si be its output. (In practice, the parameters of Si−1 can be used as a warm start.)
6 Ui ← the set of sample problems that Si failed to solve 7 Update by summing over problems that Si doesn’t solve:
θi+1 = θi + η n ∑ p∈Ui ( 1− 2λ− λ logDθi(p) ) ∇θ logDθi(p)
8 end 9 return generator parameters θN

heading: 3.3 TROUBLEMAKER ALGORITHM FOR SOLVING THE PROBLEM-GENERATION GAME

text:
To find the distribution D∗, one may maximize J(D) = minS∈S v(D,S), which is concave in D:
Observation 1. The function J(D) = minS∈S v(D,S) is concave in D.
Hence, as a concave function, it can be theoretically maximized to within arbitrary precision, using the standard gradient-projection ascent, namely:
1 Choose D1 to be uniform over P 2 for i← 1 to N do 3 Find solver Si to minimize v(Di, S) 4 Update Di+1 = Π∆(P) ( Di + η∇Dv(Di, Si)
) 5 end
Here we have used the fact that a gradient of a minimum of functions is the gradient of whichever function is minimal at that point. Note that minimizing v(Di, S) over S ∈ S is equivalent to finding the solver that solves the most problems where each problem p has a non-negative weight wp = 1 − λ − λ logDi(p). Also, ΠT denotes the projection on to the closest point in convex Euclidean set T , in this case the closest probability distribution. This gradient-projection method is known to converge at a rate that depends on N and step size η > 0 (e.g. Zinkevich, 2003). However, this again is a theoretical algorithm assuming that one can represent an arbitrary distribution and can evaluate v(S,D) over all problems, which is computationally intractable. In practice, one represents a Generator Dθ by parameters θ ∈ Rn and optimizes them w.r.t. the samples drawn from the generator. The TM algorithm, described in Algorithm 1, follows the alternating gradient ascent procedure above procedure except that, using a sampling approximation similar to the REINFORCE algorithm (Williams, 1992) except that the gradient calculation is changed since the reward depends on the probability of generation. It requires sampling from Dθ and computing gradients∇θ logDθ(p) of log-probabilities, as is standard for sequential neural generation procedures. One also needs to be able to compute a best solver in response to a distribution of problems, which a Learning Solver can also approximate from problems sampled from Dθ. The analysis showing how the update in Step 4 is an unbiased estimate of the gradient of J is given in Lemma 2 in Appendix B.

heading: 4 TROUBLEMAKER: GENERATING PROGRAMMING PUZZLES

text:
Having derived a general form of the problem generation problem, we turn our attention to its instantiation in the Troublemaker framework. In this section, we first define a problem representation for puzzles used by our generator Dθ, and then describe the architecture of the trainable generator.
puzzles with floating-point solutions. Each production rule is annotated with a weight, automatically learned by the generator (see main text).
We assume a language of programs L defined as a Context Free Grammar (CFG). Each abstract syntax tree (AST) T ∈ L describes a programming puzzle problem pT : X → {>,⊥}, as defined in Section 3. When T is clear from context, we write p instead of pT . For the purpose of this paper, we assume interesting problems are hard puzzles whose solution a solver cannot obtain within the given time budget i.e. time(S, pT ) > B. However, our framework is agnostic to this assumption and can be trivially modified to generate problems for different notions of “interesting.”
To generate puzzles that involve complex reasoning patterns, the language L needs to be expressive enough to represent a wide range of puzzles. For example, Figure 2 shows an excerpt from our grammar for generating floating-point puzzles (full definition in Appendix A). Due to its expressiveness, sampling programs from L uniformly at random is not useful as it may generate overly simple problems or even unsolvable ones like x2 = −1. We will first describe our core procedure for generating puzzles in L, and will then turn our attention to ensuring their complexity and solvability.

heading: 4.1 GENERATION MODEL

text:
Generation with Probabilistic Grammars The first generation strategy we consider is to employ a probabilistic grammar as shown in Fig. 2. As can be seen, depending on the solver, different rules can be encouraged to bias the production of problems. For instance, the weights in Fig. 2 display a higher preference for multiplication of terms – this lends itself conveniently to the generation of puzzles with higher-degree polynomials. Note that the probability of generating a program p factorizes into its constituent production rules:
Pr(pT ) = ∏ r∈T Pr(r)
which constructively corresponds to a standard sampling procedure that builds the AST T one production at a time by sampling a production to expand each nonterminal using its corresponding weight as an unnormalized probability. Further, as mentioned, we aim to produce hard problems, i.e. maximize log time(S, T ) or, in general, any reward that fits into the framework described in Section 3. The weights θ of the probabilistic grammar can be learned using Algorithm 1, since sampling, computing the log-likelihood and its gradient are straightforward.
Neural Guided Generation While this strategy allows us to tailor generation for a given solver, it only tunes global preferences (i.e. encourages certain rules always) as opposed to context-dependent changes (i.e. rule A is preferred conditioned on the current partial AST). To enable finer-grained control over the generation process, we propose a more versatile generation strategy that conditions prediction of a rule on the rules in a partial AST produced so far. The context-dependent conditioning model is parameterized as a trainable neural network, whose parameters guide the generation process.
Let T< t be a partial AST generated so far at the generation timestep t, assuming some fixed ordering of nonterminal expansions to generate the whole AST (we use the pre-order traversal). The neural-guided generation strategy parameterized the probability of the puzzle as
Pr(pT ) = ∏ t Pr(rt | T<t)
where rt is the production rule expanded in the AST T at the tth timestep. The probability Pr(rt | T<t) is, in turn, parameterized as a neural network that takes as input a partial tree embedding φ(T<t) and outputs a distribution of probabilities for each syntactically valid production rule.
We consider two state-of-the-art approaches to parameterize the tree embedding model φ. The first parameterization is a naïve baseline – encoding a traversal of the tree T<t with an LSTM (Hochreiter & Schmidhuber, 1997). While straightforward, it does not explicitly makes use of the syntax structure present in the AST. Motivated by recent research in program representation (Allamanis et al., 2017; Brockschmidt et al., 2018), we choose graph neural networks (GNNs) as a second tree embedding model. Specifically, the model employed is GNN-FiLM (Brockschmidt, 2019), a recent GNN architecture that allows for feature-wise linear modulations, achieving state-of-the-art performance on a range of graph tasks like node classification.

heading: 4.2 COMPLEX AND SOLVABLE PUZZLES

text:
Generating Solvable Programs In order to generate solvable puzzles, we use domain-specific knowledge to convert a puzzle sampled from L to a solvable one. To continue with the floatpuzzle example, we first select a random solution x0. Then given an equation a(x) == b(x) where both a, b ∈ Lterm, we can convert it to a solvable puzzle at x0 by modifying the program to be a(x) = b(x)− k where k = a(x0)− b(x0).
Generating Complex Puzzles A standard strategy employed by experts for posing mathematical problems is chaining (Silver, 1994). Chaining expands on an existing problem (and solution) such that finding the solution for the modified problem requires solving the original problem as an intermediate step. For instance, in the case of our float-puzzle problems, exponentiating both sides of the equation is a good example of chaining – while preserving the solvability, it requires solving the original problem as an intermediate step (after taking log of both sides). In our setting of generating programming puzzles, we incorporate this problem posing strategy via tree-rewriting rulesR : L→ L that transform an existing AST to another AST in the language. For the example of float-puzzles, Fig. 3 provides a bank of tree-rewrite rules that can be used to produce complex solvable puzzles.
This approach is sufficiently general to apply to other domains such as int-puzzles or set-puzzles. For example, consider the sub-set sum problem – find set B ⊆ A such that the sum of elements in B is a given integer K. If this set-puzzle is solvable, chaining can be used to produce more complex puzzles by replacing A with A ∪ C for some non-empty integer set C. This transformation preserves solvability but can also make the puzzle harder, e.g. if the entire set B = A is initially a solution.

heading: 4.3 TRAINABLE SOLVERS

text:
Finally, while the Troublemaker framework as presented in Algorithm 1 is applicable for an arbitrary solver, it is particularly interesting for trainable solvers that can be improved with data produced by the generator. For them, the Troublemaker generation leads to an adversarial optimization process where the weights of the puzzle generator are updated to produce harder problems for the solver and similarly, the solver’s weights are updated based on the newly generated hard problems. In this work, we study two variants of trainable solvers:
Induction Solver (IS): This neural solver directly outputs the solution x of the puzzle pT given some embedding of the puzzle ψ(T ). In the case of structured outputs (like sets), the solver sequentially outputs elements along with a stop token to signal the end of generation.
Synthesis Solver (SS): This solver is similar to the neural generator – given a grammar L along with a bank of useful constants, it constructs a solution x as a constant expression in the grammar. The construction procedure is similar to puzzle generation – at each timestep t, it uses an encoding of the puzzle ψ(T ) and the current partial expression to select the next production rule to expand in the expression. Notably, while the generator emits the puzzle pT using an end-to-end differentiable LSTM, we found that synthesis of solutions x is best parameterized as a discrete search process guided by the rule-prioritizing neural network as described above. This is similar to other state-of-the-art neuro-symbolic program synthesis techniques such as DeepCoder (Balog et al., 2016) and NGDS (Kalyan et al., 2018).
In both solvers, the puzzle embedding modelψ(T ) is a GNN-FiLM network, parameterized identically to the generator’s embedding model (Section 4.1).

heading: 5 EXPERIMENTS

text:
In this section, we present results for the TroubleMaker approach to generate hard problems for a given solver. We consider float, int and intset puzzles to demonstrate the flexibility of the proposed puzzle generation framework. We provide the full grammar and tree-rewrites in Appendix A.
Puzzle Generators As discussed earlier, we study both probabilistic grammar based and neuralguided problem generators. Further, in the grammars used, we allow copy operations i.e. that can copy a node of type τ from the partial tree generated so far as opposed to generating a tree from LNT where NT is of type τ . The introduction of this operator helps the puzzle generator produce recursive structure (e.g. 1010 − xx = 0) – a desirable quality that often results in interesting reasoning patterns. As discussed in Sec. 4.1, both generators are trained using Algorithm 1. Unless otherwise mentioned, all the solvers are capped to run within a time limit of 0.1s. Similarly, the size (# rules) of the puzzles is limited to a maximum of 20 and cannot exceed a depth of 10. Recall the definition of the reward function (Eq. 1) – ideally, a generator that maximizes this reward should have uniform support over “hard” puzzles (i.e. solver fails to solve within 0.1s) and at most be of size 20.
Solvers We consider multiple solvers, both static and trainable. We now give their details below:
Grid Search (GrS): This solver, as the name suggests, searches in the solution space, narrowing down to a satisfying solution based on comparisons. Unlike other solvers, a solution is passed off as correct if the equation holds within a specified tolerance. In our experiments, we use a fairly small tolerance of 10−32. Note that this solver is not a general purpose puzzle solver and is used only in the context of floating point and integer puzzles.
Sympy (https://www.sympy.org) is a Python library for symbolic mathematics and similar to GrS, it is used to only solve floating point and integer problems. Specifically, we use the solve function to evaluate the generator. Sometimes, despite arriving at the right solution, errors due to rounding the solution to floating point numbers causes the objective to be non-zero. Similar to GrS, we account for this by requiring the equation to hold within a specified tolerance – this check is performed only if the solver returns a solution.
Enumerative Solver (ES): Given a grammar to generate the solution, this solver performs enumerative search to find a satisfying solution. For the sake of simplicity, we provide the solver with the same grammar used to generate a puzzle, albeit without the ability to produce variables. Apart from the constants already present in the grammar, the solver can also use constants extracted from the puzzle.
Guided Solver (GS): This solver builds on top of the enumerative solver by using a neural network to guide the search process conditioned on the puzzle, as described in Section 4.3. By learning heuristics from data, this solver learns to accelerate enumerative search by pruning away large portions of the search space.
We also consider a simpler version of the guided solver where instead of a neural network, we have a pCFG like setting where a single weight determines the application of a rule. In both cases, the generator samples from the probability distribution produced on the set of rules (or rewrite rules).
Training Details As mentioned
before, the generators are trained by maximizing for the reward in Eq. (1). The trainable solver guides the generation process exactly like the generator and is also trained via REINFORCE to maximize the number of solved puzzles. Additionally, the trainable solver is often warm started by using the traces of the enumerative solver. Both solvers and puzzle generators, when trainable, are optimized using Adam (Kingma & Ba, 2014) with a learning rate of 10−2. All the LSTM networks use a hidden size of 64, and all GNN-FiLM networks use 3 propagation steps and a node representation size of 64.
Results In terms of achieving higher reward values (see Fig. 4) and thus, producing more unsolvable problems for a static solver (see Fig. 5, the neural guided approach is better than the probabilistic grammar based generator. Both outperform randomly sampling puzzles from the grammar. Example generations with high reward are provided in Fig. 7.
In the case of learnable solvers, both the pCFG based and the guided solvers are trained for N = 100 iterations and each iteration ∼ 2000
puzzles are sampled from the generator. From Figure 6, we see that the generator is always in a position to find more “hard”problems for the learning solver – likely because of building the guided solvers on top of the enumerative solvers. From qualitative examples presented in Figure 7, one can see that both the enumerative and the guided solvers have similar weaknesses (e.g. exponentiation) as appropriate inverse operations like square roots are not present in the grammar. Further, the solvers learned via TM are tuned to the distribution of problems from the corresponding generator – they solve only about 100 randomly sampled puzzles from the grammar (when evaluated at any iteration).

heading: 6 CONCLUSIONS

text:
This work suggests a new type of problem called Programming Puzzles and a framework for generating a large set of hard problems that can both expose the weaknesses of existing solvers and which can be used in a GAN-like setup to train better solvers. Our system differs from prior work on data sets of problems, in that: (1) our puzzles are short, interpretable problems which may have multiple solutions but for which it is trivial to validate the accuracy of any solution, and (2) the puzzles are targeted specifically at any given solver. While it would be useful to have a ground-truth dataset of puzzles drawn from e.g. programming contests like ACM ICPC (see Appendix C), such a dataset is not strictly necessary for our worst-case approach.
One of the technical challenges that arises is that, in addition to optimizing for hardness, we also seek a large set of problems. Hence the reward of the puzzle generator takes into account the probability of each generated puzzle, which is uncommon in most GANs or reinforcement learning problems. Nonetheless, we show that the problem can be made well-defined in a differentiable pipeline, with a unique optimum solution that can be shown to converge. While our system is far from the final word on this problem, we believe these two ideas may initiate a line of work in which it is easier to make progress on the grand challenge of teaching computers to write complex programs.

heading: A GRAMMARS AND TREE-REWRITE RULES

text: We present the full grammars for the float and int-set domains used in this work in Figure 8. The integer rules are similar to the float domain except with additional functions factorial and modulo.

heading: B THEORETICAL ANALYSIS AND PROOFS

text:
Proof of Lemma 1. We can write the payoff as v(D,S) = ∑ p∈HS D(p) ( λ(− logD(p)) + 1− λ ) = (1− λ)D(HS)− λ ∑ p∈HS D(p) logD(p).
Clearly (1− λ)D(HS) ≤ 1− λ is maximized if and only if all problems generated are hard for S. The second term − ∑ p∈HS D(p) logD(p), is the entropy which is known to be maximized over the uniform distribution but is only summed over HS . For example, if λ = 1 and |HS | = 1, then the uniform distribution over HS would have a payoff of 0 because it has 0 entropy, and a distribution which put probability 1/e on this hard problem and probability 1− 1/e on an easy problem would actually be optimal. However, whatever probability D(HS) is assigned to hard problems, it is straightforward to see optimality requires distributing this uniformly over HS : by the strict concavity of the −z log z function there is a unique optimum and by symmetry it is uniform. Finally, since −z log z is increasing up to z = 1/e > 1/3, this quantity is only increasing in D(HS) as long as there are at least three hard problems, so the optimum is D(HS) = 1 only over hard problems. To prove Theorem 1, a key technical observation is that v(D,S) = ∑ p∈HS D(p) ( λ(− logD(p)) +
1 − λ )
is concave in D, which follows from the concavity of −z log z for z ∈ [0, 1]. Hence, as a zero-sum game with actions D ∈ ∆(P) and S ∈ S , if the game were played with “mixed strategies” in which players could randomize amongst D and S, it is a dominant strategy for the Generator never to randomize—instead it could achieve an expected payoff at least as large as any distribution over D’s by choosing the mean of the distributions. Hence, the “value” of this zero-sum game, given P , S (and λ), is:
v(P,S) = max D∈∆(P) min S∈S v(D,S).
In fact, this optimization has a unique optimal distribution D (which is not true of zero-sum games in general, and there may be multiple optimal mixed strategies for the Solver):
Proof of Theorem 1. The minimax theorem (Neumann, 1928) implies that,
v(P,S) = max D∈∆(P) min S∈S v(D,S) = min µ∈∆(S) max D∈∆(P) ES∼µ[v(D,S)],
where we have simplified again by the concavity of v in D in not consider distributions over D’s. In particular, let µ∗ be any minimizer of the right-hand-side above. Any maximum D∗ of minS∈S v(D,S) must also maximize ES∼µ∗ [v(D,S)], which we denote by,
v(D,µ∗) = ES∼µ∗ [v(D,S)] = ∑ p µ∗({p | p ∈ HS})D(p) ( λ(− log2D(p)) + 1− λ ) .
It remains to argue that there is a unique D∗ which maximizes the above quantity. Note that − log2D(p) ≥ 0 so the quantity in the right-hand parentheses is non-negative. Also note that −D(p) logD(p) is increasing for 0 ≤ D(p) < 1/e. Let hp = µ∗({p | p ∈ HS}) be the hardness of p, the probability a random solver from µ doesn’t solve p. We do this by arguing, first, that any maximal D∗ would assign D(p) = 0 to any “easy” puzzle p such that hp = 0. To see this, note that since every solver has three puzzles that are hard for it, there must be at least three puzzles for which hp > 0 and at least one of these call it p′ must have D(p′) ≤ 1/3 < 1/e and hp′ > 0. Hence, v(D,µ∗) could be increased by taking an amount of probability D(p) assigned to a p with hp = 0 and moving it to p′.
Therefore D distributes its probability only over p with hp > 0. Since −D(p) logD(p) is strictly concave and D(p) is trivially concave (as a linear function), the quantity of interest,∑
p:hp>0
hpD(p) ( λ(− log2D(p)) + 1− λ ) is strictly concave in D and hence has a unique maximum. To see why you need some lower-bound on the number of hard puzzles, note that if only one puzzle p′ was hard for all solvers ∀S HS = {p′}, λ = 1, and all other puzzles were easy, then the optimum solution would not put all D on the hard puzzle. Instead it would be optimal to assign D(p′) = 1/e and spread the remaining 1− 1/e fraction of probability arbitrarily among the puzzles where hp = 0.
We now discuss how Step 4 of the TM algorithm (see Figure 1) yields an unbiased estimate of the gradient∇θJ(Dθ) from samples. Lemma 2. For any Generator Dθ and solver S, over random iid samples p1, . . . , pn from D,
∇θv(Dθ, S) = Ep1,...,pn∼D  1 n ∑ j:pj∈HS ( 1− 2λ− λ logDθ(pj) ) ∇θ logDθ(pj)  . Again, pj ∈ HS means that solver S did not solve problem pj .
Proof. We first compute the gradient of J(Dθ) with respect to θ: ∇θJ(Dθ) = ∇θEp∼Dθ [r(p, S,Dθ)]
= ∑ p ∇θ ( Dθ(p)r(p, S,Dθ) ) = ∑ p r(p, S,Dθ)∇θDθ(p) +Dθ(p)∇θr(p, S,Dθ)
= ∑ p r(p, S,Dθ)Dθ(p)∇θ logDθ(p) +Dθ(p)∇θr(p, S,Dθ)
= Ep∼Dθ [ r(p, S,Dθ)∇θ logDθ(p) +∇θr(p, S,Dθ) ] In the second-to-last line above, we have used the standard “REINFORCE trick” writing ∇f(θ) = f(θ)∇ log f(θ) to make it writable as an expectation. Also note that above applies to an arbitrary reward whose gradients may be computed by automatic differentiation, so the approach generalizes to other reward functions.
Now, for our specific reward function defined in Eq. (1),∇θr(p, S,Dθ) = −1p∈HSλ∇θ logDθ(p), where 1P for proposition P is the indicator function that is 1 if P holds and 0 otherwise. Using this notation, r(p, S,Dθ) = 1p∈HS (1− λ− λ logDθ(p)). Hence, we have, ∇θJ(Dθ) = Ep∼Dθ [ 1p∈HS (1− λ− λ logDθ(p))∇θ logDθ(p)− 1p∈HSλ∇θ logDθ(p)
] = Ep∼Dθ [ 1p∈HS (1− 2λ− λ logDθ(p))∇θ logDθ(p) ]
By summing over those samples for which pj ∈ HS , the quantity in the lemma is seen to be equal to the above in expectation.
C ICPC PROBLEM
As a somewhat complicated but illuminating example, consider the first problem of the 2019 International Collegiate Programming Contest (ICPC). At its core, the goal is, given input two matrices P,H ∈ R2×n, to find a pair of permutations σ, τ on {1, 2, . . . , n} such that,
h1σi < h2τi and p1σi ≤ p1σi+1 and p2τi ≤ p2τi+1 for all i
The permutations σ and τ are to be applied to the two rows of P , which correspond to prices. When permuted, the prices are to be non-decreasing. If there are duplicate values in P , this constraint leaves flexibility in σ and τ which must be chosen so as to that when heights, encoded in H , are also permuted by σ and τ , the first row is greater than the second coordinate-wise. Figure 9 shows the problem in English and our PSAT version.
Note that there are a few important differences:
Input parsing. First, the problem like many requires reading and parsing the data from a file rather than receiving it as lists of integers. However, much prior work has successfully shown how to automatically parse such data (see the survey by Gulwani et al., 2017), so we focus on the algorithmic questions.
Solvability. Second, the problem posed in the contest asks users to print “impossible” if the problem has no solution. For such problems, the corresponding puzzle is unsolvable – there simply aren’t any valid input which makes it return True. If one wanted to have an objective question where one could verify that an answer of “impossible” was correct, the puzzle would need some sort of proof that the problem is unsolvable which is much more difficult. However, the uncertainty of knowing whether an unsolved puzzle is solvable is not critical for optimization. For example, imagine a solver takes a test with 1,000 problems and knows with certainty that one solved 300 of them and didn’t solve the remaining 700. Now, suppose changing a parameter of the system makes it so that it solves an additional 20 problems. This increase in objective is desirable, and even though a humans may be frustrated and even slower to solve a problem without knowing whether or not it is solvable, a computer algorithm will experience no such frustration or slowdown.
Solving instances. For people, there is a difference between submitting a program that solves a given problem with varied inputs and just submitting solutions for a number of given inputs – the latter may be easier as they may identify peculiarities in the inputs which make them easier to solve (or they may even solve them by hand). However, for computers this distinction is not crucial. Given a program
that is only capable of solving individual instances, that same program can itself be submitted as a solution to the general problem. This distinction is similar to a classification problem in which a binary classifier must be returned versus one in which unlabeled test data is provided and the labels alone must be submitted. Similar techniques are often used for computers to solve these two closely-related problems if the test set is sufficiently large.

heading: D EXPERIMENTS: MAXIMIZING TIME

text: Table 1 shows the results for different generators when optimized for logtime instead of the reward function discussed in Equation (1).