AISB02

Automated Puzzle Generation: 

Automated Puzzle Generation Simon Colton Universities of Edinburgh and York

Background: 

Background Train journey with Jeremy Gow To meet Herb Simon Puzzle generation rather than problem solving Wrote some puzzles for Jeremy Jeremy kept getting the 'wrong' answer Puzzle generation is a difficult task Reviewer’s comment View puzzles independently of implementation

Some Example Puzzles: 

Some Example Puzzles Which is the odd one out? Hair, triangles, squares, plants, words, trees Answer: triangles (others have roots) Jingle is to corporation as ? Is to politician Campaign, platform, slogan, promises Answer: slogan What is next in the sequence 4, 3, 6, 6, 2, 9 ? Answer: later

Overview of What’s Needed: 

Overview of What’s Needed Structure for puzzles Characterisation of puzzles Puzzles must have single solutions Theory formation helps here Puzzles must be of correct difficulty Methods for disguising the answer

Queendom.com Examples: 

Queendom.com Examples What’s the odd one out? Coconuts, oysters, clams, eggs, walnuts, haddock A: haddock (the others have shells) Hair is to stubble as potatoes are to ? F.fries, sweet potatoes, potato skins, vegetable A. French fries What’s next in the sequence 3, 8, 15, 24, 35? A: 48 (square integers and subtract 1)

A Characterisation of Puzzles: 

A Characterisation of Puzzles Three (of many) types of puzzle are: Odd one out, analogy, next in sequence Have (almost) the same structure: Question statement Set of choices, one of which is answer Solution which is an embedded concept Some tweaking necessary to make a fit Next in sequence puzzles have no choices Analogy puzzles have no solution concept

Solutions to Puzzles: 

Solutions to Puzzles Solution is a single embedded concept Fairly simple and positively stated Which is the odd one out: 4, 9, 8, 36? A: 9 (even numbers), A: 8 (square numbers) Puzzle is unsatisfying if there are two answers Which is the odd one out: 2, 3, 9, 20? A: 9 (it is a square number) Which is the odd one out: 23, 25, 27, 29? A: 27 (others are primes or squares)

The Difficulty of Puzzles: 

The Difficulty of Puzzles Embedded concept is usually not complex Probably in order to ensure single solution Number of possible answers Increases the search space for answer Could make the problem easier Disguising concepts Odd one out: haddock puzzle, they’re all foodstuffs Next in sequence (from queendom): 2, 7, 4, 14, 6? Another concept interleaved (or stuck on)

The HR Program: 

The HR Program Automated theory formation Concepts (ex. andamp; def.), conjectures, proofs Theory is a collection of concepts (in this case) Concept formation via 8 production rules Builds new concepts from old ones Compose,disjunct,exists,forall,match,negate,size,split Complexity of a concept: Number of production rule steps Specialisation concepts important Specialistion of objects of interest (e.g., prime nums)

Extension for Puzzles (General): 

Extension for Puzzles (General) HR generates theory, then builds puzzles Embed each concept, make all puzzles, choose rep. From characterisation of solution: Don’t use negate or disjunct production rules in ATF From single solution: Exhaust theory up to a complexity limit Check for alternative solutions and discard From difficulty consideration Present puzzles in order of conc. complexity, disguise Actively add disguise where possible

Extension for Puzzles (Special): 

Extension for Puzzles (Special) User: chooses the number of possible answers (n) Answers are presented in random order Odd one out: Choose n positive and 1 negative example of spec. conc Check all other concepts for a different solution Next in sequence (only in domain of integers) Embed number type (e.g. primes, 2, 3, 5, 7, ?) Embed function (e.g. number of divisors, 1, 2, 2, 3, ?) Actively disguise by interleaving simple seq. Analogy: A is to B as C is to: D, E, F, G? A, B, C and D share spec. property, E, F and G do not

Experiment 1: Animals: 

Experiment 1: Animals Animals dataset (distributed with Progol) 18 animals (dog, platypus, snake, eagle, etc.) 12 properties (class, homeothermic, eggs, etc.) Theory formation up to comp. limit 5 Compose, exists, forall, match, size, split Asked for all odd one out andamp; analogy puzzles User specifies: 4 answers possible

Animals Results: 

Animals Results 31 puzzles about animals formed Good examples [15] Which is OOO: penguin, ostrich, cat, bat? [31] Eel is to platypus as shark is to snake,eagle,turtle,lizard? Bad example [27] Cat is to dog as eagle is to lizard, eel, ostrich, trout? Observations: Low complexity of concepts, little disguise found Need more examples of animals Conclusion: Single solutions worked OK, but fairly easy to solve

Experiment 2: Integer Sequences: 

Experiment 2: Integer Sequences Integers 1 to 30 provided Addition, multiplication, digits, divisors Compose, exists, match, size, split Theory formed up to complexity 4 Disguise simple concepts (comp. andlt; 3) By interleaving other simple concepts All next in sequence puzzles asked for User specifies: 6 terms of the sequence given

Sequences Results: 

Sequences Results 24 next in sequence puzzles generated Good examples: [2] 4, 3, 6, 6, 2, 9, ? [numdiv, 27, mult. of 3] [3] 21, 3, 24, 6, 27, 9, ? [mult 3, mult 3] [10] 21, 22, 24, 25, 26, 28, ? [digit is a div] Bad examples: [20] 6, 0, 2, 0, 4, 0, ? [# even divisors of 24, …] [22] 11, 12, 12, 13, 13, 14, ? Observations Functions should start earlier on number line Embedded concepts are in general too complex

Remarks about Creativity: 

Remarks about Creativity Setter: creative act is finding concept/examples Solver: creative act is finding the answer/solution Having a single solution: Want the solver to be P-creative, not H-creative Difference between answer and solution IQ tests: interested in answer, not solution More will come to light after field testing Comments very welcome

Conclusions and Future Work: 

Conclusions and Future Work Characterisation of puzzles Single pos. simp. solution, difficulty (disguise) Puzzle generation can be automated Results not stunning, but still preliminary Puzzle generation needs improvement Also needs hand crafting of input files More answers/questions about puzzle solver/setter creativity After a field test of HR’s puzzles