Adversary and Partition Search
Adversary search refers to the issues that arise when trying to
program computers to play games of strategy, like chess and bridge.
Partition search is a technique that can be used to substantially
reduce the portion of a game tree that needs to be expanded by a
computer player. Conventional techniques store positions that have
been evaluated along with their values, but partition search that
incorporates dependency analysis, so that groups of positions
with identical values can be identified as the search proceeds. By
storing a group of positions instead of just a single one, we increase
the number of positions that can be evaluated by table lookup instead
of by search, reducing the running time of the associated algorithm.
CIRL
Partition search was discovered at CIRL, and we continue to work on
extensions to the method. It is also one of the main technical ideas
underlying GIB.
Pointers
-
Partition Search
- We introduce a new form of game search called partition
search that incorporates dependency analysis, allowing
substantial reductions in the portion of the tree that needs to be
expanded. Both theoretical results and experimental data are
presented. For the game of bridge, partition search provides
approximately as much of an improvement over existing methods as
alpha-beta pruning provides over minimax. Written by Matt Ginsberg
and appeared in Proc. AAAI in 1997. Compressed postsript document.
- Parent areas:
- Systematic search
- Implementation:
- GIB
Back to the CIRL Overview Page.