Search

This paper presents a general approach for measuring distances between board games within the Ludii general game system. These distances are calculated using a previously published set of general board game concepts, each of which represents a common game idea or shared property. Our results compare and contrast two different measures of distance, highlighting the subjective nature of such metrics and discussing the different ways that they can be interpreted., Comment: Accepted at the Computers and Games 2022 conference

Proof-Number Search (PNS) and Monte-Carlo Tree Search (MCTS) have been successfully applied for decision making in a range of games. This paper proposes a new approach called PN-MCTS that combines these two tree-search methods by incorporating the concept of proof and disproof numbers into the UCT formula of MCTS. Experimental results demonstrate that PN-MCTS outperforms basic MCTS in several games including Lines of Action, MiniShogi, Knightthrough, and Awari, achieving win rates up to 94.0%., Comment: Accepted at IEEE CoG 2022. Copyright of final version held by IEEE

There are several different game description languages (GDLs), each intended to allow wide ranges of arbitrary games (i.e., general games) to be described in a single higher-level language than general-purpose programming languages. Games described in such formats can subsequently be presented as challenges for automated general game playing agents, which are expected to be capable of playing any arbitrary game described in such a language without prior knowledge about the games to be played. The language used by the Ludii general game system was previously shown to be capable of representing equivalent games for any arbitrary, finite, deterministic, fully observable extensive-form game. In this paper, we prove its universality by extending this to include finite non-deterministic and imperfect-information games., Comment: Accepted for publication in the Proceedings of the 2024 IEEE Conference on Games

In many board games and other abstract games, patterns have been used as features that can guide automated game-playing agents. Such patterns or features often represent particular configurations of pieces, empty positions, etc., which may be relevant for a game's strategies. Their use has been particularly prevalent in the game of Go, but also many other games used as benchmarks for AI research. In this paper, we formulate a design and efficient implementation of spatial state-action features for general games. These are patterns that can be trained to incentivise or disincentivise actions based on whether or not they match variables of the state in a local area around action variables. We provide extensive details on several design and implementation choices, with a primary focus on achieving a high degree of generality to support a wide variety of different games using different board geometries or other graphs. Secondly, we propose an efficient approach for evaluating active features for any given set of features. In this approach, we take inspiration from heuristics used in problems such as SAT to optimise the order in which parts of patterns are matched and prune unnecessary evaluations. This approach is defined for a highly general and abstract description of the problem -- phrased as optimising the order in which propositions of formulas in disjunctive normal form are evaluated -- and may therefore also be of interest to other types of problems than board games. An empirical evaluation on 33 distinct games in the Ludii general game system demonstrates the efficiency of this approach in comparison to a naive baseline, as well as a baseline based on prefix trees, and demonstrates that the additional efficiency significantly improves the playing strength of agents using the features to guide search., Comment: Accepted for publication in the journal of Artificial Intelligence (AIJ)

Game boards are described in the Ludii general game system by their underlying graphs, based on tiling, shape and graph operators, with the automatic detection of important properties such as topological relationships between graph elements, directions and radial step sequences. This approach allows most conceivable game boards to be described simply and succinctly., Comment: Accepted at Advances in Computer Games (ACG) 2021

This paper describes three different optimised implementations of playouts, as commonly used by game-playing algorithms such as Monte-Carlo Tree Search. Each of the optimised implementations is applicable only to specific sets of games, based on their rules. The Ludii general game system can automatically infer, based on a game's description in its general game description language, whether any optimised implementations are applicable. An empirical evaluation demonstrates major speedups over a standard implementation, with a median result of running playouts 5.08 times as fast, over 145 different games in Ludii for which one of the optimised implementations is applicable., Comment: Advances in Computer Games (ACG) 2021

