Computers and Games

Current chess rating systems update ratings incrementally and may not always accurately reflect a player’s true strength at all times, especially for rapidly improving players or very rusty players. To overcome this, we explore a method to estimate player ratings directly from game moves and clock times. We compiled a benchmark dataset from Lichess with over one million games, encompassing various time controls and including move sequences and clock times. Our model architecture comprises a CNN to learn positional features, which are then integrated with clock-time data into a Bidirectional LSTM, predicting player ratings after each move. The model achieved an MAE of 182 rating points on the test data. Additionally, we applied our model to the 2024 IEEE Big Data Cup Chess Puzzle Difficulty Competition dataset, predicted puzzle ratings and achieved competitive results. This model is the first to use no hand-crafted features to estimate chess ratings and also the first to output a rating prediction after each move. Our method highlights the potential of using move-based rating estimation for enhancing rating systems and potentially other applications such as cheating detection.

We present the use of chess filters for the convolutional layers used in computer chess. We compare different types of blocks with and without chess filters. Our comparison uses the Leela Chess Zero (Lc0) T60 dataset to train the networks with supervised learning.

We create algorithms and implement them to completely solve the rules of perpetual check and chase for a Chinese Chess Endgame Tablebase (EGTB) generator. The algorithms are vital for creating endgames when both sides have attackers. The implementation has been published as an open source and it is the first time published ever. The generator can create any endgame for real-life matches.

Much of the research on board games focuses on strong play and on solving games exactly. Recently, programs such as AlphaZero have reached superhuman level in board games such as chess and Go. We study the gap between such AI systems and perfect play, in order to deepen our understanding of their current strengths and limitations. Our study uses Go endgame puzzles with special combinatorial sum game structure, for which an optimal solver is available. We develop an extended Go endgame dataset labelled with exact scores and optimal moves. We evaluate KataGo, the strongest open source AlphaZero-derived program for the game of Go, on these puzzles. We study how the training of different neural networks and the amount of search used affect KataGo’s ability to play perfectly. We observe improved move selection with strong policies, and measure the effect of different MCTS search settings, as well as the challenges KataGo faces in competing against an exact solver. We further analyse move choices in terms of changes of average action value, lower confidence bound, winrate, and number of visited nodes in the MCTS search of KataGo. On our perfect game dataset, KataGo achieves a 90.8% success rate in matches against the exact solver.

NoGo is a version of Go where stones are never removed from the board, once played. Strong computer players have been created for NoGo. However, the game properties and optimal play strategies are not well studied. We introduce CGTSolver, a search algorithm that applies concepts from combinatorial game theory (CGT) in order to solve Linear NoGo. We develop several decomposition strategies and simplification rules for this game. Our results show that CGTSolver is much more efficient than previous solvers, and as the board size increases, the performance gap widens. With this new approach we solved all NoGo boards up to \(1\times 39\)—twelve boards more than in previous work.

We recast move generators for solving board games as operations on compressed sets of strings. We aim for compressed representations with space sublinear in the number of game positions for interesting sets of positions, move generation in time roughly linear in the compressed size and membership tests in constant time. To the extent that we achieve these tradeoffs empirically, we can strongly solve board games in time sublinear in the state space. We demonstrate this concept with the game Breakthrough where we empirically compress relevant sets of n positions to roughly \(n^{0.5}\) to \(n^{0.7}\) states and solved the \(5 \times 6\) size.

Monte Carlo Tree Search and Monte Carlo Search have good results for many combinatorial problems. In this paper we propose to use Monte Carlo Search to design mathematical expressions that are used as exploration terms for Monte Carlo Tree Search algorithms. The Monte Carlo Tree Search algorithm we aim to optimize is SHUSS (Sequential Halving Using Scores). We automatically design the SHUSS root exploration term. For small search budgets of 32 evaluations the discovered root exploration term makes SHUSS competitive with usual PUCT (Predictor Upper Confidence bounds for Trees).

Nonograms are Japanese logic puzzles where the player must find a 2D black-and-white image using information on the columns and rows. Here we present a new method to generate nonograms of varying difficulties and enjoyability using a human-like solver to estimate the difficulty of a puzzle, and Monte Carlo Tree Search algorithms to optimize the estimation of the difficulty.

This paper explores automated Nonogram solving using a constraint satisfaction problem (CSP) formulation. Nonograms require players to use numerical clues to color cells in a grid and reveal a hidden image. Our approach decomposes the puzzle into separate CSPs for each row and column, where the starting positions of clues are treated as variables, with constraints ensuring non-overlapping and sufficient spacing. Once these individual CSPs are solved, the entire puzzle board is modeled as a single CSP, with rows and columns as variables and constraints enforcing cell color consistency at intersections. To efficiently solve the puzzle, we employ inference and backtracking techniques, enhanced by Nonogram-specific logical analysis. We conduct comparative analyses with established solving methods to evaluate the effectiveness of our proposed approach. Experimental results demonstrate the efficiency of our CSP formulation and automated solving algorithm.

