We know that algorithms can provide mechanisms that beat humans at chess or more complex games like Go… but what about bridge? This game, beyond its combinatorial aspects, places a strong emphasis on human interaction. The bridge-playing robot, Nook, developed by NukkAI, ranks among the best thanks to a combination of symbolic AI and numerical AI.
Bridge is a card game in which a team of two players tries to achieve a common goal called a “contract,” which is determined during the bidding phase. Fulfilling a contract involves winning at least a certain number of tricks against an opposing team that works together according to established rules to try to defeat the contract.
Unlike board games such as chess or Go, bridge is a game of incomplete information. At the start, each player knows only the 13 cards in their hand. During the game, by analyzing the information revealed during the bidding phase and the cards played in each trick, each player can narrow down their assumptions about the cards remaining in play, but they must make their decisions (choosing which card to play in each trick) without full knowledge of the cards remaining in their partner’s or opponents’ hands.
To play bridge well, you need to master a variety of skills:
Make inferences (if a certain player played a certain sequence of moves, they either have or do not have a certain card)
Formulate and revise assumptions (e.g., a certain opponent has at least 5 Spade cards or has no more Heart cards)
Anticipate a number of likely moves by the opposing team
Assess the probabilities of the various possible opponent hands to guide risk-taking and calculate the expected value of the moves to be made.
Nook’s artificial intelligence, by leveraging the combined strength of symbolic AI approaches and computational AI techniques, has succeeded in outperforming eight world-class bridge champions over several hundred games with the same contract to fulfill (3 No Trumps). To ensure a fair comparison between Nook and human players, Nook and each champion played the same hands, in the same declarer position, against two Wbridge5 bots comprising the opposing team. Wbridge5 (developed by Yves Costel) is a multiple world champion in robot bridge competitions featuring only bots. Each human champion (just like Nook) plays with their own hand (hidden) and their partner’s hand (which serves as the “dead hand”), visible to all, against two opponents—simulated here by Wbridge5 configured in the defender’s position.
Unlike games with complete information (such as chess or Go), in a bridge game tree, the possible moves opponents can make in response to a move chosen by the robot depend on the cards in the opponents’ hands, which are unknown to the robot. For each Min node in the tree (i.e., a node that models the opponents’ responses), it is therefore necessary to generate possible worlds (the opponents’ possible hands) and, for each one, to explore the opponents’ most likely responses to the card played by the robot.
Nook's strength lies in its intelligent exploration of a game tree featuring possible worlds, drawing on four complementary techniques:
Automatic Reasoning Based on Rules
Machine learning based on a sample of previously played games to learn opponents' strategies
Monte Carlo -style random generation of possible worlds constrained by domain rules and adversary models
A Min-Max tree search with Alpha-Beta pruning in each possible world, utilizing the models of the various players.
More specifically, the algorithm for exploring Nook’s game tree of possible worlds is an extension of the AlphaMu algorithm developed by Tristan Cazenave and Véronique Ventos, which has been optimized. At each stage of the game, the algorithm randomly generates different possible worlds while verifying their compatibility with the constraints inferred from rules and from observed or learned opponent models. In each of these possible worlds, the various possible moves are evaluated by a MinMax algorithm made highly selective through the use of opponent models.
Some player models are neural networks that have been automatically trained for their specific task. The training data was obtained from hundreds of thousands of games played by WBridge5 against itself. The neural network used—a ResNet—is not very large, and the size of the training dataset is reasonable. As a result, the training phase—carried out on the CNRS’s Jean Zay computer—required 200,000 times fewer computational resources than the training of the neural network used in DeepMind’s AlphaGo, which defeated Go master Lee Sedol in 2016.
Automatic rule-based reasoning is key to narrowing down the number of possible combinations and explaining decisions. The rules provided to Nook model the knowledge of a bridge player, allowing it to infer—based on the bidding sequence—positive or negative constraints on the hands of the various players. For example, a partner’s “2 No Trump” bid following a “1 No Trump” opening bid and an opponent’s Pass implies that the partner has a balanced hand or fewer than 5 cards in Hearts or Spades. Other rules describe how the opponent chooses the opening lead (Lead Selection Module).
These rules can be interpreted by humans (since they are expressed using concepts that make sense to players, such as “even distribution”) and can be processed by a machine that has been provided with the link between these abstract concepts and specific hand distributions. Based on the abstract, inferred knowledge that a hand has a regular distribution, we can automatically generate all corresponding concrete hands (and their probabilities) based on the cards in our own hand and, as the game progresses, the cards played by the various players.
It is therefore easy to see the value of rules for gradually narrowing down the set of possible worlds over time and thus guiding the random generation process at the heart of Monte Carlo-style tree-based exploration.
Another benefit of these rules is that they can be used to explain, at any point during the game, a high-level, probabilistic view of opponents’ hidden hands. In fact, in bridge, answering questions such as “Why did you play that card?” is part of the rules of good conduct, specifically to verify that a player is not cheating or that a trick was not merely a matter of luck.
Even though Nook currently plays only one variation of existing bridge “contracts” (the “three-no-trump” contract), its developers have already demonstrated the benefits of a “hybrid” AI that, among other things, enables it to explain its decisions. This new approach, which NukkAI plans to deploy in other fields such as cybersecurity, education, and transportation, paves the way for “something that more closely resembles intelligence than what we’ve seen in recent years,” notes Cédric Villani, author of a 2018 parliamentary report that inspired the French government’s strategy on artificial intelligence, who came to observe the challenge in person.
