An Upper Bound on the Complexity of Tablut

Abstract

Tablut is a complete-knowledge, deterministic, and asymmetric board game, which has not been solved nor properly studied yet. In this work, its rules and its characteristics are presented, then a study on its complexity is reported. Dividing the state-space of the game into subspaces according to specific conditions, an upper bound to its complexity is eventually found. Since this upper bound is comparable to the one found for Draughts, the open challenge of solving this game seems to require a considerable computational effort.