Encoding to SAT and applying a state-of-the-art SAT solver can be a highly effective way of solving constraint problems. For many types of constraints there exist several alternative SAT encodings; and the choice of encoding can significantly affect SAT solver performance for any given problem. Previous work has shown that machine learning (ML) can be used to select SAT encodings for some constraint types, making a choice for each relevant constraint type in a problem instance. The state-of-the-art approach achieves good performance by first building a small portfolio of configurations, then selecting a configuration for a given problem instance using an ML model. The approach necessitates generating training data for every combination of encodings for the constraint types, thus it scales exponentially as more constraint types are added. In this work, we select potentially different encodings for each individual constraint in a problem instance. We are able to match the state-of-the-art performance while avoiding any limitation on the number of constraint types considered. To achieve this we are proposing new individual constraint features, we present a novel method for generating training data, and we have developed a new machine learning pipeline involving both unsupervised and supervised learning.

Esports has become a popular field of research, enabling advances in areas such as machine learning and environment modeling. However, complex modeling systems require complex visualisations. Despite that, visualisation of complex modeling systems within esports have been limited or fragmented, particularly when focused on the audience. Furthermore, the use of data visualisation and data-driven storytelling has been proven to be an effective and imperative method for enhancing audience experience for esport spectators. Therefore, this paper investigates data visualisation techniques within esports, and compiles design considerations for developing visualisation tools for esports broadcast. This is achieved through a case-study, in which the WARDS model was utilised in live coverage of a Dota 2 tournament and evaluated through observational data.

Esports - competitive video games watched by online audiences - are the fastest growing form of mainstream entertainment. Esports coverage is predominantly delivered via online video streaming platforms which include interactive elements. However, there is limited understanding of how audiences engage with such interactive content. This paper presents a large-scale case study of an interactive data-driven streaming extension developed for Dota 2, reaching over 300,000 people during the DreamLeague Season 15 DPC Western Europe tournament. The extension provides interactive live statistics, analysis and highlights reels of ongoing matches. This paper presents an analysis of audience telemetry collected over the course of the four week tournament, introducing a novel approach to analysing usage data delivered seamlessly in conjunction to a linear broadcast feed. The work presented advances our general understanding of the evolving consumption patterns in esports, and leverages esports as a lens to understand future challenges and opportunities in interactive viewing across sports and entertainment.

Data analytics is commonly used to enable storytelling and enhance esport coverage. One prominent use of it is win prediction, where machine learning models predict the winner of the game before its conclusion. However, predictions are most commonly results of black-box systems, forcing commentators to produce ad-hoc interpretations. Additionally, broadcasters generally rely other metrics to build narratives, limiting the impact of win prediction models for storytelling. This paper explores an alternative method to win prediction, identifying the needs of broadcasters to guide development of a novel win condition model. By focusing on existing storytelling points, the proposed win condition model can offer greater storytelling opportunities to broadcasters, focusing on the user needs identified from within the esport domain. Rather than utilising game state data to predict the winner, as it is usually done in win prediction, the proposed win condition model uses an exploration of the possible winners to predict the game state needed for each team to win. Lastly, the features identified for win condition are evaluated through a series of machine learning models, which provide a data-driven metric to test and predict win condition in the context of Dota 2, a popular esport title.

In several real-world problems, it is often the case that the goal is to optimise several objective functions. However, usually there is not a single optimal objective vector. Instead, there are many optimal objective vectors known as Pareto-optima. Finding all Pareto-optima is computationally expensive and the number of Pareto-optima can be too large for a user to analyse. A compromise can be made by defining an optimisation criterion that integrates all objective functions. In this paper we propose several SAT-based algorithms to solve multi-objective optimisation problems using the leximax criterion. The leximax criterion is used to obtain a Pareto-optimal solution with a small trade-off between the objective functions, which is suitable in problems where there is an absence of priorities between the objective functions. Experimental results on the Multi-Objective Package Upgradeability Optimisation problem show that the SAT-based algorithms are able to outperform the Integer Linear Programming (ILP) approach when using non-commercial ILP solvers. Additionally, experimental results on selected instances from the MaxSAT evaluation adapted to the multi-objective domain show that our approach outperforms the ILP approach using commercial solvers.

Imitation learning has been demonstrated as a useful technique in automatic game testing and the development of believable Non-Player Characters (NPCs). However, imitation learning methods typically focus on learning a policy to complete a task without consideration about the playstyle used. In this work we consider the case where the task is to imitate a given playstyle. We defined a player’s playstyle based on the strategies they use in order to complete the overall task. This has been achieved by rewarding a learning agent based on the similarity of the agent and demonstration trajectories, within a learnt representation space. This allows the playstyle to be learnt in levels that differ to the one the demonstrations were collected in.

