A Knowledge-Based System for Locating Missing High Cards in Bridge

1. INTRODUCTION

Recent years have seen the emergence of more and more high-performance systems whose power derives not so much from the merits of an underlying general algorithm, but rather from the richness of the knowledge structures they employ. So for Instance, Instead of having a system to do X that consists of a sophisticated quasi-decision process (such as a resolution theorem prover) together with a small number of axioms that are sufficient for X In the logical sense, a system of this new breed might be a simple generate-and­ test type of data base Interpreter together with a large col­ lection of rules, advice, methodologies and distilled wisdom extracted In some more or less painful way from a human X-pert. A goodly sample of them appears In (8] while the much-cited survey [1] gives an excellent overview.

This paper describes the present status of such a knowledge­ based system whose application area Is one small corner of the game of Bridge. After the opening lead each player can see two hands-his own and that of the dummy-leaving two 'closed' hands. Any high card (ace, king, queen or jack) that does not appear In the open hands must be in one or the other of the closed hands, and often the ability to determine In which hand It lies holds the key to the development of a correct line of play. Expert players can usually do much bet­ ter than guessing which closed hand holds a particular high card. Clues from the bidding and partial play of the hand may be sufficient to place any given high card with certainty or at worst with high probability. Several expert-level books, notably (2] and (3), are devoted to techniques for achieving this. Since Lawrence's book Is particularly helpful, the goal of this system Is to perform high-card location to the level of that found In [2] and using the techniques outlined therein.

There were two motivations for tackling this particular task. Unlike most games, Bridge Is played with Incomplete infor­ mation; this characteristic has perhaps been responsible for the relative dearth of AI programs In this area (see [6,7]).

The work reported here was performed while the author was visiting the Computer Science Department, Stanford University, and using facilities made available there by the Heuristic Programming Project and the Artificial Intelligence Laboratory.

Thus knowledge about card holdings can be unspecific (East has either the ace or the l<lng) and uncertain (he probably has the l<lng). Moreover Information can come from different sources; what a player did or did not bid, what he led or did not lead, and so on. In short this problem Is a microcosmic environment In which reasoning processes typical of 'real' problems can be brought Into play. Secondly, It was used to Investigate the utility and generality of ·some current rule­ based models, their accessibility to a neophyte knowledge engineer, and their adequacy for this non-trivial problem.

As It stands, the system Is Qnly part-way towards Its goal. The following sections give an Illustration of the level of performance that It Is currently able to achieve, and a com­ parison of results to date with the model (I.e. the book).

2. AN EXAMPLE

Imagine If you will that you are sitting In the South seat for the hand shown in figure 1. Your analysis as you attempt to locate the missing honours might run something like this:

West led the ¥4. He would not underlead an ace, so he does not hold the ace In the suit lead. Neither the dummy nor I have It, so East must have the ¥A.

West's lead Is weak, suggesting that he was unable to make a stronger lead such as from the ace-king or king­ queen of an unbid suit or from any sequence of honours In his own suit. In particular, then, he does not hold both the ·a and ¥J.

It is unlikely that East would have played from the middle of a sequence. Since East holds both the ¥A and ¥K, he cannot also hold the ¥0 (otherwise he would not have played the king). Therefore West has it.

Since West does not have both the ¥a and ¥J, but does have the ¥a, then East mus· have the ¥J.

There are 40 high-card points In all. Dummy and I together have 19, so East and West together hold 21. I already know that East has the ¥A, ¥K and ¥J for a total of 8 high-card points; If he held so much as another queen then West would have opened the bidding with at most 11 high-card points, which Is unlikely. Therefore the +A and +a and the ·A are with West.

Reasoning along these lines, South Is able to pinpoint each missing honour except the tJ, In his analysis he has made

North

+ KQ 6

· 6 2

+ K 10 8 3

· a 10 3 2

South

+ AJ1094

· g 7

+ J 7 6

· K 9 4

Opening lead: ¥4

First trick taken by East with ¥K

Figure 1 : A sample hand for analysis.

use of several sources of Information. Besides facts about this particular hand there are rules or guidelines that South believes his opponents will adhere to, such as

