--- 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)