ADAPTIVE GENERATION OF PROGRAMMING PUZZLES
Authors: Ashwin Kalyan
Oleksandr Polozov
Adam Tauman Kalai
Venue:  (2020)
Keywords: program synthesis
reasoning
math problems

Abstract: AI today is far from being able to write complex programs. What type of problems
would be best for computers to learn to program, and how should such problems
be generated? To answer the first question, we suggest programming puzzles as a
domain for teaching computers programming. A programming puzzle consists of a
short program for a Boolean function f(x) and the goal is, given the source code, to
find an input that makes f return True. Puzzles are objective in that one can easily
test the correctness of a given solution x by seeing whether it satisfies f, unlike the
most common representations for program synthesis: given input-output pairs or an
English problem description, the correctness of a given solution is not determined
and is debatable. To address the second question of automatic puzzle generation,
we suggest a GAN-like generation algorithm called “Troublemaker” which can
generate puzzles targeted at any given puzzle-solver. The main innovation is that it
adapts to one or more given puzzle-solvers: rather than generating a single dataset
of puzzles, Tro

Under review as a conference paper at ICLR 2020
ADAPTIVE GENERATION OF PROGRAMMING PUZZLES
Anonymous authors
Paper under double-blind review
ABSTRACT
Al today is far from being able 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 short program for 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 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 single dataset of puzzles at random, it generates a diverse set of puzzles that are difficult for the solver. In our experiments, Troublemaker learns generate challenging problems for a variety of sate-of-tthear puzzlc-solving techniques.
INTRODUCTION
Computers still perform worse than humans at elementary programming and mathematical reasoning problems, let alone the Al grand challenge of designing, analyzing, and implementing sophisticated algorithmms. For example, many symbolic mathematical software packages fail to solve n²" 10 100000 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 programmingg problems 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-66
(Barrett 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 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.'
In summary, to advance artificial reasoning, the ideal programming problem representation should be:
Objective: a candidate solution ought be unambiguously validated as 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 casily 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.
As a better standard for evaluating and advancing artificial reasoning, we propose Programming Puzzles. In puzzle, given the source code of function f in a fixed programming language (e.g. Python), the goal is to find an input æ such that f(x) returns Truc.
Programming Puzzles
After creating NAPS (Zavershynskyi et al., 2018), a "Natural Programming Synthesis" dataset of program- ming contest problems with English descriptions and input-output examples, one of the authors later conceded that "MI., specifically natural language understanding, is not there yet." (Polosukhin, 2018)

---

Under review as a conference paper at ICLR 2020
def (n: int, prefix=123456789) find an integer whose square begins with 123456789 return str (n=n) .tt.nn)stttttsiiii. (str (prefix))
def (S: Set [intl, 0=11010010); # return (110 for i in $))
find set S of powers of 10 summing to 11010010
def (s: str):
find a string with 1,000 As but no two consecutive As return socut ("A") =1000 and s. count (*AA")==4
def (x: List [Boclean)):
solve a classic Boolean SAT CNF formula
return (x10) or x111 and (not x x11] or not x x12]]
def (m: int, n- n=109876543211 return m and
find nontrivial integer of 1098765432/
Figure 1: Sample programming puzzles with valid answers 111111111 (Python: int ( (9)) )
S {1,4, 6,7, 7), s = a concatenation of 1000 copies of "AB" (Python: ==000==1000) x = [True, True, Falsel, and
7. Problems range from easy hard unsolvable.
As Figure 1 illustrates, short puzzles can capture extremely difficult problems such as factoring or subset-sum as well easy questions such as list reversal or solving (æ + 1) == 100 100 for r. Importantly, such puzzles are objective a candidate solution can easily be evaluated for correctness.
Not all programming problems can be nicely defined puzzles. In some problems, writing the puzzle 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 constitute the complexity class N.P. which contains P' problems such shortest-path as well as hard problems such as factoring and finding a neural network with a sufficiently low training loss.
definitions
Troublemaker Our second main contribution a "Troublemaker" algorithm that automatically generates puzzles in 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 specific discovered weakness). Automatic problem generation has been applied train program synthesis systems (Balog et al., 2016; Christakopoulou & Kalai, 2018) and in numerous related domains such mathematical problems (Saxton al., 2019) and IQ tests (Barrett al., 2018). However, these problems were generated non- adaptivelyy often via random sampling. In this work, we use host of sfate-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 given grammar that would be hard for given solver. The search process is made adaptive by guiding it with trained neural network. The network 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 training progresses.
This paper introduces (1) programming puzzles, a class of objective problems that can be used to evaluate and improve the reasoning ability of existing Al 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 neural and symbolic solvers. We focus on adaptive problem generation and establishing the puzzle domain suitable for teaching machines how to program, leaving the improvements of puzzle solving techniques to future work.
Contributions
evaluate our puzzle generation
lftte-of-hhe-rt
2 RELATED WORK
Program Synthesis The prior work 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 Fi. yi where the goal is to find a "natural" function f such that f(x) W:-
2

---

Under review as a conference paper at ICLR 2020
This representation is subjective the issue is not that there 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 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 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 Christakopoulon & Kalai (2018), which inspired this paper. They consider a specification that is itself a program that takes a whole prollem-solvingg program as input. The specification program then generates 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.
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 constant program that satisfies this specification. In the programming languages community, the intent is often defined by a formal specificution 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 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 al.. 2019) has noted that such randomly generated datasets often fail to capture important properties of the desired program distribution, and thus result in biased program synthesizer. Our Troublemaker framework allows adapting the dataset to the evaluation metric of a particular synthesizer.
As mentioned in Section 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 given puzzle solver. As such, its main goal to evaluate the solver and set an adaptive milestone to facilitate Al progress. However, a similar technique can be used to adaptively generate 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, teacher agent and a student agent engage in self- 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 ad- versarial 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 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.
3 PROBLEM GENERATION AS A ZERO-SUM GAME
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 E P computes
3

