Simon And Newell Human Problem Solving Theory 1971

---
license: Apache-2.0
name: simon-and-newell-human-problem-solving-theory-1971
description: Foundational cognitive science theory of human problem-solving through heuristic search in problem spaces
category: Research & Academic
tags:
  - problem-solving
  - cognitive-science
  - search
  - heuristics
  - theory
---

# SKILL: Human Problem Solving Theory

## Core Insight
Intelligence = examining the right 50 nodes out of 10^100, not searching faster through millions. This skill provides L3 decision frameworks for when and how to apply selective search principles to agent systems.

## DECISION POINTS

### Agent Performance Diagnosis
```
IF agent examines >1000 nodes for problems with <10^6 states
├── THEN selectivity problem
├── Fix: Extract structural information for heuristics
└── NOT: Add more compute power

IF same problem solved easily with different representation
├── THEN problem space construction issue  
├── Fix: Test alternative state representations
└── NOT: Optimize search within current representation

IF agent succeeds on similar problems but fails here
├── Check: Does current problem space expose task structure?
├── If NO: Reconstruct problem space
└── If YES: Refine heuristics for this structure

IF resource usage grows unbounded
├── THEN strategy exceeds architectural constraints
├── Fix: Switch to constraint-compatible strategy
└── Example: Progressive deepening for limited memory
```

### Search Strategy Selection
```
Working Memory: LIMITED + Backtracking: CHEAP
└── Use progressive deepening (depth-first with backtrack)

Working Memory: ABUNDANT + State comparison: NEEDED  
└── Use scan-and-search (breadth-first)

Task Structure Assessment:
├── Clear goal state + Measurable progress → Means-ends analysis
├── Hard constraints + Dependencies → Most-constrained-first
├── Recognizable patterns + Action opportunities → Opportunistic planning
└── Multiple valid paths + Resource limits → Constraint satisfaction
```

### Heuristic Design Decision Tree
```
Task has well-defined goal state?
├── YES: Extract differences between current and goal
│   ├── Differences are measurable? → Means-ends analysis
│   └── Differences are qualitative? → Pattern-based selection
└── NO: Use structural constraints
    ├── Hard constraints exist? → Most-constrained-first
    ├── Known patterns exist? → Production rules (condition→action)
    └── Multiple operators available? → Extract structural ranking info
```

## FAILURE MODES

### Speed Fallacy Anti-Pattern
**Detection Rule**: If solution involves "faster hardware" or "more parallelism" for search problems
**Symptoms**: Agent examines thousands of nodes, performance scales with compute
**Diagnosis**: Missing selectivity through structural information extraction
**Fix**: Analyze task structure for exploitable patterns, constraints, or goal-distance measures

### Universal Strategy Trap
**Detection Rule**: If same search approach (usually means-ends) applied to all problems
**Symptoms**: Works on clear-goal problems, fails on constraint satisfaction or opportunistic tasks  
**Diagnosis**: Strategy-task structure mismatch
**Fix**: Match search pattern to task structure—means-ends for goal reduction, constraint propagation for CSPs, pattern recognition for opportunistic planning

### Representation Blindness
**Detection Rule**: If optimization effort goes to search algorithms before testing representations
**Symptoms**: Extensive tuning yields marginal gains, "obviously easy" problems remain hard
**Diagnosis**: Wrong problem space for task structure
**Fix**: Test 2-3 alternative state representations before optimizing search within any one

### Architecture-Strategy Mismatch  
**Detection Rule**: If strategy requires more working memory than system provides
**Symptoms**: Thrashing, exponential memory growth, inability to backtrack effectively
**Diagnosis**: Importing unlimited-memory strategies to constrained systems
**Fix**: Use progressive deepening for memory-limited, scan-and-search only when memory permits full state tracking

### Construction Neglect Pattern
**Detection Rule**: If problem space treated as "given" without explicit construction phase
**Symptoms**: Agent can't initialize on new tasks, representation seems arbitrary
**Diagnosis**: No systematic problem space construction from task environment
**Fix**: Allocate design effort to representation selection proportional to search difficulty

## WORKED EXAMPLES

### Example 1: Cryptarithmetic Problem (SEND + MORE = MONEY)
**Novice Approach**: 
- Problem space: All possible letter-to-digit assignments (10! = 3.6M states)
- Search: Try random assignments, check arithmetic
- Result: Examines thousands of invalid states

