Search and Planning Under Incomplete Information
A Study Using Bridge Card Play
Published on 7. December 2011
Book
Paperback/Softback
XIX, 340 pages
978-1-4471-1596-0 (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
Softcover reprint of the original 1st ed. 1998
Language
English
Place of publication
London
United Kingdom
Target group
Professional and scholarly
Research
Illustrations
XIX, 340 p.
Dimensions
Height: 244 mm
Width: 156 mm
Thickness: 20 mm
Weight
576 gr
ISBN-13
978-1-4471-1596-0 (9781447115960)
DOI
10.1007/978-1-4471-1594-6
Schweitzer Classification
Other editions
Additional editions
Book
07/1998
Springer
€85.55
Article exhausted; check different version
Content
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.