Human and Machine Problem Solving

1 Human and Machine Problem Solving: Toward a Comparative Cognitive Science.- 1. Introduction.- 2. Problem Solving.- 2.1. Problems.- 2.2. Solving.- 3. Perspectives.- 3.1. Psychological Perspective.- 3.2. Machine Perspective.- 3.3. Interaction of Human and Machine Perspectives.- 4. Some Issues.- 5. References.- 2 Nonadversary Problem Solving by Machine.- 1. Introduction.- 1.1. Problem-Solving Systems.- 1.2. State Space Search and Problem Reduction.- 1.3. Blind Search and Heuristic Search.- 1.4. Graphs and Trees.- 2. State Space Representation.- 2.1. The Graph Traverser.- 2.2. Blind Search.- 2.3. Heuristic Search.- 3. Problem Reduction Representation: And/or Graphs.- 3.1. Blind Search.- 3.2. Heuristic Search.- 3.3. Means/Ends Analysis.- 4. Planning.- 4.1. Theorem-Proving Approaches.- 4.2. sTRips-like Systems.- 4.3. Hierarchical and Nonlinear Planners.- 5. Conclusions.- 6. References.- 3 Human Nonadversary Problem Solving.- 1. Introduction.- 1.1. Definitions.- 1.2. Types of Problems.- 1.3. Analysis of Problem Solving.- 2. Constraints on a Model of Human Nonadversary Problem Solving.- 2.1. Humans Systematically Distort the Problem To Be Consistent with Prior Knowledge.- 2.2. Humans Focus on Inappropriate Aspects of the Problem.- 2.3. Humans Change the Problem Representation during Problem Solving.- 2.4. Humans Apply Procedures Rigidly and Inappropriately.- 2.5. Humans Are Intuitive and Insightful and Creative.- 2.6. Humans Let Their Beliefs Guide Their Approach to Problem Solving.- 3. Conclusion.- 4. References.- 4 Adversary Problem Solving by Machine.- 1. Introduction.- 2. Search Techniques for Two-Person Games.- 3. Minimaxing with an Evaluation Function.- 4. The Alpha-Beta Algorithm.- 5. Refinements of the Basic Alpha-Beta Rule.- 6. Theoretical Analyses of Alpha-Beta and Its Variants.- 7. Other Problem-Independent Adversary Search Methods.- 8. Selective Search, Evaluation Functions, and Quiescence.- 9. A Short History of Game-Playing Programs.- 10. Example of Implementation Method for Chess.- 11. Knowledge-Based Selective Search.- 12. Exact Play in Chess Endgames.- 13. Other Nonprobabilistic Games.- 14. Games of Imperfect Information, Game Theory.- 15. Conclusion-Likely Future Trends.- 16. References.- 17. Further Reading.- 5 Adversary Problem Solving by Humans.- 1. Adversary Games.- 1.1. Games Research.- 1.2. Memory and Skill.- 1.3. The Need for Alternative Explanations.- 2. Dealing with the Adversary.- 2.1. Predicting Opponent Moves.- 2.2. The Opponent's Intentions.- 3. Characteristics of the Search Process.- 3.1. Problem Behavior Graphs.- 3.2. Progress through the Tree.- 4. Plans and Knowledge.- 4.1. Using Plans.- 4.2. Using Knowledge.- 4.3. Knowledge and Skill.- 5. Evaluation Functions.- 5.1. Material and Positional Evaluations.- 5.2. Judgment and Skill.- 5.3. Comparison with Computers.- 6. Projecting Ahead.- 6.1. Following One Line of Moves.- 6.2. Anticipation through a Tree.- 6.3. Human Minimaxing.- 7. Humans versus Computers.- 7.1. Knowledge, Search, and Evaluation.- 7.2. Experimental Comparisons.- 7.3. Playing against Computers.- 8. Overview.- 8.1. Unresolved Issues.- 8.2. Conclusions.- 9. References.- 6 Machine Expertise.- 1. The Automation of Problem Solving-Continuing a Tradition.- 2. Problem-Solving Knowledge Representation.- 3. The Nature of Expert Knowledge.- 4. Knowledge Representation.- 5. Problems with the Traditional Approach.- 6. Architectures for Representing Machine Expertise.- 6.1. The Production System Approach.- 6.2. Multiple Experts and Mixed Reasoning Strategies.- 6.3. The Set-Covering Approach (or Frame Abduction).- 6.4. Multiple Paradigms.- 7. The Rule-Based Approach-mycin, prospector, and xcon.- 7.1. The mycin System.- 7.2. The xcon System (r1).- 7.3. The prospector System.- 8. The Blackboard Approach (hearsay).- 9. The Set-Covering Approach (Frame Abduction).- 9.1. The Inference Mechanism.- 9.2. System D-An Example.- 9.3. The internist System.- 10. Multiple Paradigm Approaches.- 10.1. The compass System.- 11. Expert System Shells.- 11.1. The Shell Concept.- 11.2. What Does a Shell Provide?.- 11.3. What Sorts of Shells Exist?.- 12. Recent Developments.- 12.1. Nonmonotonic Reasoning.- 12.2. Deep Knowledge.- 12.3. Commonsense Reasoning and Causality.- 12.4. Better Tools.- 13. Conclusions.- 14. References.- 7 Human Expertise.- 1. Introduction.- 2. The Theoretical Framework: Information-Processing Theory of Problem Solving.- 3. The Construction of a Problem Representation.- 4. The Role of Schemata in Problem Solving.- 5. Problem-Solving Strategies.- 5.1. Interaction of Different Problem-Solving Strategies.- 5.2. Switching Problem-Solving Strategy.- 6. The Development of Expertise.- 6.1. Acquisition of Episodic Knowledge Structures.- 6.2. Acquisition of Procedural Knowledge.- 7. Conclusion.- 8. References.- 8 Machine Inference.- 1. Input of Knowledge.- 1.1. Formal Languages.- 1.2. Recognition and Parsing.- 1.3. Translation.- 1.4. Summary of Input of Knowledge.- 2. Machine Inference Based on Logic.- 2.1. Introduction.- 2.2. Classical Propositional Logic.- 2.3. Automatic Inference in Classical Propositional Logic.- 2.4. Summary of Machine Inference Based on Logic.- 3. The Production-Rule-Based Approach to Inference.- 3.1. What Is a Production-Rule-Based System?.- 3.2. Origins of the Production-Rule-Based Approach.- 3.3. Rule Application.- 3.4. Accommodating Uncertainty.- 3.5. Summary of the Production-Rule-Based Approach to Inference.- 4. The Frame-Based Approach to Inference.- 4.1. Some Definitions.- 4.2. Matching.- 4.3. Finding the Best Match.- 4.4. Inference in the Frame-Based Approach.- 4.5. Summary of the Frame-Based Approach to Inference.- 5. The Current Status of Machine Inference.- 5.1. The Status of the Logic-Based Approach to Inference.- 5.2. The Status of the Production-Rule-Based Approach to Inference.- 5.3. The Status of the Frame-Based Approach to Inference.- 5.4. Integration of Techniques from All Three Approaches.- 6. References.- 9 Human Inference.- 1. Introduction.- 1.1. What Is an Inference?.- 1.2. Implicit and Explicit Inferences.- 1.3. Logic and Comprehension.- 2. The Mental Logic Approach.- 2.1. Henle's Argument.- 2.2. Mental Logic and Propositional Reasoning.- 2.3. Other Arguments and Evidence for Mental Logic.- 3. The Mental Models Approach.- 3.1. Simulation by Mental Model.- 3.2. Truth-Functional Reasoning.- 3.3. Propositional Reasoning with Mental Models.- 3.4. Reasoning with Syllogisms.- 4. The Nature of Inference.- 4.1. The Argument from Observation.- 4.2. Analytical Comprehension Revisited.- 4.3. Conclusion.- 5. References.- 10 Machine Learning.- 1. Introduction.- 2. Learning Concepts from Examples: Problem Statement.- 2.1. Concepts as Sets.- 2.2. Description Languages for Objects and Concepts.- 2.3. The Problem of Learning from Examples.- 2.4. Criteria of Success.- 3. Learning Concepts by Induction: A Detailed Example.- 4. Learning Decision Trees and Coping with Noise.- 4.1. The TDIDT Family of Learning Programs.- 4.2. Tree Pruning in TDIDT Programs.- 4.3. How Pruning Affects Accuracy and Transparency of Decision Trees.- 5. Other Approaches to Learning and Bibliographical Remarks.- 6. References.- 11 Human Learning.- 1. Introduction.- 2. Schemata, Scripts, and Frames.- 3. Amnesia.- 4. Retrieval from Long-Term Memory.- 5. Concept Learning.- 6. Conclusions.- 7. References.- 12 Problem Solving by Human-Machine Interaction.- 1. Problem Solving for the Real World.- 1.1. What Is Problem Solving?.- 1.2. The Importance of Problem Solving.- 1.3. How Can Computers Help People Solve Problems?.- 2. Problem Solving Reconsidered from a Human Factors Perspective.- 2.1. The Importance of the Task.- 2.2. The Importance of the User.- 2.3. The Importance of the Interface.- 2.4. Recommendations for Human-Computer Problem Solving.- 3. Stages of the Problem-Solving Process.- 3.1. Problem Finding.- 3.2. Problem Formulation.- 3.3. Idea Generation.- 3.4. Idea Evaluation.- 3.5. Solution Match with Goal.- 3.6. Solution Match with Environment.- 3.7. Idea Integration.- 3.8. Acceptance or Modification.- 3.9. Planning for Implementation.- 3.10. Measuring the Outcome.- 3.11. Evaluating the Process.- 4. Human-Computer Problem Solving: Cases.- 4.1. Speech Synthesis as an Interface Problem.- 4.2. The Computer as an Active Communications Medium.- 5. A Retrospective Example.- 5.1. Designing a Strategy for Human Factors.- 5.2. The Actual Use of Computers in Solving This Problem.- 5.3. The Potential for Human-Computer Problem Solving.- 6. Summary and Conclusions.- 7. References.- 8. Further Reading.- 13 Human and Machine Problem Solving: A Comparative Overview.- 1. Introduction.- 2. Nonadversary Problems.- 3. Adversary Problems.- 4. Expertise.- 5. Inference.- 6. Learning.- 7. Solving Problems by Human-Computer Interaction.- 8. Concluding Comments.- 9. References.- Author Index.