In this paper we present a process for automatically generating manuals for board games within the Ludii general game system. This process requires many different sub-tasks to be addressed, such as English translation of Ludii game descriptions, move visualisation, highlighting winning moves, strategy explanation, among others. These aspects are then combined to create a full manual for any given game. This manual is intended to provide a more intuitive explanation of a game's rules and mechanics, particularly for players who are less familiar with the Ludii game description language and grammar., Comment: 12 Pages, 6 Figures

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.

Population dynamics and evolutionary genetics underly the structure of ecosystems, changing on the same timescale for interacting species with rapid turnover, such as virus (e.g. HIV) and immune response. Thus, an important problem in mathematical modeling is to connect ecology, evolution and genetics, which often have been treated separately. Here, extending analysis of multiple virus and immune response populations in a resource - prey (consumer) - predator model from Browne and Smith \cite{browne2018dynamics}, we show that long term dynamics of viral mutants evolving resistance at distinct epitopes (viral proteins targeted by immune responses) are governed by epistasis in the virus fitness landscape. In particular, the stability of persistent equilibrium virus-immune (prey-predator) network structures, such as nested and one-to-one, and bifurcations are determined by a collection of circuits defined by combinations of viral fitnesses that are minimally additive within a hypercube of binary sequences representing all possible viral epitope sequences ordered according to immunodominance hierarchy. Numerical solutions of our ordinary differential equation system, along with an extended stochastic version including random mutation, demonstrate how pairwise or multiplicative epistatic interactions shape viral evolution against concurrent immune responses and convergence to the multi-variant steady state predicted by theoretical results. Furthermore, simulations illustrate how periodic infusions of subdominant immune responses can induce a bifurcation in the persistent viral strains, offering superior host outcome over an alternative strategy of immunotherapy with strongest immune response.

This paper investigates the performance of different general-game-playing heuristics for games in the Ludii general game system. Based on these results, we train several regression learning models to predict the performance of these heuristics based on each game's description file. We also provide a condensed analysis of the games available in Ludii, and the different ludemes that define them., Comment: 4 pages, 1 figure, 2 tables

In this paper, we use fully convolutional architectures in AlphaZero-like self-play training setups to facilitate transfer between variants of board games as well as distinct games. We explore how to transfer trained parameters of these architectures based on shared semantics of channels in the state and action representations of the Ludii general game system. We use Ludii's large library of games and game variants for extensive transfer learning evaluations, in zero-shot transfer experiments as well as experiments with additional fine-tuning time.

Combinations of Monte-Carlo tree search and Deep Neural Networks, trained through self-play, have produced state-of-the-art results for automated game-playing in many board games. The training and search algorithms are not game-specific, but every individual game that these approaches are applied to still requires domain knowledge for the implementation of the game's rules, and constructing the neural network's architecture -- in particular the shapes of its input and output tensors. Ludii is a general game system that already contains over 500 different games, which can rapidly grow thanks to its powerful and user-friendly game description language. Polygames is a framework with training and search algorithms, which has already produced superhuman players for several board games. This paper describes the implementation of a bridge between Ludii and Polygames, which enables Polygames to train and evaluate models for games that are implemented and run through Ludii. We do not require any game-specific domain knowledge anymore, and instead leverage our domain knowledge of the Ludii system and its abstract state and move representations to write functions that can automatically determine the appropriate shapes for input and output tensors for any game implemented in Ludii. We describe experimental results for short training runs in a wide variety of different board games, and discuss several open problems and avenues for future research.

This technical report outlines the fundamental workings of the game logic behind Ludii, a general game system, that can be used to play a wide variety of games. Ludii is a program developed for the ERC-funded Digital Ludeme Project, in which mathematical and computational approaches are used to study how games were played, and spread, throughout history. This report explains how general game states and equipment are represented in Ludii, and how the rule ludemes dictating play are implemented behind the scenes, giving some insight into the core game logic behind the Ludii general game player. This guide is intended to help game designers using the Ludii game description language to understand it more completely and make fuller use of its features when describing their games.

