On pruning search trees of impartial games

Piotr Beling, Marek Rogalski

Artificial Intelligence, volume 283, pages 103262, March 2020, doi: 10.1016/j.artint.2020.103262

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

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.

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