---

Under review as a conference paper at ICLR 2020
Boolean function p : X' { for some set X, and each solver S E S computes a function S:P P. - X. Problem p is said to be easy for S if p(S(p)) = T and hard for S otherwise. The set S experiments have time budget B by wrapping
captures the resource constraints on solvers (e.g.. 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 solvability.
The Problem-gend -eneerattnnn game is a two-player zero-sum game between a Generator that chooses an arbitrary distribution D ((P) over P. where A(T) denotes the set of probability distributions over set T, and a Learning Solver who chooses S E 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)) BBppD(D(rr S, D)}, where, r is reward function and D(p) is the probability of generating problem p.
[M( log, D(p)) A1 00
i(((sp)) + if p(S()) = T.
rp. S. D)
The reward is parameterized by À E [0. 1] which offers a trade-off: at X = 0, any hard problem carns the Generator reward of 1, while at À = 1 the reward is the expected negative log- ligleieli over hard problems. The reward function may seem peculiar at first since it depends not only on problem's 's hardness but also its probability of being generated. At X 0 the reward does not account for the diversity of the distribution of problems-agtne agginst any solver S a generator could maximize with the distribution that always outputs single hard problem p E S. yet we want D generate diverse hard problems. To account for diversity, the reward therefore depends on D as well. As one varies À from to one expects the fraction of hard problems decrease but the entropy of the hard problems to increase, measure of greater diversity.
3.1 STATIC SOLVER
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)) + T} 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) (D) S. Hs, then (D, S) = A (D). where H (D) is the entropy of distribution D. Entropy is standard notion of diversity of a distribution, though other notions may be used.
Lemma 1. For any X (0, 1] and any solver S with [Hs 2 3 hard problems, the uniform distribu- tion Uits over Hs uniquely maximizes the Generator's s payoff ((MHss))) = - X + X Algg |Hs)
All proofs are deferred to Appendix B. In practice, of course the Generator may not find this uniform distribution but H&| 2 2"((S)) remains a lower bound for whatever D is found.
3.2 LEARNING SOLVER
Next, consider an adaptive solver that can tailor its choice of S E 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 game, this is somewhat confusing as mixed strategies for the
themselves. In the Generator are distributions over distributions of problems in A(A(P)), and mixed strategies for the solver are distributions over solvers in A(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 "pure strategy", single distribution D' E (DD over problems rather than a distribution over distributions. Nontheless, there may be multiple optimal strategies for the Learning Solver.
Theorem 1. For any set and (0, 1), as long as each solver S fails on at least |Hsl 2 3 problems, there is unique distribution D* that achieves the value of the zero-sum Problem-gente generation game.
In particular, D' is simply the distribution that maximizes J(D) minses vDD,S) S). As mentioned, 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*.
4

---

Under review as a conference paper at ICLR 2020
The Troublemaker algorithm for finding parameters for the generator distribution. If learning solver cannot accommodate weights, subsampling can be used to simulate weights.
Algorithm 1:
Input:
sample size number of steps N, step size function that generates samples for any given Da, differentiable function that computes log-pni log-probabilities for Da and either: (a) fixed solver S' or, (b) Learning Solver that maps weighted set of problems to solver S.
Choose 0, E θ
for f- to N do
Create a problems sample Pi1, P........ by independent draws from Do.
if S is a fixed solver then St 5
else feed problems p. with weights wij = 1 - x - A log Da, (pi)) on problem Pij into the Learning Solver and let S; be its output. (In practice, the parameters of S be used as warm start.)
Ug + the set of sample problems that S; failed solve
Update by summing over problems that S; doesn't 't solve:
0,+1- 0; + 2 peu, (1 2λ- X log Do, (p)) Va log (p)(p)
end
return generator parameters ON
3.3 TROUBLEMAKER ALGORITHM FOR SOLVING THE PROBLEM-GENERATION GAME
To find the distribution D" one may maximize J(D) = minses v(D, S), which concave in D:
Observation The function (DD = minses v(D,)) S) concave in D.
Hence, as concave function, can be theoretically maximized to within arbitrary precision, using the standard gradient-projectio ascent, namely:
Choose D1 to be uniform over P
for i + 1 to N do
Find solver S; to minimize (Di;,
Update D4+1 = llA(P) (D; + v/V De
end
Here we have used the fact that a gradient of a minimum of functions is the gradient of whichever function minimal at that point. Note that minimizing v v(D,, S) over S E is equivalent to finding the solver that solves the most problems where each problem has non-neeative weight - À log (p).. Also, 117 denotes the projection on to the closest point in convex Euclidean set T, in this case the closest probability distribution. This mradient-projectinn method is known to converge at a rate that depends on N and step size 17 > 0 (e.g. Zinkevich, 2003). However, this again is theoretical algorithm assuming that one represent arbitrary distribution and can evaluate vS, D) over all problems, which is computationally intractable. In practice, one represents a Generator Do by parameters 0 E R. and optimizes them w.r.t. the samples drawn from the generator.
Wp =
The TM algorithm, described in Algorithm 1, follows the alternating gradient ascent procedure above procedure except that, using sampling approximation similar 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 Dy and computing gradients V. log Do(p) of log pre--rrbbbiiiiss as is standard for sequential neural generation procedures. One also needs to be able to compute best solver response to a distribution of problems, which a Learning Solver can also approximate from problems sampled from Dg. The analysis showing how the update in Step 4 is an unbiased estimate the gradient of is given in Lemma Appendix
4 TROUBLEMAKER GENERATING PROGRAMMING PUZZLES
Having derived general form of the problem generation problem, turn attention to its instantiation in the Troublemaker framework. In this section, we first define problem representation for puzzles used by generator Dg. and then describe the architecture of the trainable generator.
5

---

Under review as a conference paper at ICLR 2020
bool equation ==
term term
float term =
0.1
term term
0.2
term term
0.05
term term
0.05
term /
term
0.15
float (term
0)
// evaluates 1.0 if equality holds, 0.0 otherwise
0.05
0.05
0.05
0.0 // constants
0.3
x: // variable
Figure 2:
An excerpt from our Probabilistic Context Free Grammar (PCFG) that defines a family of puzzles with doating-point solutions. Each production rule is |annotated with weight, automatically learned by the generator (see main text).
We assume a language of programs I. defined as a Context Free Grammar (CFG). Each abstract syntax tree (AST) T describes a programming puzzle problem Pr : - [T, as defined in Section 3. When I' is clear from context, write p instead of pr. For the purpose of this paper, assume interesting problems are hard puzzles whose solution a solver cannot obtain within the given time budget i.e. t Lime(SS Pr) B. However, our framework is agnostic 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 expres- siveness, sampling programs from L uniformly at random is not useful as it may generate overly simple problems even vnsolvable ones like x² -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,
4.1 GENERATION MODEL.
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. display 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 factorizes into its constituent production rules:
Pr(pt) = Pr(r)
rET
which constructively corresponds standard sampling procedure that builds the AST T one production at time by sampling a production to expand each nonterminal using its corresponding weight as an unnormalized probability. Further, mentioned, we aim to produce hard problems, iee. maximize log t me,S 7') or, in general, any reward that fits into the framework described in Section The weights 0 of the probabilistic grammar can be learned using Algorithm 1, since sampling, computing the likelioeldoood and its gradient are straightforward.
Neural Guided Generation While this strategy allows us to tailor generation for given solver, only tunes global preferences (i.e. encourages certain rules always) as opposed to context-dependent changes (i.e. rule A preferred conditioned on the current partial AST). To enable finer-grained control over the generation process, we propose more versatile generation strategy that conditions prediction of a rule on the rules in partial AST produced so far. The context-dependent conditioning model is parameterized as trainable neural network, whose parameters guide the generation process.
Let 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 the pre-order traversal). The neural-guided generation strategy parameterized the probability of the puzzle as
Pr(pr) II Pr(r. Tet)
where r, is the production rule expanded in the AST T at the 4h timestep. The probability Pr(r, T2e) is, in turn, parameterized as a neural network that takes as input partial tree embedding o(T<e) and outputs distribution of probabilities for each syntactically valid production rule.

---

Under review as a conference paper at ICLR 2020
1hs == rhe p+*lhs p**rhs lhs rhs + p+lhs == p+rhs
1hs rhs 1hs+*p rhs**p
lhs rhs + p+lhs p+rhs
Figure 3: Tree rewrite rules for float puzzles. Here p also term from the grammar in Figure 2.
We consider two state- tfte-of-theeart approaches to parameterize the tree embedding model ø. The first parameterization a naive baseline encoding a traversal of the tree Ter 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). 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- linear modulations, achieving state-of-the-ard performance on a range of graph tasks like node classification.
4.2 COMPLEX AND SOLVABLE PUZZLES
Generating Solvable Programs In order to generate solvable puzzles, we use domain-speeific knowledge to convert a puzzle sampled from I. to a solvable one. To continue with the float- puzzle example, we first select random solution zg. Then given an equation a(x) = b(x) where both a, 6 E Lierns can convert it to solvable puzzle at zo by modifying the program to be a(x)= = b(x) where = a(zo)= b(zg).
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 intermediate step. For instance, in the case of our f -puzzee problems, exponentiating both sides of the equation is good example of chaining while preserving the solvability, 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 rules R: L that transform an existing AST to another AST in the language. For the example of float-puzzle Fig. 3 provides bank rrwe-rewrite rules that can be used to produce complex solvable puzzles.
This approach is sufficiently general to apply to other domains such as i int- -uzzleee or set-puzzles. For example, consider the sub-set sum problem find set S 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.
4.3 TRAINABLE SOLVERS
Finally, while the Troublemaker framework as presented in Algorithm I 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 of the puzzle pr given some embedding of the puzzle (T). In the case of structured outputs (like sets), the solver sequentially outputs elements along with stop token to signal the end of generation.
Synthesis Solver (SS): This solver is similar to the neural generator given grammar L along with bank of useful constants, it constructs solution J as constant expression in the grammar. The construction procedure is similar to puzzle generation at each timestep f, it uses an encoding of the puzzle (TT) and the current partial expression to select the next production rule to expand in the expression. Notably, while the generator emits the puzzle Pr using an and-to-end differentiable LSTM, we found that synthesis of solutions ø 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 DeepCoder (Balog et al., 2016) and NGDS (Kalyan et al., 2018).
7

