AI and Bridge


Bridge still offers a massive challenge for programming artificial intelligence. Want to find out more about the AI behind bridge robots? Here are some articles, studies and resources:

Article from the French magazine HUFFPOST 2017:

Why bridge still resists artificial intelligence.

The rules of the famous card game, whose World Championship takes place in Lyon, are not easy to understand for a robot.

Bridge fans hold their breath. This Saturday, August 12, the world championships of the card game begin in Lyon. The winner will be known a few days later, on August 26th. In parallel in Lyon, computers will be confronted in the World Computer Bridge Campionship, which begins on August 19th.

No official confrontation human vs artificial intelligence is provided for. But then, who of the man or the machine is the strongest at the bridge? "On the last confrontations, the programs were still below the best human players," says HuffPost Tristan Cazenave, a CNRS researcher specializing in game-related algorithms. However, artificial intelligence has already overcome the failures and the game of Go, so why not the bridge? In contrast to these board games, "the information available is incomplete here, it's more difficult to program," says Tristan Cazenave In go or chess, the computer sees the whole board (the difficulty is in the number of possible combinations). In a card game, on the contrary, only one part of the information is available for the machine, the cards in his hand. This complicates enormously the deal. However, an artificial intelligence has managed to win in a duel against a poker champion at the beginning of the year. A feat not expected until a few years, especially that in this version of the card game, it is possible to bet as much money as desired, which greatly complicates the task for the machine. So why not the bridge? Already, it must be understood that there are fewer specialized researchers on these issues. But there is also a specificity of this card game: its rules is more complicated. "There are several players and an auction system, it's more difficult to program," said Tristan Cazeneuve. More than poker? "I do not know exactly, but intuitively, I would say yes."'

Speak without knowing Indeed, in bridge, as in belote or tarot, it is necessary to bid the score that one hopes to make. All with incomplete information. Only after the participants have played their cards it is known. This first part of the game is the nerve of war.

Moreover, as early as 1998, a machine managed to get by with real-life bridge professionals ... without the phase of bidding. In bridge, the man still has the advantage over the machine. But for how long? The French program Wbridge5, improved in 2016, won the robotics world championship of bridge last year and should improve still further. In the same year, researchers at the National Taiwan University claimed to outperform the best programs available for bidding. Rather than trying to create an algorithm that tries to copy the human strategies for the bidding, the two authors used the same thing as DeepMind, the machine that prevailed over the game of go. These techniques, deep learning and reinforcement learning, allow a computer to create models from a large number of examples, then to self-train. Their next step is to perfect the program and train it so that it can handle the play of the cards.. Whether this one or another artificial intelligence will sucessed, the supremacy of the man on the bridge is challenged.

Article from the french magazine LE TRIBUNE 2017:

Bridge, the next frontier of artificial intelligence

With English checkers (in 1994) or chess (in 1997), so-called brute force programs allowed computers to defeat human champions. But with the game of Go, computers and brute force capped at the amateur level. It was not until 2016 that a British company, Deepmind, achieved a breakthrough with artificial intelligence. Poker followed quickly. Why did the bridge survive until then? And why is France well placed in the competition? By Jean-Baptiste Fantun, at the Long Term Observatory. The bridge, whose world championships have just started in Lyon, is one of the last big games where the man still surpasses the machine. Creating a better artificial intelligence than the bridge champions could therefore be a major challenge for years to come. And French researchers have serious assets to win the race.

Games, field of experiments for researchers

Games have always been a perfect field of experimentation to test the capacity of computer technologies. The rules are often simple, limited in number and a solid human expertise has accumulated over time, making the field of games much easier to understand and model than the real world. The first complex game where the computer has surpassed the human is the English ladies where the software Chinook obtained in 1994 a title of world champion against a human. Better known, Deep Blue developed by IBM beat in 1997 the world chess champion Garry Kasparov. Chinook, Deepblue and their successors rely on so-called brute-force techniques and emerged thanks to the meteoric rise of machine power in the 1990s.

The long battle of the game of Go

With regard to Go programs, the number of game combinations and the increasing difficulty of evaluating a given position render ineffective brute-force programs (which are limited to trying all possible solutions). As a result, for many years, the best programs did not exceed the level of an average amateur player. It was not until January 2016 that the British company Deepmind made a breakthrough with Alphago, an AI (Artificial Intelligence) coupling deep neural networks and reinforcement learning. In May 2017, Alphago crushes the best player in the world, Ke Jie, by 3 games to 0. In the wake, Dennis Hassabis, CEO of DeepMind, announces that Alphago played there his last competitive match, his research teams being gone after their research work on this topic. Most recently, Artificial Intelligence has also defeated poker: in January 2017, the Libratus system won a no-limit Texas hold'em poker tournament heads-up against one of four professional level players. world. To express himself as a hacker, poker was more difficult to "crack" than the go because it is an incomplete information game: in poker we see his two cards (hidden) and those of the flop but not those of the opponents while the go the location of the pieces is known to all.

