Search

After two years of pandemic-related cancellations, the World Computer Chess Championship returned in July 2022. The title of World Computer Chess Champion, first contested in 1974, was successfully defended by Komodo. The World Chess Software Championship was won by Ginkgo. The World Computer Speed Chess Championship title was shared by Leela Chess Zero and Ginkgo.

The automatic generation of game mechanics is nowadays one of the most complex challenges within procedural content generation (PCG), even being considered by itself as automatic game generation in the literature. Previous works have contributed with research papers related to PCG in general, and, in particular, the generation of game mechanics from a specification written in a game description language (GDL). One primary reference is the Ludii general game system that allows to generate new mechanics for two-player combinatorial (board) games. Ludii manages game specifications written in a GDL that can be directly represented in a tree structure. These structures are then evolved by means of genetic programming (GP), a well-known bio-inspired optimization technique, to produce new game rules. Now, this paper extends the approach centered on 2-player games and proposed in the Ludii general game system to n-player videogames. The paper describes a system to automatically generate videogame mechanics. The starting point is a videogame specification written in the XML-based videogame description language (XVGDL). Similarly to Ludii, this videogame specification can be directly translated to rule tree structures that can be evolved by GP. The viability of this approach is demonstrated by experimentation with practical examples. The experiments show how it is possible to automatically produce and evaluate a number of distinct versions (that differ in their mechanics) of a videogame that was originally specified in XVGDL.

The 25th Computer Olympiad was held online during July/August 2022. With 53 participating programs competing in 18 events, the event was a success.

Cylinder-Infinite-Connect-Four is Connect-Four played on a cylindrical square grid board with infinite row heights and columns that cycle about its width. In previous work, the first player’s cannot-lose strategies were discovered for all circumferences, and the second player’s cannot-lose strategies were discovered for all circumferences except for 6 and 11. In this paper, we show the second player’s cannot-lose strategy for circumference 11.

In this paper, we present a real-time scoring algorithm for steel dartboards, by using five (configurable) low-cost cameras that are positioned parallel to the baseline (surface) of the dartboard. In order to achieve that, firstly the cameras are placed at suggested places. Then, their central focus is configured to look at the center of the dartboard. Subsequently, the dartboard is calibrated and thresholds are adjusted for each camera respectively. After this step, the software runs and processes in real-time, detecting the darts with high precision as they are thrown. The algorithm is a daemon process, requiring high processing power. We detect parts that require long processing times by profiling the algorithm. Using techniques of parallel-programming, important parts of the algorithm are adjusted to run in parallel, in order to achieve a real-time effect. In our experiments, our algorithm achieved a detection accuracy rate of 99.63%, by using five low-cost cameras having an 85 degree horizontal field of view (HFOV). Simultaneously, each throw is detected in less than 600 ms, giving the real-time effect to players. This algorithm is tested with a variety of professional steel dartboards, and dart arrows of different materials (tungsten, steel etc.). The obtained outcomes indicate the robustness of the proposed algorithm, producing promising results.

Combinatorial game theory provides results for the class of two-player, deterministic games with perfect information. With the aim of generalizing this theory to the class of non-perfect information games in mind, we introduce and analyze three variants of the game of Nim. In these variants, the opponent only receives partial information on the move executed by the opponent. We model the variants as games in extensive form and compute Nash equilibria for different starting configurations. For one variant, this provides a full characterization of the game. For the other variants, we prove some partial and structural results, but a full characterization remains elusive.

Dynamic difficulty adjustment (DDA) is a highly significant research direction in game AI. Rubber-banding is one of the DDA techniques extensively used in racing games. This paper improves the poor adaptability of the rubber-banding system combined with the game design and development techniques. An Adaptive Rubber-Banding System (ARBS) based on ARBS relationship curve, modular mechanism, as well as detail processing schemes, is implemented in Unreal Engine 4. The paper builds various test programs and compares each system in terms of the number of players, gameplay mode, and track distance. Experimental results demonstrate that ARBS is more adaptive and provides a better experience for players. Game designers and developers are thus able to employ ARBS to design and implement AI systems suitable for racing games effectively.

The 24th Computer Olympiad was held online during August/September 2021. With 60 participants competing in 22 events, the event was a success. This raises the question as to whether the ICGA and its members are best served by having future Olympiads online or returning to the in-person format.

The game of Scrabble has been successfully tackled by two engines: Quackle and Maven. They attain the state-of-the-art in Computer Scrabble. These engines use simulation techniques and precalculated values to achieve superhuman play. This paper presents a Scrabble-playing engine, Heuri, which achieves world championship standards when playing in Spanish, and a very high level when playing in English and French, without using brute-force approaches.One advantage of Heuri is that its calculations, as opposed to many in Quackle, are not precomputed and instead performed for every turn. Spanish match results of different versions of Heuri against humans and two versions of Quackle are presented in this paper. Results against Quackle, in English and French, are also given. The main goal of this paper is to enrich Computer Scrabble with the description of a Scrabble playing program, Heuri, which is differently designed from earlier ones such as Maven and Quackle. An additional goal is to give Scrabble players an excellent strategy for obtaining championship level in Spanish.