An opening bid Indicates at least 7 2 high-card points. Opening leaders avoid underleadlng an ace. Third hand does not play from the middle of a sequence.

The guidelines are used In conjunction with facts to obtain new facts by 'everyday' reasoning processes. Knowing that West would not underlead an ace (guideline) and that he led the ¥4 (fact) give us that he does not have the ¥A (fact). Having determined that he does not hold both the ¥0 and ¥J (fact) but that he has the 'IQ (fact) Implies that he does not have the 'IJ (fact). The guidelines are also used negatively-patterns such as 'If he held x he would have done y; since he didn't, he does not hold x' are common In bridge books.

3. SUMMARY OF RESULTS

The first substantial chapter of the book basically restricts Itself to analysis of who has what using Information from the bidding and first trick. It contains fourteen case studies, In all of which the unknown hands belong to the defenders. For each study we are given the open hands, the bidding and opening lead, and sometimes further history of the play of the hand.

In Its current state the system can handle these studies fairly comfortably. Its conclusions are Identical to those of the book In twelve of the fourteen cases; the example of the previous section Is one of them. Of the other two cases, one Is almost correct-a single queen Ia mlalocated. The remaining case Is unusual In that the analysis In the book, which follows play down to the fifth trick, Is concerned only with the more likely location of a single card, using both a rule for understanding play and a technique called counting that have yet to be Incorporated In the program. On this example the system understandably flounders.

In the next chapter the focus Is on the opening lead, with a battery of quizzes and eight more case studies. The sys­ tem performs well on six of the eight, Ia slightly deficient In ono case (missing out on one queen), and has substantial difficulty with the remaining case, which uses Information from the first three tricks and once again requires counting.

These chapters constitute about 40% of the material in the book. Of the twenty-two case studies they contain, the system locates the missing high cards with the same preci­ sion In eighteen cases, slightly lower precision In two cases, and with shortcomings attributable to the absence of crucial mechanisms In two cases.

As a further test, the program was run on some hands that had not been used In Its development: those from the next chapter of [2] and from the bidding analysis chapter of [3] · For each of these 18 hands the program was given only the bidding, known hands and opening lead. It managed to locate a total of 14 honours with certainty (all correct), and made an additional 13 less specific asserlons of the form 'x holds either y or z' (one error). It accurately established the high­ card points of each closed hand (usually to within a range of two or three points) In all but one case when It was one point out.

4. DESCRIPTION OF THE PROGRAM

Like Gaul, the system Is divided roughly Into three parts concerned with bidding, opening leads and commonsense reasoning respectively. (There Is In addition an embryonic play section which merely says that play from a sequence Is either from the top or the bottom.) The system Is written In INTERLISP [6] and takes a few seconds of DEC KA-1 0 time to complete the analysis of a hand.

4.1 Bidding

Bridge bidding Is notoriously complex. The bidder must choose what Incomplete Information he wishes to convey about his hand and the most economical message for doing so unam­ biguously. However, our program does not have to maile bids but Instead understand them; It does not have the problems of choice of Information or bid, but only the problem of decod­ Ing the message once the bid Is made. The Information ex­ tracted from a single bid Is primarily the range of high-card points and suit holdings that It Indicates, but more general distributional Information for the opening lead module Ia also extracted from the bidding as a whole.

The method of determining the nature of a bid Is simply to find a rule which It matches In context, so this part of the program Is similar to a pure production system. The 2¥ bid In figure 1 matches a rule that may be stated as

• If partner has just opened or overcalled In a suit, and the Intervening bidder has passed, and this bid Is a minimum raise of partner's suit

then this Is a weak reply Indicating 6-9 high-card points and three or more cards In the suit bid

To date only the more common bids have been Included-the program understands passes; openings of one In a suit or strong no-trump; overcalls; second round openings; takeout doubles; free, weak and strong replies; and rebids. This entire body of bidding knowledge consists of 18 rules.

4.2 Opening Lead

The second principal source of facts Is the opening lead. All twenty-two case studies reach a suit contract, so the program was restricted to analysis of opening leads against sub-slam suit contracts; sections for leads against no-trump and slam contracts should be quite similar.