The notion of self-play, albeit often cited in multiagent reinforcement learning as a process by which to train agent policies from scratch, has received little efforts to be taxonomized within a formal model. We present a formalized framework, with clearly defined assumptions, which encapsulates the meaning of self-play as abstracted from various existing self-play algorithms. This framework is framed as an approximation to a theoretical solution concept for multiagent training. Through a novel qualitative visualization metric, on a simple environment, we show that different self-play algorithms generate different distributions of episode trajectories, leading to different explorations of the policy space by the learning agents. Quantitatively, on two environments, we analyze the learning dynamics of policies trained under different self-play algorithms captured under our framework and perform cross self-play performance comparisons. Our results indicate that, throughout training, various widely used self-play algorithms exhibit cyclic policy evolutions and that the choice of self-play algorithm significantly affects the final performance of trained agents.

Automated game balancing has often focused on single-agent scenarios. In this paper we present a tool for balancing multi-player games during game design. Our approach requires a designer to construct an intuitive graphical representation of their meta-game target, representing the relative scores that high-level strategies (or decks, or character types) should experience. This permits more sophisticated balance targets to be defined beyond a simple requirement of equal win chances. We then find a parameterization of the game that meets this target using simulation-based optimization to minimize the distance to the target graph. We show the capabilities of this tool on examples inheriting from Rock-Paper-Scissors, and on a more complex asymmetric fighting game.

Player clustering when applied to the field of video games has several potential applications. For example, the evaluation of the composition of a player base or the generation of AI agents with identified playing styles. These agents can then be used for either the testing of new game content or used directly to enhance a player’s gaming experience. Most current player clustering techniques focus on the use of internal game variables. This raises two main issues: (1) the availability of game variables, as source code access is required to log them and hence limits the data sources that can be used, and (2) the choice of game variables can introduce unintended bias in the types of play style extracted. In this work, a hybrid unsupervised frame encoder and a ‘reference-based’ clustering algorithm are both proposed and combined to allow clustering from raw game play videos. It is shown that the proposed methods are most beneficial when the types of play styles are unknown.

Throughout scientific history, overarching theoretical frameworks have allowed researchers to grow beyond personal intuitions and culturally biased theories. They allow to verify and replicate existing findings, and to link disconnected results. The notion of self-play, albeit often cited in multiagent Reinforcement Learning, has never been grounded in a formal model. We present a formalized framework, with clearly defined assumptions, which encapsulates the meaning of self-play as abstracted from various existing self-play algorithms. This framework is framed as an approximation to a theoretical solution concept for multiagent training. On a simple environment, we qualitatively measure how well a subset of the captured self-play methods approximate this solution when paired with the famous PPO algorithm. The results indicate that throughout training the trained policies exhibit cyclic evolutions, showing that self-play research is still at an early stage.

Esports have become major international sports with hundreds of millions of spectators. Esports games generate massive amounts of telemetry data. Using these to predict the outcome of esports matches has received considerable attention, but micro-predictions, which seek to predict events inside a match, is as yet unknown territory. Micro-predictions are however of perennial interest across esports commentators and audience, because they provide the ability to observe events that might otherwise be missed: esports games are highly complex with fast-moving action where the balance of a game can change in the span of seconds, and where events can happen in multiple areas of the playing field at the same time. Such events can happen rapidly, and it is easy for commentators and viewers alike to miss an event and only observe the following impact of events. In Dota 2, a player hero being killed by the opposing team is a key event of interest to commentators and audience. We present a deep learning network with shared weights which provides accurate death predictions within a five-second window. The network is trained on a vast selection of Dota 2 gameplay features and professional/semi-professional level match dataset. Even though death events are rare within a game (1% of the data), the model achieves 0.377 precision with 0.725 recall on test data when prompted to predict which of any of the 10 players of either team will die within 5 seconds. An example of the system applied to a Dota 2 match is presented. This model enables real-time micro-predictions of kills in Dota 2, one of the most played esports titles in the world, giving commentators and viewers time to move their attention to these key events.

