Problem solving Flashcards
What does the Problem Space theory claim?
We analyse problems in terms of search strategies
What are search strategies?
Strategies that involve searching within an abstract problem space
A problem is made up of 3 elements. What are they?
- A starting state (where you are)
- A goal state (where you want to be)
- A set of processes (operators) that transform one state into another
If all 3 elements of a problem can be identified, what type of problem is this?
A well-defined problem
What types of problems can you get?
- Well-defined vs. ill-defined
- Knowledge-rich vs. knowledge-lean
- Adversary vs. non-adversary
What is a well-defined problem?
The start state, goal state & operators in the problem are identifiable
What is a knowledge-rich problem?
The problem requires specific knowledge/skills to solve it
You must access info from LTM/production memory to solve it
The start state, goal state & operators are identifiable
What is a knowledge-lean problem?
The problem can be solved using instructions & general problem-solving skills
What is an adversary problem?
It matters what others do - someone is trying to stop you reaching the goal state
You must overcome the opposition to reach the goal state
Each step towards the goal state is the largest possible move towards the goal state from the current state space
What is a non-adversary problem?
It doesn’t matter what others do - you aren’t being stopped by anyone
Name 3 search strategies.
- Depth-first
- Breadth-first
- Best-first
What does the depth-first search strategy involve?
Going through all alternatives to a move before considering another move
What does the breadth-first search strategy involve?
Working out which move will most likely put you where you want to be
Can use cost analysis (how much it is costing you to do these things & how much you will get back)
What are the problems with using unguided search strategies?
X the n-tile puzzle is hard to solve by exhaustive search
X intelligence problem-solving requires SOME form of guided search
- AI researchers have suggested several forms, but some aren’t compatible with human cognition (e.g. best-first search; require too much memory/too-fast computation)
Why is the n-tile puzzle hard to solve by exhaustive search?
The problem space increases with the number of tiles
n=6x5x4x3x2x1 = 720 possible states for 6-tile puzzle n=9x8x720 = 51,840 possible states for 9-tile puzzle
Why is the n-tile puzzle a ‘limited state space’?
There is a limited number of states that the puzzle can be in
What is difference reduction & what does it involve?
It is a difference of local maxima
You must move away from the goal state to solve the problem
A chicken wants food (in another location) & they must reduce the difference between their current state & the goal state (food)
There is a barrier to the food (a fence) – the chicken pecks it
Who studied chickens in this study?
Why does this problem violate difference reduction?
Kohler (1927)
By pecking the fence, the chicken is only applying difference reduction
The chicken must move away from the goal (food) to get around the barrier –> violates difference reduction
What scenarios can difference reduction be applied to?
- If you are following difference reduction, you climb up the hill & reach the peak (= the goal), & then descend
- If you are following difference reduction, you climb up the hill & reach a peak but not the highest one –> you must go down the hill to go up again to reach the highest peak - this violates difference reduction
What does the Orc problem involve?
There are 3 orcs & 3 hobbits on one side of a river bank
A boat can only take 2 creatures at a time across the bank (one must steer the boat)
Goal = get all 6 creatures to the other side of the bank
Orcs must not outnumber hobbits on either side of the bank
How do you solve the Orc problem? Why do pps tend to make mistakes?
To solve the problem, you must move away from the other side of the bank (= the goal) to pick up more creatures –> this is a backwards step
This is where pps make a mistake - they keep wanting to do difference reduction but it doesn’t solve the puzzle
What does the 9-dot problem involve?
You must connect 9 dots using 4 straight lines, without taking your pen off the paper
Why do people have difficulties with the 9-dot problem?
The dots form a square - has boundaries, so people automatically add rules…
“I have to connect dots without taking my pen off the paper AND I must do it without going outside the confines of the square”
Difficulty to do the 9-dot problem is called…
…maximisation - you are trying to maximise what you get our of your limited number of moves
What are the pps doing wrong in the 9-dot problem?
There is a problem with how they are searching the space (applying a difference reduction principle)
They have a problem with insight
What problem/difficulty does means-end analysis overcome?
The problem of difference reduction
How was means-end analysis introduced?
It was introduced as an AI procedure
Used as a description of human problem-solving alongside the formalisation of Operators as Production/Condition-Action/If-Then rules/Production System
Means-end analysis suggests a way of thinking about operators as…
…production rules
What is the process of means-end analysis?
- Set up a goal/sub-goal
- Look for a difference between your current state & the goal/sub-state (if there is no difference → success)
- Look for an operator that will reduce this difference
- Apply the operator
- Check your new current state → apply 2-4 until the goal is reached
What is the difference between means-end & difference reduction?
The means can (temporarily) become the end
Anderson et al. (1993) found that it takes pps on average ___ seconds to make the first move in the Tower of Hanoi task (move disc A from disc B).
Anderson et al. (1993) found that it takes pps on average 8.95 seconds to make the first move in the Tower of Hanoi task (move disc A from disc B).
Anderson et al. (1993) found that it takes pps on average ___ seconds to make the second move in the Tower of Hanoi task (move disc B from disc C).
Anderson et al. (1993) found that it takes pps on average 2.46 seconds to make the second move in the Tower of Hanoi task (move disc B from disc C).
Why do patients with frontal lobe damage have difficulty on the ToH task?
Have difficulty with problems that involve planning or holding multiple sub-goals in memory
What type of resources does sub-goaling require?
Memory resources (to hold the goals & sub-goals)
Variants of ToH can be devised that require more/less sub-goals to be held in memory to solve the problem.
Who found that patients with frontal lobe damage had particular difficulty with multi-sub-goal versions?
Goel & Grafman (1995)
What type of effect does the water jugs problem show?
What is this effect?
The water jugs problem shows the einstellung effect - this is when you solve a problem in a certain way, even thought more appropriate methods exist
What does the water jugs problem involve?
Pps are told that 3 jugs contain 14, 50 & 11 litres of water - the goal is to end up with 33 litres in each jug
What did Luchins’ (1942) water jugs problem study involve?
Experimental group: given 5 problems that were solvable using a certain method
Control group: given 5 problems that were solvable using many methods
Both groups were given 5 ‘impossible’ problems solvable using Y=A-C
What did Luchins (1942) find in his water jugs problem study?
The control group solved all 5 problems using a direct method
In the experimental group, 55% of the problems were solved using a direct method, 40% were solved using a long method & 5% weren’t solved at all
What did Luchins (1942) conclude from his water jugs problem study?
People learn a way of doing things & keep applying that method, even if it is longer & harder than other methods
What did Luchins (1942) name this phenomenon?
The mechanisation of thought
4 pps in Luchins’ (1942) study had GCSE maths A* - which method did they use?
All used the long method
2 pps failed to solve the ‘impossible’ problems & reverted to a tedious solution
2 pps worked out a direct solution for the ‘impossible’ problems & thereafter used it
