Piotr Beling

In this paper, some improvements of the partition search algorithm are proposed.

Partition search is a form of game search, proposed by Matthew L. Ginsberg in 1996, who wrote that the method “incorporates dependency analysis, allowing substantial reductions in the portion of the tree that needs to be expanded.” In this paper, some improvements of the partition search algorithm are proposed. The effectiveness of the most important extension we contribute, which we call local partition search, has been verified experimentally. The results obtained (which we present in the paper) show that using this extension, leads, in the case of bridge, to a significant reduction (almost by half) of the search tree size and calculation time. Another extension we proposed allows for more effective usage of the transposition table (using it to narrow the search window or by cutting more than one entry). Additionally, we contribute a formal proof of the correctness of all presented partition search variants. We draw conclusions from it about a possible generalization of partition search by making the definition of a partition system less restrictive. We also provide a formal definition of a partition system for the double dummy bridge.

@ARTICLE{7346447, author={Piotr Beling}, journal={IEEE Transactions on Computational Intelligence and AI in Games}, title={Partition Search Revisited}, year={2017}, volume={9}, number={1}, pages={76-87}, abstract={Partition search is a form of game search, proposed by Matthew L. Ginsberg in 1996, who wrote that the method “incorporates dependency analysis, allowing substantial reductions in the portion of the tree that needs to be expanded.” In this paper, some improvements of the partition search algorithm are proposed. The effectiveness of the most important extension we contribute, which we call local partition search, has been verified experimentally. The results obtained (which we present in the paper) show that using this extension, leads, in the case of bridge, to a significant reduction (almost by half) of the search tree size and calculation time. Another extension we proposed allows for more effective usage of the transposition table (using it to narrow the search window or by cutting more than one entry). Additionally, we contribute a formal proof of the correctness of all presented partition search variants. We draw conclusions from it about a possible generalization of partition search by making the definition of a partition system less restrictive. We also provide a formal definition of a partition system for the double dummy bridge.}, doi={10.1109/TCIAIG.2015.2505240}, ISSN={1943-0698}, month={March} }