Problem SolvingSolve this maze at your leisure.Views of Problem solvingProblem solving as searchSolving most games involves searchProblem Solving is a search problemSearch spaces can be largeWhat if the search space is too large?Trial and ErrorHill ClimbingSlide 11Means-end analysisSetting subgoals in means-end analysisGoal Stack: last in, first outWhat about ill-defined problems?Six stick problemFunctional FixednessSlide 18Slide 19Duncker’s problem: support a candle on a doorWhy people get stuck solving problemsKohler (1945): monkey and banana problem.InsightEvidence for concept of insight: Metcalfe and Weibe (1987) experimentResults (1)Results (2)ExpertiseDeveloping ExpertiseSee anything unusual?Chess StudiesChase & Simon (1973)Number of pieces successfully recalled by chess players after the first study of a chess board.Conclusion from Chase & Simon (1973)What makes an expert an expert?10 year ruleWhat about talent?Difference between good and exceptional musicians is related to the amount of practiceProblem SolvingSolve this maze at your leisure.Start at phil’s house. At first, you can only make right turns through the maze. Each time you cross the red zigzag sign (under Carl’s auto repair), the direction in which you turn changes. So, after the first time you cross that sign, you can then only make left turns; after the second time, you switch back to right turns only, etc. How can Carl’s auto repair be reached?•Well-defined problems–Much studied in AI–Requires search–Domain general heuristics for solving problems•What about ill-defined problems?–No real mechanisms for dealing with these–The problem may be solved suddenly by ‘seeing’ the problem differently –Often requires developing a suitable representationViews of Problem solvingProblem solving as searchINITIAL STATE GOAL STATEINITIAL STATEGOAL STATE?Play the game: http://www.mazeworks.com/hanoi/Solving most games involves search •Examples:–Cannibals and missionaries:http://www.learn4good.com/games/puzzle/boat.htm–Theseus and the Minotaur:http://www.logicmazes.com/theseus.html–More special mazeshttp://www.logicmazes.com/Problem Solving is a search problemInitial stateGoalstateSearch SpaceSolutionSearch spaces can be large#DISCS #STATES3 33 = 274 34 = 815 35 = 2436 36 = 729What if the search space is too large?•It is not possible to enumerate the entire search space for many well-defined problems.•We must use heuristics –Not guaranteed to work but easy to implement–Example heuristics•Trial and error•Hill climbing•Means-end analysisTrial and Error•Edward L. Thorndike (1874-1949) found that many animals search by trial and error(aka random search)•Found that cats in a “puzzle box” (see left) initially behaved impulsively and apparently random. •After many trials in puzzle box, solution time decreases.In order to escape the animal has to perform three different actions: press a pedal, pull on a string, and push a bar up or downHill Climbing•Find some measure of the distance between your present state and the end state.–Take a step in the direction that most reduces that distanceHill Climbing•Might lead to suboptimal solutions: local maximumfence3 4 5FOOD5 41 2 302311 2 11Means-end analysis•Set up a goal•Look for a difference between current state and goal or subgoal state•Find an operator to reduce this difference. One operator is the setting of a new subgoal•Apply operator•Repeat until final goal is achievedSetting subgoals in means-end analysis•Painting your house (GOAL 1)•Apply paint (SUBGOAL 2)•Need paint and brush (SUBGOAL 3)•Go to hardware store (SUBGOAL 4)•Went to hardware store (SUBGOAL 4)•Got paint and brush (SUBGOAL 3)•Apply paint (SUBGOAL 2)•Paint the house (GOAL 1)G1Goal Stack: last in, first outG1G2G1G2G3G1G2G3G4Push Goal 1on StackG1G2G3G4Push Goal 2on StackPush Goal 3on StackPush Goal 4on StackSolved Goal 4:Pop-off StackWhat about ill-defined problems?•No real mechanisms for dealing with these•According to Gestalt psychologists, the problem may be solved suddenly by ‘seeing’ the problem differently •Often requires developing a suitable representationSix stick problemWrong solution:With these six sticks:Make four equilateral triangles:Answer:Functional FixednessMaier’s (1931) two-string problemOnly 39% of subjects were able to see solution within 10 minutesFrom: Adams (1976). Conceptual blockbusters.Duncker’s problem: support a candle on a doorA box of tacks, some matches, and a candleWhy people get stuck solving problems•Functional Fixedness–Subjects who utilize an object for a particular function will have more trouble in a problem-solving situation that requires a new and dissimilar function for the object.–Young children suffer less from functional fixedness Less experience might help...Kohler (1945): monkey and banana problem.Kohler observed that chimpanzees appeared to have an insight into the problem before solving itInsight•Seemingly sudden understanding of a problem•Often involves conceptualizing a problem in a totally different way (e.g. six stick problem, overcoming functional fixedness)•How can we distinguish between problems requiring insight and problems requiring noninsightful problem solving?Evidence for concept of insight: Metcalfe and Weibe (1987) experiment1) Noninsight problem (algebra): -factor 16y^2 – 40yz + 25z^22) Insight problem (nonroutine):•A prisoner was attempting escape from a tower. He found in his cell a rope which was half long enough to permit him to reach the ground safely. He divided the rope in half and tied the two parts together and escaped. How could he have done this?Results (1)•First result: subjects “feelings of knowing” (beforehand) only predicted eventual success of solving the problem for noninsight problems.•At 15 seconds intervals, ss. rated how close they felt to solving the problem:1=cold (nowhere close to solution) ….7=hot (problem is virtually solved)Results (2)Number of times a particular warmth rating was givenExpertiseDeveloping Expertise•What are differences between novices and experts?•How to become an expert?See anything unusual?•Experts need only a few seconds to see what is wrong (or what isn’t)•Experts perceive large meaningful patterns in their domain(collapse of the upper right lobe, upper left in picture) (normal)Chess Studies•De Groot (1965)•Instructed 5 chess grandmasters to think out