This short paper describes an ongoing research project that requires the automated self-play learning and evaluation of a large number of board games in digital form. We describe the approach we are taking to determine relevant features, for biasing MCTS playouts for arbitrary games played on arbitrary geometries. Benefits of our approach include efficient implementation, the potential to transfer learnt knowledge to new contexts, and the potential to explain strategic knowledge embedded in features in human-comprehensible terms., Comment: Paper exactly as it appeared at KEG Workshop held at AAAI 2019

Games potentially provide a wealth of knowledge about our shared cultural past and the development of human civilisation, but our understanding of early games is incomplete and often based on unreliable reconstructions. This paper describes the Digital Ludeme Project, a five-year research project currently underway that aims to address such issues using modern computational techniques.

Expert Iteration (ExIt) is an effective framework for learning game-playing policies from self-play. ExIt involves training a policy to mimic the search behaviour of a tree search algorithm - such as Monte-Carlo tree search - and using the trained policy to guide it. The policy and the tree search can then iteratively improve each other, through experience gathered in self-play between instances of the guided tree search algorithm. This paper outlines three different approaches for manipulating the distribution of data collected from self-play, and the procedure that samples batches for learning updates from the collected data. Firstly, samples in batches are weighted based on the durations of the episodes in which they were originally experienced. Secondly, Prioritized Experience Replay is applied within the ExIt framework, to prioritise sampling experience from which we expect to obtain valuable training signals. Thirdly, a trained exploratory policy is used to diversify the trajectories experienced in self-play. This paper summarises the effects of these manipulations on training performance evaluated in fourteen different board games. We find major improvements in early training performance in some games, and minor improvements averaged over fourteen games., Comment: Accepted at the IEEE Conference on Games (CoG) 2020

Infection by distinct Dengue virus serotypes and host immunity are intricately linked. In particular, certain levels of cross-reactive antibodies in the host may actually enhance infection severity leading to Dengue hemorrhagic fever (DHF). The coupled immunological and epidemiological dynamics of Dengue calls for a multi-scale modeling approach. In this work, we formulate a within-host model which mechanistically recapitulates characteristics of antibody dependent enhancement (ADE) in Dengue infection. The within-host scale is then linked to epidemiological spread by a vector-host partial differential equation model structured by host antibody level. The coupling allows for dynamic population-wide antibody levels to be tracked through primary and secondary infections by distinct Dengue strains, along with waning of cross-protective immunity after primary infection. Analysis of both the within-host and between-host systems are conducted. Stability results in the epidemic model are formulated via basic and invasion reproduction numbers as a function of immunological variables. Additionally, we develop numerical methods in order to simulate the multi-scale model and assess the influence of parameters on disease spread and DHF prevalence in the population.

Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intractable puzzle, such as Sudoku, but also enjoy the ability to check their solution easily once it's done. For this reason, using constraint programming is naturally suited to solve them. In this paper, we focus on logic puzzles described in the Ludii general game system and we propose using the XCSP formalism in order to solve them with any CSP solver., Comment: Accepted at the IEEE Conference on Games (CoG) 2019 (Short paper)

Ludii is a general game system being developed as part of the ERC-funded Digital Ludeme Project (DLP). While its primary aim is to model, play, and analyse the full range of traditional strategy games, Ludii also has the potential to support a wide range of AI research topics and competitions. This paper describes some of the future competitions and challenges that we intend to run using the Ludii system, highlighting some of its most important aspects that can potentially lead to many algorithm improvements and new avenues of research. We compare and contrast our proposed competition motivations, goals and frameworks against those of existing general game playing competitions, addressing the strengths and weaknesses of each platform., Comment: Accepted at the IEEE Conference on Games (CoG) 2019

