AUTOMATIC TREATMENT OF A SUIT AT BRIDGE
Joël BRADMETZ
Playing a suit at bridge means determining the optimal way for declarer (conventionally sitting South), whose partner is the dummy (sitting North), to play a suit
of 13 cards spread over four hands, of which those of EastWest are unknown, so as to maximise his chances of taking a number of tricks n. Playing a suit is a subject which is fairly
well documented in bridge, although to date, except ScanSuit, there is no program capable of conducting an exhaustive automatic analysis of any position and the judgement of experts
(and the errors they may contain) are the principal references [1,2]. The problem is NPcomplete [3] and requires computation which is exponential in relation to the size of the tree.
The theory of suit treatment is based on one statement of fact and two hypotheses. The fact that any lead in the suit made by one of the opposing players cannot give him an advantage allows the initiative in the game to be limited to the NorthSouth partnership which does not need to fear losing the lead (according to the rules of bridge, the player who leads to a new trick is the one who won the previous one). The hypotheses are that: i) NorthSouth is not limited in its entries (ensured by the other suits) and that: ii) EastWest will play the best defence, in other words they know not only what cards NorthSouth will play but also their strategy. Similarly declarer can, for each possible distribution of his opponents' cards and once he has fixed his own strategy, know his opponents' defensive strategy. For example, South wants to take three tricks with AK32/J98 and he envisages playing low towards the 9 and then allowing the J to win if possible. (It is not his best strategy but he may wish to protect himself against QX which he wrongly believes East to hold). In response to a lead of 2 and holding Q65, West would not play Q as minimax would prescribe, and which would ensure at least one trick, but 5 which, in this case, will bring two.
QX888 (1case); X888/Q (1 case); QX88/8 (3 cases); X88/Q8 (3 cases);
QX8/88 (3 cases); X8/Q88 (3 cases); QX/888 (1 case); X/Q888 (1 case).
Of these 16 cases, it appears that Q is in East in 7 cases and can be taken by playing A followed by J, against only 4 cases in West where it can be taken by a finesse. This ratio of 7 to 4 would thus suggest playing A. However, after 58 a similar analysis would have suggested the finesse. Which means that the opponents, with QX8 in West would save their queen by playing X and with X88 or X8, would save a queen in East by playing 8, and declarer would lose in (almost) all situations. This shows that a subtree of the game cannot be analysed separately, a phenomenon that Frank [4] calls nonlocality.
One can imagine a combinatory analysis of probabilities which envisages all responses simultaneously. Here, the examination of JJ, JA, AJ and AA on 48 and 4X shows success rates of 9/30, 6/30, 5/30 and 7/30 and suggests that whether West plays 8 or X, declarer should always play J. However, this method, valid in this case, risks leading to failure in other cases. Take an example of the leaves on the game tree 432/KJ98 with the objective of taking three tricks.
After 4A87 4QK7 47, two possible EW combinations remain :
The second has a higher probability (.0533 against .0484 at the start of the game and .5238 against .4762 at this stage). Thus North should play J to flush out the X in East if he takes account of the probabilities, but in this case he would lose in both worlds because, in the first, West plays A in the first round (as in the example given above) and in the second he plays 7 to make the X in East, which means that the probability of success goes from .2400 (double finesse for all the cases where QX are in West), to .1550 (these probabilities take account of vacant places, i.e. the number of places available in a hand to receive cards of the suit in question).
The solution to the problem is thus purely combinatory and, for each number of tricks boils down to seeking the subset of combinations which offers the greatest probability of success for a given strategy. In other words, it is necessary to consider all the possible subsets of EastWest combinations and all possible strategies of declarer.
Take, for example AJ85/Q963. EastWest's cards – KX742 – are distributed in a set of cardinal 2^{5} = 32 combinations. The 2^{32 }subsets of worlds of this set must be compared with all the possible strategies. A solution of this problem is to generalise the minimax algorithm for a situation with incomplete information, by playing all the worlds at the same time and by evaluating all the possible tricks in a single operation. For this calculation we have developed a combinatory algorithm on a lattice of disjunctive normal nary forms, i.e. as many as there are tricks which can be taken. Ginsberg [5] presents the theory of alphabeta reduction in such a distributive lattice in the case of a single objective to be attained and his binary lattice can thus be simplified using algorithms of reduction of OBDD (ordered binary decision diagram) and the data structure can be reduced to the subsets themselves and not to the values obtained. This possibility is not open to us and the reduction of disjunctive nary forms is much more complex. Nevertheless, certain pruning operations allow to reduce this time significantly and to arrive at solutions for all the possible distributions (for example, the 660 positions listed in [1] are computed in 80 seconds with a 2 Ghz processor), but the combination in books are simple compared for example with AQ83/X75 for which the best treatment to obtain two tricks (.9516) appear only in 8,240^{th} position out of 77, 579 noninclusive treatments.
In actual games of bridge the situation exists, for the majority of the time, where declarer has some information, however little, about EastWest's cards. A realistic program must take account of this. The ScanSuit program does this, estimating all the possible plays while being able to attribute to an opposing player cards of the suit being played or of another suit (in order to modify the number of places available), taking into account previous discards by any player in the suit concerned, by knowing whether East or West is long and/or strong in the suit, by fixing whether a player has an even or an odd number of cards in the suit, by limiting the available entries for South and/or North. The program also gives the treatment to be used when the overall number of tricks, after being coded as points, is converted into values specific to pairs tournaments or fourhanded tournaments. In the first case, it is necessary to take account of the strategy of the field and in the second, of that of the other table. In both cases, the recommended play may differ from the theoretical one.
A 
B 
C 
D 
E 
F 
G 

