Total-Order Multi-Agent Task-Network Planning for Contract Bridge

Abstract

This paper describes the results of applying a modified version of hierarchical task-network (HTN) planning to the problem of declarer play in contract bridge. We represent information about bridge in a task network that is extended to represent multi-agency and uncertainty. Our game-playing procedure uses this task network to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes. This approach avoids the difficulties that traditional game-tree search techniques have with imperfectinformation games such as bridge---but it also differs in several significant ways from the planning techniques used in typical HTN planners. We describe why these modifications were needed in order to build a successful planner for bridge. This same modifiedHTN planning strategy appears to be useful in a variety of application domains---for example, we have used the same planning techniques in a...