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

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Multiagent Problem Solving

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 imperfect-information 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 modified HTN planning strategy appears to be useful in a variety of application domains-for example, we have used the same planning techniques in a process-planning system for the manufacture of complex electromechanical devices (Hebbar et al. 1996). We discuss why the same technique has been successful in two such diverse domains.