{'fraction_non_alphanumeric': 0.032838492639116076, 'fraction_numerical': 0.005740563562852998, 'mean_word_length': 4.808892076012908, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient Reasoning in Regular Boardgames

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.


I. INTRODUCTION
The idea of a generalized game playing (GGP) program, the one with the ability to successfully play any given game even such that it has not seen before, may be seen as a direct descendant of the famous General Problem Solver created by Simon, Shaw, and Newell in 1959 [1]. Although the first published formalism starting a new domain of GGP research is a work from 1968 by Pitrat [2] concerning a generalization of chess-like games, which was followed in the 90s by Pell and his Metagame approach [3], the real attention towards the idea started in 2005 with the publication of Stanford's Game Description Language (GDL) and the announcement of the annual International General Game Playing Competition (IGGPC) co-located with AAAI conference [4], [5]. Since that time, for almost a decade, Stanford's GGP had been the leading field for developing generalized AI solutions, and a source of numerous advancements in search [6], [7], knowledge representation [8], [9], and other fields [10], [11]. In 2016, the last (so far) IGGPC was held, given the number of GDL-related publications was steadily decreasing, as researchers started shifting their attention to other topics. Today, however, we apparently experience a General Game Playing renaissance. In just a few years, several alternative languages and platforms had been released -by multiple author groups, featuring a variety of game types, based on diverse methodologies, and with different purposes under consideration.
In this work, we present the technical side of reasoning in Regular Boardgames (RBG) language -a universal 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 in development of general algorithms for games, which includes knowledge inference and game analysis, learning, and playing algorithms. In all these tasks, both generality and efficiency are important. Generality is necessary to avoid solutions designed only for specific game types, which have no chances to work on a new, and previously unpredicted problem instances. Computational efficiency makes every task more feasible, allowing e.g., a more detailed analysis of the search tree -which increases the playing strength of an AI agent.
RBG tries to achieve both goals. We explain how it reaches a high level of performance, competitive even with some manually implemented reasoners, while still describing games completely in a general abstract form. We present the insights of the RBG compiler and its optimizations.
Then, we perform an in-depth efficiency comparison with other popular and currently developed GGP systems. Additionally, we include in the comparison our own highly optimized game-specific reasoners of a few games under RBG interface. The results from the benchmarks can be used as a point of reference for both implementing a reasoner for a given game and developing new general game playing systems. In the former, one can compare the efficiency of a game implementation against various levels of optimization. As for the latter usage, any GGP approach to be practical requires some amount of fast reasoning. This efficiency survey shows where such a system fits regarding its computational capabilities, and on what types of games it behaves better or worse. It also points out the set of games that is good to implement when aiming to compare with other GGP systems. Finally, we discuss issues and methodology of producing such benchmarks, such as the impact of altering the formal game rules for different variants.

II. REGULAR BOARDGAMES
We briefly describe the main concepts of Regular Boardgames. For the full formal definition, we refer to [13].
A game embedding in RBG consists of a board, variables, player roles, and rules. The game state contains a configuration of pieces on the board, values of the variables, the current player, the current position on the board, and the current index (position) in the rules. The board is a directed graph with labeled edges, called directions. The current player, in his turn, can perform a sequence of elementary actions, which, when applied sequentially, can modify the game state in a specific way. For an action to be legal, it must be both valid for the current game state when it is applied and also permitted by the rules. There are seven types of actions: 1) Shift, e.g., left or up, which changes the current position on the board following the specified direction. When there is no such edge, the action is invalid. 2) On, e.g., {whiteQueen}, which does not modify the game state but checks if the specified piece is on the board at the current position. 3) Off, e.g., [whiteQueen], which puts the specified piece at the current position on the board. It is always valid. 4) Comparison, e.g., {$ turn==100}, which compares two arithmetic expressions involving variables. 5) Assignment, e.g., [$ turn=turn+1], which assigns to a variable the value of an arithmetic expression. 6) Switch, e.g., ->white, which changes the current player to the specified one. This action ends a move. 7) Pattern, e.g., {? left up}, which is valid only if there exists a legal sequence of actions under the specified rules; in the example, if from the current square there is a path with two edges labeled by left and up. A sequence of actions ending with a switch defines a move. Example 1: In Amazons, the following sequence of actions defines a move with a (white) queen moving two squares up and then shooting an arrow one square right. Technically, a move is the subsequence of (indexed) actions that are offs, assignments, and switches, together with the positions in rules regular expression where they are applied. These are precisely the actions that modify the game state, except the board position and the rules index. Hence, the above example defines a move of length 4.
A playout ends when the current player has no legal moves. Then, each player's score is given in a dedicated variable, named the same as the player's role. The rules are given by a regular expression over the alphabet of the above actions. The language defined by this expression contains all potentially legal sequences of actions. For a concise encoding of the regular expression, a description in RBG is described through C-like macros that are instantiated for given parameters.

