Chatting with Meadowlark about AI

Computer bridge players of the 90s and early 2000s might remember a piece of bridge software called Meadowlark Bridge. It was the champion of the WCBC in 2000 and it stands as one of the classically fun bridge programs.

Meadowlark Bridge for PC can be downloaded at the official website over here!

Great Bridge Links caught up with Rodney A. Ludwig, creator of Meadowlark, to dig into how the software works and what is in store for Meadowlark in the future.

Meeting Meadowlark

“AI is a term not often used when describing the programming basis of computer bridge programs.” says Rodney as an introduction.

“The general algorithm has been to add heuristics to fast double-dummy solvers. If the hands generated are similar, the solver is much faster for, let us say, 100 hands. But the use of double-dummy solvers requires hands (hundreds of them) that are appropriate to the problem at hand.”

He says that current programs end up being better at play than bidding, because they need to draw conclusions about the meaning of the current sequence “while then determining the best bid all the while considering conventional bids and deliberately deceptive ones. Play of the hand has much more information to generate hands.”

“I’ll outline how Meadowlark bid and plays, and you can decide if this is AI.”

Meadowlark’s Bidding Bared

Rodney splits up the bidding process for Meadowlark Bridge into several different stages. Here they are – in his words, since he said it best!

1. The Early Bidding

“Early bidding is totally based on pattern matching the sequence and drawing conclusions about constraints that have been shown for that sequence. The next bid is selected from a prioritized list of available bids that match the description of the hand. For example, after a one of a major opener a splinter bid of 4 of a minor would be a higher priority bid than one notrump forcing. It would, however, need to have four card support of the given major and shortness in a minor and game forcing support.

If the description of the hand matches that pattern, it would not consider lower priority bids. Each bidding rule has flags as to whether conventions are on or off.

With a lesser hand, the forcing one notrump would come up for consideration. The conventional flags would determine whether this is a splinter or Swiss or something else.”

2a. The Later Bidding

“Previously, get a trial bid by using rules, then generate hands matching the bidding, solve them using double-dummy, get the scores for each bid for each generated hand and select the accumulated best bid or trial bid.

Currently, get a trial bid by using the rules, then generate hands matching the bidding, but use a hand evaluator for all four hands, combine the evaluator output for the pairs, get the scores based on what the evaluator says can be made for each pair for the bid being considered, again use the accumulated best bid.

This is much faster. Developing now, use the evaluator, but have a correction factor, that being a decision tree or neural network that has been trained with the evaluator, and a few hundred thousand hands to fine tune evaluation to the current situation.”

2b. Later Bidding

“Meadowlark has Amzi! prolog embedded in it. (it was recently made open source). There are specialized situations that it recognizes.

An example of this, forcing passes. It is able to use a set of rules to determine when a forcing pass obtains, and then what responding bids are appropriate. This uses standard prolog backtracking techniques based on the bidding sequence.

Note: Meadowlark no longer uses a double-dummy solver for bidding. I expect to be using a neural network as a correction to a hand evaluator as my next iteration on bidding improvement.

At the recent San Francisco competition, Meadowlark was dominated by programs that simulate competitive situations well. I was only using my base rules, not the evaluator, at that tournament, so I expect some improvement in the future, but not sure how much, against WBridge, Synrey, Microbridge or Q-plus.

Note: Meadowlark has two main systems…SAYC and 2/1. It has hundreds of conventions. Turning on and off conventions interactively is an exercise in AI in and of itself.

Note: Analyzing bidding by opponents. Nothing done so far, but could be very useful. Weak two bids are one area that would be interesting to categorize opponents and use AI techniques to defend.”

Playing the Hand

Rodney breaks down the hand-playing capabilities of Meadowlark into 3 stages.

Opening Leads

“Amzi! prolog rules based on suits bid by partner and opponents, followed by ranked strongest leads.”

Following the Opening Leads

“Immediately following the opening lead. Amzi! prolog rules for switch in time (ala Granovetters book) are used.”

Generating 100 Bids

“Subsequent to that 100 hands are generated from constraints on bidding and the plays made so far. The best accumulated score for each play is selected.”

“No prolog rules are used for play of the hand, although previous versions did have single dummy prolog play of the hand which has been abandoned.”

He notes that he’s switching to the Monte-Carlo Tree Search for hand play in future updates, an AI solving-system that has shown promise in games like Go.

Testing with the Raven

Rodney also designed a separate program that he calls “the Raven” to test Meadowlark’s bidding capacity. He says it’s truly fascinating to see in action.

“It uses knowledge of the par contract on known hands, plus the knowledge of how Meadowlark will bid a hand, to generate destructive bids. It’s equally adept at high level intervention and finding holes in the biding system.”

He says that the Raven has tracked down far more flaws in the bidding than humans have, and often psyches.

“It has not yet bid a control that it doesn’t have,” says Rodney, but also adds that his theory on this is because the system is testing bidding and not trying to influence the lead.

“The test program is one reason I switched to not using double-dummy solvers during bidding.”

The Raven considers every possible bi, and then computes the hand from there for all four players. There, Rodney says it calculates the worst score for the opponents – and comparatively, he says that the use of a solver would be far too slow. “If done recursively, it could bring even a supercomputer to its knees.”

The future for Meadowlark

We had heard through the grapevine that Meadowlark might be considering an online bridge platform so we asked Rodney:

“I do not think I will do online play, there seems to be plenty of that available. I am thinking of a multiplatform app, but I have not set up a timeline.”