Why bridge has so far resisted scientific

Advances Bridge is even more difficult to tackle than poker because of the incompleteness of the game, which is stronger. The bridge is played four (two teams of two) and there are three hidden hands: the hands of two opponents and the hand of our partner. There are therefore 13 unknown cards for each player while in poker there are only two. On the other hand, if bridge integrates bluffing elements like poker (existing only in games with imperfect information), the need for collaboration between partners brings additional complexity. Finally, during the bidding phase, each player has the obligation to explain the meaning of his actions, additional difficulty for an automated system. In real life, the problems that we encounter are mostly incomplete information and some require the cooperation of several actors who communicate with each other and must explain the rationality of their actions: any scientific breakthrough in the field of automated bridge is therefore likely to have repercussions that go far beyond the sphere of play.

France well placed in the race for bridge solution

Until now, the complexity of the bridge has been a barrier to entry for researchers, few of them having the level of understanding of the bridge necessary for further research in this area. The decisive impulse came from France thanks to Véronique Ventos, a researcher in Artificial Intelligence at the Paris-Saclay Computer Research Laboratory and also an expert bridge player. Finding here a unique opportunity to combine her passion for bridge and her research work, she has assembled a team of researchers from different fields of Artificial Intelligence like Olivier Teytaud (one of the pioneers of Go AI) and champions of bridge like Jean-Christophe Quantin (multiple European bridge champion).

Véronique Ventos published in June 2017 in the Journal of Artificial Intelligence an article presenting her first steps towards a bridge AI whose architecture will be composed of modules from recent work in machine learning. This architecture will allow both to play at a level higher than that of current AI and explain to a human reasoning by the program. His results were used by Yves Costel, a Lyon engineer who created the bridge software WBridge5 in 1980, and who won the last computer bridge world championships in October 2016 in Wroclaw (Poland). France has good assets to win the race for the resolution of the bridge. And considering both the media effect, but, especially, applications to other areas, it's a game to take seriously!

Links

Why 'Bridge' a cerebral game that even AI can't conquer deserves more attention, Dayly O

How A.I. Can Solve the World's Problems: Challenge It to a Game of Bridge

Philippe Pionchons ideas about AI and Bridge from 1984, which is still valid today.

Computer Bridge: A Big Win for AI Planning, AI Magazine 1998

The State of automated Bridge Play, NYU Computer Science 2009

GIB: Steps Toward an Expert Level Bridge Playing Program, Mattew L. Ginsberg

GIB: Imperfekt Information in a computationally challenging game, Mattew L. Ginsberg

The Computer game model of Contract Bridge, X Mei 2012

Contract Bridge bidding by learning, CY Ho 2015

Automatic Bridge Bidding Using Deep Reinforcement Learning, CK Yeh 2016

Boosting a Bridge Artificiell Intelligence, V Ventos 2017

Bridge a new challenge for AI, V Ventos and O Teytaud 2017 In French,                                                     Google Translate can be used for translation...

IEEE CIS Webinar "Bridge a new challenge for AI" Nov 27, 2017

USBC analysis & Levin - Weinstein profile 2018

AI, Contract Bridge, Conventional Bidding. A casual update 2018

A new Bridge Bot, Alan Frank 2018

Computer Bridge: Card Combinations in Notrump , David Levin 2019

Robots in theory and practice, The Bridge World,                                                                                               Al Levy: Part I (2015) - Part II (2016) - Part III (2017)

Facebook takes on Poker. When will the bridge robots play like that!

Simple is better: Training an End-To-End Contract Bridge Bidding Agent without Human knowledge

Competitive bridge bidding with deep neural networks

Learning multi-agent implicit communication through actions: A case study in contract bridge, a collaborative imperfect information

Learning to Communicate Implicitly by Actions

Bridge and Artificial Intelligence in Orlando

AI, Contract Bridge, Conventional Bidding. A casual update. 

Man vs machine: How AI is taking over human bastions of complex strategy games

Frontier in Pattern Rekognition and AI

Artificial "General" Intelligence is still science fiction

Interesting Artificial Links 

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

Success in Spades: Using AI Planning Techniques to Win the World 

A Planning approach to declarer play in Contract Bridge