A. Example
A complete example of game Amazons is given in Fig. 1. Its underlying nondeterministic finite automaton, processed by the game compiler, is shown in Fig.2.
At the beginning of the description (Fig. 1, lines 1-14) we define the players (and their maximal achievable scores), pieces, variables (note that variables for players, containing their current scores, are created automatically), and the board graph with its initial state -in this case a rectangular board with four possible movement directions. Then we define some helpful, game-dependent macros. anySquare can change the current position to any square on board, by first jumping an arbitrary number of squares vertically, and then horizontally. directedShift allows movement in direction dir (given as a parameter) as long as the encountered squares are empty (they contain piece e), but at least one step has to be made. queenShift encodes all possible queen-like moves as a sum of directed shifts. Note that we can pass any sequence of tokens as a macro argument (in this case, two consecutive directions that allow us to encode diagonal movements).
The main game logic, the turn macro (lines 23-28), encodes a single turn for player me, whose queen pieces are encoded as piece. It starts by switching the player to ourselves, then switching the current square to any that contain our queen. We pick up the queen making this square empty, move it to the desired square, and put down. Then we find another square that will be the destination for an arrow. The ->> gives control to the game manager (special role named keeper), as the player has no more decisions to make. The remaining steps put down the arrow (the x symbol) and set the winning score for the last player. If the playout ends because the current player has no legal moves, this stage will not be reached and the previous player will win the game. Finally, the overall rules of the game are encoded as a repetition of the sequence of the white and the black player turns (line 29).