0*0 
1 
1 
1 
1 
1 
1 
1 
1*1 
13 
13 
13 
13 
13 
2 
2 
2*1 
78 
78 
78 
78 
23 
3 
2 
2*2 
78 
78 
78 
78 
78 
10 
10 
3*2 
858 
726 
726 
506 
296 
23 
21 
3*3 
286 
286 
286 
286 
286 
56 
56 
4*2 
2145 
1540 
1540 
1540 
349 
27 
23 
4*3 
2860 
2200 
2200 
1705 
1219 
201 
198 
4*4 
715 
715 
715 
715 
715 
330 
330 
5*3 
12870 
7425 
7425 
6303 
3831 
631 
612 
5*4 
6435 
4455 
4455 
3663 
2879 
1723 
1719 
5*5 
1287 
1287 
1287 
1287 
1287 
1287 
1287 
6*3 
17160 
7260 
7260 
7260 
2269 
607 
575 
6*4 
25740 
11880 
11880 
10494 
7288 
7288 
7254 
6*5 
10296 
6336 
6336 
5412 
4495 
4495 
4494 
6*6 
1716 
1716 
1716 
1716 
1716 
1716 
1716 
7*4 
60060 
17640 
17640 
16134 
10484 
10484 
10315 
7*5 
36036 
12936 
12936 
11682 
8799 
8799 
8777 
7*6 
12012 
6468 
6468 
5676 
4890 
4890 
4889 
7*7 
1716 
1716 
924 
924 
924 
924 
924 
8*4 
45045 
8001 
8001 
8001 
3343 
3343 
3212 
8*5 
72072 
14112 
14112 
13077 
9377 
9377 
9271 
8*6 
36036 
9702 
6104 
5564 
3627 
3627 
3626 
8*7 
10296 
4752 
1638 
1428 
1097 
1097 
1096 
8*8 
1287 
1287 
252 
252 
252 
252 
252 
9*5 
90090 
8820 
6376 
5951 
2259 
2259 
2220 
9*6 
60060 
7350 
3275 
3015 
1502 
1502 
1501 
9*7 
25740 
4950 
1290 
1135 
668 
668 
667 
9*8 
6435 
2475 
385 
329 
242 
242 
241 
9*9 
715 
715 
70 
70 
70 
70 
70 
10*5 
36036 
1596 
389 
379 
101 
101 
101 
10*6 
60060 
2940 
714 
692 
192 
192 
191 
10*7 
34320 
2400 
597 
511 
192 
192 
191 
10*8 
12870 
1650 
258 
218 
116 
116 
115 
10*9 
2860 
880 
90 
75 
53 
53 
52 
10*10 
286 
286 
20 
20 
20 
20 
20 
11*6 
36036 
588 
64 
62 
19 
19 
18 
11*7 
25740 
540 
64 
62 
19 
19 
18 
11*8 
12870 
450 
60 
59 
19 
19 
18 
11*9 
4290 
330 
50 
40 
19 
19 
18 
11*10 
858 
198 
21 
17 
12 
12 
11 
11*11 
78 
78 
6 
6 
6 
6 
6 
12*6 
6006 
28 
4 
4 
2 
2 
2 
12*7 
10296 
48 
6 
6 
3 
3 
2 
12*8 
6435 
45 
6 
6 
3 
3 
2 
12*9 
2860 
40 
6 
6 
3 
3 
2 
12*10 
858 
33 
6 
6 
3 
3 
2 
12*11 
156 
24 
5 
4 
3 
3 
2 
12*12 
13 
13 
2 
2 
2 
2 
2 
13*7 
1716 
1 
1 
1 
1 
1 
1 
13*8 
1287 
1 
1 
1 
1 
1 
1 
13*9 
715 
1 
1 
1 
1 
1 
1 
13*10 
286 
1 
1 
1 
1 
1 
1 
13*11 
78 
1 
1 
1 
1 
1 
1 
13*12 
13 
1 
1 
1 
1 
1 
1 
13*13 
1 
1 
1 
1 
1 
1 
1 
Total 
797162 
159094 
127842 
116477 
75073 
66728 
66141 
Legend :
The first column shows the hand, XY, where X = the total number of cards held by NorthSouth, Y = the number of cards held by south.
A = Total number of hands with South >= North; In each successive column the number of hands corresponding to the reductions given below is subtracted :