Computers in Chess : Solving Inexact Search Problems

Much water has flowed over the dam since this book went to press in Moscow. One might expect that PIONEER would have made substantial advances-unfortunately it has not. There are reasons: the difficulty of the problem, the disenchantment of the mathematicians (because of the delays and drawing out of the work), and principally the insufficiency and some­ times complete lack of machine time. The general method used by PIONEER to solve complex multidimen­ sional search problems had already been formulated at that time. It was supposed that the successful completion of the chess program PIONEER-l would provide a sufficient validation for the method. We did not succeed in completing it. But, unexpectedly, PIONEER's method obtained a different kind of validation. Since our group of mathematicians works at the Institute for Electroen­ ergy, we were invited to solve some energy-related problems and were assigned the task of constructing a program that would plan the recondi­ tioning of the equipment in power stations-initially for one month. Until then, the technicians had been preparing such plans without the aid of computers. Although the chess program was not complete even after ten years, the program PIONEER-2 for computing the monthly repair schedule for the Interconnected Power System of Russian Central was completed in a few months. In mid-October of 1980 a medium-speed computer constructed the plan in 40 seconds. When, at the end of the month, the mathematician A.

1 The General Statement.- Definition of an Inexact Task.- Inexact Tasks and Control Systems.- Two Methods for Solving Inexact Problems.- The Goal of the Game and the Scoring Function.- Goal and Prognosis (The Optimal Variation).- Multi-level Control Systems.- Types of Multi-level Systems.- Advantages of the General Goal.- The Method for Connecting the Optimal Variations of the Components for Types C and E Regimes.- Computer Programs and Humans.- The Expansion of Artifical Intelligence.- 2 Methods for Limiting the Search Tree.- Truncation.- The Goal of an Inexact Game.- The Scoring Function.- Breaking Off a Variation.- The Pruning of Branches.- The Horizon.- Two Trees: The Mathematical Model (MM).- The Stratification of the System.- Three General Limitation Principles.- Improving the Results of a Search.- 3 The Search for a Solution and Historical Experience.- The Search for a Solution by Association.- The Handbook Method of Searching.- 4 An Example of the Solution of an Inexact Problem (Chess).- A. The Search for a Move in an Original Situation.- The Truncated Search Tree.- The Goal of the Inexact Game in Chess.- The Scoring Function: Two Components.- Breaking Off a Variation and Suspension of Play.- The Horizon.- Chess as a Three-Level System.- The First Level—A Piece with a Trajectory.- The Second Level—A Field of Play.- The Third Level—The Ensemble of All Fields (MM).- The Search Tree and the Minimax Procedure.- The Technique for Defining Trajectories.- The Technique for Forming Fields.- The Positional Component of the Scoring Function.- Priorities for Including in the Search Those Pieces and Fields that Take Part in the Play.- The Inclusion of a Field in the Play.- The Repetition of Moves at a Node.- The Depth of a Search and the Inclusion of Fields in It.- The Pruning of Branches.- Three States of a Field (The Active Mathematical Model).- Keeping the MM in Mind at a Terminal Node.- A Technical Question.- B. The Use of Historical Experience.- The Library of Openings.- The Library of Middle Games.- The Endgame Library.- 5 Three Endgame Studies (An Experiment).- 6 The Second World Championship.- KAISSA-CHESS 4.6.- Conclusions.- Appendix 1.- Fields of Play (by B. M. Stilman).- 1. The Formation of Fields and the Search Within Them.- 1.1. The Concept of a Field.- 1.2. The Search Procedure in the Initial Position.- 1.3. The Formation of Fields During the Search—An Example.- 1.4. Formation of a Field.- 1.5. Storage of Information about Sheaves of Trajectories in Computer Memory. Linked Lists.- 1.6. Information on the Trajectories of a Field.- 1.8. Computing the Length of a Denial Trajectory.- 1.9. Correction of the Sighting Method.- 1.10. The Pseudosearch.- 1.11. The Extent of the Climb Up a Branch in the Pseudosearch.- 1.14. Freezing a Trajectory for Lack of a Connection to an Active One.- 1.15. Criteria for Freezing.- 1.16. The Algorithm for Freezing.- 1.18. Trajectory and Field.- 2. The Choice of Moves in an Ensemble of Fields (The Mathematical Model).- 2.1. The Goal of the Game and the Ending of a Variation.- 2.2. The Criteria for Breaking Off a Variation in the Search.- 2.3. Testing the Criteria for Ending a Variation.- 2.4. Pruning Branches by the Minimax Principle. On the Branch-and-Bound Method.- 2.5. Pruning Branches by the Worst Case Method.- 2.6. Priority of Moves in a Search.- 2.7. Analysis of the Trajectories of a Sheaf for Inclusion in the Search.- 2.8. Analysis of Trajectories for Forking.- 2.9. Retreat and Deblockade.- 2.10. Pruning in the Presence of Branching in a Sheaf of Trajectories.- 2.11. The Structure of the Search Tree.- 2.12. A New Content of Known Procedures.- Appendix 2 The Positional Estimate and Assignment of Priorities (by M. A. Tsfasman and B. M. Stilman).- Appendix 3 The Endgame Library in PIONEER (Using Historical Experience by the Handbook Method and the Outreach Method) (by A. D. YUDIN).- 3.1. Introduction.- 3.2. Formulation of the Problem.- 3.3. Configurations.- 3.4. The Boundary Effect. Decomposition Formulae.- 3.5. Symmetries.- 3.6. The Structure of the Library. Classes. Coding of the Information.- 3.7. Organization of the Information in the Form of Two-Dimensional Tables with Subordination of Entries.- 3.8. The Algorithm for Using the Endgame Library (The Search for Exact Coincidence).- 3.9. Examples of the Operation of the Subroutine for Using the Endgame Library.- 3.10. Outreach for a Library Position.- 3.11. The Search for Nearby Positions.- 3.12. Filter with Respect to the Pawn Structure.- 3.13. The “One Color-Different Color” Filter.- 3.14. Filters Within a Set of Positions.- 3.15. Finding a Group of Neighboring Positions.- 3.16. Implementation of the Outreach Method. Anti-outreach.- 3.17. Entry from the Move-Search Routine.- 3.18. Outreach and Exact Coincidence.- 3.19. The Potential for Wide Use of Library Rules in PIONEER.- 3.20. The Breakoff Criterion Based on the Rule of the Square.- 3.21. Conclusion.- Appendix An Associative Library of Fragments (by A. I. Reznitsky and A. D. Yudin).- References.- Glossary of Terms.- Index of Notation.