Analysis of the lead requires mechanisms that are awkward to express In any conventional rule format. The underlying Idea Is that leads are ranked by their strength, and that a neutral or weak lead Indicates an Inability to make a stronger one. This ranking Is most fluently represented as a strongly ordered sEJquence of rules of the form If-then-else, where no rule can fire unless all previous ones have failed to do so. For Instance the first such rule developed tests for the lead of an ace In an unbid suit, while the second Is

• If the lead Is a king of an unbid suit
• then the leader also holds either the ace or queen of that suit, but not both
• else the leader does not hold the ace-king or king-queen of any unbid suit

where the else clause uses the ordering of rules to establish that the lead was neither the ace nor king of any unbid suit.

The lead-understanding module In fact contains three com­ ponents; a supplementary unordered set of productions, a procedural section to classify suits (e.g. as unbid), and 1 2 of these unorthodox If-then-else rules. Despite Its simplicity It turns out to be surprisingly accurate, accounting exactly tor all but three of the 80-odd such opening leads In the book. One error was the result of a strong lead of trumps, the other two were caused by perverse distributions. The procedural section attempts to Identify suits In which the leader Is likely to hold either a singleton or a doubleton, using Information from the open hands and distributional clues from the defenders' bidding. If the real distribution of the suit led Is very different from the predicted one then the lead can be misinterpreted. However the figures Indicate that such situations are rare.

4 .3 Commonsense Reasoning

The bidding and opening lead are sources of facta. The third component of the system Is the embodiment of reasoning processes that Inter-relate guidelines and facts to obtain new facts. This component was developed using AGE (4], a package that guides the novice In the design and test­ Ing of rule-based systems. The prototype AGE was limited to a 'blackboard' model In which rules are partitioned Into 'experts' Invoked by 'events', but this seemed quite ap­ propriate for the reasoning task. The package did suffer from a real if temporary limitation, however, in that an event could Invoke only a single expert. Rather than program around this and other very minor Irritants, the structures developed were translated to INTERLISP pending a more advanced ver­ sion of AGE.

The most Interesting facts are naturally those ascribing par­ ticular high cards to particular hands. It is not always pos­ sible to discover facts of this form directly; Instead, they must be derived from Intermediate, less interesting facts. However the variety of facts that have bearing on the loca­ tion of missing high cards Is limited. A hand can be asserted to hold a particular card, one or more of a set of cards, or not all of a set of cards. It can also be described by the possible range of high-card .points and suit holdings It contains. An event Is taken as the discovery of any such fact, and can trigger one or more of eight experts containing a total of fifteen rules. Each expert encapsulates all knowledge of some facet of the reasoning task; for Instance, one knows about the consequences of high-card point ceilings, another about the Implications of locating a particular card. A sense of purpose Is maintained by giving priority to experts capable of generating facts of the first (and most Interesting) form.

6. CONCLUSION

The performance of the program to date Is encouraging, especially In the light of the small number of rules with which It has been equipped. The next steps In Its development are clear: the addition of a section for counting, the Installation of a more powerful play-understanding component, and the filling In of the gaps In the system's knowledge of bidding and leading. None of these present any conceptual problem.

The program has one glaring weakness. While It can ac­ r.n"'odate vagueness It cannot resolve conflict such as might nrisc If the opening lead Indicates that one player does not have a particular ace, while arguments from high-card points Indicate that he does. There Is a need to be able to associate a degree of certainty with a fact or a guideline. Fortunately one of the most advanced features of AGE Is Its provision of mechanisms for specifying, propagating and updating such certainty factors. When the program Is recoded In AGE this weakness should disappear.

The program In Its present form represents about two man­ months of effort and 13 pages of code. With the exception of the If-then-else rules, the concepts and techniques It uses are standard. This suggests that current Ideas for rule­ based systems, especially when Incorporated In systems with a tutorial capability, have put knowledge engineering within reach of the masses.

ACKNOWLEDGEMENTS

The author Is grateful to Penny Nil and Nelleke Aiello for ac­ cess to the AGE system, and to Peter Friedland for helpful discussions on the Bridge content of the program.