General Board Game Concepts

Many games often share common ideas or aspects between them, such as their rules, controls, or playing area. However, in the context of General Game Playing (GGP) for board games, this area remains under-explored. We propose to formalise the notion of"game concept", inspired by terms generally used by game players and designers. Through the Ludii General Game System, we describe concepts for several levels of abstraction, such as the game itself, the moves played, or the states reached. This new GGP feature associated with the ludeme representation of games opens many new lines of research. The creation of a hyper-agent selector, the transfer of AI learning between games, or explaining AI techniques using game terms, can all be facilitated by the use of game concepts. Other applications which can benefit from game concepts are also discussed, such as the generation of plausible reconstructed rules for incomplete ancient games, or the implementation of a board game recommender system.


I. INTRODUCTION
Since the foundation of Artificial Intelligence (AI), games have often been used as testbeds for major advancements [1]. This can be explained by their simplicity and popularity, but also because, as humans, we can perceive the problems (game interfaces) and their solutions (strategies). In the field of game AI, two agent types can be distinguished. Dedicated Game AI agents designed for a single game (or a small set of games) and General Game AI agents built to play any arbitrary game.
Game-specific agents have been studied since the beginning of the AI field [2], [3] and are often used as benchmarks of well-known problems. For example, many single-player games, commonly called puzzles, are interesting illustrations of planning problems (e.g. Rubik's Cube [4] or Sokoban [5]) or Constraint Satisfaction Problems [6]. Similarly, multiplayer games are representations of many different AI research areas (Knowledge Representation, Reinforcement Learning, Transfer Learning, etc.) which lead to the development of many game AI agents trying to outperform human players. Nowadays, computer players for classical board games like Chess [7], Go [8], Shogi [9] or Checkers [10], can defeat expert human players. Even for stochastic games like Backgammon [11], games with incomplete information like Poker [12], or video games like Starcraft II [13], computer players have reached an excellent level of play. The success of these dedicated game-playing programs has demonstrated their capacity to outperform humans, marking a milestone in artificial intelligence research [8], [14]. However, they are often highly reliant on game-specific knowledge and expertise, preventing them from playing other games as effectively.
Building general game AI agents that perform well on any board game, rather than being specialised, is the aim of General Game Playing (GGP). These general game AI agents are implemented without knowing the games they will play in advance and consequently, they cannot use specific pre-defined knowledge about them when playing the game. This differs greatly from dedicated game AI agents, as the AIs developed for specific games are often biased by human-developed heuristics. Unfortunately, humans still tend to outperform AI in general board games. This can be explained by the human capacity for understanding common aspects between games and consequently being able to learn new games quicker by detecting common points with previously played games.
This paper introduces board game concepts for GGP through the Ludii general game system. These concepts are expressed in game terms commonly used by game players and designers, making them an interesting mechanism for providing human-understandable explanations of different AI techniques. These concepts can be associated with several levels of abstraction, such as the game itself, a game trial, a game state, or individual moves. This opens many new possibilities for different AI research topics, including agent selection, transfer learning between games, AI explainability, as well as game generation, reconstruction, and recommendation.
The remainder of this paper is organised as follows: Section II describes the field of GGP and the different general game systems proposed so far. Section III describes the Ludii system as well as the ludeme-based language used to describe the games and the reasons behind its use for identifying game concepts. Section IV highlights the notion of game concepts in the context of Ludii, how they are modelled and computed for each game. Section V proposes several GGP research directions which can benefit from our proposed game concepts. Finally, Section VI concludes the paper.

II. BACKGROUND A. General Game Playing
In Artificial Intelligence, the General Game Playing (GGP) challenge [15] is to develop computer players that understand the rules of previously unknown games, and learn to play these games well without human intervention in situations where its knowledge of the games rules, objectives and strategies is limited to the game description. Developing these general agents, and the AI techniques behind them, is vitally important in the development of real-world agents which can deal with unpredictable and novel situations. For this reason, General Game Playing is seen as a necessary step on the way to Artificial General Intelligence (AGI) [16].
Historically, the first GGP model is defined in 1968 by Jacques Pitrat [17] to describe two-player games with complete information and rectangular boards. Then, only from the '90s, other work on General Game systems appeared such as SAL [18], Metagamer [19], Hoyle [20], and Morph-II [21]. After the turn of the millennium, more modern General Game systems started appearing such as Multigame [22] in 2001 and Zillions of Games [23] in 2002.

B. General board Game Languages
Many GGP systems describe their games using a standardised game description language. Different game descriptions are written in different formats and with different levels of abstraction, lending themselves to different kinds of knowledge representation, reasoning, and learning approaches (such as for performance reasons).
1) GDL: Since 2005, the Game Description Language (GDL) [24] and the GGP-Base platform [25] proposed by the Stanford Logic Group 1 has become one of the main standards for academic research in GGP. The purpose of GDL is to provide a generic language for representing any board game [26], including collaborative games and games with simultaneous actions. GDL describes the games in a language inspired by Prolog, using first-order logical clauses. An extension named GDL-II [27] has been developed to handle games with partial observations and stochastic actions, and another extension named GDL-III [28] for epistemic games. This formalism and platform have provided a high-level challenge which has led to important research contributions [29], [30] especially in Monte Carlo tree search (MCTS) enhancements [31], [32], with some original algorithms combining constraint programming, MCTS, and symmetry detection [33]. These techniques have lead to the development of several General Game AI agents that perform well on specific games (e.g. Gamer [34], CadiaPlayer [35], ClunePlayer [36], WoodStock [37], etc.).
Unfortunately, GDL also has some negative points. This includes poor efficiency [38], the fact that each element of the game has to be defined tabula rasa and cannot easily be taken from previously modelled examples, and verbose game descriptions that are not representative of any game-related aspects that human players typically use. The opaque and low-level character of GDL descriptions, without any shared semantics or high-level concepts being explicitly recognisable between games, forms a challenge for tasks such as the creation of mappings between games for transfer learning, or the generation of human-understandable explanations about any aspect of a game. 1 Stanford Logic Group: logic.stanford.edu/ 2) RBG: The Regular Boardgames (RBG) system [39] proposes the idea of encoding piece movement for games using a regular language. This formalism can describe any finite deterministic game with perfect information excluding simultaneous moves. RBG game descriptions are typically much short than their GDL counterparts, making it much easier to model complex board games (e.g. Chess, Go and Arimaa). RBG also runs substantially faster than GDL, averaging over 50 times as many playouts during a recent comparison [38].
3) Ludii: The Ludii system 2 , named after its predecessor LUDI [40], is a complete general board game system, that can model games as a tree of ludemes. The decomposition of games into their conceptual units of game-related information ludemes [41] results in more intuitive games descriptions compared to prior GGP systems. The number and variety of board games that are implemented within Ludii also go far beyond those presented by most prior general game systems [42]. Ludii is capable of modelling the full range of playable GDL games, as well as stacking games, boardless games, and games with hidden information. This, combined with high efficiency compared to other general systems [38], makes Ludii the ideal system for investigating the new game concepts-based research directions discussed in this paper.