In this study, the group of finite cyclic lamplighter states is reinterpreted as the novel lamplighter puzzle. The rules of the puzzle are outlined and related back to properties of the lamplighter group with specific interest placed upon the discussion of which puzzle instances are solvable. The paper shows that, through the use of algebra, many puzzle instances can be identified as solvable without the use of an exhaustive search algorithm. Solvability depends upon the creation of irregular generating sets for subgroups of the finite cyclic lamplighter group and the cosets formed by these subgroups. Further possible generalizations of the lamplighter puzzle are also discussed in closing.

The Computer Olympiads have been held 24 times over the past 33 years. This series of events is an important landmark that demonstrates the progress of artificial intelligence technology applied to games. This article presents comparative data on the Olympiads. Some entries contain partial information, while a few have conflicting answers. The author asks the ICGA community for help in ensuring that the data is complete and correct.

The 23rd Computer Olympiad was held November/December 2020. As a consequence of the global pandemic, for the first time the competitions were fought online. This involved creating new rules that were, in large part, dependent on having the participants cooperate on organizing and conducting the events. The event was a success and will be repeated online in 2021.

PuyoPuyo is one of the Tetris-type games, which is dealt with as a single-player game in this paper. The player has a winning strategy if the player can keep playing the game infinitely on a gameboard of a constant height. In this paper, we consider how lookahead of input pieces affects the existence of winning strategies in PuyoPuyo, and show conditions that the player cannot win even with lookahead. First, we show the number of colors sufficient to make the player lose on the gameboard of width w when the number of lookahead pieces is m. Next, we show that ten and twenty-six colors are sufficient to make the player lose on the gameboards of width two and three, respectively, no matter how large the number of lookahead pieces is.

The prevalence of draws in chess is an increasing concern: in the ICCF’s 2017 ‘MT van Oosteram’ Correspondence event, all 56 games were drawn. This article reports a ‘Mobility Chess’ proposal by ‘Aloril’ which addresses this problem. He prefers to retain his anonymity but should be regarded as the primary author of this paper. He has defined a logical sequence of increasingly subtle and decreasingly rewarded ‘winning’ goals G k . Each position in itself associates with both an immediate achievement A j of goal G j – and an ultimate, best-achievable goal G k , k ⩽ j. Therefore, Aloril has eliminated the draw in Mobility Chess and shown how Chess can reduce the incidence of draws as much as required.

We present a variant of Sudoku called Sudoku Ripeto. It seems to be the first to admit any combination of repeated symbols, and includes Sudoku as a proper subset. We present other Sudoku Ripeto families, each with a different repetition pattern. We define Sudoku Ripeto squares and puzzles, prove several solving rules that generalize those for Sudoku, and give sufficient conditions to flexibly solve puzzles with rules only, without search.

The Mahjong game has widely been acknowledged to be a difficult problem in the field of imperfect information games. Because of its unique characteristics of asymmetric, serialized and multi-player game information, conventional methods of dealing with perfect information games are difficult to be applied directly on the Mahjong game. Therefore, AI (artificial intelligence)-based studies to handle the Mahjong game become challenging. In this study, an efficient AI-based method to play the Mahjong game is proposed based on the knowledge and game-tree searching strategy. Technically, we simplify the Mahjong game framework from multi-player to single-player. Based on the above intuition, an improved search algorithm is proposed to explore the path of winning. Meanwhile, three node extension strategies are proposed based on heuristic information to improve the search efficiency. Then, an evaluation function is designed to calculate the optimal solution by combining the winning rate, score and risk value assessment. In addition, we combine knowledge and Monte Carlo simulation to construct an opponent model to predict hidden information and translate it into available relative probabilities. Finally, dozens of experiments are designed to prove the effectiveness of each algorithm module. It is also worthy to mention that, the first version of the proposed method, which is named as KF-TREE, has won the silver medal in the Mahjong tournament of 2019 Computer Olympiad.

TCEC19 was the 18th season of the Top Chess Engine Championship and ran from August 6th to October 16th, 2020. TCEC has become the largest Open Computer Chess Championship. It attracts the best engines in the field and provides an opportunity for a comparative analysis of the Shannon-AB and the new Neural-Network engines’ styles of play. STOCKFISH retained the Grand Champion title with +9 in another exciting Superfinal, but only because it took on 'NN' technology 'just in time'. These two engines have dominated the field for the last eight TCEC seasons now. The attached files at http://centaur.reading.ac.uk/93815 provide the 726 games with engine PVs, the detail on them, some summary statistics and the completion to mate of the wins. Bonus matches put these two engines' performance in a valuable context of STOCKFISH_CLASSICAL and KOMODO.

This is the report of the 'TCEC Cup 7' computational experiment, the 7th TCEC knockout event and the second major part of TCEC’s 19th season. It started on 30th October 2020 and featured the best 32 available engines of the ‘TCEC 19’ league event. The games were held at Rapid tempo, the different format calling for different optimal settings in the engines and enabling a comparison with performance at slower tempi, albeit both being at super-GM level. STOCKFISH defeated LEELA CHESS ZERO in the Final. All decisive games in the supplementary data have been played out by FRITZ17 at search depth 24 to enable and to benchmark endgame practice.