III. OPTIMIZATIONS IN RBG
The core of the RBG infrastructure is the compiler, which, given an RBG game description as the input, generates a C++ module implementing a reasoner for this game. As in every GGP system, the reasoner satisfies a common interface, which, ) 29 #rules = (turn(w; white; black) turn(b; black; white)) * in the case of RBG, allows computing legal moves, reading parameters, accessing the board, etc.
A fundamental part of the reasoner is computing a list of all legal moves. This is done through a DFS-based algorithm [13,Theorem 9] on the automaton that is the NFA representing the game rules joint with the board graph. A straightforward implementation of the algorithm already provides a decent level of efficiency, but, through a prior analysis of the game rules, we were able to improve it significantly. We describe here a few of the most important optimizations, which are obtained by inferring knowledge from the game description. Table I shows the results of four techniques.
1) Shift tables: Very often, traversing the board consist of multiple shift actions, representing even complex behavior. For instance, on a rectangular board, (left * + right * )(up * + down * ) allows changing the current square into any square, and up * {! up} changes the square to that in the top row but in the same column. Obviously, the number of possibilities from such sequences is limited. Each sequence of actions consisting only of shifts and possibly patterns with shifts can be represented by a map that, for each given square, stores a subset of allowed destination squares. Hence, we replace each such sequence with one elementary shift table action, which simply enumerates all the possibilities with non-deterministic transitions. Additionally, we can generate further simplifications if the shift table is deterministic or does not depend on the current square.
Shift tables as a whole are the most important optimization, which significantly affects every game.
2) Visited check skipping: The basic reasoning algorithm requires that we check whether a pair of the current square and the index in the rules has been already visited. Consider for in-...
which checks whether from the current square there is a path on squares with x to the north-west line (example from Hex). Obviously, by applying actions we could return to the same square and the same position in the rules. However, in many typical cases, this is not possible. We can detect these cases by analyzing the transitions in the joint automaton, and omit checking visited pairs.
3) Bounding move length: Because of the straightness condition that RBG description must satisfy [13], guaranteeing that the game is finite and the number of legal moves if always finite, the moves have a bounded maximal length measured in the number of modifiers. For instance, in breakthrough, each move has length 2, which corresponds to the selection of the initial (picking up the pawn) and the destination squares. In chess, the maximum move length is 7. We can use the limit directly to define the move type structure having exactly this optimal size, also avoiding any dynamic memory allocations. We can easily calculate this limit if the joint automaton does not contain cycles containing a modifier and not containing a switch. For such games, we have a usually small upper bound on the length of every move. In other case (an example is the draughts family of games), such cycles could potentially generate infinite moves, thus the straightness condition must be satisfied non-trivially, and calculating the limit in general is a PSPACE-hard problem (cf. [13,Theorem 10]).
4) Monotonic classes of moves: Sometimes, especially in simple games, the bottleneck is the general interface itself. In the case of RBG compiler, all legal moves must be generated every time from scratch. Besides advantages like preserving minimal game state representation, informative move content (which contains a sequence of actions, in contrast to, e.g., a pure move index), fixed ordering, and modifiable moves list, it comes with an efficiency drawback in certain situations. In the case of simple games with many moves, the cost of generating them can be prevailing and thus get behind systems that admit, e.g., only modifying the list of legal moves.
We develop the general concept of monotonicity classes, which can deal with the above problem in several game types. We will split the game states into classes such that they share their legal moves. Let S be the set of all reachable game states from the initial state, and for S ∈ S, let moves(S) be the set of all legal moves. Let M = S∈S moves(S) (the set of all possible moves). Now we define that a function c : S → N is monotonic classifier if for every state S ∈ S, we have moves(S ′ ) ⊆ moves(S) for every state S ′ ∈ S that is a successor of S in the game tree with c(S) = c(S ′ ). There always exists a trivial monotonic classifier that assigns a different class number to each state. However, the smaller number of assigned classes is better. A game description is k-movemonotonic if there exists a monotonic classifier assigning at most k class numbers. Obviously, the existence of monotonic classifiers depends on the particular move representation.
Returning to RBG, a natural candidate to classify moves are switches. For each switch, we need to check whether for a game state with the rules index at this switch, the legal moves are a superset of the legal moves of every successor game state. We use several conditions for that, for example, if a move is related to the specific content of a square (e.g., empty) and, in the rules, this content is never added, then there will be no new moves in the successor game states. The monotonicity optimization also requires shift tables to detect if moves do not depend on the current square. Using that, we can determine that the game descriptions of, e.g., Connect4, Gomoku, and Hex (without the pie rule) are 2-monotonic. Also, in Pentago (split), we assign one monotonic class for the moves related to rotation (the eight rotation moves are invariant), despite that the placement moves cannot be assigned to the same class. Table I shows the impact of the described optimizations. We show their importance in the final version by the efficiency drop if an optimization is skipped. The effects of the optimizations strongly correlate. Monotonic classes optimization requires shift tables, thus there is no result for a variant with only shift tables skipped. Also, as described before, some optimizations (monotonic classes, bounding move length) provide a boost only for specific types of games, and are neutral for all the remaining ones; these cases are represented by 0%.

