The Best is Yet to Come
By: Fred Gitelman

Why is it that we keep reading about computer chess programs challenging World Champions while the best computer bridge programs would have a hard time coming above average in most club games? One of the main reasons is historic. Since the 1950s hundreds of highly skilled chess players and computer scientists have worked on the problem of getting a computer to play a good game of chess. Indeed, developing good chess programs has been a defining goal for the field of artificial intelligence (AI).

As far as I know there is only one person in the world who is both a top AI programmer and an expert bridge player. The good news is that this person is actually working on the project of programming computers to play a good game of bridge. His name is Matthew Ginsberg and the software he is developing is truly remarkable.

Matt, 41, received his doctorate in mathematics from Oxford at age 24. In 1992 Matt founded the Computational Intelligence Research Laboratory at the University of Oregon. He directed this facility for several years and still does his research there. Matt has written an AI textbook and has published dozens of papers. He is one of the leading AI researchers in the world. Matt is an excellent bridge player and a serious student of the game. Unfortunately, the demands of his research do not afford Matt much time for bridge these days. Matt lives in Eugene Oregon with his wife Pam and 2 year old son, Navarre. His other interests include stunt flying, writing plays, card tricks, and baking fancy deserts. Matt has also had some success writing programs to help make stock market decisions.

Matt has developed a program called GIB (short for Goren In a Box). GIB in not currently a full bridge playing program. Presently it can be used to solve declarer and defensive play problems. Matt's latest work has involved teaching GIB to bid, as well as improving the speed and accuracy of its card play.

At the heart of GIB is a program that can look at all 52 cards in a bridge deal and decide how many tricks can be made (a double dummy problem). GIB can solve a typical 52 card double dummy problem in about a second. Since some particularly fiendish double dummy problems have been constructed that stump human experts for days, GIB's performance is really amazing. We all have memories of playing bridge hands and wondering "could I have made that contract?". GIB could tell you in a second or so.

GIB can go one step further. It can answer the question, "should I have made that contract?". By performing a double dummy analysis on 100 or so possible layouts of the unseen cards, GIB can figure out the best card to play in any situation. Since this process involves some random simulation of the unseen hands and due to complex programming issues, GIB occasionally errs in deciding which cards to play. Matt's latest ideas should solve these problems and lead to near perfect card play by the next version of GIB (to be known as GIBSON).

Even in its current "non-perfect" state, GIB's card play skills are in a completely different league than anything that is currently commercially available. Matt recently performed an interesting experiment to test GIB's declarer play skills. GIB's "victim" in this test was Bridge Baron, one of the best existing bridge programs. Matt used Bridge Master, a program that I created, to perform the test.

Bridge Master is an educational program that is designed to improve the user's declarer play. The user is presented with a series of instructional deals to play at whatever level of difficulty they like. We have recently begun selling Bridge Master for Windows which comes with 180 lesson deals, 36 at each of 5 levels of difficulty. One of the nice things about Bridge Master is that it allows your contract to succeed only if you play correctly as declarer. Any mistakes will be punished by the defeat of your contract. As we all know, in real bridge a lucky lie of the cards or a misdefensive often allows us to get away with card play mistakes. This does not happen with Bridge Master where mistakes are always punished. This property of Bridge Master made it an excellent medium for Matt's experiment.

Matt had both GIB and Bridge Baron play all 180 deals in Bridge Master. Here are the results:

Those of you who have tried Bridge Master will find these results amazing. For those of you who have not, I would guess that there are less than 20 players in world that could match GIB's performance on the Level 5 hands. It is also interesting to note that GIB's performance was fairly consistent regardless of the difficulty level of the deals that it played.

GIB is scheduled to play a 96 board match against Bridge Baron in June. The winner of this match will win $2500 and play bridge against human experts in the upcoming Hall of Champions - a competition between the best human and computer players of several strategy games.

What is Matt's goal? Nothing less than world bridge supremacy. Zia Mahmood once bet one million British pounds that no team of 4 computers will ever beat a team of 4 people that Zia puts together. Matt was hoping to collect on this bet but when Matt approached Zia, Zia turned tail and ran, claiming the bet was not on indefinitely. Zia had heard through the grapevine about Matt and GIB.

If Matt can get permission from the ACBL he is hoping to enter GIB in some National events. GIB is already a member of the ACBL and may play in a side game at the upcoming Nationals in Dallas. As GIB is only 3 years old, it has already improved the ACBL's age demographics!

My company is trying to join forces with Matt in an effort to develop GIB into a commercial product (likely with a new name). The resulting product will play much better than anything currently available. GIB will finally provide a challenge for tournament level players who are sick of programs that bid and play worse than they do. Expect to see a commercial version of GIB early in 1998.

Our game is sadly lacking in media exposure. The recent success of chess programs has received front page coverage in most major newspapers. Major corporations (like Intel) put millions of dollars into to chess tournaments between people and machines. If GIB turns out to be everything Matt thinks it will be (and, after meeting Matt and seeing his work, I believe him) this project will give bridge some badly needed publicity.

If you have an interest in computer science and would like to talk to Matt about GIB he can be reached via e-mail at: ginsberg@cirl.uoregon.edu. If you would like to read more about GIB, visit GIB's web page:

http://www.gibware.com