Search and Planning under Incomplete Information: A Study Using Bridge Card Play
Ian Frank
PhD Thesis, Department of Artificial Intelligence, University of
Edinburgh, 1996.
(Joint winner of the UK 1997 Distinguished
Dissertations Award.)
Copies available from Springer-Verlag --- See this page
Abstract:
This thesis investigates problem-solving in domains featuring
incomplete information and multiple agents with opposing goals. In
particular, we describe FINESSE --- a system that forms plans for the
problem of declarer play in the game of Bridge.
We begin by examining the problem of search. We formalise a best
defence model of incomplete information games in which equilibrium
point strategies
can be identified, and identify two specific problems that can affect
algorithms in such domains. In Bridge, we show that the best defence
model corresponds to the typical model analysed in expert texts, and examine
search algorithms which overcome the problems we have identified.
Next, we look at how planning algorithms can be made to cope with
the difficulties of such domains. This calls for the development of
new techniques for representing uncertainty and actions with
disjunctive effects, for coping with an opposition, and for reasoning
about compound actions.
We tackle these problems with an architecture that identifies and
resolves conflicts on the basis of probabilistic reasoning about
resources. The prime contribution of this architecture is that it
can construct plans which succeed under a large number of possible
world states without having to consider each world state separately.
By casting our algorithm within the classical plan-space planning
paradigm we show how our techniques differ from, yet may be
incorporated into, existing planning architectures.
The original motivation for this work came from the field of
mathematical reasoning.
In Edinburgh, a technique known as proof-planning has been developed
to control the search for the proofs of mathematical theorems.
The defining feature of this paradigm is that it restricts the
available options at any stage of planning to a pre-determined set of
possibilities. By applying proof-planning techniques to the domain of
Bridge
(although currently only in the sub-problem of play without a trump suit),
FINESSE becomes capable of constructing plans that look ahead
right to the end of the tree of possible actions. Against human
players it is therefore less prone to the short-sightedness that
afflicts the traditional look-ahead approach. This allows it to solve
problems that are beyond the range of previous systems.
We also describe two useful side-effects of formalising the
way in which Bridge can be played. Firstly, the high-level nature
of the objects in FINESSE's plans, combined with the utilisation of a
qualitative uncertainty representation language, gives the system
the ability to produce meaningful textual explanations for its
actions. Secondly, by distilling the large diversity of card-play
examples found in the Bridge literature into a manageable number of
concrete and distinct manoeuvres we arrive at a deeper
understanding of the game itself.
| 