Search and Planning Under Incomplete Information
A Study Using Bridge Card Play
Published on 10. July 1998
Book
Hardback
XIX, 340 pages
978-3-540-76257-7 (ISBN)
Description
This book updates the thesis I produced for my PhD at the Department of Artificial Intelligence of the University of Edinburgh, correcting errors, and improving some of the formatting and readability. Since the original work was completed (early 1996), research has progressed. Most notably, the public profile of AI and game-playing has reached new heights with the feats of the chess computer DEEPER BLUE (which surely uses AI, no matter what IBM would have us believe). Although less heralded, the ability of computers to play Bridge (the main example domain in this book) has also increased. In July of 1997 a world championship for computer Bridge programs was hosted by the American Contract Bridge League in Albuquerque, New Mex ico. This contest was won by a program called Bridge Baron, produced by Great Game Products. Bridge Baron incorporates knowledge-based planning techniques developed by Stephen Smith and Dana Nau [1, 2]. Progress has also been made on the contrasting, more brute-force, approach of sampling the possible card distributions. In particular, Matt Ginsberg has developed a fast double-dummy solver based on partition search [3]. Ginsberg's program fared poorly in the 1997 Bridge championships, but Ginsberg himself reports very promising results [4] on a hard set of complete Bridge deals taken from the Bridge tutoring program Bridge Master.
More details
Series
Edition
1st Edition.
Language
English
Place of publication
London
United Kingdom
Publishing group
Springer Berlin
Target group
College/higher education
Professional and scholarly
Research
Illustrations
156 figures, bibliography
Dimensions
Height: 240 mm
Weight
680 gr
ISBN-13
978-3-540-76257-7 (9783540762577)
DOI
10.1007/978-1-4471-1594-6
Schweitzer Classification
Other editions
Additional editions
E-Book
12/2012
Springer
€96.29
Available for download
Book
12/2011
Springer
€106.99
Shipment within 15-20 days
Content
1 Introduction.- 1.1 Motivation.- 1.2 Aims.- 1.3 Achievements.- 1.4 Bridge.- 1.4.1 The Basic Rules.- 1.4.2 Who Wants to be a Millionaire?.- 1.5 The Rest of this Book.- 2 A Good Deal of Bridge Literature.- 2.1 Computer Bidders.- 2.1.1 The Rule-based Approach.- 2.1.2 Interpreting Other Players' Bids.- 2.1.3 Incorporating Look-ahead.- 2.1.4 COBRA.- 2.2 Computer Defender/Declarers.- 2.2.1 Rule-based Systems.- 2.2.2 Tactics.- 2.2.3 Tackling Card Combinations.- 2.2.4 Double-dummy Programs.- 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.1.1 Plan Representation.- 3.1.2 Search Techniques.- 3.2 Planning Systems.- 3.3 Refinement Search.- 3.3.1 Background.- 3.3.2 Basic Formalisation.- 3.3.3 Brief Discussion.- 3.4 Plan-space Planning as Refinement Search.- 3.4.1 Partial Plan Representation.- 3.4.2 Auxiliary Constraints.- 3.4.3 A General Plan-space Planning Algorithm.- 3.4.4 Applying the Framework to Classical Planning Systems.- 3.5 Summary.- 4 The Bridge Search Space Size.- 4.1 Preliminary Estimates.- 4.2 Shape.- 4.3 Tightening the Bounds.- 4.3.1 Factoring in the Number of Possible Deals.- 4.3.2 The Number of Possible Shapes of a Single Hand.- 4.3.3 The Number of Possible Shapes of the Unseen Hands.- 4.3.4 The Incomplete Information Search Space in Bridge.- 4.4 Double-dummy Bridge.- 4.4.1 The Expected Number of Legal Play Sequences.- 4.4.2 Interpretation.- 4.5 Summary.- 5 Proof-planning: Solving Independent Goals Using Tactics and Methods.- 5.1 Proof-Planning.- 5.2 Bridge Tactics.- 5.2.1 Cashing.- 5.2.2 Finessing.- 5.2.3 Ducking.- 5.2.4 Top Sequences.- 5.2.5 Summary of the Tactic Set.- 5.3 Representing the Defenders' Plays.- 5.3.1 Card Sequences.- 5.3.2 Critical Cards.- 5.4 Methods.- 5.5 Finesse's Planning Algorithm.- 5.5.1 A Planning Example.- 5.6 Interface Issues.- 5.6.1 Tracing the Planner.- 5.7 Searching with Histories.- 5.7.1 General Analysis.- 5.7.2 Performance.- 5.7.3 Memory Management.- 5.8 Summary.- 6 Search in Games with Incomplete Information.- 6.1 Introduction.- 6.2 Game Theory Background.- 6.2.1 The Extensive and the Normal Forms of 2-player Games.- 6.2.2 Minorant and Majorant Games: The Minimax Theorem.- 6.2.3 Pure and Mixed Strategies.- 6.2.4 Preliminarity and Anteriority.- 6.3 Equilibrium Points in Bridge.- 6.3.1 Bridge as a Game of Incomplete Information.- 6.3.2 The Best Defence Model of an Incomplete Information Game.- 6.3.3 Solving the Best Defence Model.- 6.4 Exhaustive Strategy Minimisation.- 6.4.1 The Algorithm.- 6.4.2 An Example.- 6.4.3 Comparison with Standard Minimaxing.- 6.4.4 Possible Worlds.- 6.4.5 The Complexity of Exhaustive Strategy Minimisation.- 6.5 Bridge Architectures Based on Standard Minimaxing.- 6.6 Repeated Minimaxing Fails: Strategy Fusion.- 6.6.1 A Bridge Example.- 6.6.2 Some Practical Consequences.- 6.7 Non-locality (Repeated Minimaxing Fails Again).- 6.7.1 A Bridge Example.- 6.8 Summary.- 7 Identifying The Best Strategy: Tackling Non-locality.- 7.1 Representing Information Qualitatively.- 7.1.1 A One-pass Approach.- 7.1.2 Discussion.- 7.2 Parameterised Local Evaluation Functions.- 7.2.1 Doublethink.- 7.2.2 Oddthink.- 7.2.3 Payoff Reduction.- 7.3 Application to Bridge: The Interpreter Algorithm.- 7.3.1 Action at Leaf Nodes.- 7.3.2 Action at Internal Nodes.- 7.3.3 Lines of Play.- 7.4 Representing Uncertainty in Bridge.- 7.4.1 Binary Strings.- 7.4.2 C-conjunctions.- 7.4.3 Redundancy.- 7.4.4 Subsumption.- 7.4.5 Tidying up.- 7.4.6 Generating Probabilities.- 7.5 Coping with Non-locality in Bridge.- 7.6 Summary.- 8 Interleaving Plans with Dependencies.- 8.1 The Problem.- 8.1.1 Combinatorial Explosion.- 8.1.2 Reasoning about Dependencies: Resources.- 8.1.3 Resources in Bridge: Leads and Entries.- 8.1.4 Coping with an Opposition.- 8.1.5 Problem Summary.- 8.2 Resource Profiles.- 8.2.1 Context-dependency.- 8.2.2 Considering all Possible Worlds.- 8.3 Refinement Search.- 8.3.1 Review.- 8.3.2 Interleaving as Refinement Search.- 8.4 Goal Selection and Establisher Selection.- 8.4.1 Finding a Solution vs Finding the Best Solution.- 8.4.2 Using Probabilities.- 8.4.3 Maintaining the Profiles.- 8.4.4 The Effects of Ordering.- 8.5 Auxiliary Constraints and Book-keeping.- 8.5.1 Partial Order Plan-space Representation.- 8.5.2 To Split or Not to Split?.- 8.5.3 The Effect of an Opposition.- 8.6 A Solution Constructor Function for Bridge.- 8.6.1 A Naïve Approach.- 8.6.2 Utilising an Uncertainty Representation Language.- 8.6.3 Redistributing the Search Burden.- 8.6.4 A State-based Search Alternative.- 8.6.5 Using a Network of Constraints to Guide Interleaving.- 8.7 Summary.- 9 Re-introducing Neglected Actions.- 9.1 The Simple Squeeze.- 9.2 Re-introducing Squeeze Plays into the Interleaver.- 9.2.1 The Need for a Squeeze Tactic.- 9.2.2 A Tailor-made Tactic.- 9.2.3 Carrying Out the Interleaving.- 9.2.4 Constructing a General Method for Simple Squeezes.- 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.2.1 A Modified Planning Loop.- 10.3 Forming 'Best-Case' Profiles.- 10.3.1 A Simple Approach.- 10.3.2 Don't Count Your Chickens.- 10.3.3 Losers.- 10.4 An Improved Overall Architecture.- 10.5 Summary.- 11 Results.- 11.1 Single-suit Plans.- 11.1.1 Basic Performance.- 11.1.2 Comparison Against Bridge Encyclopedia.- 11.1.3 Discovery of Errors.- 11.1.4 Relaxing the Best Defence Model.- 11.2 Global Plans.- 11.3 Summary.- 12 Conclusions.- 12.1 Contributions.- 12.1.1 Search.- 12.1.2 Planning.- 12.1.3 Proof-planning.- 12.1.4 Bridge.- 12.2 Further Work.- 12.2.1 Play Module.- 12.2.2 Incorporating Information from the Bidding.- 12.2.3 A Bridge Tutoring System.- 12.2.4 Extension to Suit Play.- 12.2.5 Adding Inter-suit Methods and Tactics.- 12.2.6 Improving the Top-level Control Structure.- 12.2.7 Making Inferences Based on Opponents' Play Styles.- 12.2.8 Identifying More General Algorithms to Deal with Nonlocality.- 12.2.9 Planning to Discover Information.- 12.2.10 Extension to Mixed Strategies.- 12.2.11 Choosing the Hardest Line of Play to Defend Against.- 12.2.12 Extension to Defender Play.- 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.