**Expert Application**:
- **Problem space construction**: States are partial assignments of letters to digits with constraints
- **Structural information extraction**: 
  - Column constraints (C1 + C2 + carry_in = result + 10*carry_out)
  - Most-constrained variable first (S and M have only 2 valid values each)
  - Constraint propagation (if S=9, then M=1, eliminating other M values)
- **Decision point**: Use constraint satisfaction, not means-ends (no single goal state)
- **Search strategy**: Most-constrained-first with forward checking
- **Result**: Solution in 50-100 nodes by eliminating impossible branches early

**Key Insight**: Same task, different problem space. Constraint-based representation exposes structure that assignment-enumeration hides.

### Example 2: Tower of Hanoi (5 disks)
**Representation Comparison**:

**Poor representation**: States as disk positions [(disk1_peg, disk2_peg, ...)]
- 3^5 = 243 possible states, most invalid (large on small)
- No structural guidance for move selection
- Search examines invalid configurations

**Good representation**: States as peg configurations with implicit size ordering
- Only ~100 valid states (legal configurations)
- Move constraints embedded in representation
- Goal-distance heuristic: count disks not on target peg

**Decision Logic Applied**:
1. **Task structure**: Clear goal state (all disks on peg 3), subgoal decomposition possible
2. **Strategy selection**: Means-ends analysis appropriate (goal-directed with measurable progress)
3. **Heuristic design**: Difference = number of disks not on target peg
4. **Architecture match**: Recursive subgoaling fits human memory limits through problem decomposition

**Search Performance**: Expert finds solution in 31 moves (optimal) by examining ~50 nodes. Poor representation might examine 1000+ nodes and find suboptimal 100-move solution.

### Example 3: Medical Diagnosis Task
**Task Environment**: Patient symptoms → disease identification → treatment

**Problem Space Construction Decision**:
- **Option A**: States = all possible diseases, operators = diagnostic tests
- **Option B**: States = symptom clusters, operators = differential diagnosis rules
- **Option C**: States = causal pathways, operators = evidence accumulation

**Expert Choice**: Hybrid approach
- **Initial search**: Pattern recognition (symptoms → candidate diseases)
- **Refinement search**: Most-constrained-first (tests that differentiate top candidates)
- **Architecture consideration**: Use production rules for fast pattern matching, deeper search only for ambiguous cases

**Decision Framework Applied**:
1. **Recognizable patterns exist** → Use opportunistic planning (symptom patterns trigger disease hypotheses)
2. **Hard constraints exist** → Most-constrained-first for disambiguation (tests that rule out maximum candidates)
3. **Memory limits binding** → Progressive deepening with early pattern termination

## QUALITY GATES

- [ ] Problem space representation chosen explicitly (not assumed/inherited)
- [ ] Search strategy matches task structure (goal-directed vs. constraint-based vs. opportunistic)
- [ ] Heuristics extract information from problem structure (not generic distance metrics)
- [ ] Architecture constraints respected (memory limits, processing speed, backtracking costs)
- [ ] Selectivity demonstrated (examines <1% of theoretical search space for non-trivial problems)
- [ ] Failure modes have detection rules (can diagnose wrong representation vs. weak heuristics)
- [ ] Alternative representations tested when performance poor
- [ ] Structural information sources identified (constraints, patterns, goal-distances, dependencies)
- [ ] Strategy switches based on task structure assessment
- [ ] Problem space construction process explicit (not ad-hoc representation choice)

## NOT-FOR Boundaries

**Do NOT use this skill for**:
- **Pure optimization problems**: Use mathematical optimization theory instead
- **Machine learning model selection**: Use statistical learning theory
- **Parallel algorithm design**: Use concurrent systems theory  
- **Database query optimization**: Use relational algebra optimization
- **Real-time control systems**: Use control theory

**Delegation Rules**:
- For numerical optimization with continuous variables → Use `convex-optimization` or `metaheuristics`
- For pattern recognition with training data → Use `machine-learning-fundamentals`
- For concurrent search across multiple agents → Use `distributed-systems-coordination`
- For problems with probabilistic uncertainty → Use `decision-theory-under-uncertainty`
- For reactive systems with timing constraints → Use `real-time-systems-design`

**Boundary Markers**:
- Problem has discrete states and operators (not continuous optimization)
- Search space is large but finite (not infinite optimization landscapes)
- Solution quality depends on path/sequence (not just final state)
- Human-level intelligence provides useful benchmarks (not superhuman performance requirements)