C. Related Work
In the context of game AI research, prior work on feature extraction has been predominantly focused on video games. This includes more general frameworks such as the General Video Game AI (GVGAI) system [43], [44], but also specific video games such as Angry Birds [45] and Starcraft [46]. These papers used their extracted features to predict the performance of different agents on unknown games, creating a portfolio or ensemble agent that combines the strengths of multiple AI techniques.
Despite the demonstrated advantages of this approach, little work has been done on feature extraction for general board games. Banerjee and Stone [47] proposed a reinforcement learning game player interacting with the GGP-base system, which can transfer knowledge learned in one game to expedite learning in other games. This work is based on valuefunction transfer [48] where general features are extracted from the state space of a previous game and matched with the different state space of a new game. This work showed good performance for low-level features on small games, but only for a limited set of specific types of source-target pairs where appropriate state space mappings can be automatically detected based on GDL game descriptions [49].
Some of the best General Game Playing players based on GDL have shown the importance of heuristics and game features by using them to improve their performance during GGP competitions. ClunePlayer used heuristic evaluation functions to represent simplified games as abstract models, incorporating the most essential aspects of the original game to construct tailored heuristics [36]. CadiaPlayer used template matching to identify simple board game features, such as square tiling or specific piece types [35]. Each of these agents won the International General Game Competition [50], in 2005 for ClunePlayer and 2007, 2008, and 2012 for CadiaPlayer.

