Published in the mid-1970s, this research by Gerald A. Goldin and George P. Luger serves as a pivotal bridge between the emerging field of Artificial Intelligence and classical cognitive psychology. The authors investigate how the mathematical "skeleton" of a problem—specifically its state space, symmetries, and subproblem divisions—influences the strategies and paths human solvers take toward a solution.
Theoretical Framework: State Space Algebra
In the 1970s, AI research led by figures like Newell and Simon utilized "state spaces" (graphs representing all possible configurations and legal moves) to develop automated theorem provers. Concurrently, developmental psychologists like Jean Piaget explored "cognitive structures"—the internal rules governing human understanding. Goldin and Luger sought to unify these perspectives by asking if formal mathematical properties could predict human problem-solving behavior.
To achieve this, they employed State Space Algebra. A problem is modeled as a directed graph where nodes represent states and edges represent legal moves. Two key concepts emerge from this formalization:
- Symmetry Groups (Automorphisms): Using group theory, the authors identify "equivalent" states. For instance, in games like Tic-Tac-Toe, rotational symmetry means a corner move is functionally identical regardless of which specific corner is chosen.
- Subproblem Decomposition: The larger state space is divided into "subspaces." In the Tower of Hanoi, solving for a subset of rings constitutes a distinct subspace within the overall four-ring problem.
Experimental Methodology
The study compared human performance on two isomorphic problems—tasks that are mathematically identical but perceptually different:
- The Tower of Hanoi: The classic puzzle involving moving disks between pegs.
- The Tea Ceremony: A social ritual involving a host and guests performing tasks of varying importance, mapped to the same state space as the Tower of Hanoi.
The researchers analyzed the "protocols" (step-by-step move sequences) of 45 adults solving the 4-ring Tower of Hanoi and 21 adults solving the Tea Ceremony.
Cognitive Insights: Symmetry and Subgoals
The authors argue that human "insight" often corresponds to the internalization of a problem's symmetry. When a solver recognizes a symmetry group, they effectively "collapse" a complex state space into a simpler, reduced version. This is analogous to Piaget’s concept of "conservation"—recognizing that certain properties remain invariant despite superficial changes.
Furthermore, solvers tend to navigate the state space in "episodes." A subject might solve a 2-ring subproblem perfectly (using the minimum number of moves) even if they are still struggling with the 4-ring goal. This suggests that humans naturally decompose complex problems into manageable algebraic sub-structures.
Analysis of Results
The data strongly supported the structuralist hypothesis:
- Goal-Directedness: Nearly 100% of subjects exited a subproblem space immediately upon reaching a subgoal, demonstrating high intentionality within subspaces.
- Subproblem Mastery: 86% of subjects exhibited at least one "episode" of perfect navigation through a complex sub-structure.
- Symmetry Exploitation: 52% of subjects utilized "symmetric conjugates"—mirroring a previous strategy on a different part of the problem space after hitting a dead end.
While the problems were mathematically identical, subjects did not always produce congruent paths across both isomorphs. This indicates that the perceptual representation (e.g., physical disks vs. social roles) significantly impacts a human's ability to perceive and exploit the underlying mathematical symmetry.
Conclusion and Future Directions
Goldin and Luger’s work demonstrates that state space algebra is a powerful tool for describing human cognition. However, it also highlights a gap: why are some symmetries easier to perceive than others? Future research in this vein points toward studying transfer effects—how knowledge of a simple problem's structure carries over to more complex versions—and developing AI models that emulate human "structuralist" behaviors rather than relying solely on exhaustive search algorithms.
Summary updated