Advances in Computer Games

The best chess programs have reached the level of top players in the human chess world. The so-called opening books, which are databases containing thousands of Grandmaster games, have been seen as a big advantage of programs over humans, because the computers do never forget a variation. Interestingly, it is this opening phase which causes most problems for the computers. Not because they do not understand openings in general, but because the opening books contain too much rubbish. We introduce a heuristic which explores the database during a game. Without that, the computer repeats failures of weaker players. Our contribution presents best practice.

A plethora of enhancements are available to be used together with the αβ search algorithm. There are so many, that their selection and implementation is a non-trivial task, even for the expert. Every domain has its specifics which affect the search tree Even seemingly minute changes to an evaluation function can have an impact on the characteristics of a search tree. In turn, different tree characteristics must be addressed by selecting different enhancements. This paper introduces Pilot, a system for automatically selecting enhancements for αβ search. Pilot generates its own test data and then uses a greedy search to explore the space of possible enhancements. Experiments with multiple domains show differing enhancement selections. Tournament results are presented for two games to demonstrate that automatically generated αβ search performs at least on a par with what is achievable by hand-crafted search engines, but with orders of magnitude less effort in its creation.

Most game programs have a large number of parameters that are crucial for their performance. Tuning these parameters by hand is rather difficult. Therefore automatic optimization algorithms in game programs are interesting research domains. However, successful applications are only known for parameters that belong to certain components (e.g., evaluation-function parameters). The SPSA (Simultaneous Perturbation Stochastic Approximation) algorithm is an attractive choice for optimizing any kind of parameters of a game program, both for its generality and its simplicity. Its disadvantage is that it can be very slow.

In this article we propose several methods to speed up SPSA, in particular, the combination with RPROP, using common random numbers, antithetic variables, and averaging. We test the resulting algorithm for tuning various types of parameters in two domains, Poker and LOA. From the experimental study, we may conclude that using SPSA is a viable approach for optimization in game programs, in particular if no good alternative exists for the types of parameters considered.

Amazons is a two-player perfect information game with a high branching factor, particularly in the opening. Therefore, improving the efficiency of the search is important for improving the playing strength of an Amazons program. In this paper we propose a new method for improving search in Amazons by using move categories to order moves. The move order is decided by the likelihood of the move actually being selected as the best move. Furthermore, it will be shown that the likelihood of move selection strongly depends upon the stage of the game. Therefore, our method is further refined by adjusting the likelihood of moves according to the progress of the game. Self-play experiments show that using move categories significantly improves the strength of an Amazons program and that combining move categories with game progress is better than using only move categories.

Progressive Pruning (PP) is employed in the Monte-Carlo Go-playing program Indigo. For each candidate move, PP launches random games starting with this move. The goal of PP is: (1) to gather statistics on moves, and (2) to prune moves statistically inferior to the best one [7]. This papers yields two new pruning techniques: Miai Pruning (MP) and Set Pruning (SP). In MP the second move of the random games is selected at random among the set of candidate moves. SP consists in gathering statistics about two sets of moves, good and bad, and it prunes the latter when statistically inferior to the former. Both enhancements clearly speed up the process of selecting a move on 9×9 boards, and MP improves slightly the playing level. Scaling up MP to 19×19 boards results in a 30% speed-up enhancement and in a four-point improvement on average.

We propose a new threat-base search algorithm which takes into account threats by both players. In full-board Semeais in Go or Shogi endgames, making naive attack moves often result in losing the game. The reason is that a player must first make a defense move if the opponent has a better attack move than his own. Some attack moves weaken the defense of the player who made the move. Thus, players must be aware of the threats by both players to avoid such naive attack moves. However, existing threat-based search algorithms are only aware of threats by one player, and cannot detect such naive attacks efficiently. We propose a solution to this problem, by applying λ-search mutually recursively so that it searches the best move by taking into account threats by both players. We call this search algorithm dual λ -search. Dual λ-search can handle inversions efficiently compared to previous algorithms by making passes for both players. We implemented dual λ-search with Df-pn as the driver, and made experiments with difficult Shogi-endgame problems. We showed the effectiveness of our algorithm by solving 32 problems out of 97. It includes solving problems that even one of the strongest Shogi program had not yet been able to solve correctly.

In the past, there have been numerous studies into the cognitive processes involved in human problem solving. From the start, games and game theory have played an important role in the study of human problem solving behavior. In Chess, several cognitive experiments have been performed and those experiments have shown that expert chess players can memorize positions very quickly and accurately. Chase and Simon introduced the concept of chunking to explain why expert chess players perform so well in memory tasks. Chunking is the process of dividing a chess position into smaller parts that have meaning. We performed similar experiments in Shogi with a set of next-move problem positions, collecting verbal protocol data and eye-movement data. Even though experiments in Chess indicated that expert chess players searched as wide and deep as non-expert players, our experiments show that expert Shogi players search more moves, search deeper and search faster than non-expert players. Our experiments also show that expert Shogi players cannot only memorize the patterns of the positions but also recognize move sequences before and after the position. The results suggest that other than the perceptual spatial chunks introduced in chess research, there are also chunks of meaningful move sequences. We call such chunks “temporal chunk”. Our research indicates that Shogi players become stronger by acquiring these temporal chunks.

In the last decade many games have been successfully approached by what is commonly known as brute force, i.e., searching as much as possible. This tendency of computer play has been criticized since it differs much from emulating human thoughts which once was one of the primary goals of computer game playing. An alternative way which is much closer to human game playing, is to discover rules automatically for a given game with the aid of Artificial-Intelligence techniques and human thought. Obtaining such rules can be done by building computer game programs. This research line may have a much broader scope (1) to understand better the ideas of a certain game, (2) to investigate how to build automatically learnt policies for a planning problem, and perhaps even (3) to understand a bit better human thinking. To illustrate these three points, we use a small game, that could be called King Race, and we aim at discovering rules to solve it. To discover these rules we use some human thought and a decision tree program. Then we prove mathematically that these automatically obtained rules indeed solve the game. The rules can aid in building computer-chess endgame programs that do not use brute force.

