On pruning search trees of impartial games

Streszczenie

Artykuł dotyczy obliczania wartości Sprague-Grundy’ego dla krótkich gier bezstronnych, w których przegrywa gracz niemogący wykonać ruchu. Przedstawiamy w nim nowe metody skutecznie przycinające drzewa tych gier, nawet bez wiedzy dziedzinowej na temat badanej gry. Algorytmy te są inspirowane przez α-β, znaną metodę przycinania drzew minimaksowych. Jednak nasze algorytmy dotyczą drzew, których wartości węzłów są przypisywane przez funkcję mex zamiast min/max. Skuteczność naszych algorytmów zweryfikowaliśmy eksperymentalnie w wybranych grach bezstronnych (Nim, Chomp i Cram). Z wyników naszych eksperymentów wynika, że: (1) nasze metody są na ogół wydajne, zwłaszcza gdy tablica transpozycji może pomieścić tylko niewielki ułamek wszystkich pozycji gry (co jest typowe w przypadku większych gier); (2) jeden z naszych algorytmów stanowi bardziej uniwersalną alternatywę dla algorytmu zaproponowanego przez Lemoine’a i Viennot’a.

Publikacja
Artificial Intelligence, 2020, numer 283, DOI: 10.1016/j.artint.2020.103262
Data