---

Under review as a conference paper at ICLR 2020
ang teward) 100 gucates
ma Sowwang 1000 guzzlee
and 1100 punziie
prob
6-
prob
prob guided
250
500 iterations
750 1000
1250
250
500
750
1000
1250
20
40
100
100
iteraaions
iterations
100
Figure 4: For the static solvers (Grid Solver, Enumerative and Sympy respectively). note that the reward achieved by both the probabilistic the neural-guide approach increases time. Owing to its better expressivity and ability to model context, the guided approach latches on to the weakenesses of the solver faster than the probabilistic approach.
In both solvers, the puzzle embedding model (T") is GNN-FiLM network, parameterized identically to the generator's 's embedding model (Section 4.1).
EXPERIMENTS
In this section, we present results for the TroubleMaker approach 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 Appendix A.
Puzzle Generators As discussed earlier, we study both probabilistic grammar based and neural- guided problem generators. Further, in the grammars used, we allow copy operations i.e. that can copy a node of type 7 from the partial tree generated so far opposed to generating a tree from LxT where NT is of type r. The introduction of this operator helps the puzzle generator produce recursive structure (e.g. 10 x² 0) desirable quality that often results in interesting reasoning patterns.
As discussed in Sec. 1.1, both generators are trained using Algorithm 1. Unless otherwise mentioned, all the solvers capped to run within time limit of 0.1s. Similarly, the size (# rules) of the puzzles limited to maximum of 20 and cannot exceed a depth of 10. Recall the definition the reward function (Eq. I) ideally, 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 satisfying solution based comparisons. Unlike other solvers, solution is passed off as correct if the equation holds within a specified tolerance. In our experiments, 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 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 specified tolerance this check is performed only if the solver returns solution.
Enumerative Solver (ES): Given grammar to generate the solution, this solver performs enumera- tive search find satisfying solution. For the sake of simplicity, we provide the solver with the same grammar used to generate puzzle, albeit without the ability to produce variables. Apart from the constants already present 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
guide the search process conditioned the puzzle, 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.
8

---

Under review as a conference paper at ICLR 2020
We also consider 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 rule. In both cases, the generator samples from the probability distribution produced on the set of rules (or rewrite rules).
Training Details As mentioned
2000
before, the generators are trained by maximizing for the reward Eq. (1).
The trainable solver guides the gen- eration process exactly like the gen- erator and is also trained via RE- INFORCE 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 gener- optimized using Adam (Kingma & Ba, 2014)
600
100
garbae) meddon
cancort
100
500
1000 generater
100
ators, when trainable,
with learning rate of 10 All the
LSTM networks use hidden size of and all GNN-FiLB networks use 3 propagation steps and node repre- sentation size of 64.
p100
p100 quited
guceed
Results In terms of achieving higher reward values (see Fig. 4) and thus, producing more unsolv- able problems
100
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.
1000
250
000
000
860
p-0:
550
0-0
Figure 5: Number of unsolved and valid puzzles generated for each of the static solvers (Grid Solver, Enumerative, and Sympy respectively). While both the pCFG based and neural- guided generators find more "hard" puzzles over time, the guided solver saturates much higher value.
In the of learnable solvers, both the pCFG based and the guided solvers are trained for erations and each iteration ~ 2000 puzzles are sampled from the generator. From Figure 6, we see that the generator always position to find more "hard"problenn" problems for the learning solver likely because of building the guided solvers on top the enumerative solvers. From qualitative examples presented in Figure one can 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 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).
100 it-
200
700
glidel
glided
200
600
200
100
Figure 6: (Left) This figure shows the number of problems solved by the solver at each iteration - for every "iteration" of TM, both the generator and solver are updated. (Right) This figure shows the number of puzzles unsolved per 1000 generations. Critically, note that this and the previous plot are "offset" by an iteration ie. the generator produces hard problems for the previously updated solver.

---

Under review as a conference paper at ICLR 2020
grid solver:
(2, abs (math. sin (math. cos (math. leg (abs (math, (math. (x)())))))(()))))))))))))
(2. ** (I. + -0. 00.4849143300 95472)
(math. sin matth.inn(a ** math.pi) ( ((x + 2.
**
math.pi)
0
enumerative solver:
(-x ** 2.) - (xx + o. 0.01653257550549251 ** 2.) ==
(7. ** abs (math. cos (math. sin
- (7. * (x
5.8165676846602548)
==
sympy solver:
(6. ** ((x ** abs (x)) ** x) - (6. ** (9. --8.00115300111155) = ((((8. 4.) + 2.) -8.) 7.) ((((8. ** 4.) 2.) + -8.) ** (1
float (math. log (math. (math. log (x)) == x)) 7.0)) ==
learnable solver:
(5. (math.log (x) / ).)) - (5. + ((1. / abs (-x) - 17577770005777311111
0 #iteration=10
( (2. x) math.pi) (( (math cos cos
x) -39. 69986689933022463
math.pi) 0 #iteration=90
Figure 7: Qualitative examples of puzzles that achieve a high reward (sampled from top- 100 of 1000 generations) for each static solver. each of these cases, a neural-guides generator has been used to produce the puzzles. Each solver, has its specific weakness can be seen from the examples for example, excessive use of non-linear functions such as log, sin, and cos, make a problem hard for the grid solver. Similarly, simple exponentiation (here, via rewrite rules that simply exponentiate both sides) as the ability to compute the square root, etc. of a number is not provided in the grammar. Further, the generator games the sympy solver by frequently using exponentiation and absolute value. Note that the solver fails to solve some of the generator problems due to the time constraint, a fact exploited by the generator. As the learning solver built on top of the enumerative solver, the generator in our setting overpowers the solver by producing puzzles with frequent exponentiations.
CONCLUSIONS
This work suggests new type of problem called Programming Puzzles and a framework for generating large set of hard problems that can both expose the weaknesses of existing solvers and which can be used in 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 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 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, also seek a large set of problems. Hence the reward of the puzzle generator takes into account the probability of each generated puzzle, which 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 shown to converge. While our system 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.
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. arXiv preprint
2017.
Rajeev Alur, Rishabh Singh, Dana Fisman, and Armando Solar-Lezama. Search-based program synthesis. Communications of the ACM, 61(12):84-95 2018.
10

---

Under review as a conference paper at ICLR 2020
Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. arXiv preprint wrXiv:161..01999 2016.
David GT Barrett, Felix Hill, Adam Santoro, Ari S Morcos, and Timothy Lillicrap. Measuring abstract reasoning in neural networks, arXiv preprint arXiv:1807.04222 2018.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference machine learning, pp. 41-48. ACM, 2009.
James Bornholt and Emina Torlak. Synthesizing memory models from framework sketches and litmus tests. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, pp. 467-481, New York, NY, USA, 2017. ACM. ISBN doi: 10.1145/3062341.33 330263333
978- --100444988---8
Mare Brockschmidt. GNN-FiLM: Graph neural networks with feature-wise linear modulation. arXiv preprint arXiv: 12/92, 2019.
Mare Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. arXiv preprint arXiv: (.civ:8805.08444 08490, 2018.
François Chollet. The measure of intelligence. arXiv preprint arXiv:1911.015444 2019.
Konstantina Christakopoulou and Adam Tauman Kalai. Glass-box program synthesis: A machine learning approach. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018. 2018.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. arXiv preprint 1rXiv:1703.07469. 2017.
Ishan Durugkar and Peter Stone. Adversarial goal generation for intrinsic motivation. In Thirty- Second AAAI Conference on Artificial Intelligence, 2018.
Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- fion processing systems, pp. 2672-2680, 2014.
Alex Graves, Mare Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. In Proceedings of the 34th International Conference on Srariing-Volume
Machine Learning- Volume 70, pp. 1311-1320. JMLR. org, 2017.
Sumit Gulwani, William R Harris, and Rishabh Singh. Spreadshect data manipulation using examples. Communications of the ACM, 5508)977-005, 2012
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Foundations and Trends@ in Programming Languages, 4(1-2):1-119, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-guided deductive search for real-time program synthesis from examples. arXiv preprint arXiv:1804.01 186, 2018
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
Percy Liang. Learning executable semantic parsers for natural language understanding. Commun. ACM, 69697667776, August 2016. ISSN 0001-0782, doi: 10. 145/2866568.
Zohar Manna and Richard Waldinger. A deductive approach program synthesis. TOPLAS, 2(1):
90-121, 1980.
Roger B Myerson. Game theory. Harvard university press, 2013.

---

Under review as a conference paper at ICLR 2020
J Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295-3200 1928.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. arXiv preprint 1rXiv:1611.01833 2016.
Lerrel Pinto, James Davidson, Rabul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2817-2826. JMLR. org, 2017.
Illia Polosukhin. aEAR.i NEAR Protocol, August 2018. https: https:/neerpxotooo.cco blog/neer-aa ai near protocol// /, Last accessed on 2019-09-24.
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. CoRR, abs//194.01157, 2019.
abs/1904 01557.
Richard Shin, Neel Kant, Kavi Gupta, Chris Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song. Synthetic datasets for neural program synthesis. In International Conference on Learning Representations, 2019.
Edward A Silver. On mathematical problem posing. For the learning of mathematics, 14(1):19-28. 1994.
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. In International Conference on Learning Representations, 2018.
Ronald J Williams. Simple statistical cradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-22) 1992.
/as///b//////a 807. 031 68. Maksym Zavershynskyi, Alexander Skidanov, and Illia Polosukhin. NAPS: natural program synthesis
dataset. CoRR, abs//807.00161 03 2018. URL http:
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 928-936, 2003.
12

---

Under review as a conference paper at ICLR 2020
(a) bool equation term term float term = term term term term
term term | term term term -term
float (ferm -- 0) I float (term !- 0)
(term) | log (term) sin (term)
copy float () copies a afflaut node from current partial free
0.0 1 1. 2. 3. 4. 5. 6. 7. 8. 9.
π e // variable
(b) bool equalion int in term I sum (term) inl set term = Ø
} | {int_term, int_terrm {int_fed int_ferm,, int_term, int int_term) union (term, term) intersection (term, term)
difference (ferm, term)
(e for e in range(int sangejinttterm term, int [et_]t
int int ferm = // integer grammar
Figure 8: Grammars that define programming puzzles with (a) float and (b) int -et solutions.
A GRAMMARS AND FREE-REWRITH RULES
We present the full grammars for the flatt and int-sen 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.
B THEORETICAL ANALYSIS AND PROOFS
Proof of Lemma 1. We can write the payoff as
S) = Σ D(p)
+1 (1-N)= - E D(p) log D(p).
PE
pEHs
Clearly (1 (1- () 11-3 A is maximized and only all problems generated are hard for The second term Epens D(p) log D(p), is the entropy which is known be maximized over the uniform distribution but is only summed over Hlg. For example, if X and [Ht]] 1, then the uniform distribution over Hs would have a payoff of O because it has 0 entropy. and a distribution which put probability 1/c on this hard problem and probability 1 1/c 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 Hg: by the striet concavity of the log function there is unique optimum and by symmetry it is uniform. Finally, since -2 log z increasing up to z 1/e > 1/3, this quantity is only increasing in D(Hs) as long as there are least three hard problems, so the optimum is D(Hs) 1 only over hard problems. O
To prove Theorem 1, a key technical observation is that v (D.S) -
(og
1 A) is concave in D, which follows from the concavity of =z log z for [o, 1]. Hence, as zero-sum game with actions e ((P) and S E 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 candomize-instedd
it could achieve an expected payoff 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 A), is:
ePP.S)
max min S). DEA(P) SES
fact, this optimization has a unique optimal distribution D (which is not true 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,
(P,SS) = max min vf (D) min max [Es=u[v(D, (v)D))) pEA(S) DEA(P)
DEA(P) SES
13

---

Under review as a conference paper at ICLR 2020
where have simplified again by the concavity of in D in not consider distributions over D's. In particular, let μe be any minimizer of the right-hand-sidd above. Any maximum D of minses () must also maximize Esw (o(D, S)], which we denote by,
v(D, = Es [v( = - p (tp P Hs)) log2 D(p)) +1 2).
It remains argue that there is unique D which maximizes the above quantity. Note that
- -log2 (p)) 2 0 so the quantity in the right-hand parentheses is non-negative. Also note that (pp) log ((p) is increasing for 0 I D(p) 1/c.
Let hp = ((p I E Hs}) be the hardness of p. the probability a random solver from μ doesn't t solve p. We do this by arguing, first, that any maximal D" would assign D(p)
any "easy" puzzle 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 hy > 0 and at least one of these call it p' must have D(p') < 1/3 < 1/e and hy > O. Hence, v(D, ,²) could be increased by taking an amount of probability (p) assigned to a p with hp = 0 and moving
p'.
Therefore D distributes its probability only over p with hp > 0. Since -D(p) log D(p) is strictly concave and D(p) is trivially concave (as a linear function), the quantity of interest,
Σ p=h.20
hpp log, D(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 VS Hs {r') }. == 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(y/) 1/e and spread the remaining 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 VoJ( from samples.
Lemma 2. For any Generator Da and solver S, over random iid samples PI...., p from D.
1 2 Alog Do(;)) Do(p;)
S) = Ept D
Again, Pj E Hg means that solver S did not solve problem Pj-
Proof. We first compute the gradient of (Dg) with respect A:
(D)(Do) (,
Σ (o(Do(D)ro,ss
Σr(p,s, Do) Dola)
Σ r(p, S, Da) log DD
= [T(p. S, Vo log Dz(p) + (or(p, D.))
In the second-to-last line above, we have used the standard "REINFORCE trick" writing Vf(0) V() log f(f make it writable reward whose gradients may be computed by automatic differentiation, so the approach generalizes to other reward functions.
expectation. Also note that above applies to arbitrary
Now, for our specific reward function defined in Eq. (1), Vor(p, S, Do) = -1 XVo log Do(p), where 1 for proposition P is the indicator function that is if P holds and 0 otherwise. Using this notation, r(p, S, D₂) LpEHs (1 - X - Alog Do(p)). Hence, we have,
V ((D) = Ep-Do [peHH Hy (1 X Alog Do V log Do(p) 1pe XV log Do(p)]
Ep-Do 1pEHs (1 2A Alog Do (p) V log Do(p))
14

---

Under review as a conference paper at ICLR 2020
def score_azulejos (s: List [int), t: List [int],
p1=13, 2, 1, 21, h1=12, 3, 4, 31, p2- 1, 2, 11, h2- [2, 2, 1, 31):
n len (p1)
return
sorted (s) (trted(t) 1ist (zange
and
all (h1 [s [1] [{]]]{{]22[]]]]] for i in range (n)
and all (p][s[[1]](<pp((([HH)) for in range (n-1))
and all (=2 for in range (
Figure 9: ICPC Problem 2019A in English (left) and programming puzzle (right). In the PSAT, p1, p2 are arrays of n prices, hl, h2 are arrays of n heights. The goal to find 8, t, required to be lists of integers in the function specification. They are further tested to be permutations by checking if sorting them yields 1ist (range (n) ) the list of numbers from to n.
By summing over those samples for which P5 Hs, the quantity the lemma is seen to be equal to the above in expectation.
C ICPC PROBLEM
As somewhat complicated but illuminating example, consider the first problem of the 2019 Inter- national Collegiate Programming Contest (ICPC). At its core, the goal is, given input two matrices P, E R22x,, to find a pair of permutations a, 7 on ..., n) such that,
hi; < h2r, and Pio; P1epp and p2r: S P2 for all i
The permutations a and T 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 o 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 few important differences:
Input parsing. First, the problem like many requires reading and parsing the data from file rather than receiving it 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" 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 of proof that the problem is unsolvable which is much more difficult. However, the uncertainty of knowing whether an unsolved puzzle solvable not critical for optimization. For example, imagine solver takes test with 1,000 problems and knows with certainty that one solved 300 of them and didn't 't solve the remaining 700. Now, suppose changing parameter of the system makes it so that it solves an additional 20 problems. This increase in objective is desirable, and even though humans may be frustrated and even slower to solve a problem without knowing whether or not is solvable, a computer algorithm will experience no such frustration slowdown.
Solving instances. For people, there is a difference between submitting program that solves a given problem with varied inputs and just submitting solutions for number of given inputs the latter may be easier as they may identify peculiarities in the inputs which make them casier to solve (or they may even solve them by hand). However, for computers this distinction is not erucial. Given program
15

---

Under review as a conference paper at ICLR 2020
ooat-puzzles
Puzzle Generators
Solvers
Enumerative Solver
Guided Solver
Grid Solver
Sympy
Random Prob
1.21
0.92
1.5
0.05
2.47
1.95
2.22
1.02
Guided
2.78
1.99
2.34
1,45
fnt-puzzles
Random
3,06
2.93
3.78
4.21
Prob 3.22
2.95
3.82
4.33
Guided 3,45
3.15
3.85
4.54
int intt-setpuzzlles
Random
4.12
3.83
Prob
4.33
4.02
Guided
4.51
4.19
Table I: As can be seen from the table, both generators probabilistic grammar based (Prob) and neural guided (Guided) lead to improvements (over randomly sampled puzzles) in the time required for the solvers, with the guided solver showing the highest gains. Note that randomly sampled puzzles can sometimes be unsolvable in which case the solver just times out. Further, all values are measured in seconds and solvers have time bound B
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 binary classifier must be returned versus 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 is sufficiently large.
D EXPERIMENTS: MAXIMIZING TIME
Table I shows the results for different generators when optimized for logt ime instead of the reward function discussed in Equation (1).
16


Reviews:
[{"review_id": "SJgZe8sAYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nAlthough I'm not an expert in this area, I have found this paper well written and easy to follow. The problem is well motivated, and the approach is sensible. As this is a novel problem, the paper also defines their own metric, namely the average time taken to solve the puzzle by given solvers, and the diversity of generated puzzles. It is nice to see that the generator indeed learns to generate puzzles that are significantly harder than random counterparts, while maintaining reasonable diversity. Although I think these are convincing results, my question to the authors is: have you tried or considered other ways of evaluating the generated puzzles? E.g., if you train the guided search solver on the generated puzzles and evaluate it on a random set of puzzles, would you see an improvement? I think this would be interesting to see, which can serve as an alternative evaluation metric.\n\nMy other comments are regarding the experiment section:\n1. It would be useful to provide references to the solvers used, both in the adversarial training phase and the evaluation phase, if there is any.\n2. More details of the training process would also be valuable. E.g., the training time and stability, common failure modes if any.\n\nMinors:\n1. Figure f3 should be s.count(\"A\")==1000 and s.count(\"AA\")==0 \n2. First sentence under Fig 1, one is give -> one is given\n3. Figure 5, f2: 2**(x**2)) == 16 -> 2**(x**2) == 16", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1xQslvMiH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nI found the paper well-written and easy to understand. The methodology to generate programs is convincing. I am not sure time to solve is the best way to measure the complexity of the program, but it seems a reasonable proxy. Did the authors study if the program length is correlated to the time to execute? If the correlation holds, then can complex programs not be created by simply having a bias towards longer programs? That would be a strong baseline to compare against. \n\nI may have missed something, but I understand that only the Guided Solver is trainable. If that is the case, then why do we see increase in solving time for other solvers (Table 1). In only the case of the Guided solver can the generator adaptively increase the complexity of the programs. \n\nOverall, I feel that the paper puts forth an interesting class of programs. But there are some gaps in the evaluation and the baselines. I am also not sure how this class of programs can help advance artificial reasoning. \n\nFeedback:\n- The authors should provide more references to the solvers used in Section 5. \n- The paper ends abruptly. A summary/conclusion would be useful. \n\nI am not an expert in this area, and I am willing to revise my recommendation if the authors can address these issues.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HJgzFWw7qS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe paper is fairly clear overall. There is some repetition in the early parts, so this could be restructured a bit, but these are minor points. A more significant restructuring however, is that this work would benefit from the related work being present the beginning of the work. Since this work is so similar in many ways to previous work I think the overall clarity of the paper would be improved, and the contributions clearer, if the work was better situated with respect to related work.\n\nThe experiments demonstrate that the trainable puzzle generator is able to produce harder (i.e. takes longer time to solve) puzzles than a random or probabilistic generator of the same grammar. While this does show that the program generator is learning something useful, these results are insufficient to show the utility of this approach in any real context. It seems the most interesting solver to assess is a trainable solver. Yet only 1 of the 4  solvers they assess is trainable. I know the authors make a point that they are not putting forward any new solver algorithms. That ok, however, taking existing trainable solvers and assessing how they perform with this guided puzzle generation vs. some other puzzle generation approach is a critical empirical study. Furthermore, it would be helpful to have more discussion of the baseline methods of generating puzzles. When the trainable puzzle solver was originally proposed, how was it trained? Where did the  data come from? How does that compare to this approach. I am not very familiar with this literature, and I imagine this paper would be of interest to folks outside the program synthesis space, so it would be very helpful to better explain this (also we note about related work). There are several additional empirical analysis that could be added to improve this work. For example, for the trainable solver, a plot of (training time) vs (time to solve puzzle) would be interesting. Beyond looking at training time, does a solver trained with the guided puzzle generator end up being a 'better' solver in some way? Are the resulting puzzles harder but still being solved? Is there a way of quantifying the 'hardness' of a puzzle? Perhaps a proxy like size? Then it would be cool to plot (training time) vs (approx puzzle hardness) to demonstrate that . the puzzle generator is really developing a reasonable curriculum.\n\nFinally, there is a bunch of related work that I think is missing. Again, I'm not super familiar with this work, but I think there is a lot of curriculum learning stuff within RL that seems super relevant. Of particular relevance is the Alice/Bob framework from \"Intrinsic motivation and automatic curricula via asymmetric self-play\" seems very similar to the work at hand.  Something that is interesting in the Alice/Bob framework that could be transferred over here is the notion of the generator wanting to make a puzzle hard, but not too hard, i.e. make it just outside the solvers current capabilities. \n\nOverall my assessment is that this paper doesn't quite meet the standard for ICLR. My two major critiques are (1) the related work is seriously lacking making it difficult to situate this work in a broader context. The authors also seem to miss the entire curricular learning literature. (2) The empirical evaluations are lacking. In particular, more thorough analysis of how the generator is behaving, the type of curriculum it learns, and the resulting impact this has on a trainable solver all are missing. Furthermore, more focus on trainable solvers would improve this work. \n\nI'm not an expert in this area so it is possible I misjudged the significance of this work. I'm certainly open to revising my assessment if the authors are able to address (2) in a meaningful way. \n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors introducing programming puzzles as a way to help AI systems learn about reasoning. The authors then propose a GAN-like generation algorithm to generate diverse and difficult puzzles.

This is a very novel problem and the authors have made an interesting submission. However, at least 2 reviewers have raised severe concerns about the work. In particular, the relation to existing work as pointed by R2 was not very clear. Further, the paper was also lacking a strong empirical evaluation of the proposed ideas.  The authors did agree with most of the comments of the reviewers and made changes wherever possible. However, some changes have been pushed to future work or are not feasible right now. 

Based on the above observations, I recommended that the paper cannot be accepted now. The paper has a lot of potential and I would strongly encourage a revised submission addressing the questions/suggestions made by the reviewers.
Decision: Reject