A. Efficiency Gain
The most significant and universal optimization is shift tables. The second one, not much behind it, is visited checks optimization. They both affect every game. Bounding move length is a decent optimization and affects only games where moves have a bounded length by the rules and independently on the board, but this is actually a large class of games. Monotonic classes affect only simple games where moves are very straightforward, but these are usually the cases where listing all moves adds a significant computational cost.
Optimizations positively affect the computation time because they mostly reduce the amount of the generated C++ code, whose compilation is by far dominant. For example, Chess with optimizations is compiled in 7.2s and without them in 10.43s. In general, all the first three optimizations reduce the compilation time, and monotonic classes leave it unaffected. Except for monotonic classes, which require to store moves along with the game state, the optimizations do not have any real drawbacks, thus they should always be used.

A. Other GGP Approaches
Here we present in slightly more detail GGP systems that will be used in our experiments. We can describe those systems as belonging to three types of GGP approaches: "true" general game playing, where the description language is "closed" (e.g., GDL, Toss [20], Regular Boardgames); "hybrid", that describe games using an extendable set of generalized keywords (Metagame [21], Ludi, VGDL [22], Ludii); and one that just make use of a common interface for game-specific implementations (Ai Ai, GBG, OpenSpiel, Polygames). These categories are informal. Closed languages try to provide a uniform and minimal mechanism so that each new game can be effectively implemented purely in the proposed language. Hybrid languages try to provide high-level concepts that cover parts of game rules. As such, implementing a new game that requires a new rule type usually needs an extension of the language. The last type of systems just requires games to be manually implemented in a usual programming language and satisfying some interface. They also often provide parameterization of the rules. In theory, more game-specific code allows more optimization, thus should result in higher efficiency.
The GGP systems we have chosen for the comparison are the ones that are possibly very recent, currently developed, and containing enough games to find a common test set, with the exception of GDL, which is a classical example. Besides Regular Boardgames, there has been no recent approach to create a closed language for describing a large class of games.
We also performed experiments with OpenSpiel [15], however, given that this system during the playouts also computes observation tensors makes the comparison unfair. Thus, we decided not to include the results in this paper. Apart from the other GGP systems that we described above, for some games we had developed game-specific reasoners (in C++) that implement the common RBG interface (currently, the part of it necessary for computing moves and states). This is an attempt to show possibly maximal reasoning efficiency. The implementations are highly optimized with a lot of lowlevel tricks designed for a single specific game.
1) Stanford's GDL: GDL [5], used in IGGPC, is the most well-known and deeply-researched game description language. It can describe any turn-based, simultaneous-moves, finite, and deterministic n-player game with perfect information. It is a high-level, strictly declarative language based on Datalog.
GDL does not provide any predefined functions, meaning that every predicate encoding the game structure must be defined explicitly from scratch. As a result, the game descriptions are usually long and hard to understand. Because their processing requires logic resolution, it is also very computationally expensive. In fact, many games expressible in GDL could not be played by any program at a decent level. Some games, due to computational cost, are not playable at all. For example, features like longest ride in checkers or capturing in go are difficult and inefficient to implement. In such cases, only simplified rules are encoded (yet often they are available in repositories under the standard name of the full game). GDL has a number of independent reasoner implementations, among which propnets [23] are considered the fastest.
2) Ludii: Although the Ludii system [14] (the successor of Ludi, used to generate first market-selling AI-authored boardgame [24]) has been designed primarily to chart the historical development of games and explore their role in human culture, its latest versions came out with additional tools for agent implementations, game visualizations and human playing [25]. The language is based on a large number of ludemes, conceptual units of game-related information, whose behavior is encoded in the underlying Java implementation. This makes the resulting games usually concise and well suited for tasks such as procedural content generation, but hard to understand without documentation of each ludeme, which is already very long and constantly growing. Another drawback is that a large but limited set of currently implemented ludemes greatly hampers natural expressiveness and efficiency of more complex and non-standard games that do not have dedicated highly specialized building-blocks. On the positive sides, Ludii comes with a large number of implemented games. The language allows generation of generalized game-related content such as human-playable GUI and various game/algorithm analyzing tools. High-level ludemes are also an easy source of heuristics, which Ludii agents can benefit, without the need to detect game features in a knowledge-free manner.
The efficiency is similar to that of a GDL propnet, sometimes overcoming the latter. Ludii is closed-source with one reference implementation provided, and due to the complication level, it is impractical to develop an independent branch.
3) Ai Ai: Stephen Tavener's Ai Ai [12] is a closed source program that allows playing abstract games versus both AI and human opponents, with user-friendly visualization, multiple options to customize, AI settings, and game analysis tools. It is an advanced platform containing many games, and more are being added all the time. Games can be hand-coded in Java (for efficiency), or assembled from large blocks using the MGL (Modular Game Language) -a scripting language based on JSON. In practice, almost all of the games are programmed directly in Java, so the resulting game engine is as fast as its underlying implementation is optimized. Thus, although it is considered as a general game playing approach, the reasoners are game-specific with a common interface.
Each test (one game) was a run of the flat MC algorithm, yielding statistics of the average score of uniformly random playouts for each legal move from the initial state of the game, or just a run of random playouts for a given time, depending on the system. The preprocessing time was not counted in any case. The GGP system versions were the available ones up-to-date on 4th June, 2020. Each GDL propnet test constitutes of the average time of 10 runs lasting 10 minutes, not counting the preprocessing (averaging is a proper practice here, because of non-deterministic propnet construction). The used propnet implementation is by C. Sironi based on ggp-base, currently not available online, but some results were reported independently [23].
Each Ludii 0.9.3 test was performed via the commandline option --time-playouts with default settings and 1 minute measuring time.
Each Ai Ai 4.0.2.0 test was performed through the dedicated menu option MC Playouts/Second (This Game), which measures over 100 seconds.
Each RBG 1.2 test lasted 1 minute and was performed via the shared benchmark script ( rbg2cpp/run_benchmark.sh). A test of an RBG game-specific reasoner was also 1 minute long, and it was compiled with the same overlaying benchmark procedure used for RBG; the package is included in RBG 1.2 release. This version contains all optimizations described in Section III. Table II shows the results of the main experiment. There is a large gap between systems with abstract languages (GDL, Ludii) and systems with game-specific implementations (Ai Ai). RBG achieves similar performance to the latter, although the values strongly vary depending on the game, which could be explained by various levels of effort put in optimizing a game-specific implementation. Our game-specific implementations are faster than almost everything else, showing that automatically generated RBG reasoners still have optimization potential, as the RBG interface is currently not a barrier.