III. LUDII
Ludii 3 uses a class grammar approach [51] to provide a direct link between the keywords in its game descriptions and the underlying Java code that implements them. The core of Ludii is a ludeme library, consisting of several classes, each implementing a specific ludeme. Ludemes are used to define both the form of the game (rules and equipment) and its function (legal moves and outcomes for the end state).
Each game description is composed of three different sections which define the relevant information about the players (number, facing direction, etc.), the equipment (board, pieces, etc.), and the rules of the game. The rules of the game can also be decomposed into four specific sub-sections: • Meta-rules applied to each state (e.g. no repetition). • Starting rules defining the initial state. • Playing rules defining the legal moves for a state s. • Ending rules defining the conditions under which the game's outcome is determined. An important benefit of this representation is that it allows each game description to be expressed in a compact and human-understandable manner by hiding unnecessary implementation details [52]. Figure 1 shows Ludii game descriptions for the board games Amazons 4 and Havannah, 5 alongside the graphical interfaces of playouts run on these games.
Moves in Ludii are represented using an atomic model. At each state s, the ludemes describing the playing rules are evaluated and return a list of k legal moves M: m 1 , . . . , m i , . . . , m k . In Ludii, the transition between two successive states s i and s i+1 is possible thanks to a sequence of atomic actions A i applied on s i . Such a sequence is modelled as a move m: a 1 , . . . , a i , . . . , a n with n the number of actions in A i . Thanks to this representation, it is possible to associate with each move m the concepts triggered by the list of actions defining m. Similarly, concepts can be associated with any state s, by computing the concepts involved at s.

IV. GAME CONCEPTS
A concept is an abstract representation that can be shared between different objects or ideas highlighting common points. Previous work (see Section II-C)) commonly uses the term "game feature" to designate a high-level aspect of games. However, in a board game context but also for the more general purpose of this paper, we are going to use the term "game concept" due to the existing use of the term "feature" by previous work on state-action features for board games [53].
Every game concept in Ludii is defined by its name, its category, its data type (numerical or binary) and its computation type. Each concept's name is selected to be as close as possible to terms used by human players or game designers. Version 1.2.0 of Ludii, used in this paper, currently implements 428 distinct game concepts. To organise these concepts, we propose a taxonomy 6 inspired by the Core Subject Taxonomy for Mathematical Sciences Education outlined by the Mathematical Association of America [54].

A. Categories
The seven main concept categories are: • Implementation: Concepts describing game implementation details. Thanks to this taxonomy, it is possible to focus only on a specific subset of categories depending on the specific application or research field. For example, many game-playing applications would have no use for the visual category, while explainable AI research will likely disregard the implementation category.

B. Data Type
A game concept can be numerical or binary. Binary concepts are used to show the existence of concepts in games, while numerical concepts are used to quantify them.
A binary game concept is activated if a specific ludeme, or a combination of ludemes, is used in the game's description. As an example, the concept STOCHASTIC describes games involving chance elements. It can be activated by multiple ludemes in isolation, such as rolling dice (ROLL) or the use of any random value (VALUE RANDOM 1 5). Contrary to this, the concept HOP CAPTURE will be triggered if the game involves a (MOVE HOP ...) ludeme and a capturing effect within it, such as the ludeme (REMOVE ...).
Rather than being activated or not, numerical game concepts are instead associated with a value. This can be an integer, such as the number of players (NUM PLAYERS) or the number of playable sites (NUM PLAYABLE SITES), or a float, such as the average number of possible directions per site (NUM DIRECTIONS). Some numerical concepts also correspond to the frequency of binary concepts, such as the average number of times a specific terminal state is reached, e.g., in Havannah, the frequency of winning with a loop (LOOP END) compare to connected regions (CONNECTION END), or the average number of times a specific move type was made, e.g. In Amazons, the frequencies of the concepts SLIDE or SHOOT.

C. Computation
Within the Ludii software, game concepts can be obtained in two different ways. One is done near-instantaneously during game compilation (compilation concepts), the other requires running playouts (playout concepts). This distinction is important depending on the intended application. For example, tasks that have to be responsive cannot use the concepts that require playouts, as these take significantly longer to compute.
Compilation concepts are based only on the ludemes used to describe static properties of the game, such as the dimensions of the game board. During the compilation process of Ludii games [51], the existence of specific ludemes or combinations of ludemes trigger each of these concepts. Binary concepts are simply activated by the existence of ludemes while numerical concepts instead have their values set, such as the number of component types (NUM COMPONENT TYPES).
Each atomic action in Ludii can return the concepts triggered by their application to a game state, consequently, game concepts can be associated with each move played instantaneously, due to the atomic-action representation of a move. However, at a higher level such as the game, playout concepts require more time to be computed. All concepts relating to the frequency of specific binary concepts are based on playouts. Each playout corresponds to a sequence of moves called a trial τ : m 1 , . . . , m i , . . . , m ter with m ter the last move played reaching the terminal state s ter . Thanks to the association of each move to a set of binary concepts, each trial τ can compute the frequency of the concepts involved. By running many playouts and consequently obtaining many trials for a single game, the values of the frequency game concepts can be computed by averaging the frequency of the concepts in each trial. Similarly, all the concepts belonging to the Metrics category, such as GAME LENGTH or BRANCHING FACTOR, are also computed using these playouts. For all playout concepts, it is important to note that their values are dependent on the playout type, which can be obtained randomly or with different game-playing agents. Table I shows the values for a subset of concepts on  Figure 1, the concepts are shown at ludii.games/concepts.php?gameId=52 and ludii.games/concepts.php?gameId=372, respectively. We can observe that for Amazons the frequencies of the concepts SLIDE and SHOOT are both 50%, while for Havannah the frequencies of the concepts CONNECTIONEND and LOOPEND are 27% and 73%, respectively.
V. GGP RESEARCH DIRECTIONS Having now described the different game concept categories and data types, as well as how they are computed, we turn to the different possible applications and research directions that can utilise them.

