so

$${\mathcal{F}}\vee({\mathcal{F}}\wedge{\mathcal{G}})$$
$$\begin{array}{l l l}{{\mathcal{F}\vee\left({\mathcal{F}}\wedge{\mathcal{G}}\right)}}&{{=}}&{{r\left({\mathcal{F}}\lor r\left\{F_{i}\,\cap G_{j}\right\}\right)}}\\ {{}}&{{=}}&{{r\left(\left\{F_{i}\right\}\cup\left\{F_{i}\,\cap G_{j}\right\}\right)}}\\ {{}}&{{=}}&{{r\left(\left\{F_{i}\right\}\right)}}\\ {{}}&{{=}}&{{r\left({\mathcal{F}}\right)}}\\ {{}}&{{=}}&{{{\mathcal{F}}}}\end{array}$$

since, once again, each element of F ∧ G is subsumed by the corresponding F i .

□
It follows that an implementation designed to compute the value of an imperfect information game as described by Theorem 5.0.7 can indeed use αβ pruning to speed the cmputation.

## 6.5 Bridge Implementation

Given this body of theory, we implemented a single-dummy version of GIB's double-dummy search engine. Not surprisingly, the most difficult element of the implementation was building efficient data structures for the manipulation of elements of 22 To handle this, we represented each element of S as a conjunction. We first identified one of the two hidden hands H, and then for each card c, would write c if c were held by H and ¬ c if c were not held by H . An element of 2 S was then taken to be a disjunctive combination of these conjunctions, and an element of 2 25 was taken to be a list of such disjunctions. The advantage of this representation was that logical inference could be used to construct the reduction of any such list.

In order to make this inference as efficient as possible, the disjunctions themselves were represented as binary decision diagrams, or BDD's (Lind-Nielsen, 2000). There are a variety of public domain implementations of BDD 's available, and we used one provided by Lind-
Nielsen (Lind-Nielsen, 2000). 17 The resulting implementation solves small endings (perhaps 16 cards left in total) quickly but for larger endings, the running times come to be dominated by the BDD computations; this is hardly surprising, since the size of individual BDDs can be exponential in the size of S (the number of possible distributions of the unseen cards). We found that we were generally able to solve 32-card endings in about a minute, but that the running times were increasing by two orders of magnitude as each additional card was added.

This is both good news and bad news. Viewed positively, the performance of the system as constructed is far superior to the performance of preceding attempts to deal with the imperfect information arising in bridge. Frank et.al, for example, are only capable of solving single suit combinations (13 cards left, give or take) using an algorithm that appears to take several minutes to run (Frank, Basin, & Matsubara, 1998). They subsequently improve the performance to an average time of 0.6 seconds (Frank et al., 2000), but are still restricted to problems that are too small to be of mu use to a program intended to play the complete game.