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.




Playing a suit

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.





Automatic calculation of the possible plays of a suit

Declarer cannot enumerate all the possible opposing worlds and combine the minimax that he calculates with each of them because he will end up with a fusion of strategies [4]. With AQ/32 for example, declarer's objective is simple: make Q in order to take two tricks. Against all the combinations where K is in East (50%), minimax prescribes the finesse: 2xQ; against singleton K in West, minimax prescribes playing 2xA. Declarer knows what to do in each situation but does not know in which situation he is and is thus obliged to take a decision after 2x. As soon as the situation becomes a little complicated, this decision cannot be based on probability criteria equating to choosing the most probable option (here K in West) because it will come up against counter-measures from East-West.
Take the example of K954/AJ32 and the objective of taking four tricks (three tricks can be made at p = 1). After 5X, should one play A or J ? Listing the possible remaining combinations shows that the X could come from 16 possible situations which reduce to 8 distinct worlds (cards of an equivalent value are coded in an identical fashion):

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.




Actual play

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.




References [1] Francis, H.G., Truscott, A.F. (2002) The official encyclopedia of Bridge. 6th edition. New-York : D.A. Francis.
[2] Roudinesco, J.M. (1995). Le dictionnaire des maniements de couleur. Paris : Editions du Rocher.
[3] Frank, I & Basin, D. (2001). A theoretical and empirical investigation of search in imperfect information games. Theoretical Computer Science, 252, 217-256.
[4] Frank, I . (1998). Search and planning under incomplete information : a study using bridge card play. Springer-Verlag, Distinguished Dissertation Series.
[5] Ginsberg, M. (2001). GIB : Imperfect information in a computationally challenging game. Journal of Artificial Intelligence Research, 14, 303-358.



Table 1. Distribution of the possible plays of a suit.

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 :
B = Permutations (AV72-D84 = AD82-V74) ;
C = Cards in addition to useful cards (ADX987-V432 = ADX765-V432);
D = Cards below a sequence in the short hand (RX87-DV = RX32-DV) ;
E = Cards below the weakest useful card (RDV9-864 = RDV9-432);
F = Cards lower than the opponents’ sentinel (AV7-D6 = AV2-D6) ;
G = Twin hands (AD42-R53 = ARD5-432);