A. Agent Selection
Hyper-heuristic approaches aim to select the best agent, heuristic or strategy for a given task from a pre-defined set of choices [55]. Such approaches, especially for game AI research, typically involve identifying features between games that give an indication of how these different choices will perform [56], [57]. Our proposed game concepts may provide such features, if a correlation between the values for certain concepts and the performance of different agents can be identified.
Although not yet proven, it is highly likely that the existence of certain concepts or concept values would affect the abilities of different game-playing agents. A larger board and more pieces would typically indicate a greater branching factor, which affects the performance of certain AI techniques more than others. Likewise, agents that require full playouts to compare different moves (e.g. Monte Carlo tree search) may perform worse on games that take longer to complete, compared to agents that use defined state evaluation heuristics (e.g. Minimax).
After determining the performance of a set of agents for a given set of games, we can attempt to train models to predict the best agent for a game based on its concepts. If successful, this can provide a portfolio agent which can predict the best agent on a new game using its concept values. A similar approach has been previously presented in [58], which uses the ludemes within the games -rather than their conceptsto predict the performance of different general-game-playing heuristics. It is likely that the game concepts provide additional information which can help give more accurate predictions, thus leading to better portfolio agent performance.

B. Transfer Learning
Transfer learning research in games, and more generally reinforcement learning [59]- [61], focuses on transferring learned objects such as heuristics, value functions, policies, etc. from one or more source domains, to one or more target domains. This may involve transferring trained weights and/or representations -which may be explicit features [53], or learned representations such as those in hidden layers of deep neural networks.
Transfer of heuristics or value functions, which are functions of game states, between any pair of games requires that those games have identical state spaces, or compatible state representations such that we can create mappings between their state spaces. Similarly, transfer of policies, which are functions of game states and actions, also requires identical action spaces or compatible action representations that enable mappings between action spaces. There has been some research towards transferring value functions in GGP based on general features of the shape of a lookahead search tree [47], as well as value function transfer in a limited set of specific types of sourcetarget pairs where appropriate state space mappings can be automatically detected based on GDL game descriptions [49].
Ludii's object-oriented, game-independent state and action representations [52] has already been demonstrated to facilitate straightforward mappings between state and action spaces of different games, allowing for effective transfer of deep neural networks with both policy and value heads between many different pairs of games [62]. However, even when such mappings are possible, transfer learning is sometimes still ineffective (or even detrimental, a phenomenon known as negative transfer [63]) due to significant differences in the goals or optimal strategies between games. For example, the state and action representations of Hex and Misère Hex -which is Hex with an inverted win condition -are very similar, but neither policy nor value functions work well when transferred directly (although learned features, or hidden representations, can still be useful).
Game concepts may be viewed as "summarising" a problem or task description for a game, and hence also used to analyse in which aspects any pair of games is similar or different. This can be used to predict whether or not transfer may be successful, or more specifically to predict which aspectsonly policies, or only value functions, or only features/learned representations, etc. -may successfully transfer [64], [65].

C. Explainability
Explainable AI (XAI) is an emerging field in Artificial Intelligence that has become increasingly important in recent years [66]. XAI attempts to bring transparency to how AI agents perform, by providing human-understandable explanations for the decisions they make. For many AI agents, the strategies played are generally obscure and difficult to decipher. For example, Deep Reinforcement Learning based agents such as AlphaGo [67] outperforming the best Go players, are playing strategies that are still analysed by Go experts [68] years after its victory on Lee Sedol [69]. It can be similarly difficult to understand the strategies followed by agents that do not explicitly use understandable domain knowledge, such as general game agents or puzzle solvers.
Correlations between concepts associated with played moves, and concepts associated with the states in which moves are played, may provide human-understandable insights -expressed in "game terms" -of agents' strategies. For example, identifying specific concepts triggered by moves played only from states always corresponding to the same set of concepts can explain the strategy followed by an AI agent.
For General Game agents, the good or bad performance of AI techniques/agents on games could be explained by the concepts shared between games. This explanation could be provided at a game agent level but also for the different parameters or guiding search techniques to some subsets of games but not others. For example, agents based on MCTS techniques or an Alpha-Beta search without any pre-defined knowledge, are generally achieving different performances based on the rules of the games requiring more or less time to be computing at each state (e.g. Chess-like games are generally in favour of Alpha-Beta agents because of the checkmate rule).

