Search and Planning Under Incomplete Information

1 Introduction.- 1.1 Motivation.- 1.2 Aims.- 1.3 Achievements.- 1.4 Bridge.- 1.5 The Rest of this Book.- 2 A Good Deal of Bridge Literature.- 2.1 Computer Bidders.- 2.2 Computer Defender/Declarers.- 2.3 Miscellaneous Bridge Research.- 2.4 Commercial Bridge Programs.- 2.5 Comparison with Other Games.- 2.6 Summary.- 3 Planning Literature.- 3.1 Plan-space and State-space.- 3.2 Planning Systems.- 3.3 Refinement Search.- 3.4 Plan-space Planning as Refinement Search.- 3.5 Summary.- 4 The Bridge Search Space Size.- 4.1 Preliminary Estimates.- 4.2 Shape.- 4.3 Tightening the Bounds.- 4.4 Double-dummy Bridge.- 4.5 Summary.- 5 Proof-planning: Solving Independent Goals Using Tactics and Methods.- 5.1 Proof-Planning.- 5.2 Bridge Tactics.- 5.3 Representing the Defenders’ Plays.- 5.4 Methods.- 5.5 Finesse’s Planning Algorithm.- 5.6 Interface Issues.- 5.7 Searching with Histories.- 5.8 Summary.- 6 Search in Games with Incomplete Information.- 6.1 Introduction.- 6.2 Game Theory Background.- 6.3 Equilibrium Points in Bridge.- 6.4 Exhaustive Strategy Minimisation.- 6.5 Bridge Architectures Based on Standard Minimaxing.- 6.6 Repeated Minimaxing Fails: Strategy Fusion.- 6.7 Non-locality (Repeated Minimaxing Fails Again).- 6.8 Summary.- 7 Identifying The Best Strategy: Tackling Non-locality.- 7.1 Representing Information Qualitatively.- 7.2 Parameterised Local Evaluation Functions.- 7.3 Application to Bridge: The Interpreter Algorithm.- 7.4 Representing Uncertainty in Bridge.- 7.5 Coping with Non-locality in Bridge.- 7.6 Summary.- 8 Interleaving Plans with Dependencies.- 8.1 The Problem.- 8.2 Resource Profiles.- 8.3 Refinement Search.- 8.4 Goal Selection and Establisher Selection.- 8.5 Auxiliary Constraints and Book-keeping.- 8.6 A Solution Constructor Function for Bridge.- 8.7 Summary.-9 Re-introducing Neglected Actions.- 9.1 The Simple Squeeze.- 9.2 Re-introducing Squeeze Plays into the Interleaver.- 9.3 Performance and Discussion.- 9.4 Summary.- 10 Overall Architecture.- 10.1 A Simple Planning Loop.- 10.2 A Partial Ordering on Profiles.- 10.3 Forming ‘Best-Case’ Profiles.- 10.4 An Improved Overall Architecture.- 10.5 Summary.- 11 Results.- 11.1 Single-suit Plans.- 11.2 Global Plans.- 11.3 Summary.- 12 Conclusions.- 12.1 Contributions.- 12.2 Further Work.- Appendices.- A An Overview of Commercial Computer Bridge Systems.- A.1 BBC Bridge Companion.- A.2 Bidding.- A.3 Bridge Buff.- A.4 Bridge Champion with Omar Sharif.- A.5 Bridge for Windows.- A.6 Bridge Master.- A.7 Bridge Master.- A.8 BridgeMate.- A.9 Bridge Olympiad.- A.10 Bridge Pal.- A.11 Grand Slam.- A.12 Meadowlark Bridge.- A.13 Microbridge.- A.14 Micro Bridge.- A.15 Micro Bridge Companion.- A.16 Omar Sharif’s Bridge.- A.17 Oxford Bridge 4.- A.18 Positronic Bridge.- A.19 Saitek Industries.- B Generating Explanations.- B.1 Review.- B.2 A Basic Solution.- B.2.1 Pattern Matching.- B.3 Further Improvements.- B.3.1 Voids, Singletons and Doubletons.- B.3.4 Intermediate Logical Forms.- B.4 Technical Supplement.- B.5 Summary.- C Further Examples.- C.1 Summary of Performance.- C.2 Individual Examples.- D User Manual.- D.1 Implementation Overview.- D.2 Initialising the System.- D.3 Setting up Play Situations.- D.4 Basic Interface.- D.5 Interface Predicates to Planners.- D.6 Interface Predicates to Bidding System.- D.7 Notes on Implementation.- D.8 Saved Games.- E Code.- E.1 Ftp Instructions.- E.2 Getting Started.