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 East-West 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 NP-complete [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 North-South 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) North-South is not limited in its entries (ensured by the other suits) and that: ii) East-West will play the best defence, in other words they know not only what cards North-South 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 sub-tree of the game cannot be analysed separately, a phenomenon that Frank [4] calls non-locality.
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 East-West combinations and all possible strategies of declarer.
Take, for example AJ85/Q963. East-West's cards – KX742 – are distributed in a set of cardinal 25 = 32 combinations. The 232 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 n-ary forms, i.e. as many as there are tricks which can be taken. Ginsberg [5] presents the theory of alpha-beta 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 n-ary 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,240th position out of 77, 579 non-inclusive treatments.
In actual games of bridge the situation exists, for the majority of the time, where declarer has some information, however little, about East-West'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 four-handed 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, X-Y, where X = the total number of cards held by North-South, 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 :