On pruning search trees of impartial games

Piotr Beling, Marek Rogalski

Artificial Intelligence, tom 283, strony 103262, March 2020, doi: 10.1016/j.artint.2020.103262

url
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.

Abstrakt

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.

Bibtex

@article{beling:mexcut,
title = {On pruning search trees of impartial games},
journal = {Artificial Intelligence},
volume = {283},
pages = {103262},
year = {2020},
issn = {0004-3702},
doi = {10.1016/j.artint.2020.103262},
url = {https://www.sciencedirect.com/science/article/pii/S0004370218303485},
author = {Piotr Beling and Marek Rogalski},
keywords = {Combinatorial game theory, Game tree, Sprague-Grundy value, Nimber, Mex function, Impartial game, Nim, Chomp, Cram},
abstract = {In this paper we study computing Sprague-Grundy values for short impartial games under the normal play convention. We put forward new game-agnostic methods for effective pruning search trees of impartial games. These algorithms are inspired by the α-β, a well-known pruning method for minimax trees. However, our algorithms prune trees whose node values are assigned by the mex function instead of min/max. We have verified the effectiveness of our algorithms experimentally on instances of some standard impartial games (that is Nim, Chomp, and Cram). Based on the results of our experiments we have concluded that: (1) our methods generally perform well, especially when transposition table can store only a small fraction of all game positions (which is typical when larger games are concerned); (2) one of our algorithms constitutes a more universal alternative to the state-of-the-art algorithm proposed by Lemoine and Viennot.}
}