V. IMPACT OF METHODOLOGY
In [26] we pointed out several issues concerning the methodology of the benchmarks in GGP; here, we discuss two technical ones that particularly affected our experiment.

A. Influence of the Rules Implementation
An important issue is game matching, which needs special care among different systems. By the same games we understand those that have isomorphic game trees. This includes win/draw/loss distinction in terminal states. We made an effort to match the games in RBG with the existing implementations in GDL. In the other systems, some games have encoded a different variation of the rules. Up to our knowledge, we marked all these cases in Table II with a star. These differences are relatively minor to provide a meaningful comparison, basing on our subjective opinion and some internal tests with game variations. A possible exception is Chess and Arimaa in Ai Ai; they implement, among others, the threefold repetition rule, which is costly. Also, Canadian Draughts in Ludii is a split version. Nevertheless, the results could differ slightly under an exact match. Example: English Draughts (split) in RBG and GDL ends in a draw after 20 moves without moving a man nor a capture. However, in Ludii, instead of that, there is an internal hard turn limit set independently on the rules. This is a minor difference, as ending a random playout in this way is rare. As it is sadly not a standard for GGP systems to provide exact specification of the rules or reliable game statistics, most of such disparities are very hard to spot, thus they influence the fairness of the published benchmarks. Here, we would like to show some more detailed examples of how heavily the reasoning efficiency can be altered by modifying the game rules without changing their commonsense meaning.
Let us continue our example of Amazons. The orthodox version under the standard interpretation is that the player's single turn consists of moving a queen and shooting an arrow. Thus, the first player has 2176 possible moves, and the average branching factor is 374 for the first player and 299 for the second [27]. However, some implementations modify the rules so the player turn is split in two: firstly a queen movement is selected, and then an arrow shot from this queen. This interpretation operates on the game tree that is not isomorphic with the orthodox version, but it considerably reduces the branching factor thus computation time [28]. The rules in RBG encoding the described variant are shown in Fig. 3. Compared to the orthodox version, in RBG, this split2 approach allows more than 6 times faster simulations (see Table III).
Although split2 is, thanks to its straightforwardness, the most popular unorthodox variant, there are many other possible reinterpretations of the rules. Another example based on splitting player's move into two parts (split2a in Tab. III) chooses a queen and its movement direction in its first part, and shifts all the remaining operations to the second part. This version reaches similar efficiency as its predecessor. However, it is possible to create other variants that will be significantly faster. A variant named split5 (see Fig. 3 for its rules) starts a new turn after nearly every atomic choice that guarantees the correctness of the remaining playout. This variant is over two times faster than split2. Table III shows the results for even more variants based on the same orthodox encoding of Amazons, visualizing the possible impact of the splitbased trick we described. All mentioned Amazon variants are available in the RBG repository; they are obtained by a minor modification of the encoding of the orthodox version.

