some amenities for alpha-beta

The order in which the possibilities at a node are investigated can have a dramatic effect on the total time complexity of the search. If a good solution is found relatively early on, then a relatively larger number of not-as-good subtrees may be pruned.

In the context of the bridge hand evaluation problem, the set of possibilities at a node is just the set of cards that may be played at that turn. Suit-ordering specifies the order in which the 4 suits are considered as a source for the card to be next played. Dynamic suit-ordering redefines the order of the suits at each turn, thereby taking advantage of the knowledge of the current suit distribution. Rank-ordering specifies the order of the cards within a suit. Dynamic rank-ordering takes into account which cards have already been played during this trick and/or which cards might yet be played during the subsequent plays of this trick.

If two possibilities, p1 and p2, lead to the exact same set of leaf values then, after determining the results of choosing p1, there is no need to expand the subtree of possibility p2. In the bridge problem, rank equivalence refers to the fact that playing either one of two cards will have exactly the same effect. For example, if North has the 9 and 8 of Clubs, then playing the 9 will have the same effect as playing the 8. Dynamic rank equivalence refers to the fact that some cards might initially not be equivalent yet might subsequently become equivalent. For example, if initially North has the 9 and 7 of Clubs and East has the 8 of Clubs then initially the 9 and 7 of Clubs are not equivalent. However, if East plays the 8 of Clubs on the first trick and North retains the 9 and 7 of Clubs then the 9 and 7 of Clubs will be equivalent during the second trick.


Dan Hirschberg
Computer Science Department
University of California, Irvine, CA 92697-3425
dan at ics.uci.edu
Last modified: July 1, 1996