D. Move Evaluation
Concepts associated with moves can be used as a means of classifying them based on high-level categories, such as distinguishing capture moves from moves that do not capture. This may provide basic evaluations of the usefulness of different moves, and hence used to guide search algorithms. For example, such concepts could be used for move ordering in minimax-based agents, or to bias move selection in playouts using techniques such as FAST [32]. Such guidance will typically be fairly basic due to the high-level nature of concepts, but also highly efficient because the concepts can be extracted directly from moves generated by Ludii. This process does not require any additional computation, as would be required for features of a successor state.

E. Game Generation
Board game generation through the use of an evolutionary algorithm has been shown to provide interesting new games [40], [70]. One improvement to this work might be to generate games that result in some particular combination of game concepts that a specific player might find appealing. Game concepts could also be an important aspect of fitness functions for evaluating generated games, particularly for search-based approaches in the same vein as previous work on puzzle generation [71]. Concepts can also help to direct the selection of specific ludemes within a generated games description, by favouring ludemes that are associated with desirable concepts.
The use of game concepts to generate games can also provide new challenges. For example, the generation of games that use some novel combination of concepts that have not been previously created, perhaps leading to new and exciting gameplay properties. Similarly, the simplification of games by removing a particular concept from its rules could provide games that help teach specific rules to beginners. It has been shown in prior work [72] that agents learn faster when independently trained on separate simpler versions of a large game. This is useful in cases where training time is limited, for example in AI competitions [42], [50].

F. Game Reconstruction
As described by the Digital Ludeme Project (DLP) [73], there are a large number of historical games for which the rules are unknown or incomplete. A process similar to that of game generation could be used to reconstruct the rules of an incomplete game. By looking at the concepts used in known nearby games, we can use these to predict which concepts our incomplete game might have. In essence, for each game concept, we can calculate a probability that it was included in an incomplete game, based on the concepts present in other similar games.

G. Game Recommender Systems
Concepts can also be used to recommend new games to human players based on their preferences. If a player favours games with certain concepts, such as asymmetric games with hidden information, but dislike others, such as games with capture moves, then we can find and suggest other games in Ludii that also contain these desired combinations. Our concepts could also be combined with other board game recommendation systems, such as those developed for the online board game geek database [74]- [77], to create an even more extensive system.
Game concepts could also be used as searching criteria to find appropriate benchmark games for AI agents. Many AI techniques are not suitable or applicable to certain games types, such as algorithms dedicated to deterministic games versus agents dedicated to stochastic games with hidden information. This applicability problem can be more specific, mainly when the techniques are based on some specific heuristics or functions such as knowledge designed for some specific game goals. The search for good benchmarks can be timeconsuming and would be much easier with the use of game concepts showing the properties of games in a recommender system. Identifying smaller subsets of games that give near equal information about an agent compared to the full set has been previously investigated for the GVGAI framework [78]. By comparing the concepts present within the Ludii game corpus, we can achieve a similar means of creating a smaller game subset that still provides maximal concept coverage.

VI. CONCLUSION
This paper refines the notion of game concepts to General Board Game Playing. Such concepts are defined using common terms which are understood by game players and designers. These concepts can be identified automatically for games in Ludii thanks to the ludeme representation, and are associated with any level of game abstraction. Game concepts provide several interesting research possibilities, including the creation of a portfolio agent via agent or heuristic selection, transfer learning between games, explainability of AI techniques and strategies, Game Generation, Game Reconstruction and Game Recommendation.
Future work over the next few years will primarily involve identifying more game concepts and implementing their detection within the Ludii system, as well as investigating the research directions proposed in this paper. In the long term, the ludeme philosophy used to represent games could be extended to other domains, such as protein folding, physics simulations or chemical reactions, by adapting the notion of ludemes to conceptual units of each of these topics. Consequently, concepts specific to these fields could be identified and detected by similar techniques, providing a human understandable explanation for any technique applied in these fields.