Partition Search Revisited

Piotr Beling

IEEE Transactions on Computational Intelligence and AI in Games, tom 9, numer 1, strony 76-87, March 2017, doi: 10.1109/TCIAIG.2015.2505240

W artykule zaproponowano ulepszenia i uogólnienia algorytmu Partition Search dające dalszą redukcję wielkości drzewa poszukiwań. Przeprowadzono także formalny dowód jego poprawności oraz sformalizowano system podziału gry dla problemu rozgrywki w otwarte karty w brydżu.

Abstrakt

Partition Search to zaproponowana przez Matthew L. Ginsberga metoda przeszukiwania drzew minimaksowych która wykorzystuje związki pomiędzy stanami analizowanej gry. Zastosowana do problemu rozgrywki w otwarte karty w brydżu, umożliwiła, w stosunku do wcześniej znanych metod, redukcję drzewa poszukiwań porównywalną do tej jaką daje algorytm alfa-beta w stosunku do Min-Max. W artykule zaproponowano i zweryfikowano w praktyce ulepszenia i uogólnienia algorytmu Partition Search pozwalające na dalszą redukcję wielkości drzewa poszukiwań. Przeprowadzono także formalny dowód jego poprawności oraz sformalizowano system podziału gry dla problemu rozgrywki w otwarte karty w brydżu.

Bibtex

@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}
}