

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

Note first that this replacement is sound in the sense that every position that is an instance of the second diagram is guaranteed to have the same value as the original. We have not resorted to an informal argument of the form "Jacks and lower tend not to matter,"
but instead to a precise argument of the form, "In the expansion of the search tree associated with the given deal, Jacks and lower were proven never to matter."
Bridge also appears to be extremely well-suited (no pun intended) to the kind of analysis that we have been describing; a chess analog might involve describing a mating combination and saying that "the position of Black's queen didn't matter."  While this does happen, casual chess conversation is much less likely to include this sort of remark than bridge conversation is likely to refer to a host of small cards as x's, suggesting at least that the partition technique is more easily applied to bridge than to chess (or to other games).

That said, however, the results for bridge are striking, leading to performance improvements of an order of magnitude or more on fairly small search spaces (perhaps 10 6 nodes).

The deals we tested involved between 12 and 48 cards and were analyzed to termination, so that the depth of the search varied from 12 to 48. (The solver without partition search was unable to solve larger problems.) The branching factor for minimax without transposition tables appeared to be approximately 4, and the results appear in Figure 3.

Each point in the graph corresponds to a single deal. The position of the point on the x -axis indicates the number of nodes expanded using α -β pruning and transposition tables, and the position on the y-axis the number expanded using partition search as well. Both axes are plotted logarithmically.

In both the partition and conventional cases, a binary zero-window search was used to determine the exact value to be assigned to the hand, which the rules of bridge constrain to range from 0 to the number of tricks left (one quarter of the number of cards in play). As mentioned previously, hands generated using a full deck of 52 cards were not considered because the conventional method was in general incapable of solving them.  The program was run on a Sparc 5 and Power Mac 6100, where it expanded approximately 15K nodes/second. The transposition table shares common structure among different sets and as a result, uses approximately 6 bytes/node.

The dotted line in the figure is y = x and corresponds to the breakeven point relative to ϧ pruning in isolation. The solid line is the least-squares best fit to the logarithmic data, and is given by y = 1.57x 0.76 . This suggests that partition search is leading to an effective reduction in branching factor of b → t 0 . 76 . This improvement, above and beyond that