Video game streaming provides the viewer with a rich set of audio-visual data, conveying information both with regards to the game itself, through game footage and audio, as well as the streamer's emotional state and behaviour via webcam footage and audio. Analysing player behaviour and discovering correlations with game context is crucial for modelling and understanding important aspects of livestreams, but comes with a significant set of challenges - such as fusing multimodal data captured by different sensors in uncontrolled (`in-the-wild') conditions. Firstly, we present, to our knowledge, the first data set of League of Legends livestreams, annotated for both streamer affect and game context. Secondly, we propose a method that exploits tensor decompositions for high-order fusion of multimodal representations. The proposed method is evaluated on the problem of jointly predicting game context and player affect, compared with a set of baseline fusion approaches such as late and early fusion. Data and code are available at https://github.com/charlieringer/LoLEmoGameRecognition.

Hyperinflation and price volatility in virtual economies has the potential to reduce player satisfaction and decrease developer revenue. This paper describes intuitive analytical methods for monitoring volatility and inflation in virtual economies, with worked examples on the increasingly popular multiplayer game Old School Runescape. Analytical methods drawn from mainstream financial literature are outlined and applied in order to present a high level overview of virtual economic activity of 3467 price series over 180 trading days. Six-monthly volume data for the top 100 most traded items is also used both for monitoring and value estimation, giving a conservative estimate of exchange trading volume of over £60m in real value. Our worked examples show results from a well functioning virtual economy to act as a benchmark for future work. This work contributes to the growing field of virtual economics and game development, describing how data transformations and statistical tests can be used to improve virtual economic design and analysis, with applications in real-time monitoring systems.

Heightmap generation is currently a tedious topic with the majority of generation using Perlin noise which forms a reliable, but sometimes repetitive output. In this paper, a method of generating height maps from real-world digital elevation data taken from specific regions of the planet is proposed. Raw elevation data sourced from NASA's SRTM (30m) data set is transformed into a height map format, this data is then passed into a two type unsupervised model. The method uses a type of generative adversarial network to learn the spatially-invariant features within the input regions. Producing a network model that can output an extensive amount of varying, but visually and structurally similar height maps to that of the input regions. The visual validity of outputs from the network was tested using data from 262 human participants, with over 90.15% of generated samples being correctly assigned to the original input data with a significance of P <;0.001.

This paper describes a novel multi-reconfigurable architecture, which allows variability-aware design, rapid prototyping and post-fabrication optimisation of digital systems. This is achieved by exploiting reconfiguration at both the digital function level and the transistor level. A runtime variability map of the architecture, created using ring oscillators, is presented.

Intrinsic device variability has become a significant problem in deep sub-micron technology nodes. The stochastic variations in device performance, which are a result of structural irregularities at the atomic scale, can impact both the yield and reliability of a circuit design. In this paper we describe a novel multi-reconfigurable FPGA architecture, the programmable analogue and digital array (PAnDA), which can tackle this problem by allowing post-fabrication reconfiguration of the effective transistor gate widths in a circuit. We demonstrate the advantages of this architecture by creating a frequency variability map of the array using ring oscillators in order to ascertain the location of any frequency outliers. We then show that it is possible, using an evolutionary algorithm, to select alternative transistor configurations which minimise the difference in frequency between one of these outliers and the chips median frequency of operation. Such methods can be used to increase system performance and reliability by presenting an array with more uniform performance characteristics.

A novel hierarchical fault-tolerance methodology for reconfigurable devices is presented. A bespoke multi-reconfigurable FPGA architecture, the programmable analogue and digital array (PAnDA), is introduced allowing fine-grained reconfiguration beyond any other FPGA architecture currently in existence. Fault blind circuit repair strategies, which require no specific information of the nature or location of faults, are developed, exploiting architectural features of PAnDA. Two fault recovery techniques, stochastic and deterministic strategies, are proposed and results of each, as well as a comparison of the two, are presented. Both approaches are based on creating algorithms performing fine-grained hierarchical partial reconfiguration on faulty circuits in order to repair them. While the stochastic approach provides insights into feasibility of the method, the deterministic approach aims to generate optimal repair strategies for generic faults induced into a specific circuit. It is shown that both techniques successfully repair the benchmark circuits used after random faults are induced in random circuit locations, and the deterministic strategies are shown to operate efficiently and effectively after optimisation for a specific use case. The methods are shown to be generally applicable to any circuit on PAnDA, and to be straightforwardly customisable for any FPGA fabric providing some regularity and symmetry in its structure.