Unfortunately, sexism and sexual harassment are common in both private online gaming and professional esports. It has been repeatedly questioned whether the operators of multiplayer games, platforms and esports leagues are taking sufficient measures to adequately protect users, players, children, young gamers, and esports athletes. When measures are taken, such as censoring sexist or offensive chat messages or banning users, they tend to be undifferentiated. This may be partly due to a lack of surveys, studies, and data. This paper therefore presents the results of two consecutive studies using the games Overwatch and Valorant, two of the world’s most popular multiplayer first-person shooters which are also played professionally in esports leagues. Participant observations were conducted on 28 Overwatch and Valorant game sessions in a first study and 120 Valorant game sessions in a second one. These sessions’ voice chats were transcribed, coded, and statistically evaluated. The results indicate that female gamers are harassed in every seventh Valorant game, ranging from questions about their gender to unsolicited affection to threats of or jokes about rape.

This paper proposes an approach that utilizes non-intrusive and non-restrictive multimodal data—game footage videos and game context features—to recognize the player’s arousal changes in the game. In recent years, affect modeling in games from a subject-agnostic perspective has emerged due to hardware limitations and ethical considerations. However, evaluation results of these approaches across various games indicate that their effectiveness is weaker in some games compared to other games. Design patterns in such games make it difficult for their methods to accurately capture the context of the games, thus making the task more challenging. Focusing on one of these games, we utilize a new preprocessing method to generate more samples from the game data in The Arousal video Game AnnotatIoN (AGAIN) dataset. In addition, we validate our hypothesis and evaluate the effectiveness of our proposed approach. We hypothesize that the information required to recognize the player’s arousal changes is embedded in the game footage videos and the game context features, and that this information can be more effectively learned by utilizing transfer learning with a model pre-trained on a large human action dataset, such as Kinetics-400. Experimental results demonstrate that our approach achieves an accuracy of 79.96% on the test set, which shows a significant improvement over existing methods on the AGAIN dataset. This suggests that our approach can be a valuable tool for affect modeling in games.

Imperfect-information games present significant challenges for General Game Playing (GGP) agents. Traditional models have limitations that hinder their applicability in this domain. These models require agents to construct and maintain estimates about the game state, a process that is often game-specific and can unintentionally introduce domain-specific knowledge. Furthermore, this specificity undermines the core goal of GGP to generate domain-independent strategies.

To overcome these challenges, we propose the Belief Stochastic Game model. This novel framework shifts the responsibility of state estimation from the agent to the game model itself, allowing agents to focus solely on strategy development. This externalisation of the state estimation process is enabled by the exploitation of the common structures found in many imperfect-information games. The new model facilitates the development of more general agents that can adapt to a wide range of games.

In the single-player game of PlaceIt, a player must sort a random sequence of numbers in an online fashion. The game begins by sampling a sequence \(S = (s_1, \ldots , s_{20})\) of numbers uniformly at random from \(\{1, \ldots , 999\}\) without replacement. The elements of S are presented one by one to the player. Upon seeing an element \(s_i\), a player must try to guess its rank, that is, the number n such that \(s_i\) is the \(n^{\text {th}}\) smallest number in S. For example, if \(s_1 = 496\), the player might reasonably guess that \(s_1\) will be the \(10^{\text {th}}\) smallest number in S. The player must guess the rank of all 20 numbers of S correctly to win the game. Additionally, the game requires each guess to be consistent with previous guesses, so if the player guessed the rank of \(s_1 = 240\) to be 6, and then \(s_2 = 316\) is presented, the player is forced to guess a rank larger than 6 for \(s_2\). If at any point the player cannot make a consistent guess, they lose immediately. Once a rank has been assigned, it cannot be changed. This article presents a mathematical analysis of PlaceIt, in which we prove that the optimal strategy wins with probability close to 0.0001335. We then extend our analysis to a continuous variant of the game.

In this paper, we solve and visualize optimal play for All Yellow Zombie Dice, a simplification of the Zombie Dice jeopardy dice game by Steve Jackson [1] where we assume that all dice have the same outcome distribution. We present a spectrum of All Yellow Zombie Dice human-playable strategies that trade off greater play complexity for better performance, and collectively clarify key considerations for excellent play.

This paper introduces Zweistein, a dynamic programming evaluation function for Einstein Würfelt Nicht! (EWN). Instead of relying on human knowledge to craft an evaluation function, Zweistein uses a data-centric approach that eliminates the need for parameter tuning. The idea is to use a vector recording the distance to the corner of all pieces. This distance vector captures the essence of EWN. It not only outperforms many traditional EWN evaluation functions but also won first place in the TCGA 2023 competition.