Search and Planning Under Incomplete Information: A Study Using Bridge Card Play - gebrauchtes Buch

EAN (ISBN-13): 9783540762577
ISBN (ISBN-10): 3540762574
Gebundene Ausgabe
Erscheinungsjahr: 1998
Herausgeber: Springer

Buch in der Datenbank seit 2017-06-01T01:56:08+02:00 (Berlin)
Detailseite zuletzt geändert am 2024-02-04T02:40:45+01:00 (Berlin)
ISBN/EAN: 3540762574

ISBN - alternative Schreibweisen:
3-540-76257-4, 978-3-540-76257-7
Alternative Schreibweisen und verwandte Suchbegriffe:
Titel des Buches: bridge, search play

---

Daten vom Verlag:

Autor/in: Ian Frank
Titel: Distinguished Dissertations; Search and Planning Under Incomplete Information - A Study Using Bridge Card Play
Verlag: Springer; Springer Berlin
340 Seiten
Erscheinungsjahr: 1998-07-10
London; GB
Gewicht: 0,680 kg
Sprache: Englisch
85,55 € (DE)
87,95 € (AT)
106,60 CHF (CH)
Not available, publisher indicates OP

BB; Book; Hardcover, Softcover / Informatik, EDV/Informatik; Algorithmen und Datenstrukturen; Verstehen; Pattern Matching; uncertainty; computer science; game theory; search algorithm; incomplete information; algorithms; B; Algorithm Analysis and Problem Complexity; Computer Science; Mathematical Logic and Formal Languages; Artificial Intelligence (incl. Robotics); Theoretische Informatik; Künstliche Intelligenz; Robotik; BC; EA

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.