Catálogo de publicaciones - libros

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.

Endgame databases have previously been built based on complete analysis of endgame positions. In the domain of Checkers, where endgame databases consisting of 39 positions have already been built, it would be beneficial to be able to build select portions of even larger databases, without fully computing portions of the database that will almost never be needed. We present a new win-loss-draw value algorithm that can build endgame databases when unknown (partial information) values are present, showing that significant portions of these databases can be resolved using these methods.

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 , a system for automatically selecting enhancements for search. 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.

In this paper we introduce a new pruning mechanism, called for Probabilistic Opponent-Model (PrOM) Search. It is based on imposing a bound on the differences between two or more evaluation functions. Assuming such a bound exists, we are able to prove two theoretical properties, viz., the bound-conservation property and the bounded-gain property. Using these properties we develop a Similarity-Pruning algorithm. Subsequently we conduct a series of experiments on random game trees to measure the efficiency of the new algorithm. The results show that Similarity Pruning increases the efficiency of PrOM search considerably.

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.

Seki is a situation of coexistence in the game of Go, where neither player can profitably capture the opponent’s stones. This paper presents a new method for deciding whether an enclosed area is or can become a seki. The method combines local search with global-level static analysis. Local search is used to identify possible seki, and reasoning on the global level is applied to determine which stones are safe with territory, which coexist in a seki and which are dead. Experimental results show that a safety-of-territory solver enhanced by this method can successfully recognize a large variety of local and global scale test positions related to seki. In contrast, the well-known program GNU can only solve easier problems from a test collection.

Progressive Pruning (PP) is employed in the Monte-Carlo Go-playing program . 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, and , 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.

This paper discusses the intricacies of a Phantom-Go program. It is based on a Monte-Carlo approach. The program called plays Phantom Go at an intermediate level. The emphasis is on strategies, tactical search, and specialized knowledge. The paper provides a better understanding of the fundamentals of Monte-Carlo search in Go.

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 can handle inversions efficiently compared to previous algorithms by making passes for both players. We implemented dual -search with 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.