Ebook: Search and Planning Under Incomplete Information: A Study Using Bridge Card Play

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.

---

The Distinguished Dissertation series is published on behalf of the Conference of Professors and Heads of Computing and the British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. This book examines how to play and solve incomplete information games. Starting by giving a meaning to the idea of est defence it clarifies the problems that incomplete information poses to standard search algorithms, and describes alternative algori thms that fare better. It also introduces planning techniques that can cope with incomplete information by extending the classical plan-space planning paradigm. ''

---

The Distinguished Dissertation series is published on behalf of the Conference of Professors and Heads of Computing and the British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. This book examines how to play and solve incomplete information games. Starting by giving a meaning to the idea of est defence it clarifies the problems that incomplete information poses to standard search algorithms, and describes alternative algori thms that fare better. It also introduces planning techniques that can cope with incomplete information by extending the classical plan-space planning paradigm. ''
Content:
Front Matter....Pages i-xix
Introduction....Pages 1-8
A Good Deal of Bridge Literature....Pages 9-25
Planning Literature....Pages 27-43
The Bridge Search Space Size....Pages 45-58
Proof-planning: Solving Independent Goals Using Tactics and Methods....Pages 59-88
Search in Games with Incomplete Information....Pages 89-123
Identifying The Best Strategy: Tackling Non-locality....Pages 125-158
Interleaving Plans with Dependencies....Pages 159-198
Re-introducing Neglected Actions....Pages 199-209
Overall Architecture....Pages 211-224
Results....Pages 225-243
Conclusions....Pages 245-252
Back Matter....Pages 253-340

---

The Distinguished Dissertation series is published on behalf of the Conference of Professors and Heads of Computing and the British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. This book examines how to play and solve incomplete information games. Starting by giving a meaning to the idea of est defence it clarifies the problems that incomplete information poses to standard search algorithms, and describes alternative algori thms that fare better. It also introduces planning techniques that can cope with incomplete information by extending the classical plan-space planning paradigm. ''
Content:
Front Matter....Pages i-xix
Introduction....Pages 1-8
A Good Deal of Bridge Literature....Pages 9-25
Planning Literature....Pages 27-43
The Bridge Search Space Size....Pages 45-58
Proof-planning: Solving Independent Goals Using Tactics and Methods....Pages 59-88
Search in Games with Incomplete Information....Pages 89-123
Identifying The Best Strategy: Tackling Non-locality....Pages 125-158
Interleaving Plans with Dependencies....Pages 159-198
Re-introducing Neglected Actions....Pages 199-209
Overall Architecture....Pages 211-224
Results....Pages 225-243
Conclusions....Pages 245-252
Back Matter....Pages 253-340
....