Although General Game Playing (GGP) systems can facilitate useful research in Artificial Intelligence (AI) for game-playing, they are often computationally inefficient and somewhat specialised to a specific class of games. However, since the start of this year, two General Game Systems have emerged that provide efficient alternatives to the academic state of the art -- the Game Description Language (GDL). In order of publication, these are the Regular Boardgames language (RBG), and the Ludii system. This paper offers an experimental evaluation of Ludii. Here, we focus mainly on a comparison between the two new systems in terms of two key properties for any GGP system: simplicity/clarity (e.g. human-readability), and efficiency., Comment: Accepted at the IEEE Conference on Games (CoG) 2019 (Short paper)

The Digital Ludeme Project (DLP) aims to reconstruct and analyse over 1000 traditional strategy games using modern techniques. One of the key aspects of this project is the development of Ludii, a general game system that will be able to model and play the complete range of games required by this project. Such an undertaking will create a wide range of possibilities for new AI challenges. In this paper we describe many of the features of Ludii that can be used. This includes designing and modifying games using the Ludii game description language, creating agents capable of playing these games, and several advantages the system has over prior general game software., Comment: Accepted at the IEEE Conference on Games (CoG) 2019 (Demo paper)

Digital Archaeoludology (DAL) is a new field of study involving the analysis and reconstruction of ancient games from incomplete descriptions and archaeological evidence using modern computational techniques. The aim is to provide digital tools and methods to help game historians and other researchers better understand traditional games, their development throughout recorded human history, and their relationship to the development of human culture and mathematical knowledge. This work is being explored in the ERC-funded Digital Ludeme Project. The aim of this inaugural international research meeting on DAL is to gather together leading experts in relevant disciplines - computer science, artificial intelligence, machine learning, computational phylogenetics, mathematics, history, archaeology, anthropology, etc. - to discuss the key themes and establish the foundations for this new field of research, so that it may continue beyond the lifetime of its initiating project., Comment: Report on Dagstuhl Research Meeting. Authored/edited by all participants. Appendices by Thierry Depaulis

In recent years, state-of-the-art game-playing agents often involve policies that are trained in self-playing processes where Monte Carlo tree search (MCTS) algorithms and trained policies iteratively improve each other. The strongest results have been obtained when policies are trained to mimic the search behaviour of MCTS by minimising a cross-entropy loss. Because MCTS, by design, includes an element of exploration, policies trained in this manner are also likely to exhibit a similar extent of exploration. In this paper, we are interested in learning policies for a project with future goals including the extraction of interpretable strategies, rather than state-of-the-art game-playing performance. For these goals, we argue that such an extent of exploration is undesirable, and we propose a novel objective function for training policies that are not exploratory. We derive a policy gradient expression for maximising this objective function, which can be estimated using MCTS value estimates, rather than MCTS visit counts. We empirically evaluate various properties of resulting policies, in a variety of board games., Comment: Accepted at the IEEE Conference on Games (CoG) 2019

While current General Game Playing (GGP) systems facilitate useful research in Artificial Intelligence (AI) for game-playing, they are often somewhat specialised and computationally inefficient. In this paper, we describe the "ludemic" general game system Ludii, which has the potential to provide an efficient tool for AI researchers as well as game designers, historians, educators and practitioners in related fields. Ludii defines games as structures of ludemes -- high-level, easily understandable game concepts -- which allows for concise and human-understandable game descriptions. We formally describe Ludii and outline its main benefits: generality, extensibility, understandability and efficiency. Experimentally, Ludii outperforms one of the most efficient Game Description Language (GDL) reasoners, based on a propositional network, in all games available in the Tiltyard GGP repository. Moreover, Ludii is also competitive in terms of performance with the more recently proposed Regular Boardgames (RBG) system, and has various advantages in qualitative aspects such as generality., Comment: Accepted at ECAI 2020