San Jego is a two-player game with perfect information. It is a variation of the games Clobber (2001) and Cannibal Clobber. Given is a rectangular board with black and white pieces on the cells. Multiple pieces which are stacked on each other are called towers. The piece on top of a tower indicates her owner. A move consists of picking an own tower and placing it completely on top of an adjacent tower. If both players can not move anymore, the game ends. Winner is the player with the highest tower. An upper bound for the state-space complexity of San Jego is determined. Furthermore, the game-tree complexity is approximated theoretically and numerically. For small board sizes, the optimal game-theoretic values are calculated and the advantage of the first move is determined.

Recent trends in mathematics education emphasize discovery learning over drill. This has proven to be a bad idea in some cases, for the simple reason that practice is required to learn basic arithmetic skills. Drills in arithmetic skills can be made interesting through gamification. This study proposes a family of puzzles that gamify arithmetic practice. The puzzles are designed with an evolutionary algorithm forming an instance of automatic content generation. Two methods of evolutionary puzzle design are presented and discussed. The first method used transformed the problem into an almost trivial optimization. The second algorithm was designed to avoid the flaws of the first and produced a huge variety of puzzles. A hardness measure, based on the difficulty experienced by the evolutionary puzzle generator, is employed. The hardness measure is tested on a large collection of puzzles produced with the evolutionary automatic content generation system. An initial assumption, that all the pieces in the puzzle must be used to achieve a maximum score, was shown to be incorrect in puzzles located via automatic search. Two classes of puzzle are defined: those where the optimal solution uses all pieces and those where the optimal solution fails to use at least one piece. The latter sort of puzzle were found to be far more common in the search space.

In 1970, Thomas Strohlein gained his doctorate with the thesis 'Research on Combinatorial Games'. This included a graph-theoretic definition of an algorithm for computing endgame tables for chess. The computation was carried out on the LRZ AEG TR4 computer in Munich. The results spanned KRk, KQk, KRkb, KRkn and the iconic 'hard endgame' KQkr, and included maximal depths (to conversion), lists of maximal-depth positions and optimal moves. Here, we celebrate the 50th anniversary of this achievement and put his results in a broader context.

This article is a series of anecdotes about the development of several programs that advanced the state of the art in computer chess. The best known is Cray Blitz, which won the 1983 and 1986 World Computer Chess Championships. However, in terms of overall impact, perhaps Crafty is the most important. As a high-performing open-source program, it has been used by countless number of researchers and hobbyists to develop computer chess programs for competitions, research, and for fun.

The idea to let machines play games like Chess is quite old, with the Turk11 https://en.wikipedia.org/w/index.php?title=The_Turk&oldid=968314029 being one of the first hints. With the invention of computers, this idea got a new boost, and soon the first chess programs were presented. It took about 50 years until it was clear that the machines are superior chess players, far beyond the playing strengths of any human players. In the 1970s, the era of efficient search engines started and in 2004, the chess program Hydra clearly crossed the 3000 Elo mark, ahead of all other machines and human players. In this paper, we present a review on the chess program Hydra, on a technical level as well as from a social perspective.

TCEC17 was the 17th season of the Top Chess Engine Championship and ran from January 2nd to 21st April, 2020. TCEC has become the largest Open Computer Chess Championship. It attracts the best engines in the field and provides an opportunity for a comparative analysis of the Shannon-AB and the new Neural-Network engines’ styles of play. LEELA CHESS ZERO took the Grand Champion title from STOCKFISH again with +5 in an exciting Superfinal. The attached files at http://centaur.reading.ac.uk/89999 provide the 1300 games with engine PVs, the detail on them, some summary statistics and the completion to mate of the wins.

BeBe was one of the highest-performing chess programs of the 1980s. This article relates some of the fond computer chess memories from Linda Scherzer, co-author of BeBe.

This contribution reports about an almost forgotten attempt to find themes in chess composition automatically by machine. Based on investigations of the late International Master of Chess Composition Dieter Müller in the 1970s, the writers describe some of his results. They hope to fill a gap in the great history of chess programming.

On August 31, 1970, an experiment began that continues to this day. The first chess tournament for computers was held as part of the Association for Computing Machinery’s (ACM’s) National Conference. The interest generated was tremendous, leading to ACM sponsoring an annual event until 1994. Chess competitions continue to this day, allowing for 50 years of data on the growth of artificial intelligence capabilities in this domain. During this period, program ratings have soared from roughly 1400 in 1970 to over 3500 today. The 1970 event was the first continuous competition in computer science history, and it represents the longest ongoing experiment in computing history.11 Some paragraphs of the text have been taken from Man vs. Machine: Challenging Human Supremacy at Chess by Karsten Müller and Jonathan Schaeffer [2018].

It is been 46 years since the first computer chess world championship was held in Stockholm in 1974, and there have now been 24 more with over 700 games played. This paper investigates a number of questions that a curious soul might ask regarding the results of these games, especially how they ended. The data provided herein attempts to answer several related questions. In addition, it presents data showing how ratings of the top engines have increased over the years.