B. Random Generators and Benchmark Procedures
When doing many simulations, the overlaying interface becomes meaningful. We show this on a particular part that is the random generator used to draw moves uniformly in flat MC. This issue has never been raised before, but it is quite noticeable when the number of turns per second is large enough. In Table IV, we demonstrate the possible impact of the generator, which includes the random generator itself and an unbiased method for drawing an integer from a range. There is the standard method combining std::uniform_int_distribution with std::mt19937 (used in the tests for Tables I-III), a reimplemented Java method from java.util.Random, and a modern unbiased drawing algorithm by Lemire [29] combined with a fast Mersenne Twister boost::random::mt11213b.
In our experiments, for RBG, we have used the default method, which is usually the slowest of the three but probably of the highest quality (based on the traditional measurement of the period). The propnet, Ai Ai, and most likely also Ludii, use the standard Java generator. Of course, there is a tradeoff between the quality and the speed, and different systems use different methods. From our experience, the choice of reasonable generator does not influence the quality of agent nor change the statistics, but it impacts the cost of computing. The impact becomes higher when the reasoning itself is faster. In extreme cases, as Connect4, the cost of random move selection can be dominating.
The issue does not concern only random generators, but the whole benchmark procedure (with time measurements, gathering statistics, etc.). For instance, the flat MC algorithm in Ai Ai for Connect4 performs a much larger number of iterations per second (we got even 3,428,427) than the benchmark report, while other, more costly games reveal no noticeable difference.
Concluding, when reaching such a performance level, it is difficult to provide a reliable benchmark. Nevertheless, in such cases, we can expect that the cost of reasoning would be negligible compared to any accompanying computation, and then, the efficiency of reasoning loses its importance.

VI. CONCLUSION
Regular Boardgames is a modern general game playing system aiming for efficiency and describing games via an abstract, concise, and well-defined formal language. The shared environment currently consists, in particular, of the game compiler to C++, a network-based game manager, and a highlevel API allowing writing AI in Python. In this paper, we have described a few optimizations of the RBG compiler, as one of the sources of its efficiency. We performed extensive experiments comparing the efficiency of five modern general game playing systems. We conclude that RBG significantly outperforms systems based on other abstract languages and has comparable (with a high variation) performance to game-specific reasoners of other systems as Ai Ai. By comparing with our hand-made gamespecific reasoners under the same interface, we demonstrated that there is still potential for optimization. This leads to the following research question: given game rules, how to automatically produce an optimal reasoner? Our implemented optimizations so far are just an infantile play around it.
The final issues discussed, so far overlooked, should help in developing standardized benchmark methods concerning reasoners, which would allow fair, reproducible, and transparent comparisons.