Humans tend to learn complex abstract concepts faster if examples are presented in a structured manner. For instance, when learning how to play a board game, usually one of the first concepts learned is how the game ends, i.e. the actions that lead to a terminal state (win, lose or draw). The advantage of learning end-games first is that once the actions which lead to a terminal state are understood, it becomes possible to incrementally learn the consequences of actions that are further away from a terminal state - we call this an end-game-first curriculum. Currently the state-of-the-art machine learning player for general board games, AlphaZero by Google DeepMind, does not employ a structured training curriculum; instead learning from the entire game at all times. By employing an end-game-first training curriculum to train an AlphaZero inspired player, we empirically show that the rate of learning of an artificial player can be improved during the early stages of training when compared to a player not using a training curriculum., Comment: Draft prior to submission to IEEE Trans on Games. Changed paper slightly

This paper proposes using a linear function approximator, rather than a deep neural network (DNN), to bias a Monte Carlo tree search (MCTS) player for general games. This is unlikely to match the potential raw playing strength of DNNs, but has advantages in terms of generality, interpretability and resources (time and hardware) required for training. Features describing local patterns are used as inputs. The features are formulated in such a way that they are easily interpretable and applicable to a wide range of general games, and might encode simple local strategies. We gradually create new features during the same self-play training process used to learn feature weights. We evaluate the playing strength of an MCTS player biased by learnt features against a standard upper confidence bounds for trees (UCT) player in multiple different board games, and demonstrate significantly improved playing strength in the majority of them after a small number of self-play training games., Comment: Accepted at IEEE CEC 2019, Special Session on Games. Copyright of final version held by IEEE

The host immune response can often efficiently suppress a virus infection, which may lead to selection for immune-resistant viral variants within the host. For example, during HIV infection, an array of CTL immune response populations recognize specific epitopes (viral proteins) presented on the surface of infected cells to effectively mediate their killing. However HIV can rapidly evolve resistance to CTL attack at different epitopes, inducing a dynamic network of interacting viral and immune response variants. We consider models for the network of virus and immune response populations, consisting of Lotka-Volterra-like systems of ordinary differential equations. Stability of feasible equilibria and corresponding uniform persistence of distinct variants are characterized via a Lyapunov function. We specialize the model to a "binary sequence" setting, where for $n$ epitopes there can be $2^n$ distinct viral variants mapped on a hypercube graph. The dynamics in several cases are analyzed and sharp polychotomies are derived characterizing persistent variants. In particular, we prove that if the viral fitness costs for gaining resistance to each epitope are equal, then the system of $2^n$ virus strains converges to a "perfectly nested network" with less than or equal to $n+1$ persistent virus strains. Overall, our results suggest that immunodominance, i.e. relative strength of immune response to an epitope, is the most important factor determining the persistent network structure., Comment: Revised preprint, to appear in Journal of Mathematical Biology

Mathematical modeling and analysis can provide insight on the dynamics of ecosystems which maintain biodiversity in the face of competitive and prey-predator interactions. Of primary interests are the underlying structure and features which stabilize diverse ecological networks. Recently Korytowski and Smith [17] proved that a perfectly nested infection network, along with appropriate life history trade-offs, leads to coexistence and persistence of bacteria-phage communities in a chemostat model. In this article, we generalize their model in order to apply it to the within-host dynamics virus and immune response, in particular HIV and CTL (Cytotoxic T Lymphocyte) cells. Our model can produce a diverse hierarchy of viral and immune populations, built through sequential viral escape from dominant immune responses and rise in subdominant immune responses, consistent with observed patterns of HIV/CTL evolution. We find a Lyapunov function for the system which leads to rigorous characterization of persistent viral and immune variants, and informs upon equilibria stability and global dynamics. Results are interpreted in the context of within-host HIV/CTL evolution and numerical simulations are provided.