In this paper, we propose a novel technique based on multiobjective genetic algorithms (MOGA) to solve the circuit clustering problem in field-programmable gate array (FPGA) computer aided design (CAD) flow. As the circuit clustering result is subsequently used by the circuit place-and-route process at the post-synthesis stage, the clustering quality significantly affects the routing cost and the utilisation of FPGA. Among clustering metrics, reducing the global interconnects (global nets) between configurable logic blocks (CLBs) can be viewed as the most efficient precondition to improve the clustering quality. Since the circuit has many connection properties, it is difficult to identify the proper component combinations for sub-circuits that optimise interconnect, and it is even more complicated when CLBs pose constraints. In our technique, we break the circuit clustering task into two phases. We firstly apply the MOGA to identify the best component combinations to FPGA CLBs while respecting constraints, and a second MOGA takes clustering results from the first phase and performs further optimisation. Our proposed method is tested using the MCNC-20 benchmark. The results show that the proposed technique produces better results than state-of-art algorithms in reducing global nets. The overall improvement is up to 4.33% and 14.24% in reducing the cluster number and the global net number compared to the FPGA circuit packer, iRAC, which is considered to be the best clustering method to reduce global nets.

The modeling and simulation of semiconductor devices is a difficult and computationally intensive task. However the expense of fabrication and testing means that accurate modeling and simulation are crucial to the continued progress of the industry. To create these models and then perform the simulations requires parameters from accurate physical models to be obtained and then more abstract models created that can perform more complex circuit simulations. Device models (motifs) are created as a mitigation technique for improvement the circuit performance and as technology advances to help with the effects of transistor variability. In order to explore the characteristics of new device motifs on circuit designs, obtaining accurate and reliable device models becomes the first problem for designers. In this paper a Two Step Evolution Strategy (2SES) is proposed for device parameter model extraction. The proposed 2SES approach automatically extracts a set of parameters with respect to a specified device model. Compared with conventional mathematical extraction approach, 2SES is an efficient and accurate method to solve the parameter extraction problem and simultaneously addresses the fact of the mathematical extraction having the complexity of Multi-objective optimization. Compared with single step ES extract result, it is shown that the two-step ES extraction process continues improving generations by adjusting the optimisation parameters. Finally, an application of a new device motif on circuit design is given at end of the paper and compared against a standard device.

This paper explores the potential for transistor level fault tolerance on a new Programmable Analogue and Digital Array (PAnDA) architecture1. In particular, this architecture features Combinatorial Configurable Analogue Blocks (CCABs) that can implement a number of combinatorial functions similar to FPGAs. In addition, PAnDA allows one to reconfigure features of the underlying analogue layer. In PAnDA-EINS, the functions that the CCAB can implement are predefined through the use of a routing block. This paper is a study of whether removing this routing block and allowing direct control of the transistors provides benefits for fault tolerance. Experiments are conducted in two stages. In the first stage, a logic function is evolved on a CCAB and then optimised using a GA. A fault is then injected into the substrate, breaking the logic function. The second stage of the experiment consists of evolving the logic function again on the faulty substrate. The results of these experiments show that the removal of the routing block from the CCAB is beneficial for fault tolerance.

Field programmable gate arrays (FPGAs) are widely used in applications where online reconfigurable signal processing is required. Speed and function density of FPGAs are increasing as transistor sizes shrink to the nanoscale. As these transistors reduce in size intrinsic variability becomes more of a problem and to reliably create electronic designs according to specification time consuming statistical simulations become necessary; and even with accurate models and statistical simulation, the fabrication yield will decrease as every physical instance of a design behaves differently. This paper describes an adaptive, evolvable architecture that allows for correction and optimization of circuits directly in hardware using bioinspired techniques. Similar to FPGAs, the programmable analog and digital array (PAnDA) architecture introduced provides a digital configuration layer for circuit design. Accessing additional configuration options of the underlying analog layer enables continuous adjustment of circuit characteristics at runtime, which enables dynamic optimization of the mapped design's performance. Moreover, the yield of devices can be improved postfabrication via reconfiguration of the analog layer, which can overcome faults induced due to variability and process defects. Since optimization goals are generic, i.e., not restricted to reducing stochastic variability, power consumption or increasing speed, the same mechanisms can also enhance the device's fault tolerant abilities in the case of component degradation and failures during its lifetime or when exposed to hazardous environments.

This paper describes an approach to optimise transistor dimensions within a standard cell library. The goal is to extract high-speed and low-power circuits which are more tolerant to the random fluctuations that will be prevalent in future technology nodes. Using statistically enhanced SPICE models based on 3D-atomistic simulations, a genetic algorithm optimises the device widths within a circuit using a multi-objective fitness function. The results show the impact of threshold voltage variation can be reduced by optimising transistor widths, and suggest a similar method could be extended to the optimisation of larger circuits.

