In many games, moves consist of several decisions made by the player. These decisions can be viewed as separate moves, which is already a common practice in multi-action games for efficiency reasons. Such division of a player move into a sequence of simpler / lower level moves is called splitting. So far, split moves have been applied only in forementioned straightforward cases, and furthermore, there was almost no study revealing its impact on agents' playing strength. Taking the knowledge-free perspective, we aim to answer how to effectively use split moves within Monte-Carlo Tree Search (MCTS) and what is the practical impact of split design on agents' strength. This paper proposes a generalization of MCTS that works with arbitrarily split moves. We design several variations of the algorithm and try to measure the impact of split moves separately on efficiency, quality of MCTS, simulations, and action-based heuristics. The tests are carried out on a set of board games and performed using the Regular Boardgames General Game Playing formalism, where split strategies of different granularity can be automatically derived based on an abstract description of the game. The results give an overview of the behavior of agents using split design in different ways. We conclude that split design can be greatly beneficial for single- as well as multi-action games.

We solve open problems concerning the Kleene star <?TeX $L^*$?> of a finite set <?TeX $L$?> of words over an alphabet <?TeX $\Sigma$?> . The Frobenius monoid problem is the question for a given finite set of words <?TeX $L$?> , whether the language <?TeX $L^*$?> is cofinite. We show that it is PSPACE-complete. We also exhibit an infinite family of sets <?TeX $L$?> such that the length of the longest words not in <?TeX $L^*$?> (when <?TeX $L^*$?> is cofinite) is exponential in the length of the longest words in <?TeX $L$?> and subexponential in the sum of the lengths of words in <?TeX $L$?> . The factor universality problem is the question for a given finite set of words <?TeX $L$?> , whether every word over <?TeX $\Sigma$?> is a factor (substring) of some word from <?TeX $L^*$?> . We show that it is also PSPACE-complete. Besides that, we exhibit an infinite family of sets <?TeX $L$?> such that the length of the shortest words not being a factor of any word in <?TeX $L^*$?> is exponential in the length of the longest words in <?TeX $L$?> and subexponential in the sum of the lengths of words in <?TeX $L$?> . This essentially settles in the negative the longstanding Restivo’s conjecture (1981) and its weak variations. All our solutions are based on one shared construction, and as an auxiliary general tool, we introduce the concept of set rewriting systems . Finally, we complement the results with upper bounds.

We present the technical side of reasoning in Regular Boardgames (RBG) language - a universal General Game Playing (GGP) formalism for the class of finite deterministic games with perfect information, encoding rules in the form of regular expressions. RBG serves as a research tool that aims to aid in the development of generalized algorithms for knowledge inference, analysis, generation, learning, and playing games. In all these tasks, both generality and efficiency are important.In the first part, this paper describes optimizations used by the RBG compiler. The impact of these optimizations ranges from 1.7 to even 33-fold efficiency improvement when measuring the number of possible game playouts per second. Then, we perform an in-depth efficiency comparison with three other modern GGP systems (GDL, Ludii, Ai Ai). We also include our own highly optimized game-specific reasoners to provide a point of reference of the maximum speed. Our experiments show that RBG is currently the fastest among the abstract general game playing languages, and its efficiency can be competitive to common interface-based systems that rely on handcrafted game-specific implementations. Finally, we discuss some issues and methodology of computing benchmarks like this.

We propose a new General Game Playing (GGP) language called Regular Boardgames (RBG), which is based on the theory of regular languages. The objective of RBG is to join key properties as expressiveness, efficiency, and naturalness of the description in one GGP formalism, compensating certain drawbacks of the existing languages. This often makes RBG more suitable for various research and practical developments in GGP. While dedicated mostly for describing board games, RBG is universal for the class of all finite deterministic turn-based games with perfect information. We establish foundations of RBG, and analyze it theoretically and experimentally, focusing on the efficiency of reasoning. Regular Boardgames is the first GGP language that allows efficient encoding and playing games with complex rules and with large branching factor (e.g. amazons, arimaa, large chess variants, go, international checkers, paper soccer).