Contact tracing is an important control strategy for containing Ebola epidemics. From a theoretical perspective, explicitly incorporating contact tracing with disease dynamics presents challenges, and population level effects of contact tracing are difficult to determine. In this work, we formulate and analyze a mechanistic SEIR type outbreak model which considers the key features of contact tracing, and we characterize the impact of contact tracing on the effective reproduction number, $\mathcal R_e$, of Ebola. In particular, we determine how relevant epidemiological properties such as incubation period, infectious period and case reporting, along with varying monitoring protocols, affect the efficacy of contact tracing. In the special cases of either perfect monitoring of traced cases or perfect reporting of all cases, we derive simple formulae for the critical proportion of contacts that need to be traced in order to bring the effective reproduction number $\mathcal R_e$ below one. Also, in either case, we show that $\mathcal R_e$ can be expressed completely in terms of observable reported case/tracing quantities, namely $\mathcal R_e=k\dfrac{(1-q)}{q}+k_m$ where $k$ is the number of secondary traced infected contacts per primary untraced reported case, $k_m$ is the number of secondary traced infected contacts per primary traced reported case and $(1-q)/q$ is the odds that a reported case is not a traced contact. These formulae quantify contact tracing as both an intervention strategy that impacts disease spread and a probe into the current epidemic status at the population level. Data from the West Africa Ebola outbreak is utilized to form real-time estimates of $\mathcal R_e$, and inform our projections of the impact of contact tracing, and other control measures, on the epidemic trajectory.

A differential equations model is developed for the 2014 Ebola epidemics in Sierra Leone, Liberia, and Guinea. The model describes the dynamic interactions of the susceptible and infected populations of these countries. The model incorporates the principle features of contact tracing, namely, the number of contacts per identified infectious case, the likelihood that a traced contact is either incubating or infectious, and the efficiency of the contact tracing process.The model is first fitted to current cumulative reported case data in each country. The data fitted simulations are then projected forward in time, with varying parameter regimes corresponding to contact tracing efficiencies. These projections quantify the importance of the identification, isolation, and contact tracing processes for containment of the epidemics.

Mass-vaccination campaigns are an important strategy in the global fight against poliomyelitis and measles. The large-scale logistics required for these mass immunisation campaigns magnifies the need for research into the effectiveness and optimal deployment of pulse vaccination. In order to better understand this control strategy, we propose a mathematical model accounting for the disease dynamics in connected regions, incorporating seasonality, environmental reservoirs and independent periodic pulse vaccination schedules in each region. The effective reproduction number, $R_e$, is defined and proved to be a global threshold for persistence of the disease. Analytical and numerical calculations show the importance of synchronising the pulse vaccinations in connected regions and the timing of the pulses with respect to the pathogen circulation seasonality. Our results indicate that it may be crucial for mass-vaccination programs, such as national immunisation days, to be synchronised across different regions. In addition, simulations show that a migration imbalance can increase $R_e$ and alter how pulse vaccination should be optimally distributed among the patches, similar to results found with constant-rate vaccination. Furthermore, contrary to the case of constant-rate vaccination, the fraction of environmental transmission affects the value of $R_e$ when pulse vaccination is present., Comment: Added section 6.1, made other revisions, changed title

We consider a general mathematical model of a within-host viral infection with $n$ virus strains and explicit age-since-infection structure for infected cells. In the model, multiple virus strains compete for a population of target cells. Cells infected with virus strain $i\in\left\{1,...,n\right\}$ die at per-capita rate $\delta_i(a)$ and produce virions at per-capita rate $p_i(a)$, where $\delta_i(a)$ and $p_i(a)$ are functions of the age-since-infection of the cell. Viral strain $i$ has a basic reproduction number, $\mathcal{R}_i$, and a corresponding positive single strain equilibrium, $E_i$, when $\mathcal{R}_i>1$. If $\mathcal{R}_i<1$, then the total concentration of virus strain $i$ will converge to 0 asymptotically. The main result is that when $\max_i \mathcal{R}_i>1$ and all of the reproduction numbers are distinct, i.e. $\mathcal{R}_i\neq \mathcal{R}_j \ \forall i\neq j$, the viral strain with the maximal basic reproduction number competitively excludes the other strains. As an application of the model, HIV evolution is considered and simulations are provided., Comment: Minor revisions performed; reworked Figure 2