As the size of CMOS devices is approaching the atomic level, the increasing intrinsic device variability is leading to higher failure rates in conventional CMOS designs. This paper introduces a design tool capable of evolving CMOS topologies using a modified form of Cartesian genetic programming and a multi-objective strategy. The effect of intrinsic variability within the design is then analysed using statistically enhanced SPICE models based on 3D-atomistic simulations. The goal is to produce industry-feasible topology designs which are more tolerant to the random fluctuations that will be prevalent in future technology nodes. The results show evolved XOR and XNOR CMOS topologies and compare the impact of threshold voltage variation on the evolved designs with those from a standard cell library.

This paper presents a generalization of the graph- based genetic programming (GP) technique known as Cartesian genetic programming (CGP). We have extended CGP by utilizing automatic module acquisition, evolution, and reuse. To benchmark the new technique, we have tested it on: various digital circuit problems, two symbolic regression problems, the lawnmower problem, and the hierarchical if-and-only-if problem. The results show the new modular method evolves solutions quicker than the original nonmodular method, and the speedup is more pronounced on larger problems. Also, the new modular method performs favorably when compared with other GP methods. Analysis of the evolved modules shows they often produce recognizable functions. Prospects for further improvements to the method are discussed.

Genetic Programming was first introduced by Koza using tree representation together with a crossover technique in which random sub-branches of the parents' trees are swapped to create the offspring. Later Miller and Thomson introduced Cartesian Genetic Programming, which uses directed graphs as a representation to replace the tree structures originally introduced by Koza. Cartesian Genetic Programming has been shown to perform better than the traditional Genetic Programming; but it does not use crossover to create offspring, it is implemented using mutation only. In this paper a new crossover method in Genetic Programming is introduced. The new technique is based on an adaptation of the Cartesian Genetic Programming representation and is tested on two simple regression problems. It is shown that by implementing the new crossover technique, convergence is faster than that of using mutation only in the Cartesian Genetic Programming method.

Classical Evolutionary Programming (CEP) and Fast Evolutionary Programming (FEP) have been applied to real-valued function optimisation. Both of these techniques directly evolve the real-values that are the arguments of the real-valued function. In this paper we have applied a form of genetic programming called Cartesian Genetic Programming (CGP) to a number of real-valued optimisation benchmark problems. The approach we have taken is to evolve a computer program that controls a writing-head, which moves along and interacts with a finite set of symbols that are interpreted as real numbers, instead of manipulating the real numbers directly. In other studies, CGP has already been shown to benefit from a high degree of neutrality. We hope to exploit this for real-valued function optimisation problems to avoid being trapped on local optima. We have also used an extended form of CGP called Embedded CGP (ECGP) which allows the acquisition, evolution and re-use of modules. The effectiveness of CGP and ECGP are compared and contrasted with CEP and FEP on the benchmark problems. Results show that the new techniques are very effective.

Embedded Cartesian Genetic Programming (ECGP) is an extension of the directed graph based Cartesian Genetic Programming (CGP), which is capable of automatically acquiring, evolving and re-using partial solutions in the form of modules. In this paper, we apply for the first time, CGP and ECGP to the well known Lawnmower problem and to the Hierarchical-if-and-Only-if problem. The latter is normally associated with Genetic Algorithms. Computational effort figures are calculated from the results of both CGP and ECGP and our results compare favourably with other techniques.

Embedded Cartesian Genetic Programming (ECGP) is an extension of Cartesian Genetic Programming (CGP) that can automatically acquire, evolve and re-use partial solutions in the form of modules. In this paper, we introduce for the first time a new multi-chromosome approach to CGP and ECGP that allows difficult problems with multiple outputs to be broken down into many smaller, simpler problems with single outputs, whilst still encoding the entire solution in a single genotype. We also propose a multi-chromosome evolutionary strategy which selects the best chromosomes from the entire population to form the new fittest individual, which may not have been present in the population. The multi-chromosome approach to CGP and ECGP is tested on a number of multiple output digital circuits. Computational Effort figures are calculated for each problem and compared against those for CGP and ECGP. The results indicate that the use of multiple chromosomes in both CGP and ECGP provide a significant performance increase on all problems tested.

Embedded Cartesian Genetic Programming (ECGP) is a form of the graph based Cartesian Genetic Programming (CGP) in which modules are automatically acquired and evolved. In this paper we compare the efficiencies of the ECGP and CGP techniques on three classes of problem: digital adders, digital multipliers and digital comparators. We show that in most cases ECGP shows a substantial improvement in performance over CGP and that the computational speedup is more pronounced on larger problems.