Chinese-chess rules for cyclic moves differ from Western-chess rules in two respects. First the outcome of a cyclic game can be a win, a loss, or a draw. Second, depending on the plies made inside a loop, there are up to 16 rules a player can violate when a loop occurs. However, the same rule has to be violated three times in a row, i.e., in three consecutive loops, in order to lose a game. Therefore, a player can violate different rules in three cycles and still achieve a draw. In contrast, Western-chess rules always define a game as a draw after three consecutive loops. This paper reports on an adequate implementation of the Chinese-chess rules used to decide the outcome of a game when it falls into loops. The rules are proposed by the Asia Chinese-Chess Association.

This paper contains three contributions. First, it introduces a new family of k-in-a-row games, Connect(m,n,k,p,q). In Connect(m,n,k, p,q), two players alternately place p stones on an m ×n board in each turn, except for the start when the first player places q stones at her first move. The player who first obtains k consecutive stones of her own first wins. The traditional game five-in-a-row, also called Go-Moku, in the free style is Connect(15,15,5,1,1). For brevity, Connect(k,p,q) denotes the game Connect(∞,∞,k,p,q), played on infinite boards.

Second, this paper analyzes the characteristics of these games, especially for the fairness. In the analysis of fairness, we first exclude the ones which are apparently unfair or solved. Then, for the rest of games, we argue that p=2q is a necessary condition for fairness in the sense that one player always has q more stones than the other after making a move. Among these games, Connect(6,2,1) is most interesting to this paper and is named Connect6.

Third, this paper proposes a threat-based strategy to play Connect(k,p,q) games and implements a computer program for Connect6, based on the strategy. In addition, this paper also illustrates a new null-move search approach by solving Connect(6,2,3) where the first player wins. The result also hints that for Connect6 the second player usually should not place the initial two stones far away from the first stone played by the first player.

This paper presents novel and systematic algorithms to solve a variant of the Mastermind game, which is called “Mastermind with a Lie”. Firstly, we use the k-way-branching(KWB) algorithm to get an upper bound of the number of guesses for the problem. With the help of clustering technique, the KWB algorithm is able to obtain near-optimal results effectively and efficiently. Secondly, we propose a fast backtracking(PPBFB) algorithm based on the pigeonhole principle to get the lower bounds of the number of guesses. That is a computer-aided approach, which is able to estimate the depth of the game tree and to backtrack when the depth is larger than a predefined value. Moreover, we also develop two novel methods, named “volume-renewing” and “preprocessing”. They can improve the precision in the estimation of the lower bound and speed up the game tree search. As a result of applying the KWB algorithm and the PPBFB algorithm, we are able to show that the upper bound is 7 and that is also the lower bound. Thus, the problem is solved completely and the exact bound of the number of guesses for the problem is 7.

Multi-player games, however, have been investigated considerably less, and although literature of game theory fills books about equilibrium strategies in such games, practical experiences are rare. Recently, Korf, Sturtevant and a few others started highly interesting research activities. We focused on investigating a four-person chess variant, in order to understand the peculiarities of multi-player games without chance components. In this contribution, we present player models and search algorithms that we tested in the four-player chess world. As a result, we may state that the more successful player models can benefit from more efficient algorithms and speed, because searching more deeply leads to better results. Moreover, we present a meta-strategy, which beats a paranoid α-β player, the best known player in multi-player games.

Probabilistic combinatorial games (PCGs) are a model for Go-like games recently introduced by Ken Chen. They differ from normal combinatorial games since terminal positions in each subgame are evaluated by a probability distribution. The distribution expresses the uncertainty in the local evaluation. This paper focuses on the analysis and solution methods for a special case, 1-level binary PCGs. Monte-Carlo analysis is used for move ordering in an exact solver that can compute the winning probability of a PCG efficiently. Monte-Carlo interior evaluation is used in a heuristic player. Experimental results show that both types of Monte-Carlo methods work very well in this problem.

A sumber is a sum of ups, downs and star. Sumbers can describe the positions of many partisan infinitesimal games. Earlier, we provided a simplification rule [6] that can determine whether a game G is a sumber or not, and if it is, determine the exact sumber of G from its left and right options, G ^L and G ^R . This article extends the previous result and presents three variations of colored heap games; each of them can be solved by sumbers.

The paper presents a method to simulate the physics of the game of pool. The method is based upon a parametrization of ball motion which allows the time of occurrence of events, such as collisions and transitions between motion states, to be solved analytically. It is shown that the occurrences of all possible events are determined as the roots of polynomials up to fourth order, for which closed-form solutions exist. The method is both accurate, returning continuous space solutions for both time and space parameters, and efficient, requiring no iterative numerical methods. It is suitable for use within a game tree search, which requires a great many potential shots to be modeled efficiently, and within a robotic pool system, which requires a high accuracy in predicting shot outcomes.

The paper describes optimization principles to produce a computer pool player. A good player has technical and planning abilities. Technically, he sinks balls with precision, and controls the position of the cue ball after the shot. He uses his technical abilities to devise a game plan, sinking the balls in a winning order.

We propose to use the optimization techniques in such a way that it simulates an excellent player. In this paper, we focus on the technical abilities. We provide optimization models to compute the shots to not only sink a given ball, but bring the cue ball at a specified target. Some hints on planning optimization strategies are given.