Partition Search Revisited

Streszczenie

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.

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