Catálogo de publicaciones - libros

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 -in-a-row games, (,,,,). In Connect(,,, ,), two players alternately place stones on an × board in each turn, except for the start when the first player places stones at her first move. The player who first obtains 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(,,) denotes the game Connect(∞,∞,,,), 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 =2 is a necessary condition for fairness in the sense that one player always has 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 .

Third, this paper proposes a threat-based strategy to play Connect(,,) 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 (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 (PPBFB) algorithm based on the 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.

For a long period of time, two person zero-sum games have been in the focus of researchers of various communities. The efforts were mainly driven by the fascination of special competitions such as vs. Kasparov, and of the beauty of parlor games such as Checkers, Backgammon, Othello, and Go.

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 is a sumber or not, and if it is, determine the exact sumber of from its left and right options, and . 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 , returning continuous space solutions for both time and space parameters, and , 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.