TL;DR
This paper introduces Tignum 2, a novel AI system for playing contract bridge that leverages a modified Hierarchical Task-Network (HTN) planning approach. By adapting HTN planning to handle multi-agency and uncertainty, Tignum 2 achieves state-of-the-art performance in bridge declarer play, outperforming existing commercial programs.
What Problem Does This Paper Address?
Playing imperfect-information games like contract bridge presents a significant challenge for traditional AI approaches, primarily due to the massive branching factor of game trees and the inherent uncertainty about opponents' hidden cards. Standard game-tree search methods, successful in perfect-information games like chess, struggle with bridge because a full search is computationally infeasible within the time constraints of a game. While some approaches attempt to mitigate this by making assumptions about opponents' hands, these methods have limitations. This paper tackles the problem of developing an AI that can play bridge declarer effectively by proposing a planning-based approach that directly addresses these challenges.
Methods
The core of Tignum 2's approach is a modified Hierarchical Task-Network (HTN) planning system. Unlike traditional HTN planners, Tignum 2 employs a total-order planner, meaning tasks are always expanded in the strict order they are to be performed. This is a deliberate choice to simplify reasoning about the uncertain state of opponents' cards.
Key modifications to standard HTN planning include:
- Multi-agency and Uncertainty: The HTN framework is extended to represent multiple agents (declarer, dummy, opponents) and the inherent uncertainty of hidden cards.
- Total Ordering: Tasks are expanded in the order they will be executed, which simplifies reasoning about uncertain information. This contrasts with typical HTN planners that might expand tasks out of order to prioritize critical decisions.
- Arbitrary Code for Preconditions: Instead of relying solely on predicates, Tignum 2 uses arbitrary code to check preconditions for methods. This allows for more flexible and sophisticated reasoning about specific bridge scenarios, such as identifying various types of "finesse" opportunities.
- Scheme-Based Planning: The planning process is driven by "tactical and strategic schemes" (analogous to methods in HTN planning) derived from bridge literature. This reduces the branching factor of the game tree, as the number of branches from each state is determined by the number of applicable schemes, not just possible actions.
Datasets
Not discussed in the paper. The evaluation was performed on 5000 randomly generated bridge deals.
Key Insights and Ideas
- HTN Planning for Imperfect Information: The paper demonstrates that HTN planning, when adapted, can be a powerful paradigm for tackling imperfect-information games, offering an alternative to brute-force game-tree search.
- Total Ordering as an Advantage: While counter-intuitive for some planning problems, forcing a total order in Tignum 2 simplifies reasoning about uncertain information, which is crucial for bridge.
- Flexibility in Precondition Checking: The ability to use arbitrary code for method preconditions significantly enhances the system's ability to reason about complex, domain-specific situations like bridge card play.
- Generalizability of the Approach: The modified HTN planning strategy, initially developed for bridge, has also proven successful in process planning for complex electro-mechanical devices, suggesting a broader applicability of the core ideas.
Key Results
Tignum 2 demonstrated superior performance in declarer play compared to the strongest commercially available bridge program. On 5000 randomly generated deals (including both suit and notrump contracts), Tignum 2 won 254 deals to the opponent's 202, with 544 ties. This result was statistically significant at the $\alpha = 0.05$ level and was achieved without training on specific deals, mitigating bias.
Limitations and Future Work
The authors acknowledge that their approach is a "sketch" and that full details are available in another publication. They also note that while their approach avoids examining all possible moves, it is related to forward pruning in game-playing. Future work includes investigating the applicability of this approach to defensive play in bridge and exploring other imperfect-information domains. They also mention that efficiency improvements for game trees (like transposition tables and alpha-beta pruning adaptations) are available but not yet implemented in Tignum 2.
Summary updated